Преобразование последовательных программ в последовательно-параллельные
Задача распараллеливания. В любом полном рассмотрении вопросов параллельного программирования должны быть представлены способы получения параллельной программы из обычной алгоритмической записи, которая несет в себе след чисто последовательной логики рассуждений, так как любые вычисления, проводимые вручную и автоматически, выполнялись последовательно. Однако оказывается, что любой реальный процесс при детальном его рассмотрении выполняется параллельно. И чем внимательнее и детальнее мы постараемся его описать, тем больше это описание будет приближаться к параллельной форме. Следовательно, задача состоит в том, чтобы с помощью каких-то понятий научиться достаточно просто и полно описывать естественные параллельные процессы.
Сложность задачи распараллеливания во многом определяется языком, на котором записан исходный алгоритм. Наиболее просто это делать, если язык не содержит циклических структур. Примером таких языков можно назвать языки "геометрического описания деталей со сложной объемной конфигурацией". Это язык, в котором предложение – последовательность директив.
Как правило, основное время выполнения программ на обычных языках связано с реализацией циклов. Поэтому важной задачей является распараллеливание циклов.
Как указывалось выше, некоторые языки программирования имеют средства для описания параллелизма. Однако все параллельные фрагменты программы должны быть указаны явным образом. Более того, должна быть указана последовательность их выполнения, организована передача необходимых управлений и т. д.
При использовании языка PL/1, например, программист должен:
· выделить и пометить независимые фрагменты программы (с помощью операторов CALL и TASK, например);
· обеспечить синхронизацию при выполнении фрагментов (используя, скажем, оператор DELAY);
· осуществить взаимное управление фрагментами (операторы COMPLETE, WAIT, RETURN).
Следовательно, все трудности по организации параллельной обработки ложатся на программиста, так как он, по-существу, должен предварительно написать весь "сценарий" прохождения задачи через компьютер в параллельном режиме.
На разработку математического и программного обеспечения, согласно различным литературным источникам, тратится от 70 до 90 % всех затрат на создание ВС. Это одна из основных причин, почему необходимо эффективно использовать накопившееся обеспечение для однопроцессорных ЭВМ при переходе к МВС. Математическое и программное обеспечение следует адаптировать для новых ВС. Таким образом, рождается актуальная проблема – преобразование последовательных программ в последовательно-парал-лельные. Но так как эта работа необычайно трудоемка, ее следует автоматизировать. Решение указанной проблемы позволяет, во-первых, высвободить большие трудовые ресурсы, во-вторых, использовать накопленный за долгие годы развития ЭВМ информационно-программный багаж без ручного перепрограммирования и, в-третьих, осуществить переход на многопроцессорные системы с меньшими затратами труда и времени.
Распараллеливание программ можно осуществлять как на уровне отдельных задач, так и на уровне отдельных процедур, операторов, операций и микроопераций. Целесообразность преобразования на указанных уровнях должна решаться в каждом отдельном случае в зависимости от структуры ВС, типа программы и цели, которая ставится при ее решении.
Рассмотрим общую схему преобразования последовательных программ в последовательно-параллельные. Организовать параллельные вычисления можно с помощью некоторой формальной процедуры, выполняемой автоматически над каждой программой, состоящей из последовательности операторов обычного ЯП. Эта процедура позволяет избавить программиста от анализа собственной программы и помогает выявить ее внутренний параллелизм. Выявление параллелизма заключается в разбиении всех операторов программ на два класса: тех, которые могут выполняться параллельно, и тех, которые должны быть завершены прежде, чем следующие последовательности операторов начнут выполняться.
Такой подход к распараллеливанию основывается на представлении программы в виде ориентированного графа G, множество вершин которого V = {v1, v2, ..., vn} соответствует либо отдельным операторам программы, либо совокупности этих операторов (типа подпрограмм в языке ФОРТРАН либо процедур в языке АЛГОЛ или ПАСКАЛЬ).
Множество направленных дуг U = {u1, u2, ..., um} соответствует возможным переходам между операторами программы.
Из теории графов известно, что ориентированный граф полностью описывается соответствующей матрицей смежности такой, что ее элемент
|
ì 1, если существует дуга (ui,uj); |
|
|
Сij = |
í |
|
|
î 0, если такой дуги нет. |
 |
Рис. 10.3. Сильносвязный подграф
Подграфу, представляющему собой последовательность различных вершин, каждая из которых имеет единственную входную и единственную выходную вершины, будем ставить в соответствие линейный участок в
программе.
Итак, ставится задача – преобразовать алгоритм решения задачи, заданный последовательной программой, для параллельной его реализации на многопроцессорной вычислительной системе.
Для преобразования программы из одной (последовательной) формы в другую (последовательно-параллельную) мы используем ее интерпретацию в виде орграфа. Вообще говоря, идея использовать некоторый "формализм" в качестве посредника для преобразования программ встречалась и раньше в связи с другими задачами. Так, в трансляторе системы АЛЬФА был введен дополнительный проход, во время которого по исходной программе строилась ее модель в виде схемы Лаврова, что позволило обнаруживать и анализировать информационные связи в целях глобальной экономии памяти.
Построим схему алгоритма распараллеливания программ, используя некоторые сведения из теории графов.
