Программирование для параллельных вычислительных систем

Классификация Хэндлера

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

• уровень выполнения программы — опираясь на счетчик команд и некоторые другие регистры, устройство управления (УУ) пр
• уровень битовой обработки — все элементарные логические схемы процессора (ЭЛС) разбиваются на группы, необходимые для выполнения операций над одним двоичным разрядом.

Подобная схема выделения уровней предполагает, что вычислительная система включает какое-то число процессоров каждый со своим устройством управления. Если на какое-то время не рассматривать возможность конвейеризации, то число устройств управления k, число арифметико-логических устройств d в каждом устройстве управления и число элементарных логических схем w в каждом АЛУ составят тройку для описания данной вычислительной системы C: (k, d, w)

где   k — число УУ,

d — число АЛУ в каждом УУ,

w — число разрядов в слове, обрабатываемых в АЛУ параллельно.

Классификация Скилликорна

Классификация Скилликорна (1989) была очередным расширением классификации Флинна. Архитектура любого компьютера в классификации Скилликорна рассматривается в виде комбинации четырёх абстрактных компонентов: процессоров команд (Instruction Processor — интерпретатор команд, может отсутствовать в системе), процессоров данных (Data Processor — преобразователь данных), иерархии памяти (Instruction Memory, Data Memory — память программ и данных), переключателей (связывающих процессоры и память). Переключатели бывают четырёх типов — «1-1» (связывают пару устройств), «n-n» (связывает каждое устройство из одного множества устройств с соответствующим ему устройством из другого множества, то есть фиксирует попарную связь), «n x n» (связь любого устройства одного множества с любым устройством другого множества). Классификация Скилликорна основывается на следующих восьми характеристиках:

• Количество процессоров команд IP
• Число ЗУ команд IM
• Тип переключателя между IP и IM
• Количество процессоров данных DP
• Число ЗУ данных DM
• Тип переключателя между DP и DM
• Тип переключателя между IP и DP
• Тип переключателя между DP и DP

 

 

Глава 3. Программирование для параллельных вычислительных систем

 

3.1 Параллельная форма алгоритма

Для реализации алгоритма на параллельной системе его следует представить в виде последовательности групп операций.

Отдельные операции в каждой группе должны обладать следующим свойством: их можно выполнять одновременно на имеющихся в системе функциональных устройствах.

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

Представление алгоритма в таком виде называется параллельной формой алгоритма. Каждая группа операций называется ярусом, а число таких ярусов – высотой параллельной формы. Максимальное число операций в ярусах (число привлекаемых процессов в ярусах) — шириной параллельной формы.

Один и тот же алгоритм может иметь много параллельных форм. Формы минимальной высоты называются максимальными.

3.2 Представление и реализация алгоритмов

Реализация алгоритма на вычислительной системе — это реализация базовой программы эквивалентным способом. Поэтому (явно или неявно) должны быть определены:

— функция, устанавливающая взаимно однозначное соответствие между вершинами графа алгоритма и отдельно срабатываниями функциональных устройств вычислительной системы;

— потоки информации между функциональными устройствами системы;

— моменты включения функциональных устройств.

Имеются две основные стратегии при решении этих задач:

— статическая;

— динамическая.

При статической стратегии решение принимается заранее на основе анализа алгоритма и вычислительной системы, а при динамической стратегии решение принимается в процессе реализации.

Динамическая стратегия характеризует так называемые потоковые линии. Иногда используют смешанные стратегии.

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

Соответствие, которое устанавливает упомянутая выше функция между алгоритмом и срабатываниями системы, чрезвычайно важна: ее неудачный выбор может оказаться первой причиной несрабатывания алгоритма. Важно также, чтобы класс "удачных" функций был достаточно широк; иначе, например, может случиться, что в этом классе нет приемлемой функции, которая дает программу с допустимым временем реализации.

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

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

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

Определение 1.1. Последовательности с максимальным из минимальных времен выполнения называются максимальными последовательностями.

Благодаря теореме 1.2 легко устанавливаем следующее утверждение.

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

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

Определение 1.2. Режим называется синхронным, если моменты включения функциональных устройств создают равномерную сетку на оси времени, и асинхронным — в противном случае.

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

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

 

 

3.3 Модели программирования

 

Традиционной считается последовательная модель программирования (Рис.1). В этом случае в любой момент времени выполняется только одна операция и только над одним элементом данных. Последовательная модель универсальна. Ее основными чертами являются применение стандартных языков программирования (для решения вычислительных задач это, обычно, Fortran и С/С++), хорошая переносимость программ и невысокая производительность.

Рис.1 Модель последовательного программирования

Основными особенностями параллельной модели программирования являются более высокая производительность программ, применение специальных приемов программирования и, как следствие, более высокая трудоемкость программирования, проблемы с переносимостью программ. Параллельная модель не обладает свойством универсальности (Рис. 2).

Рис.2 Модель параллельного программирования

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

Повышенная трудоемкость параллельного программирования связана с тем, что программист должен заботиться:

• об управлении работой множества процессов;
• об организации межпроцессных пересылок данных;
• о вероятности тупиковых ситуаций (взаимных блокировках);
• о нелокальном и динамическом характере ошибок;
• о возможной утрате детерминизма ("гонки за данными");
• о масштабируемости;
• о сбалансированной загрузке вычислительных узлов.

 

3.4 Парадигмы параллельного программирования

Параллелизм данных

• одна операция применяется сразу к нескольким элементам массива данных. Различные фрагменты такого массива обрабатываются на векторном процессоре или на разных процессорах параллельной машины;
• обработкой данных управляет одна программа;
• пространство имен является глобальным;
• параллельные операции над элементами массива выполняются одновременно на всех доступных данной программе процессорах.

От программиста требуется:

• задание опций векторной или параллельной оптимизации транслятору;
• задание директив параллельной компиляции;
• использование специализированных языков параллельных вычислений, а также библиотек подпрограмм, специально разработанных с учетом конкретной архитектуры компьютера и оптимизированных для этой архитектуры.

Параллелизм задач

• вычислительная задача разбивается на несколько относительно самостоятельных подзадач. Каждая подзадача выполняется на своем процессоре (ориентация на архитектуру MIMD);
• для каждой подзадачи пишется своя собственная программа на обычном языке программирования (чаще всего это Fortran или С);
• подзадачи должны обмениваться результатами своей работы, получать исходные данные. Практически такой обмен осуществляется вызовом процедур специализированной библиотеки. Программист при этом может контролировать распределение данных между различными процессорами и различными подзадачами, а также обмен данными.

 

Заключение

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

1) любая задача распараллеливается лишь частично (при полном распараллеливании параллельные части не могут взаимодействовать в процессе счета и представляют собой отдельные задачи меньшего размера, так что использование параллельной системы теряет смысл);