Кластеры -- о главном

14 май, 2002 - 23:00Андрей Зубинский
Во времена оные написание статьи с такой "громкой" тематикой никаких проблем бы не вызвало. Да и какие могут быть проблемы, если речь идет о столь насущной и востребованной теме, когда "космические корабли бороздят...", "враг не дремлет...", "ядерный щит" требует чуть ли не ежеминутного совершенствования, а соревнование систем заставляет заботиться о престиже. Сегодня же все не так просто...
Вместо бравурного начала (возможно, даже и вполне уместного) автор предпочитает сразу озадачить читателя более чем странным вопросом: "Насколько реально применение супервычислений в нашей сегодняшней действительности?". Увы, мы вынуждены искать ответ на этот вопрос еще до толкований используемых терминов; пока же вместо них мы ограничимся интуитивным соображением -- приставка "супер" означает, что речь идет о чем-то действительно исключительном.

Кластеры -- о главном
Закон Амдала в действии -- при достаточно большой доле в составе программы нераспараллели-ваемых команд (например, S=20%) наблюдается прекращение роста производительности после определенного (20) числа вычислителей
Кластеры -- о главном
В таком представлении закон Амдала позволяет сделать вывод: наиболее эффективным способом повышения производительности является не увеличение числа вычислителей, а алгоритмическое совершенствование задач
Ставшие уже классическими области применения суперкомпьютеров как главного механизма супервычислений перечислить нетрудно -- к ним относятся вычислительные эксперименты, заменяющие (дополняющие) натурные испытания в фундаментальных или прикладных исследованиях, моделирование сложных технических систем на разных этапах проектирования, построение математических моделей естественных, социальных, экономических структур, решение задач управления крупномасштабными системами с высокой степенью риска (например, противовоздушной обороной страны). Список можно продолжать очень долго, но, несмотря на колоссальные различия между отдельными сферами применения, у них есть одно важнейшее общее свойство. А именно -- все они исключительно дороги. Настолько дороги, что сам факт концентрации усилий в этих областях заставляет услышать в словах "сверхвычисления" и "сверхдержава" не только игру слов.

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

И все-таки, старательно избегая столь модной в последнее время "IT-маниловщины", сверхвычислениям можно найти применение куда более массовое и реальное. Логистика, построение, анализ и оптимизация моделей бизнес-процессов, решение глобальных задач оптимизации транспортной, коммуникационной, энергетической и оборонной систем, управление закупками энергоносителей -- разве эти темы не актуальны? И при серьезном подходе, а не на уровне полушаманских методик -- разве они не требуют громадных вычислительных ресурсов? Судя по тому, что в США одним из самых надежных заказчиков суперкомпьютеров является Министерство экономики, подобные задачи действительно и актуальны, и ресурсоемки. Впрочем, в этих очевидных соображениях гораздо важнее реальная достижимость результатов -- хотя бы по сравнению с сомнительностью прожектов столь популярной Internet-экономики.

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


Амдал против Мура

Раз уж мы говорим о супервычислителях, то не воспользоваться хотя бы простым калькулятором было бы непозволительно. Тем более что в поисках ответа на вопрос "а не стоит ли подождать роста производительности?" можно и нужно прибегнуть к "супервычислениям".

В соответствии с законом Мура вычислительная мощность процессоров увеличивается в 2 раза за промежуток времени 18 месяцев, что позволяет прогнозировать с достаточной точностью прирост производительности.

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

Предположим, что некоторая задача, выполняющаяся на однопроцессорной машине за Ts единиц времени, допускает частичную параллельную реализацию. Часть операций этой задачи, для которых возможно только последовательное выполнение, обозначим S (S<1). Соответственно, подлежащим распараллеливанию операциям остается часть задачи, равная (1-S). Теперь если мы запустим задачу на идеальном параллельном компьютере с N однотипными процессорами, ее время исполнения можно определить по очевидной формуле:

Tp = S·Ts + ((1-S)·Ts)/N,

где S·Ts -- время выполнения последовательной части задачи, ((1-S)·Ts)/N -- время выполнения распараллеленной части на N процессорах. Теперь можно найти прирост производительности абстрактного параллельного компьютера, разделив время решения задачи обычным последовательным вычислителем на время, достигаемое распараллеливанием:

A = Ts/Tp = N/(N·S + 1-S).


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

