Технологии распараллеливания.
Первоисточник: http://www.spbcas.ru/cfd/techn/Parallel.htm

Аннотация

Зачем это нужно?

Бурный прогресс в развитии вычислительной техники привел не только к росту производительности процессоров и объема оперативной памяти компьютеров, но и сделал их общедоступным и сравнительно недорогим средством, применяемым в различных сферах человеческой деятельности. Высокопроизводительная вычислительная техника, ранее доступная ученым и военным пришла и в сугубо "мирные" отрасли. Производители компьютеров предлагают широкий спектр техники оснащенной средствами параллельной обработки данных. Сразу оговоримся, что речь идет не о настольных компьютерах, а о системах более производительных - от так называемых корпоративных серверов до суперкомпьютеров. Опыт создания и эксплуатации параллельных машин говорит о том, что, как правило, переход от однопроцессорной конфигурации к многопроцессорной системе из N процессоров не приводит к сокращению времени счета в N раз. Иными словами вычислительная мощность параллельной системы используется лишь частично и может возникнуть вопрос - нужно ли задействовать подобную систему для решения задачи, если ее вычислительная эффективность в параллельном режиме вычислений низкая? Можно утверждать, что одно из условий создания хорошо распараллеленной программы это правильно составленный алгоритм решения задачи за что целиком и полностью отвечает программист. Разумеется нельзя сбрасывать со счетов аппаратные и системные средства параллельной обработки, но они играют вспомогательную роль, основная работа ложится на человека. Далее вкратце будут рассмотрены типы архитектур современных компьютеров и какие особенности с точки зрения программирования имеет распараллеливание на данных типах машин.

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

Парк современных высокопроизводительных машин можно разделить на два типа:

- векторно-конвейерные;

- массивно-параллельные.

1.1 Векторно-конвейерные компьютеры

Векторно-конвейерные ЭВМ относятся к так называемому классу SIMD-машин (single instruction multiply data - один поток команд много потоков данных) , массивно-параллельные к MIMD - компьютерам (multiply instruction multiply data много потоков команд много потоков данных).

Данной операции присущ параллелеризм - сложение элементов массивов A(i) и B(i) есть независимые процессы, которые могут исполняться параллельно. В алгоритмических языках высокого уровня (C, Fortran, Pascal и т.п.) существуют специальные операторы цикла, необходимые для исполнения данного суммирования:

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

1.2 Массивно-параллельные компьютеры

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

MIMD- компьютер представляет собой набор процессорных узлов (processor node), состоящих как минимум из одного процессора и приданного этому процессору банка памяти. Процессорные узлы соединены между собой в единую систему с помощью высокоскоростной шины или коммутатора, по сути компьютер представляет собой сеть из процессорных элементов. По типу организации доступа к памяти массивно-параллельные компьютеры делятся на машины с распределенной памятью (distributed memory) и машины с общей или разделяемой памятью (shared memory).

Остановимся поподробнее на двух типах доступа к памяти.

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

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

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

Подытожим информацию об архитектурных типах современных машин:

SIMD -компьютеры:

Под это понятие, строго говоря попадают векторно-конвейерные машины с одним процессором. В настоящее время в подобных системах используют мультипроцессорную обработку данных, т.е. количество векторных процессоров составляет величину от 2 до 16 и более. Такие компьютеры попадают под классификацию MIMD машин, однако основной вклад в ускорение программ, эксплуатирующихся на подобных системах, дают векторные средства обработки, параллелеризм является лишь дополнительным средством. Как правило векторный процессор обладает очень высокой производительностью в сотни MFlops.

MIMD - компьютеры:

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

Для программиста SIMD и MIMD- машины с разделяемой памятью представляют собой компьютер с глобально адресуемым адресным пространством.

MIMD- машина с распределенной памятью имеет локальную адресацию памяти в каждом процессорном узле. Для межпроцессорных коммуникаций необходимо применять специальные средства.

2. Методы распараллеливания

Один из архитекторов системы IBM/360 Амдаль (G.Amdahl) в 1967 году сформулировал закон в виде следующего постулата: "Производительность вычислительной системы определяется самым медленным ее компонентом". Если предположить, что p - относительное время, затрачиваемое последовательными командами в программе ( 1-p соответственно время исполнения параллельных

инструкций), то максимальное теоретическое ускорение s за счет распараллеливания в системе из N процессоров может быть рассчитано по следующей формуле:

