Лаборатория вычислительных систем

РЕЗУЛЬТАТЫ НАУЧНЫХ ИССЛЕДОВАНИЙ

Мультикластерная ВС ИФП СО РАН и ФГОБУ ВПО «СибГУТИ»

Программное обеспечение мультикластерной ВС MPIPerf, HBICT, GBroker, ... – компоненты, разработанные в лаборатории

1. Анализ функционирования распределенных вычислительных систем

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

   

   Рис. 1. Модель функционирования вычислительной системы со структурной избыточностью

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

   Также получены формулы для расчета среднего числа отказавших машин, ожидающих восстановления, (по процессу с полным восстановлением) с учетом соответствующего среднего квадратичного отклонения для ВС:

   

   где N - количество машин в ВС, μ - интенсивность полного восстановления отказавших машин, λ - интенсивность отказа одной машины, i - количество неисправных машин в начальный момент времени.

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

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

2. Разработка моделей и алгоритмов вложения параллельных программ в большемасштабные распределенные ВС

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

   Пусть имеется пространственно-распределённая ВС из H подсистем. Рассмотрим вложение параллельной программы в подсистему из N элементарных машин (ЭМ) (рис. 2). Для программы выделяется подсистема, которая также имеет иерархическую структуру. Обозначим n_l – число элементов на уровне l ∈ {1, 2, ..., L}; n_lk – количество прямых дочерних узлов элемента k ∈ {1, 2, ..., n_l}, находящегося на уровне l; c_lk – количество ЭМ, принадлежащих потомкам данного элемента.

   

   Рис. 2. Пример подсистемы ЭМ для решения параллельной задачи ранга r = 16

   Параллельная программа представлена информационным графом G = (V, E), где V = {1, 2, ..., N} – множество ветвей, а E ⊆ V × V – множество информационно-логических связей между ветвями. Обозначим через d_ij вес ребра (i, j) ∈ E, отражающий “интенсивность” обмена данными между ветвями i и j при выполнении программы.

   Вложение в ВС задаётся значениями переменных x_ij ∈ {0, 1}: x_ij = 1, если i ∈ V назначена на процессорное ядро j ∈ {1, 2, ..., N}, иначе x_ij = 0.

   В качестве критерия эффективности вложения использовалось время T выполнения обменов. Требуется построить вложение X, доставляющее минимум T:

   (1)

   

   при ограничениях

   (2)

   

   (3)

   

   Задача (1)-(3) является трудноразрешимой. Предложены алгоритмы её приближённого решения. Алгоритмы основаны на разбиении графа задачи на подмножества ветвей и вложения их в ЭМ, связанные быстрыми каналами связи. Цель разбиения – минимизация суммы весов ребер, инцидентных разным подмножествам разбиения. Разбиение выполняется многократно: для каждого уровня иерархии коммуникационной среды.

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