Теперь, когда мы обладаем "мощной теоретико-эмпирической базой", пора искать подход к поиску ответа на поставленный вопрос. Почему только подход? Так как мы заранее не знаем ни пригодность пока еще абстрактной задачи к распараллеливанию (т. е. долю последовательно выполняемых операций S), ни важность этой задачи, которую можно выразить в стоимости времени, затраченного на ожидание достижения процессорами требуемого уровня быстродействия в соответствии с законом Мура, никаких общих выводов мы делать не вправе. Кроме, естественно, формулировки принципа оценки -- если в задаче доля последовательных операций велика (более 1/3), требуемый для ее решения прирост производительности также не очень высок (скажем, порядок), и, наконец, время решения задачи некритично (стоимость ожидания невелика) -- то, вероятнее всего, о сверхвычислителе лучше и не задумываться. В противном случае пора начинать строить свой суперкомпьютер. Это, кроме всего прочего, еще и интересно.


Отсекая недоступное

"Зато теперь мы знаем, где нет грибов..."

Кластеры -- о главном
Масштабный параллельный DMMPS-компьютер компании Genetic Programming -- 1000 вычислителей, производительность 0,35 TFLOPS, для охлаждения конструкции используются два промышленных кондиционера весом по 25 тонн каждый
Кластеры -- о главном

В формулировке закона Амдала скрыт один маленький, но крайне важный нюанс -- идеальность параллельного вычислителя. А как только начинаются нюансы, вся красота и изящность логических конструкций меркнет. Под "идеальностью" здесь понимается полное игнорирование расходов времени на разнообразные дополнительные операции, неизбежно сопровождающие параллельное решение задачи на нескольких процессорах. Или, иначе говоря, идеальный параллельный вычислитель Амдала подразумевает бесконечную полосу пропускания каналов связи, соединяющих все элементы вычислительной машины. Реальным компьютерам до такой идиллии далеко, соответственно, и их показатели производительности намного хуже предсказываемых моделью Амдала. Правда, в отличие от эмпирического характера закона Мура, деградацию производительности в реальных машинах учесть проще, чем вероятности землетрясения на Тайване или падения курса акций компании X. И кроме того, степень удаленности архитектуры реальной машины от вычислителя Амдала дает нам неожиданно мощный инструмент классификации, вооружившись которым, мы можем оценить не блещущий разнообразием перечень высокоуровневых архитектур параллельных компьютеров, выбрать из него подходящую (соответствующую нашим реалиям) и даже оценить ее достоинства и недостатки. И все это -- без углубленного анализа низкоуровневой организации!

Уже вполне очевидно, что реальная машина тем "ближе" к машине Амдала, чем быстродействие каналов связи в ней выше. В современных компьютерах самый быстрый канал связи соединяет центральный процессор (CPU) и оперативную память -- следовательно, наиболее "близкими" к идеалу будут параллельные компьютеры, у которых множество процессоров использует именно этот высокопроизводительный ресурс. Такие системы называются SMMP (Shared Memory MultiProcessor) -- "мультипроцессорами с разделяемой памятью", они давно реализованы: в мире настольных компьютеров -- в достаточно убогом, но доступном варианте SMP (симметричных мультипроцессорных систем), а в мире суперсерверов -- в баснословно дорогих и не менее баснословно производительных системах. К слову, факт дороговизны SMMP-компьютеров -- не прихоть их производителей, и мы уже обладаем достаточным набором знаний для его объяснения: хотя шина оперативной памяти характеризуется очень высокой пропускной способностью, а сама память -- высоким быстродействием, эти показатели конечны. И решение задачи сохранения близости к идеальной машине Амдала SMMP-компьютера со многими процессорами требует катастрофически дорогих ухищрений по мере роста числа CPU. Впрочем, эта особенность SMMP хорошо наблюдаема в характеристиках реальных систем -- число процессоров в них не превышает нескольких десятков (в редких случаях измеряется сотнями -- например, 256 CPU суперкомпьютеров семейства SGI Origin), а стоимость выражается шестизначными числами.

