Технологии высокопроизводительных вычислений

Когда – то давно, во времена малых объемов оперативной памяти и коротких машинных адресов, программисты использовали для работы с большими объемами данных «библиотеки организации виртуальных массивов». Такой массив хранился в файле на жестком диске, и отображался на массив в оперативной памяти порциями в режиме «скользящего окна», по явным запросам прикладной программы. В Global Arrays применяется та же дисциплина, но «виртуальные массивы» не хранятся на жестком диске, а «размазаны» по оперативным памятям вычислительных узлов. Если массив очень большой, то допускается также «размазывание» по оперативным памятям и локальным жестким дискам узлов. Каждый узел работает с массивом, запрашивая отображение (фактически – одностороннее копирование) произвольной части виртуального массива в свою память. Имеются отдельные запросы для явной синхронизации. Некоторым программистам писать программы в этой дисциплине оказалось проще, чем при помощи MPI.

По мере развития коммуникационного оборудования технология односторонних обменов все больше приобретала значение как базовая, то есть как способная абстрагировать для программиста те свойства аппаратуры, которые средствами MPI просто не выразимы. Выше, в разделе, посвященном обзору ориентированных на кластеры сетевых технологий, мы уже говорили о том, что все специализированные кластерные сети поддерживают RDMA – аппаратную реализацию односторонних обменов. Это означает, что сетевая карта вычислительного узла А может отправить запрос сетевой карте узла Б на доступ к памяти Б, физически не «ставя в известность» процессор узла Б об этом доступе. Здесь речь уже не только об удобстве программирования – речь об эффективности. Если бы существовал класс прикладных программ, особенно эффективно использующих именно этот режим работы аппаратуры, то программистам, пишущим такие программы, совершенно необходимо было бы предоставить право этой возможностью пользоваться. Для этого им надо дать библиотеку организации односторонних обменов, уже не в качестве «дополнительного удобства», а в качестве средства адекватного учета свойств оборудования в своих программах.

Сегодня принято считать, что важнейшим классом прикладных программ такого рода являются программы расчетов на неструктурных сетках. При дискретизации расчетной области в численных методах сетки, покрывающие область, вовсе не всегда бывают четырехугольными – очень популярны, например, треугольные сетки. Хранение такой сетки в оперативной памяти – нетривиальная задача. В самом деле, в случае четырехугольной сетки поле величин хранится в двумерном массиве, соседство ячеек выражается в терминах индексов. Например, «верхняя» граница некоторой области – это всегда нулевая строка двумерного массива. «Правый сосед» ячейки – это элемент массива со вторым индексом, на единицу большим, чем у данной ячейки, и т. п. А как быть, если сетка треугольная? В этом случае значения величин в ячейках хранятся в одномерном массиве, значение индекса в котором никак не отражает соседства ячеек. Информация о соседстве хранится в других массивах, тоже одномерных. Если мы захотим выполнить для такого представления сетки нечто подобное параллельной реализации метода Якоби, мы обнаружим, что «буферная зона на границе двух процессоров», которая раньше была строкой двумерного массива, теперь превратилась в совокупность отдельных чисел, весьма причудливо разбросанных по памятям обоих процессоров. Числа эти было бы здорово передать в соседний процессор (или принять из него) по одному, да еще так, чтобы не оба процессора, а лишь один – инициатор обмена – мучительно вычислял, откуда именно что взять и куда именно положить. Задача – в точности для аппаратуры, поддерживающей односторонние обмены. Потом, когда серия обменов закончится, можно и синхронизироваться отдельным запросом из всех взаимодействующих процессоров.

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

В качестве базовой модель односторонних обменов впервые получила сравнительно широкое применение на многопроцессорных вычислительных системах серии Cray T3, в виде библиотеки shmem [3,16]. Это крайне простая, аскетичная библиотека, с развитыми средствами как собственно односторонних обменов, так и специальных режимов синхронизации, вроде ожидания обнуления «чужой» переменной. Возможности библиотеки почти буквально отражают аппаратные возможности коммуникационной системы Cray T3. Крайне остроумно решена проблема расширенной глобальной адресации. Считается, что, поскольку система однородна (все узлы одинаковы и снабжены одной версией ОС), а все исполняемые модули ветвей параллельной программы также одинаковы, то одинаково и распределение адресов статических данных, и в качестве адреса обмена в другом процессоре можно указывать адрес собственной переменной с тем же именем. Например: «Послать мою переменную А в переменную Б на процессоре В».

