Лабораторные работы по информатике

Гуманитарные науки

У нас студенты зарабатывают деньги

 Дипломы, работы на заказ, недорого

 Контрольные работы

Контрольные работы

 Репетиторы онлайн по английскому

Репетиторы онлайн по английскому

Приглашаем к сотрудничеству преподователей

Приглашаем к сотрудничеству преподователей

Готовые шпаргалки, шпоры

Готовые шпаргалки, шпоры

Отчет по практике

Отчет по практике

Приглашаем авторов для работы

Авторам заработок

Решение задач по математике

Закажите реферат

Закажите реферат

Практикум по физике Лабораторные работы по информатике Microsoft Visio Алгоритмические основы машинной графики AutoCAD
Практикум по механике и молекулярной физике
ОПРЕДЕЛЕНИЕ МОМЕНТА ИНЕРЦИИ
МАТЕМАТИЧЕСКИЙ МАЯТНИК
Физический маятник
ОПРЕДЕЛЕНИЕ МОДУЛЯ ЮНГА
ПОПЕРЕЧНЫЕ КОЛЕБАНИЯ СТРУНЫ
ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ВЯЗКОСТИ
ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ПОВЕРХНОСТНОГО НАТЯЖЕНИЯ
ОПРЕДЕЛЕНИЕ ВЛАЖНОСТИ ВОЗДУХА
ОПРЕДЕЛЕНИЕ АДИАБАТИЧЕСКОЙ ПОСТОЯННОЙ ВОЗДУХА
Вынужденные колебания линейного осциллятора
Лабораторные работы по информатике
Определение параметров n-мерных коммутационных структур
Преобразование последовательного алгоритма в параллельный
Представление алгоритмов в виде граф–схем.

Построение матрицы логической несовместимости операторов

Построение множеств взаимно независимых операторов
Определение ранних и поздних сроков окончания выполнения операторов
Запуск параллельных программ на кластере
Microsoft Visio
Спецификация требований к информационной системе
Основы работы в редакторе деловой графики Microsoft Visio 2010.
Лабораторная работа №3
Лабораторная работа №4
Функциональное моделирование
Диаграмма классов
Алгоритмические основы машинной графики

Анимация и морфинг

Отсечение прямоугольным окном
Построение проекции трехмерного объекта
Создание простых объектов
Основные навыки работы с объектами
Привязка объектов
Редактирование формы произвольных кривых
Приемы работы с контурами объектов
Создание цветных изображений
Обмен изображениями с другими программами
Ввод и редактирование текста
СИСТЕМА АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ AutoCAD
Основы работы с использованием системы AutoCAD
Команды рисования
Нанесение надписей
Команды редактирования
Проставление размеров на чертеже
Работа с блоками чертежа
 

Лабораторная работа №4. Построение матрицы логической несовместимости операторов

Цель работы – ознакомление с понятием логической несовместимости операторов, практическая реализация алгоритмов работы с матрицами логической несовместимости L в виде программных модулей.

Теоретическая часть

Для оценки возможности выполнения программных модулей параллельно, важную роль играют логически несовместимые операторы.

Рассмотрим множество вершин, принадлежащих n-ветви i-го логического оператора. Это множество назовем Mi.n. Аналогично построим множество вершин для дуги k – это множество вершин, принадлежащих k-ветви i-го логического оператора – множество MKi. В множества Mi.n и Mi.k сама вершина i не входит.

Определение 4.1. Если вершина p  Mi.n, а q  Mi.k и соответствующие им операторы могут выполняться либо один, либо другой при однократном выполнении алгоритма, то эти операторы называются логически несовместимыми.

При реализации алгоритма в логическом операторе i выполняется либо ветвь i.n, либо i.k. Следовательно, при планировании параллельных вычислений следует исключать планирование параллельного выполнения операторов, принадлежащих разным ветвям, т.е. попросту исключить их из планирования. Однако встречаются ситуации, когда ветви i.n и i.k пересекаются, т.е. Mi.n I Mi.k = Mi.nk  Ø.

Определение 4.2. Если Mi.nk  Ø, то существует внутреннее замыкание i-го логического оператора.

