Серия "Параллельные вычисления для начинающих".

Суперкомпьютерная грань компьютерного мира

© Вл.В.Воеводин
директор, д.ф.-м.н., заведующий лабораторией
Параллельных информационных технологий НИВЦ МГУ
(e-mail: voevodin@vvv.srcc.msu.su)

При использовании отдельных частей данной статьи ссылка на автора обязательна.

Содержание:

Суперкомпьютеры - что это? (Вместо введения)

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

Для многих подобные компьютеры так и остаются тайной за семью печатями, некой TERRA INCOGNITA, с которой ассоциации всегда связаны с чем-то большим: огромные размеры, большие задачи, крупные фирмы и компании, невероятные скорости работы или что-то иное, но обязательно это будет "на грани", для чего "обычного" явно мало, а подойдет только "супер", суперкомпьютер или супер-ЭВМ. В этом интуитивном восприятии есть изрядная доля истины, поскольку к классу супер-ЭВМ принадлежат лишь те компьютеры, которые имеют максимальную производительность в настоящее время. Быстрое развитие компьютерной индустрии определяет относительность данного понятия - то, что десять лет назад можно было назвать суперкомпьютером, сегодня под это определение уже не попадает. Например, производительность персональных компьютеров, использующих Pentium-II/300MHz, сравнима с производительностью суперкомпьютеров начала 70-х годов, однако по сегодняшним меркам суперкомпьютерами не являются ни те, ни другие.

В любом компьютере все основные параметры тесно связаны. Трудно себе представить универсальный компьютер, имеющий высокое быстродействие и мизерную оперативную память, либо огромную оперативную память и небольшой объем дисков. Следуя логике, делаем вывод: супер-ЭВМ это компьютеры, имеющие в настоящее время не только максимальную производительность, но и максимальный объем оперативной и дисковой памяти (а также специализированное ПО, с помощью которого можно эффективно всем этим воспользоваться - прим. ред.).

Определений суперкомпьютерам пытались давать много, иногда серьезных, иногда ироничных. В частности, лет пять назад, когда эта тема поднималась в конференции comp.parallel, Кен Батчер (Ken Batcher) предложил такой вариант: суперкомпьютер - это устройство, сводящее проблему вычислений к проблеме ввода/вывода. Все верно, в каждой шутке есть доля шутки: что раньше долго вычислялось, временами сбрасывая нечто на диск, на супер-ЭВМ может выполниться мгновенно, переводя стрелки неэффективности на относительно медленные устройства ввода/вывода.

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

CRAY T932, векторно-конвейерный компьютер фирмы CRAY Research Inc. (в настоящее время это подразделение Silicon Graphics Inc.), впервые выпущенный в 1996 году. Максимальная производительность одного процессора равна почти 2 млрд. операций в секунду, оперативная память наращивается до 8Гб (Гига это в тысячу раз больше, чем Мега), дисковое пространство до 256000Гб (т.е. 256Тб, Тера это в тысячу раз больше, чем Гига). Компьютер в максимальной конфигурации содержит 32 подобных процессора, работающих над единой общей памятью, поэтому максимальная производительность всей вычислительной системы составляет более 60 млрд. операций в секунду.

IBM SP2, массивно-параллельный компьютер фирмы IBM (иногда такие компьютеры называют компьютерами с массовым параллелизмом). В настоящее время строится на основе стандартных микропроцессоров PowerPC 604e или POWER2 SC, соединенных между собой через высокоскоростной коммутатор, причем каждый имеет свою локальную оперативную память и дисковую подсистему. Характеристики этих микропроцессоров известны и особых удивлений не вызывают, однако в рамках одной SP системы их может быть объединено очень много. В частности, максимальная система, установленная в Pacific Northwest National Laboratoriy (Richland, USA), содержит 512 процессоров. Исходя из числа процессоров, можно представить суммарную мощность всей вычислительной системы...

HP Exemplar, компьютер с кластерной архитектурой от Hewlett-Packard Inc. В частности, модель V2250 (класс V) построена на основе микропроцессора PA-8200, работающего с тактовой частотой 240MHz. До 16 процессоров можно объединить в рамках одного узла с общей оперативной памятью до 16Гб. В свою очередь узлы в рамках одной вычислительной системы соединяются между собой через высокоскоростные каналы передачи данных.