Библиотека shmem уже много лет является базовым системным средством коммуникаций на всех машинах Cray и Silicon Graphics, несмотря даже на то, что с некоторых пор машины эти приобрели NUMA – архитектуру, то есть прямо адресуемую общую память. Shmem также поддержана в кластерной сети Quadrics.

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

6.5. Модель: NUMA.

Модель NUMA – несимметричной (по времени доступа) прямо адресуемой общей памяти – также может рассматриваться и как базовая (когда такая память есть физически), и как производная (когда она моделируется на более функционально слабом оборудовании для удобства программиста). Говоря о NUMA – компьютерах, часто неявно подразумевают следующие дополнительные свойства реализации:

- асимметрия времени доступа к памяти не очень велика (в пределах одного десятичного порядка),

- вся память в системе является общей, на установке работает единая многопроцессорная операционная система,

- наконец, общность памяти – аппаратная, то есть вся память системы действительно прямо адресуется всеми командами работы с памятью при их выполнении в любом процессоре.

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

Наиболее используемой технологией в стиле NUMA является язык программирования UPC (Unified Parallel C, Унифицированный параллельный C) [17]. Идея этого языка, являющегося расширением C, в главном исключительно проста. Прежде всего, наличие единой операционной системы и единого адресного пространства, включающего в себя все переменные всех процессов, не предполагается. Параллельная программа представляет собой совокупность ветвей – отдельных процессов, каждый – со своим адресным пространством, в точности так, как если бы мы использовали MPI. По умолчанию все переменные, расположенные в ветвях, у каждой ветви свои. При этом некоторым указателям и/или массивам присваивается дополнительный квалификатор «shared» (разделяемый). Он означает, что данный массив (область, адресуемая указателем) «размазан(а)» по памятям процессоров, то есть массив расположен в несимметричной по времени доступа общей памяти. У каждого процесса (процессора) имеется «своя», то есть доступная быстро, часть в каждом таком массиве, а остальные его части, являющиеся «своими» для других процессов, для данного процесса доступны медленно. Прикладному программисту предлагается писать программу таким образом, чтобы обращений к «своей» части  разделяемого массива было гораздо больше, чем к «чужим». На уровне текста программы доступ к разделяемым массивам качественно однороден. Если p – разделяемый массив, то оператор «p[i] = a;» правилен и выполнится в любом случае. Если значение i таково, что p[i] лежит в «своей» для данного процесса части массива, он выполнится быстро, в противном случае – медленно. Такая модель вполне адекватна случаю, когда NUMA реализован аппаратно – пусть не для всей памяти, пусть с очень большой степенью асимметрии по времени доступа, но все же – аппаратно, на уровне процессорных команд. Если же это не так, то есть качественная однородность способов доступа к «своей» и «чужой» памяти реализована программно, средствами транслятора, мы получим такую картину:

l[i] = a; // l – обычный (не shared) указатель

Этот оператор выполняется быстро, и касается, по определению, только локальной (не общей) памяти.

p[i] = a; // p – указатель на shared, то есть на общую память.

Этот оператор выполняется, скажем, в 10 раз медленнее, чем предыдущий, если значение i таково, что мы попали в «свою» память, и в 5000 раз медленнее, если значение i таково, что память «чужая».

Разработчики языка UPC предусматривали возможность его реализации на вычислительных системах, в которой полная аппаратная поддержка NUMA отсутствует. Это выразилось в том, что в языке есть возможность явным образом убрать упомянутое выше 10 – кратное замедление. Язык позволяет написать, например:

l = p + 100;

……..

l[j] = a;

В результате выполнения первого из операторов мы получим «совсем быстрый», то есть локальный, вариант указателя на область, находящуюся в общей памяти. Правда, только на «свою» часть этой области (чудес не бывает). В данном примере требуется, чтобы 100-й элемент массива p находился в «своей» для данного процессора памяти, и 100+j-й элемент – тоже.

Язык UPC обладает многими  положительными свойствами языков программирования в модели общей памяти, на которые обычно ссылаются, противопоставляя способы программирования в системах с общей памятью и без таковой. Важнейшим из таких свойств является возможность пошагового «распараллеливания» программы [3]. Когда у программиста имеется последовательный, однопроцессорный вариант программы, и он начинает строить параллельный вариант при помощи MPI, у него возникает желание делать это, внося изменения в программу постепенно, шаг за шагом, возможно, «распараллеливая» только критические по быстродействию части кода. Но «пропасть нельзя преодолеть в два прыжка». При использовании MPI, например, невозможно отладить сначала посылки сообщений, а потом – их приемы. Также невозможно работать с массивом, как с распределенным, в критическом цикле, и как с «обычным» (ценой быстродействия) – в той части программы, вклад которой в суммарное время выполнения очень мал. Также весьма нелегко постепенно оптимизировать логику распределения данных по процессорам и порядок обменов сообщениями – все это надо продумать заранее, от начала до конца, и отладить, как единое целое.

