Software tools for decentralized servicing of parallelMPI-jobs streams in geographically distributed multicluster computer systems.pdf При решении сложных задач науки и техники широкое применение получилипространственно-распределенные вычислительные системы (ВС) - макроколлекти-вы рассредоточенных вычислительных средств (подсистем), взаимодействующихмежду собой через локальные и глобальные сети связи (включая сеть Internet) [1, 2].К таким системам относятся GRID-системы и мультикластерные ВС.К значимым проблемам организации функционирования пространственно-распределенных ВС относится диспетчеризация параллельных программ. Для каж-дой программы, из поступивших в ВС, требуется определить ресурсы (подсистемы)для ее выполнения. В средствах диспетчеризации необходимо учитывать возмож-ность изменения состава и загрузки распределенной ВС с течением времени.Централизованные средства диспетчеризации программ имеют существенныйнедостаток: отказ управляющего узла ВС может привести к неработоспособностивсей системы. Кроме того, в случае применения таких средств в большемасштаб-ных ВС возрастают временные затраты на поиск требуемых ресурсов. Поэтомуактуальной является задача разработки децентрализованных моделей, алгоритмови программного обеспечения для диспетчеризации параллельных задач в распре-деленных ВС.При децентрализованной диспетчеризации в вычислительной системе долженфункционировать коллектив диспетчеров, осуществляющий выбор необходимыхресурсов для реализации программ. Это позволяет достичь и живучести больше-масштабных ВС, то есть способности систем продолжать работу при отказах от-дельных компонентов и подсистем.Существует несколько пакетов централизованной диспетчеризации парал-лельных программ в пространственно-распределенных системах: GridWay,Common Scheduler Framework (CSF), Nimrod/G, Condor-G, GrADS, AppLeS,DIRAC, WMS и др. В пакете GridWay [3, 4] преследуется цель минимизации вре-мени обслуживания задач, при этом учитывается время решения задачи и её пре-бывания в очереди; реализован механизм миграции задач между подсистемами.Среда CSF [5] предоставляет средства резервирования ресурсов на основе алго-ритма Round-Robin и алгоритмов, созданных пользователем. В основе Nimrod/G[6] лежит экономическая модель, целью которой является поиск равновесного со-стояния между поставщиками и потребителями ресурсов посредством механизмааукциона. Диспетчер Condor-G [7], являющийся развитием системы Condor, ори-ентирован на использование в системах высокой пропускной способности (HighthroughputComputing) и основан на алгоритмах Matchmaking и ClassAd. Предпо-лагается, что пользователь самостоятельно выбирает подсистему из списка дос-тупных; при этом поддерживается возможность создания пользовательских дис-петчеров. Функционирование диспетчера WMS [8], используемого в GRID-проекте Enable Grid for e-Science, основывается на применении двух алгоритмовдиспетчеризации: либо задача отправляется на подсистему для решения как мож-но быстрее, либо ожидает в очереди до тех пор, пока ресурс не станет доступным.В DIRAC [9] на подсистемах установленыКоллектив диспетчеров представлен в виде ориентированного графаG = (S, E), в котором вершинам соответствуют диспетчеры, а ребрам - логиче-ские связи между ними. Наличие дуги (i, j)  E в графе означает, что диспетчер iможет отправлять ресурсные запросы (задачи из своей очереди) диспетчеру j.Множество всех вершин j, смежных вершине i, образуют её локальную окрест-ность L(i) = {j  S: (i, j)  E}.Пользователь направляет задачу и запрос на выделение ресурсов одному издиспетчеров. Диспетчер (в соответствии с реализованным в нем алгоритмом)осуществляет поиск (суб)оптимальной подсистемы j∗  S для выполнения задачипользователя.Считаем, что задача характеризуется рангом r - количеством параллельныхветвей, ожидаемым временем t выполнения программы (walltime) и суммарнымразмером z исполняемых файлов и данных ([z] = байт). Рассмотрим децентрализо-ванный алгоритм обслуживания потоков параллельных задач в пространственно-распределенных ВС.2. Децентрализованный алгоритм диспетчеризации параллельных задачПри поступлении программы пользователя в очередь подсистемы i  S её дис-петчер выполняет следующий алгоритм:1. У каждого диспетчера j  L(i)  {i} запрашивается оценка времени tj, черезкоторое программа может быть запущена на ресурсах подсистемы j в случае пе-редачи программы в её очередь.2. Через систему мониторинга определяется текущее значение пропускнойспособности bij = b(i, j, z) канала связи между подсистемами i и j.3. Отыскивается оценка времени t(i, j) обслуживания программы в случае еёперенаправления в очередь подсистемы j. Время обслуживания включает в себявремя доставки исполняемых файлов и данных до подсистемы j, время ожиданияtj в очереди подсистемы и время t выполнения программы:t(i, j) = z / bij + tj + t.4. Программа перенаправляется в очередь подсистемы j∗, в которой достигает-ся минимальное значение времени t(i, j) обслуживания параллельной программы*( ) { }argmin { ( , )}j L i ij ti j = .Диспетчер выполняет описанный алгоритм поиска подсистем при наступленииодного из нижеследующих событий.1. Поступление новой задачи в очередь от пользователя.2. Удаление задачи из очереди, начало выполнения задачи, изменение парамет-ров (количества ветвей, времени решение) одной или нескольких задач в очереди.Перечисленные события влекут за собой поиск новых подсистем для задач, стоя-щих в очереди после задач с модифицированными параметрами и состояниями.3. Окончание временного интервала ƒ c момента последнего запуска алгорит-ма поиска подсистем.Периодический поиск подсистем для задач в очереди позволяет учесть дина-мически изменяющуюся загрузку ресурсов пространственно-распределенных вы-числительных и GRID-систем. Описанный подход реализован в программном па-кете GBroker децентрализованной диспетчеризации параллельных MPI-программв пространственно-распределенных мультикластерных ВС.3. Программный пакет GBrokerВ Центре параллельных вычислительных технологий ГОУ ВПО «Сибирскийгосударственный университет телекоммуникаций и информатики» (ЦПВТ ГОУВПО «СибГУТИ») и Лаборатории вычислительных систем Института физики по-лупроводников им. А.В. Ржанова СО РАН (ИФП СО РАН) создан и развиваетсяпрограммный пакет GBroker [10] децентрализованной диспетчеризации парал-лельных MPI-программ в пространственно-распределенных ВС. Пакет разработанна языке ANSI C для операционной системы GNU/Linux.В пакет (рис. 2) входят диспетчер gbroker, клиентское приложение gclient исредство мониторинга производительности каналов связи netmon между подсис-темами на уровне стека протоколов TCP/IP.Рис. 2. Функциональная структура пакета GBrokerМодуль gbroker устанавливается на каждой из подсистем и на основе расши-ряемой архитектуры обеспечивает интерфейс с локальной системой пакетной об-работки заданий (на данный момент − TORQUE). Модуль netmon устанавливаетсявместе с gbroker на подсистемах. Взаимодействуя друг с другом, сервисы netmonсобирают информацию о производительности каналов связи между подсистема-ми. Модуль gclient реализует интерфейс между пользователем и системой.Администратор настраивает локальные окрестности диспетчеров gbroker, ука-зывая, какие диспетчеры с какими могут обмениваться задачами из своих очере-дей, и настраивает сервис netmon.Пользователь формирует задание, состоящее из параллельной MPI-программыи паспорта на языке ресурсных запросов JSDL (Job Submission DescriptionLanguage) и отправляет его средствами gclient любому из диспетчеров gbroker.Диспетчер в соответствии с описанным алгоритмом выбирает подсистему, на ко-торой должна выполняться задача.4. Моделирование алгоритмов и программных средствСозданный инструментарий децентрализованной диспетчеризации параллель-ных задач исследован на действующей мультикластерной ВС, созданной ЦПВТГОУ ВПО "СибГУТИ" совместно с Лабораторией ВС ИФП СО РАН. В экспери-ментах было использовано 3 сегмента мультикластерной ВС (рис. 3):- кластер Xeon16: 4 узла (2 x Intel Xeon 5150, 16 процессорных ядер);- кластер Xeon32: 4 узла (2 х Intel Xeon 5345, 32 процессорных ядра);- кластер Xeon80: 10 узлов (2 x Intel Xeon 5420, 80 процессорных ядер).Сеть связи между сегментами ВС Fast Ethernet.На сегментах системы был установлен пакет Gbroker и настроен компонентnetmon (рис. 3). В локальную окрестность каждого диспетчеры были включеныдиспетчеры всех кластеров.Рис. 3. Тестовая конфигурация пространственно-распределенноймультикластерной ВС (H = 3)В качестве тестовых задач использовались MPI-программы из пакета NASParallel Benchmarks (NPB). Моделирование проводилось следующим образом. Навыбранную подсистему поступал стационарный поток из M = 500 параллельныхзадач. Тестовые задачи выбирались псевдослучайным образом. Ранг ri параллель-ной программы генерировался в соответствии с распределением Пуассона со зна-чениями математического ожидания r = {4, 8, 12, 16}. Задачи поступали в очередьдиспетчера кластера Xeon80 через интервалы времени t, экспоненциально распре-деленные со значениями интенсивности ƒ = {0.1, 0.2, 0.3, 0,4}, [ƒ] = с−1.Обозначим через ti - момент времени поступления задачи i  {1, 2, …, M} навход диспетчера, , ti - момент времени начала решения задачи i, ti - момент за-вершения решения задачи i. Тогда суммарное время ƒ обслуживания (ожидания вочереди и решения) M задач составит1,2, , 1,2, ,imaxMi iminMit t= =ƒ = −… ….Для оценки эффективности алгоритма диспетчеризации использовались сле-дующие показатели:- среднее время T обслуживания задачи11 ( )Mi iiT M t t== ƒ − ;среднее время W пребывания задачи в очереди11 ( )Mi iiW M t t== ƒ − ;- пропускная способность B системыB = M / ƒ.На рис. 4 показана зависимость среднего времени обслуживания параллельныхзадач от интенсивности их поступления в систему.05101520251234T, с0,05 0,15 0,25 0,35 ƒ, c-1Рис. 4. Зависимости среднего времени T обслуживания задачиот интенсивности ƒ потока задач: 1 - r = 4; 2 - r = 8; 3 - r = 12; 4 - r = 16Из графиков видно, что среднее время обслуживания задачи увеличивается сростом интенсивности потока поступления задач. Это связано с образованиемочередей задач на подсистемах ВС. Такое влияние интенсивности потока особен-но значительно при рангах параллельных программ, близких к количеству про-цессорных ядер в подсистемах.Среднее время W пребывания задачи в очереди незначительно (рис. 5) по срав-нению с суммарным временем её обслуживания и в среднем не превосходит однойсекунды (для рассматриваемой конфигурации ВС). Среднее время пребывания за-дачи в очереди не изменяется существенно как с ростом интенсивности потока по-ступления задач, так и с увеличением среднего ранга параллельных задач.W, с43210,800,600,400,2000,05 0,15 0,25 0,35 ƒ, c-1Рис. 5. Зависимости среднего времени W пребывания задачи в очередиот интенсивности ƒ потока задач: 1 - r = 4; 2 - r = 8; 3 - r = 12; 4 - r = 16Пропускная способность системы (рис. 6) растет при увеличении интенсивно-сти потока поступления задач. При больших значениях интенсивности происхо-дит снижение пропускной способности системы, что связано с образованием оче-редей на подсистемах. С увеличением среднего ранга задач это влияние интен-сивности на пропускную способность системы усиливается.B,задач/с43210,050,040,030,020,05 0,15 0,25 0,35 ƒ, c-1Рис. 6. Зависимости пропускной способности B системыот интенсивности ƒ потока задач: 1 - r = 4; 2 - r = 8; 3 - r = 12; 4 - r = 16ЗаключениеЦентрализованные системы диспетчеризации большемасштабных распреде-ленных ВС характеризуются вычислительной сложностью поиска требуемых ре-сурсов. Децентрализованная диспетчеризация параллельных программ в про-странственно-распределенных вычислительных и GRID-системах позволяет по-высить их живучесть. Кроме того, применение централизованных систем диспет-черизации в большемасштабных ВС ограничено вычислительной сложностью по-иска требуемых ресурсов.Результаты исследования созданного инструментария децентрализованнойдиспетчеризации параллельных MPI-программ на мультикластерной ВС показали,что среднее время обслуживания задач и при децентрализованной, и при центра-лизованной диспетчеризации сопоставимы. Время диспетчеризации достаточномало по сравнению со временем выполнения задач.Инструментарий децентрализованной диспетчеризации - один из необходи-мых компонентов обеспечения живучести пространственно-распределенноймультикластерной ВС ЦПВТ ГОУ ВПО «СибГУТИ» и лаборатории ВС ИФП СОРАН.

Скачать электронную версию публикации