Прошло время, когда создатели суперкомпьютеров стремились обеспечить максимальную производительность любой ценой. Специальные процессоры, дорогостоящая сверхбыстрая память, нестандартное периферийное оборудование - все это обходилось заказчикам в круглую сумму. Приобретали суперкомпьютеры либо предприятия ВПК, либо крупные университеты. И те и другие делали это, как правило, за государственный счет. Окончание "холодной войны" и последовавшее за ним сокращение ассигнований на военные и околовоенные нужды нанесли серьезный удар по производителям суперкомпьютеров. Большинство из них были поглощены изготовителями менее производительной, но более доступной и ходовой вычислительной техники. Впрочем, у этих слияний были и технологические предпосылки - быстродействие серийно выпускаемых микропроцессоров постоянно росло, и производители суперкомпьютеров быстро переориентировались на них, что позволило существенно сократить общую стоимость разработки. Fujitsu AP3000 Scalar Parallel Server использует процессоры UltraSPARC, Cray/SGI - DEC Alpha 21064 и MIPS, Convex/HP - PA-RISC. Основной упор стал делаться на увеличение числа процессоров и повышение степени параллелизма программ.
Всем известно, что сегодня существуют две основные архитектуры параллельных компьютеров: симметричные мультипроцессорные системы с общей памятью (SMP) и мультипроцессорные системы с распределенной памятью (MPP). Основное преимущество SMP - относительная простота программирования. В ситуации, когда все процессоры имеют одинаково быстрый доступ к общей памяти, вопрос о том, какой из процессоров какие вычисления будет выполнять, не столь принципиален, и значительная часть вычислительных алгоритмов, разработанных для последовательных компьютеров, может быть ускорена с помощью распараллеливающих и векторизирующих трансляторов. SMP-компьютеры - это наиболее распространенные сейчас параллельные вычислители, а 2-, 4-х процессорные ПК на основе Pentium и Pentium Pro стали уже массовым товаром. Однако общее число процессоров в SMP-системах, как правило, не превышает 16, а их дальнейшее увеличение не дает выигрыша из-за конфликтов при обращении к памяти. Применение технологий типа UPA, основанной на коммутации пакетов вместо общей шины (в семействе Ultra Sun) и локальной кэш-памяти большого объема, способно частично решить проблему, подняв число процессоров до 32.
Альтернатива SMP - архитектура MPP. Каждый процессор имеет доступ лишь к своей локальной памяти, а если программе нужно узнать значение переменной, расположенной в памяти другого процессора, то задействуется механизм передачи сообщений. Процессор, в памяти которого находятся нужные данные, посылает сообщение тому процессору, которому они требуются, а последний принимает его. Этот подход позволяет создавать компьютеры, включающие в себя тысячи процессоров. На нем основаны все машины, имеющие производительность в сотни миллиардов операций в секунду.
Но эта архитектура имеет ряд существенных недостатков. Во-первых, требуется быстродействующее коммуникационное оборудование, обеспечивающее среду передачи сообщений. Во-вторых, при создании программ необходимо учитывать топологию системы и специальным образом распределять данные между процессорами, чтобы минимизировать число пересылок и объем пересылаемых данных. Последнее обстоятельство и мешает широкому внедрению подобных архитектур. Число программистов, способных написать достаточно крупную программу, пользуясь примитивами передачи сообщений, чрезвычайно мало - даже программирование решения системы линейных уравнений требует недель напряженного труда. К тому же необходимо не только отладить программу, но и настроить ее таким образом, чтобы эффект от распараллеливания был бы достаточно весомым. Из-за того, что MPP-системы включают различное число процессоров, объединенных коммуникационными подсистемами различной топологии и пропускной способности, поддерживающими разные наборы примитивов, программы, стремящиеся максимально полно использовать возможности компьютера, оказываются жестко привязанными к его архитектуре. В итоге число пакетов программ, разработанных для каждой из MPP-систем, весьма ограниченно. Это сдерживает распространение таких систем и делает их дороже, что, в свою очередь, не способствует росту числа приложений. В результате возникает порочный круг.
Как же разорвать его?
Создатели некоторых компьютерных архитектур, в частности разработчики Cray T3D и T3E, пошли по пути создания виртуальной общей памяти. Каждый процессор по-прежнему может обращаться напрямую только к своей локальной памяти, однако все узлы используют единое адресное пространство. Если программа обратилась по адресу, принадлежащему локальной памяти другого процессора, генерируется аппаратное прерывание по особому случаю адресации, и операционная система выполняет пересылку страницы с одного узла на другой. В результате можно ускорять программы, первоначально разработанные для последовательных систем, транслируя их при помощи распараллеливающего компилятора. Благодаря чрезвычайно высокому быстродействию коммуникационной системы (пиковая скорость передачи данных между двумя узлами составляет 300 Мбайт/с в каждом направлении) этот подход в целом оправдывает себя. Впрочем, когда на одну страницу виртуальной памяти попадает несколько "популярных" переменных, считываемых и модифицируемых множеством процессоров, возникает эффект пинг-понга: страница непрерывно мигрирует с узла на узел и производительность системы падает.
Эта архитектура позволила существенно снизить стоимость программирования, но сверхбыстрая коммуникационная система - пока слишком дорогое решение, чтобы тиражировать его.
Сети дешевле
Другой резерв снижения стоимости MPP-компьютеров - отказаться от нестандартного коммуникационного оборудования, заменив его обычным сетевым. Начиная с 1992 года по скорости роста производительности сетевое оборудование обгоняет процессоры. Для многих организаций перспектива использования сетей рабочих станций и ПК в качестве суперкомпьютеров весьма заманчива. Основные достоинства сетей - возможность постепенного расширения и модернизации, а также режим эксплуатации сети днем для обычных нужд разработки и проектирования, а ночью для расчетов. Сети не могут соревноваться по скорости вычисления с суперкомпьютерами-рекордсменами, но они на один-два порядка дешевле, их можно использовать там, где объемы расчетов велики, а суперкомпьютеры экономически не оправданы. Уже имеется опыт применения сетей ПК и рабочих станций для решений задач рендеринга.
Такие сетевые технологии будут способствовать использованию сетей в качестве параллельных вычислителей. В первую очередь это Fast Ethernet и Gigabit Ethernet. Далее идут технологии коммутации. И, наконец, новые сетевые протоколы, поддерживающие широковещание и мультикастинг. До последнего времени основным препятствием для применения сетей в качестве параллельных вычислителей было отсутствие инструментария. Упомянутые приложения базировались на интерфейсе сокетов - слишком низкоуровневом для большинства применений. Написать и отладить программы, основанные непосредственно на интерфейсе сокетов, не легче, чем написать вручную и отладить программу в машинных кодах.
Параллельные программы - главный тормоз
Главным препятствием к внедрению практически всех параллельных архитектур является отсутствие параллельных программ. У унаследованных от последовательного мира программ имеется недостаток - большой объем кода, принципиально не допускающий параллельного исполнения. Его нельзя преодолеть за счет усовершенствования техники компиляции. Так, если программа половину времени занимается действиями, которые требуется совершать строго последовательно, то параллельное выполнение оставшейся половины в предельном случае даст лишь двукратное ускорение. В результате, хотим мы этого или нет, последовательные вычислительные алгоритмы придется заменять параллельными.
Необходимость переработки существующих алгоритмов при переносе их на параллельные системы - момент принципиальный. Специалисты по численным методам наработали большой багаж программ на Fortran и не хотели бы переходить на другие языки (скажем, Cи или C++), чтобы не переписывать свои программы заново. Увы, при переходе на параллельные компьютеры или сети переделывать их придется, и процесс этот во много раз сложнее, чем переписывание программы с одного последовательного языка на другой.
MPI
Практически на всех параллельных системах имелись свои собственные библиотеки передачи сообщений. В простейшем случае они предусматривали передачу и прием отдельных пакетов между соседними процессорами. Более сложные поддерживали передачу сообщений произвольной длины, маршрутизацию сообщений и аппарат тегов, который позволяет принимающей стороне самой решать, в какой последовательности обрабатывать поступающие сообщения. Некоторые библиотеки допускали динамическое порождение и уничтожение процессов.
За последние годы в деле создания ПО для систем с распределенной памятью наметился серьезный прогресс. Самым крупным достижением была стандартизация интерфейса передачи сообщений MPI (message passing interface). Набор функций этого интерфейса вобрал в себя лучшие черты своих предшественников p4 и PVM. Во-первых, MPI поддерживает несколько режимов передачи данных, важнейшие из которых: синхронная передача, не требующая выделения промежуточных буферов для данных и обеспечивающая надежную передачу данных сколь угодно большого размера, и асинхронная передача, при которой посылающий сообщение процесс не ждет начала приема, что позволяет эффективно передавать короткие сообщения. Во-вторых, MPI позволяет передавать данные не только от одного процесса к другому, но и поддерживает коллективные операции: широковещательную передачу (broadcasting), разборку-сборку (scatter и gather), операции редукции. В-третьих, MPI предусматривает гетерогенные вычисления. Вычислительная система может включать разные процессоры, в том числе имеющие различные наборы команд и разное представление данных. Если у вас имеется суперкомпьютер, то это кажется излишним, но для организаций, эксплуатирующих сети рабочих станций с различными процессорами и версиями Unix, - это находка.
Синтаксис MPI облегчает создание приложений в модели SPMD (single program multiple data) - одна программа работает в разных процессах со своими данными. Одна и та же функция вызывается на узле-источнике и узлах-приемниках, а тип выполняемой операции (передача или прием) определяется с помощью параметра. Такой синтаксис вызовов делает SPMD-программы существенно компактнее, хотя и труднее для понимания.
Основное отличие стандарта MPI от его предшественников - понятие коммуникатора. Все операции синхронизации и передачи сообщений локализуются внутри коммуникатора. С коммуникатором связывается группа процессов. В частности, все коллективные операции вызываются одновременно на всех процессах, входящих в эту группу. Поскольку взаимодействие между процессами инкапсулируется внутри коммуникатора, на базе MPI можно создавать библиотеки параллельных программ.
Поддержка модульного программирования в сочетании с независимостью от аппаратуры дала мощный импульс к созданию библиотек. Одна из самых интересных разработок - пакет линейной алгебры ScaLAPACK, разработанный группой Дж. Донгарра.
Реализации MPI
Библиотеки MPI реализованы практически на всех современных суперкомпьютерах.
Основное достоинство пакета LAM - богатые отладочные возможности. Трассировка обращений к MPI и анализ состояния параллельной программы после аварийного завершения - серьезный аргумент в пользу этой библиотеки, особенно учитывая серьезность проблем отладки. С другой стороны, пакет MPICH более мобилен - имеются инструкции, следуя которым можно перенести MPI на новую платформу. Для этого необходимо написать лишь несколько драйверов нижнего уровня. Установка библиотеки MPICH проходит труднее, чем установка LAM MPI, поскольку приходится задавать гораздо большее число параметров, причем назначение некоторых из них известно только разработчикам. К тому же, по нашим наблюдениям, MPICH несколько эффективнее передает сообщения, однако отлаживать программы в среде MPICH труднее.
Самые последние экспериментальные версии MPICH поддерживают мультипротокольную передачу сообщений. Часто на одном узле (особенно если он включает несколько процессоров, имеющих доступ к общей памяти) функционирует несколько процессов. Однако однопротокольные библиотеки не учитывают это обстоятельство, и для передачи сообщений как вовне, так и внутри узла используют стек TCP/IP. Из-за этого передача сообщения внутри узла сопровождается бесчисленными вызовами функций стека и многократным копированием информации в локальной памяти узла. Мультипротокольная реализация позволяет в рамках узла передавать данные через общую память, что намного быстрее.
На базе MPICH в университете Коимбра (Португалия) разработали библиотеку MPI для Windows 95 (http://pandora.uc.pt:80/w32mpi), которая особенно интересна для преподавателей и студентов, поскольку при отладке достаточно иметь обычный ПК, а запуск параллельных приложений в сети позволяет получить реальный выигрыш в производительности.
MPICH дает возможность использовать механизм сокетов и протокол TCP/IP для реализации драйверов нижнего уровня. При этом библиотека берет на себя все преобразования типов, работу с внутренними очередями и организацию коллективных операций. Увы! Не обошлось без ложки дегтя. Несмотря на то что протокол сетевого уровня поддерживает передачу сообщений "один - многие", на транспортном уровне такая поддержка отсутствует. В результате для реализации широковещательной рассылки существующие общедоступные реализации MPI используют цикл одиночных посылок. Если коммуникатор включает в себя более двух процессов, время выполнения широковещательных операций возрастает пропорционально числу процессов.
Чтобы исправить этот недостаток, следует воспользоваться одним из экспериментальных протоколов транспортного уровня, поддерживающих передачу данных от одного узла группе. Зачастую дело тормозит отсутствие стандарта. Здесь могут помочь протоколы MTP-2 (Multicast Transport Protocol), RMP (Reliable Multicast Transport), RMTP (Reliable Multicast Transport Protocol) и несколько других, детальный обзор которых можно найти на узле http://www.tacsnets.com/mist/doc. Отметим, что в идеале передача широковещательного сообщения будет занимать столько же времени, сколько и пересылка сообщения между двумя процессами.
Возможен и другой способ оптимизации коллективных операций. Если используется сеть с коммутатором, когда по сети одновременно без коллизий можно передавать несколько пакетов, то нетрудно реализовать передачу широковещательного сообщения по дереву - параллельно несколько пар процессов будут обмениваться информацией. В этом случае время передачи широковещательного сообщения будет пропорционально логарифму числа процессов в коммуникаторе, по которому идет передача.
Практический опыт показывает, что идеально распараллеливаемые задачи, такие как распределенный рендеринг или параллельное умножение матриц, можно решать практически на любых сетях, и добавление даже относительно слабых вычислительных узлов дает выигрыш.
Другие задачи, в частности решение систем линейных уравнений, более требовательны к коммуникационному оборудованию и качеству реализации передачи сообщений. Именно поэтому тесты для оценки реального быстродействия параллельных вычислительных систем базируются на параллельных аналогах известного пакета Linpack. Так, система линейных уравнений размером 800х800 решается на четырех компьютерах Sun SPARCstation 5, объединенных сетью Ethernet 10 Мбит/c, быстрее, чем на трех; на пяти - приблизительно за то же время, что и на четырех, а добавление шестого компьютера однозначно ухудшает производительность вычислительной системы. Если вместо Fast Ethernet 10 Мбит/c использовать Fast Ethernet 100 Мбит/с, что лишь незначительно увеличивает общую стоимость системы, время, затрачиваемое на коммуникацию, уменьшается почти в 10 раз, а для решения данной задачи можно будет эффективно применять уже десятки рабочих станций.
Средства программирования высокого уровня
Несмотря на то что MPI представляет собой значительный шаг вперед по сравнению с предшествующим поколением библиотек передачи сообщений, ожидать появления большого числа прикладных пакетов, построенных непосредственно над MPI, не приходится, поскольку программировать на MPI достаточно сложно. Причину этого следует искать не в изъянах стандарта, а в самой парадигме передачи сообщений. Его можно рассматривать как уровень ассемблера для параллельных программ. Неопытный программист может как угодно далеко в тексте программы разнести вызовы функций посылки и получения сообщения и потом долго искать ошибку, связанную с неверным тегом или размером сообщения. Типичные ошибки, связанные с недетерминированностью программ, основанных на парадигме передачи сообщений, часто никак не проявляются на относительно небольших системах, на которых идет отладка, но приводят к загадочным сбоям при запуске на системах, включающих множество узлов. В итоге основные усилия тратятся не на поиск наиболее быстрого алгоритма, а на отыскание элементарных ошибок.
Часто в сетях отдельные компьютеры неравноценны, и имеет смысл нагружать их по-разному, однако даже простейшая программа, учитывающая балансировку нагрузки, - если кодировать ее, используя лишь средства MPI, - становится необъятной, и отладка ее мало кому окажется по силам. Так, матрицы в пакете SсаLAPACK, независимо от решаемой задачи и мощностей вычислительных элементов, всегда распределяются по процессорам равномерно. В результате, при наличии хотя бы одного слабого компьютера в сети, вычисления затягиваются - все ждут отстающего. Динамическая балансировка нагрузки, практически бесплатно получающаяся на SMP-компьютерах, в распределенных системах чрезвычайно трудна, и даже простое распределение данных в соответствии с мощностями узлов и последующие пересылки кодируются весьма непросто.
Выходом из создавшегося положения стали языки программирования, основанные на параллелизме данных. Первый из них, Fortran-D, появился в 1992 г. На смену ему пришел High Performance Fortran (HPF), представляющий собой расширение языка Fortran 90 и требующий от пользователя лишь указать распределение данных по процессорам. В остальном программа имеет последовательный вид (это, впрочем, не означает, что, придумывая алгоритм, не следует задумываться о присущем ему параллелизме). Транслятор самостоятельно распределяет вычисления по процессорам, выбирая в качестве узла, на котором следует производить вычисления, тот процессор, на котором будет использован результат вычисления выражения. При необходимости транслятор генерирует обращения к библиотеке передачи сообщений, например MPI. От компилятора HPF требуется тщательный анализ программы. Пользователь практически не имеет рычагов управления количеством пересылок, а поскольку инициализация каждой пересылки, независимо от объема передаваемой информации, - это десятки тысяч машинных тактов, качество получаемой программы от него зависит слабо. Язык HPF - вызов специалистам по оптимизации кода.
В языке программирования mpC (http://www.ispras.ru) - расширении ANSI Cи - принят компромиссный подход. Здесь пользователь распределяет не только данные, но и вычисления. Переменные и массивы распределяются по виртуальным сетям (networks) и подсетям, при этом в описаниях сетей указываются относительные мощности узлов и скорости связей между ними. В процессе выполнения mpC-программы система поддержки языка стремится максимально эффективно отобразить виртуальные сети на группы процессоров. В результате пользователь получает возможность равномерно нагружать узлы. Этот подход позволяет эффективно использовать гетерогенные сети и решать нерегулярные задачи, отличающиеся тем, что объем вычислений, производимых на каждом узле, выясняется динамически в процессе решения задачи. Этот язык позволяет избежать трудностей отладки, характерных для библиотек передачи сообщений. В то же время mpC достаточно прозрачный язык, и применяющий его программист сохраняет контроль за числом операций пересылок и объемами передаваемых данных. Относительная (по сравнению с MPI) простота программирования позволяет создавать программы и библиотеки функций, настраивающиеся на особенности конкретной вычислительной системы со своим числом процессоров и скоростями связей между ними. Такие программы не только мобильны, но и сохраняют свою эффективность при переносе с одной вычислительной системы на другую.
Попытка прогноза
Использование сетей компьютеров для вычислительных задач - уже сегодня дело вполне реальное. В этом направлении ведутся научные разработки и сделан ряд пилотных проектов. В качестве коммуникационной платформы сейчас наиболее экономически оправдано применение коммутируемых сетей Fast Ethernet. При этом себестоимость системы производительностью 1,5-6 операций с вещественными числами в секунду на задачах линейной алгебры будет ниже 100 тыс. долл. Через пару лет в качестве коммуникационной платформы можно будет использовать Gigabit Ethernet или ATM, обеспечивающие на порядок более высокие скорости передачи данных. В течение одного-двух лет должны появиться общепризнанные широковещательные протоколы транспортного уровня и основанные на них реализации MPI. На уровне прикладных программ MPI использоваться не будет. На нем станут базироваться лишь некоторые библиотеки и системы поддержки языков, основанные на параллелизме данных.
Основные достоинства MPI
Имеются также три свободно распространяемые библиотеки MPI:
LAM MPI (http://www.osc.edu);
MPICH (http://www.msc.anl.gov/mpi/mpich);
CHIMP (ftp://ftp.epcc.ed.oc.uk/pub/chimp),
функционирующие на Unix-машинах и сетях рабочих станций.
