Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005) (1186026), страница 36
Текст из файла (страница 36)
В этой работе рассмотриммодель полнодуплексной ненаправленной передачи информации методом коммутации сообщений. В такой модели протокол состоит из последовательности шагов, и в течение каждого шага каждый процессорможет посылать (и получать) сообщения от всех своих соседей. Дляорганизации парных обменов требуется определение кратчайших путей в графе.
Известны различные распределенные алгоритмы поискакратчайших путей в двумерных циркулянтных сетях [4, 8–10] и трехмерных циркулянтах с N = O(d2) [4, 11]. Получены алгоритмы трансляционного обмена для двумерных циркулянтов [4, 9] и трехмерныхциркулянтов с N = O(d2) [4]. В работе [5] даны оценки времени трансляционного обмена для циркулянтов вида (N; 1, 2, ..., δ/2) при условии,что вершина может обмениваться сообщениями с k ≤ δ соседями в течение каждого шага.В докладе представлено семейство трехмерных оптимальных циркулянтных сетей с максимальным числом вершин для любого диаметраи аналитическим описанием.
Для этих сетей разработаны эффективныйдинамический алгоритм парной маршрутизации и алгоритм трансляционного обмена, обеспечивающий минимумы времени выполнения и176нагрузки сообщений в сети, полученные в полнодуплексной моделикоммутации сообщений.Оптимальные циркулянтные сети степени 6Максимальное число вершин циркулянтной сети вида (N; 1, s2, s3)[7] с любым диаметром d ≥ 1 равноM(d,3) = 4p3 + 4p2 + 3p + 1, если d ≡ 0 mod 3,4p3 + 12p2 + 15p + 7, если d ≡ 1 mod 3,4p3 + 20p2 + 35p + 21, если d ≡ 2 mod 3и достигается для образующих(s2, s3) = (2p + 1, 4p2 + 2p + 1) или (2p2 + p, 2p2 + 3p + 2),если d ≡ 0 mod 3,(2p2 + 3p + 2, 2p2 + 5p + 4), если d ≡ 1 mod 3,(2p + 3, 4p2 + 14p + 13) или (2p2 + 5p + 4, 2p2 + 7p + 6),если d ≡ 2 mod 3, где p = 2⎣d/3⎦.Отметим, что полученное семейство сетей с числом вершин, равным M(d,3), значительно превосходит по соотношению N/d все ранеенайденные семейства трехмерных циркулянтов (см., например, [2, 3,12]).
В таблице даны описания трехмерных циркулянтных сетей с максимальным числом вершин для диаметров 1 ≤ d ≤ 18.d123456789M(d,3)721551172033335157371027s2, s32, 44, 610, 1616, 2222, 2836, 4646, 5656, 6678, 92s2, s33, 85, 217, 579, 7311, 13313, 157d101112131415161718M(d,3)139318152329294336294431535763717525s2, s392, 106106, 120136, 154154, 172172, 190210, 232232, 254254, 276300, 326s2, s315, 24117, 27319, 38121, 42123, 55325, 601Алгоритм парной маршрутизацииПри организации парных обменов в сети связи требуется решениепроблемы поиска кратчайшего пути между взаимодействующими процессорами. Рассмотрим решение этой проблемы для полученных трехмерных циркулянтных сетей.
Поскольку циркулянт – вершинно-транзитивный граф, то достаточно определить для любой вершины v кратчайший путь между 0 и v. Для вершины v вектор кратчайшего пути177P(v) = (P1, P2, P3), где | Pi |, i = 1, 2, 3, задает число шагов по образующей si (–si) в кратчайшем пути из 0 в v, а знак +(–) – движение по si(–si). Для d ≡ 0 mod 3 рассмотрим семейство оптимальных графов Γ == {(N(p); 1, s2(p), s3(p)), p – четное число}, где N = 4p3 + 4p2 + 3p + 1,s2 = 2p + 1, s2 = 4p2 + 2p + 1.Для любой вершины 0 ≤ v ≤ N графа семейства Γ получен следующийАлгоритм вычисления вектора кратчайшего пути P(v)begina = 0; r = 2p2 + 2p + 1; ∆ = v mod s3;if ∆ > r then {∆ = 2r – ∆; a = 1};i = v div s3; j = ∆ div s2; k = ∆ mod s3 – p – 1;if (p/2 ≤ i + j ≤ 3p/2) and k ≤ –p/2 + i + j) or (i + j > 3p/2)P1then begin P3 = i – p; P2 = j – p; P1 = k; if a = 1 then {P2 = – P2;= – P1}; stop; endP3 = i; if (0 ≤ i + j < p/2) and (k ≤ 0) or (p/2 ≤ i + j ≤ 3p/2) and(k < p/2 – i– j)then begin P2 = j; P1 = k + p + 1; endelse begin P2 = j + 1; P1 = k – p; end;if a = 1 then begin P3 = P3 + 1; P2 = –P2 + 1; P1 = –P1; end;else begin P1 = –k – p – 1; P2 = 1 – j; P3 = i + 1; end; stop;endКак видим, полученный алгоритм не зависит от числа вершин вграфе и имеет сложность O(1).
Он позволяет быстро вычислять в каждой вершине пути между любыми источниками и приемниками сообщений без использования табличного представления сети, помещенного в каждой вершине. Схема алгоритма парной маршрутизации(АПМ) для графов рассмотренного семейства:1. АПМ вычисляет вектор кратчайших путей P в вершинеисточнике сообщения, используя номер вершины-приемника.2. В каждой промежуточной вершине (и вершине-источнике) АПМвыбирает номер выходного направления, принадлежащего кратчайшему пути до вершины-приемника, и вектор P модифицируется так, чтобы модифицированный вектор P ′ задавал остаток кратчайшего пути довершины-приемника.
При этом выбор номера выходного направленияможет учитывать не только нулевые координаты вектора P ′, но такжетекущие состояния смежных вершин и линий связи (отказы, нагрузку).3. АПМ завершается, когда все координаты P ′ равны 0.178Алгоритм трансляционного обменаРассмотрим трансляционный обмен при полнодуплексной моделикоммутации сообщений для оптимальных циркулянтных сетей семейства Γ : требуется организовать передачу сообщений из любого процессора (PE) во все другие за минимальное время и без дублированиясообщений. Последнее требование вызвано необходимостью минимизировать нагрузку в сети при коллективных обменах.
Одно из решенийпроблемы заключается в построении минимального покрывающегодерева с корнем в источнике и передаче копий сообщения только понаправленным ребрам этого дерева. На рисунке слева показана нумерация входных (выходных) полюсов процессора (вершины) и соответствие их образующим графа, справа - дан фрагмент минимального покрывающего дерева (не показаны ребра, соответствующие образующим ±s1) для циркулянтного графа с N = 333 и диаметром 6. Вершинаисточник расположена в центре, стрелки на ребрах указывают направления передач копий сообщения между смежными PE по линиям связи,соответствующим образующим s2 (по горизонтали) и s3 (по вертикали).Структура сообщения для трансляционного обмена: msg:= {T, U,V, W, B}, где T – текст сообщения, U, V, W – счетчики числа шаговмежду PE, выполняющим алгоритм, и PE-источником, по линиям связи, соответствующим трем образующим, B – признак трансляционногообмена.
Если сообщение прибывает в PE первый раз, тогда оно должнобыть принято, в противном случае PE заканчивает алгоритм трансляционного обмена. Это позволяет избежать передач лишних копий сообщения по линиям связи, соответствующим образующим ±s1, и ограничить требуемое число шагов алгоритма диаметром графа. Алгоритмначинает работу в транзитном PE (или PE-источнике) после получениясообщения с признаком B с входа 1–6 (или 0). В транзитном PE параметры Um, Vm, Wm поступившего с входа i сообщения преобразуются впараметры U, V, W для сообщения в выходной очереди.Алгоритм трансляционного обмена в процессоре-источнике.beginU := 0; V := 0; W :=0;for i = 1 to 6 do send msg to output i; stopendАлгоритм трансляционного обмена в транзитном процессоре.beginif msg is received for the first time then send msg to output 0179else begin delete msg from input i; stop end;if i=5 or i=6 then begin U := Um + 1; V := Vm; W := Wm;if U + V + W = d then stop else begin send msg to output i; stop end; endelse if i mod 2=1 then begin U := Um; V := Vm; W := Wm + 1; endelse begin U := Um; V := Vm + 1; W := Wm; end;for k = 5 to 6 do send msg to output k;if (V = 0) or (W = 0 and V < p) then send msg to output (i + 2) mod 4 + 1else if (V + W = d) or (i mod 2 = 1 and W = p) or (i mod 2 = 0 andV = p) then stopelse send msg to output (i + 1) mod 4 + 1; stopendЗаключениеПолучены оптимальные трехмерные циркулянтные сети, которые всвоем классе обладают наилучшими структурными показателями,включая низкую задержку при передаче информации и высокую живучесть (за счет минимизации диаметра), а также имеют простые и эф180фективные алгоритмы маршрутизации, не использующие таблиц маршрутизации.
Построенные алгоритмы обменов инвариантны к числупроцессоров в системе и допускают простые модификации, учитывающие отказы процессоров и линий связи. Полученное семействооптимальных сетей представляет интерес с практической точки зрения,т. к. циркулянтные графы используются в качестве коммуникационныхсетей связи для реальных и проектируемых вычислительных и мультикластерных систем.Литература1. Hwang F.K. A survey on multi-loop networks. Theoretical ComputerScience, 2003, 299, P. 107–121.2. Монахов О.Г., Монахова Э.А.
Параллельные системы с распределенной памятью: структуры и организация взаимодействий, Новосибирск,Изд-во СО РАН, 2000.3. Bermond J.-C., Comellas F., and Hsu D.F. Distributed loop computernetworks: a survey. J. Parallel Distributed Comput., 1995, 24, P. 2–10.4. Liestman A.L., Opatrny J., and Zaragoza M.
Network Properties of Double and Triple Fixed-Step Graphs. Int. J. Found. Comp. Sci., 1998, 9, P. 57–76.5. Comellas F., Mitjana M., Peters J.G. Broadcasting in Small-WorldCommunication Networks. Proc. 9th Int. Coll. on Structural Information andCommunication Complexity, eds. C. Kaklamanis and L. Kirousis. Proceedingsin Informatics, 13, P. 73–85 (2002).6. Muga F.P., and Yu W.E.S. A Proposed Topology for a 192-ProcessorSymmetric Cluster with a Single-Switch Delay. In Proc. of the Philippine Computing Science Conf.
(2002).7. Monakhova E. Optimal Triple Loop Networks with Given TransmissionDelay: Topological Design and Routing. In Proc. of the International NetworkOptimization Conference, (INOC'2003), Evry / Paris, France, 2003, P. 410–415.8. Narayanan L., Opatrny J., Sotteau D. All-to-All Optical Routing inChordal Rings of Degree Four. Algorithmica, 2001, 31(2), P. 155–178.9. Монахова Э.А.
Алгоритмы межмашинных взаимодействий и реконфигурации графов связей в вычислительных системах с программируемойструктурой. Вычислительные системы, Новосибирск, 1982, No. 94, С. 81–102.10. Robic B. and Zerovnik J. Minimum 2-terminal routing in 2-jump circulant graphs. Computers and Artificial Intelligence, 2000, 19(1), P. 37–46.11. Barriere L., Fabrega J., Simo E., Zaragoza M. Fault-Tolerant Routingsin Chordal Ring Networks. Networks, 2000, Vol. 36(3), P. 180–190.12.
Chen S., and Jia X.-D. Undirected loop networks. Networks, 1993, 23,P. 257–260.181СЖАТИЕ НАУЧНЫХ ДАННЫХ БОЛЬШОГО ОБЪЕМАДЛЯ ОБЕСПЕЧЕНИЯ ВОЗМОЖНОСТИ ИХ ВИЗУАЛИЗАЦИИС.В. МуравьевИММ РАН, МоскваВведениеСовременные компьютерные системы позволяют решать довольносложные задачи, возникающие как при численном моделировании, таки при обработке данных, получаемых в научных экспериментах. Получаемые результаты (обычно трехмерные скалярные данные) могут занимать довольно большой объем дискового пространства компьютера.Большой объем данных может создавать существенные проблемы вомногих областях их применения (визуализация, передача данных поузким каналам Интернета, исследование данных в интерактивном режиме и др.) Таким образом, весьма актуальна проблема сжатия подобных данных.В данной работе рассматриваются алгоритмы сжатия данных 2-хтипов. Первый тип данных – это трехмерные поверхности произвольного вида. Исследование поверхностей может потребоваться, например, при изучении изоповерхностей скалярного физического параметра, распределенного в трехмерной объемной области.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