При использовании UPC, напротив, пошаговое улучшение программы возможно и совершенно естественно. Например, упомянутый выше прием «убирания 10-кратного замедления» можно сначала не включать в разрабатываемый параллельный вариант программы, а затем – включить только в критические циклы.

Конечно, число шагов, которые придется сделать, улучшая программу на UPC по шагам, очень сильно зависит от конкретной реализации UPC. Если базой такой реализации служит NUMA – оборудование – возможно, многих шагов и не потребуется, если сеть Gigabit Ethernet – шагов будет гораздо больше.

В настоящее время доступны две свободно распространяемых в исходных текстах реализации UPC. Поддерживаются разные варианты оборудования, в том числе – специализированные «кластерные» сети. На оборудовании, реализующем RDMA, программы на UPC работают лучше и требуют меньше шагов оптимизации. Имеются также варианты реализации на «обычных» сетях, и даже на базе MPI – совсем медленные.

Конечно, наличием квалификатора «shared» специальные «параллельные» конструкции UPC не исчерпываются. По сравнению с классическим C, имеются также средства барьерной синхронизации, средства согласованной работы с файлами из общедоступной файловой системы, оператор параллельного цикла и многое другое.

Языку UPC в значительной степени аналогичен co-array Fortran [18]. Это – так называемый «Фортран с процессорной размерностью». Массивы, разделяемые между процессами (процессорами), имеют дополнительную – «процессорную» размерность, указываемую в дополнительных квадратных скобках. Например, F(I, j)[K] – элемент двумерного массива, с индексами (I, j), на процессоре K. Как отдельные элементы, так и вырезки из таких массивов (строки, столбцы, прямоугольные области) можно присваивать, перемещая, тем самым, данные между процессами. Имеются средства синхронизации. Стиль программирования совершенно аналогичен принятому в UPC, форма записи не нарушает традиций языка (присваивание строк, столбцов и вырезок уже давно есть в традиционном Фортране).

В целом прослеживается довольно очевидное глубинное родство модели односторонних обменов и модели NUMA. Односторонние обмены – это «почти NUMA», поскольку и в том, и в другом случае мы имеем возможность доступа в память другого процесса без его ведома, без необходимости организации рандеву. Различие лишь в форме записи. Логика организации программы при использовании, скажем, shmem, Global Arrays, в одном случае, или же  UPC или co-array Fortran, в другом, примерно одинакова. Возможности пошаговой разработки, конечно, в случае модели NUMA несколько выше.

Говоря об эффективности программ, написанных на NUMA – ориентированных языках, следует различать два вопроса:

- если аппаратура, на которой реализован язык, хорошо поддерживает эту модель, скажем, представляет собой NUMA или обеспечивает RDMA с очень низкой латентностью, то насколько велик будет выигрыш от использования этих возможностей по сравнению с программой на MPI, в которой их использовать невозможно?

- если аппаратура, на которой реализован язык, плохо поддерживает эту модель (высоколатентная сеть без RDMA), то насколько велик будет проигрыш от использования возможностей, сравнительно дорого «эмулируемых» программно, вместо «честного» кодирования на MPI со всеми вытекающими трудностями для программиста?

Опыт показывает, что реализации UPC на специализированных «кластерных» сетях вполне пригодны на практике, программы довольно часто получаются вполне приемлемого качества и за «терпимое» число шагов оптимизации.

Совсем недавно появилась (правда, в классе коммерческого, лицензионного программного обеспечения) еще одна разработка языка программирования в модели NUMA. Это – продукт Intel под названием Cluster OpenMP [5]. Язык OpenMP [3] (точнее, набор расширений традиционных вариантов C и Фортрана) в течение многих лет использовался для программирования для систем SMP, то есть с физически реализованной полностью общей памятью, однородной по времени доступа для всех процессоров. Специалистам Intel удалось, ценой внесения минимальных изменений в сам язык, сделать его пригодным для модели NUMA, и выполнить соответствующую реализацию на базе сети tcp/ip, то есть для классического кластера, сеть которого не поддерживает даже RDMA, а реальной общей памяти нет и в помине. Насколько это все работоспособно в реальной производственной практике – надо пробовать.