Ни для кого не секрет, что скорость развития вычислительной техники сейчас стала совершенно космической. Около десяти лет назад IBM PC AT с i80286 тактовой частоты 12Мгц считалась верхом мечтаний для обычного программиста (не имеющего доступа к вычислительным центрам), а сейчас можно себе позволить держать дома машину с Pentium 233, которая через полгода устареет даже для нашей страны. Однако вычислительной мощности однопроцессорных ЭВМ есть физический предел и кроме этого, аппетиты пользовательских приложений и запросов сектора научно-технического прогресса не желают занимать последнее положение, нам всегда всего мало, так уж мы устроены, а если этому потворствовать, как это происходит в области IT, то угнаться за потребностями абсолютно нереально.

Но электроника дешевеет также стремительно, как и развивается и вот-вот появятся доступная даже для домашнего использования техника по архитектуре схожая с суперкомпьютерами.

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

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

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

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

Для записи параллельных программ конечно были созданы параллельные языки. Они могут быть совершенно новыми, как например OCCAM, а могут быть основаны на традиционных языках, так например, существуют параллельный C, параллельный Паскаль, Фортран и др. Достаточно полную информацию и документацию по параллельным языкам а также свободно распространяемые версии можно найти по адресу www.hensa.ac.uk/parallel/ или огромное число ссылок на computer.org/parascope/.

Для систем с распределенной памятью обычно при программировании программу разбивают на части, которые называют задачами и которые должны выполняться на разных процессорах, а чтобы задачи могли передавать и получать друг от друга данные, используется механизм называемый передачей сообщений. В данном случае сообщение это просто кусок области данных (переменная или чаще всего массив). Сообщения передаются с помощью нескольких функций, основные типы которых send(…) – послать сообщение и receive(…) – соответственно получить.

Практически каждая фирма, разрабатывающая суперкомпьютер, предлагала свой вариант параллельного расширения языка, что конечно не вызывало восхищения у программистов, но иначе не получалось эффективно использовать архитектурные особенности каждой суперЭВМ. Выход был найден в разработке стандарта, который устанавливал определенный вид и типы параметров функций передачи сообщений, в этом случае фирме-производителю требуется лишь написать библиотеки, удовлетворяющие определенному стандарту и параллельные программы могут быть свободно переносимы в разные вычислительные системы. Наиболее известные спецификации библиотек передачи сообщений это PVM и EXPRESS, а не так давно был разработан международный стандарт MPI. MPI и PVM получили широкое распространение и сейчас можно найти свободно распространяемые варианты этих библиотек для Linux и даже Win95 и NT (dsg.dei.uc.pt/w32mpi/ и dsg.dei.uc.pt/wpvm/).

Современные подходы к параллельному программированию.

Итак, с появлением высокопроизводительных ЭВМ с параллельной архитектурой, средства параллельного программирования появились сразу во всех традиционных последовательных языках. Стандартом MPI можно сказать был завершен этот этап развития параллельного программирования. Но, тем не менее, это не принесло удовлетворения программистам на суперкомпьютерах. Препятствие ко всеобщему благоденствию в “параллельном мире” оказалось тем же, что и для традиционного программирования

На заре своей эры языки программирования плодились сотнями. Но затем стало ясно, что тремя структурными for, while, if ограничиться не получится. Сенсационное “открытие”, что 80-90% времени разработки программы тратится на отладку, привело к необходимости разработать средства, существенно понижающие возможность ошибки в программе, уменьшающие время, необходимое для отладки, надо было создавать такие языки, которые сами побуждали бы писать правильные программы. Это привело к появлению Pascal, Ada, Modula2, вершиной явились объектно-ориентированные языки.

Тот же самый путь необходимо проделать и в параллельном программировании. Проблема отладки здесь встает с необычайной остротой. То, что программа выполняется параллельно, сообщает ей свойство вести себя гораздо более непредсказуемо, чем обычная последовательная программа. Если раньше можно было хотя и затратив уйму времени, но пройти все возможные пути в программе, при этом большую помощь оказывают традиционные средства отладки, предоставляющие возможность пошагового прохождения и точки останова, то в параллельной программе эта техника не работает. Неизвестно, будет ли оператор А выполняться раньше В при выполнении на разных процессорах, скорее всего, возможно и то и другое. Последовательную программу, в редких случаях, возможно протестировать на всех, или почти всех, входных данных, и быть уверенным в том, что программа отлажена, но теперь и эта возможность утеряна. Часто случается, что типичные ошибки, связанные с недетерминированностью параллельных программ никак не проявляют себя на небольших системах, но при запуске на массивно параллельных вычислителях с большим числом процессорных элементов дают загадочные сбои. Особенно этим страдают программы написанные с использованием механизма передачи сообщений, основным для массивно параллельных вычислителей. PVM можно рассматривать лишь как язык параллельного программирования низкого уровня, нечто вроде ассемблера. Программировать с помощью него все равно, что активно использовать оператор GOTO.

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

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

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

Скрытый параллелизм в Fortran90.

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

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

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

Например, можно извлечь квадратный корень из всех элементов массива A операцией A=SQRT(A).

А с массивами

можно записать такие выражения:

Интересно поглубже познакомиться с возможностями Fortran90 по оперированию с массивами. Например, можно выделять секции в массивах и оперировать с ними как с новыми массивами и т.п.

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

Самый простой пример, программа в стандарте Fortran77:

в Fortran90 записывается

Любителям красоты программирования можно предложить записать в векторном виде синтаксиса Fortran90 операцию матричного произведения.

HPF.

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

