557_Obrabotka_informatsii_i_matematicheskoe_modelirovanie_2014_
.pdfдолжны быть высоконадежными и живучими и не должны выходить из строя. Они могут находиться либо в режиме высокой производительности либо низкой производительности. В процессе функционирования могут выходить из строя ЭМ.
Поддержку высокой производительности ВС осуществляет структурная избыточность. Если структурная избыточность пуста, то считается, что ВС находится в режиме низкой производительности.
Пусть распределенная вычислительная система состоит из N элементарных машин, n из них составляют структурную избыточность, а остальные N n образуют основную подсистему [1]. Любая из ЭМ основной подсистемы может выйти из строя. Вышедшая из строя ЭМ меняется на одну из ЭМ структурной избыточности, а сама вместе с другими машинами, число которых не более чем
ждет завершения восстановления. Все восстановленные ЭМ возвращаются в вычислительную систему. Моменты завершения восстановления описываются пуассоновским процессом с параметром μ . Если
из строя выходит очередная ЭМ, а структурная избыточность пуста, то ВС переходит из состояния высокой производительности в состояние низкой, то есть основная подсистема работает в пониженном режиме.
Получено выражение для вероятности того, что ВС в состоянии низкой производительности и будет находиться в течение времени не меньшего заданного:
(1)
|
|
|
N λ |
n |
где p |
отк |
|
|
. |
|
||||
|
|
|
|
|
|
|
|
μ N λ |
Функция G t 1 F t / pотк является функцией распределения времени
нахождения ВС в состоянии низкой производительности.
Оценка погрешности (t, m) для функции (1)
(t,m) Nλ / Nλ μ m n 1 F(t) ,
где m есть то число, на которое нужно увеличить объем резерва, чтобы ВС оставалась в состоянии высокой производительности практически достоверно.
Литература
1.Хорошевский В.Г. Архитектура вычислительных систем. М.: МГТУ им.
Баумана, 2008. 520 с.
2.Nikolic S. High Performance Computing Directions: The Drive to ExaScale Computing // Труды международной научной конференции “Параллельные вычислительные технологии (ПаВТ’2012). – Новосибирск, 2012, URL: http://pavt.susu.ru/2012/talks/Nikolic.pdf (дата обращения 14.02.2014).
3.Schroeder В. A., Gibson G.A. Large-scale study of failures in high-performance computing systems // Dependable Systems and Networks (DSN2006): proceedings of the International Conference. – USA: Philadelphia, PA, 2006. – P. 10.
4.Top 500. URL: http://www.top500.org, 2013.
81
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ДЛЯ РАСЧЕТА ВЕРОЯТНОСТИ РЕШЕНИЯ ЗАДАЧ ПОТОКА НА РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ*
Павский К.В. СибГУТИ, Новосибирск
e-mail: pkv@isp.nsc.ru, тел.: (383) 330-56-26
Рассматривается распределенная вычислительная система (ВС), на которую поступают задачи для решения. Поступившая задача попадает в накопитель. Из задач формируется пакет, количество задач в пакете ограничено числом элементарных машин (ЭМ) решающих задачи. В рамках теории массового обслуживания формулируется нижеследующая задача. На СМО поступает поток требований интенсивностью , из которых формируется пакет объема n, n 1,2,... . Если пакет сформирован, то требование получает отказ. Как только СМО освобождается, она приступает к обслуживанию с
интенсивностью β(t) очередного |
пакета, |
пусть даже и не до конца |
|||
сформированного. |
Интенсивность |
β(t) |
имеет |
зависимость |
от |
производительности системы, в которой возможны отказы ЭМ [1].
Требуется найти Pk (t) – вероятность, что в момент времени t 0, пакет
состоит из k нерешенных задач, при условии, что в начальный момент времени пакет был пустым; k 0,1,2,....
Получена система дифференциальных уравнений
d |
|
|
|
|
|
P0 (t) P0 (t) (t) Pk (t), |
|
|
|
||
dt |
k 1 |
(1) |
|
|
|
||
d |
|
|
|
|
|
Pk (t) ( (t)) Pk (t) Pk 1 (t), k E1 |
|
|
|
||
dt |
|
|
с начальными условиями
P0 (0) 1, Pk (0) 0 , k 0 .
В работе предлагаются решения для системы (1).
Литература 1. Хорошевский В.Г. Архитектура вычислительных систем. М.: МГТУ им.
Баумана, 2008. 520 с.
*) Работа выполнена при поддержке РФФИ (гранты №13-07-00160, №12-07-00145).
82
ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ДЛЯ РАСЧЕТА ФУНКЦИИ ОСУЩЕСТВИМОСТИ РЕШЕНИЯ СЛОЖНЫХ ЗАДАЧ
НА РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ*
Павский К.В. СибГУТИ, Новосибирск
e-mail: pkv@isp.nsc.ru, тел.: (383) 330-56-26
Одним из показателей эффективности функционирования распределенных вычислительных систем (ВС) является функция осуществимость параллельного решения задач [1]. Под этой функцией понимается вероятность параллельного решения задач на распределенных ВС.
В работе предложен параллельный алгоритм для расчета P(T ,t,n)
вероятности решения сложной задачи (представленной параллельной программой) за время T на распределенной ВС состоящей из n исправных ЭМ при общим числе машин – N; t – время решения задачи на одной ЭМ [2].
Алгоритм был реализован на языке программирования Си с использованием библиотеки MPI. Результаты эффективности исполнения параллельной программы на сегменте кластерной вычислительной системе представлены на рисунке 1.
Рисунок 1 – Зависимость коэффициента ускорения вычислений на кластерной ВС от числа вычислительных ядер
Литература
1.Хорошевский В.Г. Архитектура вычислительных систем. М.: МГТУ им.
Баумана, 2008. 520 с.
2.Павский К.В. Математическая модель для оценки функции осуществимости
решения сложной задачи на распределенных вычислительных системах //
*) Работа выполнена при поддержке РФФИ (грант №13-07-00160, №12-07-00145).
83
Материалы Российской научно-технической конференции "Обработка информационных сигналов и математическое моделирование", Новосибирск, 2013, С. 136-137.
ОЦЕНКА ЭФФЕКТИВНОСТИ ВЫПОЛНЕНИЯ ОПЕРАЦИЙ С РАСПРЕДЕЛЁННЫМИ ДАННЫМИ В ПАРАЛЛЕЛЬНЫХ ПРОГРАММАХ НА ЯЗЫКЕ CRAY CHAPEL5
Пазников А.А. СибГУТИ, Новосибирск
e-mail: apaznikov@gmail.com, тел.: (383) 269-82-75
Современные распределённые ВС – это сложный программноаппаратурный комплекс, включающий композицию элементарных машин (ЭМ), каналов связи и средства параллельного мультипрограммирования [1]. Текущий уровень развития высокопроизводительных вычислений характеризуется большемасштабностью, иерархической организацией коммуникационных сред, гетерогенностью ресурсов.
Библиотеки коммуникационных функций стандарта MPI (MPICH, Open MPI и др.) являются основным средством разработки параллельных программ. Вместе с тем сегодня активно развиваются средства разработки параллельных программ на основе модели глобального разделённого адресного пространства (Partitioned Global Address Space – PGAS). К семейству PGASязыков относится Cray Chapel, IBM X10, Unified Parallel C, Coarray Fortran и др.
Данные языки моделируют единое адресное пространство и обеспечивают для параллельных ветвей возможность доступа к участкам памяти, расположенным на любом из удалённых вычислительных узлов (ВУ) распределённой ВС (рисунок 1). Модель PGAS позволяет снизить трудоёмкость разработки параллельных программ. Для PGAS-языков остро стоит задача оптимизации операций над данными, распределёнными между ВУ.
Рисунок 1 – Модель глобального разделяемого адресного пространства (PGAS)
5 Работа выполнена при поддержке РФФИ (гранты № 12-07-00145, 13-07-00160) и Совета при Президенте РФ (грант МД-2620.2014.9)
84
При разработке параллельных программ и оптимизации операций с распределёнными данными в PGAS-языках требуется оценивать эффективность выполнения программ с большим (порядка 106) количеством параллельных ветвей и при использовании различных технологий (Infiniband, 10-gigabit Ethernet, Myrinet) и структур коммуникационных сред.
На сегодняшний день существуют средства моделирования распределённых вычислений, такие как LogGOPSim, BigSim, SILAS, MPI-SIM, PSINS, DIMEMAS. LogGOPSim [2], например, позволяет по результатам профилирования MPI-программ моделировать выполнение при большом количестве параллельных ветвей. Однако имеющиеся пакеты моделирования не учитывают особенности реализации PGAS-программ: большое количество информационных обменов малого размера, использование коммуникационных операций прямого доступа к памяти, динамический параллелизм. Поэтому практически значимой является задача разработки инструментария моделирования, ориентированного на языки класса PGAS.
Среди языков PGAS можно выделить Cray Chapel [3], который является одним из наиболее перспективных и интенсивно развивающихся. В нём вычисления на распределённых ВС реализуются за счёт взаимодействия параллельных ветвей (“локалей”, locales), которые в физическом плане соответствуют вычислительным узлам. Интенсивность информационных обменов между ветвями можно представить в виде матрицы (рисунок 2) или графа взаимодействий. Матрицы могут иметь различные размеры, в которых можно выделить шаблоны взаимодействий, характерные для отдельных классов задач.
a б
Рисунок 2 – Матрицы интенсивности взаимодействий (операции удалённого доступа к памяти) для программы High Performance Linpack при различном количестве n параллельных ветвей (a – n = 8, б – n = 12)
В данной работе предложены алгоритмы оценки эффективности выполнения Chapel-программ с большим количеством параллельных ветвей и с использованием различных технологий межмашинных связей. Алгоритмы основаны на анализе матриц информационных обменов, полученных в результате профилирования Chapel-программ.
85
В Центре параллельных вычислительных технологий ФГОБУ ВПО “Сибирский государственный университет телекоммуникаций и информатики” (ЦПВТ ФГОБУ ВПО “СибГУТИ”) и Лаборатории вычислительных систем Института физики полупроводников им. А.В. Ржанова СО РАН (ИФП СО РАН) разрабатывается программный пакет ChapelProf анализа эффективности выполнения параллельных программ.
Проведено моделирование с использованием тестовых задач из пакетов
HPC Challenge Benchmark, Scalable Synthetic Compact Application (SSCA).
Профилирование выполнялось мультикластерной ВС ЦПВТ ФГОБУ ВПО “СибГУТИ” и Лаборатории ВС ИФП СО РАН. Выполнено сравнение аналитических моделей дифференцированных обменов (LogP, LogGP, pLogP и др.), приведены показатели эффективности при изменении числа параллельных ветвей и типов коммуникационных сред.
Для исследования эффективности пакета ChapelProf при анализе операций над распределёнными массивами данных в распределённых иерархических ВС предложен алгоритм HierarchicReduce иерархической редукции. Текущая реализация редукции в Cray Chapel не предусматривает распараллеливание по процессорным ядрам [3]. Алгоритм HierarchicReduce реализован на языке Cray Chapel и выполняет распараллеливание операции редукции как между локалями (вычислительными узлами), так и внутри локалей между процессорными ядрами (рисунок 3).
Рисунок 3 – Алгоритм иерархической редукции в языке Cray Chapel
На мультикластерной ВС ЦПВТ ФГОБУ ВПО “СибГУТИ” и ИФП СО РАН проведено исследование эффективности алгоритма HierarchicReduce. В докладе приводится подробная информация о результатах экспериментов и сравнение с реализацией редукции по умолчанию.
86
Литература 1. Хорошевский В.Г. Распределённые вычислительные системы с
программируемой структурой // Вестник СибГУТИ. – 2010. – № 2. – С. 3-41.
2.T. Hoefler, T. Schneider and A. Lumsdaine. LogGOPSim – Simulating LargeScale Applications in the LogGOPS Model // 19th ACM International Symposium on High Performance Distributed Computing. – 2010. – P. 597-604.
3.D. Callahan, B.L. Chamberlain, H.P. Zima. The Cascade High Productivity Language // HIPS '04. – 2004. – P. 52-60.
4.S.J. Deitz, D. Callahan, B.L. Chamberlain, L. Snyder. Global-view abstractions for user-defined reductions and scans // PPoPP '06. – 2006. – P. 40-47.
АЛГОРИТМЫ ДИНАМИЧЕСКОЙ БАЛАНСИРОВКИ НАГРУЗКИ РАБОЧИХ ПОТОКОВ ПРИ WORK-STEALING-ПЛАНИРОВАНИИ НА ОСНОВЕ РЕЗУЛЬТАТОВ ПРОФИЛИРОВАНИЯ6
Пазников А.А., Нилов Д.С., Малыгин С.А. СибГУТИ, Новосибирск
e-mail: deadbilberrypie@gmail.com, тел.: (383) 269-82-75
Современные большемасштабные распределённые вычислительные системы (ВС) комплектуются из большого числа многопроцесорных узлов на основе SMP/NUMA-систем и модулей специализированных ускорителей [1]. Вычисления на таких ВС реализуются с помощью инструментария многопоточного программирования (Cilk, Intel TBB, OpenMP, C++11-threads).
Основным компонентом данных средств является планировщик, обеспечивающий балансировку загрузки рабочих потоков (процессорных ядер). Параллельная программа представляется композицией задач (problems, tasks) для выполнения на рабочих потоках. Необходимо распределить задачи между потоками с целью минимизации времени выполнения программы (рисунок 1). При этом необходимо учитывать блокировки ресурсов (deadlocks), гонки (race), голодание (starvation), обеспечение асинхронности, атомарности операций.
Рисунок 1 – Балансировка загрузки рабочих потоков
6 Работа выполнена при поддержке РФФИ (гранты № 12-07-00145, 13-07-00160) и Совета при Президенте РФ (грант МД-2620.2014.9)
87
Существует множество алгоритмов планирования задач: First-come Firstserved (FCFS), Round-robin (RR), Shortest-Remaining Time-First (SRTF), Shortest Job First (SJF), Work-stealing и др. В Cilk (Cilk++) [2], Intel TBB [3] используется планировщик на основе графа зависимостей. Стандартная библиотека многопоточности, входящая в состав C++11, не реализует свой планировщик. Work-stealing [4-5] является наиболее распространённым (Cilk, Intel TBB и др.); он предусматривает множество стратегий планирования, например, критический путь в графе зависимостей, work-first, help-first [6].
В работе рассматривается задача динамического планирования на основе Work-stealing. Предложены эвристические алгоритмы балансировки нагрузки на основе механизма назначения приоритетов задач по результатам профилирования. Цель алгоритмов – минимизация времени выполнения параллельных программ.
Рисунок 2 – Балансировка загрузки рабочих потоков на основе профилирования
Для каждой задачи строится граф зависимостей и вычисляется критический путь. Оценка времени обслуживания критического пути корректируется по результатам профилирования выполнения задач. Задача назначается в очередь рабочего потока, который обеспечивает минимизацию времени завершения его выполнения (рисунок 2). При реализации программных средств использовались асинхронные вызовы C++11 и atomic-операции для планирования задач.
Моделирование алгоритмов выполнялось на мультикластерной ВС Центра параллельных вычислительных технологий ФГОБУ ВПО «СибГУТИ» с использованием программ, реализующих распространённые алгоритмы обработки данных. Эксперименты проводились на кластере Jet (18 узлов, 2 x
88
Intel Xeon E5420, сеть Gigabit Ethernet). Результаты экспериментов будут представлены в докладе.
Литература 1. Хорошевский В.Г. Распределённые вычислительные системы с
программируемой структурой // Вестник СибГУТИ. – 2010. – № 2. – С. 3-41.
2.R.D. Blumofe, C.F. Joerg, B.C. Kuszmaul, C.E. Leiserson [et al.]. Cilk: An Efficient Multithreaded Runtime System // Journal of Parallel and Distributed Computing. – 1995. – Vol. 61(11). – P. 207-216.
3.J. Reinders. Intel Threading Building Blocks Outfitting C++ for Multi-core Processor Parallelism. – Sebastopol: O'Reilly & Associates, 2007. – 334 p.
4.M. Wimmer, D. Cederman, J.L. Träff, P. Tsigas. Work-stealing with configurable scheduling strategies // PPoPP '13. – 2013. – P. 315-316
5.R.D. Blumofe, C.E. Liserson. Scheduling multithreaded computations by work stealing // Journal of ASM. – 1999. – Vol. 46(5). – P. 720-748.
6.Y. Guo, R. Barik, R. Raman. Work-First and Help-First Scheduling Policies for Async-Finish Task Parallelism // Parallel & Distributed Processing. – 2009. – P. 1-12.
АЛГОРИТМЫ ПРОГНОЗИРОВАНИЯ ВРЕМЕНИ РЕАЛИЗАЦИИ ИНФОРМАЦИОННЫХ ОБМЕНОВ В ПАРАЛЛЕЛЬНЫХ MPI-ПРОГРАММАХ НА ОСНОВЕ МОДЕЛЕЙ АВТОРЕГРЕССИИ7
Пазников А.А., Чирихин К.С. СибГУТИ, Новосибирск
e-mail: chirihinkonstant@mail.ru, тел.: 8913-372-43-94
Распределённые вычислительные системы (ВС) являются основным средством высокопроизводительной обработки информации [1]. В настоящее время параллельные программы для таких систем разрабатываются в стандарте MPI. При организации функционирования распределённых ВС часто возникает необходимость оценки времени выполнения параллельных MPI-программ.
Выполнение программ в модели передачи сообщений складывается из времени вычислений и времени выполнения коммуникационных функций. Оценка времени выполнения информационных обменов основано на использовании аналитических моделей дифференцированных обменов, таких как Hockney, LogP, LogGP, pLogP и др. Следует отметить, что модель LogP [2]
является универсальной (не зависит от специфических параметров ВС, таких как топология сети и алгоритмы маршрутизации). На её основе разработаны модели LogGP, в которой учитывается размер крупных сообщений pLogP, параметры которой зависят от размера m сообщения, и другие.
Существующие системы (Netgauge, COMB, Netpipe, NWSи др.) оценки времени выполнения коммуникационных функций используют вышеописанные
7 Работа выполнена при поддержке РФФИ (гранты № 12-07-00145, 13-07-00160) и Совета при Президенте РФ (грант МД-2620.2014.9)
89
модели. В Netgauge [3] реализован метод измерения параметров модели LogGP с низкими накладными расходами. Netpipe [4] использует обмены типа «точкаточка» и модифицированную модель Хокни [5]. Параметры аналитических моделей существенно изменяются в условиях длительной эксплуатации ВС. Приведенные системы не учитывают динамическую загрузку каналов связи. Поэтому требуется разработка инструментария прогнозирования времени выполнения MPI-обменов. При этом необходимо также учитывать тип обменов (дифференцированные, коллективные, односторонние) и технологии коммуникационных сред (Infiniband, GigabitEthernet, Internet).
В работе предлагаются алгоритмы прогнозирования времени выполнения MPI-обменов на основе временных рядов. Используются модели авторегрессии(AR), авторегрессии-скользящего среднего (ARMA) и интегрированная модель авторегрессии-скользящего среднего(ARIMA) для построения прогноза времени выполнения обменов на основе моделей LogP, LogGP, pLogP и др.
Разработанные алгоритмы реализованы в программном инструментарии MPI-Forecast (рисунок). Для построения временных рядов параметров моделей используется пакет Netgauge [3] оценки времени выполнения информационных обменов. На основе временного ряда строится прогноз времени выполнения дифференцированных и коллективных операций заданного размера. Учитывается алгоритм реализации коммуникационной операции, ранг параллельной программы (в случае коллективных обменов) и тип коммуникационной среды [6].
Рисунок – Функциональная схема пакета MPI-Forecast
90