Куда дальше от идеала располагается обширный класс параллельных вычислителей, именуемый DMMPS (Distributed Memory Massively Parallel System) -- массово-параллельные системы с распределенной памятью. По сути, за этим страшным названием может скрываться что угодно, объединенное общим свойством, -- DMMPS-компьютер состоит из множества отдельных вычислительных машин (каждая из которых имеет собственный неразделяемый самый быстрый ресурс -- оперативную память), соединенных некоторыми каналами связи в единую систему. Иными словами, DMMPS больше относится к характеру использования множества компьютеров, чем к специфическим дорогостоящим аппаратным ухищрениям или к достижениям архитектурной мысли. Например, обычную офисную сеть из самых заурядных ПК можно превратить в DMMPS-систему. Или другая крайность -- можно построить DMMPS-систему на основе специальных микрокомпьютеров: некогда знаменитая компания INMOS даже выпускала чудесные серийные однокристальные процессорные узлы -- транспьютеры, специально спроектированные для реализации больших DMMPS-вычислителей. Возвращаясь к теме удаленности от идеальной машины Амдала, следует обратить внимание читателя на использованные в пояснении определения DMMPS слова "некоторые каналы связи". В реальности они действительно "слишком некоторые" -- с несоизмеримо худшими параметрами по сравнению с шиной оперативной памяти. Соответственно, оценка прироста производительности в DMMPS-системах значительно ниже (в некоторых случаях -- на 80--90%) ожидаемой. Правда, закон Амдала оставляет маленькую "лазейку" -- зависимость от размера нераспараллеливаемой части программы, которая на деле является пусть не панацеей, но все же чем-то более внушительным, чем спасительная соломинка.

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

Мы же можем уже сделать ряд определенных выводов -- SMMP-системы обладают очень высоким быстродействием, но характеризуются и исключительно высокой стоимостью масштабирования (повышения числа CPU) и, что важнее, имеют принципиальный верхний порог масштабирования. DMMPS-системы, напротив -- быстродействием не блещут, но очень дешевы и несоизмеримо лучше масштабируются, а пороговый уровень масштаба для них в общем случае никем не определен -- давно существуют DMMPS-компьютеры с числом вычислителей 65535 и даже более.

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


Мур ставит точку в деле Амдала

Кластеры -- о главном
Кластер Acme -- самый дешевый из всех бюджетных, несмотря на более чем скромные технические показатели (вычислители с процессорами AMD K62-450, объемом памяти 40 MB и медленными сетевыми картами Ethernet), достигает очень высокой для своей ценовой категории произво-дительности

Модель идеальной машины Амдала обладает еще одним примечательным нюансом -- она не учитывает производительности отдельного вычислителя. Даже косвенная оценка последней (время выполнения всей задачи одним процессором Ts) исчезает в конечной формуле. Что, впрочем, легко объясняется допущением идеальности. В реальных параллельных компьютерах, естественно, все обстоит немного иначе -- иногда настолько "немного", что "с точностью до наоборот". В SMMP-системах, где над архитектурой довлеет ограничение -- максимум полосы пропускания шины с оперативной памятью, повышение производительности отдельных процессоров может просто вызвать необходимость уменьшения их количества, что вносит дополнительную прелесть в оценку масштабируемости таких архитектур. А вот DMMPS-системы, опять же, с зеркальной точностью по отношению к своим конкурентам реагируют на проявления закона Мура -- их быстродействие растет.

Естественно, с учетом ряда нюансов, но о них -- позже. Главным для нас остается неоспоримый факт влияния... закона Мура на закон Амдала -- с увеличением производительности и снижением стоимости вычислителей от DMMPS-систем можно добиться повышения вычислительной мощности "малыми финансами", в случае же с SMMP-системами все не так просто и очевидно. Кроме того, у проявлений закона Мура есть и косвенные следствия -- с ростом процессоров повышаются (пусть и не так быстро, как хотелось бы) и пропускные способности периферийных шин, что позволяет полноценно использовать немалые ресурсы дешевеющих день за днем "скорострельных" сетей, например Gigabit Ethernet.

В принципе, таких соображений достаточно -- по сути, ход наших рассуждений привел нас к тем же выводам, к которым пришли очень многие специалисты во всем мире. Но, чтобы придать большую убедительность выбору, остается добавить "последнюю каплю" -- еще один неприятный нюанс, преподносимый реальностью. А именно -- вопрос надежности. Как показывает практика, выходить из строя может все, что угодно -- даже то, что проектировалось с учетом самых немыслимых требований. В SMMP-системе, например, выход из строя крошечного чипа, задействованного в сложнейшей реализации схемы управления шиной разделяемой памяти, приведет, естественно, к неминуемой "погибели" всего супервычислителя -- вместе с решавшимися не одну неделю суперзадачами. В плохо спроектированной DMMPS-системе сбой одного вычислителя может привести к аварийной остановке решаемых задач... но -- пока мы говорим о супервычислителе, не слишком отдаляясь от модели Амдала, в понятие "хорошо спроектированный" мы включаем не только аппаратные средства и системное ПО, но и сами прикладные задачи (по модели Амдала ставшие неотъемлемой частью показателей качества системы). И именно в случае DMMPS "хорошее проектирование" является прерогативой программиста -- для этого есть и доступные инструментальные средства, и системная поддержка, и отработанные приемы программирования.

