СКИПОДы 2007 полная версия (1127795), страница 51
Текст из файла (страница 51)
Обзор языка2.1. Модель программирования и модель параллелизмаЯзык Fortran DVM (FDVM) представляет собой язык Фортран 77 [5], расширенныйспецификациями параллелизма. Эти спецификации оформлены в виде специальныхкомментариев, которые называются директивами. Директивы FDVM можно условноразделить на три подмножества:Распределение данных (разделы 2, 3, 4, 8, 9)Распределение вычислений (разделы 5, 7)Спецификация удаленных данных (раздел 6)Модель параллелизма FDVM базируется на специальной форме параллелизма по данным:одна программа – множество потоков данных (ОПМД). В этой модели одна и та жепрограмма выполняется на каждом процессоре, но каждый процессор выполняет своеподмножество операторов в соответствии с распределением данных.В модели FDVM пользователь вначале определяет многомерный массив виртуальныхпроцессоров, на секции которого будут распределяться данные и вычисления.
При этомсекция может варьироваться от полного массива процессоров до отдельного процессора.На следующем этапе определяются массивы, которые должны быть распределены междупроцессорами (распределенные данные). Эти массивы специфицируются директивамиотображения данных (раздел 4). Остальные переменные (распределяемые по умолчанию)отображаются по одному экземпляру на каждый процессор (размноженные данные).Размноженная переменная должна иметь одно и то же значение на каждом процессоре заисключением переменных в параллельных конструкциях (см. раздел 5.1.3, 5.1.4 и 7.5).Модель FDVM определяет два уровня параллелизма:параллелизм по данным на секции массива процессоров;параллелизм задач – независимые вычисления на секциях массива процессоров.Параллелизм по данным реализуется распределением витков тесно-гнездового цикла междупроцессорами (раздел 5). При этом каждый виток такого параллельного цикла полностьювыполняется на одном процессоре.
Операторы вне параллельного цикла выполняются поправилу собственных вычислений (раздел 5.2).170Параллелизм задач реализуется распределением данных и независимых вычислений насекции массива процессоров (раздел 7).При вычислении значения собственной переменной процессору могут потребоваться какзначения собственных переменных, так и значения несобственных (удаленных)переменных. Все удаленные переменные должны быть указаны в директивах доступа кудаленным данным (раздел 6).Язык Sisal.Цели создания языка SISAL:создание универсального функционального языка;разработка техники оптимизации для высокоэффективных параллельных программ;достижение эффективности исполнения, сравнимой с императивными языками типа Fortranи C;внедрение функционального стиля программирования для больших научных программ.Название языка расшифровывется как "Streams and Iterations in a Single AssignmentLanguage", сам он представляет собой дальнейшее развития языка VAL, известного всередине 70-х годов.
Среди целей разработки языка SISAL следует отметить наиболеехарактерные, связанные с функциональным стилем программирования:Эти цели содателей языка SISAL подтверждают, что функциональные языки способствуютразработке корректных параллельных программ. Одна из причин заключается в том, чтофункциональные программы свободны от побочних эффектов и ошибок, зависящих отреального времени. Это существенно снижает сложность отладки. Результаты переносимына разные архитектуры, операционные системы или инструментальное окружение. Вотличие от императивных языков, функциональные языки уменьшают нагрузку накодирование, в них проще анализировать информационные потоки и схемы управления.Легко создать функциональную программу, которая является безусловно параллельной,если ее можно писать, освободившись от большинства сложностей параллельногопрограммирования, связанных с выражением частичных отношений порядка междуотдельными операциями уровня аппаратуры.
Пользователь Sisal-а получает возможностьсконцентрироваться на конструировании алгоритмов и раз работке программ в терминахкрупноблочных и регулярно организованных построений, опираясь на естественныйпараллелизм уровня постановки задачи.Начнем с примера программы:1. Вычисление числа π (пи).For% инициирование циклаApprox := 1.0;Sign := 1.0;Denom := 1.0;i := 1while i <= Cycles do % предусловие завершения циклаSign := -Sign;% однократныеDenom := Denom + 2.0;% присваиванияApprox := Approx + Sign / Denom;% образуютi := i + 1% тело цикла171returns Approx * 4.0% выбор и вычисление результата циклаend for2.
Это выражение также вычисляет число π (пи).for i in [1..Cycles/2] do% пространство параллельно% исполнимых итерацийval := 1.0/real(4*i-3) — 1.0/real(4*i-1);% тело цикла, для каждого i% исполняемое независимоreturns sum( val ) % выбор и свертка результатов% всех итераций циклаend for * 4.0 % вычисление результата% выраженияЭто выражение вычисляет сумму всех вычисленных значений val и умножает результат на4.0.3, 4. В for-выражениях операции dot и cross могут порождать пары индексов приформировании пространства итерирования:for i in [1..2] dot j in [3..4] do% для пар индексов [1,3] и% [2,4]returns product (i+j)% произведение суммend for % = 24for i in [1..2] cross j in [3..4] do% для пар [1,3], [1,4], [2,3]% и [2,4]returns product (i+j)% произведение суммend for % = 6005.
Итеративное for-выражение с обменом данными между итерациями:forI := 1while I < S doK := I;I := old I + 2;% значение из предыдущей итерацииJ := K + I;returns product(I+J)end forКак это свойственно языкам фукнционального программирования, Sisal языкматематически правильный — функции отображают аргументы в результаты без побочныхэффектов, и программа строится как выражение, вырабатывающее значение. Наиболее172интересна форма параллельного цикла.
Она включает в себя три части: генераторпространства итераций, тело цикла и формирователь возвращаемых значений.SISAL-программа представляет собой набор функций, допускающих частичноеприменение, т.е. вычисление при неполном наборе аргументов. В таком случае поисходному определению функции строятся его проекции, зависящие от остальныхаргументов, что позволяет оперативно использовать эффекты смешанных вычислений иопределять специальные оптимизации программ, связанные с разнообразием используемыхконструкций и реализационных вариантов параллельных вычислений.function Sum (N); % Сумма квадратов result (+ ( sqw (1 .. N)));Обычно рассматривают оптимизации, обеспечивающие устранение неиспользуемого кода,чистку циклов, слияние общих подвыражений, перенос участков повторяемости дляобеспечения однородности распараллеливаемых ветвей, раскрутку или разбиение цикла,втягивание константных вычислений, уменьшение силы операций, удаление копийагрегатных конструкций и др.Система программирования Норма.Язык Норма является специализированным языком и предназначен для спецификациичисленных методов решения задач математической физики.
Изначально он былориентирован на решение задач математической физики разностными методами, однако,как показала практика, может быть использован для решения более широкого классавычислительных задач.Первоначально термин Норма расшифровывался следующим образом: НепроцедурноеОписание Разностных Моделей Алгоритмов. Сейчас мы считаем уместной и другуютрактовку - это Нормальный уровень общения прикладного математика с ЭВМ: расчетныеформулы, полученные им в процессе решения прикладной задачи, почти непосредственноиспользуются для ввода в вычислительную систему и проведения счета.В записи на Норме не требуется никакой информации о порядке счета, способахорганизации вычислительных (циклических) процессов.
Порядок предложений языкаможет быть произвольным -- информационные взаимосвязи выявляются и учитываютсятранслятором при организации вычислительного процесса. Программа на языке Нормаможет рассматриваться как описание запроса на вычисление, а реализация этого запроса сучетом архитектуры ЭВМ и возможностей выходного языка - то есть синтез выходнойпрограммы - возлагается на транслятор.Выбор уровня языка Норма определяет характерную его черту - это язык с однократнымприсваиванием, то есть каждая переменная может принимать значение только один раз.Такие понятия, как память, побочный эффект, оператор присваивания, управляющиеоператоры в языке Норма отсутствуют по определению.Эти свойства, и некоторые другие ограничения (в первую очередь, на вид индексныхвыражений и способы описания индексных пространств), позволяют строго обосноватьразрешимость задачи синтеза выходной программы [2,3], так как в достаточно общейпостановке решение этой задачи приводит к значительным математическим трудностям она может оказаться NP-полной либо вообще неразрешимой.
С другой стороны,исследования, связанные с разработкой и применением языка Норма показывают, чтоимеющиеся ограничения приемлемы с практической точки зрения [5].173Программа на Норме состоит из одного или нескольких разделов. Разделы могут быть трехвидов - главный раздел, простой раздел и раздел-функция, вид раздела определяетсяключевыми словами MAIN PART, PART, FUNCTION соответственно.Разделы могут вызывать друг друга по имени и передавать данные при помощи механизмаформальных и фактических параметров, или через внешние файлы при помощи описанийINPUT и OUTPUT.
Для каждого раздела справедливо правило локализации: имена,описанные в разделе, локализованы в этом разделе; понятие глобальных переменных вязыке отсутствует.Главный раздел обязательно должен присутствовать в программе на Норме и бытьединственным; формальных параметров он не имеет. Вызовы главного раздела, а такжерекурсивные вызовы разделов запрещены. В заголовке раздела указывается имя раздела исписок формальных параметров. Формальные параметры должны быть описаны в телераздела при помощи declaration-of-scalar-variables, declaration-of-variables-on-domains илиdeclaration-of-externalПараметры-величины, указанные до ключевого слова RESULT в списке формальныхпараметров, являются исходными данными для вычислений, описываемых в разделе;параметры, перечисленные после - являются результатами вычислений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
