557_Obrabotka_informatsii_i_matematicheskoe_modelirovanie_2014_

F t pотк exp (1 pотк ) μ t ,

n 1,

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

Поддержку высокой производительности ВС осуществляет структурная избыточность. Если структурная избыточность пуста, то считается, что ВС находится в режиме низкой производительности.

Пусть распределенная вычислительная система состоит из 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: [e-mail], тел.: [phone]

Рассматривается распределенная вычислительная система (ВС), на которую поступают задачи для решения. Поступившая задача попадает в накопитель. Из задач формируется пакет, количество задач в пакете ограничено числом элементарных машин (ЭМ) решающих задачи. В рамках теории массового обслуживания формулируется нижеследующая задача. На СМО поступает поток требований интенсивностью , из которых формируется пакет объема 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: [e-mail], тел.: [phone]

Одним из показателей эффективности функционирования распределенных вычислительных систем (ВС) является функция осуществимость параллельного решения задач [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: [e-mail], тел.: [phone]

Современные распределённые ВС – это сложный программноаппаратурный комплекс, включающий композицию элементарных машин (ЭМ), каналов связи и средства параллельного мультипрограммирования [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: [e-mail], тел.: [phone]

Современные большемасштабные распределённые вычислительные системы (ВС) комплектуются из большого числа многопроцесорных узлов на основе 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: [e-mail], тел.: [phone]

Распределённые вычислительные системы (ВС) являются основным средством высокопроизводительной обработки информации [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