Используя закон Амдаля можно сделать верхнюю оценку ускорения: например, при доле последовательных операций в программе p=10% невозможно получить ускорение s выше 10, а при р=50% s < 2, причем получаемые предельные ускорения не зависят от числа процессоров N.

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

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

- векторизация;

- распараллеливание.

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

Данный метод распараллеливания применяется только на векторно-конвейерных машинах и имеет существенное ограничение - векторизации подлежат только циклы с заранее известным количеством итераций. Д. Кнутом (D.E.Knuth) было проанализировано большое количество программ на языке Fortran и было установлено, что в среднем циклы занимают менее 4% кода, но требуют на выполнение более 50% счетного времени. Таким образом кажущаяся ограниченность векторизации не является большим недостатком для алгоритмов, содержащих большое количество векторизуемых циклов. Мы не будем подробно освещать теорию векторизации (оптимизацию программного кода для эффективного использования векторного процессора), подробное изложение основ и методов можно найти например в [1,2]. Перечислим лишь необходимые требования к циклам, подлежащим векторизации:

- цикл должен быть самым внутренним;

- не допустимы ветвления внутри тела цикла;

- не допустимы вызовы внешних функций и процедур из тела цикла;

- не должно быть рекурсии элементов векторов или массивов в теле цикла.

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

Методы распараллеливания можно условно разделить на следующие:

1. директивами оптимизирующего компилятора;

2. специальными директивами, расширяющими возможности языка к параллелизации;

3. параллельные языки программирования;

4. коммуникационные средства, или средства межпроцессорного интерфейса.

Разумеется, список возможных средств не исчерпывается перечисленными позициями, однако, по-видимому, вышеупомянутые методы имеют самое широкое распространение.

1. Распараллеливание директивами компилятора является самым простым, "автоматическим" средством, которое может эффективно применяться для выборочного класса задач, однако обладает

следующими недостатками:

а) непереносимость с одной системы на другую , или даже при смене компилятора с одного на другой.

2. Введение специальных директив, поддерживающих средства параллельной обработки, в стандартные языки программирования является перспективным направлением. Пример такого развития - HPF (High Performance Fortran) представляющий собой параллельное расширение Fortran'а с помощью оформленных с виде комментариев директив параллельной обработки. Можно отметить следующие преимущества такого подхода:

а) переносимость с одной системы на другую исходного кода, требуется лишь наличие HPF- компилятора.

б) совместимость с последовательной версией программы, поскольку директивы HPF, воспринимаются обычным Fortran-компилятором как комментарии, таким образом отладку последовательного можно проводить на машине без HPF-компилятора.

г) простота освоения пользователем, который должен только указать компилятору блоки для параллельного исполнения, а не конкретизировать какие данные и куда пересылать.

3. Параллельные языки программирования

4. Коммуникационные средства

Следует отметить, что на MPI был опубликован стандарт, что положительно сказывается на развитии данного средства, поскольку производители вычислительной техники включают поддержку MPI в своих программных продуктах, а так же то, некоторые массивно-параллельные системы в качестве средства межпроцессорного обмена используют только MPI, например, установленный в CSA Parsytec CC/20.

Перечислим достоинства применения MPI для параллелизации программ:

а) Переносимость с одной платформы на другую на уровне исходных текстов. Существуют версии MPI предназначенные для настольных компьютеров даже под Win'95, помимо версий для более "серьезных" машин и операционных систем. Данный интерфейс может функционировать как на системах с общей или разделяемой памятью, так и на компьютерах с распределенной памятью.

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

К недостаткам, скорее присущем не столько MPI, а средствам распараллеливания вообще, можно отнести трудности отладки для достаточно сложных программ.

В заключение можно предложить следующий подход к распараллеливанию вычислительных задач:

1. Следует провести анализ алгоритма на предмет выявления блоков, подходящих для распараллеливания, и если алгоритм в принципе не параллелится, или может показать ускорение к примеру в 1.5 раза, то стоит ли возиться?

2. Выбор того или иного способа или модели распараллеливания напрямую зависит от аппаратной платформы, на которой будет эксплуатироваться программа. Иными словами не стоит заниматься векторизацией на машине со скалярными процессорами.

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

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

Литература

[1] Дж. Ортега введение в параллельные и векторные методы решения линейных систем - М. Мир, 1991, 365с.

[2] Векторизация программ: теория, методы, реализация - сб./ Под ред. Г.Д. Чинина -М. Мир, 1991, 272с.