ASCI RED, детище программы Accelerated Strategic Computing Initiative, - это самый мощный на настоящий момент компьютер. Построенный по заказу Министерства энергетики США, он объединяет 9152 (!) процессоров Pentium Pro, имеет 600Гб суммарной оперативной памяти и общую производительность 1800 миллиардов операций в секунду. Человеку потребовалось бы 57000 лет, чтобы даже с калькулятором выполнить все те операции, которые этот компьютер делает за 1 секунду!

Простые расчеты показывают, что даже умеренные конфигурации таких компьютеров могут стоить не один миллион долларов США - ради интереса прикиньте, сколько стоят, скажем, лишь 600 Гбайт оперативной памяти? Возникает целый ряд естественных вопросов:

  • какие задачи настолько важны, что требуются компьютеры стоимостью несколько миллионов долларов?
  • Или, какие задачи настолько сложны, что хорошего Pentium-II не достаточно?

На эти и подобные им вопросы хотелось бы найти разумные ответы.

Суперкомпьютеры - зачем это?

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

Примем упрощенную схему, при которой моделируемая область отображается в куб, однако и ее будет достаточно для оценки числа необходимых арифметических операций. Разумные размеры куба, при которых можно получать правдоподобные результаты - это 100*100*100 точек. В каждой точке куба надо вычислить от 5 до 20 функций: три компоненты скорости, давление, температуру, концентрацию компонент (вода, газ и нефть - это минимальный набор компонент, в более реалистичных моделях рассматривают, например, различные фракции нефти). Далее, значения функций находятся как решение нелинейных уравнений, что требует от 200 до 1000 арифметических операций. И наконец, если исследуется нестационарный процесс, т.е. нужно понять, как эта система ведет себя во времени, то делается 100-1000 шагов по времени. Что получилось:

106(точек сетки)*10(функций)*500(операций)*500(шагов по времени) = 2.5*1012

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

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

  • автомобилестроение,
  • нефте- и газодобыча,
  • фармакология,
  • прогноз погоды и моделирование изменения климата,
  • сейсморазведка,
  • проектирование электронных устройств,
  • синтез новых материалов,
  • и многие, многие другие.

По данным Марка Миллера (Mark Miller, Ford Motor Company), для выполнения crash-тестов, при которых реальные автомобили разбиваются о бетонную стену с одновременным замером необходимых параметров, съемкой и последующей обработкой результатов, компании Форд понадобилось бы от 10 до 150 прототипов новых моделей при общих затратах от 4 до 60 миллионов долларов. Использование суперкомпьютеров позволило сократить число прототипов на одну треть.

В 1995 году корпус автомобиля Nissan Maxima удалось сделать на 10% прочнее благодаря использованию суперкомпьютера фирмы Cray (The Atlanta Journal, 28 мая, 1995г). С помощью него были найдены не только слабые точки кузова, но и наиболее эффективный способ их удаления.

Совсем свежий пример - это развитие одной из крупнейших мировых систем резервирования Amadeus, используемой тысячами агенств со 180000 терминалов в более чем ста странах. Установка двух серверов Hewlett-Packard T600 по 12 процессоров в каждом позволила довести степень оперативной доступности центральной системы до 99.85% при текущей загрузке около 60 миллионов запросов в сутки.

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

Суперкомпьютеры - как это?

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

Попробуем разобраться, какой из факторов является решающим в достижении современных фантастических показателей производительности. Для разрешения этого вопроса обратимся к историческим фактам. Известно, что на компьютере EDSAC (1949 г.), имевшего время такта 2мкс, можно было выполнить 2*n арифметических операций за 18*n мс, то есть в среднем 100 арифметических операций в секунду. Сравним с современным суперкомпьютером CRAY C90: время такта приблизительно 4нс, а пиковая производительность около 1 миллиарда арифметических операций в секунду.

