Параллельное программирование: Учебное пособие, страница 25

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

Из всех рассмотренных способов выполнения итераций цикла наиболее проблематичными являются случаи, когда индексное множество включает группы функционально связанных друг с другом индексов. В многомерных циклах (рис. 2.8) эта взаимосвязь может функционально связывать индексы разных уровней вложения. Два подхода к распараллеливанию таких циклов детально рассмотрены в [******?*****].

2.3  Формальные методы распараллеливания.

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

2.3.1  Графовая модель параллельных процессов.

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

Абстрактное понятие ориентированного по направлению ребра или дуги однозначно может быть закреплено за направлением передачи выработанных данных (информации) от одной вершины к другой. Это связано с тем, что в параллельных программах исполнение того или иного оператора или команды инициируется моментом готовности входных данных, размещенных в нужном месте процессами (вершинами), вырабатывающими и поставляющими эти данные. Число входящих и выходящих из вершины ребер является важной характеристикой вершины.

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

Характер взаимосвязи абстрактных вершин и абстрактных ориентированных ребер является отображением одного множества на другое, семантикой которого для параллельного программирования может служить какая-либо параллельная форма алгоритма решения задачи.

Таким образом, нами определены все абстракции, которые необходимы для применения к анализу параллельных алгоритмов методов теории графов. Применительно к задачам параллельного программирования описанную абстрактную модель параллельного вычислительного процесса называют графом информационной зависимости (ГИЗ).

2.3.2  Описание графов информационной зависимости

Для визуального изображения ориентированного графа (орграфа) G будем использовать в качестве вершин зачерненные кружочки, в качестве направленных ребер – стрелки, а отображение множества дуг на множество вершин – соединением конкретных вершин соответствующей дугой.