Концепция неограниченного параллелизма.
На начальном этапе проектирования параллельного программирования целесообразно использовать так называемую концепцию «неограниченного параллелизма», которая предполагает решение задачи на идеализированной вычислительной системе без учета ограничений реальной вычислительной системы.
Делается предположение, что параллельный алгоритм будет реализован на вычислительной системе, которая не накладывает на него никаких других ограничений кроме числа доступных обрабатывающих устройств. Тогда объектами исследования остаются только высота и ширина параллельной формы.
Идеализированная вычислительная система состоит из необходимого числа обрабатывающих устройств и оперативной памяти произвольного размера, одновременно доступной все обрабатывающим устройствам. Никакие конфликты при обращении к памяти не возникают.
Точность выполнения операций так же не учитывается.
Концепция «неограниченного параллелизма» применяется на уровне исследования задачи в целом, позволяет оценить минимально достижимую высоту и загруженность процессоров в системе.
Применение этой концепции включает следующие этапы:
Расщепление исходной задачи на большие независимые подзадачи.
Выделение к каждой полученной подзадачи большого потока независимых однотипных подзадач.
Дальнейшее рекурсивное расщепление подзадач до тех пор, пока не будут получены типовые математические задачи.
Если типовых задач получается достаточно много и они настолько большие, что можно пренебречь временем обмена данными между ними, то дальнейшее распараллеливание не осуществляется, так как вся задача целиком эффективно решается на системах класса MIMD.
Если все полученные задачи однотипные, то более выгодной может оказаться решение задачи в целом на системах класса SIMD.
Описанный подход называется крупноблочным распараллеливанием.
Реальное преимущество ПА для типовых задач достигается только при достаточно большом количестве процессоров. Дальнейшее ускорение может быть получено только при распараллеливании типовых математических задач. В настоящее время основное внимание в области параллельных вычислений уделяется созданию методов выявления параллельных структур в традиционных последовательных алгоритмах.
Методы преобразования последовательных алгоритмов в параллельную форму.
Любой последовательный алгоритм можно представить в виде совокупности участков 3 типов:
Линейные участки, которые содержат только последовательно выполняемые операторы, а так же операторы условного и безусловного перехода;
Выражения (в т.ч. рекуррентные соотношения);
Циклические участки (циклы).
Наибольших выигрыш получается при распараллеливании циклических участков.
Область применения, достоинства, недостатки метода гиперплоскостей.
*В этом методе пространство итераций, выполняемых параллельно, представляется в виде семейства параллельных гиперплоскостей. Метод дает линейные выражения для преобразования индексов в теле цикла таким образом, чтобы для каждой полученной в результате преобразования гиперплоскости было возможно одновременное независимое выполнение всех итераций, принадлежащих этой гиперплоскости.
Метод предполагает использование сложного математического аппарата. Лучше использовать в системах MIMD.
Смысл: найти уравнения таких плоскостей, для всех точек которых можно вести параллельный счет. Критерий правильности: совпадение результатов параллельного и последовательного счета и как таковые параллельные вычисления.
Пусть дан гнездовой циклический алгоритм вида:
DO 99 I=1,L
DO 99 J=2,M
DO 99 K=2,N
V(J,K)=(V(J+1,K)+V(J-1,K)+V(J,K-1)+V(J,K+1))*0,25