Итак, пора делать выводы -- на основе наших рассуждений уверенно победили DMMPS-системы.


Вторая проекция

Кластеры -- о главном
Кластер Klingon, использующийся для астрофизических исследований

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

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

Речь, естественно, идет о самой знаменитой классификации Флинна, датируемой далеким 1966 г. SISD,MISD,SIMD и MIMD -- аббревиатуры, образованные комбинациями всего четырех слов: S -- один (Single), M -- много (Multiple), I -- команда (Instruction), D -- данные (Data). Например, SISD -- один поток команд, один поток данных (Single Instruction Single Data) -- описывает обширный класс однопроцессорных последовательных машин, SIMD и MIMD -- не менее обширные классы параллельных машин, обрабатывающих одновременно одним потоком данных (программой) разные наборы данных (SIMD) и многими потоками команд (разными программами) разные данные (MIMD). Для классификации Флинна существует множество расширений, но при нашем подходе они не потребуются -- введя ограничение архитектуры DMMPS, мы достаточно точно определяем интересующий нас класс архитектур.

В терминах DMMPS-вычислений наибольший интерес представляют "проекции" SIMD и MIMD. Для них даже "изобретены" менее понятные, но более неформальные названия -- "crowd computing" ("вычисления толпой", SIMD/SPMD, где P -- программа), "tree computing" ("древовидные вычисления", вариация MIMD/MPMD). "Вычисления толпой" подразумевают параллельную обработку разных фрагментов данных одним и тем же кодом, "древовидные вычисления" намного сложнее -- структура изменяется в соответствии с некоторым алгоритмом, в результате чего отдельные вычислители обрабатывают разными программами разные фрагменты данных.

Существует и еще одна точка зрения на эту "проекцию", сторонники которой называют MIMD "обработкой с функциональной декомпозицией", а SIMD -- "обработкой с декомпозицией данных".

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


Основа основ, или Size no matter

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

Наконец наступило время вооружиться "увеличительным стеклом" и рассмотреть ключевой элемент любой DMMPS-системы, без которого само ее существование как приближения к идеальной машине Амдала было бы невозможным. Для начала сообщим нечто совершенно неординарное: исполняемый файл одного из вариантов этой "основы основ" параллельных вычислений, созданный для ОС FreeBSD, занимает всего... 2400 байт! Вот уж, действительно, неисповедимы пути развития технологий -- могучая инфраструктура, основанная на множестве концепций, высокие технические показатели, оказывается, "опираются" на совсем крохотную утилитку и маленькую библиотеку функций!

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

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

Но все-таки есть один исключительно ресурсоемкий метод, гарантирующий работоспособность для любой функции, -- метод "грубой силы", иначе -- полного перебора. Перебирать, естественно, придется как можно больше точек в области значений функции (перебрать все точки нереально даже для идеальной машины Амдала с любым конечным числом процессоров). Для этого существует мощная математическая абстракция -- так называемые точки и кривые, равномерно заполняющие многомерный куб (например, кривые Пеано), и простые и быстрые программные реализации генераторов таких точек/кривых. Очевидно, что эффективного распараллеливания в решении такой задачи можно добиться разбиением всей области значений на фрагменты и "раздачей" фрагментов для поиска одинаковым программам, выполняющимся на каждом вычислителе DMMPS-компьютера. На отдельных вычислителях будет работать простая программа, не сильно отличающаяся от однопроцессорной версии, генерирующая точку в своей многомерной области (т. е. формирующая набор значений переменных), вычисляющая значение функции F1 от этого набора, генерирующая новую точку и вычисляющая значение функции F2 в ней, сохраняющая в качестве F1 большее (или меньшее при поиске минимума) значение и повторяющая эти действия, скажем, несколько десятков миллионов раз.

