ИТМиВТ - Институт точной механики и вычислительной техники С. А. Лебедева РАН
Институт точной механики и вычислительной техники им. С. А. Лебедева РАН - научно-исследовательский институт в области информационных технологий, вычислительной техники и микроэлектроники
English
Главная страница Контактная информация Карта сайта и поиск
Об институте Решения Проекты Образование

Умножение матриц на суперкомпьютере MERRIMAC

А.Климов

Аннотация

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

При оценке возможностей суперЭВМ обычно используют два рода показателей: по арифметическим устройствам (FLOPs) и по обращениям к распределенной общей памяти.

Спроектированный в Стэнфорде суперкомпьютер MERRIMAC [1] согласно своему проекту имеет производительность 2PFlops. Попытаемся ответить на вопрос: а сможет ли он перемножить две квадратные матрицы размера 1000х1000 за 1 мкс?

Если учитывать только выполняемые арифметические операции, то требуется 2GFlop, что в пересчете на 1 сек как раз и дает 2PFlops. Получается, что может. Но что если учесть доступ к данным? При оценивании будем исходить только из пропускной способности сетей и только по значениям данных. Расходами на передачу адресной информации пренебрежем. Вопрос сводится к оценке объемов информации, передаваемой через коммуникационную сеть.

Рассмотрим умножение матриц блочным методом. Пусть умножаются две матрицы N1 x N0 и N0 x N2. Результат будет размера N1 x N2. Разобьем каждое измерение на K0, K1 и K2 частей соответственно. Для вычислений будем использовать K=K•K•K2 процессорных модулей, соединенных коммуникационной сетью. В модуле номер ‹ k0,k1,k› будет умножаться блок номер ‹ k1,k0 › первой матрицы на блок номер ‹ k0,k› второй матрицы. Результатом будет слагаемое для блока номер ‹ k1,k›выходной матрицы. В каждый модуль должны прийти два входных блока и выйти один выходной. Их размеры — d1xd0, d0xd2 и d1xd2 соответственно, где di = Ni / Ki. Общий поток на один процессорный модуль составит

И тогда на всю систему:


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

Вернемся к нашей задаче. Положим N0 = N1 = N2 = N = 1024. Тогда оценка полного потока упростится до  слов.

Теперь обратимся к суперпроцессору Merrimac. В нем 16K процессорных модулей, по 16 на плате, платы сгруппированы в стойки по 32, всего 32 стойки. Коммутатор на плате имеет пропускную способность (в пересчете на 1 процессорный модуль) 20 GB/s или на всю систему — 320 TB/s. Коммутатор внутри стойки имеет на каждый процессор по 5GB/s, всего — 80TB/s. И наконец, между стойками оптические каналы пропускают общий поток в 40 TB/s (по 2.5 GB/s на процессор).

Для оптимального распределения задачи умножения матриц по процессорам выберем  . Тогда общий объем межпроцессорного трафика будет 10242(16+32+32) слов = 80Mслов = 640MБ, что в пересчете на секунду составит 640ТБ/с. А в наличности есть только 320TБ/с. То есть на уровне процессоров лимит потока превышен вдвое.

Оценим теперь поток между платами. Варианты:  =<4,16,16> или <16,8,8>, что дает от 32 до 36 Мслов, или 256—288 ТБ/с. А в наличии имеется только 80 ТБ/с, то есть превышение лимита почти четырехкратное.

Наконец, на уровне стоек пусть  =<2,4,4>, что дает потребный поток 10 Мслов или 80ТБ/с, при том что есть только 40ТБ/с, а значит опять налицо двукратное превышение.

Сведем все имеющиеся оценки в таблицу:

Уровень Число элементов K Разбиение задачи  Наличная пропускная способность, ТБ/с Потребная пропускная способность, ТБ/с
Плата (board) 16384 (процессора) 16,32,32 320 640
Стойка (cabinet) 1024 (платы) 4,16,16 или 16,8,8 80 256—288
Система (system) 32 (стойки) 2,4,4 40 80

