557_Obrabotka_informatsii_i_matematicheskoe_modelirovanie_2014_

Проведено моделирование алгоритмов на мультикластерной ВС Центра параллельных вычислительных технологий ФГОБУ ВПО “СибГУТИ”. Использовались кластерные ВС Jet (18 узлов,2 x Intel Xeon E5420, сеть Gigabit Ethernet, 144 процессорных ядра) и Oak (6 узлов, 2 x Intel Xeon E5620, сеть Infiniband QDR, 48 процессорных ядер). В докладе проводится сравнение алгоритмов прогнозирования для различных моделей информационных обменов и технологий коммуникационных сетей.

3.T. Hoefler, T. Mehlan, A. Lumsdaine, W. Rehm. Netgauge: A Network Performance Measurement Framework // HPCC’07. – 2007. – P. 659-671.

4.Q. Snell, A. Mikler, J. Gustafson. Netpipe: A Network Protocol Independent Perfomance Evaluator // IASTED International Conference on Intelligent Information Management and Systems. – 1996. – 6p.

5.R. Hockney. The communication challenge for MPP: Intel Paragon and Meiko CS-2 //ParallelComputing. – 1994. – Vol. 20. –P.389-398

6.T. Hoefler, T. Schneider, A. Lumsdaine. LogGOPSim – Simulating Large-Scale

Applications in the LogGOPS Model // HPDC’10. – 2010. – P. 597-604.

АЛГОРИТМЫ ОПТИМИЗАЦИИ ВЫЧИСЛЕНИЙ

НА СПЕЦИАЛИЗИРОВАННЫХ УСКОРИТЕЛЯХ В MPI-ПРОГРАММАХ8

Пазников А.А., Яковлев Р.А. СибГУТИ, Новосибирск

e-mail: xehxtkf@gmail.com, тел.: 8960-798-56-99

Современное состояние развития распределённых вычислительных систем (ВС) характеризуется парадигмой мультиархитектуры, большемасштабностью, иерархической топологией коммуникационных сред [1]. Вычислительные узлы часто представляют собой композицию многоядерных процессоров и специализированных ускорителей (графических процессоров, многоядерных сопроцессоров, ПЛИС-ускорителей). Преобладающей при разработке параллельных программ для таких систем является модель передача сообщений (библиотеки MPI) в композиции с инструментарием для реализации вычислений на специализированных ускорителях (NVIDIA CUDA, OpenCL,

OpenACC, OpenMP).

На сегодняшний день существуют библиотеки MPI (MVAPICH, MPI-ACC, Open MPI), эффективно реализующие информационные обмены между ЭМ,

8 Работа выполнена при поддержке РФФИ (гранты № 12-07-00145, 13-07-00160) и Совета при Президенте РФ (грант МД-2620.2014.9)

91

укомплектованными специализированными ускорителями. При реализации передачи информации между GPU в этих библиотеках данные могут быть непосредственно переданы между ускорителями (технологии Unified Virtual Addressing, NVIDIA GPUDirect), при этом реализуется конвейеризация передачи данных [2-4].

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

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

ВС состоит из множества C = {1, 2, …, N} элементарных машин. Обозначим A C – множество ЭМ, оборудованных специализированными ускорителями. Пусть P = {1, 2, …, M} – множество процедур в параллельной программе для запуска на ускорителях. Известно значение функции f(p, a) времени выполнения процедуры p P на ускорителе a A. В функции f учитывается производительность ускорителей и каналов связи. В соответствии с предлагаемым алгоритмом, при отправке вычислительной процедуры выбирается ускоритель a с минимальным значением функции f. Таким образом обеспечивается равномерная загрузки ЭМ (рисунок).

Рисунок – Оптимизация выполнения MPI-программ с использованием ускорителей

92

Разработанные алгоритмы реализованы в программном пакете, который включает в себя модули диспетчера и монитора. MPI-ветвь отправляет запрос диспетчеру, который оценивает значение f и определяет ЭМ k для выполнения вычислительной процедуры. Монитор выполняет опрос состояния ускорителей.

Проведены эксперименты на мультикластерной ВС Центра параллельных вычислительных технологий ФГОБУ ВПО “СибГУТИ”. Было задействовано три сегмента кластерной ВС Jet, укомплектованных графическими процессорами NVIDIA GTX 680, GTX 650 и 2 х GTX 250. Использовались библиотеки OpenMPI 1.7.2, NVIDIA CUDA 5.5 и средства мониторинга NVIDIA. В качестве тестовых задач были выбраны параллельные программы, реализующие различные численные методы. В докладе представлены результаты моделирования, приведено сравнение со стандартными средствами библиотек MPI.