Что же получается? Производительность компьютеров за этот период выросла в приблизительно в десять миллионов раз. Уменьшение времени такта является прямым способом увеличением производительности, однако эта составляющая (с 2мкс до 4нс) в общем объеме дает вклад лишь в 500 раз. Откуда же взялось остальное? Ответ очевиден - использование новых решений в архитектуре компьютеров, среди которых основное место занимает принцип параллельной обработки данных.

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

 

Параллельная обработка. Если некое устройство выполняет одну операцию за единицу времени, то тысячу операций оно выполнит за тысячу единиц. Если предположить, что есть пять таких же независимых устройств, способных работать одновременно, то ту же тысячу операций система из пяти устройств может выполнить уже не за тысячу, а за двести единиц времени. Аналогично система из N устройств ту же работу выполнит за 1000/N единиц времени. Подобные аналогии можно найти и в жизни: если один солдат вскопает огород за 10 часов, то рота солдат из пятидесяти человек с такими же способностями, работая одновременно, справятся с той же работой за 12 минут - принцип параллельности в действии!

 

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

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

Казалось бы конвейерную обработку можно с успехом заменить обычным параллелизмом, для чего продублировать основное устройство столько раз, сколько ступеней конвейера предполагается выделить. В самом деле, пять устройств предыдущего примера обработают 100 пар аргументов за 100 единиц времени, что быстрее времени работы конвейерного устройства! В чем же дело? Ответ прост, увеличив в пять раз число устройств, мы значительно увеличиваем как объем аппаратуры, так и ее стоимость. Представьте себе, что на автозаводе решили убрать конвейер, сохранив темпы выпуска автомобилей. Если раньше на конвейере одновременно находилась тысяча автомобилей, то действуя по аналогии с предыдущим примером надо набрать тысячу бригад, каждая из которых (1) в состоянии полностью собрать автомобиль от начала до конца, выполнив сотни разного рода операций, и (2) сделать это за то же время, что машина прежде находилась на конвейере. Представили себестоимость такого автомобиля? Нет? Согласен, трудно, разве что Ламборгини приходит на ум, но потому и возникла конвейерная обработка...

Сегодня параллелизмом в архитектуре компьютеров уже мало кого удивишь. Все современные микропроцессоры, будь то Pentium II или PA-8200, MIPS R10000 или Power2 SuperChip используют тот или иной вид параллельной обработки. На презентациях новых чипов и в пресс-релизах корпораций это преподносится как последнее слово техники и передовой край науки, и это действительно так, если рассматривать реализацию этих принципов именно в рамках одного кристалла.

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

Все новое - это хорошо забытое старое

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

Все самые первые компьютеры, например, EDSAC, EDVAC, UNIVAC, сначала считывали данные последовательно бит за битом из памяти, а затем их аналогично обрабатывали в арифметическом устройстве.

1953 г. Первым коммерчески доступным компьютером, использующим разрядно-параллельную память (на CRT) и разрядно-параллельную арифметику, стал компьютер IBM 701. К слову будет сказано, наибольшую популярность в то время получила модель IBM 704 (1955 г.), проданной в количестве 150 экземпляров (!), в которой, помимо упомянутых особенностей, была впервые применена память на ферритовых сердечниках и аппаратное арифметическое устройство с плавающей точкой.

1958г. Процессоры первых компьютеров сами управляли вводом/выводом. Однако скорость работы самого быстрого внешнего устройства, а по тем временам это магнитная лента, была в 1000 раз меньше скорости процессора, поэтому во время операций ввода/вывода процессор фактически простаивал. В 1958г. к компьютеру IBM 704 присоединили 6 независимых процессоров ввода/вывода, которые после получения команд могли работать параллельно с основным процессором, а сам компьютер переименовали в IBM 709. Данная модель получилась удивительно удачной, так как вместе с модификациями было продано около 400 экземпляров, причем последний был выключен в 1975 году - 20 лет существования!

1961г. Создается компьютер IBM STRETCH, имеющий две принципиально важные особенности: опережающий просмотр вперед для выборки команд и расслоение памяти на два банка для согласования низкой скорости выборки из памяти и скорости выполнения операций.

