Optimization of collective communication algorithms for hierarchical distributed computer systems.pdf Начиная с середины 1960-х годов распределенные вычислительные системы(ВС) активно используются как инструментальные средства решения сложных за-дач в различных отраслях науки и техники. В архитектурном плане распределен-ная ВС [1, 2] представляется композицией множества взаимодействующих эле-ментарных машин (оснащенных средствами коммуникаций и внешними устрой-ствами) и сети межмашинных связей. Элементарная машина (ЭМ) - это основнойфункциональный и структурный элемент ВС; конфигурация ЭМ допускает варьи-рование в широких пределах - от процессорного ядра до ЭВМ. Все основные ре-сурсы распределенных ВС (арифметико-логические устройства, память, средствауправления и коммуникаций) являются логически и технически рассредоточен-ными. Число ЭМ в распределённых ВС допускает варьирование от несколькихединиц до сотен тысяч.Параллельные алгоритмы и программы для распределенных ВС преимущест-венно разрабатываются в модели передачи сообщений (Message Passing). В этоймодели ветви параллельной программы взаимодействуют друг с другом путемобменов информационными сообщениями по каналам межмашинных связей ВС.Выделяют два типа обменов информацией между ветвями параллельных про-грамм [1, 2]: дифференцированный (point-to-point) и коллективные (collective) об-мены. При дифференцированном обмене осуществляется передача информациииз одной ветви в любую другую ветвь. Коллективные обмены подразделяются нанесколько видов: трансляционный (ТО, One-to-all Broadcast), трансляционно-циклический (ТЦО, All-to-all Broadcast) и коллекторный обмены (КО, All-to-oneReduce). При трансляционном обмене данные из одной ветви передаются во всеостальные; при трансляционно-циклическом обмене информация из ветвей пере-дается каждой ветви и принимается из всех; коллекторный обмен подразумеваетприем информации из всех ветвей в одну.Анализ использования в параллельных алгоритмах и программах схем обме-нов информацией показывает, что до 80 % времени обменов приходится на кол-лективные операции [3]. Как правило, количество обращений в алгоритмах и про-граммах к коллективным операциям обменов имеет функциональную зависимостьот размера входных данных и в среднем находится в интервале от 101 до 104.В настоящее время в коммуникационных библиотеках стандарта MPI и систе-мах параллельного программирования (в частности, в модели PGAS - PartitionedGlobal Address Space) для реализации коллективных обменов используются алго-ритмы рассылки данных по кольцу, рекурсивного сдваивания, алгоритмДж. Брука (J. Bruck) и алгоритмы, упорядочивающие ветви в деревья различныхвидов [4]. Перечисленные алгоритмы характеризуются различным временем вы-полнения и опираются на предположение об однородности каналов связи междуЭМграммы, а ребрам - информационные обмены между ними. Вес dij ребра в графеотражает объем данных, переданных по нему при реализации алгоритма. Объемыданных, передаваемых между ветвями параллельной программы при реализацииТЦО алгоритмами рекурсивного сдваивания и Дж. Брука, различны. По этой при-чине время реализации ТЦО рассматриваемыми алгоритмами в иерархическихраспределенных ВС зависит от того, как ветви параллельной программы распре-делены по элементарными машинам системы. Рассмотрим модель иерархическойорганизации распределенных ВС.2. Модель распределенных ВС с иерархической структуройРаспределенная вычислительная система с иерархической структурой, уком-плектованная N однородными ЭМ, может быть представлена в виде дерева, со-держащего L уровней [6, 7]. Каждый уровень системы образован отдельным ви-дом функциональных модулей (например, телекоммуникационные шкафы, вы-числительные узлы и т. п.), которые объединены каналами связи своего уровня.Введем следующие обозначения: tl(m) - время передачи сообщения размеромm байт между парой элементарных машин ВС через каналы связи уровняl  {1, 2, …, L}; bl - максимальное значение пропускной способности каналовсвязи на уровне уровня l; z(p, q) - номер уровня функционального модуля, яв-ляющегося ближайшим общим предком для ЭМ p, q  {1, 2, …, N}, иначе говоря,номер уровня, через который они взаимодействуют.Вычислительные системы, представленные в списке TOP500 (35-я редакция),имеют как минимум два уровня в иерархической организации - сеть связи междувычислительными узлами и их общую память.На рис. 1 показано время передачи данных через каналы связи различныхуровней между ЭМ кластерных ВС: кластера Центра параллельных вычислитель-ных технологий ГОУ ВПО «Сибирский государственный университет телеком-муникаций и информатики» (ЦПВТ ГОУ ВПО «СибГУТИ») и кластера Информа-ционно-вычислительного центра ГОУ ВПО «Новосибирский государственныйуниверситет» (ИВЦ ГОУ ВПО «НГУ»).Время передачи данных между ЭМ в иерархических ВС сокращается с умень-шением номера уровня, через каналы связи которого они взаимодействуют. В тоже время, в зависимости от конфигурации распределенной ВС, могут существо-вать интервалы размеров сообщений, для которых последнее утверждение не вы-полняется. Например (рис. 1, б), для сообщений с размерами m > 222 байт. Рас-смотрим особенности реализации ТЦО в иерархических распределенных ВС.3. Реализации ТЦО в иерархических распределенных ВСОбозначим через xi  {1, 2, …, N} номер ЭМ, на которую распределена ветвьi {0, 1, …, n - 1} программы; h - количество функциональных модулей уровня L(вычислительных узлов), выделенных для реализации программы; ; q1,q2,...,qh -номера выделенных функциональных модулей; sr - количество ЭМ функциональ-ного модуля qr, выделенных для реализации программы, r  {1, 2, …, h}.На рис. 2 приведен пример реализации ТЦО алгоритмом Дж. Брука на вычис-лительном кластере с иерархической организацией. Время выполнения алгоритмас распределением ветвей по ЭМ стандартными средствами библиотеки MPI(MPICH2 1.2.1) составило 567 мкс, а время реализации с учетом графа алгоритмаи иерархической организации кластерной ВС - 324 мкс.t, мс24 28 212 216 220 байт22 24 26 28 210 21201020t, мксбайтРис. 1. Время передачи данных между элементарными машинамикластерной ВС через общую память вычислительного узла и сетьмежузловых связей: а - кластер ЦПВТ ГОУ ВПО «СибГУТИ»;б - кластер ИВЦ ГОУ ВПО «НГУ»; - разделяемая память;- сеть Gigabit Ethernet; - сеть InfiniBand 4x DDRПричиной сокращения времени выполнения ТЦО в 1,75 раз (рис. 2, б) являетсяраспределение ветвей, обменивающихся большими объемами данных, на одинвычислительный узел, в рамках которого они взаимодействуют через его общуюпамять. Учитывая последнее, разработаны метод и алгоритмы реализации ТЦО виерархических распределенных ВС.Накладные расходы на реализацию ТЦО с заданным распределениемX = (x0, x1, …, xn - 1) параллельных ветвей по ЭМ системы и заданным информаци-онным графом G = (V, E) алгоритма могут быть выражены как сумма T(X) временпередачи данных между ветвями программы1 1( , )0 0( ) i jn nij z x xi jT X d b− −= == ƒ ƒ ,где dij - вес ребра в графе алгоритма, а bz(xi,xj) - пропускная способность каналовсвязи на уровне z(xi, xj), через которые взаимодействую ветви i и j.В основе разработанного метода лежит процедура распределения параллель-ных ветвей программы, обменивающихся большими объемами данных при реали-зации ТЦО заданным алгоритмом, на ЭМ одного функционального модуля. Этообеспечивает локализацию взаимодействий ветвей через каналы связи функцио-нального модуля и, как следствие, сокращение времени информационных обме-нов. Например, при реализации ТЦО алгоритмом Дж. Брука суммарный объемданных, передаваемых между ветвями 0, 2, 4 и 6, больше объема данных, отправ-ляемых другим ветвям, поэтому распределение этих ветвей на один вычислитель-ный узел (рис. 2, б) обеспечило их взаимодействие через общую память узла и со-кращение времени реализации ТЦО.Сеть Gigabit EthernetРазделяемая памятьЯдро ЯдроПроцессорЯдро ЯдроПроцессорРазделяемая памятьЯдро ЯдроПроцессорЯдро ЯдроПроцессор1) 4 5 6 7 0 1 2 3а0 2 4 6 1 3 5 7Сеть Gigabit EthernetРазделяемая памятьЯдро ЯдроПроцессорЯдро ЯдроПроцессорРазделяемая памятьЯдро ЯдроПроцессорЯдро ЯдроПроцессор2)бРис. 2. Реализация ТЦО алгоритмом Дж. Брука на кластернойВС (n = 8; m = 2048; L = 2): а - реализация ТЦО с распределе-нием ветвей стандартным алгоритмом библиотеки MPI;б - реализация ТЦО с учетом иерархической организации ВСМетод подразумевает (суб)оптимальное распределение ветвей по ЭМ и реали-зацию ТЦО в соответствии с ним. Рассмотрим основные шаги метода, осуществ-ляемые до реализации ТЦО.1. Формируется взвешенный информационный граф G = (V, E) алгоритма реа-лизации ТЦО для m = 1 с количеством вершин n.2. Строится разбиение R = (r0, r1, …, rn - 1) информационного графа G = (V, E)на h непересекающихся подмножеств V1, V2, …, Vh с целью минимизации суммар-ного веса рёбер, инцидентных различным подмножествам разбиения. Черезri  {1, 2, …, h} обозначен номер подмножества разбиения, к которому отнесенавершина i  V . Количество элементов в подмножестве Vu должно быть равно за-данному числу su, u = 1, 2, …, h. Параметры h и su определены ранее.3. Ветвям с номерами из подмножества Vu назначаются номера ветвей, распре-деленных на элементарные машины функционального модуля qu, u = 1, 2, …, h.Таким образом, строится взаимно однозначное отображение ƒ(i), которое сопос-тавляет исходным номерам 0, 1, …, i, …, n - 1 ветвей новые номераƒ(0), ƒ(1), …, ƒ(n - 1). Через ƒ−1(i) обозначим отображение, обратное к ƒ(i).На рис. 3 показано применение описанного метода для алгоритма Дж. Брука накластерной ВС с иерархической структурой.V1V2аСеть Gigabit EthernetРазделяемая памятьЯдро ЯдроПроцессорЯдро ЯдроПроцессорРазделяемая памятьЯдро ЯдроПроцессорЯдро ЯдроПроцессор4 5 6 7 0 1 2 36 2 7 3 4 0 5 1iπ(i)бРис. 3. Пример оптимизации алгоритма Дж. Брука (L = 2;n = 8; h = 2; s1 = 4; s2 = 4): а - приближенное разбиение графаалгоритма Дж. Брука на подмножества V1 и V2; б - отображе-ние ƒ(i) номеров ветвей программыАлгоритмы рекурсивного сдваивания и Дж. Брука требуют модификации дляреализации ТЦО с заданным распределением (отображениями ƒ(i) и ƒ−1(i)) ветвейпо ЭМ. В исходных алгоритмах каждая ветвь i располагает сообщением ai, но всоответствии с полученным распределением ветвь должна осуществлять ТЦО подновым номером ƒ(i). Предложим версии алгоритмов рекурсивного сдваивания иДж. Брука, обеспечивающие реализацию ТЦО с заданными распределениями вет-вей по ЭМ.Алгоритм Bruck exch. Ветвь i передает свое сообщение ai ветви ƒ−1(i),принимает от ветви ƒ(i) сообщение и делает его начальным. На шагеk = 0, 1, …, ⎡log2n⎤ - 1 ветвь i передает все принятые сообщения ветвиƒ−1((i' - 2k + n) mod n) и принимает сообщения от ветви ƒ−1((i' + 2k) mod n), гдеi' = ƒ(i). Далее каждая ветвь циклически сдвигает сообщения вниз на i' позиций.Алгоритм Bruck reorder. На шаге k = 0, 1, …, ⎡log2n⎤ - 1 ветвь i передает всепринятые сообщения ветви ƒ−1((i' - 2k + n) mod n) и принимает сообщения от вет-ви ƒ−1((i' + 2k) mod n), где i' = ƒ(i). Далее каждая ветвь переставляет сообщение изпозиции j = 0, 1, …, n - 1 в позицию ƒ−1((j + i') mod n).Алгоритм recursive doubling exch. Ветвь i передает свое сообщение ai ветвиƒ−1(i), принимает от ветви ƒ(i) сообщение и делает его начальным. На шагеk = 0, 1, …, log2n - 1 ветвь i и ƒ−1(i ⊕ 2k) обмениваются принятыми 2k сообщениями.Алгоритм recursive doubling reorder. Ветвь i сдвигает свое сообщение ai из по-зиции i в позицию ƒ(i). На шаге k = 0, 1, …, log2n - 1 ветвь i и ƒ−1(i ⊕ 2k) обмени-ваются ранее принятыми 2k сообщениями. Далее каждая ветвь переставляет со-общение из позиции j = 0, 1, …, n - 1 в позицию ƒ−1(j).Формирование, разбиение графа и построение отображений ƒ(i) и ƒ−1(i) осу-ществляется единожды при создании подсистемы ЭМ (например, при созданиикоммуникаторов в библиотеках стандарта MPI). После этого построенные ото-бражения многократно используются для реализации ТЦО. Все шаги метода эф-фективно реализуемы в параллельном виде на подсистеме ЭМ, выделенной дляреализации программы. Также допустима организация распределенного храненияинформационного графа на ЭМ системы. На протяжении всего времени выполне-ния программы ветвям требуется лишь информация об отображении смежных сними ветвей. Последнее, для алгоритмов рекурсивного сдваивания и Дж. Брука,требует хранения каждой ветвью в памяти порядка 2⎡log2n⎤ байт. Сказанное вышеобеспечивает применимость метода для большемасштабных распределенных ВС.4. Экспериментальное исследование алгоритмовРазработанный метод реализован в коммуникационной библиотеке TopoMPI,созданной и развиваемой ЦПВТ ГОУ ВПО «СибГУТИ» совместно с лабораториейвычислительных систем Института физики полупроводников им. А.В. РжановаСО РАН. В библиотеке используется интерфейс профилирования стандарта MPIдля перехвата обращений к функциям коллективных операций информационныхобменов, остальные вызовы передаются системной библиотеке MPI (MPICH2,OpenMPI и др.). Построение отображений номеров ветвейтован 64 двухпроцессорными узлами Hewlett-Packard BL460c с четырехъядерны-ми процессорами Intel Xeon 5355. Первый уровень коммуникационной среды кла-стера - сеть связи стандарта InfiniBand 4x DDR, второй уровень - общая памятьвычислительных узлов.На кластере ЦПВТ ГОУ ВПО «СибГУТИ» пакет TopoMPI компилировался сбиблиотекой стандарта MPI - MPICH2 1.2.1 в операционной системе CentOS 5.2x86-64, а на кластере ИВЦ ГОУ ВПО «НГУ» - в операционной системе SUSELinux Enterprise Server 10 SP1 x86-64 с библиотекой OpenMPI 1.2.5.На рис. 4 показано время формирования, разбиений информационных графовалгоритмов и создание отображений ƒ(i), ƒ−1(i) на процессоре Intel Xeon E5420.Видно, что время, затрачиваемое на формирование отображений номеров ветвей,незначительно. Время же разбиения информационного графа алгоритмаДж. Брука с количеством вершин n = 1048576 на h = 131072 подмножеств состав-ляет 32,73 с. Поэтому для большемасштабных ВС востребованы параллельные ал-горитмы формирования и разбиения графов и создания отображений.00,20,40,60,8t, с20000 40000 60000 nРис. 4. Зависимость времени разбиения информационныхграфов на h подмножеств от количества n вершин: -граф алгоритма Дж. Брука, h = 128; - граф алгорит-ма Дж. Брука, h = 256; - граф алгоритма Дж. Брука,h = 512; - граф алгоритма рекурсивного сдваивания,h = 128; - граф алгоритмаРис. 5. Зависимость времени ТЦО от размера m сообщения на кластер-ной ВС ЦПВТ ГОУ ВПО «СибГУТИ» (n = 64; h = 8; s1 = s2 = … = s8 = 8):- алгоритм Дж. Брука; - алгоритм Bruck exch.; -алгоритм Bruck reorder; - алгоритм рекурсивного сдваивания;- алгоритм recursive doubling exch.; - алгоритма recursivedoubling reorder0 2 4 6 8 10 12 m, кбайт20016040801203 5 7 9 11 13 150246Рис. 6. Зависимость коэффициента ускорения алгоритмов ТЦО от разме-ра m передаваемого сообщения на кластерной ВС ЦПВТ ГОУ ВПО«СибГУТИ» (n = 64; h = 8; s1 = s2 = … = s8 = 8): а - ускорение алгоритмовна коротких сообщениях; б - ускорение алгоритмов на длинных сообще-ниях; - алгоритм Bruck exch.; - алгоритм Bruck reorder;- алгоритм recursive doubling exch.; - алгоритма recursivedoubling reorderНа рис. 6 приведены значения коэффициентов ускорения созданных алгорит-мов при передаче коротких и длинных сообщений относительно алгоритмов ре-курсивного сдваивания и Дж. Брука. Ускорение в 130 - 180 раз на коротких со-общениях объясняется тем, что при реализации ТЦО сообщениями размером1 кбайт осуществляется обмен блоками 1, 2, 4, 8, 16 и 32 кбайт, время передачикоторых через сеть связи Gigabit Ethernet и общую память узла отличается в 10 -55 раз (рис. 1, а).Ускорение алгоритмов реализации ТЦО между 64 параллельными ветвями накластерной ВС ИВЦ ГОУ ВПО «НГУ» (рис. 7) наблюдается только для сообще-ний размеров 256 байт - 128 кбайт. Это объясняется тем, что при передаче сооб-щений размеров больше 222 байт сеть InfiniBand (рис. 1, б) превосходит общуюпамять узла по времени передачи данных.2 4 6 8 10 12 m, кбайт0,81,21,62Рис. 7. Ускорение алгоритмов на кластерной ВС ИВЦ ГОУ ВПО «НГУ»(n = 64; h = 8; s1 = s2 = … = s8 = 8): а - время ТЦО короткими сообще-ниями; б - коэффициент ускорение алгоритмов на коротких сообщениях;- алгоритм Дж. Брука; - алгоритм Bruck exch.; -алгоритм Bruck reorder; - алгоритм рекурсивного сдваивания;- алгоритм recursive doubling exch.; - алгоритма recursivedoubling reorderСозданные алгоритмы целесообразно применять для реализации ТЦО сообще-ний таких размеров, для которых время их передачи через каналы связи вышеле-жащих уровней превосходит время обменов через каналы связи нижележащихуровней.ЗаключениеПредложенный метод позволяет оптимизировать алгоритмы коллективныхобменов информацией между ветвями параллельных программ приисходными алгоритмами. Накладные расходы на оптимизацию незначительны икомпенсируются сокращением времени при многократном обращении к функци-ям реализации ТЦО.

Скачать электронную версию публикации