Параллельные вычисления
 Скачать 1.75 Mb.
|
|
овые средства Linda на самом деле допускают широкие возможности по синхронизации процессов, реализации работающих по схеме ‘главный/подчиненный’ программ и т.д. Linda эффективна для многопроцес- сорных вычислительных систем, обладающих общей памятью (только в при размещении пространства кортежей в памяти такого типа возможно реали- зовать быстроту операций с кортежами); при реализации Linda для систем с распределенной памятью возникают проблемы, аналогичные NUMA- системам (VSM - Virtual Share Memory - виртуальная разделяемая память в системе Linda реализуется программно). В настоящее время Linda коммерчески поддерживается образованной в 1980 г. фирмой SCA (Scientific Computing Associates, Inc.), торговая марка TCP Linda ( http://www.lindaspaces.com, lunix-support@LindaSpaces.com ) включа- ют графическую отладочную среду Tuplescope. На основе VSM фирмой SCA разработаны системы Piranha (средство объединения персональных ЭВМ в многопроцессорную вычислительную систему), JParadise (система поддерж- ки распределенных прикладных Java-программ), SCA предлагает также Win- dows-вариант системы программирования Linda и (совместно с OptTek Systems, Inc., http://www.opttek.com ) параллельную версию библиотеки OptQuest Callable программных пакетов многомерной оптимизации. Linda использована при разработке системы Gaussian'03 (изучение элек- тронной структуры химических веществ), применена при разработке системы Paradise для параллелизации процесса обнаружения знаний в базах данных (технология Data Mining), используется фирмой Motorola, Inc. при проекти- - 106 - ровании микросхем, для поддержки финансовой деятельности, обработки данных геофизических исследований при морской нефтедобыче и др. Низкоуровневая модель передачи сообщений (MPI). Модели параллелизма: по данным (HPF), по данным и по управлению (DVM), гибридная модель параллелизма по управлению с передачей сообщений (OpenMP+MPI), сис- тема НОРМА. 4.3 Автоматизация распараллеливания алгоритмов 4.3.1 Распараллеливающие компиляторы Желание автоматизировать процесс перевода в параллельный вариант ог- ромного количества наработанного (и вновь разрабатываемого) программно- го обеспечения является более чем естественным. Разработка полностью автоматически распараллеливающего компилято- ра, казалось, может снять все проблемы программиста. К сожалению, реаль- ные разработки в этом направлении не впечатляют своей эффективностью. Во-первых, априори невозможно создать такой компилятор универсальным (вследствие наличия значительного количества архитектур ЭВМ и систем команд процессоров, при этом оптимизированный для одной системы ком- пилятор окажется малоэффективным для другой). Во-вторых, (на основе опыта уже разработанных систем параллельного программирования) пред- ставляется проблематичной сама идея полностью автоматического распа- раллеливания (подобная система должна обладать существенными чертами искусственного интеллекта и, скорее всего, будет громоздкой и трудно на- страиваемой). Весьма проблематична (хотя на сегодняшний день уже скорее чисто технически) разработка единой схемы распараллеливания произволь- ного алгоритма с отображением на архитектуру реальной ЭВМ (именно здесь как нельзя более полезны приемы классификации и описания архитектур). Именно поэтому обычно ограничиваются задачей синтаксического анализа исходно-параллельного текста с целью выявления потенциального паралле- лизма и генерацией распараллеленного исходного текста (часто в стиле MPI), компиляция этой программы осуществляется машинно-зависимым компиля- тором с поддержкой библиотеки MPI (частично такие системы описаны в подразделе 3.2). Например, в состав полнофункционального пакета Forge90 (APR - Applied Parallel Research, Inc., http://www.infomall.org/apri//index.html, forge@netcom.com ) входят препроцессоры dpf, spf, xhpf (для систем с распределенной памятью, общей памятью и для использования программирования в HPF-стиле соот- ветственно), позволяющие на основе исходного текста последовательного алгоритма сформировать текст, уже распараллеленный в технологии PVM на Fortran’77; подобные пакеты объемны и дорогостоящи. - 107 - 4.3.2 Автоматическое распараллеливание с помощью Т-системы Разработка технологии автоматического динамического распараллелива- ния программ (названная ‘Т-система’) ведется с конца 80-х г.г. в Институте программных средств РАН (г. Переславль-Залесский). В целом стиль Т- программирования близок традиционным языкам программирования (Fortran, C/C++), причем явное указание на параллельность выполнения бло- ков программы в тексте отсутствует. Базовые принципы Т-системы основаны на результатах общей теории функционального программирования (ФП). Теоретические основы импера- тивного (операторного) программирования были заложены в 1930-х г.г. (Алан Тьюринг, Джон фон Нейман), положенная в основу функционального подхода теория родилась в 1920 ÷ 1930-х г.г. (комбинаторная логика - Мозес Шенфинкель, Хаскелл Карри, лямбда-исчисление - Алонзо Черч, 1936). Математические функции выражают связь между параметрами (входом) и результатом (выходом) некоторого процесса. Вычисление – также процесс, имеющий вход и выход, при этом функция является вполне подходящим и адекватным средством описания вычислений. Именно этот простой принцип положен в основу функциональной парадигмы и функционального стиля программирования. Функциональная программа представляет собой набор определений функций. Функции определяются через другие функции или рекурсивно через самих себя. В процессе выполнения программы функции получают параметры, вычисляют и возвращают результат, в случае необхо- димости вычисляя значения других функций. Программируя на функцио- нальном языке, программист не должен описывать порядок вычислений - ему необходимо лишь описать желаемый результат в виде системы функций. Функции в ФП не имеют побочных эффектов. Обращение к функции не вызывает иного эффекта, кроме вычисления результата (в этом смысле при- вычные вызовы традиционных языков программирования суть процедуры, а не функции в понятии ФП); это устраняет серьезный источник ошибок и де- лает порядок выполнения функций несущественным (так как побочные эф- фекты не могут изменять значение выражения, оно может быть вычислено в любое время). Теория функционального программирования долгое время оставалась ‘гадким утенком’ (в противоположность идеям императивного программиро- вания) до момента разработки первого почти функционального языка про- граммирования Lisp (Джон МакКарти, 1950). К началу 1980-х г.г. появились ФП-языки ML, Scheme, Hope, Miranda, Clean и др.; одной из популярных в настоящее время реализаций ФП-подхода является язык Haskell (Хаскелл Карри, начало 1990-х г.г., http://www.haskell.org ). - 108 - Важной особенностью Haskell является механизм ‘ленивых (отложенных) вычислений’. В традиционных языках программирования (например, Fortran, C/С++) вызов функции приводит к вычислению всех аргументов (‘вызов-по- значению’); при этом если какой-либо аргумент не использовался в функции, то результат вычислений пропадает, т.е. вычисления были произведены впус- тую. Альтернативой вызова-по-значению является вызов-по-необходимости (этом случае аргумент вычисляется, только если он действительно необходим для вычисления результата); понятный программисту пример – выполнение оператора конъюнкции && из C/C++, который никогда не вычисляет значе- ние второго аргумента, если первый аргумент суть ‘ложь’. Языки, исполь- зующие отложенные вычисления, называются нестрогими (примеры – Haskell, Gofer, Miranda); если функциональный язык не поддерживает отло- женные вычисления, он является строгим (языки Scheme, Standard ML, Caml, в таких языках порядок вычисления строго определен). Одно из главенствующих понятий Т-системы – ‘чистые’ функции (функ- ции без побочных эффектов при вычислениях); чистая функция может быть выполнена параллельно с основной программой. Чистыми (отсутствуют по- бочные эффекты) обычно являются нестрогие языки. В каждый момент времени выделяются готовые к вычислению ‘подвыра- жения’ и распределяются по имеющимся процессорам, при этом за основу берется граф, узлы которого представляют выбранные функции, а дуги соот- ветствуют отношению ‘выражение-подвыражение’. Для использования возможностей функционального программирования в традиционные языки вводится понятие неготового значения. В применении к С это выражается введением дополнительного атрибута tval описания пере- менных, tval int j определяет переменную, значение которой может быть це- лым числом или неготовым (пока не посчитанным) значением, в описании функции без побочных эффектов необходим атрибут tfun , выходного значе- ния – tout , глобальной ссылки на неготовую переменную - tptr (измененный таким образом С++ получил название Т++, см. Приложение 3). Т-система запускает чистые функции как ветви параллельной программы, а неготовые переменные (НП) являются основным средством синхронизации их выполнения. При чтении НП происходит блокировка процесса вычисле- ния, выполнившего такое обращение, причем ожидание продлится до тех пор, пока переменная не получит готового значения (исключение – операция присваивания НП, при этом блокировка не возникает). При записи обычного значения в НП она становится готовой для всех выражений, в которые она входит; ранее заблокированные на ней процессы выходят из блокировки. Т-система снабжена развитыми системами отладки – от начальной прогон- ки программы на последовательной машине ( t -атрибуты в этом режиме игно- рируются) до использования спецметодов (трассировка, профилировка и др.) для оптимизации при выполнении на многопроцессорной ЭВМ. - 109 - Преимущества Т-системы заключается в практически полном освобожде- нии программиста от обдумывания деталей описания распараллеливания, не- достатки – в требовании описания алгоритма в функциональном стиле (фор- мально необходимо составить программу в виде набора чистых Т-функций, что непривычно). Вычислительная сложность Т-функций (она задает размер гранулы параллелизма) также должна определяться программистом (излишне малая приведет к чрезмерным накладным расходам по обмену данными ме- жду процессорами, слишком большая – к неравномерной загрузке вычисли- тельных узлов). 4.3.3 Непроцедурный декларативный язык НОРМА Свободно распространяемым инструментом автоматизации создания па- раллельных MPI-программ является система HOPМА (h ttp://www.keldysh.ru/pages/norma ), позволяющая (на основе специализирован- ного декларативного языка) синтезировать исходный Fortran/С - текст с вы- зовами MPI [9]. Непроцедурный язык НОРМА является проблемно- ориентированным и предназначен для автоматизации решения сеточных задач на вычислительных системах с параллельной архитектурой. Этот язык позволяет исключить фазу параллельного программирования, которая необ- ходима при переходе от расчетных формул, заданных прикладным специали- стом, к программе. Концепция непроцедурного языка НОРМА (Непроцедурное Описание Раз- ностных Моделей Алгоритмов или НОРМАльный уровень общения приклад- ного математика с компьютером, http://www.keldysh.ru/pages/norma ) предло- женная еще в 60-х г.г. в ИПМ им.М.В.Келдыша РАН. Язык НОРМА называют декларативным вследствие упора именно на описание правил вычисления значений, а не на исчерпывающе подробную конкретизацию алгоритма. Разработчик прикладных программ абстрагиру- ется от особенностей конкретных ЭВМ и мыслит в привычных терминах своей предметной области (сеточные методы математической физики, в ос- новном метод конечных разностей - МКР). Система НОРМА включает синте- затор, назначением которого является преобразование НОРМА-текста в (один из привычных) языковых стандартов параллельного или последова- тельного программирования (в настоящее время существует возможность получения Fortran’MPI, Fortran’PVM, Fortran’77 или соответствующих C- текстов). Именно синтезатор учитывает архитектуру конкретной ЭВМ, в са- мом языке НОРМА не предусмотрено никаких указаний на параллелизм или описания структуры целевого компьютера (см. Приложение 4). Эффективный автоматический синтез параллельного кода на основе НОР- МА-программы достигается определенными ограничениями языка, важное из которых – отсутствие многократного присваивания (при этом несущественна - 110 - последовательность операторов, отсутствуют глобальные переменные, за- прещена рекурсия, нет побочных эффектов при вычислениях и др., [9]). Ис- ходный текст на НОРМА в высшей степени близок к записи численного ме- тода решения конкретной задачи. В записи на языке НОРМА отсутствуют избыточные информационные связи (полный анализ которых как раз и явля- ется ‘ахиллесовой пятой’ систем выявления скрытого параллелизма), что и позволяет реализовать эффективное автоматическое распараллеливание. За- метим явное сходство парадигмы системы НОРМА с (использованной при разработке Т-системы) идеей функционального программирования. Программа на НОРМА содержит не менее одного раздела. Возможны раз- делы трех видов: главный (ключевые слова MAIN PART), простой (PART) и раздел-функция (FUNCTION), разделы могут вызывать друг друга по имени (рекурсия запрещена) и обмениваться данными с помощью механизма фор- мальных и фактических параметров или путем использования внешних фай- лов (описания INPUT и OUTPUT). Все описанные в списке формальных па- раметров до слова RESULT являются входными данными, далее – выходные (для раздела FUNCTION слово RESULT не используется, т.к. результат вы- числения функции связывается с именем и типом последней). Описанные в разделе переменные являются локальными, глобальных переменных не су- ществует. В теле раздела могут быть заданы (в произвольном порядке) описания, операторы и итерации. Важным понятием НОРМА является одномерная об- ласть, путем операции произведения областей строится многомерная область (с каждой размерностью связывается имя индекса). Возможна операция мо- дификации областей (добавление/удаление точек, изменение диапазона). Ус- ловная область представляет собой подобласть, определяемую выполнением некоторого условия над значениями точек области. Мощность языка НОРМА выражена коллективными операциями над узлами областей (поддерживается линейная топология и двумерная решетка). В НОРМА определены имеющие привычные типы REAL, INTEGER, DOUBLE и идентифицируемые именами скалярные величины и величины на области (последние связаны с конкретной областью и индексированы). Скалярные операторы вычисляют арифметические значения скаляров, оператор ASSUME вычисляет арифметические значения величин на областях (вычисляются все значения по индексам области). Для выполнения итераций имеется специальная конструкция ITERATION. В НОРМА определены стан- дартные арифметические функции, функции редукции и внешние функции пользователя (могут быть вызовами функций на Fortran'е). Заключенные в ограничители # ... # операторы выполняются строго в порядке их следования в программе. Более подробно описание языка см. в [9] и на сайте http://www.keldysh.ru/norma - 111 - Однако для создания НОРМА-программы все же требуется программист, знакомый с правилами языка и формально ‘набивающий’ (после этапа обду- мывания) исходный текст программы. Особенности НОРМА позволяют сде- лать следующий шаг в сторону, противоположную операции разработки про- граммы в виде последовательной записи операторов, т.е. вообще не приме- нять текстовое представление программы. Логично снабдить синтезатор НОРМА интерактивной графической подсистемой, позволяющей манипули- ровать с программой как с отображением в виде графики и гипертекста сово- купности объектов (включая формулы, вводимые пользователем в отдель- ные поля гипертекстовых форм) [5]. Рисунок 26 — Этапы создания исполняемых программ: a) - классический подход, б) - использование НОРМА-программирования совместно с оболочкой ‘Интерактив- ная НОРМА’ С этой целью на кафедре ИТ-4 МГAПИ разрабатывается система ‘Интерак- тивная НОРМА’ ( http://norma.deniz.ru ), позволяющая создавать параллельные программы практически без написания исходных текстов на языке програм- мирования (рис.26б). 4.4 Стандартные предметно-ориентированные библиотеки параллельных вычислений При всей широте средств разработки параллельных программ создавать такие программы (и особенно эффективные!) все же очень и очень непросто. Одним из путей разработки эффективных параллельных программ является использование предметно-ориентированных библиотек. - 112 - В этом случае оптимизация вообще скрыта от проблемного программиста. Чем больший объем работы внутри программы отводится подпрограммам такой библиотеки, тем большим будет итоговый выигрыш в скорости ее ра- боты. Собственно же программа пишется на обычном языке программирова- ния безо всяких упоминаний о MPI и строится стандартным компилятором; от программиста требуется лишь указать при компоновке имя соответствую- щего библиотечного файла и запускать полученный в итоге исполняемый файл как MPI-программу. Т.о. чем большую часть вычислений удастся пере- ложить на библиотечные подпрограммы (а они особенно тщательно протес- тированы, отлажены и оптимизированы), тем более эффективной получится результирующая программа. Наиболее известны библиотеки программ для решения задач матфизики (матричные операции, численное решение систем дифуравнений и т.п.). Напр., разработанный в Sandia Laboratories пакет AZTEC ( http://www.cs.sandia.gov/CRF/aztec1.html ) специализирован на решение с ис- пользованием многопроцессорных систем линейных алгебраических уравне- ние (СЛАУ) с разреженными матрицами. AZTEC включает в себя процедуры, реализующие итерационные методы Крылова: • метод сопряж |