47536 (Массивно-параллельные суперкомпьютеры серии Cry T3 и кластерные системы класса BEOWULF), страница 4

2. Принципы построения многопроцессорных вычислительных систем

2.1 Архитектура многопроцессорных вычислительных систем

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

Компьютеры с общей памятью состоят из нескольких процессоров, имеющих равноприоритетный доступ к общей памяти с единым адресным пространством (рисунок 7a).

Рисунок 7. Параллельные компьютеры: с общей памятью – а) и с распределенной памятью – б)

Типичный пример такой архитектуры – компьютеры класса SMP (Symmetric Multi Processors), включающие несколько процессоров, но одну память, комплект устройств ввода/вывода и операционную систему. Достоинством компьютеров с общей памятью является относительная простота программирования параллельных задач, минусом – недостаточная масштабируемость. Реальные SMP-системы содержат обычно не более 32 процессоров, для дальнейшего наращивания вычислительных мощностей подобных систем используется NUMA-технология.

В компьютерах с распределенной памятью (мультикомпьютерные системы) каждый вычислительный узел является полноценным компьютером и включает процессор, память, устройства ввода/вывода, операционную систему и др. (рисунок 7б). Типичный пример такой архитектуры – компьютерные системы класса MPP (Massively Parallel Processing), в которых с помощью некоторой коммуникационной среды объединяются однородные вычислительные узлы. Достоинством компьютеров с распределенной памятью является (почти неограниченная) масштабируемость, недостатками – необходимость применения специализированных программных средств (библиотек обмена сообщениями) для осуществления обменов информацией между вычислительными узлами. Для многопроцессорных вычислительных систем с общей и распределенной памятью используются термины сильно- и слабосвязанные машины соответственно.

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

Рисунок 8. Многопроцессорные системы с общей шиной – а), с матричным коммутатором – б) и с каскадированием коммутаторов (Омега-сеть) – в)

При построении более мощных систем используются более изощренные подходы. Эффективной является схема матричной коммутации (рисунок 8б), при которой устройства связываются между собой двунаправленными переключателями, разрешающими или запрещающими передачу информации между соответствующими модулями. Альтернативой является каскадирование переключателей; например, по схеме Омега-сети (рисунок 8в). При этом каждый переключатель может соединять любой из двух своих входов с любым из двух выходов, для соединения n процессоров с n блоками памяти в этом случае требуется n×log2n/2 переключателей. Недостаток схем с каскадированием коммутаторов – задержки срабатывания переключателей.

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

Рисунок 9. Варианты топологий связи процессоров в многопроцессорных вычислительных системах

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

Топология "решетка" (рисунок 9г) использовалась еще в начале девяностых годов при построении суперкомпьютера Intel Paragon на основе процессоров i860; нахождение минимального пути передачи данных между процессорами A и B для топологии "трехмерная решетка" иллюстрировано на рисунке 10. Топология "двумерный тор" (рисунок 9д) расширяет "двумерную решетку" дополнительными связями, снижающими длину среднего пути (само собой, возможен и "трехмерный тор") и характерна для сетевой технологии SCI. Применяется (рисунок 9e) характеризующаяся наличием связи каждого процессора с каждым трехмерная топология "клика". На рисунке 9з приведен общий вид топологии полной связи всех процессоров между собой; такая топология характеризуется наименьшей длиной среднего пути между процессорами, однако аппаратно практически нереализуема при значительном числе процессоров вследствие катастрофического роста числа связей. Для топологии "гиперкуб" (рисунок 9и) характерна сокращенная длина среднего пути и близость к структурам многих алгоритмов численных расчетов, что обеспечивает высокую производительность. N-мерный гиперкуб содержит 2N процессоров. Двухмерный гиперкуб – это квадрат, трехмерный гиперкуб образует обычный куб, а четырехмерный гиперкуб представляет собой куб в кубе. Для семейства суперкомпьютеров nCube гиперкуб максимальной размерности 13 содержит 8192 процессора, в системе nCube 3 число процессоров может достигать 65536 (16-мерный гиперкуб).

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

Рисунок 10. Нахождение минимального пути для передачи сообщений между процессорами в топологии "трехмерная решетка"

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

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

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

• Стоимость определяется, например, как общее количество линий передачи данных в многопроцессорной вычислительной системе.

Естественным представляется объединение преимуществ систем с общей (относительная простота создания параллельных программ) и распределенной памятью (высокая масштабируемость); решением этого вопроса явилось создание компьютеров с архитектурой NUMA (Non Uniform Memory Access).

В этом смысле классические SMP-компьютеры обладают архитектурой UMA (Uniform Memory Access). При этом применяется механизм (обычно аппаратного уровня – что быстрее), позволяющий пользовательским программам рассматривать всю (физически) распределенную между процессорами память как единое адресное пространство. Примерами NUMA-компьютеров является построенная еще в семидесятых годах и содержащая объединенный межкластерной шиной набор кластеров система Cm и объединяющий 256 процессоров комплекс BBN Butterfly (1981, фирма BBN Advanced Computers).

2.2 Распределение вычислений и данных в многопроцессорных вычислительных системах с распределенной памятью

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

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

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

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

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

2.3 Классификация параллельных вычислительных систем

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

SISD (Single Instruction stream / Single Data stream) – одиночный поток команд и одиночный поток данных; к SISD-классу относятся классические последовательные (фон-Неймановского типа) машины. В таких машинах имеется только один поток (последовательно обрабатываемых) команд, каждая из которых инициирует одну скалярную операцию. В этот класс попадают и машины с технологией конвейерной обработки.

SIMD (Single Instruction stream / Multiple Data stream) – одиночный поток команд наряду со множественным потоком данных. При этом сохраняется один поток команд, но включающий векторные команды, выполняющие одну арифметическую операцию сразу над многими данными. Выполнение векторных операций может производиться матрицей процессоров (как в машине ILLIAC IV) или конвейерным способом (Cray-1). Фактически микропроцессоры Pentium VI и Xeon c набором инструкций MMX, SSE, SSE2 являются однокристальными SIMD-системами.