Под законом Амдала

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

Суперкомпьютеры воплощают идею параллельной обработки данных, существующую в двух ипостасях: конвейерности и собственно параллельности. Обе интуитивно понятны, поэтому дам лишь небольшие пояснения.

Параллельная обработка. Если некое устройство выполняет одну операцию за единицу времени, то тысячу операций оно выполнит за тысячу единиц. Если предположить, что есть пять таких же независимых устройств, способных работать одновременно, то тысячу операций система из пяти устройств может выполнить уже за двести единиц времени. Аналогично, системе из N устройств на ту же работу понадобится 1000/N единиц времени. Однако это идеальный случай, от которого реальность бывает весьма далека. Простой пример. Один землекоп за один час может выкопать яму объемом один кубометр. Два землекопа, работая вместе, выкопают такую же яму за полчаса. А шестьдесят землекопов? Ясно, что они будут просто мешать друг другу и быстрее процесс не пойдет.

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

Идея конвейерной обработки заключается в разбиении процесса выполнения общей операции на отдельные этапы - их называют микрооперациями или ступенями. Причем каждая микрооперация, выполнив свою работу, передает результат следующей, одновременно принимая новую порцию входных данных. Получаем очевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных во времени операций. Предположим, что в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени. Тогда одно неделимое последовательное устройство обработает сто пар аргументов за пятьсот единиц времени. Если же каждую микрооперацию выделить в отдельный этап конвейерного устройства, то на пятой единице времени на разной стадии обработки будут находиться первые пять пар аргументов, первый результат будет получен через пять единиц времени, каждый следующий - через одну единицу после предыдущего, а весь набор из ста пар будет обработан за 5+99=104 единицы времени - ускорение по сравнению с последовательным устройством почти в пять раз (по числу ступеней конвейера).

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

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

Используя параллельную систему с p вычислительными устройствами, мы, разумеется, ожидаем получить ускорение выполнения программы в p раз по сравнению с последовательным вариантом. Но действительность почти всегда оказывается далека от идеала (вспомните про шестьдесят землекопов). Вот как это описывается с формальной точки зрения.

Предположим, что мы определили структуру информационных зависимостей программы (что в общем случае - очень непростая задача), и доля операций, которые нужно выполнять последовательно, равна f (при этом под долей понимается не статическое число строк кода, а время выполнения последовательной программы). Крайние случаи в значениях f соответствуют полностью параллельным (f = 0) и полностью последовательным (f = 1) программам. Тогда для того, чтобы оценить, какое ускорение S может быть получено на компьютере из p процессоров при данном значении f, можно воспользоваться законом Амдала:

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

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

Таким образом, заставить параллельную вычислительную систему или супер-ЭВМ работать с максимальной эффективностью на конкретной программе - задача не из простых, поскольку необходимо тщательно согласовывать структуру программ и алгоритмов с архитектурой параллельных вычислительных систем.

Сегодня параллелизмом в архитектуре компьютеров уже никого не удивишь. Современные микропроцессоры, будь то Pentium III или PA-8700, MIPS R14000, Е2К или Power3, используют тот или иной вид параллельной обработки. В ядре Pentium 4 на разных стадиях выполнения может одновременно находиться до 126 микроопераций (на Pentium 4 вычислительные программы, специально оптимизированные для этого процессора, работают примерно на 50% быстрее неоптимизированных. Самый наглядный пример - кодер DivX 4.12. - Прим. ред.). Идеи параллелизма появились давно. Изначально они внедрялись в самых передовых, а потому единичных компьютерах своего времени. Затем, после отработки технологии и удешевления производства, они спускались в компьютеры среднего класса, и, наконец, сегодня все это в полном объеме воплощается в рабочих станциях и персональных компьютерах.