Литература 1. Хорошевский В.Г. Распределённые вычислительные системы с

программируемой структурой // Вестник СибГУТИ. – 2010. – № 2. – С. 3-41.

2.A.M. Aji, S.S. Panwar, F. Ji, M. Chabbi [et al]. On the Efficacy of GPU-Integrated MPI for Scientific Applications //ACM HPDC. – 2013. – P. 17–21.

3.H. Wang, S. Potluri, M. Luo, A.K. Singh, S. Sur, D.K. Panda. MVAPICH2-GPU: optimized GPU to GPU communication for InfiniBand clusters // Computer Science - Research and Development. – 2011. – Vol. 26. – P.257-266.

4.J. Kraus. An Introduction to CUDA-Aware MPI [Электронный ресурс] /

NVIDIA Developer Zone. – 2013. – Режим доступа: http://devblogs.nvidia.com/ parallelforall/introduction-cuda-aware-mpi/.

АНАЛИЗ СТАТИСТИЧЕСКИХ ДАННЫХ ОБ ОТКАЗАХ В КЛАСТЕРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ9

Пименов Е.С., Поляков А.Ю. СибГУТИ, ИФП СО РАН, Новосибирск

e-mail: evgeny.s.pimenov@gmail.com, artpol@isp.nsc.ru

Распределенные вычислительные системы (ВС) являются основным инструментом высокопроизводительной обработки информации. Современные ВС большемасштабны, они формируются из 105 – 106 вычислительных ядер, а их производительность достигает десятков PFLOPS [1]. При этом ВС – сложные технические комплексы, для организации отказоустойчивого функционирования которых требуется анализ и постоянное совершенствование применяемых архитектурных и алгоритмических решений.

Согласно статистическим исследованиям [2], основными причинами возникновения отказов в ВС являются аппаратурные ошибки вычислительных узлов. В 2005 году национальной лабораторией Лос-Аламоса (США) были

9Работа выполнена при поддержке РФФИ (гранты №12-07-00019, 12-07-00106, 12-07-00145)

93

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

Также для исследователей доступны данные, собранные в университете Западного Сиднея. Репозиторий Failure Trace Archive (FTA) [3] содержит данные о функционировании различных распределенных систем. В открытый доступ предоставлены инструменты для анализа и моделирования на основе собранной статистики.

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

Созданный инструментарий поддерживает несколько форматов входных данных: оригинальный формат статистики Лос-Аламоса, а также формат FTA. Выполнена проверка корректности HPCStatTool путем сравнения вычисленных характеристик с опубликованными данными. Анализ всех систем Лос-Аламоса показывает, что некоторые выводы, сделанные в [2], справедливы не для всех архитектур ВС. Также проведен дополнительный анализ высокопроизводительных ВС, представленных в FTA.

Литература

1.TOP500 [Электронный ресурс] // Режим доступа: http://www.top500.org/.

2.Schroeder, B. A large-scale study of failures in high-performance computing systems / B. Schroeder, G. A. Gibson // Proceedings of the International Conference on Dependable Systems and Networks. – Washington DC, USA: IEEE Computer Society, 2006. – P. 249 – 258.

3.Javadia, B. The Failure Trace Archive: Enabling the Comparison of Failure Measurements and Models of Distributed Systems / B. Javadia, D. Kondob, A. Iosup,

D. Epema // Journal of Parallel and Distributed Computing. – 2013. – Vol. 73, Iss. 8. – P. 1208 – 1223.

94

КУМУЛЯТИВНОЕ ОЦЕНИВАНИЕ ХАРАКТЕРИСТИК НАДЁЖНОСТИ КОММУНИКАЦИОННЫХ СЕТЕЙ ДЛЯ УСКОРЕНИЯ ПРИНЯТИЯ РЕШЕНИЙ

Родионов А.С.

СибГУТИ, ИВМиМГ СО РАН, Новосибирск e-mail: alrod@sscc.ru, тел.: (383) 332-69-49

При принятии решения о надёжности (ненадёжности) сети по тому или иному показателю R (для определённости считаем, что большему значению R соответствует бóльшая надёжность и что значение показателя неотрицательно), задаётся некое пороговое значение α и, если R> α, то делается вывод о надёжности сети, иначе – о её ненадёжности. Этот совершенно очевидный метод может быть неэффективным при невозможности быстрого вычисления R. Например, точное вычисление таких широко используемых показателей как вероятность связности заданного подмножества узлов сети (k-terminal reliability) [1] и средняя вероятность связности пары узлов сети (average pairwise network connectivity, APNC) [2,3], представляет собою NP-трудную задачу [4]. Применение же приближённых алгоритмов, в частности метода Монте-Карло, несёт в себе опасность ошибок как первого, так и второго рода в принятии решений.