1963г. В Манчестерском университете разработан компьютер ATLAS, использующий конвейерный принцип выполнения команд. Выполнение команд разбито на 4 стадии: выборка команды, вычисление адреса операнда, выборка операнда и выполнение операции, позволившие уменьшить время выполнения команд в среднем с 6 мкс до 1,6 мкс. Справедливости ради надо отметить, что данный компьютер вообще оставил заметный след в истории развития вычислительной техники: помимо сказанного, в нем впервые была использована мультипрограммная операционная система, основанная на использовании виртуальной памяти и системы прерываний.

1964г. Фирма Control Data Corporation (CDC) при непосредственном участии одного из ее основателей, Сеймура Р.Крэя (Seymour R.Cray) выпускает компьютер CDC-6600 - первый компьютер, в котором использовалось несколько независимых функциональных устройств. Для сравнения с сегодняшним днем приведем некоторые параметры компьютера: время такта 100нс, производительность 2-3 млн. операций в секунду, оперативная память разбита на 32 банка по 4096 60-ти разрядных слов, цикл памяти 1мкс, 10 независимых функциональных устройств. Машина имела громадный успех на научном рынке, активно вытесняя машины фирмы IBM.

1969г. CDC выпускает компьютер CDC-7600 с восемью независимыми конвейерными функциональными устройствами - сочетание параллельной и конвейерной обработки.

В 1967 году были начаты работы над проектом ILLIAC IV, первым матричным процессором, объединяющим 256 синхронно работающих процессорных элементов. К концу 1971 года изготовлена система из 64-х процессоров, в 1974г. она введена в эксплуатацию, однако доводка шла до 1975 года. Несмотря на то, что построили в 4 раза меньше задуманного, да и то лишь в одном экземпляре, а денег в результате затратили в 4 раза больше, данный проект оказал огромное влияние на архитектуру последующих машин подобного класса таких, как PEPE, BSP, ICL DAP и ряда других.

В 1972 году С.Крэй покидает CDC и основывает свою компанию Cray Research, которая в 1976г. выпускает первый векторно-конвейерный компьютер CRAY-1: время такта 12.5нс, 12 конвейерных функциональных устройств, пиковая производительность 160 миллионов операций в секунду, оперативная память до 1Мслова (слово - 64 разряда), цикл памяти 50нс. Главным новшеством является введение векторных команд, работающих с целыми массивами независимых данных и позволяющих эффективно использовать конвейерные функциональные устройства.

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

Попутно стоит заметить, что параллелизм это не только передовая технология, используемая во всех современных суперкомпьютерах, но и довольно страшная сила. Очередной пример тому появился совсем недавно. По сообщению Electronic Frontier Foundation, Джон Гилмор (John Gilmore) и Поль Кочер (Paul Kocher) смогли взломать 56-битный код, используемый банками и некоторыми военными организациями США, с помощью собранной в домашних условиях параллельной вычислительной системы.

Раскрытый алгоритм шифрования, известный как DES (Data Encryption Standard), использует 56-битные ключи, и это при том, что сейчас в реальных ситуациях во многих случаях используются лишь 40-битные. До настоящего момента правительственные органы США утверждали, что ни террористы, ни какие-либо другие криминальные структуры не в состоянии сделать компьютер, взламывающий DES.

Вся работа по расшифровке была проделана за 56 часов на компьютере, состоящем из более чем 1000 процессоров: 27 плат по 64 процессора в каждой. Каждая плата была подсоединена к обычной персоналке, которая и управляла всем процессом. Гилмор назвал свою систему Deep Crack - мягкий намек на шахматный компьютер Deep Blue от IBM. Вечером 17 июля этого года после проверки 17,902,806,669,197,312 ключей компьютер определил, что зашифрованным предложением было: "It's time for those 128-, 192-, and 256-bit keys."

А что же сейчас используют в мире?

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

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

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

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

3. Параллельные компьютеры с общей памятью. Вся оперативная память таких компьютеров разделяется несколькими одинаковыми процессорами. Это снимает проблемы предыдущего класса, но добавляет новые - число процессоров, имеющих доступ к общей памяти по чисто техническим причинам нельзя сделать большим. В данное направление входят многие современные многопроцессорные SMP-компьютеры, например, сервер HP T600 или Sun Ultra Enterprise 5000.

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