Так, разрядно-параллельная память и разрядно-параллельная арифметика впервые появились в компьютерах IBM 701 (1953 год) и IBM 704 (1955), независимые процессоры ввода/вывода - в IBM 709 (1958), опережающий просмотр вперед и расслоение памяти - в IBM Stretch (1961), конвейер команд - в Atlas (1963), независимые функциональные устройства - в CDC 6600 (1964), независимые конвейерные функциональные устройства - в CDC 7600 (1969), матричные процессоры - в ILLIAC IV (1974), векторно-конвейерные процессоры - в Cray 1 (1976).

По каким же направлениям идет развитие высокопроизводительной вычислительной техники в настоящее время? Основных направлений четыре.

1. Векторно-конвейерные компьютеры. Конвейерные функциональные устройства и набор векторных команд - две главные особенности таких машин. В отличие от традиционного подхода векторные команды оперируют целыми массивами независимых данных, что позволяет эффективно загружать доступные конвейеры, то есть команда вида A=B+C может означать сложение двух массивов, а не двух чисел. Характерный представитель этой группы - семейство векторно-конвейерных компьютеров Cray, куда входят, например, Cray EL, Cray J90 и Cray T90.

2. Параллельные компьютеры с общей памятью. Оперативная память таких компьютеров разделяется несколькими одинаковыми процессорами, благодаря чему снимаются проблемы предыдущего класса, но добавляются новые: число процессоров, имеющих доступ к общей памяти, по чисто техническим причинам нельзя сделать большим. В эту группу входят многие современные многопроцессорные SMP-компьютеры или, например, отдельные узлы компьютеров HP Exemplar и Sun StarFire.

3. Массивно-параллельные компьютеры с распределенной памятью. Идея построения компьютеров этого класса тривиальна: возьмем серийные микропроцессоры, снабдим каждый своей локальной памятью, соединим посредством некоторой коммуникационной среды - вот и все. Достоинств у такой архитектуры масса: если нужна высокая производительность - можно добавить еще процессоров; если ограничены финансы или заранее известна потребная вычислительная мощность - легко подобрать оптимальную конфигурацию и т. п. Однако есть и серьезный минус, сводящий многие плюсы на нет. Дело в том, что межпроцессорное взаимодействие в компьютерах этого класса идет намного медленнее локальной обработки данных самими процессорами. Именно поэтому написать эффективную программу для таких компьютеров очень сложно, а для некоторых алгоритмов иногда просто невозможно. К этому классу можно отнести компьютеры Intel Paragon, IBM SP1, Parsytec, в какой-то степени IBM SP2 и Cray T3D/T3E (причем острота вышеупомянутого недостатка в них значительно ослаблена), а также компьютерные сети, которые все чаще рассматривают как дешевую альтернативу крайне дорогим суперкомпьютерам.

4. Последнее направление, строго говоря, представляет собой комбинации трех предыдущих. Из нескольких процессоров (традиционных или векторно-конвейерных) и общей для них памяти сформируем вычислительный узел. Если полученной вычислительной мощности недостаточно - объединим несколько узлов высокоскоростными каналами. Подобную архитектуру называют кластерной, и по такому принципу построены Cray SV1, HP Exemplar, Sun StarFire, NEC SX-5, последние модели IBM SP2 и др.

Поскольку кластерное решение позволяет достичь наилучшего соотношения цены и производительности, именно оно является в настоящее время наиболее перспективным для конструирования компьютеров с рекордными показателями производительности. Не зря самый мощный российский суперкомпьютер, установленный в Межведомственном суперкомпьютерном центре (768 процессоров Alpha 21264 в узлах, связанных между собой коммуникационной сетью Myrinet), создан по кластерной технологии, а в последнюю, 18-ю редакцию списка пятисот самых мощных компьютеров мира (ноябрь 2001 года, parallel.ru/computers/top500.list18.html) вошли уже 43 кластерные системы.

В статье затронута лишь небольшая часть вопросов, касающихся высокопроизводительных вычислений. Дополнительную информацию можно найти в Информационно-аналитическом Центре по параллельным вычислениям (parallel.ru). Там же можно получить и консультацию ведущих российских специалистов в этой области.