Возможно использование полиномиально вычислимых верхних и нижних оценок, UR и LR, соответственно (они известны, например, для вероятности связности пары узлов или всех узлов сети с ненадёжными каналами, выходящими из строя независимо [5]). Тогда если LR>α(UR<α), то решение о надёжности (ненадёжности) сети принимается однозначно. Однако весьма вероятен вариант LR<α<UR, при котором принять решение невозможно.

Вон (Won) и Каррей (Carrey) в работе [6] предложили на примере всетерминальной связности (all-terminal reliability, ATR) использовать кумулятивные оценки надёжности, получаемые в ходе использования метода точного вычисления соответствующего показателя. Применение этого подхода возможно в том случае, когда значение показателя уточняется монотонно в ходе расчёта, постепенно увеличиваясь от минимально возможного (Rmin, равно 0 для определённости) или уменьшаясь от максимально возможного показателя (Rmax) вплоть до достижения точного результата. Авторам [7] удалось для нескольких алгоритмов вычисления ATR, в которых этот показатель монотонно накапливается и тем самым даёт растущее значение LR, получить одновременно монотонно убывающее значение UR. В [7] приведены приёмы ускорения расчёта кумулятивных оценок ATR, в [8] показано, как этот подход можно применить к построению кумулятивных оценок APNC.

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

В качестве модели сети используем случайный n-вершинный m-рёберный граф G с независимыми отказами рёбер. Считаем, что показатель надёжности R есть среднее значение соответствующей функции F на реализациях G:

95

где Г есть множество всех возможных реализаций графа G.

Пусть получены значения показателя F для некоторых реализаций графа H1,H2,...,Hk с вероятностями реализаций P1,P2,...,Pk. Тогда в худшем случае для всех остальных реализаций значение показателя равно 0, а в лучшем Rmaxи, таким образом,

(2)

Если перечислять варианты разрушения сети в порядке количества удалённых рёбер, то выражение (1) трансформируются в

(3)

где Hij – j-ый вариант разрушения в графе ровно i рёбер. Как e в этом случае обозначено ребро, pe – вероятность его присутствия (работоспособности). Расчитывая аналогичным образом вероятность реализации графа из (2) получаем

(4)

В работе [8] рассматривается иной порядок перечисления реализаций (разрушений) графа, реализующий дерево разбора по состояниям отдельных рёбер. Соответствующий метод носит название метода факторизации, часто его называют также методом Мура-Шеннона и методом ветвления. Метод основан на применении формулы полной вероятности по отношению к присутствию произвольно выбранного ребра:

(5)

Здесь G/e есть граф G, в котором ребро e присутствует с вероятностью 1 (для многих показателей это соответствует стягиванию его оконечных вершин), а G\e – граф G с удалённым ребром e. Рекурсивный процесс продолжается до получения графа, для которого показатель может быть рассчитан непосредственно. Легко видеть, что при отсутствии применения каких-либо вспомогательных методов редукции размерности и/или декомпозиции и расчёте только финальных вариантов графа приходим к формуле (1). Вместе с тем возможность «отсечения» какой-либо ветви разбора за счёт применения конечной формулы на достаточно высоком уровне позволяет существенно сузить пространство перебора при сохранении теоретического уровня сложности.

96

Таким образом, при построении алгоритма кумулятивного оценивания при рассмотрении конкретного показателя необходимо решать следующие задачи:

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

2.Применить подходящие приёмы декомпозиции графа и редукции его размерности.

3.Выбрать подходящий способ организации перебора возможных реализаций графа.

В докладе показаны решения этих задач для различных показателей надёжности, включая ATRи APNC.

Литература

1.Shooman A.M. Algorithms for network reliability and connection availability analysis // Electro/95 International. ProfessionalProgramProceedings, 1995 – P. 309-

2.FangtingS.,ShaymanM.A. On pairwise connectivity of wireless multihop networks // Int. J. Secur. Netw. 2, n. 1/2, 2007 – P. 37-49.

3.Potapov A., Goemann B., Wingender E. The pairwise disconnectivity index as a new metric for the topological analysis of regulatory networks // BMC Bioinformatics, 9, n. 1, 2008, – P. 1-15.

4.Valiant L. The Complexity of Enumeration and Reliability Problems // SIAM Journal on Computing, 1979, Vol. 8, No. 3. – P. 410-421.