3. Разработка эвристических алгоритмов оптимизации информационных обменов в параллельных PGAS-программах

   В настоящее время языки программирования, реализующие модель разделённого глобального адресного пространства (PGAS) относятся к перспективным средствам разработки параллельных программ. PGAS-программы не содержат явных обращений к коммуникационным функциям; вместо этого они оперируют распределенными структурами данных и конструкциями для управления потоками выполнения (tasks, activities) и их синхронизации. Это позволяет существенно упростить разработку параллельных программ для распределённых вычислительных систем (ВС). Вместе с тем для PGAS-языков остро стоит задача разработки эффективных методов оптимизирующей компиляции. Операция редукции заданной ассоциативной операции и итерационный доступ к элементам распределённого массива являются часто встречающимися шаблонами в PGAS-программах.

   Разработан эвристический алгоритм BlockReduce выполнения редукции PGAS-программах (рис. 3). BlockReduce характеризуется невысокой вычислительной трудоёмкостью и незначительными накладными расходами на создание параллельных потоков выполнения. В отличие от существующих, данный алгоритм учитывает иерархическую структуру распределённых ВС и особенности реализации модели PGAS. Алгоритм реализован для языка Cray Chapel и позволяет сократить время выполнения редукции на 5-10% для массивов большого размера за счёт сокращения накладных расходов на создание параллельных задач.

   

   Рис. 3. Распределение элементов массива по вычислительным потокам в алгоритме BlockReduce

   При циклическом обращении к элементам массива, расположенным в памяти удаленных вычислительных узлов (ВУ) runtime-система языка будет выполнять копирование всего массива в память локального ВУ на каждой итерации цикла. Для оптимизации циклического доступа к удаленным массивам разработан алгоритм ArrayPreload минимизирующий время информационных обменов (рис. 4). ArrayPreload предотвращает многократное копирование массивов, выполняя опережающее копирование один раз перед итерациям. Алгоритм реализован для компилятора языка IBM X10 и позволяет достичь ускорения от 5 до 80 раз, в зависимости от размера массива и количества итераций.

   // Пролог цикла копирует A на каждый узел // один раз, сохраняя его в распределённом // массиве localA val localA: DistArray[Array[Long]] = ... for (i in 0..R) {  val id: Long = i % Places.MAX_PLACES;  at (Place.place(id)) {   // Использование локальной копии localA   // массива A   var a: Long = localA(id)(i % Size);  } }	for (i in 0..R) {  val id: Long = i % Places.MAX_PLACES;  at (Place.place(id)) {   // Использование одного элемента A   // приводит к копированию всего массива   // на ВУ с номером placeId   var a: Long = A(i % Size);  } }
   б	а

   Рис. 4. Пример оптимизации передачи массива A в параллельной программе на языке IBM X10:
   а – неоптимизированный код, б – оптимизированный код алгоритмом ArrayPreload

4. Разработка алгоритмов распределенного отказоустойчивого хранения контрольных точек восстановления параллельных программ

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

   1. Универсальное сжатие, например, алгоритм Лемпеля-Зива. Данный подход, в большинстве случаев, характеризуется высоким коэффициентом сжатия, однако имеет высокие накладные расходы.

   2. Дельта-сжатие предполагает исключение из формируемой КТ фрагментов, уже присутствующих в хранилище данных в ранее сохраненных КТ. Эффективность данного подхода в значительной степени зависит от шаблона изменения памяти программы, при этом он характеризуется высокой пропускной способностью.

   3. Существует также возможность комбинировать универсальное и дельта-сжатие для получения более качественных результатов.

   Для организации эффективного сжатия КТ был предложен алгоритм адаптивного выбора наиболее эффективного из доступных способов сжатия, позволяющий гибко подстраиваться под конкретную программу. Изначально из доступных методов сжатия выбирается один, который потенциальной является более эффективным (определяется субъективно администратором вычислительной системы), данный метод назовем текущим.

   В процессе формирования КТ производится одновременное ее сжатие всеми доступными методами. Для каждого из них определяется коэффициент K сжатия (отношение исходного объема КТ к сжатому) и производительность P, равная объему данных, сжимаемому в единицу времени. При этом только сжатая КТ, сформированная текущим методом записывается в хранилище данных, при этом производится оценка пропускной способности B используемой системы хранения данных. Наиболее эффективный метод сжатия определяется на основе целевой функции F, представляющей собой оценку общего времени записи КТ в хранилище данных:

   F(x) = S(x)·(KB + P)

   где x – сжимаемая КТ, а S(x) – ее размер в байтах.

   Предложенный алгоритм реализован в виде файловой системы ACFS (Adaptive Checkpointing File System).

   Также было проведено тестирование ACFS на реальных задачах, для этого использовался набор прикладных программ из промышленного теста NAS Parallel Benchmark производительности суперкомпьютеров.

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

