ПРИНЦИПЫ ПЕРЕХОДА ОТ ПОСЛЕДОВАТЕЛЬНОГО АЛГОРИТМА К ПАРАЛЛЕЛЬНОМУ. АЛГОРИТМ ПРЕОБРАЗОВАНИЯ ПОСЛЕДОВАТЕЛЬНОГО АЛГОРИТМА В ПАРАЛЛЕЛЬНЫЙ.

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

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

Существует 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 операторов.

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