Первыми попытками создания средств описания параллелизма данных явились FortranD, разработанный в 1992г. в Техасском университете, и Fortran Vienna, созданный группой из Венского университета. С целью объединения усилий и унификации языковых средств в январе 1992г. образована группа HPF (High Performance Forum), которая разработала проект языка HPF (High Performance Fortran), являющегося параллельным расширением Fortran90.

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

1. HPF содержит директивы для описания способов разбиения данных. Директивы имеют вид комментария, который начинается с символов !HPF$.

Директива !HPF$ DISTRIBUTE специфицирует как элементы массива будут распределяться по процессорам. Важным свойством является характер распределения: он может быть блочный, циклический, блочно-циклический. Например, массив А размером 100 можно распределить на три процессора, “нарезав” блоками по 30,30 и 40 элементов, это оптимально при математических расчетах, затрагивающих сразу несколько соседних элементов на каждой операции (итерации цикла). С другой стороны, если необходимо сбалансировать нагрузку всех трех процессоров, т.е. чтобы два других не ждали третьего, элементы следует расположить циклически: А(1) на первый процессор, А(2) на второй, А(3) на третий, А(4) на первый, А(5) на второй и т.д. Это, конечно надуманный пример, можно нарезать массив блоками по 33 элемента, но в том случае, если объем вычислений в теле цикла неодинаков на каждой итерации, а, к примеру, нарастает, то одинаковой нагрузки на процессоры не получится при блочном разбиении. Возможен>также вариант блочно-циклического разбиения данных (малыми блоками в циклическом порядке).

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

Пример использования директив:

2. Добавления к синтаксису языка.

С помощью директивы INDEPENDENT можно указать компилятору, что итерации в следующем DO-цикле могут выполняться независимо, в любом порядке (нет зависимостей по данным). Атрибут PURE специфицирует процедуру не имеющую побочных эффектов подобно изменению значений глобальных переменных. Подобные процедуры могут быть безопасно использованы внутри участков параллелизированного кода. Также в HPF включены дополнительные функции, оперирующие с массивами (в добавление к стандарту Fortran90).

3. Расширенная технология компиляции.

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

Основываясь на идее параллелизма данных HPF модель предполагает следующие требования.

1. Масштабируемость параллельной архитектуры.

Компилятор должен быть способен генерировать программу для архитектур с разным количеством процессоров. Это позволяет вести отладку на небольших системах и безболезненно переносить программу на массивно параллельные архитектуры.

2. Единственность управляющей цепочки программы.

Все процессоры, выполняющие HPF программу, работают по одинаковому алгоритму (пути программы). Когда встречаются параллелизированные действия, процессоры также выполняют одни и те же операции, но над различными секциями данных, при этом синхронизация не жесткая, а так называемая “свободная” (loose sinchronisation). Подобная модель называется SPMD (Single Program Multiple Data), и ее следует отличать от жестко потактовой синхронизации в параллельных машинах старых типов модели SIMD (Single Instruction Multiple Data).

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

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

Без человека не так просто обойтись.

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

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

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

как мы получаем возможность независимо выполнять итерации внутреннего цикла.

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

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

Практически каждая мощная многопроцессорная система сейчас имеет специализированное программное обеспечение для разработки эффективных параллельных программ. Например в T3E – массивно параллельному комплексу с несколькими тысячами процессоров и пиковой производительностью 2 500 000 000 000 операций с плавающей точкой в секунду бывшей фирмы Cray Research (сейчас куплена SGI)– программисту предоставляется широкий выбор средств анализа программы. Специальные утилиты фирмы Silicon Graphics собирают статистику при выполнении программы и дают информацию о том, сколько раз вызывалась та или иная процедура и каково количество времени, занимаемое ею при выполнении. Определяется время простоя процессоров при выполнении программы, место в программе, вызвавшее простой и причину. Это позволяет выделить в программе такие места, на которые ложится основная расчетная нагрузка и обратить особенное внимание на их оптимизацию. Мощный пакет визуального анализа параллельных свойств программ позволяет программисту производить нужные трансформации текста программы. В частности показывается какие циклы были распараллелены, какие нет и сообщает о причине неудачи.

6. Автоматическое распараллеливание - решение всех проблем?

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

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

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

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

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

С учетом вышесказанного, работа автоматического транслятора делится как минимум на две части.

Первая – определить какие участки программы можно выполнить параллельно (преимущественно циклы), разбить программу на как можно большее число участков и определить какие данные и какого размера нужно передавать между этими участками, если они будут выполняться на разных процессорах, определить “вес” этих участков, то есть сколько тактов процессора необходимо для их выполнения. Затем – вторая часть. Надо оптимальным образом разместить полученные участки программы на процессорах с учетом их веса и используемых данных, чтобы минимизировать количество пересылок.

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

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

Хитрый программист на старой доброй однопроцессорной машине знает, что операция умножения выполняется раз в десять медленнее сложения и “оптимизирует” программу

но при этом придет в ужас программист на параллельной ЭВМ, потому что теперь итерации внешнего цикла зависимы, на каждой итерации вычисляется переменная M и витки цикла нужно теперь выполнять строго один за другим. Такую “непараллельность” должен отловить компилятор.

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

В проекте Parafrase2 университета штата Иллинойс (США), разрабатывается компилятор, который преобразовывает исходный код последовательной программы к виду, который может распараллелить простой компилятор. Для анализа арифметических выражений активно используются теория чисел, общая алгебра и другие области высшей математики. А их коллеги, разработавшие параллелизирующий компилятор Polaris поступили более оригинально, они взяли общеизвестный пакет программ Perfect Benchmarks, специально разработанный для тестирования производительности компиляторов на суперЭВМ, и вручную распараллелили его, выделив сложные участки программ они определили какие методы автоматического анализа программ распараллеливания нужно применить к ним и реализовали их, подучив компилятор, способный распараллелить большинство сложных мест в математических пакетах численного анализа.