ИНФОРМАЦИОННЫЕ ГРАФЫ АЛГОРИТМОВ

5.1 Ключевые (основные) вопросы (моменты)

— информационный граф;

— параллелизм ветвей.

5.2 Текст лекции

5.2.1 Информационный граф

Наглядное представление алгоритма задачи дает информационный граф G (V, L) – ориентированный мультиграф с множеством вершин (узлов) V, связанных между собой множеством дуг (рёбер) L (рис.4.2).

В информационном графе узлы поставлены в соответствие операторам, а дуги – информационным связям. На входы каждого узла подаются входные переменные D, а на выходах после выполнения соответствующей операции формируются выходные результаты R. Таким образом, каждой вершине ставится в соответствие операция, имеющая столько аргументов, сколько дуг входит в эту вершину. Выходные результаты любого узла могут быть использованы в качестве входных для следующего узла. Отдельная вершина графа может представлять как отдельные элементарные операции, так и различные по сложности фрагменты программы.

Информационный граф позволяет выявить зависимости по данным. На рис.4.2 операнды D₁, D₂, D₃, D₄, D₅ соответствуют исходным данным, а R₅ и R₆ – окончательным результатам. Видно, что результат R₆ не может быть получен одновременно или до выполнения оператора вычисляющего значение R₁, при этом операторы, вычисляющие R₁ и R₅, находятся в отношении безразличия, то есть получают исходные операнды не зависимо друг от друга. Группы операторов (ветви графа), не использующие взаимно выходные и промежуточные результаты, могут быть выделены в независимые подграфы G_i (рис.4.3).

		Рис.4.3

Если выходные результаты ветвей R_i используются для выполнения последующих операций v_s, то имеет место параллелизм независимых ветвей,при котором вместо потока не связанных между собой задач, реализуются совмещенные во времени этапы выполнения одной задачи. Реализация параллелизма ветвей связана с решением проблемы программирования этапов и выделения ветвей, при этом должны быть предусмотрены средства синхронизации ветвей, то есть механизмы перехода к выполнению следующей ветви, например G₄, только после завершения предшествующих ветвей G₁ и G₂ (рис.4.3). Выявление готовых к исполнению параллельных ветвей происходит на этапе выполнения общей для них задачи.

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

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

Можно осуществить слияние вершин независимых ветвей, то есть заменить множество вершин каждой ветви более сложными операциями. Замена совокупности представленных на графе примитивных операций сложной операцией основана на свойстве вложенности описания алгоритма. Благодаря этому свойству, например, совокупность операций, представленных на графе рисунка 4.2, может быть заменена обобщенной операцией G (рис.4.4). Слияние узлов, уменьшая степень детализации алгоритма, позволяет осуществить переход к его более компактной форме записи.

6 Лекция №5

Дата добавления: 2014-11-24; просмотров: 424; Нарушение авторских прав

Мы поможем в написании ваших работ!