Принципы перехода от последовательного алгоритма к параллельному. Алгоритм преобразования последовательного алгоритма в параллельный

Параллельный алгоритм – это описание про­цесса обработки информации, ориентированного на реализацию с помощью вычислительных систем.

Представление параллельного алгоритма на языке программирования, доступном данной ВС, называется парал­лельной программой.

Существует 3 способа распараллеливания сложных задач:

1. Локальное. При локальном распараллеливании в выполняемой программе выделяются участки машинных команд, которые могут выполняться параллельно.

2. Глобальное. Глобальное распараллеливание происходит на уровне программных модулей.

3. Смешанное распараллеливание – наиболее эффективное, совмещает 1 и 2.

Приведение схем алгоритмов к виду, удобному для органи­зации параллельных вычислений. При создании параллельных программ будем использовать схемы программ в соответствии с ГОСТ 19.003-80 ЕСПД, ГОСТ 19.701-90 ЕСПД.

Вначале создается схема алгоритма, как это делалось для тра­диционных вычислительных средств без учета параллельных вы­числений. Будем называть такие алгоритмы последовательными. Затем с помощью алгоритма преобразования последовательного алгоритма в параллельный на основе анализа зависимости участков процесса по обрабатываемым переменным выделяются параллель­ные ветви вычислений. Алгоритмы с выделенными параллельными ветвями и есть параллельные алгоритмы.

Введем несколько ограничений на изображение схем алгорит­мов с параллельными ветвями:

1.При параллельном выполнении программ окончание алгорит­ма зависит от составленного плана решения задачи, поэтому символ «терминатор» конца алгоритма надо исключить.

2.Не ограничивая общности рассуждений, можно считать, что при изображении параллельных алгоритмов можно ограничиться логическим символом с двумя выходами: FALSE и TRUE.

3.Традиционное изображение вводимой информации в указан­ных ГОСТах более или менее приемлемо для ВС с общей памятью и совсем не приемлемо для ВС с разделяемой памятью, так как в этих ГОСТах вводится достаточно искусственная зависимость программных модулей по данным. Эта зависимость существен­но сужает возможности распараллеливания решаемой задачи. При рассмотрении ВС с разделяемой памятью ввод-вывод информации включается в процесс обмена информацией между процессорами и таким образом учитывается в планировании вычислительного процесса.

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

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

Разобьем последовательный алгоритм на линейные участки, заключенные между логическими операторами. Каждый логиче­ский оператор порождает не менее двух линейных участков. Ли­нейный участок, образованный входом в алгоритм и логическим оператором, назовем начальным. Начальный участок может со­держать только один оператор. Следующий за начальным участок начинается и заканчивается логическим оператором, т. е. если уча­сток Ui, состоит из множества операторов , то следующий участок и т. д., где — логические операторы, причем , а — некоторые операто­ры (не логические). Таким образом, последний логический оператор участка U_i, является первым оператором для участка U_i+1. На каждом участ­ке операторы перенумерованы: 1,2, …, U_k. Последние участки — это линейные участки, не имеющие в качестве последнего опера­тора логический оператор. Пусть в результате такого разбиения образовалось N участков k = 1,..., N, в каждом из которых оказа­лось U_k операторов.

Назовем связи, входящие в вычислительный или логический блоки, входными; выходящие из этих блоков — выходными. Будем полагать, что в каждый блок может входить и выходить несколько связей. В анализируемом алгоритме для упрощения анализа зави­симости рассматриваемого программного модуля от предыдущих принята следующая схема: анализируемый алгоритм представляет собойпоследовательность программных модулей (процедур и/или функций). Обмен данными между ними происходит только через параметры, указанные в списке при вызове модулей. Результаты ра­боты модули передаются через параметры, формируемые как <имя параметра>::=<префикс> <имя модуля>. Очевидно, что предлагаемое упрощение не является принципи­альным и в случае необходимости легко можно учесть зависимости программных модулей по данным, осуществляемые с помощью по­нятий глобальных переменных различных уровней.

Алгоритм: Преобразование последовательного алгоритма в параллельный.

1. Разобьем последовательно алгоритм на N линейных участ­ков: k = 1,..., N, исключив при этом терминаторы начала, конца и ввода-вывода информации. Перенумеруем сначала участок при k=1: U_k= 1,..., . Так как первый блок является входом в алго­ритм, то положим МV:= {1} — множество входов в алгоритм.

2. Примем := 1.

3. Вычислим , Flag:= False (переменная Flag фиксирует проведение очередной связи).

4. Если > , то проверим, все ли блоки имеют выходные связи. Если да, то переходим к шагу 7, иначе проведем связи из бло­ков, не имеющих выходных связей, в блок и перейдем к шагу 7. Если ≤ , то выполняется следующий шах.

5. Если блок использует результаты работы блока , то про­ведем связь из блока в , положим Flag:= True и перейдем к шагу 3. Иначе выполняется следующий шаг.

6. Вычислим . Если , то переходим к шагу 5, иначе, если k= 1 и Flag:= False, принимаем как еще один вход в алгоритм . Если k > 1 и Flag:= False, то проводим связь из блока в . Переходим к шагу 3.

7. Вычислим k:= k + 1. Если k > N, то определяется коней алгоритма, иначе переходим к шагу 2