В результате такого отсева будет найдена точка с экстремальным значением (о точности мы сейчас не говорим) в данной области. Остается только собрать полученные всеми вычислителями значения и выбрать из них наибольшее (или наименьшее). Идеальная картина (для нее мы уже знаем название -- "вычисления толпой"), в которой сведена до абсолютного минимума нераспараллеленная часть программы, заключается в разделении исходной области на равное числу вычислителей N подобластей и нахождении максимального/минимального значения из множества, содержащего N чисел.

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

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

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


А теперь о серьезном

Раз уж "основа основ" -- МОС -- является ведущим системообразующим элементом DMMPS-вычислителя, то с двумя ее главными представителями необходимо познакомиться поближе.

Исторически первый МОС, завоевавший устойчивое признание и не сдающий до сих пор позиции, -- PVM -- параллельная виртуальная машина (Parallel Virtual Machine). Главными особенностями этой программы, прошедшей долгие годы эксплуатации, совершенствования и оттачивания (проект PVM выдал "на-гора" первую публично доступную реализацию МОС в далеком 1991 г.), сегодня можно считать даже не распространенность, а авторство и изначально заложенный в ее идеологию и бережно сохраняемый по сей день компромисс.

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

PVM -- типичный представитель так метко описанного Бруксом класса уникальных программ. Разработан МОС PVM был всего двумя программистами -- Вайди Сандерамом и Алом Гейстом (Vaidy Sunderam, Al Geist), и очень быстро приобрел титул стандарта де-факто -- буквально через 2 года после выхода первой версии. По сей день PVM отличается отполированностью, компактностью кода и завидным изяществом реализации. А вот компромисс... Создатели PVM умышленно в пору "дорогих вычислений" выделили особым пунктом в требованиях к реализации возможность объединения принципиально разных вычислителей (с разными ОС и на различных аппаратных платформах) в единый DMMPS-компьютер. Решение такой задачи далеко не так просто, как кажется на первый взгляд, из-за технических причин: например, разные вычислители могут быть построены на процессорах с различным endian (старшинством байтов в машинном слове). Решению проблем мобильности было отдано предпочтение перед, казалось бы, более важными для подобной системы показателями производительности. К этой особенности PVM мы вернемся в дальнейшем.

Второй представитель мира МОС на деле не является программой -- это открытые спецификации стандарта на утилиты, программные вызовы, взаимодействие с ОС вычислителя и сторонним ПО системного назначения. Стандарт MPI -- интерфейса передачи сообщений (Message Passing Interface) -- разрабатывался и продолжает совершенствоваться большим комитетом разработчиков спецификаций. Конкретные программные реализации МОС по этим спецификациям -- дело сторонних коллективов. Говорить о конкуренции двух проектов -- PVM и MPI -- трудно хотя бы потому, что ведущий автор PVM Ал Гейст является "по совместительству" и одним из участников комитета разработки спецификаций MPI. И все-таки, раз есть возможность выбора, то выбор нужно сделать, а заодно и ознакомиться способом "сравнительного описания" с возможностями двух программ. На самом деле актуальность проблемы выбора невысока: для PVM и MPI давно созданы библиотеки-"облатки", позволяющие разрабатывать независимые от используемой МОС параллельные задачи.

Главное отличие двух проектов кроется в названии: PVM создает из DMMPS-системы полноценный динамически изменяемый параллельный компьютер с поддержкой средств управления процессами и ресурсами, MPI же перекладывает заботу о формировании такой высокоуровневой абстракции на стороннее ПО. Динамический характер виртуального компьютера, образованного дуэтом PVM--DMMPS-система, означает возможность перестроения структуры компьютера "на лету" -- отдельные вычислители могут добавляться в состав виртуальной машины или удаляться из нее, MPI же требует статической организации DMMPS-системы.

Еще одно отличие PVM и MPI заключается в строгости предъявляемых требований к вычислителям, образующим DMMPS-систему. MPI подразумевает так называемую гомогенность вычислительной среды в пределах одного DMMPS-компьютера, это означает, что все вычислители должны быть одной архитектуры. PVM, напротив, допускает использование гетерогенной среды -- в основанной на PVM DMMPS-системе могут "уживаться" машины различной архитектуры (естественно, копии бинарных прикладных программ должны быть созданы для всех используемых архитектур). И, наконец, одно из принципиальных свойств МОС -- поддержка механизмов, обеспечивающих устойчивость к ошибкам, на сегодняшний день реализована практически одинаково в обеих системах.

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