5.Jason I. Brown, Charles J. Colbourn. Non-Stanley Bounds for Network Reliability //Journal of Algebraic Combinatorics, Vol. 5, No 1, 1995, P.13-36.

6.Won J.-M., Karray F. Cumulative Update of All-Terminal Reliability for Faster Feasibility Decision // IEEE Trans. Reliability, vol.59, no. 3, 2010, – P. 551-562.

7.Rodionov A., Migov D, Rodionova O. Improvements in the efficiency of cumulative updating of all-terminal network reliability //IEEE transactions on reliability, 61, n. 2, 2012. – P. – 460-465.

8.Rodionov A.S., Rodionova O.K. Exact bounds for average pairwise network reliability //Proc. ACM IMCOM (ICUIMC) 2013, paper 13-5, 6 pages.

9.Satyanarayana A., Chang M.K. Network reliability and the factoring theorem // Networks, Vol. 13, 1983, – P .107-120.

97

МЕТОДИКА СОВМЕЩЕННОГО РАЗМЕЩЕНИЯ ИНЖЕНЕРНЫХ КОММУНИКАЦИЙ В ГОРОДСКИХ УСЛОВИЯХ

Токтошов Г.Ы.

ИВМиМГ СО РАН, Новосибирск e-mail: tgi_tok@rambler.ru, тел.: +7-952-913-9625

При большом числе коммуникаций и недостатке свободных территорий в современных городах целесообразно применять совместную прокладку инженерных коммуникаций по единым строительным конструкциям, которые также называют общие коллекторы для подземных коммуникаций. Совмещенная прокладка инженерных коммуникаций в технико-экономическом отношении, как правило, более рациональна, поскольку приводит к уменьшению объемов земляных работ и снижению стоимости строительства. Согласно [1], стоимость строительства подземных коммуникаций при совмещенной их прокладке ниже стоимости их строительства при раздельной прокладке на 15 – 30%, а объем земляных работ меньше на 35 – 40% .

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

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

Пусть

приведенные затраты для реализации i -го варианта проекта при размещении

линии электросвязи и т.д.; Kij – капитальные вложения для размещения j -й коммуникации по i -му варианту проекта; Ci j – текущие (эксплуатационные) затраты на обслуживания j -й коммуникации по i -му варианту проекта; Ei,jН – нормативный коэффициент эффективности капитальных вложений; Ti,jН –

нормативный срок окупаемости капитальных вложений (величина обратная

).

Введем следующие понятия и ограничения [3]. Рассматривается прямоугольная система координат XYZO с метрикой пространств , выбор которой обусловлен требованием прокладки инженерных коммуникаций по координатным осям:

(M , N) X M X N Y M YN Z M Z N ,

где (M , N ) – расстояние между двумя точками M и N пространства XYZO . При решении задачи прокладки инженерных коммуникаций различного

первоначального положения.

Задача совмещенной прокладки инженерных коммуникаций различного назначения в одной траншее предполагает следующие ограничения:

ограничение на предельно допустимый размер коллектора:

размещения j -ой инженерной коммуникации в коллекторе:

обеспечение требуемого расстояния между коммуникациями различного назначения:

где [ 1]ik , i k , нормативное расстояние между коммуникациями различного назначения, определяемое в соответствии [2];

ортогональность фрагментов совместимых коммуникаций:

(x jn 1 x jn )( y jn 1 y jn ) 0 (x jn 1 x jn )(z jn 1 z jn ) 0 ( y jn 1 y jn )(z jn 1 z jn ) 0 ; (6)

99

непересечения несовместимых коммуникаций друг с другом:

удовлетворяющего условию ПIJ min , при ограничениях (2)-(9).

opt

Традиционно поставленную задачу решают следующим образом: сначала решают задачи строительства общих коллекторов по критерию минимума единовременных капиталовложений; далее решают задачи совмещенного размещения различных инженерных коммуникаций в общем коллекторе с учетом всех правил безопасности, требований и ограничений, при которых затраты на размещения и эксплуатация коммуникаций были бы минимальными. В дискретной постановке, эти две задачи решаются классическими методами теории графов, такими как алгоритм Дейкстры, алгоритм Флойда и т.д., независимо друг от друга. На практике они должны решаться с учетом зависимости показателей элементов коллектора и инженерных коммуникаций, поскольку параметры элементов коллектора, такие как высота, длина, ширина зависят от вида и назначения совмещенно прокладываемых инженерных коммуникаций или наоборот.

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

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

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

Внастоящей работе, на основе модели структурированной S-гиперсети [4], предлагается новая методика решения проблемы совмещенного размещения инженерных коммуникаций в общем коллекторе.

100