Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Конференция «Технологии управления данными 2018»
СУБД, платформы, инструменты, реальные проекты.
29 ноября 2018 г.
2008 г.

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

Кен Кеннеди, Чарльз Коулбел, Ганс Зима
Пересказ: Сергей Кузнецов
Оригинал: 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

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

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

Содержание

1. Исторический контекст
1.1. Параллельные вычислительные системы
1.2. Программная поддержка параллельного программирования
2. HPF и его предшественники
3. Язык HPF
4. Опыт использования языка
5. Процесс стандартизации HPF 2
6. Последствия и воздействия HPF
6.1. Последствия для языка Fortran и его вариантов
6.2. Языки HPCS
6.3. Параллельные скриптовые языки Fortran и C
7. Полученные уроки
8. Заключение

Литература

Аннотация

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, 56, 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-битные адреса (или адреса еще меньшей длины). Таким образом, в системе с разделяемой памятью можно было адресовать только 232 различных элементов памяти. С другой стороны, в системе с распределенной памятью такой объем памяти можно было адресовать на любом процессоре. Следовательно, распределенная память позволяла обеспечить решение проблем, для которых требовалась память гораздо большего объема.

Не удивительно, что преимущества распределенной памяти оборачивались сложностью программирования. Чтобы один процессор мог получить доступ к элементу памяти другого процессора, процессор, в локальной памяти которого хранился этот элемент данных, должен был послать его процессору, запрашивавшему данный элемент; чтобы использовать данные, нужно было их сначала получить. Посылку и получение данных нужно было тщательно синхронизовать, чтобы обеспечивать обмен правильными данными, поскольку сравнительно просто сопоставить операцию приема данных не соответствующей ей операции посылки данных. При использовании этого подхода, стандартизованного, в конечном счете, в виде 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 добиться успеха, свойственны и другим подходам.

Содержание Вперёд

Новости мира IT:

Архив новостей

Последние комментарии:

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 985 1945361
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2015 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...