И еще серьезнее...

Постепенно увеличивая степень деталировки описания, мы наконец добрались до одного из самых важных вопросов в построении DMMPS-систем -- до пока ни разу не "открывших личика" абстрактных "соединений" между вычислителями. Впрочем, похоже, наступило время полностью раскрыть карты и начать называть вещи своими именами. Под "соединениями" в дальнейшем будут пониматься доступные и хорошо поддержанные различными ОС реализации стандартных протоколов, таких, как Fast Ethernet и Gigabit Ethernet (мы ведь ведем беседу реальными в наших условиях терминами), под "вычислителями", опять же, -- реальные в наших условиях недорогие компьютеры архитектуры x86 (и прочие, но с соблюдением одного условия -- доступные). Эти два последних штриха позволяют дать более привычное и модное название столь экзотичному понятию "DMMPS-система" -- кластер.

Теперь пора поговорить конкретнее о "соединениях". Возвращаясь к приведенному выше примеру решения оптимизационной задачи, следует отметить, что далеко не все (скорее -- очень немногие) полезные задачи обладают такой идеальной приспособленностью к эффективному распараллеливанию. Для большинства требуются изощренные алгоритмы, очень интенсивно использующие процессы передачи небольших сообщений. Естественно, что в программах, написанных на основе МОС PVM и MPI, в том или ином виде присутствуют механизмы синхронизации, поддерживающие процесс "общения" (даже в MPI, выгодно отличающейся асинхронным дизайном, эти механизмы "упрятаны" в реализации библиотеки). Так, в PVM, например, есть три основных способа получения сообщения -- блокирующий выполнение программы до появления требуемого сообщения, неблокирующий -- срабатывающий только в том случае, если сообщение существует, и, наконец, -- получение с блокировкой выполнения, ограниченной по времени (для исключения возможности остановки исполнения навсегда). Масштабы времени, с которыми приходится иметь дело, оперируя понятием "получение сообщения", ничтожно малы -- ведь речь идет о библиотечных вызовах в программах, выполняющихся на процессорах с очень высокой тактовой частотой. Следовательно, задержки в "соединении" существенно "затормаживают" выполнение распараллеленной программы с интенсивным обменом сообщениями -- ведь львиную долю времени (в масштабах процессора) задачи ожидают получения сообщений -- задержки в широкодоступных сетях измеряются сотнями микросекунд. За время типовой задержки 150 мкс в некоммутируемой сети FastEthernet процессор с тактовой частотой 1 GHz мог бы выполнить... 150 тыс. коротких однотактных команд! Этот простейший пример дает нам возможность оценить степень удаленности реального кластера от идеальной модели вычислителя Амдала. На фоне этой информации покажется интересным факт, выявленный во время продолжительной эксплуатации больших кластеров, использующих в качестве соединений FastEthernet: оказывается, многие задачи совершенно неприхотливы к полосе пропускания сети. Так, в 1000-процессорном кластере компании Genetic Programming задействованная в ходе расчетов полоса пропускания сети составляет всего 2 Mbps (т. е. 2%).

Для борьбы с простоями из-за задержек в соединениях в кластерах используют характеризующиеся временем задержки порядка единиц микросекунд дорогостоящие специализированные интерфейсы или же... с ней смиряются, добиваясь повышения суммарной производительности совершенствованием алгоритмов. И, надо сказать, добиваются "малой кровью" -- "потешный" кластер проекта Acme, собранный из "компьютерных отходов" с блошиного рынка, основанный на МОС PVM, суммарной стоимостью $2948 показывает в тестах трехкратное превышение производительности по сравнению с четырехпроцессорным сервером Enterprise 450 от Sun.