5. Алгоритмы оптимизации функционирования ВС при решении масштабируемых задач

   Эффективность использования ресурсов вычислительных систем (ВС) во многом зависит от того, как организован процесс решения на них задач пользователей. Анализ пользовательских задач показывают, что более 98 % из них обладают свойством масштабируемости. Такие задачи допускают решение на подсистемах с различным количеством вычислительных узлов и называются масштабируемыми (moldable). В работе предложены алгоритмы оптимизации функционирования ВС при решении масштабируемых задач с учётом штрафов за задержку их решения и заданных пользователями приоритетов выбора значений параметров задач (их рангов). Под рангом понимается количество ветвей в параллельной программе масштабируемой задачи.

   Общая формулировка поставленной задачи следующая. Имеются вычислительная система (ВС), состоящая из N вычислительных узлов, и набор I из L масштабируемых задач. Каждая задача i ∈ {1,2,...,L} описывается вектором параметров p_i = (p_i¹,p_i²,...,p_i^q_i) и величиной штрафа c_i за задержку её решения в единицу времени, c_i>0.

   Каждый k-ый элемент вектора параметров p_i^k=(r_i^k,t_i^k,w_i^k) означает, что для решения i-той задачи требуется выделить подсистему из r_i^k узлов на время t_i^k, w_i^k – вес данного размера подсистемы (определяемый пользователем). Последний показатель определяет приоритет пользователя относительно выделения для решения i-ой задачи k-ой конфигурации, выражается как , где k ∈ {1,2,...,q_i}, 0<r_i^k≤N, t_i^k>0, w_i^k>0.

   Считается, что в наборе присутствуют задачи с различным количеством параметров (q_i). Допускается существование в векторе p_i нескольких элементов с одинаковым приоритетом. Каждой ветви параллельной программы выделяется не более одного узла. Любые два узла могут взаимодействовать через сеть связи. Зависимости между величинами r_i^k, t_i^k, w_i^k, c_i отсутствуют.

   Необходимо для каждой задачи i определить время s_i начала её решения, выбрать k_i – номер элемента вектора p_i и выделить множество номеров ЭМ J_i подсистемы необходимого размера. В результате должен быть сформирован вектор S = ⟨(k₁,s₁,J₁),(k₂,s₂,J₂),...,(k_L,s_L,J_L)⟩, называемый расписанием решения задач на ВС.

   Показателями эффективности расписаний являются время T(S) завершения решения последней задачи; суммарный штраф F(S) за задержку решения задач.

   

   Кроме этого, качество сформированного расписания оценивается степенью загрузки ресурсов ВС при решении задач.

   Требуется найти расписание S* решения задач на вычислительной системе такое, чтобы суммарное время T(S*) решения задач и штраф F(S*) за задержку их решения были минимальными;

   (1)

   

   (2)

   

   при ограничениях:

   (3)

   

   где Ω – область допустимых расписаний S, Ξ(t) = {i ∈ {1,2,...,L}|s_i ≤ t≤ s_i + t_i^k_i} – множество задач, решаемых в момент времени t. Ограничение (3) гарантирует, что в каждый момент времени суммарный ранг задач не превосходит количества узлов ВС.

   Задача (1) – (3) относится к многокритериальной оптимизации. Для решения задачи (1) – (3) использовать метод приоритетов, задавая функции (1) приоритет выше, чем функции (2), и метод ортогональной упаковки прямоугольных объектов в контейнеры. При этом задача набора кодируется прямоугольником с шириной, равной r_i^k и высотой t_i^k. Повороты и пересечения прямоугольников не допускаются. Известно, что эта задача является NP-сложной, поэтому актуальным является разработка алгоритмов её приближенного решения. В связи с этим предложенные в работе алгоритмы осуществляют поиск не минимальных, а субминимальных показателей целевых функций.

   Таким образом, решение задачи (1) – (3) разбивается на два этапа.

   На первом этапе задачи набора группируются в подмножества таким образом, чтобы выполнялись ограничения (3) и достигался субминимум функции (1).

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