Два раза в год собираются данные для формирования списка пятисот самых мощных вычислительных установок мира. Последняя редакция списка вышла в ноябре этого года, согласно которой первое место занимает компьютер ASCI Red, а на второй позиции стоит компьютер Cray T3E/1200 от Silicon Graphics, объединяющий 1084 процессора Alpha.

Если где-то прибудет, то где-то обязательно уменьшится

К сожалению чудеса в жизни редко случаются. Гигантская производительность параллельных компьютеров и супер-ЭВМ с лихвой компенсируется сложностями их использования. Начнем с самых простых вещей. У вас есть программа и доступ, скажем, к 256-процессорному компьютеру. Что вы ожидаете? Да ясно что: вы вполне законно ожидаете, что программа будет выполняться в 256 раз быстрее, чем на одном процессоре. А вот как раз этого, скорее всего, и не будет.

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

S<=1/(f+(1-f)/p)

Если вдуматься как следует, то закон, на самом деле, страшный. Предположим, что в вашей программе лишь 10% последовательных операций, т.е. f=0.1 . Что утверждает закон? А он говорит о том, что сколько бы вы процессоров не использовали, ускорения работы программы более, чем в десять раз никак не получите... да и то 10 - это теоретическая верхняя оценка самого лучшего случая, когда никаких других отрицательных факторов нет... :((

Отсюда первый вывод - прежде, чем основательно перепахивать код для перехода на параллельный компьютер (а любой суперкомпьютер, в частности, является таковым) надо основательно подумать: "А не будет ли потом мучительно больно за увиденный результат и стоит ли овчинка выделки?". Если оценив заложенный в программе алгоритм вы поняли, что доля последовательных операций велика, то на значительное ускорение рассчитывать явно не приходится и нужно думать о замене отдельных компонент алгоритма.

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

	s = 0
	Do i = 1, n
	    s = s + a(i)      
 	EndDo

(можно тоже самое на любом другом языке)

По своей природе он строго последователен, так как на i-й итерации цикла требуется результат с (i-1)-й и все итерации выполняются одна за одной. Имеем 100% последовательных операций, а значит и никакого эффекта от использования параллельных компьютеров. Вместе с тем, выход очевиден. Поскольку в большинстве реальных случаев нет существенной разницы, в каком порядке складывать числа, выберем иную схему сложения. Сначала найдем сумму пар соседних элементов: a(1)+a(2), a(3)+a(4), a(5)+a(6) и т.д. Заметим, что при такой схеме все пары можно складывать одновременно! На следующих шагах будем действовать абсолютно аналогично, получив вариант параллельного алгоритма.

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

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

Словом, заставить параллельную вычислительную систему или супер-ЭВМ работать с максимальной эффективностью на конкретной программе - это, прямо скажем, задача не из простых. Да что там 'заставить работать', иногда даже возникающие вокруг суперкомпьютеров вопросы ставят в тупик. Как вы думаете, верно ли утверждение: чем мощнее компьютер, тем быстрее на нем можно решить данную задачу. Ну конечно же, раз спрашиваю, значит ответ противоположный ожидаемому. Действительно, это не верно, что можно пояснить простым бытовым примером. Если один землекоп выкопает яму 1м*1м*1м за 1 час, то два таких же землекопа это сделают за 30 мин - в это можно поверить. А за сколько времени эту работу сделают 60 землекопов? Неужели за 1 минуту? Конечно же нет! Начиная с некоторого момента они будут просто мешаться друг другу, не ускоряя, а замедляя процесс. Так же и в компьютерах: если задачка слишком мала, то мы будем дольше заниматься распределением работы, синхронизацией процессов, сборкой результатов и т.п., чем непосредственно полезной работой.

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

О чем будет рассказано дальше

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

  • современных технологиях параллельного программирования;
  • истории развития архитектуры компьютеров и появления параллелизма;
  • обычных и честных методах измерения производительности параллельных компьютеров;
  • заявленных характеристиках и реальных особенностях основных классов современных супер-ЭВМ;
  • параллельных компьютерах в современной науке и промышленности;
  • о том, зачем компиляторам для супер-ЭВМ нужен особый интеллект,

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

© Лаборатория Параллельных Информационных Технологий, НИВЦ МГУ Rambler's Top100