Восход и закат High Performance Fortran: наглядный урок истории

Кен Кеннеди, Чарльз Коулбел, Ганс Зима Пересказ: Сергей Кузнецов

Я отважился пересказать статью из области компьютерных наук, в которой не являюсь специалистом. Но статья показалась мне настолько полезной, интересной и содержательной, что я взялся за это дело. Мне кажется, что смысл этой статьи выходит далеко за пределы тем параллельных версий языка Fortran, языков с распараллеливанием по данным и параллельных языков и компиляторов вообще. Это действительно интересный и поучительный пример того, как важное и полезное дело может не привести к ожидаемым и, по всей видимости, заслуженным результатам. Мне хотелось бы посвятить свою работу по пересказу этой статьи памяти одного из ее авторов, Кена Кеннеди, который скончался около года тому назад, 7 февраля 2007 г. Безусловно, это огромная потеря для компьютерного сообщества. Рекомендую прочитать подробную техническую биографию этого выдающегося человека

Сергей Кузнецов

Аннотация

High Performance Fortran (HPF) – это высокоуровневая система программирования с распараллеливанием по данным, основанная на языке Фортран. Работа по стандартизации HPF началась в 1991 г. на конференции по суперкомпьютерным вычислениям в Альбукерке (Albuquerque), где группа руководителей индустрии обратилась к Кену Кеннеди (Ken Kennedy) с просьбой возглавить работу по созданию языка общего назначения для появлявшегося класса параллельных компьютеров с распределенной памятью. Предлагаемый язык должен был фокусироваться на операциях с распараллеливанием по данным, выполняемым в одном потоке управления. Эта стратегия применялась в некоторых более ранних коммерческих и исследовательских системах, таких как CM Fortran компании Thinking Machines, Fortran D и Vienna Fortran.

Через год с небольшим группа по стандартизации, получившая название «Форум по высокопроизводительному Фортрану» (High Performance Fortran Forum, HPFF), создала определение языка, которое было опубликовано в январе 1993 г. в виде технического отчета Rice University [50], а позже в том же году – в журнале Scientific Programming [49].

Разработка HPF вызвала большую шумиху, и выпуск описания языка был хорошо принят сообществом. Однако через несколько лет в Соединенных Штатах энтузиазм пошел на убыль, хотя язык продолжал использоваться в Японии.

В статье прослеживается происхождение HPF от языков программирования, на которых он основывался. Рассматриваются основания технических решений, приведших к встраиванию в исходный вариант языка ряда дополнительных средств, и два варианта, которые за ним последовали: HPF 2.0 (расширения, введенные в течение новой серии встреч HPFF) и HPF/JA (диалект, используемый японскими компаниями и применяющийся в проекте Earth Simulator).

Уникальная особенность этой статьи состоит в обсуждении технических и социологических ошибок, допущенных как разработчиками языка, так и сообществом пользователей, ошибок, которые привели к преждевременному отказу от многообещающего подхода, использованного в HPF. Статья завершается изложением некоторых уроков, которые могут оказаться полезными в будущем, и разъяснением того, как идеи HPF влияют на разработку новых языков, выполняемую в рамках программы High Productivity Computing Systems, которая поддерживается DARPA.

1. Исторический контекст

Параллелизм – одновременное выполнение нескольких задач – является фундаментальным принципом разработки компьютеров. Параллелизм использовался даже в самых ранних компьютерных системах, в которых ввод-вывод совмещался во времени с вычислениями, и во время выполнения текущей команды из памяти выбиралась следующая команда. В некоторых компьютерах, таких как CDC 6600, использовалось несколько устройств исполнения команд, так что в одно и то же время можно было выполнить несколько длинных команд. В других компьютерах для совместного выполнения нескольких команд в одном устройстве исполнения применялась конвейеризация, что позволяло выдавать один элемент конечного результата на каждом цикле работы компьютера, хотя для выполнения каждой отдельной операции могло требоваться несколько циклов. Идея конвейеризации привела к появлению первых векторных компьютеров, характерным представителем которых является Cray-1 [31], в котором команду можно было применить к массивам входных элементов, каждая пара которых использовалась на одной единственной стадии работы конвейера операций. Векторные компьютеры преобладали на рынке суперкомпьютеров с конца 1970-х до начала 1980-х гг.

К середине 1980-х гг. становилось ясно, что параллельная обработка данных, использование нескольких процессоров для убыстрения одиночного приложения, в конце концов, заменит или, по крайней мере, потеснит векторную обработку данных как подход к конструированию развитых суперкомпьютерных систем. Однако было непонятно, какой должна быть модель высокоуровневого программирования. В этой статье прослеживается история High Performance Fortran (HPF), представителя одной из конкурирующих моделей, модели программирования с распараллеливанием по данным. Хотя проект HPF был важным благодаря своему открытому и публичному процессу стандартизации, это была всего лишь одна из многих проводившихся в то время работ по созданию языков и моделей параллельного программирования. При написании этой статьи авторы не стремились подробно рассмотреть все эти работы, поскольку это сделало бы тематику статьи слишком широкой. В статье представлен лишь минимальный материал, достаточный для иллюстрации взаимосвязей между идеями, лежавшими в основе HPF, и другими бытовавшими в то время тенденциями в области параллельного программирования.

Статья начинается с обсуждения архитектур параллельных компьютеров и того, как они влияли на разработку моделей программирования. На основе этого обсуждения приводится мотивация идей HPF. Затем описывается процесс стандартизации, характеристики языка и опыт ранних реализаций. В завершение статьи обсуждаются причины, приведшие, в конце концов, к отказу от HPF, и уроки, которые следует извлечь из истории этого языка.

1.1. Параллельные вычислительные системы

