Архивы: по дате | по разделам | по авторам

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

Архив
автор : Александр Антонов   11.02.2002

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

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

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

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

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

Литература

[1] Информационно-аналитический центр по параллельным вычислениям в сети Internet.

[2] Вл.В.Воеводин. «Суперкомпьютерная грань компьютерного мира»// «Byte/Россия», № 4, 2000.

Владимир Воеводин: «Семь раз отмерь…»

Задачи каких типов лучше решать на кластерах?

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

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

А какие задачи, наоборот, нельзя перенести на кластер и они останутся за традиционными суперкомпьютерами?

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

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

- Я бы не стал противопоставлять автоматические средства, «ручное» программирование и специальные языки разработки параллельных программ. Как правило, приходится идти на компромисс и использовать несколько средств.

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

Сегодня есть две популярные технологии, одна из которых ориентирована на компьютеры с общей памятью, другая - с распределенной, к которым относятся кластеры. Это соответственно OpenMP и MPI. Какое-то время, они, конечно, будут жить обособленно, однако уже заметна тенденция к их слиянию.

А как же Parallel Virtual Machine (PVM)?

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

Вернемся к автоматическим средствам анализа программ. Какие из имеющихся на рынке продуктов вы могли бы назвать?

- Универсальных средств так до сих пор и нет, а те, что появились несколько лет назад, развиваются медленно. Миром завладели кластеры, а все, что связано с анализом и адаптацией кода для компьютеров с распределенной памятью, - чрезвычайно сложная задача. Помимо анализа потенциального параллелизма нужно согласованно распределять данные. Сегодня ни один компилятор не берется за то, чтобы из последовательного кода сделать параллельный для компьютера с распределенной памятью.

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

Что бы вы посоветовали тому, кто собирается строить кластер?

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

А на какие грабли вы наступали?

- На многие. Не существует «трех волшебных правил», соблюдая которые, вы избежите проблем. На каждом этапе создания программно-аппаратной среды приходится решать множество вопросов. И главный из них - зачем она нужна? К примеру, мы делали центр для Московского университета. Это огромное количество разных задач и непредсказуемая нагрузка - учебный класс на двадцать человек или какое-нибудь научное приложение могут легко загрузить весь кластер на сутки. А когда приходится совмещать разные типы задач, следует быть готовым ко всему. Если бы такой универсальности не требовалось, нашлось бы менее дорогое решение.

Интервью брал
Михаил Попов [ mpopov@computerra.ru ]


Владимир Воеводин - заместитель директора Научно-исследовательского вычислительного центра МГУ.

© ООО "Компьютерра-Онлайн", 1997-2022
При цитировании и использовании любых материалов ссылка на "Компьютерру" обязательна.