В этом случае операторы  могут планироваться для параллельного выполнения. На рисунке 4.1 приведён граф, в котором на вершине 6 произошло пересечение логических ветвей оператора 1. Операторы 6, 7, 9, 10 могут быть запланированы для параллельного выполнения.

Рисунок 4.1. Граф-схема ИЛГ с пересечением логических путей оператора 1

Определение 4.3. Вершина   и имеющая наименьший номер, называется минимальной внутренне замкнутой вершиной i-го логического оператора и обозначается inzi.

Так, для примера, представленного на рисунке 4.2, inz1 = 6.

Рисунок 4.2. Граф-схема алгоритма, имеющая замыкающие дуги и со стороны 1.1, и со стороны 1.2

Следует отметить, что замыкание логических путей может осуществляться за счет внешних информационных связей. Как показано на рисунке 4.3, замыкание может произойти за счет информационных связей путями, идущими от операторов 3 или 4. При этом должен существовать информационный путь к вершинам 3 или 4 от входа в алгоритм (вершина 1).

Рисунок 4.3. Граф-схема алгоритма с замыканием логических ветвей за счёт вершин, не принадлежащих путям оператора 2

Целесообразно рассматривать внешние замыкания для ветвей i.n и i.k отдельно. Это связано с тем, что при рассмотрении возможности параллельного выполнения операторов, включенных в логические ветви, необходимо учитывать результаты как внешнего, так и внутреннего замыканий совместно, имея в виду при этом, что возможно внешнее замыкание только одной ветви.

Определение 4.4. Если существует информационный путь в вершину  от начальной вершины граф-схемы, то вершина Z называется внешне замкнутой в n-ветви для i-го логического оператора. Если таких вершин несколько, то вершину Z с минимальным номером называют минимальной внешне замкнутой вершиной в n-ветви для i-го логического оператора.

Обозначим эту вершину ezi.n = xj.

Определение 4.5. Если множество   содержит внешнее замыкание ezi.n = xj, то подмножество  называется внешне замкнутым для n-ветви логического оператора Li.

При рассмотрении влияния внешних и внутренних замыканий для оценки возможности распараллеливания операторов, принадлежащих ветвям логического оператора, необходимо учесть, что:

внутреннее замыкание, как правило, порождает операторы, которые можно выполнять параллельно;

для возможности распараллеливания операторов, принадлежащих путям логического оператора, достаточно одного внешнего замыкания при наличии внутреннего;

определение множества MZi всех замкнутых операторов i-го логического оператора требуется вычислить объединение множеств: .

Ситуации, соответствующие пунктам 1 и 2, проиллюстрированы на рисунках 4.1, 4.2 и 4.3. На рисунке 4.4 рассмотрена ситуация, соответствующая пункту 3.

Рисунок 4.4. Пример граф-схемы, в которой внешнее замыкание ветви 2.1 уточняет множество операторов, подлежащих распараллеливанию

На рисунке 4.5 приведён алгоритм построения матрицы логической несовместимости операторов, в котором использованы следующие обозначения:

S – матрица следования;

RS – размерность матрицы S;

ST – матрица с транзитивными связями;

RST – размерность матрицы ST;

MLO – множество логических операторов;

RMLO – размерность множества логических операторов;

M – множество вершин операторов;

Mk.n – множество вершин операторов, принадлежащих путям, включающим дугу n k-го логического оператора;

Vk.g – множество вершин операторов, внешне замкнутых для k-го логического оператора связи G;

Mk.g – множество вершин операторов, принадлежащих путям, включающим дугу g k-го логического оператора;

RMk.n – размерность множества логических операторов ветви k.n;

RMk.g – размерность множества логических операторов ветви k.g;

Nk.g – множество вершин операторов, внутренне замкнутых для k-го логического оператора;

Vk.n – множество вершин операторов, внешне замкнутых для k-го логического оператора связи n;

MZk – объединенное множество внешних и внутренних замыканий для k-го логического оператора.

Рисунок 4.5. Схема алгоритма построения матрицы логической несовместимости операторов. Начало

Рисунок 4.5. Продолжение

Рисунок 4.5. Окончание

Процедура PMLO.

Признаком логического оператора матрицы S является появление в соответствующем столбце значений j.n или j.g.