Нашу беседу о специфике применения распространенных сетевых решений при построении кластера остается дополнить совершенно неожиданной, но очень полезной информацией. Кажущееся очевидным стремление основывать проект сети кластера исключительно на коммутируемых соединениях, на деле оказывается совсем неочевидным. Впрочем, все зависит от масштаба -- "игрушечные" кластеры с числом вычислителей (ПК), меньшим или равным восьми, целесообразно строить на основе обычных мультиплексоров. Объяснение этому факту вполне очевидно: мультиплексоры работают по принципу "cut-through" -- пакеты "пролетают" через них с минимальной задержкой (менее 1 мкс), коммутаторы же в большинстве своем основаны на принципе "store and forward", что означает дополнительные расходы времени на запись/выдачу пакета (для модели Cisco 5000 эти расходы составляют весомые 45 мкс). Чем это чревато -- было объяснено выше. В масштабных проектах, естественно, применения коммутаторов не избежать, а минимизировать время задержки можно, например, варьируя топологию сети, -- маленькие группы компьютеров строятся на основе мультиплексоров, а объединение групп организовывается полнодуплексным коммутатором, например недорогим из модельного ряда компании Linksys со временем задержки 6 мкс. Стоимость сетевого оборудования для кластера из 64 машин получается буквально копеечной (16 мультиплексоров и один 16-портовый коммутатор), а показатели -- весьма высокими.


Попытка не пытка

Собственно, комбинации любого дистрибутива любой бесплатной версии ОС Unix и дистрибутива PVM уже достаточно для того, чтобы построить "потешный" суперкомпьютер типа реализованного в рамках проекта Acme. Но, как обычно, требуется учесть детали. Во-первых, даже "потешный" кластер -- весьма не игрушечная система по возможностям, и задуматься об эффективности утилизации этих возможностей стоит. Здесь на помощь приходят программы класса CMS (Cluster Management System). Для того чтобы централизовать доступ ко всем вычислителям с одного управляющего рабочего места, нужна некоторая разновидность удобной командной оболочки, позволяющей, например, одной командой активировать группу приложений на разных вычислителях. Наконец, требуется инструментарий для разработки программ. Чтобы не занимать время читателя описанием множества существующих доступных программных продуктов, попадающих в перечисленные классы, автор принял решение... самостоятельно собрать "потешный" кластер -- не пользуясь специально подготовленными дистрибутивами для построения кластерных систем и подбирая программы по собственному усмотрению. К сожалению, ограниченное время на подготовку статьи диктовало свои условия, и многого, того, что хотелось, сделать просто не удалось. И все же...

"Потешный" кластер с кодовым названием СМПН собирался из предоставленных компанией K-Trade ПК с процессорами Celeron 1 GHz и объемом ОЗУ 512 MB, сетевых карт Intel PRO 100/S, предложенных ASBIS, и коммутатора D-Link DES-1218 от Noos2000. В качестве ОС была выбрана FreeBSD версии 4.5, МОС -- PVM v. 3.4.4. Были развернуты три вычислительных и один управляющий узел. Для обеспечения контроля за вычислительными узлами применялся инструментальный набор Clusterit, для управления кластером использовалась комбинация пакетной системы управления заданиями OpenPBS и планировщика с балансировкой загрузки Maui. Все программы устанавливались исключительно методом трансляции и сборки из исходных текстов, для чистоты эксперимента не применялись никакие программные средства, облегчающие или автоматизирующие эти процессы. Экзамен на мобильность программы прошли с оценкой "хорошо" -- в некоторых случаях возникала необходимость прибегнуть к некритическим (можно сказать, косметическим) процедурам внесения изменений в тексты программ. Для всего ПО кластерного назначения была выделена разделяемая с помощью протокола NFS иерархия каталогов, что исключило потребность установки ПО на каждый вычислительный узел. Один из вычислительных узлов был сконфигурирован как самостоятельная рабочая станция с загрузкой с жесткого диска, второй -- как бездисковая станция с удаленной загрузкой. Утилитой NetPIPE были проверены характеристики пропускной способности сети, а утилитой traceroute (входит в стандартную поставку FreeBSD) -- время задержки.

После выполнения подготовительных процедур были установлены еще два варианта МОС -- LAM/MPI и MP_Lite. Для всех трех вариантов МОС были написаны элементарные тестовые программы типа "пинг-понг", непрерывно обменивающиеся сообщениями. Результаты тестирования с помощью этих программ никаких особых сюрпризов не преподнесли: LAM/MPI оказалась незначительно быстрее PVM, а "облегченный" вариант реализации спецификаций MP_Lite показал буквально чудеса скорости, обогнав своих "коллег" на 45%. Использование MP_Lite позволило изучить и очень интересный механизм повышения пропускной способности -- "channel bonding" (объединение каналов), когда отправляемые MP_Lite пакеты делятся пополам, и каждая половинка передается отдельным сетевым адаптером. Реализация channel bonding в MP_Lite оказалась действительно очень качественной, практически в два раза повышающей пропускную способность.

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