Параллельные вычисления
 Скачать 1.75 Mb.
|
в тех случаях, когда имеются (априори корректно работающие, но не м о гущие быть модифицируемыми вследствие различных причин) параллельные программы и требуется повысить их эффективность путем ис- пользования многопроцессорных вычислительных систем. При создании новых про- граммных комплексов для параллельного исполнения разработчик должен руково- дствоваться разумными соображениями при разработке программ. Вряд ли стоит наде- яться, что компилятор произведет ЭкП типа известной ‘задачи юного Гаусса’ (свед е- ние суммы индексов к произведению, ) 1 100 ( 50 100 1 + × = ∑ = = i i i как частный случай)! Исполь- зование правила Г о рнера ( )) x ( x ... ( x ... x a a a a x a x a a a n 1 n 1 0 n n 2 2 1 0 + + + ≡ + + + − ) хотя и уменьшает число умножений при вычислении значения полинома, но распараллели- вается ненамн о го лучше исходного выражения. Есть ли смысл распараллеливать про- цедуру сортировки на массиве из 10 (возможно, 10 2 ÷ 10 3 ) чисел? А определение значе- ния вычислительнотрудо е мкой функции нескольких переменных (например, при гра- диентном методе поиска экстремума функции многих переменных или вычислении определенного интеграла о ной) распределить по процессорам МВС программист обя- зан самостоятельно! Каждый раз (к счастью!) приходится думать!… Избыточные вычисления возникают в случае неиспользования результатов вычислений в качестве данных для последующих вычислений; в графе алго- ритма этому явлению соответствуют вершины (операторы), выходящие из которых дуги (операнды) не входит ни в какую другую вершину. Избыточ- ные вычисления возникают обычно вследствие неаккуратности программи- ста, ниже приведен пример присвоения четным по сумме индексов элементам двумерной матрицы значений true и нечетным – false : - 92 - Присутствуют избыточные вычисления Избыточные вычисления отсутствуют for(i=0;i сылках данных (обменах информацией); минимизация обменов данными особенно важна для вычислительных систем с распределенной памятью (из- за относительно больших временных задержек при передаче сообщений ин- тенсивность взаимодействия процессоров должна быть минимальной). На рис.25 приведена упрощенная схема ленточного алгоритма вычисления од- ного из прямоугольных бло- ков результирующей матри- цы [C]. Согласно этому ал- горитму каждому процессо- ру МВС пересылается ряд строк a ik , где i=i1…i2, k=1…k max (горизонтальная лента) элементов матрицы [A] и ряд столбцов (верти- кальная лента) b kj , где k=1…k max , j=j1…j2 элемен- тов матрицы [B], процессор вычисляет значение элемен- тов одного из прямоуголь- ных блоков результирующей матрицы [C]=[A] × [B] как for(i=i1; i 0.0, k=0; k c[i][j] += a[i][k] * b[k][j]; Рисунок 25 — Схема ленточного алгоритма умноже- ния матриц [A] × [B]=[C] - 93 - Фрагмент (9) повторяется циклически, чтобы вычисляемые прямоугольные блоки заполнили матрицу [C] целиком. Хотя для вычисления каждого блока матрицы [C] в самом деле необходимы указанные на рис.25 горизонтальная лента [A] и вертикальная лента [B], оне (ленты) будут пересылаться еще мно- го раз при вычислении других прямоугольных блоков результирующей мат- рицы [C]. Одна из модификаций алгоритма лежит буквально ‘на поверхно- сти’ – при заданной вертикальной ленте [B] возможно вычислить не только прямоугольный блок 2] j 1... [j i 1], i 1... [i i , с ij ∈ ∈ , но и всю вертикальную ленту 2] j 1... [j i ], ... [ i , i с max ij ∈ ∈ 1 элементов матрицы [C] (выделено пунктиром на рис.25); для этого достаточно пересылать процессорам только новые гори- зонтальные ленты матрицы [A] при неизменной вертикальной ленте [B]. Анализ избыточности пересылок привел к модификации методов умно- жения матриц – блочным алгоритмам Фокса (Geoffrey Fox) и Кэннона, в слу- чае применения которых процессам пересылаются для обработки не ленты, а прямоугольные блоки перемножаемых матриц (эти алгоритмы требуют до- полнительных обменов данными между процессорами, вычисляющим итого- вую матрицу). Наличие интенсивных обменов между процессами характерно и для методов волновой обработки данных (wavefront or hyperplane methods). Подобным же целям (конечная решаемая задача – реализация возможно более крупноблочного параллелизма) служит метод распределения данных с теневыми гранями (окружение основного обрабатываемого блока буферной зоной шириной 1 элемент данных, куда принимаются при обменах копии значений от соседних процессоров), [5]. Контрольные вопросы 1. Что такое граф алгоритма? Почему ГА является ориентированным? Чем определяется принадлежность вершин ГА к множеству входных и выход- ных? Что такое ярусно-параллельная форма алгоритма? 2. Каким образом матрица смежности представляет граф алгоритма? 3. Что такое операторы-преобразователи и операторы-распознаватели? В ка- ких моделях графового представления алгоритмов они используются? 4. В чем заключается потенциал параллелизма в циклах? Какие методы ана- лиза пространства итераций используются для выявления параллелизма? Что такое циклы ParDO? 5. Каким образом выявляется параллелизм системами автоматического рас- параллеливания? Какие эквивалентные преобразования обычно выполня- ются этими системами? Что такое редукция высоты дерева и на основе ка- ких свойств арифметики она реализуется? 6. Что такое сбалансированность загрузки процессоров при распараллелива- нии? Каково условие сбалансированности? - 94 - 7. Что такое избыточность вычислений и обменов данными? Каким путем можно свести к минимуму эти явления? 8. Количественно определить избыточность пересылок данных в примере рис.24 (пересылку каждого элемента массивов [A] и [B] считать избыточ- ной, если она происходит более одного раза за время решения задачи). Как изменится эта количественная оценка при лежащей на поверхности моди- фикации блочного алгоритма перемножения матриц? 9. Оцените количественно размер гранулы параллелизма для ленточного ум- ножения матриц (единицу измерения выберите сами на основе анализа ал- горитма). - 95 - 4 Технологии параллельного программирования Производительность параллельных вычислительных систем еще более за- висит от ‘интеллектуальности’ программного обеспечения, нежели для обычных последовательных; при этом обычной ситуацией является разоча- рование (априори излишне восторженного) программиста, получившего вме- сто ожидаемого снижения времени вычислений существенное повышение оного (даже по сравнению с последовательным вариантом программы). При разработке программ для параллельных многопроцессорных вычис- лительных систем (параллельных программ) проблема переносимости (воз- можность исполнения на различных параллельных вычислительных систе- мах) и живучести (возможность долговременного использования) также при- обретает большее значение, чем при традиционном (последовательном) про- граммировании. Дело, конечно, в ‘молодости’ (и связанным с этим быстрым их прогрессом вширь и вглубь) технологий параллельных вычислений вооб- ще. Для записи параллельных программ были созданы параллельные языки. Они могут быть совершенно новыми (например, ориентированный на про- граммирование транспьютерных устройств язык OCCAM - C.Hoar, 1984), а могут быть основаны на традиционных языках - существуют параллельный C, параллельные Pascal, Fortran и даже ParJava (Институт Системного Про- граммирования РАН, http://www.ispras.ru/javap/parallel_java/par_java/ parjava.html ). Другим языком параллельного программирования, использую- щим объектно-ориентированный подход и поддерживающим поддерживает параллельность по задачам и по данным, является Оrса (Henri Bal, Амстер- дамский университет, 1989, http://www.cs.vu.nl/orca ). Язык ZPL (Larry Snyder, http://www.cs.washington.edu/research/zpl ) обеспечивает параллельность по дан- ным, является переносимым и достаточно производительным. Язык Cilk (Charles Leiserson, Massachusetts Institute of Technology, http://supertech.ics.mit.edu/cilk ) расширяет ANSI C пятью (ключевые слова cilk, spawn, synch, inlet и abort) несложными инструментами для параллельного программирования, разработан для эффективного выполнения параллельных программ на симметричных мультипроцессорах с разделяемой памятью, поддерживает параллелизм по вычислениям и по данным, позволяет эффек- тивно работать с параллельной рекурсией; с использованием 5-й версии Cilk создано несколько шахматных программ (одна из них, Cilkchess , показала хо- рошие результаты на всемирном компьютерном чемпионате по шахматам 14 ÷ 20.VI.1999 г. в Paderborn, Germany). Первым функциональным языком, созданным специально для численных расчетов, стал Sisal (Streams and Iteration in a Single Assignment Language, Lawrence Livermore National Laboratory, 1985), вторая версия языка описана в (J.T.Feo, D.C.Cann, R.R.Oldehoeft, 1990). Реализация Sisal основана на модели - 96 - потоков данных (выражение можно вычислить, как только будут вычислены его операнды); Sisal-программы оказались эффективными, но к концу 90-х г.г. проект был закрыт. Язык NESL (Guy Blelloch, Carnegie Mellon University, 1996, http://www.cs.cmu.edu/ SCandAL/nesl.html ) представляет собой функцио- нальный язык с параллельностью по данным и в целом соответствует модели NESL (концепция работы и глубины). Функциональный язык Eden (Philipps Universität Marburg, Германии и Universidad Complutense, Мадрид, 1998, http://www.uni-marburg.de/welcome.html, http://www.ucm.es/UCMD.html ) расширяет функциональный подход языка Haskell (см. далее подраздел 4.3.2) путем от- мены механизма ‘ленивых (отложенных) вычислений’ (lazy evaluation) в мо- мент распараллеливания вычислений. Информацию и документацию по параллельным языкам и свободно рас- пространяемые версии можно найти на http://www.parallel.ru/tech/tech_dev/par_lang.html, http://www.hensa.ac.uk/parallel , по- лезные ссылки - http://computer.org/parascope К настоящему времени выкристаллизировались стандартные технологии, существенного (качественного) изменения которых ожидать в разумное вре- мя не приходится. Ниже кратко рассматриваются основанные на распределе- нии данных и вычислений системы параллельного программирования HPF, OpenMP и DVM, специализированный язык mpC высокого уровня для про- граммирования разнородных сетей, низкоуровневая технология программи- рования обменов сообщениями MPI, PVM и язык Linda, методы автоматиза- ции распараллеливания вычислений (T-система, НОРМА), см. [1,4,5,8]. Весьма показательным является связанное с проблемой распараллеливания алгоритмов обращение к результатам (давно разрабатываемой) теории функционального программирования (Т-система, НОРМА; чуть подробнее см. подраздел 4.3.2). Практическая реализация положений функционального программирования фактически переводит центр тяжести с операторного управления процессом обработки данных на процесс, управляемый данными (см. подраздел 2.5). Можно реализовать data flow на чисто алгоритмическом уровне (аппарат- ная часть остается control flow и выполняет традиционно императивные ин- струкции), именно для этого как нельзя подходят идеи функционального про- граммирования. 4.1 Дополнения известных последовательных алгоритмических языков средствами параллельного программирования Простейший (и исторически совершенный) путь создания системы созда- ния параллельных программ – дополнить традиционные языки программи- рования средствами описания распараллеливания вычислений (а возможно, и данных). При этом достигается минимум модифицирования существующих - 97 - программ (требуется лишь некоторая ‘переделка’) и сохраняется опыт про- граммирования. Недостатки подхода базируются на этих же положениях – для разработки эффективной параллельной программы необходимо учиты- вать внутреннюю структуру алгоритма, а базовый (исходно последователь- ный) язык обычно не содержит даже механизмов, с помощью которых воз- можно реализовать это. Естественно, на поверхности лежит попытка реализовать параллелизм в циклах (гнездах циклов) в Fortran-программах (см. ранее подраздел 3.2). Возможность реализовалась использованием дополнительных ключевых слов ParDO (отечественная система M-10), ParDO/ParEND (система параллельного сборочного программирования ИНЯ, ( * ). Метод ‘подсказок’ компилятору с целью дополнить его функциональность средствами распараллеливания реализован, например, в системе HPF (Hight Performance Fortran, 1995). В HPF-системе традиционный Fortran дополнен специальными директивами, записываемыми в форме комментариев (т.е. не воспринимаемых обычным компилятором – метод решения проблемы пере- носимости!). С возможностью использовать HPF-программ на последова- тельных и параллельных машинах без изменений были связаны серьезные надежды разработчиков, сменившиеся в дальнейшем здоровым скептициз- мом (несмотря на это, в 1997 г. был разработан проект стандарта HPF2, рас- ширявший возможности программиста в смысле директив распараллелива- ния, [6]). История развития HPF тесно связана с таковой языка Fortran’90. Именно в этом языке появились прототипы языковых конструкций, которые позволили компилятору эффективно генерировать параллельный код. Этот язык не яв- ляется в прямом смысле параллельным, его создатели ставили себе более общие цели - создать машинно-независимый инструмент обработки число- вых научных данных. Основные возможности параллелизации в Fortran’90 связаны с циклами (операциям над массивами, именно на эти действия при- ходится большее время выполнения научно-технических задач и именно их целесообразно распараллеливать в первую очередь). Мощным средством ра- боты с массивами в Fortran’90 является возможность использования их в арифметических операциях подобно обычным скалярам. Многие встроенные операции в языке Fortran’90 можно применить и к массивам, получая при этом массив такой же формы, каждый элемент которого будет иметь значе- ние, равное результату заданной операции над элементами массивов. Воз- можно выделять секции в массивах и оперировать с ними как с новыми мас- сивами и др., причем порядок, в котором совершаются поэлементные опера- ции, стандартом не устанавливается. Это дает возможность компилятору * В.Э.Малышкин. Основы параллельных вычислений. // Учебное пособие, часть 2. ЦИТ СГГА. –Новосибирск, 2003. - 98 - обеспечить их эффективную обработку на векторном или параллельном вы- числителе. Cинтаксис Fortran’90 помогает компилятору в большинстве случаев избавиться от применения сложных алгоритмов определения парал- лельных свойств циклических конструкций. Дальнейшее развитие околофор- трановского направления привели к разработке Fortran’D (1992) и For- tran’Vienna, HPF (1992), инструментального пакета анализа программ ParaScope (Rice University), средства автоматического распараллеливания For- tran-программ BERT 77, а также системы Forge (Applied Parallel Research, Inc., см. ниже). Система программирования HPF – типичная система с императивным ука- занием программиста компилятору, каким образом распределить данные между процессорами (вычисления распределяются на основе распределения данных – модель параллелизма по данным). Распределение данных управля- ется директивами ALIGN (определение соответствия между взаимным распо- ложением элементов нескольких массивов) и DISTRIBUTE (отображение группы массивов на решетку процессоров), при этом допустимо ‘разрезание’ массива гиперплоскостями на располагающиеся на различных процессорах блоки и динамическое (в ходе выполнения программы) перераспределение (директивы REALIGN и REDISTRIBUTE ). Параллелизм по вычислениям в HPF реализован по следующим конструкциям языка – операции над секциями массивов (параллелизм вычислений детерминируется ранее заданным рас- пределением данных, при необходимости используется пересылка данных), циклы DO и операции FORAL L (компилятором производится попытка обоб- щить эти конструкции в виде операций над секциями массивов). Пример HPF-программы приведен в Приложении 1б (исходно-последовательный ва- риант программы – Приложение а). HPF-препроцессор Adaptor ( http://www.gmd.de/SCAI/lab/adaptor/ adaptor_home.html ) распространяется (в уп- рощенной версии) свободно; автоматическое построение HPF-приложений осуществляется утилитой gmdhpf , поочередно вызывающей HPF → Fortran- препроцессор (утилита fadapt ), Fortran-компилятор и компоновщик. Программирование на HPF (существуют варианты для C/C++) с точки зре- ния программиста близк |