Алгоритм 4.1. Получение множества логических операторов.

В матрице S, размера RS выбираем первый столбец (j := 1),  RMLO := 0, MLO := Ø.

Просматриваем j-й столбец по строкам и определяем равенство текущего элемента матрицы j.n или j.g.

Если найден такой элемент, то полагаем , j := j+1.

Если j  RS,то переходим к шагу 2, иначе – конец алгоритма.

Конец алгоритма.

Процедура PMNG.

Для получения множеств Mk.n и Mk.g k-го логического оператора необходимо просмотреть k-й столбец и включить во множество MN номера операторов, которые в соответствующих строках имеют значение k.n, а во множество MG – номера операторов, которые в соответствующих строках имеют значение k.g.

Алгоритм 4.2. Получение множеств Mk.n и Mk.g k-го логического оператора.

В соответствии со значением k, выбираем элемент множества . В qk столбце матрицы ST просматриваем i-е строки, i := 1 (номер строки), l := 1 (номер позиции в множестве Mk.n), m := 1 (номер позиции в множестве Mk.g).

Если элемент матрицы SN(i, k) = j.n, то Mk.n[l] := i, l := l+1 и осуществляется переход к шагу 5.

Если SN(i, k) = j.g, то Mk.g[m] := i; m := m+1 и выполняется шаг 5.

Если условия пунктов 2 и 3 не выполняются, то осуществляется переход на шаг 5.

Вычислим i := i+1; если i > RST, то RMk.n := l, RMk.g := m и выполнение алгоритма заканчивается, иначе осуществляется переход на шаг 2.

Конец алгоритма.

Процедура PREZ.

Процедура PREZ формирует множество внешних замыканий для рассматриваемого логического оператора, используя свойства матрицы ST. Берётся i-ая строка матрицы ST, содержащая все нули (вход ИЛГ). Затем – для i-го столбца номера всех элементов, равных 1, фиксируются в множестве WZ. Если для рассматриваемого k-го логического оператора пересечения множеств  и  не пусты, то обнаружены внешние замыкания для ветвей k-го логического оператора (номера внешне замкнутых операторов входят в эти пересечения).

Алгоритм 4.3. Формирование множества внешних замыканий.

Формируем множество из номеров нулевых строк матрицы ST: ZS := {i1, ..., iq}. Полагаем Vk.n := Ø, Vk.g := Ø.

Для всех элементов ip  ZS строим множество EDp номеров строк, содержащих единичные элементы в ip столбцах.

Исключим из множества EDp, p = 1, …, q элементы, равные номеру рассматриваемого логического оператора k. Перенумеруем множества EDp, учитывая удаленные элементы. Получим множество EDu, u = 1, …, f, f < q. Если все EDu = Ø, то Vk.n := Ø, Vk.g := Ø.

Вычислим множества    где Mk.g и Mk.n – множества операторов для текущего вложенного оператора k.

Конец алгоритма.

Вопросы для самопроверки

Дайте определение логически несовместимых операторов.

Дайте определения внешних и внутренних замыканий.

Когда внешнее замыкание одной ветви сказывается на определенном множестве логически несовместимых операторов?

С какой целью вычисляется матрица логически несовместимых операторов?

Почему в алгоритме 4.3 анализируются только те столбцы матрицы ST, номера которых совпадают с номерами нулевых строк этой матрицы?

Почему учёт воздействия внешних замыканий на логическую несовместимость зависит от наличия или отсутствия внешних замыканий?

Задание на лабораторную работу

Используя программу, разработанную в предыдущей лабораторной работе, необходимо дополнить её следующими функциями:

Для заданного информационно-логического графа построить матрицу логической несовместимости операторов.

Выделить на исходном графе логически несовместимые вершины.

Продемонстрировать работающую программу преподавателю и получить отметку о её выполнении.

Сохранить копию программы для выполнения последующих лабораторных работ на дискете.

Оформить отчет о проделанной работе.

Содержание отчета

Цель работы.

Ответы на вопросы для самопроверки.

Схемы алгоритмов и их описание.

Распечатки экранных форм, полученных в результате работы программы.

Анализ полученных результатов.

Лабораторные работы