Таким образом, задачу перемножения матриц 1024х1024 при самом оптимальном разбиении на блоки система Merrimac сможет решать самое быстрое за 4 мкс. При этом тормозить будет межплатная сеть внутри стоек, тогда как сети двух других уровней будут загружены лишь наполовину, а FPU — на 25%. (Предполагаем, что каждый процессорный элемент имеет одно FPU, которое на каждом такте выполняет одно сложение или умножение.)

Посмотрим, что будет при других значениях N. С ростом N число операций растет как N3, а межмодульные потоки (при фиксированной схеме распределения) — как N2. Поэтому при N=4000 в предельном режиме будут хорошо загружены как FPU, так и сеть среднего уровня (межплатная). А при N=8000 уже все сети будут работать с 2—4 кратным недогрузом.

Выводы

1. На данной задаче в коммуникационной среде системы Merrimac узким местом является сеть среднего уровня. Для полной сбалансированности, ее пропускную способность следовало бы увеличить вдвое. Это на так много, так что можно сказать, что в целом система коммуникации Merrimac достаточно хорошо сбалансирована, по крайней мере по отношению к задачам типа умножения больших матриц. Аналогичными свойствами обладают и задачи типа разностных схем на трехмерных сетках. Для таких задач для равномерности загрузки сетей их пропускная способность в пересчете на один элемент может убывать с ростом уровня как кубический корень из полного числа элементов соответствующего уровня. (Для двумерных сеток — как квадратный корень). Как, видим, эта асимптотика примерно соответствует тому, что есть в системе Merrimac. (Между прочим, такую же асимптотику можно вывести из предположения, что система строится путем однородного заполнения схемами и каналами трехмерного или двумерного пространства.)

2. Показателем «распараллеливаемости» задачи является не только ширина ее вычислительного графа (число операций, которые могут выполняться параллельно), но и объемы возникающих информационных потоков. Пределы в реализации вычислений могут проистекать не только из ограничений по производительности арифметических устройств и латентности (задержек) при передаче данных, но и из пропускной способности (bandwidth) коммуникационной сети. Важно уметь оценивать свойство алгоритмов оказывать давление на сеть и оптимизировать их с этой точки зрения.

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

4. При оценивании предельных возможностей коммуникационных сетей часто используют понятие бисекционной пропускной способности. Она отражает способность сети выдерживать нагрузку по передаче определенного объема информации от одной половины системы к другой при наименее выгодном разбиении системы на две части примерно равного объема (то есть таком разбиении, при котором оцененная пропускная способность будет наименьшей). Для оценивания предельных возможностей оптимизации параллельных алгоритмов с точки зрения создаваемой ими коммуникационной нагрузки на сеть полезно ввести понятие бисекционной (коммуникационной) сложности. Это объем информации, передаваемый между двумя половинами вычислительного графа алгоритма при наиболее выгодном (с точки зрения минимизации этого объема) его разрезании на две примерно равные части. Для задачи умножения матриц размера NxN блочным методом бисекционная сложность равна O(N2). (Для сравнения: бисекционная коммуникационная сложность сложения двух матриц равна нулю.) Эта характеристика устанавливает пределы для оптимизации алгоритма с точки зрения создаваемой им нагрузки на коммуникационную сеть, а также необходимые требования к аппаратуре, обеспечивающей его эффективное выполнение.

  1. Dally,W. et al, Merrimac: Supercomputing with streams. http://merrimac.stanford.edu/publications/sc03_merrimac.pdf
  2. Henry Hoffmann, Volker Strumpen, Anant Agarwal. Stream Algorithms and Architecture. Laboratory for computer science, Massachusetts Institute of Technology, Technical Memo, MIT-LCS-TM-636, March 26, 2003, 46 pp.

 

© 1948—2016 «ИТМиВТ»
Версия для печати Контактная информация