Параллельные вычисления
 Скачать 1.75 Mb.
|
|
у г и число их не зависит от значе- ний внешних переменных программы. Для минимальных графов зависимостей получено их представление в виде конечного набора простейших функций, а оно, в свою очередь, позволяет решать широкий спектр задач в области исследования структуры алгорит- мов. Применение минимальных графов зависимостей позволило решить задачи (включая задачи, решение тесно связано с минимальными графами), [1]: • Определение параллельной структуры алгоритмов и программ на уровне отдельных операций. • Расчлен е ние алгоритмов на крупные параллельно исполняемые фрагменты. • Восстановление по программе исходных математических формул. • Оптимизация использования внешней памяти. • Оценка параллельной сложности алгоритмов и программ. • Быстрое вычисление градиента сложных функций. • Исследование влияния ошибок округления. • Построение математических моделей систолических массивов. • Разработка порт а бельных библиотек программ. - 76 - Результаты разработок использованы при создании системы V-Ray (разработка НИВЦ МГУ, http://parallel.ru/v-ray ). В общем случае анализ имеющего m дуг графа алгоритма с целью выявле- ния параллелизма (напр., выявление ярусов) требует порядка т 2 переборов, при этом сам алгоритм выполняется (на однопроцессорном компьютере) за пропорциональное m время. Т.о. время исследования структуры алгоритма с целью выявления параллелизма значительно превышает время его выполне- ния! Как показано в работе ( ∗ ), решение наиболее практически ценных вари- антов задачи оптимального размещения операций по процессорам МВС тре- бует числа переборов порядка m! для только одного набора входных данных (т.е. по трудоемкости относится к NP-полным задачам и точное решение не- возможно получить за разумное время). В большинстве (из огромного множества наработанных) последовательных алгоритмов присутствует внутренний параллелизм (возможность представле- ния алгоритма в параллельной форме при сохранении его вычислительных свойств – численной устойчивости и др.), который может быть выявлен ме- тодом построения и анализа графа алгоритма. В сложных случаях применя- ются эквивалентные преобразования исходных алгоритмов. Графы алгорит- мов для некоторых задач приведены в [1,3]. Для часто применяемых алго- ритмов (напр., операции с матрицами) операции распараллеливания прове- дены и соответствующие программы собраны в проблемно- ориентированные библиотеки (пакеты). Практического использование выявленных возможностей распараллелива- ния требует отображения графа алгоритма на конкретную многопроцессор- ную вычислительную систему, для чего необходимо иметь описание МВС - количественные параметры процессоров и коммуникационной среды (на первом этапе анализа часто принимается одинаковое время выполнения лю- бых вычислительных операций и мгновенный обмен данными между процес- сорами, при учете времени обмена данными проводится анализ коммуника- ционной трудоемкости параллельного алгоритма). Именно на этом этапе можно определить: • Время выполнения параллельного алгоритма. • Ускорение (отношение времени решения задач на скалярной ЭВМ к вре- мени выполнения параллельного алгоритма). • Эффективность (величина, определяющая усредненную долю времени выполнения алгоритма, в течение которой процессоры на самом деле ис- пользуются для решения задачи). ∗ Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. –М.: Мир, 1982, -416 c. - 77 - На основе этих данных строится описание параллельного выполнения алго- ритма, один из вариантов построения которого приведен в книге ( ** ) и рабо- те [3]). Неравномерность загрузки процессоров снижает эффективность использо- вания МВС, поэтому проблема балансировки (равномерности загрузки про- цессоров) относится к числу важных задач параллельного программирования. Один из действенных подходов к обеспечению равномерности загрузки процессоров состоит в организации всех готовых к выполнению в системе вычислительных действий в виде очереди заданий. При вычислениях любой освободившийся процессор запрашивает для себя работу из этой очереди; появляющиеся по мере обработки данных дополнительные задания допол- няют очередь. Эта схема балансировки вычислительной нагрузки между процессорами проста, наглядна и эффективна, что позволяет говорить об ис- пользовании очереди заданий как об общей модели организации параллель- ных вычислений для систем с общей памятью [3]. При теоретическом анализе применяется также понятие стоимости парал- лельного алгоритма (произведение сложности алгоритма на число исполь- зуемых процессоров). Известно, например, что оптимальный алгоритм сор- тировки требует O(n × log n) операций (n – число сортируемых записей, см. ( *** )), тогда для параллельного алгоритма со сложностью O(n) коэффициент ускорения составит O(log n), а стоимость параллельного алгоритма на p про- цессорах равна O(n × p). Т.к. стоимость алгоритма последовательной сорти- ровки на одном процессоре совпадает с его сложностью и равна O(n × log n), алгоритм параллельной сортировки обходится дороже параллельной при 1 > = × × n log p n log n p n (т.е. p>log n) и дешевле в противоположном случае (при p 3.2 Потенциал распараллеливания циклов. Циклы ParDO Практика программирования (особенно научно-технических задач – в пер- вую очередь для сеточных методов) показывает, что наибольший ресурс па- раллелизма сосредоточен в циклах, поэтому распространенным способом распараллеливания является распределение итераций циклов (если между итерациями не существует информационных зависимостей, то итерации ** Dimitri P.Bertsekas, John N.Tsitsiklis. Parallel and distributed Computation. Numerical Methods. - Prentice Hall, Englewood Cliffs, New Jersey, 1989. *** Макконел Дж. Основы современных алгоритмов. –М.: Техносфера, 2004, -368 с. - 78 - можно определенным способом распределить разным процессорам для па- раллельного исполнения). Циклы, все итерации которых информационно независимы, принято назы- вать ParDO циклами, из условия независимости следует, что возможно их выполнять в любом порядке (в т.ч. параллельно). Этот вид параллелизма ва- жен на практике благодаря частой встречаемости и простоты использования. Нахождение циклов ParDO производится с помощью анализа информацион- ной структуры программы (основанный на графовом представлении алго- ритмов критерий определения цикла ParDO приведен, напр., в работе [1]). Причем найденное по графу алгоритма свойство ParDO говорит лишь о принципиальной возможности независимого выполнения итераций (для реа- лизации возможности необходимо произвести определенные преобразования цикла), полностью готовые к распараллеливанию циклы обозначаются как TrueParDO. Одними из первых программных средств, обеспечивающих некоторую ав- томатизацию распараллеливания, явились как раз системы выявления парал- лелизма в циклах. Обычно используют два типа таких систем: • Специализированные компиляторы (компиляторы с традиционных язы- ков программирования – обычно Fortran), функциональность которых расширена средствами выявления параллелизма, эквивалентными преоб- разованиями цикла и созданием соответствующего исполняемого кода (обычно рассчитанного на векторную архитектуру вычислителя). • Препроцессоры, осуществляющие анализ и отбор циклов на векториза- цию или распараллеливание, выявленные блоки часто конвертируются в допускающее параллельную обработку расширение языка (напр., MPI, см. подраздел 4.1); в дальнейшем (преобразованный) исходный текст обраба- тывается стандартным компилятором. Многие такие системы допускают диалоговый режим работы – при этом автоматически выявляются блоки-кандидаты на распараллеливание, а окон- чательное решение о необходимости и способе преобразования в параллель- ную форму принимает разработчик. Одним из известных и мощных препроцессоров-векторизаторов, каждый член которого настроен на конкретную объектную машину, является KAP. Система KAP использует для оптимизации коллапс циклов, разбиение цикла, переупорядочение операторов и разрушение контуров зависимостей по дан- ным, сегментацию цикла (преобразование исходного цикла в гнездо из не- скольких циклов при соблюдении условия непереполнения кэш-памяти). Известными системами являются PFC (и основанная на ней инструмен- тальная диалоговая система анализа программ PTOOL), ParaScope, BERT 77, - 79 - D-система, Polaris и др., ( * ). Основой для решений о распараллеливании яв- ляется граф зависимостей по данным (строится по исходному тексту про- граммы), в некоторых случаях используется дополнительная информация о глубине зависимости для гнезда циклов или векторов направлений зависимо- сти. Исследование графа выявляет как области нераспараллеливания или по- следовательного исполнения, так и структуру таких областей. Например, изучение контуров зависимости на предмет однородности дуг контура может показать, что контур может быть разрушен. Здесь возможно применение пре- образований типа переименования переменных. В нашей стране также разрабатывались системы подобного типа - напр., cистема программирования для ПС-3000 для МВК ПС-3000 (включает язык программирования Фортран’77ВП, являющийся расширением стандарта For- tran’77 средствами организации векторных и параллельных вычислений), Система М10 (М.А.Карцев), конвертер-векторизатор Фора-ЕС (для специа- лизированного векторного процессора СПЕС, Институт прикладной матема- тики АН СССР), векторизующий ПЛ/1-компилятор ИПК АН СССР (для ма- шин Cray, Институт проблем кибернетики АН СССР) и др. Из современных разработок рекламируется система ОРС (Открытая Распа- раллеливающая Система, Open Parallelizing System Group; Ростовский госу- дарственный университет, http://ops.rsu.ru ) - программная инструментальная система, ориентированная на разработку распараллеливающих компилято- ров, оптимизирующих компиляторов с параллельных языков, систем полуав- томатического распараллеливания (так система позиционируется разработ- чиками). OPC базируется на интерактивном характере распараллеливания (разработана мощная система визуализации), использует различные графо- вые модели программ, эквивалентные преобразования выражений, одномер- ных циклов и гнезд циклов. При ручном анализе и преобразовании циклов используют наработанные эмпирические методы, часть из них описана ниже. Приведем пример программирования в технологии MPI (подробнее см. подраздел 4.1), согласно MPI все процессоры выполняют одинаковый испол- няемый код, а необходимые каждой параллельной ветви действия определя- ются использованием условных операторов; один из процессоров (обычно нулевой) является управляющим, остальные - рабочими. Задача заключается в суммировании N чисел, последовательно располо- женных в массиве A[ ] , число процессоров равно N_P ( диапазон 0 ÷ N_P-1) ; предполагается, что каждый процесс ‘знает’ собственный номер (переменная I_AM ): * В.А.Евстигнеев, И.Л.Мирзуитова. Анализ циклов: выбор кандидатов на распараллели- вание. // Препринт. Российская академия наук Сибирское отделение Институт систем информатики им. А. П. Ершова. –Новосибирск, 1999, -41 c. - 80 - int k = N / N_P; // целое от деления N на N_NP int k1 = N % N_P; // остаток от деления N на N_P if ((I_AM > 0) && I_AM < N_P-1) { // для всех процессов кроме нулевого и последнего… s = 0; for (i=k ∗ (N_P-1); i N_P; i++) // суммируем k элементов массива A[ ] s += A[i]; // s – локальная для каждого процесса переменная послать s управляющему процессу // оператор не конкретизируется } // конец блока if () else if (I_AM == N_P-1) { // для последнего процессора… s = 0; for (i= k ∗ (N_P-1); i< k ∗ N_P+k1; i++) // суммируем k+k1 элементов массива A[ ] s += A[i]; // s – локальная для каждого процесса переменная послать s управляющему процессу // оператор не конкретизируется } // конец блока if () Здесь каждый процессор (кроме нулевого и последнего) осуществляет сум- мирование очередных K элементов массива A[ ] , последний процессор сумми- рует оставшиеся K+K1 элементов. Последним действием (выполняющимся после всех приведенных – именно здесь необходима синхронизация) является суммирование всех частичных сумм, полученных N_P-1 процессорами: if (I_AM == 0) { // выполняется управляющим процессом sum = 0; for (j=1; j ÷ N_P принять значение s от процесса j // оператор не конкретизируется sum += s; // готовое значение – в переменной sum } // конец блока for () } // конец блока if () При излишне большом размере массива A[ ] процесс распределения его про процессам может повторяться многократно (что способствует экономии ОП каждого процессора), общее ускорение выполнения программы будет, конеч- но, несколько меньше N_P (сетевой закон Амдаля, см. подраздел 1.5). При разработке параллельной программы желательно использовать алгоритм, аб- страгирующийся от количества процессоров (программа должна выполняться на МВС с числом процессоров ≥ 2). Приведенный пример иллюстрирует блочное распределение итераций по процессорам и является типовым для множества алгоритмов, основными действиями в которых являются обладающие свойством ассоциативности операций сложения/умножения (матричные операции, поиск экстремумов в массивах, интегрирование и многие др.). Преимуществом его является сба- лансированность загрузки ‘рабочих’ процессоров (все кроме одного выпол- няют одинаковую работу, последний ‘перерабатывает’ менее чем на 1 - N_P 100% ). Заметим, что условием сбалансированности загрузки процессоров является приблизительно равноценные по времени исполнения распределяемые ите- рации (рассматриваемый пример удовлетворяет этому условию). Таким ус- - 81 - ловиям (с некоторыми оговорками) соответствует, например, распределение по процессорам вычисление одной и той же функции в нескольких точках (при поиске экстремумов функции многих переменных градиентными мето- дами). Циклическое распределение итераций предполагает выполнение все- ми процессорами по одной последовательной итерации цикла (для простых операций в теле цикла размер гранулы может при этом оказаться чересчур мелким). В программах часто встречаются многомерные циклические гнезда, при- чем каждый цикл такого гнезда может содержать некоторый ресурс паралле- лизма. Пространство итераций (Lamport L., 1973) гнезда тесно вложенных циклов называют множество целочисленных векторов, координаты которых задаются значениями параметров циклов данного гнезда.Задача распаралле- ливания в этом случае сводится к разбиению этого множества векторов на выполняющиеся друг за другом последовательно подмножества, однако для каждого подмножества итерации могут быть выполнены параллельно (внут- ри подмножества не существует информационных зависимостей). Среди методов анализа пространства итераций известны методы гиперп- лоскостей, координат, параллелепипедов и пирамид ( * ). При использовании метода гиперплоскостей пространство итераций размерности n разбивается на гиперплоскости размерности 1 − n таким образом, что все операции, соот- ветствующие точкам одной гиперплоскости, могут выполняться параллельно. Метод координат заключается в том, что пространство итераций фрагмента разбивается на гиперплоскости, перпендикулярные одной из координатных осей. Метод параллелепипедов является логическим развитием двух преды- дущих методов и заключается в разбиении пространства итераций на n- мерные параллелепипеды, объем которых определяет результирующее уско- рение программы. При использовании метода пирамид находятся итера- ции, вырабатывающие значения, которые далее в теле гнезда циклов не ис- пользуются; каждая такая итерация служит основанием отдельной параллель- ной ветви, в которую входят и все итерации, информационно влияющие на выбранную (неприятным эффектом при этом является дублирование ин- формации в разных ветвях, что может приводить к потере эффективности). Известны методы (напр., метод линейного преобразования), являющиеся более мощными, нежели метод гиперплоскостей и даже метод координат Лэмпорта, ( ** ). Пространство итераций для простого цикла * А.С.Антонов. Введение в параллельные вычисления (методическое пособие). // Изд. МГУ им.М.В.Ломоносова, НИВЦ. -М.: 2002, -69 c. ** Lamport L. The coordinate method for the parallel execution of DO-loops. // Sagamore com- puter conference on parallel processing, 1973. - 82 - for (i = 1; i < N; i++) for (j = 1; j < M; j++) (6) A[i][j] = A[i-1][j] + A[i][j]; приведено на рис.21 (окружности соответствуют отдельным операторам вычисления и присваивания, стрелки - информационным зависимостям). Из рис.21 видно, что разбиение пространства итераций по измерению I приводит к разрыву информационных зависимостей; для измерения J таково- го не происходит, поэтому возможно применение метода координат с разбие- нием пространства итераций гиперплоскостями, перпендикулярными оси J (на рис.21 – пунктир). Эти операции назначаются для выполнения на одном про- цессоре. Для гнезд |