Компьютеры с распараллеливанием по данным. Вычислительная модель с распараллеливанием по даннымхарактеризуется тем свойством, что последовательности операций или операторов могут выполняться в параллель над каждым элементом набора данных. Среди наиболее ранних параллельных машин, разработанных в 1960-е гг., в которых эта модель была реализована на уровне аппаратуры, можно выделить архитектуры Solomon [87] и Illiac IV [9]. Последовательность команд обрабатывалась одним устройством управления, которое передавало каждую команду в массив простых процессорных элементов, скомпонованных в виде регулярной решетки. Процессорные элементы работали в строгом синхронном режиме, применяя одну и ту же команду к своим локальным данным и регистрам. Флинн (Flynn [37]) относит эти машины к архитектуре «одна команда – много данных» (Single-Instruction Multiple-Data (SIMD). При наличии решетки процессоров, у каждого из которых имеется отдельная локальная память, значения данных, находящиеся в памяти одного процессора и требующиеся другому процессору, приходится копировать по соединяющей их сети; этот процесс называется коммуникацией. Подобные межпроцессные коммуникации приводят к большим задержкам при потребности в доступе к данным других процессоров.

В векторных компьютерах, которые появились в 1970-х гг., и характерным представителем которых является Cray-1, использовалась архитектурная парадигма, поддерживающая простую форму параллелизма по данным на уровне аппаратуры. Как и в случае исходных архитектур SIMD, в векторных компьютерах выполнялся один поток управления. Ключевым отличием являлась предоставлявшаяся программистам повышенная гибкость за счет отсутствия необходимости специальной организации данных в соответствии с аппаратной конфигурацией процессоров. Кроме того, в векторном процессоре отсутствовали проблемы коммуникационных задержек, поскольку у него имелась единая совместно используемая память.

В 1980-х гг. достижения в области разработки сверхбольших интегральных схем позволили перейти к следующему поколению архитектур SIMD, характеризовавшемуся наличием тысяч однобитовых процессорных элементов при наличии аппаратной поддержки произвольных схем коммуникаций. Индивидуальные арифметические операции в этих машинах выполнялись очень медленно, поскольку обработка велась в «поразрядной» манере, т.е. по одному биту в каждый момент времени. Поэтому улучшение производительности достигалось исключительно за счет высокого уровня параллелизма. К важным представителям этого класса машин относятся CM-2 и CM-200 компании Connection Machines [52], а также MP-1 компании MasPar Computer Corporation [27].

В моделях программирования для SIMD-машин особое значение имели векторные и матричные операции над большими массивами. Это хорошо подходило для некоторых алгоритмов и областей приложения (например, программ, решающих задачи линейной алгебры, операций над регулярными сетками), но ограничивало применение машин в других контекстах (например, сложных системах моделирования по методу Монте-Карло). В частности, эта модель представлялась интуитивно понятной, поскольку в ней имелся единственный поток управления, что делало ее похожей на модель последовательного программирования. Как показано далее в статье, это модель сильно повлияла на разработку языков с распараллеливанием по данным.

Основное достоинство вычислений с распараллеливанием по данным – полностью синхронное функционирование – одновременно являлось самой большой слабостью этого подхода. Единственный способ выполнения условных вычислений состоял в выборочном отключении некоторых процессоров машины, что делало компьютеры с распараллеливанием по данным непригодными для использования при решении проблем, в которых отсутствует регулярность, таких как обработка разреженных матриц или вычисления на нерегулярных сетках. Дополнительным недостатком являлась схема обмена данными между процессорами. В большинстве случаев процессоры связывались только с ближайшими соседями в двух- или трехмерной решетке. (К важным исключениям относятся система STARAN[10] с ее сетью с двусторонней передачей данных («flip» network), CM-1, CM-2 и CM-200 [52] со связями в виде гиперкуба и MasPar MP-1[27] с глобальным маршрутизатором (Global Router).) Поскольку все операции являлись синхронными, передача данных в процессоры, отдаленные в решетке от отправителя, занимала достаточно большое время, что делало эти машины медленными при выполнении любых вычислений, для которых требовались удаленные коммуникации. Эти недостатки привели к выходу на первый план асинхронных параллельных компьютеров с более гибкой структурой взаимных связей.

Асинхронные параллельные компьютеры с разделяемой памятью. Важным шагом на пути к появлению сегодняшних машин явилась разработка архитектур, состоящих из набора полнофункциональных процессоров, каждый из которых мог независимо выполнять поток команд. В сообществе параллельного программирования полагали, что в наилучшей конструкции такой мультипроцессорной систем категории «много команд, много данных» (Multiple-Instruction Multiple-Data, MIMD) по классификации Флинна следует использовать некоторый вид памяти, разделяемой на уровне аппаратуры, поскольку в этом случае было бы легко реализовать модель программирования с совместно использумой памятью, которая считалась наиболее естественной с точки зрения программистов. В этой модели каждый из независимых процессоров имел доступ ко всей памяти машины. В виде коммерческих продуктов появилось большое число мультипроцессоров с совместно используемой памятью, которые в настоящее время принято называть «симметричными» мультипроцессорами (symmetric multiprocessors, SMP). Примерами подобных систем являются серия Alliant FX, CDC Cyber 205, серия Convex C, Cray XMP и YMP, Digital VAX 8800, Encore Multimax, ETA-10, FLEX/32, IBM 3090, Kendall Square KSR1 и KSR2, Myrias SPS-1 и SPS-2, серия Sequent Balance [5, 30, 97, 59, 62, 71, 74, 48, 32]. Следует заметить, что некоторые машины из этого списка (например, системы компаний Convex, Cray, ETA и IBM) были гибридными в том смысле, что каждый процессор мог выполнять векторные операции. Многие сегодняшние многоядерные архитектуры можно считать наследниками SMP.

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

Первой проблемой была масштабируемость: как масштабировать эти системы, чтобы они могли включать сотни и тысячи процессоров? Поскольку в большинстве ранних систем SMP использовалась шина – единственный многобитный канал, который можно мультиплексировать в разные промежутки времени для обеспечения коммуникаций между процессорами и памятью, – общая пропускная способность доступа к памяти ограничивалась средним числом бит, которые можно было передавать по шине в заданный промежуток времени. Для вычислительных приложений с интенсивными обращениями к памяти шина обычно становилась перегруженной, когда число процессоров превышало 16. В более поздних системах с этой проблемой пытались бороться путем использования координатных коммутаторов (crossbar switch), но всегда приходилось выбирать между существенными дополнительными расходами на улучшенную схему соединений и потерей производительности подсистемы основной памяти.

Вторая проблема присутствовала в самой модели программирования. Многие производители предлагали параллельные программные конструкции, такие как параллельные циклы, которые при неправильном использовании могли приводить к чрезвычайно неприятным ошибкам категории «гонок по данным» (data race). Гонки по данным возникают, когда две параллельные задачи, такие как шаги параллельного цикла, обращаются к одной и той же ячейке памяти, причем, по крайней мере, одна из задач пишет в эту ячейку. В этом случае при разных планах параллельного выполнения могут получаться разные результаты. Такие ошибки трудно обнаруживать и устранять, потому что они не повторяются; в результате для установления отсутствия гонки по данным во время отладки требуется проверить все возможные планы. В векторных компьютерах проблема гонок по данным не возникает, поскольку во всех соответствующих языках программирования поддерживается единственный поток управления, и компилятор может определить, какие операции в программе можно корректно представить на основе векторных операций.

Компьютеры с распределенной памятью. Проблемы масштабируемости совместно используемой памяти привели к существенному изменению в направлении параллельных вычислений. На основе академических (Caltech Cosmic Cube [85] и Suprenum [41]) и коммерческих (транспьютерные сети [41]) исследовательских проектов возникла новая парадигма, названная параллелизмом на основе распределенной памяти (или, более элегантно, мультикомпьютинг (multicomputing)). В компьютерах с распределенной памятью у каждого процессора имелась собственная основная память, и процессоры связывались в сеть, организованную в виде двух- или трехмерной решетки или гиперкуба. Такая архитектура была более масштабируемой, чем шинные архитектуры, использовавшиеся в машинах с общей памятью.

У распределенной памяти имелись два основных преимущества. Во-первых, использование масштабируемых сетей делало большие системы намного более рентабельными (за счет введения дополнительной задержки доступа к данным). Во-вторых, можно было собирать системы с гораздо большим суммарным объемом памяти. В то время почти во всех микропроцессорах использовались 32-битные адреса (или адреса еще меньшей длины). Таким образом, в системе с разделяемой памятью можно было адресовать только 2³² различных элементов памяти. С другой стороны, в системе с распределенной памятью такой объем памяти можно было адресовать на любом процессоре. Следовательно, распределенная память позволяла обеспечить решение проблем, для которых требовалась память гораздо большего объема.

Не удивительно, что преимущества распределенной памяти оборачивались сложностью программирования. Чтобы один процессор мог получить доступ к элементу памяти другого процессора, процессор, в локальной памяти которого хранился этот элемент данных, должен был послать его процессору, запрашивавшему данный элемент; чтобы использовать данные, нужно было их сначала получить. Посылку и получение данных нужно было тщательно синхронизовать, чтобы обеспечивать обмен правильными данными, поскольку сравнительно просто сопоставить операцию приема данных не соответствующей ей операции посылки данных. При использовании этого подхода, стандартизованного, в конечном счете, в виде Message Passing Interface (MPI) [70, 88, 42], требуется, чтобы программист полностью отвечал за управление коммуникациями и синхронизацию. Таким образом, переход к распределенной памяти привел к утрате удобств, свойственных разделяемой памяти, но при этом сохранилась сложность нескольких потоков управления, привнесенных архитектурой SMP.

Небольшое упрощение обеспечила стандартная для таких систем модель программирования «одна программа, много данных» (Single-Program Multiple Data, SPMD) [58, 34], в которой на каждом процессоре выполняется одна и та же программа над разными частями пространства данных; обычно на каждом процессоре обрабатывалась та порция пространства данных, которой владел данный процессор. При использовании этой модели, являющейся очевидным обобщением модели распараллеливания по данным SIMD, требуется, чтобы реализация явно синхронизовала процессоры до коммуникации, поскольку, возможно, в каждый заданный момент времени на них выполняются разные части программы. Однако такая модель позволяет эффективно использовать индивидуальные для каждого процессора управляющие структуры для обработки локальных данных в промежутках между шагами коммуникаций и дает возможность программисту более тщательно сосредотачиваться на коммуникациях в пределах адресного пространства каждого процессора. Это является важным усовершенствованием, но не полностью устраняет бремя управления коммуникациями вручную.

1.2. Программная поддержка параллельного программирования

Вообще говоря, имеются три программных стратегии для поддержки параллельных вычислений: (1) автоматическое распараллеливание программ на последовательных языках, (2) модели и языки явного параллельного программирования и (3) языки с распараллеливанием по данным; третья стратегия представляет собой смесь первых двух стратегий. В следующих пунктах рассматриваются некоторые наиболее важные идеи этих трех стратегий. Особое внимание уделяется тому, как эти стратегии используются для поддержки параллелизма по данным, что является наиболее распространенным подходом для достижения масштабируемости в научных приложениях.

Автоматическое распараллеливание. Исходная идея программирования для машин с совместно используемой памятью состояла в адаптации методов автоматической векторизации, которые оказались довольно успешными при создании векторизованных программ на основе последовательных спецификаций на языке Fortran [3, 99]. (Хотя в официальных стандартах написание названия языка было изменено с « FORTRAN » на «Fortran», только начиная с Fortran 90, в данной статье для всех версий языка используется позднейшая форма написания названия.) В этих методах использовалась теория зависимостей [65, 63, 4], которая позволяет установить, используются ли в каких-либо двух разных обращениях к массиву одинаковые адреса памяти, чтобы можно было выяснить, возможно ли преобразование данного цикла в последовательность векторных присваиваний. Это преобразование заключается в разделении цикла по каждому оператору и последующей перезаписи каждого полученного цикла в виде последовательности присваиваний векторных регистров. Основная идея состоит в том, что любой оператор, прямо или косвенно зависящий сам от себя, не может быть перезаписан таким образом.

Векторизация была исключительно успешной технологией, поскольку концентрировалась на оптимизации внутренних циклов, что проще понималось программистами. Несмотря на то, что «унаследованные» («dusty-deck») фортрановские программы не всегда хорошо векторизовались, пользователям обычно удавалось переписать эти программы в форме «векторизуемых циклов», что позволяло добиться их эффективного выполнения на различных машинах. Казалось разумным предположение, что аналогичного успеха можно добиться и при распараллеливании для машин с совместно используемой памятью.

Но, к сожалению, при распараллеливании программ для SMP возникли дополнительные сложности. В то время как векторное выполнение программ являлось, по существу, синхронным, с обеспечением синхронизации по каждой операции, для мультипроцессорного параллелизма требовались явные операции синхронизации (на основе, например, барьеров или событий), создающие дополнительные накладные расходы в придачу к тем, которые тратились на запуск задач и обеспечение совместного доступа к данным через несколько кэшей. Для компенсации этих расходов компилятору требовалось либо найти очень крупные циклы, которые можно было бы подразделить на крупные части, либо суметь параллелизовать внешние циклы. Анализ зависимостей, который хорошо работал для векторизации, теперь требовалось применять к гораздо более крупным циклам, часто включавшим вызовы подпрограмм. Это вынудило исследователей сосредоточиться на межпроцедурном анализе как стратегии определения того, какие циклы могли бы выполняться в параллель [93, 16, 29].

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

Проблемы автоматического распараллеливания еще более усложняются при использовании систем с распределенной памятью и передачей сообщений. Кроме того, что в компиляторе приходится решать проблемы обнаружения параллелизма и управления его гранулярностью; в нем также необходимо найти схему размещения данных, минимизирующую расходы на коммуникации. Проблеме автоматического размещения данных посвящался ряд исследовательских проектов [67, 60, 6, 23, 44], но созданные стратегии мало применяются в коммерческих компиляторах, в которых для всех массивов всегда используется стандартная схема размещения данных (обычно с обычным или циклическим разбиением на блоки).

Явное параллельное программирование: PCF и OpenMP. Проблемы автоматического распараллеливания вынудили часть сообщества параллельного программирования искать простые методы явной спецификации параллелизма в приложениях. Для мира Fortran это означало появление конструкций параллельных циклов, параллельных переключателей и параллельных задач, ориентированных на различные коммерческие мультипроцессоры с общей памятью. Проблемой являлось отсутствие согласованности этих конструкций между разными вычислительными платформами. Для решения этой проблемы группа, возглавлявшаяся Дэвидом Куком (David J. Kuck) из Иллинойского университета и включавшая исследователей и разработчиков из университетских, коммерческих и правительственных лабораторий, начала разработку стандартного набора расширений Fortran 77, которые должны были обеспечить возможности спецификации параллелизма на уровне циклов и задач. Группа получила название Parallel Computing Forum (PCF). Кен Кеннеди участвовал во всех собраниях этой группы и активно способствовал подготовке заключительного проекта документа, в котором определялся язык PCF Fortran [66], язык с одним потоком управления, поддерживающий SPMD-параллелизм на основе конструкций параллельных циклов, параллельных переключателей и «параллельных регионов» («parallel regions»). Конструкция «параллельного региона» создавала среду выполнения SPMD, в которую можно было встраивать ряд явно специфицированных параллельных циклов. PCF Fortran также включал механизмы явной синхронизации и правила распределения памяти внутри параллельных конструкций.

Основные конструкции PCF Fortran позднее были стандартизованы комитетом X3H5 (Parallel Extensions for Programming Languages) ANSI и, в конце концов, проникли в неформальный стандарт OpenMP [73, 33].

Основное ограничение расширений PCF и OpenMP состоит в том, что они предназначались для мультипроцессоров с совместно используемой памятью с одинаковым для всех процессоров временем доступа к памяти; наиболее мощные представители таких мультипроцессоров вытеснялись системами с распределенной памятью. Хотя на основе OpenMP or PCF Fortran можно генерировать код и для систем с передачей сообщений, у пользователей отсутствует какая-либо возможность управления коммуникациями или размещением данных на уровне исходного текста программ, что приводит к серьезным проблемам производительности.

Языки с распараллеливанием по данным. Одним из способов преодоления трудностей, свойственных модели PCF/OpenMP, является использование явной передачи сообщений. При использовании этого подхода стандартный язык (такой как Fortran или C/C++) расширяется библиотекой передачи сообщений (такой как MPI), обеспечивающей программисту полное управление разделением данных, их распределением между процессорами и требуемыми коммуникациями. Однако вскоре стало понятно, что эта парадигма программирования приводит к появлению сложных и подверженных ошибкам программ, поскольку применяемые алгоритмы и коммуникации становятся тесно переплетенными.

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

Эти вопросы привели к появлению нового класса языков с распараллеливанием по данным, на которые сильное воздействие оказали парадигма программирования SIMD и близость к доминирующей модели последовательного программирования. В языках с распараллеливанием по данным крупные структуры данных приложения раскладывались по частям в локальную память процессоров параллельной машины с распределенной памятью. После этого подкомпоненты этих распределенных структур данных могли обрабатываться в параллель на всех процессорах. К ключевым свойствам этих языков относятся наличие глобального пространства имен и единого потока управления по операторам языка на уровне исходного текста программ, когда отдельные параллельные операторы выполняются на всех процессорах (слабо) синхронным образом. (Вычисление называется слабо (loosely) синхронным, если оно состоит из перемежающихся фаз вычислений и межпроцессорных коммуникаций.) Коммуникации не программируются явным образом, и соответствующий код генерируется автоматически системой компиляции/поддержки времени исполнения на основе декларативной спецификации схемы размещения данных.

При любом обсуждении языков с распараллеливанием по данным нельзя не затронуть Fortran 90, поскольку это была первая версия языка Fortran, включавшая операторы присваивания массивов. В Fortran 90 поведение оператора присваивания массивов определялось таким образом, как если бы все массивы, используемые в правой части присваивания, копировались в векторные регистры неограниченной длины и полностью на них обрабатывались до того, как в левой части присваивания будет произведено какое-либо сохранение данных. Если рассматривать элементы векторного регистра неограниченной длины как распределенную память, то присваивание массивов в Fortran 90 можно считать операцией распараллеливания по данным. Кроме того, при наличии крупной SIMD-машины, такой как CM-2 компании Thinking Machines, можно также выполнять в параллель присваивания многомерных массивов. Именно по этой причине Fortran 90 оказал такое влияние на последующие языки с распараллеливанием по данным. Однако с появлением более сложных систем с распределенной памятью стало проблематичным достижение хорошей производительности программ на Fortran 90, поскольку при распределении данных нужно было учитывать наряду с ограничениями на объем доступной памяти каждого процесса требования балансировки нагрузки и расходы на коммуникации.

В конце 1980-х и начале 1990-х гг. был разработан ряд новых языков с распараллеливанием по данным для параллельных машин с распределенной памятью, включая Fortran D [38, 53], Vienna Fortran [102, 21], CM Fortran [91], C* [45], Data-Parallel C, pC++ [14] и ZPL [89, 19]. В разработку HPF и требуемую технологию компиляции внесло свой вклад и несколько других академических и коммерческих проектов [7, 47, 79, 68, 69, 77, 78, 80, 81, 95 57, 51, 75].

Безусловно, подход языков с распараллеливанием по данным не был всеми принят ни в сообществе исследователей методов компиляции, ни в сообществе разработчиков приложений. У каждой из трех стратегий поддержки программного обеспечения, описанных в этом разделе, имелись свои горячие сторонники. Оглядываясь назад, следует заметить, что ни одна из этих стратегий не стала практически превалирующей: до настоящего времени доминирующим подходом к разработке масштабируемых приложений остается явное использование передачи сообщений на основе MPI. Основная причина состоит в том, что каждой из этих стратегий в той или иной степени свойственны сложность проблем параллелизации на основе использования компиляторов, размещения данных и оптимизации коммуникаций. Далее в статье авторы сосредотачиваются на подходе к распараллеливанию по данным, примененном в расширениях HPF языка Fortran. В частности, исследуются причины неудачи HPF. Однако многие факторы, не позволившие подходу HPF добиться успеха, свойственны и другим подходам.

2. HPF и его предшественники

В конце 1980-х и начале 1990-х гг. Fortran все еще оставался доминирующим языком в области технических расчетов, которая, в свою очередь, обеспечивала крупнейший рынок масштабируемых машин. Поэтому было естественно предполагать, что версия языка Fortran с распараллеливанием по данным будет хорошо принята сообществом пользователей, поскольку она могла бы способствовать эффективному использованию огромного количества программ, написанных на этом языке. К числу наиболее важных языков с распараллеливанием по данным, основанных на Fortran и оказавших глубокое воздействие на разработку HPF, относятся два исследовательских языка Fortran D и Vienna Fortran, а также один коммерческий продукт CM Fortran.

В этом разделе рассматриваются основные характеристики каждого из этих языков. Раздел завершается описанием работ, приведших к возникновению процесса стандартизации HPF, и обзором самого этого процесса.

Fortran D. В 1987 г. исследовательская группа в университете Rice, руководимая Кеном Кеннеди, начала сотрудничать с Джеффри Фоксом (Geoffrey Fox) в области поддержки средств высокоуровневого программирования для компьютеров с распределенной памятью. Фокс обратил внимание на то, что основной проблемой при написании приложения для системы с распределенной памятью являлся выбор правильного распределения данных, поскольку после совершения этого выбора реальный параллелизм определялся потребностью минимизации коммуникаций. Таким образом, можно было выполнять вычисления в параллель на процессорах, владеющих данными, которые участвовали в вычислениях. Это привело к той идее, что программы, написанные на некотором языке с моделью совместно используемой памяти и единственного потока управления, можно компилировать в эффективный код для системы с распределенной памятью, если программисты обеспечат информацию о том, как следует распределить данные между процессорами. Фокс и группа университета Rice создали спецификацию нового языка, названного ими Fortran D, в котором поддерживалось средство двухуровневого определения распределения данных, похожее на то, которое позже было включено в HPF. Основная идея состояла в том, что группы массивов выравнивались в соответствии с некоторым абстрактным объектом, называемом шаблоном (template). Затем все эти массивы отображались на процессоры с помощью одного оператора распределения данных, который отображал шаблон на эти процессоры.

В Fortran D поддерживались блочное, циклическое и блочное циклическое (иногда называемое cyclic(k)) распределения шаблонов на процессоры в нескольких измерениях. Для каждого отдельного распределения требовалось определять свой шаблон. Однако этот механизм можно было использовать для гарантированного обеспечения того, чтобы массивы разных размеров, такие как разные сетки в многосеточных вычислениях, отображались на правильные процессоры.

Конечно, язык с распараллеливанием по данным, каким являлся Fortran D, был бы бесполезным, если бы отсутствовала возможность его компиляции в код с разумной эффективностью для любой целевой параллельной платформы. Проблема состояла в том, что нужно было произвести декомпозицию вычислений и отобразить их на процессоры таким образом, чтобы минимизировать расходы на коммуникации. Кроме того, компилятор должен был генерировать код для коммуникаций, когда это требовалось, и оптимизировать эти коммуникации таким образом, чтобы данные передавались между каждой парой процессоров в виде крупных блоков, а не последовательностей отдельных слов. Это было очень важно, поскольку в то время большая часть расходов на коммуникацию измерялась временем доставки первого байта (задержки были очень большими, а пропускная способность – вполне разумной).

Fortran D был ориентирован на использование коммуникационных библиотек, поддерживающих двухсторонние протоколы: чтобы передать данные из одного процессора в другой, процессор, владеющий данными, должен был послать их, а процессор, нуждающийся в данных, – принять данные. Это затрудняло генерацию коммуникационного кода, поскольку компилятор должен был определить, в каких точках программы нужно было выполнить примитивы send и receive на каждом процессоре.

Для решения проблемы разделения вычислений в проекте университета Rice была выработана стратегия «считает владелец» («owner-computes»), в соответствии с которой вычисления распределялись по процессорам поблизости от данных, которые надлежало обрабатывать. В частности, в первом прототипе компилятора Rice использовалась стратегия «считает левосторонний владелец» («left-hand-side owner-computes»), согласно которой каждый оператор компилировался таким образом, чтобы все вычисления выполнялись на процессорах, владеющих результатами предыдущих вычислений. (Строго говоря, компиляторы Fortran D, как большинство других реализаций языков с распараллеливанием по данным, являлись трансляторами исходного текста в исходный текст, генерирующими SPMD-реализацию, такую как Fortran плюс вызовы примитивов передачи сообщений, как «объектного кода». На самом деле, одной из движущих сил (не основной) начала процесса стандартизации MPI являлось стремление обеспечить машинно-независимую цель для компиляторов языков с распараллеливанием по данным.)

Первая статья, описывающая стратегию компиляции Rice, была написана Каллаханом и Кеннеди, представлена в 1988 г. на конференции LCPC (International Workshop on Languages and Compilers for Parallel Computing) в Корнеле и включена в подборку материалов этой конференции, напечатанную в Journal of Supercomputing [18]. (Ранее в том же году Зима (Hans P. Zima), Баст (Heinz-J. Bast) и Гендт (Michael Gerndt) опубликовали статью про средство параллелизации SUPERB [100], в котором также использовался подход распределения данных и вычислений.) Хотя Каллахан и Кеннеди описывали стратегию «считает владелец» в ее начальной форме, оптимизации коммуникаций и вычислений выполнялись локально с использованием преобразований, заимствованных из традиционных методов оптимизации кода. Когда этот подход оказался неэффективным, группа университета Rice переключилась на использование стратегии компиляции целых вложенных циклов, каждого по отдельности. Эта работа описывалась в серии статей, в которых также обсуждалась реализация прототипа, основанного на этом новом подходе [54, 53, 94]. Хотя представленные результаты были получены для довольно небольших программ, эти статьи демонстрировали значительное улучшение производительности, подтверждающее жизнеспособность компиляции на основе распределения данных и вычислений. В центре процесса компиляции находится преобразование из глобального пространства индексов массивов, поддерживаемого в Fortran D, в локальное индексное пространство каждого процессора. Для выполнения этого преобразования компилятору нужно для каждого цикла выявить, для каких итераций не требуются коммуникации, для каких итераций требуется послать данные в другой процессор, и для каких итераций требуется получить данные до выполнения каких-либо вычислений. Краткое изложение этого подхода можно найти в главе 14 книги Алена (Randy Allen) и Кеннеди [4].

Для генерации правильного кода всей программы на языке Fortran D требовалось решить одну важную проблему: как в каждой точке программы определить, какое распределение было ассоциировано с каждым массивом данных? Поскольку распределения сами не являлись объектами данных, их было невозможно явно передавать в подпрограммы; вместо этого они неявно ассоциировались с массивами данных, передаваемыми в качестве параметров. Для генерации кода подпрограммы компилятор должен был следовать одному из трех подходов: (1) на уровне всей программы выполнять некоторый анализ развития распределений, (2) полагаться на описания, обеспечиваемые программистами в интерфейсе каждой процедуры или (3) динамически определять распределения во время выполнения программы на основе дескриптора каждого распределенного массива. Группа Fortran D решила, что динамическое определение распределений слишком замедляло бы работу программы, а рассчитывать на подсказки программистов было бы непрактично, особенно в тех ситуациях, когда библиотеки могли бы создаваться при отсутствии вызывающей программы. В результате в компиляторе Fortran D производился межпроцедурный анализ распространения распределений данных, в результате чего он становился компилятором программы целиком. Это упрощало проблемы межпроцедурных границ, но усложняло структуру компилятора. Позже этот подход был признан неприемлемым группой по стандартизации HPF.

Vienna Fortran. В 1985 г. в германском университете города Бонн группа под руководством Ганса Зимы начала разработку новой системы компиляции SUPERB для языка с распараллеливанием по данным в контексте германского суперкомпьютерного проекта Suprenum [41]. В качестве исходных данных система SUPERB [100] принимала текст программы на языке Fortran 77 и спецификацию обобщенного блочного распределения данных, производя в результате параллельную программу с явной передачей сообщений для архитектуры с распределенной памятью Suprenum с использованием стратегии «считает владелец». Этот подход, который сначала понимался как выполнение вычислений на процессоре, владеющем левой частью оператора присваивания (или, в более общем смысле, целью вычислений), позже был обобщен до стратегии выбора любого процессора с максимизацией локальности вычислений. Позже эта идея стала одной из наиболее важных идей HPF. Диссертация на соискание ученой степени PhD Микаела Герндта [40], завершенная в 1989 г., является первой работой, в которой полностью описаны преобразования программ, требуемые для такой трансляции. Обзор этой технологии компиляции представлен Зимой и Чэпмен (Barbara Chapman) в [101].

Проект SUPERB не был направлен на разработку языка. Он посвящался преобразованиям программ в компиляторах, и для спецификации распределений данных использовалась специально подобранная нотация. Однако после того, как группа Зимы перебралась в Венский университет, они начали в сотрудничестве с Пийушем Меротрой (Piyush Mehrotra) из института ICASE (Institute for Computer Application in Science and Engineering) при NASA работу над полной спецификацией высокоуровневого языка с параллелизмом по данным в контексте Fortran.

Этот новый язык, получивший название Vienna Fortran, обеспечивал программистам возможность определения массивов виртуальных процессоров, а распределения рассматривались как отображения из пространств индексов многомерных массивов в (под)множества пространств процессоров. Особый акцент делался на поддержке нерегулярных и адаптивных программ: в дополнение к регулярным блочными циклическим блочным классам распределений в языке поддерживались обобщенное блочное и косвенноераспределения. При использовании обобщенного блочного распределения, унаследованного от проекта SUPERB, измерение массива разделялось на непрерывные части произвольной длины, которую можно было вычислять во время выполнения программы. Такие распределения, если их использовать совместно с переупорядочиванием, позволяют эффективно представлять нерегулярные сетки. Косвенные распределения представляют собой другой механизм, предназначенный для решения проблем нерегулярности. В этом случае допускается спецификация произвольных отображений между множествами индексов массивов и процессорами. И обобщенное блочное, и косвенное распределения позже были включены в спецификацию HPF 2.0, описываемую в разд. 5. Реализация обоих этих распределений затруднительна, поскольку реальные отображения остаются неизвестными до времени выполнения. Поэтому компилятор должен генерировать код для шага предварительной обработки, иногда называемого инспектором [26, 96], который во время выполнения определяет расписание коммуникаций и балансирует нагрузку между различными процессорами.

Ключевым компонентом спецификации языка Vienna Fortran являлись определяемые пользователями распределения и выравнивания. Хотя эта возможность была реализована только частично, она мотивировала исследования в области распределенных представлений разреженных матриц [96] и обеспечила важные идеи для недавней реализации подобных методов в высокоэффективном языке Chapel [17]. В системе Vienna Fortran Compilation System расширялись функциональные возможности компилятора Vienna Fortran Compilation System, поддерживалась большая часть конструкций языка, хотя основной акцент делался на оптимизации нерегулярных алгоритмов. Обзор технологии компиляции, использовавшейся в этой системе, приведен в статье Бенкнера (Siegfried Benkner) и Зимы [12].

CM Fortran. CM Fortran был первой коммерческой реализацией языка с распараллеливанием по данным. Этот язык разрабатывался группой компании Thinking Machines Corporation (производителя серии Connection Machines) под руководством Гая Стила (Guy Steele) и группой программистов из небольшой софтверной компании COMPASS, Inc. под руководством Дэвида Лавмена (David Loveman) и Роберта Моргана (Robert Morgan). Целью проекта CM Fortran являлась поддержка разработки технических приложений для машины CM-2 с архитектурой SIMD, выпущенной в 1987 г. Исходная модель программирования для машины CM-2 и ее предшественников основывалась на языке *Lisp, поскольку компания изначально ориентировалась на приложения искусственного интеллекта. Однако в 1991 г. с целью привлечения пользователей из областей науки и техники был выпущен компилятор с языка Fortran [91].

В CM Fortran были включены операторы присваивания массивов и арифметические операции над массивами, вошедшие в спецификацию Fortran 90, а также средство, которое в последний момент было удалено из этого стандарта: оператор FORALL, обеспечивающий очень простой способ спецификации присваивания массива в стиле задания цикла. Массивы, используемые в этих операторах, классифицировались как CM-массивы и отображались на множества виртуальных процессоров (virtual processor, VP), по одному элементу массива на каждый процессор. В свою очередь, VP регулярным образом отображались на реальные процессоры CM-2. Это отображение можно было изменить с использованием опциональных директив ALIGN и LAYOUT. В отличие от Fortran D, в CM Fortran для спецификации схемы размещения данных для массивов данных в SIMD-массиве процессоров CM-2 использовались директивы компилятору, вводимые пользователями как комментарии. Каждое присваивание массива компилировалось в последовательность SIMD-инструкций, вычисляющих маски исполнения, перемещающих данные и вызывающих реальные вычисления. Эта простая и эффективная стратегия была дополнена в компиляторе Thinking Machines стратегией секционирования (“slicewise”), позволяющей сократить избыточные пересылки данных и маскирование.

Возможности программирования в среде CM Fortran были развиты благодаря наличию библиотеки общих вычислительных и коммуникационных примитивов CMSSL, разработанной под руководством Леннарта Джонссона (Lennart Johnsson). Кроме мощных вычислительных примитивов, библиотека включала ряд глобальных операций, таких как sum reduction и scatter/gather, которые используются для преобразования данных с нерегулярной структурой в компактные массивы и наоборот. Многие из этих подпрограмм были позднее включены в спецификацию библиотеки HPF.

Когда компания Thinking Machines выпустила в 1993 г. машину CM-5 с архитектурой MIMD, она сохранила для новой архитектуры язык CM Fortran, что показывает популярность и переносимость этой модели.

Процесс стандартизации HPF. В ноябре 1991 г. на конференции Supercomputing ’91 в Альбукерке (Нью-Мехико) к Кеннеди и Фоксу обратились с запросом о возможности стандартизации синтаксиса распараллеливаемых по данным версий языка Fortran. Движущими силами этого процесса являлись коммерческие поставщики, в частности, компания Thinking Machines, производившая масштабируемые параллельные машины с распределенной памятью. В создании кросс-платформы для языка Fortran была также заинтересована компания Digital Equipment Corporation (DEC), которая стремилась включить в нее многие специальные средства, входящие в DEC Fortran.

После начальных обсуждений этой идеи Кеннеди и Фокс организовали встречу с представителями академических и промышленных кругов на сессии birds-of-a-feather. Участники пришли к согласию применить более формальный процесс стандартизации на основе группы, которую стали называть High Performance Fortran Forum (HPFF). Кеннеди согласился возглавить HPFF, а роль исполнительного директора взялся исполнять Чарльз Коулбел (Charles Koelbel). При поддержке Исследовательского центра параллельных вычислений (Center for Parallel Computation Research, CRPC) университета Rice была срочно организована встреча, которая состоялась в январе 1992 г. в г. Хьюстон, Техас. Интерес к процессу стандартизации проявился и в большом числе участников встречи (около 100 человек), и в активных обсуждениях в течение презентаций. В заключение встречи была проведена бизнес-сессия, на которой более 20 компаний взяли на себя обязательства поддерживать процесс подготовки нового стандарта.

По причине высокого уровня интереса и наличия реальной потребности в новом стандарте участники договорились постараться получить результат в течение примерно одного года. Хотя полностью выполнять работу за это время не удалось, это «управленческое» соглашение повлияло на характеристики языка. Наличие жесткого временного графика вынудило участников процесса следовать неформальному правилу, в соответствии с которым в HPF включались только те средства, полезность которых уже была продемонстрирована не менее чем в одном языке и компиляторе (включая компиляторы, созданные в рамках исследовательских проектов). Конечно, этот подход ограничивал набор обсуждаемых средств, в особенности, в области развитых методов распределения данных. Однако следует заметить, что правило «поддержки рассматриваемого средства не менее чем в одном компиляторе» часто нарушалось. В частности, комитет выяснил, что отсутствует какой-либо полностью удовлетворительный механизм описания интерфейсов подпрограмм, продемонстрированный в каком-либо языке, и поэтому был использован ряд дополнительных средств.

Активные участники HPFF (30-40 человек) проводили двухдневные совещания через каждые шесть недель, и эти совещания чаще всего проходили в одном из отелей Далласа, Техас, выбранного по причине удобного воздушного сообщения. (Отчасти умышленно в том же отеле позже организовывались совещания участников Message Passing Interface Forum (MPIF). Один из участников обоих комитетов в шутку говорил, что это единственный в мире отель, в котором он может сказать бармену: «как обычно» и получить правильную выпивку.) Среди постоянных участников совещаний встречалось немало талантливых людей. Кроме Кеннеди и Коулбела, в число редакторов документа стандарта входили Марина Чен (Marina Chen), Боб Найтен (Bob Knighten), Дэвид Лавмен, Роб Шрайбер (Rob Schreiber), Марк Снир (Marc Snir), Гай Стил, Джоэл Вильямсон (Joel Williamson) и Мэри Зоусел (Mary Zosel). В таб. 1 приведен более полный список участников HPFF, упорядоченный по названиям компаний, которые они представляли. Названия компаний включены в список на основании двух соображений: во-первых, у каждой организации (представители которой участвовали не менее чем в двух из последних трех встреч) имелся один голос; во-вторых, перечень организаций иллюстрирует широту кругозора группы. Имелись представители компаний, производящих аппаратуру и программное обеспечение, университетские исследователи, пользователи правительственных и производственных приложений. HPFF не являлся проектом одной организации, это был процесс, в котором формировалось согласованное общее мнение разных сторон.

Таблица 1. Участники (и организации) процесса HPFF, 1992-1993 гг.

David Reese (Alliant)	Jerrold Wagener (Amoco)
Rex Page (Amoco)	John Levesque (APR)
Rony Sawdayi (APR)	Gene Wagenbreth (APR)
Jean-Laurent Philippe (Archipel)	Joel Williamson (Convex Computer)
David Presberg (Cornell Theory Center)	Tom MacDonald (Cray Research)
Andy Meltzer (Cray Research)	David Loveman (Digital)
Siamak Hassanzadeh (Fujitsu America)	Ken Muira (Fujitsu America)
Hidetoshi Iwashita (Fujitsu Laboratories)	Clemens-August Thole (GMD)
Maureen Hoffert (Hewlett Packard)	Tin-Fook Ngai (Hewlett Packard)
Richard Schooler (Hewlett Packard)	Alan Adamson (IBM)
Randy Scarborough (IBM)	Marc Snir (IBM)
Kate Stewart (IBM)	Piyush Mehrotra (ICASE)
Bob Knighten (Intel)	Lev Dyadkin (Lahey Computer)
Richard Fuhler (Lahey Computer)	Thomas Lahey (Lahey Computer)
Matt Snyder (Lahey Computer)	Mary Zosel (Lawrence Livermore)
Ralph Brickner (Los Alamos)	Margaret Simmons (Los Alamos)
J. Ramanujam (Louisiana State)	Richard Swift (MasPar Computer)
James Cownie (Meiko)	Barry Keane (nCUBE)
Venkata Konda (nCUBE)	P. Sadayappan (Ohio State)
Robert Babb II (OGI)	Vince Schuster (Portland Group)
Robert Schreiber (RIACS)	Ken Kennedy (Rice)
Charles Koelbel (Rice)	Peter Highnam (Schlumberger)
Don Heller (Shell)	Min-You Wu (SUNY Buffalo)
Prakash Narayan (Sun)	Douglas Walls (Sun)
Alok Choudhary (Syracuse)	Tom Haupt (Syracuse)
Edwin Paalvast (TNO-TU Delft)	Henk Sips (TNO-TU Delft)
Jim Bailey (Thinking Machines)	Richard Shapiro (Thinking Machines)
Guy Steele (Thinking Machines)	Richard Shapiro (United Technologies)
Uwe Geuder (Stuttgart)	Bernhard Woerner (Stuttgart)
Roland Zink (Stuttgart)	John Merlin (Southampton)
Barbara Chapman (Vienna)	Hans Zima (Vienna)
Marina Chen (Yale)	Aloke Majumdar (Yale)

Эта группа сталкивалась с многочисленными техническими и политическими проблемами. Многие из них возникали из-за противоречий в потребности языковых возможностей высокого уровня и желании добиться простой реализации. С самого начала было понятно, что HPF должен быть достаточно гибким и мощным, чтобы на его основе можно было реализовать широкий набор приложений, демонстрирующих хорошую производительность. Однако у реальных приложений существенно различаются структуры данных и способы их обработки, поэтому для поддержки этих приложений требовались разные методы распределения данных. Для реализации каждого метода распределения данных, встраиваемого в язык, требовалась масса усилий со стороны разработчиков компиляторов. Какого количества методов разделения данных было бы достаточно? Например, рассмотрим циклическое блочное распределение, в котором группы из k строк или столбцов массива назначаются циклическим образом процессорам из массива процессоров. Опыт разработки исследовательских компиляторов показывал, что при реализации этого метода распределения возникали бесспорные сложности. Некоторые члены HPFF выступали против включения соответствующих возможностей в HPF. Однако, в конце концов, они были включены в язык, поскольку такое распределение требовалось для балансировки вычислительной нагрузки между процессорами при выполнении треугольных вычислений типа тех, которые производятся в плотной линейной алгебре (например, LU-разложение квадратной матрицы). Вообще говоря, именно потребность в балансировке нагрузки с целью достижения максимального увеличения быстродействия путем назначения каждому процессору одного и того же объема вычислений мотивирует потребность в развитом наборе методов распределения данных.

Проблемы противоречий между мощностью языка и сложностью реализации усложнялись отсутствием большого опыта разработки компиляторов языков с распараллеливанием по данным. Исследовательские компиляторы, большей частью, являлись академическими прототипами, применявшимися лишь к немногим приложениям обычно небольшого размера. С другой стороны, CM Fortran был относительно новым языком с не такими развитыми возможностями, как у Fortran D и Vienna Fortran. Поэтому многие решения принимались без наличия полного понимания их влияния на сложность компиляторов.

Еще одним сложным решением был выбор между Fortran 77 и Fortran 90 в качестве основы нового языка. В начале процесса стандартизации HPF Fortran 90 являлся новым стандартом. Проблема состояла в том, что у большинства компаний, производивших параллельные машины, имелись компиляторы, которые воспринимали только Fortran 77. Эти компании неохотно брали на себя обязательства реализовать полный стандарт Fortran 90 в качестве первого шага по направлению к HPF. С другой стороны, компании, которые уже ориентировали свои компиляторы на Fortran 90, такие как Thinking Machines, хотели иметь возможность пользоваться преимуществами более развитого языка. В конце концов, пользователи, участвовавшие в процессе стандартизации, склонили общее мнение в пользу Fortran 90. Для этого имелось много оснований. Одним из основных из них было то, что в состав Fortran 90 входили средства, обеспечивающие большую понятность определению языка HPF, в частности средства спецификации интерфейсов подпрограмм. Кроме того, спецификация Fortran 90 включала синтаксис операций над массивами, который согласовывался с понятием глобальных массивов. Такие операции помогали распознавать глобальные операции, которые можно было бы выполнять в параллель. Оглядываясь в прошлое, авторы считают это решение ошибочным, поскольку реализация Fortran 90 усложнила задачу создания компилятора в разумное время. Как отмечается в разд. 4, это привело к замедлению разработки компиляторов HPF и, тем самым, ограничило признание языка.

Еще одна крупная техническая проблема состояла в потребности выработки способа работы с информацией о распределениях в подпрограммах. Разработчики технических приложений на языке Fortran полагались на возможность построения библиотек подпрограмм, широко распространяемых в академических институтах и продаваемых коммерческими компаниями, такими как IMSL и NAG. Для достижения успешности HPF требовалось обеспечить возможность разрабатывать библиотеки, которые работали бы корректно с параметрами-массивами с разными распределениями. Таким образом, требовалось наличие возможности определения внутри подпрограммы, какие распределения данных ассоциированы с массивами, передаваемыми этой подпрограмме.

В проекте Fortran D решение этой проблемы было возложено на межпроцедурный компилятор. Понятно, что поставщики, участвующие в HPFF, не хотели следовать этому подходу, потому что в большинстве коммерческих компиляторов отсутствовали какие-либо возможности межпроцедурного анализа (даже если не затрагивать вопрос о том, пожелали ли бы поставщики библиотек предоставлять свои исходные тексты). Таким образом, при разработке языка требовалось определить способ объявления распределений параметров, чтобы библиотеки подпрограмм HPF можно было использовать с разными распределениями без нанесения серьезного вреда производительности. Основная проблема здесь состояла в том, стоит ли перераспределять массив в пределах подпрограммы, или же следует каким-то образом «унаследовать» распределение от вызывающей программы. Перераспределение данных приводит к расходам на перемещение данных при входе в подпрограмму и выходе из нее, но позволяет подпрограмме использовать то распределение, которое является оптимальным для заложенного в нее алгоритма. Наследование распределения вызывающей программы позволяет избежать расходов на перераспределение, но может повредить производительности из-за того, что полученное распределение не соответствует алгоритму, или из-за расходов на динамическую интерпретацию полученного распределения. Эти проблемы были наиболее сложными в техническом отношении во всем процессе стандартизации, и связанные с ними части стандарта являются наименее понятными.

Этот пример иллюстрирует одну из проблем, с которой сталкивались участники процесса стандартизации HPF, и плотность графика, на котором основывался этот процесс. Хотя с самого начала участники согласились включать в стандарт только те средства, которые были опробованы в некотором исследовательском прототипе или коммерческой реализации, группа временами игнорировала этот принцип и подменяла опыт интуицией.

Результатом этой работы явился новый язык, который был завершен в начале 1993 г. [50,49] и представлен на Supercomputing Conference осенью того же года. Особенности языка обсуждаются в следующем разделе.

В 1994 г. была проведена дополнительная серия совещаний участников HPFF с целями (1) внести исправления, пояснения и толкования в существующий стандарт и (2) обсудить новые средства, требуемые для расширения функциональных возможностей HPF. В качестве руководителя снова выступал Кен Кеннеди, а Мэри Зоусел взяла на себя роль исполнительного директора. В этих совещаниях в основном участвовали те же люди, что на встречах в 1992-1993 гг. Наиболее заметными новыми участниками были Ян Фостер (Ian Foster, Argonne National Laboratory) и Джоэл Сольц (Joel Saltz, University of Maryland), которые возглавили подгруппы, рассматривающие новые аспекты. Исправления вошли в состав спецификации стандарта High Performance Fortran 1.1, которая являлась немного исправленной версией документа 1993 г. и была представлена в ноябре 1994 г. на конференции Supercomputing’94 в Вашингтоне. В самом документе HPF 1.1 отмечаются некоторые аспекты языка, требующие дальнейшего прояснения (эти аспекты не влияют на примеры, приводимые в следующем разделе). Обсуждавшиеся новые возможности и пояснения, не вошедшие в HPF 1.1, были собраны в HPF Journal of Development и послужили стартовой точкой процесса стандартизации HPF 2, обсуждаемого в разд. 5.

3. Язык HPF

Цели процесса разработки HPF были довольно простыми:

• Обеспечить удобную поддержку программирования для масштабируемых параллельных компьютерных систем, обращая особое внимание на параллелизм по данным.
• Предоставить понятную машинно-независимую модель программирования, обладающую тремя основными качествами:
  1. У разработчиков приложений должна иметься возможность представлять память как единое совместно используемое адресное пространство даже на машинах с распределенной памятью; другими словами, массивы должны являться глобально доступными, но распределенными по памятям процессоров, участвующих в вычислениях.
  2. Должно казаться, что у программ, написанных на новом языке, имеется единственный поток управления, чтобы такая программа могла бы корректно выполняться на одном процессоре; таким образом, весь параллелизм должен происходить из параллельного применения операций к распределенным структурам данных.
  3. Код коммуникаций должен генерироваться неявно, чтобы от программиста не требовалось заботиться о деталях определения межпроцессорных обменов сообщениями и управлении ими.
• Обеспечить возможности генерации кода, эффективность которого была бы сопоставима с эффективностью наилучшей «ручной» реализации того же приложения с использованием MPI.

Для достижения этих целей в стандарте HPF 1.0 определялся язык с рядом новых характеристик.

Во-первых, язык основывался на Fortran 90, а расширения определялись как набор «директив», представляемых в форме комментариев Fortran 90. Эти директивы могли интерпретироваться компиляторами HPF как рекомендации относительно того, как генерировать параллельные программы. На скалярных машинах HPF-программы могли выполняться без изменений путем игнорирования этих директив, если машины располагали памятью достаточного объема. Этот подход, который позже был перенят группой по стандартизации OpenMP, позволял точно отделить параллельные расширения HPF от основной программы на Fortran 90: в программу по-прежнему требовалось встроить алгоритм распараллеливания по данным, но одна и та же программа могла работать как на последовательных, так и на параллельных системах. От компиляторов для последовательных систем не требовалось распознавание каких-либо директив HPF. Следует заметить, что возможность выполнения по-существу одной и той же программы на последовательной и параллельной машинах обеспечивает огромное преимущество программистам при отладке алгоритма.

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

REAL A(1000,1000), B(1000,1000)
DO J = 2, N
  DO I = 2, N
    A(I,J)=(A(I,J+1)+2*A(I,J)+A(I,J-1))*0.25 &
&          + (B(I+1,J)+2*B(I,J)+B(I-1,J))*0.25
  ENDDO
ENDDO

Директива DISTRIBUTE указывает, как следует разделить массив данных по памятям реальной параллельной машины. В данном случае наиболее естественно распределить первое измерение, поскольку итерации по нему могут выполняться в параллель. Например, программист может распределить данные смежными участками между доступными участками, введя директиву

!HPF$ DISTRIBUTE A(BLOCK,*)

после объявления массива A. В HPF также обеспечиваются другие стандартные схемы распределений, включая CYCLIC, в которой элементы назначаются процессорам циклически, и CYCLIC(K), в которой процессорам циклически назначаются блоки из K элементов. Вообще говоря, схема BLOCK обеспечивает предпочтительное распределение для вычислений с поэлементными коммуникациями ближайших соседей, в то время как варианты схемы CYCLIC допускают более тонкую балансировку некоторых вычислений.

Кроме того, во многих вычислениях (включая приведенный выше пример) для разных массивов данных следует использовать одну и ту же схему размещения данных или родственные схемы. В этих случаях директива ALIGN указывает поэлементное соответствие между массивами. Например, чтобы придать массиву B то же распределение, что и у массива A, программист мог бы использовать директиву

!HPF$ ALIGN B(I,J) WITH A(I,J).

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

При использовании этих директив приведенному выше фрагменту программы соответствовал бы следующий HPF-вариант:

REAL A(1000,1000), B(1000,1000)
!HPF$ DISTRIBUTE A(BLOCK,*)
!HPF$ ALIGN B(I,J) WITH A(I,J)
DO J = 2, N
  DO I = 2, N
    A(I,J)=(A(I,J+1)+2*A(I,J)+A(I,J-1))*0.25 &
&          + (B(I+1,J)+2*B(I,J)+B(I-1,J))*0.25
  ENDDO
ENDDO

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

Как показывали проекты Fortran D и Vienna Fortran, особенно сложно было определять распределения данных аргументов подпрограмм. Механизм, который, в конце концов, был принят в HPF, можно кратко описать следующим образом. Формальные аргументы подпрограммы (т.е. переменные, объявленные внутри подпрограммы) можно было ассоциировать с директивами ALIGN и DISTRIBUTE. Если эти директивы полностью специфицировали распределение данных, то действительные аргументы (т.е. объекты, передаваемые вызывающей программой) должны были перераспределяться в соответствии с этой новой схемой распределения данных при обработке вызовы и подвергаться обратному перераспределению при возврате из подпрограммы. Конечно, предполагалось, что, если распределения вызывающей и вызываемой программ находились в соответствии, то компилятор или система поддержки времени исполнение воздержатся от копирования данных, требуемого для их перераспределения. В HPF также определялась система «унаследованных» распределений, при использовании которой распределение формальных аргументов являлось идентичным распределению действительных аргументов. Для такого объявления требовалось наличие явного интерфейса подпрограммы, такого как блок INTERFACE в Fortran 90. В этом случае отсутствовала необходимость в каком-либо копировании, но генерация кода подпрограммы становилась более сложной, поскольку требовалось обрабатывать все возможные входные распределения. На самом деле, эта сложность была настолько велика, что, насколько известно авторам, такой подход не был полностью реализован ни в одном компиляторе.

Кроме директив, определяющих распределения, в HPF имелись специальные директивы, которые можно было использовать для поддержки распознавания параллелизма. Поскольку HPF основывался на Fortran 90, в нем присутствовали операции над массивами, позволяющие явно выразить свойство поэлементного параллелизма. Эти операции были особенно уместными, когда применялись к распределенному измерению; в этом случае компилятор мог (относительно) простым образом управлять как синхронизацией, так и перемещением данных. При использовании нотации операций над массивами, приведенный выше пример мог бы выглядеть следующим образом:

REAL A(1000,1000), B(1000,1000)
!HPF$ DISTRIBUTE A(BLOCK,*)
!HPF$ ALIGN B(I,J) WITH A(I,J)
DO J = 2, N
    A(2:N,J) = &
&    (A(2:N,J+1)+2*A(2:N,J)+A(I,J-1))*0.25 &
&   + (B(3:N+1,J)+2*B(2:N,J)+B(1:N-1,J))*0.25
ENDDO

Вдобавок к этому, в HPF имелась возможность определять, какие итерации цикла должны выполняться в параллель. Более точно, директива INDEPENDENT говорила, что следующий за ней цикл можно выполнять в параллель. Это можно проиллюстрировать на еще одном варианте предыдущего примера:

REAL A(1000,1000), B(1000,1000)
!HPF$ DISTRIBUTE A(BLOCK,*)
!HPF$ ALIGN B(I,J) WITH A(I,J)
DO J = 2, N
  !HPF$ INDEPENDENT
  DO I = 2, N
    A(I,J)=(A(I,J+1)+2*A(I,J)+A(I,J-1))*0.25 &
&          + (B(I+1,J)+2*B(I,J)+B(I-1,J))*0.25
  ENDDO
ENDDO

Использование этой директивы обеспечивало генерацию кода с параллельным циклом любым компилятором HPF, которому была бы представлена подобная программа. Многие компиляторы могли сами обнаруживать возможность параллельного выполнения цикла путем анализа программ, в которых индексные выражения в переменных цикла были линейными, на основе анализа зависимостей и информации о распределениях. Однако директива INDEPENDENT существенно важна для циклов, которые теоретически не поддаются анализу, – например, для циклов, итерирующих над ребрами неструктурированной сетки, которые содержат проиндексированные индексы. Часто у программиста имеется специализированное знание, позволяющее выполнять такие циклы в параллель.

Хотя наличие директивы INDEPENDENT противоречит цели поддержки единственного потока управления, в стандарте удалось обойти эту проблему, определив эту директиву как утверждение, что в цикле отсутствуют зависимости между итерациями, которые могли бы вызвать «гонки данных» (data races); если это утверждение оказывалось неверным, то программа объявлялась не соответствующей стандарту. Таким образом, HPF-программа, соответствующая стандарту, всегда должна была производить одни и те же результаты на скалярной и параллельной машинах. К сожалению, из-за наличия этого средства было невозможно установить во время компиляции, соответствует ли стандарту данная программа.

В HPF также имелся оператор FORALL, позаимствованный из CM Fortran и ранних вариантов Fortran 90, обеспечивающий альтернативные средства для выражения присваивания массивов. Вложенный цикл из примера релаксационного цикла можно было записать следующим образом:

FORALL (J = 2:N, I=2:N) &
&    A(I,J)=(A(I,J+1)+2*A(I,J)+A(I,J-1))*0.25 &
&           + (B(I+1,J)+2*B(I,J)+B(I-1,J))*0.25

Семантически оператор FORALL был идентичен оператору присваивания массивов; он вычислял значения в правой части для всех значений индексов до того, как сохранить результаты в какой-либо области памяти правой части. (Имелся также мультиоператор FORALL, который применял это семантическое правило по очереди ко всем присваиваниям в своем теле.) Наличие явной индексации позволяет использовать FORALL для удобного выражения более широкого набора видов массивов и вычислений, чем это возможно при использовании стандартного присваивания массивов. Это демонстрирует следующий пример:

! Assignment to a diagonal, computed its index
FORALL (I=1:N) A(I,I) = I*I

High Performance Fortran был одним из первых языков, в стандарте которого специфицировалась соответствующая библиотека HPF Library. В библиотеке обеспечивались специальные глобальные операции, такие как sum reduction, gather и scatter, частичные префиксные операции. В библиотеку были включены многие параллельные операции над глобальными массивами, показавшие себя полезными в других языках с распараллеливанием по данными, таких как CM Fortran. Эта библиотека невероятно повысила мощность языка. Спецификация ассоциированной библиотеки теперь является стандартной практикой для языков C, C++ и Java.

Наконец, HPF включал ряд средств, способствующих совместимости и интероперабельности с другими языками и моделями программирования. В частности, поддержка интерфейса EXTRINSIC позволяла вызывать подпрограммы, написанные на других языках, таких как скалярный Fortran и C. Особенно важной была возможность вызова подпрограмм, написанных на основе MPI, что позволяло более эффективно переписывать подпрограммы HPF.

4. Опыт использования языка

Первую реакцию на появление HPF можно охарактеризовать как осторожный энтузиазм. Большая часть сообщества пользователей, которая еще не переписала свои приложения с использованием средств явной передачи сообщений, надеялась на то, что этот язык обеспечит высокоуровневый программный интерфейс для параллельных машин, позволяющий сделать параллельные программы переносимыми и эффективными без потребности в ручном написании коммуникационного кода с использованием MPI или подобных ему средств. С другой стороны, поставщики надеялись на то, что появление HPF позволит расширить рынок масштабируемых параллельных компьютеров настолько, что это повысит прибыльность их бизнеса. Некоторые поставщики, включая Digital [46], IBM [43] и Thinking Machines, инициировали независимую разработку компиляторов. Ряд других поставщиков предлагал пользователям варианты компиляторов, созданные независимыми производителями программного обеспечения, такими как Portland Group, Inc. (PGI) [15] и Applied Parallel Research [8]. На пике этой активности 17 поставщиков предлагали продукты HPF и более 35 крупных приложений, написанных на HPF, по крайней мере, в одном из которых содержалось более 100000 строк исходного кода.

Тем не менее, по мере накопления опыта использования языка возрастало и разочарование части пользователей. Становилось понятно, что с использованием HPF не так уж просто добиться ожидавшихся высокой эффективности и переносимости программ, и многие разработчики программного обеспечения отказывались от применения HPF и переключались на использование MPI. К концу 1990-х гг. поток использования HPF в США практически иссяк, хотя, в Японии сохранялся высокий уровень интереса к этому языку (см. ниже).

Почему же HPF не добился большего успеха, хотя язык опирался на вполне разумные идеи о том, как можно расширить существующий язык для включения в него поддержки параллелизма по данным? С точки зрения авторов, это было вызвано четырьмя основными причинами: (1) недостаточно развитой технологией компиляции и отсутствием терпения в сообществе HPC; (2) недостаточной поддержкой важных средств, которые сделали бы язык пригодным для решения широкого набора проблем; (3) несогласованностью реализаций, мешавшей пользователям достичь переносимой эффективности своих программ; (4) сложностью взаимосвязей между программой и производительностью, которая затрудняла определение и устранение проблем, связанных с производительностью. В следующих ниже подразделах эти причины анализируются более подробно.

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

Во-первых, HPF определялся поверх стандарта Fortran 90, который являлся первой крупной модернизацией стандарта языка Fortran с 1977 г. Кроме того, расширения Fortran 90 были непростыми: для их реализации требовались огромные усилия разработчиков компиляторов. К числу новых средств, добавленных в Fortran 90, относились следующие: (1) механизмы полной и частичной обработки массивов, для поддержки которых требовались реализации, основанные на использовании дескрипторов массивов, и «скаляризация» присваиваний массивов; (2) модули и блоки интерфейсов (которые требуются в HPF для спецификации распределений массивов, передаваемых в подпрограммы); (3) рекурсия; (4) динамическое распределения памяти и структуры данных, основанные на указателях. Поскольку ни одно из этих средств не присутствовало в Fortran 77, для построения компилятора Fortran 90 требовалось значительное изменение реализации, в которой должны были появиться стековые фреймы для поддержки рекурсии, динамически распределяемая память и дескрипторы массивов. Для перехода от Fortran 77 к Fortran 90 требовалась работа, соизмеримая с работой по созданию компилятора с нуля (за исключением низкоуровневой генерации кода). Ко времени появления в 1993 г. первой спецификации HPF в большинстве компаний еще не были выпущены первые компиляторы для Fortran 90. Поэтому для реализации HPF этим компаниям сначала нужно было почти полностью реализовать Fortran 90, что сильно препятствовало принятию HPF.

Во-вторых, полный набор средств HPF, включая HPF Library, был достаточно обширным, и для его реализации требовались новые стратегии компиляции, которые к моменту выпуска HPF 1.0 были опробованы только в исследовательских компиляторах и в компиляторе CM Fortran. Для корректной компиляции HPF-программ требовались обширный глобальный анализ распределений, разделение вычислений, генерация коммуникационного кода и оптимизации, такие как чередование коммуникаций и вычислений. Для хорошей реализации всего этого требовалась зрелая технология компиляции, достигаемая лишь с годами, даже если бы предусловием не являлась реализация Fortran 90.

Наконец, для эффективной реализации HPF-программ требовалось, чтобы в компиляторе особое внимание уделялось локальности на отдельных процессорах. Поскольку большую часть процессоров, использовавшихся в системах с распределенной памятью, составляли монопроцессоры со сложной иерархией кэшей, для генерации эффективного кода требовалось использование развитых стратегий преобразования, таких как нарезка циклов (loop tiling) для обеспечения повторного использования кэша. Ко времени выпуска начальной спецификации HPF эти методы становились все более понятными [39,98,64], но они еще не использовались в большинстве коммерческих компиляторов [84, 28].

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

Тем временем, у разработчиков параллельных приложений имелись свои временные ограничения, которые не позволяли им дожидаться поры зрелости HPF. Вместо этого они обращались к использованию языка Fortran с явными вызовами MPI, т.е. программной модели, которая была достаточно сложной, но, по крайней мере, готовой для применения. Миграция на платформу MPI существенно снизила потребность в HPF, что привело к сокращению объема работ коммерческих компаний по разработке компиляторов (а иногда и прекращению этой работы). В результате HPF так никогда и завоевал уровня признания в среде пользователей передовых параллельных компьютеров, достаточного для достижения успеха. Можно достаточно точно сказать, что HPF упустил первую волну разработчиков приложений и, по существу, умер (или, по крайней мере, стал восприниматься как неудачная попытка) до появления второй волны.

Отсутствующие средства. Для достижения высокой производительности на различных приложениях и алгоритмах в модели параллельного программирования должны поддерживаться различные разновидности распределений данных. Это особенно важно для разреженных структур данных и адаптивных алгоритмов. В исходную спецификацию HPF были включены только три основных распределения: BLOCK, CYCLIC и CYCLIC(K). Эти распределения были эффективными для вычислений над плотными массивами, а в случае CYCLIC(K) – даже для вычислений линейной алгебры. Однако многие важные алгоритмические стратегии было затруднительно, а иногда и невозможно выразить средствами HPF без большой потери производительности. Этот недостаток заметно сужал пространство приложений, которые можно было бы эффективно выразить средствами HPF. В результате разработчики приложений, которым требовались распределения, не поддерживаемые в HPF, переходили к использованию MPI. Хотя эта проблема была частично устранена в стандарте HPF 2.0 (обсуждаемом ниже), вред был уже нанесен. В заключительном разделе этой статьи авторы предлагают стратегию для решения этой проблемы в будущих языках с распараллеливанием по данным.

Второй проблемой использования HPF являлась ограниченная поддержка параллелизма на уровне задач. Немного выручала возможность параллельных циклов, но пользователям требовались более мощные стратегии задачного параллелизма. Опять же, этот недостаток был исправлен в HPF 2.0, но было слишком поздно. Должно было произойти слияние возможностей HPF и OpenMP, обсуждаемое ниже.

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

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

Во-вторых, для решения некоторых проблем удобства использования и производительности можно было использовать библиотеку HPF Library, описанную в предыдущих разделах. Например, для реализации вычислений над разреженными массивами можно было использовать примитивы gather и scatter. Однако отсутствовала эталонная реализация этой библиотеки с открытыми исходными текстами, так что в каждом проекте по разработке компилятора приходилось реализовывать собственную версию библиотеки. Количество и сложность компонентов библиотеки делали эту реализацию очень обременительной. Конечный результат состоял в том, что библиотеке уделялось недостаточное внимание, ее реализации были несогласованными и, как правило, не обеспечивали должную производительность. Поэтому пользователям снова приходилось кодировать свои приложения по-разному для разных целевых машин, используя те библиотечные подпрограммы, которые обеспечивали наилучшую производительность.

Трудности при настройке производительности. Все известные авторам компиляторы HPF производили трансляцию исходных текстов на HPF в тексты на языке Fortran плюс MPI. В процессе трансляции выполнялись многие существенные преобразования, которые затемняли связи между тем, что написал разработчик, и тем, что выполнялось на параллельной машине. Это затрудняло распознавание пользователями проблем производительности и их устранение.

Для решения проблемы распознавания проблем производительности группа разработчиков из университета Rice совместно с группой Дэна Рида (Dan Reed) из Иллинойского университета выполнила работу по отображению в исходные тексты программ на HPF диагностики, выдаваемой системой Pablo Performance Analysis, которая была основана на архитектуре передачи сообщений [2]. Эта работа была исключительно эффективной, и соответствующая реализация была выполнена, по крайней мере, для одного коммерческого компилятора, но проблеме настройке в ней уделялось недостаточное внимание. Другими словами, пользователь мог хорошо разобраться в том, что вызывает проблему производительности, но не иметь никаких идей насчет того, каким образом следует изменить текст программы на HPF, чтобы преодолеть эту проблему. Конечно, пользователь мог использовать интерфейс EXTRINSIC, чтобы спуститься на уровень MPI, но это сводило на нет все преимущества от использования HPF.

Проблема распознавания проблем производительности в контексте настройки производительности также решалась группой Vienna Fortran в сотрудничестве с группой Марии Калцаросса (Maria Calzarossa) из итальянского университета Pavia. В этом проекте разрабатывался графический интерфейс, на основе которого явно параллельный, основанный на MPI целевой код совместно с информацией о производительности, обеспечиваемой инструментальным средством MEDEA, мог привязываться к соответствующим исходным операторам. Например, с использованием этого средства программист, знакомый с принципами генерации кода для независимого цикла на основе парадигмы инспектор/исполнитель [83], мог на основе анализа выяснить, является ли источником проблемы производительности время, требуемое для выполнения работы по распределению данных, (автоматическая) генерация расписания коммуникаций инспектором или же реальные коммуникации, сгенерированные для выполнения цикла.

5. Процесс стандартизации HPF 2

В стремлении исправить некоторые недостатки в HPF 1.0 и 1.1 HPF Forum в 1995-1996 гг. предпринял вторую попытку стандартизации. Эта работа привела к созданию стандарта HPF 2.0, в который вошел ряд новых средств:

1. Раздел REDUCTION директивы INDEPENDENT, определяющей независимые циклы. Этот раздел существенно расширял множество случаев, в которых была применима директива INDEPENDENT. (В HPF 1.0 имелся раздел NEW директивы INDEPENDENT, разрешающий наличие «локальных» переменных в каждой итерации цикла, но отсутствовал какой-либо прямой способ выполнения простого суммирования.)
2. Новые процедуры HPF Library SORT_DOWN, SORT_UP для выполнения сортировки. (В HPF 1.0 имелись функции GRADE UP и GRADE DOWN, которые производили вектора перестановок, а не сортировали элементы непосредственно.)
3. Расширенные возможности отображения данных, включая отображение объектов на подмножества множества процессоров; отображения указателей и компонентов производных типов; схемы распределения GEN BLOCK и INDIRECT, а также модификаторы распределения RANGE и SHADOW. (Как отмечалось выше, в HPF 1.0 поддерживались только регулярные схемы распределения данных.)
4. Расширенные возможности управления параллельными вычислениями, включая директиву ON для спецификации процессора, на котором должны производиться вычисления, и директива TASK REGION, обеспечивающая выполнение крупноблочных параллельных задач. (В HPF 1.0 все отображения вычислений возлагались на компилятор и систему поддержки времени исполнения.)
5. Множество дополнительных внутренних и библиотечных (из HPF Library) процедур, в основном, имеющих дело с поддержкой запросов и управления распределениями данных. (В HPF 1.0 имелась некоторая поддержка этих возможностей, но оказалось, что требуется большее количество средств.)
6. Поддержка асинхронного ввода/вывода с использованием нового оператора WAIT, а также дополнительного управляющего параметра ввода/вывода в операторе языка Fortran READ/WRITE. (В HPF 1.0 средства ввода/вывода игнорировались.)

За исключением первых двух пунктов этого списка, новые возможности относились скорее к «усовершенствованным расширениям» («Approved Extensions»), а не к «базовому языку» («Core Language»). Группа HPFF предполагала, что поставщики незамедлительно реализуют средства базового языка (например, раздел REDUCTION), а расширения будут реализовываться в соответствии с приоритетами, устанавливаемыми требованиями заказчиков. Не удивительно, что это привело к неразберихе в наборах средств, предлагаемых в продуктах разных поставщиков. Насколько известно авторам, ни одна коммерческая компания или исследовательская группа даже и не попыталась реализовать полный набор усовершенствованных расширений.

6. Последствия и воздействия HPF

Хотя проект HPF не является безоговорочно успешным, он оказал и оказывает огромное влияние на разработку высокоуровневых параллельных языков. В текущей базе данных CiteSeer насчитывается 827 ссылок на исходный технический проект 1993 года, который позже был опубликован в журнале Scientific Programming [50]. Это наиболее часто цитируемый в 21-м веке материал из области компьютерных наук (по данным CiteSeer). Кроме того, в более чем 1500 публикаций, сохраняемых в CiteSeer, упоминается «High Performance Fortran». Во многих этих статьях представлены различные подходы к реализации языка или его усовершенствованию, что показывает всплеск интеллектуальной активности в академических кругах, вызванный проектом HPF.

6.1. Последствия для языка Fortran и его вариантов

Fortran 95. В то время, когда происходили встречи, приведшие к определению HPF 1.1, организовывались и совещания комитета X3J3 ANSI с целью разработки стандарта Fortran 95 [1]. Эта группа долгое время отслеживала разработку HPF в надежде перенять наиболее удачные решения, и Джерри Вагенер (Jerry Wagener) исполнял роль неформального связного между двумя группами. Кен Кеннеди представил комитету X3J3 параллельные возможности HPF и убедился в том, что нет никаких проблем с авторскими правами, которые могли бы воспрепятствовать включению средств HPF в официальный стандарт языка Fortran. Когда стандарт Fortran 95 [1] был официально принят в 1996 г., он включал средства FORALL и PURE, почти дословно позаимствованные из HPF. Новый стандарт также включал менее существенные расширения MAXLOC и MINLOC, которые были перенесены в HPF Library из CM Fortran. В обеих группах HPFF и X3J3 это совместное использование наработок расценивалось как положительное явление.

HPF/JA. В 1999 г. ассоциация Japan Association for High Performance Fortran, консорциум японских компаний, включающих Fujitsu, Hitachi и NEC, выпустила спецификацию HPF/JA [86], которая включала ряд средств из предыдущих языков программирования для параллельно-векторных машин компаний Hitachi и NEC. Важным вкладом в HPF/JA явился язык HPF+ [11], разработанный и реализованный в рамках европейского проекта, который выполнялся венской группой с участием NEC в качестве партнера. В языке HPF+, созданном на основе анализа развитых индустриальных программ, обеспечивался раздел REUSE для указания независимых циклов, с помощью которого определялось утверждения о повторной используемости расписания коммуникаций, вычисляемого при первом исполнении цикла. В том же контексте была введена конструкция HALO языка HPF+, позволяющая функционально специфицировать доступ к нелокальным данным в процессорах и обеспечить контроль пользователей над копированием таких данных в границах региона.

Эти и другие средства обеспечивали улучшенное управление локальностью в программах HPF/JA. Например, можно было использовать директиву LOCAL для указания того, что в некоторых ситуациях, которые трудно различить компилятору, для доступа к данным не требуются коммуникации. Кроме того, в HPF/JA присутствовала директива REFLECT, соответствующая директиве HALO языка HPF+. HPF/JA был реализован в обсуждаемом ниже проекте Japanese Earth Simulator [86].

OpenMP. Наконец, авторы комментируют взаимосвязи между HPF и OpenMP [73, 33]. Спецификация OpenMP была предложена как расширение языков Fortran, C и C++, обеспечивающее набор директив, которые поддерживали хорошо обоснованный интерфейс переносимого программирования для архитектуры SMP, основанный на модели «разветвление/соединение» (fork/join) параллельных вычислений. В этом стандарте развивалась работа, выполненная группой Parallel Computing Forum (PCF) в составе комитета по стандартизации X3H5 [66], и расширялся набор директив компании SGI для программирования с использованием разделяемой памяти. Разработчики OpenMP следовали модели HPF, специфицируя все средства в форме директив, которые могли игнорироваться компиляторами для монопроцессоров. Большая часть средств OpenMP была полностью совместима с HPF: в действительности, конструкции организации параллельных циклов в основном являлись расширениями соответствующих конструкций HPF.

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

Этот недостаток скоро был осознан, и был предпринят ряд попыток интегрировать OpenMP с языковыми средствами, которые поддерживали программирование с учетом локальности [72, 13]. Однако в текущем стандарте OpenMP не поддерживается ни одно их этих предложений. На самом деле, недавняя разработка языков высокой производительности (High Productivity Languages) может привести к тому, что подобные попытки устареют, поскольку во всех этих языках многопотоковость и учет локальности искусным образом интегрируются.

В заключение интересно отметить, что группа по разработке OpenMP, которая начала свою работу после выпуска HPF 1.0, определила синтаксис своих директив таким образом, что он оказался несовместимым с синтаксисом HPF. (Со своей стороны, группу OpenMP, вероятно, могло сбить с толку то, что в HPF был определен собственный синтаксис, а не использовались существующие конструкции PCF.) Лидеры обеих групп несколько раз встречались для изучения возможности унификации языков, поскольку это обеспечило бы каждому из них требуемые функциональные возможности, но совместный проект по стандартизации так и не был начат.

Использование HPF. После исходного выпуска High Performance Fortran состоялись три собрания группы пользователей HPF: первый в Санта Фе (Santa Fe, NM, 24-26 февраля 1997 г.), второй в Порто, Португалия (25-26 июня 1998 г.) и третий в Токио, Япония (18-20 октября 2000 г.). Во время этих собраний был проведен опрос пользователей для определения способов использования HPF и путей его дальнейшего развития. Доклады, представленные на собрании в Токио, вошли в специальный сдвоенный выпуск журнала Concurrency, Practice and Experience (Volume 14, Number 8-9, August 2002). Собрание в Токио показало сохранение высокого уровня заинтересованности в HPF в Японии. Позже этот интерес был подтвержден установкой системы Japanese Earth Simulator [86] и началом ее использования для прогона приложений. В Earth Simulator присутствовала реализация HPF с поддержкой широкого набора функциональных возможностей, изначально основанная на компиляторе компании Portland Group, в котором поддерживались расширения HPF/JA. В специальном выпуске Concurrency, Practice and Experience описывались два приложения, которые были перенесены в среду Earth Simulator и достигли производительности около 10 Teraflops. Приложение Impact3D показало производительность почти в 15 Teraflops, что составило около 40% пиковой скорости машины [82]; за это достижение разработчики приложения были удостоены награды Gordon Bell Prize на конференции SC2002. Ни одно из этих приложений не содержало явного использования MPI.

6.2. Языки HPCS

Хотя HPF потерпел неудачу на переднем крае разработки параллельных приложений, идеи этого языка проникают в более новые языки программирования. Недавно агентство DARPA (Defense Advanced Research Projects Agency) профинансировало разработку тремя коммерческими компаниями прототипов аппаратных и программных систем для проектов High Productivity Computing Systems (HPCS). Основной целью этой работы является ослабление бремени программирования передовых систем, основанных на инновационных архитектурах. Эти три компании предложили три новых языка: Chapel (Cray) [17, 20, 36], Fortress (Sun) [<90] и X10 (IBM) [22]. Во всех них присутствует некоторая форма параллелизма по данным.

Chapel, Fortress и X10 – это новые объектно-ориентированные языки, поддерживающие широкий набор средств программирования, параллелизм и безопасность. Во всех них поддерживаются глобальное пространство имен, явная многопотоковость и явные механизмы для работы с локальностью. Имеются средства для распределения массивов по вычислительным узлам системы, а также для установления связи между потоками управления и данными, которые ими обрабатываются. Наконец, в этих языках поддерживаются как параллелизм по данным, так и задачный параллелизм. Поскольку разработчики языков HPCS были знакомы с опытом создания HPF, они создали средства поддержки параллелизма по данным, в которых устранены многие недостатки, описанные в разд. 4.

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

X10 основан на языке Java; однако средства языка Java для поддержки параллелизма и массивов заменены средствами, более уместными для высокопроизводительных вычислений, такими как разделение глобального адресного пространства. В отличие от этого, Chapel – это полностью новый язык, основанный на идеях, которые считаются наиболее перспективными идеями в современном объектно-ориентированном подходе.

Управление локальностью. Во всех трех языках обеспечивается доступ пользователей к виртуальным единицам локальности, называемых локалями (locale) в Chapel, регионами (region) в Fortress и участками (place) в X10. Каждое выполнение программы привязывается к некоторому набору таких единиц локальности, которые отображаются операционной системой на физические сущности, такие как вычислительные узлы. Это обеспечивает пользователей механизмом для (1) распределения коллекций данных по единицам локальности, (2) выравнивания различных коллекций данных и (3) установления связи между вычислительными потоками управления и данными, над которыми они работают. Этот подход является очевидным обобщением ключевых элементов HPF.

В Fortress и X10 обеспечиваются обширные библиотеки встроенных распределений, а также имеется возможность порождения новых, определяемых пользователями распределений данных путем декомпозиции пространства индексов или комбинирования распределений в разных измерениях. В Fortress все массивы распределяются по умолчанию; если для некоторого массива никакое распределение не специфицировано, то ему назначается распределение по умолчанию. С другой стороны, в Chapel отсутствуют встроенные распределения, но обеспечивается обширная инфраструктура, которая поддерживает произвольные распределения данных, определяемые пользователями и являющиеся достаточно мощными для того, чтобы позволить работу с разреженными данными [36]. В X10 имеется «правило локальности» (Locality Rule), запрещающее в любой активности непосредственные чтение/запись по ссылкам на удаленные местоположения. В Chapel и Fortress на уровне исходного кода не проводится различие между локальными и удаленными ссылками.

Многопотоковость. В HPF параллельные циклы определяются с использованием атрибута независимости (independent attribute), который позволяет специфицировать утверждение о том, что цикл не содержит каких либо внутренних зависимостей. Это исключает ситуацию гонок данных. В Chapel различаются последовательные циклы «for» и параллельные циклы «forall», в которых итерации над элементами индексной области производятся без ограничений, аналогичных тем, которые в HPF вызывает наличие атрибута независимости. Таким образом, за избежание зависимостей, приводящих к гонкам данных, отвечают пользователи.

В Fortress цикл «for» по умолчанию является параллельным, так что, если итерации цикл выполняются над распределенным измерением массива, эти итерации будут группироваться по процессорам в соответствии с распределениями данных. Для сериализации цикла «for» можно использовать специальное «последовательное» распределение. Компилятор Fortress и система поддержки времени выполнения могут реорганизовывать исполнение программы для улучшения производительности, если при этом сохраняется ее смысл в рамках семантики организации циклов на основе распределения данных. В частности, распределение данных, по существу, приводит к суперазделению (overpartition) индексного пространства, так что операции можно динамически перемещать на свободные процессоры для балансировки нагрузки.

В X10 различаются два вида параллельных циклов: цикл «foreach», который ограничен единственной единицей локальности, и цикл «ateach», позволяющий выполнять итерации над несколькими единицами локальности. Как и по отношению к обсуждавшемуся выше «правилу локальности», разработчики X10 следуют здесь более консервативной стратегии, чем разработчики Chapel и Fortress, вынуждая программиста различать эти два случая.

6.3. Параллельные скриптовые языки Fortran и C

Хотя сообщества Fortan и C были склонны мириться с трудностями написания MPI-кода для масштабируемых параллельных машин, похоже, что к этому была не готова большая группа пользователей высокоуровневых скриптовых языков, таких как Matlab, R и Python. Популярность этих языков частично объясняется их простотой. Тем не менее, имеется реальный интерес к возможности написания на этих языках параллельных программ. В результате в ряде исследовательских и коммерческих проектов, включающих MathWorks, изучались возможности применения стратегий параллельного программирования, в особенности, в Matlab [76, 35, 55, 61]. В большинстве этих проектов стандартное представление массивов, принятое в Matlab, заменялось представлением глобальных распределенных массивов, и все стандартные операции над массивами заменялись распределенными операциями. Хотя это соответствует духу HPF, накладные расходы на создание вручную библиотек операций и коммуникаций ограничивает число разных распределений, которые могут поддерживаться в таких системах. Поэтому большинство текущих реализаций ограничивается распределениями, поддерживаемых ScaLAPACK, параллельной версией библиотеки LAPACK, который используется для реализации операций над массивами в продукте Matlab.

Проект, недавно начатый в университете Rice и возглавляемый Кеннеди, направлен на расширение технологии компиляции Rice HPF, описываемой в разд. 7, для обеспечения более обширного набора распределений массивов. Основная идея этой работы состоит в создании библиотеки операций над распределенными массивами в HPF и обеспечении возможности компилятору HPF адаптировать эти библиотечные подпрограммы ко всем поддерживаемым распределениям. В настоящее время в список поддерживаемых распределений входят sequential(*), block, block-cyclic и block(k) в каждом измерении плюс новое двухмерное распределение, называемое «multipartitioning», которое полезно для достижения максимально возможной производительности на эталонных тестовых наборах NAS Parallel Benchmarks. Однако обдумывается и ряд новых распределений, которые должны быть реализованы в ближайшем будущем.

Целью этих работ является обеспечение сообщества пользователей скриптовых языков, в особенности, пользователей Matlab простым методом достижения достаточно масштабируемого параллелизма при минимальном изменении их программ. Если усилия исследователей университета Rice окажутся успешными, то это позволит не только обосновать общий замысел работ, проводимых после неудачи с HPF, но также существенно расширить сообщество разработчиков приложений для масштабируемых параллельных машин.

7. Полученные уроки

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

Во-первых, за двенадцать лет, прошедших после выпуска HPF 1.0, удалось многое узнать о технологии компиляции. Понятно, что при применении первых компиляторов HPF было трудно достичь высокой производительности. Распространенной практикой являлась перепись прикладных тестовых наборов для использования сильных сторон компилятора HPF в расчете на конкретную целевую машину. Другими словами, разработчикам приложений приходилось переписывать приложение для каждой новой платформы. Показательным примером являются параллельные тестовые наборы NAS. В версию HPF тестовых наборов NAS был включен набор HPF-программ, написанных инженерами компании Portland Group. Эти тестовые программы были разработаны с целью достижения наибольшей возможной производительности с использованием компилятора Portland Group. Они позволяли избежать просчетов в генерации кодов, которые могли бы подорвать эффективность генерируемого кода. К сожалению, это подрывало цель HPF – обеспечение возможности кодировать приложение в машинно-независимой форме и его компиляции без каких-либо изменений для различных платформ. Иначе говоря, практика кодирования с учетом особенностей целевой машины подрывала простоту использования HPF, приводя к существенным затратам времени при переносе программ с одной платформы на другую.

В последние десять лет основной целью исследовательской работы в университете Rice, возглавляемой Джоном Меллор-Крумми (John Mellor-Crummey), было достижение высокой производительности на HPF-программах, которые получались путем внесения минимальных изменений в программы, ранее написанные на Fortran 90. Если говорить о параллельных тестовых наборах NAS, то это означало, что последовательную программу на Fortran 90 (со встроенным параллельным алгоритмом) нужно было бы изменить только путем добавления соответствующих директив распределения данных: все остальной должно было быть сделано компилятором. Окончательной целью являлась генерация кода, который мог бы конкурировать по производительности с написанными вручную MPI-версиями программ, разработанных для тестовых наборов NAS.

Этой цели невозможно было достичь с использованием компилятора dHPF, разработанного в проекте университета Rice, потому что в MPI-версиях использовалось распределение, называемое «мультиразделением» (multipartitioning), которое не поддерживалось ни в HPF 1.0, ни в HPF 2.0. После того как исследователи из университета Rice добавили мультиразделения к набору распределений, поддерживаемых dHPF, они смогли достичь производительности, которая всего на несколько процентов отличалась от производительности вручную написанных MPI-версий приложений SP и BT из набора NAS [25].

Этот результат подтверждается опытом использования HPF в среде Earth Simulator и последующим экспериментом, в котором компилятор dHPF транслировал приложение Impact3D для системы Lemieux Питтсбургского суперкомпьютерного центра (Pittsburgh Supercomputer Center; система основывалась на процессорах Alpha и коммутаторах компании Quadrics). На полученном целевом коде удалось добиться производительности в 17% от пиковой производительности системы при числе процессоров от 128 до 1024 (в последнем случае была достигнута производительность в 352 Gigaflops, что, вероятно, является национальным рекордом США для HPF-программ) [24].

Эксперименты с мультиразделением иллюстрируют еще один важный аспект расширения области применимости языков с распараллеливанием по данным: требуется найти некоторый способ увеличения числа распределений, доступных для конечных пользователей. К сожалению, мультиразделение – это всего лишь одно из многих возможных распределений, которые может понадобиться внедрить в компилятор HPF; еще пару распределений представляют обобщенное блочное и косвенное распределения, введенные в HPF 2.0. Имеется много других распределений, которые можно было бы использовать для достижения высокой производительности при использовании конкретных приложений на конкретных параллельных системах. Базовая система не может поддерживать все возможные полезные распределения. Из этого следует потребность в некотором механизме, позволяющем добавлять в систему распределения, определяемые пользователями. Если бы имелась возможность определения интерфейса распределений и оптимизаций компилятора в терминах этого интерфейса, то можно было бы достичь цели разделения структур данных и распределений данных. В результате можно было бы значительно увеличить гибкость языка. В настоящее время исследования в этой области проводятся в контексте языка программирования Chapel, разрабатываемого в проекте Cascade. В Chapel [17] не поддерживаются какие-либо встроенные распределения, но имеется интерфейс класса распределений, позволяющий явно специфицировать отображения, определять последовательные и параллельные итераторы и, при необходимости, контролировать представлений распределений и структур локальных данных.

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

Одной из причин успеха MPI являлось наличие достаточно качественной эталонной реализации, называемой MPICH. Аналогичная эталонная реализация компилятора HPF и HPF Library была бы существенной поддержкой языка HPF. Компилятор компании Portland Group близко подошел к тому, чтобы его можно было считать эталонной реализацией HPF, но не было соответствующей стандартизованной реализации библиотеки. Несколько лидеров из сообщества разработчиков компиляторов и библиотек HPF обсуждало возможность получения федеральной поддержки для обеспечения эталонной реализации HPF Library, но финансирование так и не было открыто. Это было особенно печально по той причине, что очень хорошая реализация большей части требуемых функциональных возможностей имелась в составе библиотеки CMSSL (Connection Machine Scientific Subroutine Library), входившей в систему поддержки выполнения CM Fortran компании Thinking Machines. Когда компания Thinking Machines вышла из бизнеса и была продана компании Sun Microsystems, можно было сэкономить на разработке требуемых функциональных средств, если бы имелась государственная поддержка, но и эта возможность была упущена.

Отдельный класс проблем связан со средствами настойки производительности для HPF. Как отмечалось выше, сотрудничество между разработчиками компиляторов и соответствующих инструментальных средств могло бы обеспечить возможность отображения информации о производительности в код программ на HPF: примерами являются использование системы Pablo совместно с компиляторами dHPF и Portland Group [2]. Трудность состояла в том, что у пользователей имелись лишь ограниченные возможности мелкоструктурного управления генерацией кода после обнаружения источника узких мест в производительности. По сути, эти возможности сводились к использованию директивы EXTRINSIC для перехода на уровень непосредственного применения MPI. В расширениях HPF/JA эта ситуация была немного улучшена за счет обеспечения более развитых средств управления локальностью. Однако совершенно ясно, что в языке требуются дополнительные средства, позволяющие при необходимости подменить стандартные действия компилятора. В противном случае на пользователей возлагается решение сложной обратной проблемы, когда в распределение или структуру цикла вносятся небольшие изменения в надежде на то, что это заставит компилятор сделать именно то, что от него в данном случае требуется.

В заключение авторы отмечают отсутствие терпения в сообществе пользователей. Действительно, High Performance Fortran был введен в производственный режим раньше времени, не достигнув должной зрелости, но если бы пользователи оказывали давление на разработчиков с целью совершенствования языка и его реализаций, а не просто переходили на использование MPI, можно было бы добиться того, чтобы обеспечивалась, по крайней мере, одна высокоуровневая программная модель для параллельного программирования. Как показывают работы в университете Rice и Японии, при использовании правильной технологии компиляции HPF может обеспечить высокую производительность, в особенности, при наличии средств, обеспечивающих контроль пользователей над производительностью. К сожалению, сообщество в Соединенных Штатах ждать не захотело. Федеральное правительство Соединенных Штатов могло бы помочь стимулировать терпение пользователей путем финансирования одного или нескольких фундаментальных прикладных проектов, направленных на использование новых инструментов, подобных HPF, а не просто добиваться как можно более быстрого выполнения приложений на параллельных платформах. Из-за этого отсутствия терпения и поддержки вторая волна разработчиков параллельных приложений не может получить пользу из опыта первой волны. Это является упущенной возможностью сообщества HPC.

8. Заключение

High Performance Fortran не смог достичь того уровня успеха, на который надеялись его создатели. Для этого имеется несколько причин: недостаточно зрелая технология компиляции, ведущая к плохой производительности; отсутствие гибких распределений данных; несогласованные реализации; отсутствие требуемых инструментальных средств, отсутствие терпения в сообществе пользователей. Тем не менее, HPF привнес ряд важных идей, которые будут использованы в следующем поколении высокопроизводительных компьютерных языков. К числу этих идей относятся однопотоковая модель выполнения с использованием глобального адресного пространства; интерперабельность с другими языковыми моделями; обширная библиотека примитивных операций для параллельных вычислений. Кроме того, в течение десятилетних исследований и разработок удалось преодолеть многие препятствия на пути эффективной реализации. Возможно, настало время для того, чтобы сообщество HPC еще раз попыталось воспользоваться новыми моделями программирования с распараллеливанием по данным, похожими на модель, поддерживаемую в HPF.

Литература

1. Jeanne C. Adams, Walter S. Brainard, Jeanne T. Martin, Brian T. Smith, and Jerrold L. Wagener. Fortran 95 Handbook. Complete ISO/ANSI Reference. Scientific and Engineering Computation Series. MIT Press, Cambridge, Massachusetts, 1997.
2. Vikram S. Adve, John Mellor-Crummey, Mark Anderson, Ken Kennedy, Jhy-Chun Wang, and Daniel A. Reed. An Integrated Compilation and Performance Analysis Environment for Data Parallel Programs. In Proceedings of Supercomputing '95, November 1995.
3. J. R. Allen and K. Kennedy. Automatic Translation of Fortran Programs to Vector Form. ACM Transactions on Programming Languages and Systems, 9(4):491–542, October 1987.
4. R. Allen and K. Kennedy. Optimizing Compilers for Modern Architectures. Morgan Kaufmann, San Francisco, California, 2002.
5. Alliant Computer Systems.
6. Jennifer M. Anderson and Monica S. Lam. Global Optimizations for Parallelism and Locality on Scalable Parallel Machines. In PLDI '93: Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, pages 112–125, New York, NY, USA, 1993. ACM Press.
7. F. Andre, J.-L. Pazat, and H. Thomas. PANDORE: A System to Manage Data Distribution. In International Conference on Supercomputing, pages 380–388, Amsterdam, The Netherlands, June 1990.
8. Applied Parallel Research, Sacramento, California. Forge High Performance Fortran xhpf User's Guide, Version 2.1, 1995.
9. G. H. Barnes, R. M. Brown, M. Kato, D. Kuck, D. Slotnick, and R. Stokes. The ILLIAC IV computer. IEEE Transactions on Computers, C-17:746–757, 1968.
10. Kenneth E. Batcher. The Multi-Dimensional Access Memory in STARAN. IEEE Transactions on Computers, C-26(2):174–177, February 1977.
11. S. Benkner, G. Lonsdale, and H.P. Zima. The HPF+ Project: Supporting HPF for Advanced Industrial Applications. In Proceedings EuroPar'99 Parallel Processing, volume 1685 of Lecture Notes in Computer Science. Springer–Verlag, 1999.
12. S. Benkner and H. Zima. Compiling High Performance Fortran for Distributed-Memory Architectures. Parallel Computing, 1999.
13. J. Bircsak, P. Craig, R. Crowell, Z. Cvetanovic, J. Harris, C.A. Nelson, and C. Ofner. Extending OpenMP for NUMA Machines. In Proceedings of Supercomputing 2000, November 2000.
14. F. Bodin, P. Beckman, D. Gannon, S. Yang, S. Kesavan, A. Malony, and B. Mohr. Implementing a Parallel C++ Runtime System for Scalable Parallel Systems. In Proceedings of Supercomputing '93, November 1993.
15. Z. Bozkus, L. Meadows, S. Nakamoto, V. Schuster, and M. Young. PGHPF—An Optimizing High Performance Fortran Compiler for Distributed Memory Machines. Scientific Programming, 6(1):29–40, 1997.
16. M. Burke and R. Cytron. Interprocedural Dependence Analysis and Parallelization. In Proceedings of the SIGPLAN '86 Symposium on Compiler Construction, Palo Alto, California, June 1986.
17. D. Callahan, Bradford L. Chamberlain, and Hans P. Zima. The Cascade High Productivity Language. In Ninth International Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS'04), pages 52–60, April 2004.
18. D. Callahan and K. Kennedy. Compiling Programs for Distributed–Memory Multiprocessors. Journal of Supercomputing, 2:151–169, October 1988.
19. Bradford L. Chamberlain. The Design and Implementation of a Region-Based Parallel Programming Language. PhD thesis, Department of Computer Science and Engineering, University of Washington, 2001.
20. Bradford L. Chamberlain, D. Callahan, and H. P. Zima. Parallel Programmability and the Chapel Language. The International Journal of High Performance Computing Applications, 2007. Special Issue on High Productivity Programming Languages and Models (in print).
21. B. Chapman, P. Mehrotra, and H. Zima. Programming in Vienna Fortran. Scientific Programming, 1(1):31–50, Fall 1992.
22. Philippe Charles, Christian Grothoff, Vijay Saraswat, Christopher Donawa, Allan Kielstra, Kemal Ebcioglu, Christoph von Praun, and Vivek Sarkar. X10: An Objectoriented Approach to Non-uniform Cluster Computing. In OOPSLA '05: Proceedings of the 20th annual ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications, pages 519–538, New York, NY, USA, 2005. ACM Press.
23. Siddhartha Chatterjee, John R. Gilbert, Robert Schreiber, and Shang-Hua Teng. Automatic array alignment in dataparallel programs. In POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 16–28, New York, NY, USA, 1993. ACM Press.
24. Daniel Chavarr´ıa-Miranda, Guohua Jin, and John Mellor-Crummey. Assessing the US Supercomputing Strategy: An Application Study Using IMPACT-3D. In Proceedings of the 19th International Parallel and Distributed Processing Symposium (IPDPS), Denver, CO, April 2005.
25. Daniel Chavarr´ıa-Miranda and John Mellor-Crummey. An Evaluation of Data-Parallel Compiler Support for Line-Sweep Applications. The Journal of Instruction-Level Parallelism, 5, February 2003. Special issue with selected papers from: The Eleventh International Conference on Parallel Architectures and Compilation Techniques, September 2002. Guest Editors: Erik Altman and Sally McKee.
26. A. Choudhary, G. Fox, S. Ranka, S. Hiranandani, K. Kennedy, C. Koelbel, and J. Saltz. Software Support for Irregular and Loosely Synchronous Problems. International Journal of Computing Systems in Engineering, 3(2):43–52, 1993. (also available as CRPC-TR92258).
27. Peter Christy. Software to Support Massively Parallel Computing on the MasPar MP-1. In Proceedings of the IEEE Compcon, 1990.
28. Stephanie Coleman and Kathryn S. McKinley. Tile Size Selection Using Cache Organization and Data Layout. In PLDI '95: Proceedings of the ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation, pages 279–290, New York, NY, USA, 1995. ACM Press.
29. K. D. Cooper, M. W. Hall, K. Kennedy, and L. Torczon. Interprocedural Analysis and Optimization. Communications in Pure and Applied Mathematics, 48:947–1003, 1995.
30. Cray history.
31. Cray-1 Computer System. Hardware Reference Manual 224004. Technical report, Cray Research, Inc., November 1977. Revision C.
32. David E. Culler, Jaswinder Pal Singh, and Anoop Gupta. Parallel Computer Architecture. A Hardware/Software Approach. Morgan Kaufman Publishers, San Francisco, California, 1999.
33. L. Dagum and R. Menon. OpenMP: An Industry-Standard API for Shared-Memory Programming. Computational Science and Engineering, 5(1):46–55, 1998.
34. F. Darema-Rogers, D. A. George, V. A. Norton, and G. F. Pfister. VM/EPEX – A VM Environment for Parallel Execution. Technical Report RC 11225(#49161), IBM T. J. & Watson Research Center, Yorktown Heights, New York, January 1985.
35. Luiz DeRose and David Padua. A MATLAB to Fortran 90 Translator and Its Effectiveness. In Proceedings of the 10^th International Conference on Supercomputing, May 1996.
36. R. L. Diaconescu and H.P. Zima. An Approach to Data Distributions in Chapel. The International Journal of High Performance Computing Applications, 2006. Special Issue on High Productivity Programming Languages and Models (in print).
37. M. Flynn. Some Computer Organisations and their Effectiveness. Trans. Computers, 21:948–960, 1972.
38. G. Fox, S. Hiranandani, K. Kennedy, C. Koelbel, U. Kremer, C.-W. Tseng, and M. Wu. The Fortran D Language Specification. Technical Report TR90–141, Department of Computer Science, December 1990.
39. Dennis Gannon, William Jalby, and Kyle Gallivan. Strategies for Cache and Local Memory Management by Global Program Transformation. J. Parallel Distrib. Comput., 7-19 5(5):587–616, 1988.
40. Michael Gerndt. Automatic Parallelization for Distributed-Memory Multiprocessing Systems. PhD thesis, University of Bonn, Germany, 1989.
41. Wolfgang K. Giloi. SUPRENUM: A Trendsetter in Modern Supercomputer Development. Parallel Computing, pages 283–296, 1988.
42. W. Gropp, S. Huss-Lederman, A. Lumsdaine, E. Lusk, B. Nitsberg, W. Saphir, and M. Snir. MPI – The Complete Reference: Volume 2, The MPI Extensions. Scientific and Engineering Computation Series. MIT Press, Cambridge, Massachusetts, September 1998.
43. M. Gupta, S. Midkiff, E. Schonberg, V. Seshadri, D. Shields, K. Wang, W. Ching, and T. Ngo. An HPF Compiler for the IBM SP2. In Proceedings of Supercomputing '95, San Diego, California, December 1995.
44. Manish Gupta. Automatic Data Partitioning on Distributed Memory Multicomputers. PhD thesis, University of Illinois at Urbana-Champaign, Champaign, IL, USA, 1992.
45. L. Hamel, P. Hatcher, and M. Quinn. An Optimizing C* Compiler for a Hypercube Multicomputer. In J. Saltz and P. Mehrotra, editors, Languages, Compilers, and Run–Time Environments for Distributed Memory Machines. North–Holland, Amsterdam, The Netherlands, 1992.
46. J. Harris, J. Bircsak, M. R. Bolduc, J. A. Diewald, I. Gale, N. Johnson, S. Lee, C. A. Nelson, and C. Offner. Compiling High Performance Fortran for Distributed–Memory Systems. Digital Technical Journal of Digital Equipment Corporation, 7(3):5–23, Fall 1995.
47. P. Hatcher, A. Lapadula, R. Jones, M. Quinn, and J. Anderson. A Production Quality C* Compiler for Hypercube Machines. In 3rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 73–82, April 1991.
48. John L. Hennessy and David A. Patterson. Computer Architecture. A Quantitative Approach. Morgan Kaufman Publishers, 1996. Second Edition.
49. High Performance Fortran Forum. High Performance Fortran Language Specification. Scientific Programming, 2(1–2):1–170, 1993. (also available as CRPC–TR92225).
50. High Performance Fortran Forum. High Performance Fortran Language Specification, version 1.0. Technical Report CRPC-TR92225, Rice University, Center for Research on Parallel Computation, Houston, Tex., 1993.
51. R. Hill. MIMDizer: A New Tool for Parallelization. Supercomputing Review, 3(4), April 1990.
52. W. Daniel Hillis. The Connection Machine. Series in Artificial Inteligence. MIT Press, Cambridge, MA, 1985.
53. S. Hiranandani, K. Kennedy, and C.-W. Tseng. Compiling Fortran D for MIMD Distributed – Memory Machines. Communications of the ACM, 35(8):66–80, August 1992.
54. S. Hiranandani, K. Kennedy, and C.-W. Tseng. Evaluation of Compiler Optimizations for Fortran D on MIMD Distributed–Memory Machines. In Proceedings of the 1992 ACM International Conference on Supercomputing, Washington, DC, July 1992.
55. P. Husbands, C. Isbell, and A. Edelman. MATLAB*P: A Tool for Interactive Supercomputing. In Proceedings of the 9th SIAM Conference on Parallel Processing. Scientific Computing, 1999.
56. ESA/390 Principles of Operation. Technical report, IBM Corporation. IBM Publication No. SA22-7201.
57. K. Ikudome, G. Fox, A. Kolawa, and J. Flower. An Automatic and Symbolic Parallelization System for Distributed Memory Parallel Computers. In Fifth Distributed-Memory Computing Conference, pages 1105–1114, Charleston, South Carolina, April 1990.
58. H. F. Jordan. The Force. In L. H. Jamieson, D. B. Gannon, and R. J. Douglass, editors, The Characteristics of Parallel Algorithms. MIT Press, 1987.
59. Kendall Square Systems.
60. Ken Kennedy and Uli Kremer. Automatic Data Layout for Distributed Memory Machines. ACM Transactions on Programming Languages and Systems (TOPLAS), 20(4):869–916, July 1998.
61. Jeremy Kepner and Nadya Travinin. Parallel Matlab: The next generation. In Proceedings of the 2003 Workshop on High Performance Embedded Computing (HPEC03), 2003.
62. KSR1 Principles of Operation, 1991. Waltham, MA.
63. D. Kuck, Y. Muraoka, and S. Chen. On the Number of Operations Simultaneously Executable in Fortran-like Programs and Their Resulting Speedup. IEEE Transactions on Computers, C-21(12):1293–1310, December 1972.
64. Monica D. Lam, Edward E. Rothberg, and Michael E.Wolf. The Cache Performance and Optimizations of Blocked Algorithms. In ASPLOS-IV: Proceedings of the Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 63–74, New York, NY, USA, 1991. ACM Press.
65. L. Lamport. The Parallel Execution of DO Loops. Communications of the ACM, 17(2):83–93, February 1974.
66. B. Leasure. Parallel Processing Model for High-Level Programming Languages. Technical report, American National Standard for Information Processing, April 1994.
67. J. Li and M. Chen. Compiling Communication-Efficient Programs for Massively Parallel Machines. IEEE Trans. Parallel Distrib. Syst., 2(3):361–376, 1991.
68. J. Li and M.Chen. Generating Explicit Communication from Shared-Memory Program References. In Proceedings of Supercomputing '90, pages 865–876, New York, NY, November 1990.
69. J. H. Merlin. Adapting Fortran 90 Array Programs for Distributed-Memory Architectures. In H.P. Zima, editor, First International ACPC Conference, pages 184–200. Lecture Notes in Computer Science 591, Springer Verlag, Salzburg, Austria, 1991.
70. Message Passing Interface Forum. MPI: A Message–Passing Interface Standard. International Journal of Supercomputer Applications and High Performance Computing, 8(3/4):165–414, 1994. (special issue on MPI, also available electronically via
71. Myrias Systems.
72. D. S. Nikolopoulos, T.S. Papatheodoru, C.D. Polychronopoulos, J. Labarta, and E. Ayguade. Is Data Distribution Necessary in OpenMP? In Proceedings of Supercomputing 2000, November 2000.
73. OpenMP Application Program Interface. Version 2.5. Technical report, OpenMP Architecture Review Board, May 2005.
74. Anita Osterhaug. Guide to Parallel Programming on Sequent Computer Systems. Prentice Hall, Englewood Cliffs, New Jersey, 1989.
75. D. Pase. MPP Fortran Programming Model. High Performance Fortran Forum, January 1991.
76. M. Quinn, A. Malishevsky, N. Seelam, and Y. Zhao. Preliminary Results from a Parallel MATLAB Compiler. In Proceedings of the International Parallel Processing Symposium, pages 81–87, April 1998.
77. A. P. Reeves and C.M. Chase. The Paragon Programming Paradigm and Distributed-Memory Multicomputers. In J. Saltz and P. Mehrotra, editors, Compilers and Runtime Software for Scalable Multiprocessors. Elsevier, Amsterdam, The Netherlands, 1991.
78. A. Rogers and K. Pingali. Process Decomposition Through Locality of Reference. In Proceedings of the SIGPLAN '89 Conference on Programming Language Design and Implementation, Portland, Oregon, June 1989.
79. John R. Rose and Guy L. Steele. C*: An Extended C Language for Data Parallel Programming. In Proceedings Second International Conference on Supercomputing, volume Vol.II,2-16, 1987. International Supercomputing Institute.
80. M. Rosing, R.W. Schnabel, and R.P. Weaver. Expressing Complex Parallel Algorithms in DINO. In Fourth Conference on Hypercubes, Concurrent Computers, and Applications, pages 553–560, 1989.
81. R. Ruehl and M. Annaratone. Parallelization of Fortran Code on Distributed-Memory Parallel Processors. In International Conference on Supercomputing, Amsterdam, The Netherlands, June 1990. ACM Press.
82. H. Sakagami, H. Murai, Y. Seo, and M. Yokokawa. 14.9 TFLOPS Three-dimensional Fluid Simulation for Fusion Science with HPF on the Earth Simulator. In SC2002, November 2002.
83. J. Saltz, K. Crowley, R. Mirchandaney, and H. Berryman. Run-time Scheduling and Execution of Loops on Messagepassing Machines. Journal of Parallel and Distributed Computing, 8(2):303–312, 1990.
84. Vivek Sarkar. Automatic Selection of High Order Transformations in the IBM XL Fortran Compilers. IBM Journal of Research and Development, 41(3), May 1997.
85. C. L. Seitz. The Cosmic Cube. Communications of the ACM, 28(1):22–33, January 1985.
86. M. Shimasaki and Hans P. Zima. Special Issue on the Earth Simulator, November 2004.
87. D. Slotnick, W. Brock, and R. MacReynolds. The SOLOMON computer. In Proceedings of the AFIPS Fall Joint Computer Conference, pages 87–107, 1962.
88. M. Snir, S. Otto, S. Huss-Lederman, D. Walker, and J. Dongarra. MPI – The Complete Reference: Volume 1, The MPI Core. MIT Press, Cambridge, Massachusetts, 2 edition, 1998.
89. Lawrence Snyder. A Programming Guide to ZPL. MIT Press, Scientific and Engineering Computation Series, March 1999.
90. Sun Microsystems, Inc., Burlington, Massachusetts. The Fortress Language Specification, Version 0.707, July 2005.
91. Thinking Machines Corporation, Cambridge, Massachusetts. CM Fortran Reference Manual, Version 1.0, February 1991.
92. Transputer: A Programmable Component that Gives Micros a New Name. Computer Design, 23:243–244, February 1984.
93. R. Triolet, F. Irigoin, and P. Feautrier. Direct Parallelization of CALL Statements. In Proceedings of the SIGPLAN '86 Symposium on Compiler Construction, Palo Alto, California, June 1986.
94. C.-W. Tseng. An Optimizing Fortran D Compiler for MIMD Distributed–Memory Machines. PhD thesis, Rice University, January 1993.
95. P. S. Tseng. A Systolic Array Programming Language. In Fifth Distributed-Memory Computing Conference, pages 1125–1130, Charleston, South Carolina, April 1990.
96. M. Ujaldon, E.L. Zapata, B. Chapman, and H. Zima. Vienna Fortran/HPF Extensions for Sparse and Irregular Problems and Their Compilation. IEEE Transactions on Parallel and Distributed Systems, 8(10):1068–1083, October 1997.
97. Vax computers.
98. Michael E. Wolf and Monica S. Lam. A Data Locality Optimizing Algorithm. In PLDI '91: Proceedings of the ACM SIGPLAN 1991 Conference on Programming Language Design and Implementation, pages 30–44, New York, NY, USA, 1991. ACM Press.
99. M. J. Wolfe. Optimizing Supercompilers for Supercomputers. MIT Press, Cambridge, Massachusetts, 1989.
100. H. Zima, H.-J. Bast, and M. Gerndt. SUPERB: A Tool For Semi–Automatic MIMD/SIMD Parallelization. Parallel Computing, 6:1–18, 1988.
101. H. Zima and B. Chapman. Compiling for Distributed–Memory Systems. Proceedings of the IEEE, 81(2):264–287, February 1993.
102. Hans P. Zima, P. Brezany, B. Chapman, P. Mehrotra, and A. Schwald. Vienna Fortran – A Language Specification. Internal Report 21, ICASE, NASA Langley Research Center, March 1992.

Оригинал: Ken Kennedy, Charles Koelbel, Hans Zima, The Rise and Fall of High Performance Fortran: An Historical Object Lesson, Proceedings of the third ACM SIGPLAN conference on History of programming languages 2007, San Diego, California, June 09 - 10, 2007
статья публиковалась на сайте citforum.ru в 2008 г.
Помещена в музей с разрешения автора 12 июня 2019