Decentralized scheduling algorithms of geographically-distributedcomputer systems.pdf В настоящее время при решении сложных задач науки и техники широко ис-пользуются пространственно-распределённые вычислительные системы (ВС).В архитектурном плане такие ВС представляют собой макроколлективы рассре-доточенных вычислительных средств (подсистем), взаимодействующих междусобой через локальные и глобальные сети связи (включая сеть Internet) [1]. К про-странственно-распределённым относятся мультикластерные вычислительные иGRID-системы.К значимым проблемам организации функционирования пространственно-распределённых ВС относится диспетчеризация. Для каждой параллельной зада-чи, из поступивших в ВС, требуется определить подсистемы для её решения. Приэтом важно учитывать изменения состава и загрузки ВС с течением времени.В пространственно-распределённых вычислительных и GRID-системах каждаяподсистема функционирует под управлением локальной системы управления ре-сурсами (СУР) (TORQUE, Altair PBS Pro, SLURM и др.), которая поддерживаеточереди пользовательских задач и выделяет для них вычислительные ресурсы(процессорные ядра).Централизованные средства диспетчеризации задач в пространственно-распределённых ВС подразумевают наличие в системе центрального диспетчера,поддерживающего глобальную очередь задач. Отказ такого диспетчера можетпривести к неработоспособности всей системы. Кроме того, в случае применениятаких средств в большемасштабных ВС возрастают временные затраты на поисктребуемых ресурсов.Основными программными пакетами организации централизованной диспетче-ризации параллельных задач в пространственно-распределённых вычислительных иGRID-системах являются: GridWay [2], AppLeS [3], GrADS [4], Nimrod/G [5],Condor-G [6]. Пакет GridWay входит в состав пакета Globus Toolkit и является наи-более распространённым GRID-диспетчером. В нём преследуется цель минимиза-ции времени обслуживания задач и поддерживается механизм их миграции междуподсистемами. В AppLeS диспетчеризация выполняется на уровне самого приложе-ния, что требует от пользователя знания конфигурации системы - это снижает уни-версальность указанного пакета. Пакет GrADS, как и GridWay, поддерживает ми-грацию задач и допускает указание зависимостей по данным между задачами.Nimrod/G на основе экономических моделей обеспечивает равновесие между ус-ловными поставщиками (подсистемами) и потребителями вычислительных ресур-сов (задачами). В Condor-G зависимости между задачами задаются в виде ориенти-рованного ациклического графа.При децентрализованной диспетчеризации в распределённой ВС функциони-рует коллектив диспетчеров, которые поддерживают распределённую очередь за-дач и совместно принимают решение о выборе ресурсов. Это позволяет достичьживучести ВС - способности систем продолжать работу при отказах отдельныхподсистем.Для распределённых вычислительных систем с программируемойПодсистема1Диспетчер1Локальные задачиЭМ1 ЭМ2 ... ЭМn1СУРПодсистема2Диспетчер2Локальные задачиЭМ1 ЭМ2 ... ЭМn2СУРПодсистема3Диспетчер3Локальные задачиСУРПодсистема4Диспетчер4Локальные задачиСУРЭМ1 ЭМ2 ... ЭМn3 ЭМ1 ЭМ2 ... ЭМn4Рис. 1. Пример локальных окрестностей диспетчеров:H = 4, L(1) = {2, 3}, L(2) = {1, 4}, L(3) = {1, 4}, L(4) = {2, 3}Пользователь направляет задачу диспетчеру i. Задача содержит программу,входные файлы и ресурсный запрос, в котором указываются ранг r программы(количество параллельных ветвей), размеры z1, z2, …, zk исполняемого и входныхфайлов программы ([zl] = байт), а также номера h1, h2, …, hk, подсистем на кото-рых размещены соответствующие файлы (hl  S). Диспетчер (в соответствии среализованным в нём алгоритмом) выполняет поиск (суб)оптимальной подсисте-мы j*  L(i)  {i} (или подсистем 1 2 , , ,m j∗ j∗ j∗ … ) из его локальной окрестности.2. Децентрализованные алгоритмы диспетчеризации задачПредложено четыре децентрализованных алгоритма диспетчеризации парал-лельных задач в пространственно-распределённых ВС. Каждый алгоритм описы-вает функционирование диспетчера i при поступлении задачи в его очередь. Наначальном этапе работы все алгоритмы предполагают обращение диспетчера i ксистеме2.1. А л г о р и т м л о к а л ь н о - о п т и м а л ь н о й д и с п е т ч е р и з а ц и и ( Д Л О )Алгоритм осуществляет выбор локально-оптимальной подсистемы.Шаг 1. Из окрестности S(i) диспетчера i выбирается подсистема j* с мини-мальным значением F(j), j ƒ S(i):*( )argmin ( )j S ij Fj= ,maxmax maxmax, если или 0,( ), иначе,j jj jjjt c wc r qt c wF jtt⎧+ + < > ⎪⎪=⎨⎪⎪⎩где1( , , )kj l llt th jz== ƒ - время доставки файлов задачи до подсистемы j;max ( )mj Saxi { j}t t= ; max ( )mj Saxi { j}c c= , wj = qj / nj - количество задач в очереди, прихо-дящееся на одну ЭМ подсистемы j; max ( )mj Saxi { j}w w= .Шаг 2. Задача направляется в очередь локальной СУР подсистемы j*, послечего осуществляется доставка файлов задачи на эту подсистему.Ранжирование подсистем по значению функции F(j) позволяет учесть времядоставки файлов задачи до подсистем, а также их относительную загруженность.2 . 2 . А л г о р и т м д и с п е т ч е р и з а ц и и н а о с н о в ер е п л и к а ц и и з а д а ч ( Д Р )Шаг 1. Из окрестности S(i) выбирается m подсистем 1 2 , , ,m j∗ j∗ j∗ … в порядке не-убывания значений функции F(j).Шаг 2. Задача одновременно направляется в очереди локальных СУР подсис-тем 1 2 , , ,m j∗ j∗ j∗ … , после чего осуществляется доставка файлов задачи до этих под-систем.Шаг 3. С интервалом времени ƒ диспетчер i проверяет состояние задачи наподсистемах 1 2 , , ,m j∗ j∗ j∗ … и определяет подсистему j', на которой задача запущенана выполнение раньше других подсистем.Шаг 4. Задача удаляется из очередей локальных СУР подсистем, отличныхот j'.2 . 3 . А л г о р и т м д и с п е т ч е р и з а ц и и н а о с н о в ем и г р а ц и и з а д а ч ( Д М )Шаг 1. Из окрестности S(i) диспетчера i выбирается подсистема j* с мини-мальным значением F(j), j ƒ S(i).Шаг 2. Задача направляется в очередь локальной СУР подсистемы j*, послечего осуществляется доставка файлов задачи на эту подсистему.Шаг 3. Диспетчер i c интервалом времени ƒ запускает процедуру ДЛО поискаподсистемы j' для задачи в очереди диспетчера j*.Шаг 4. Если для найденной подсистемы выполняется условие F(j*) - F(j') > ƒ,то выполняется миграция задачи в очередь подсистемы j' (задача удаляется изочереди диспетчера j*).2 . 4 . А л г о р и т м д и с п е т ч е р и з а ц и и н а о с н о в ер е п л и к а ц и и и м и г р а ц и и з а д а ч ( Д Р М )Алгоритм основан на комбинации двух подходов - назначения на несколькоподсистем и миграции из очереди.Важно отметить, что вычислительная сложность поиска подсистем предло-женными алгоритмами не зависит от количества H подсистем, так как поиск осу-ществляется только в пределах локальных окрестностей диспетчеров. Это обеспе-чивает применимость алгоритмов в большемасштабных пространственно-распре-делённых ВС.3. Программный пакет GBrokerдецентрализованной диспетчеризации задачВсе предложенные алгоритмы были реализованы в пакете GBroker [9] децен-трализованной диспетчеризации параллельных задач в пространственно-распределённых ВС. Пакет разрабатывается Центром параллельных вычисли-тельных технологий ФГОБУ ВПО «Сибирский государственный университет те-лекоммуникаций и информатики» (ЦПВТ ФГОБУ ВПО «СибГУТИ»), совместно сЛабораторией вычислительных систем Института физики полупроводниковим. А.В. Ржанова СО РАН (ИФП СО РАН). Он включает в себя диспетчерGBroker, модуль интерфейса GClient и системы мониторинга NetMon и DCSMon.Модуль GBroker реализует алгоритмыРис. 2. Тестовая конфигурация мультикластерной ВС (H = 6, N = 130)Генерировались простейшие потоки c различной интенсивностью ƒ поступле-ния задач, которые псевдослучайно с равномерным распределением выбиралисьиз тестового набора. Каждый поток формировался из M задач. Ранг r каждой за-дачи выбирался из множества {1, 2, 4, 8} псевдослучайно с равномерным распре-делением.Обозначим через tk время поступления задачи k  {1, 2, …, M} на вход диспет-чера, tk - время начала решения задачи k, tk - время завершения решения задачиk. Пусть ƒ - суммарное время обслуживания потока из M задач.Для оценки эффективности алгоритмов диспетчеризации использовались сле-дующие показатели: пропускная способность B системы, среднее время T обслу-живания задачии среднее время W пребывания задачи в очереди:B = Mƒ,11 ( )Mk kkT t tM == ƒ − ,11 ( )Mk kkW t tM == ƒ  − .4 . 1 . С р а в н и т е л ь н ы й а н а л и з а л г о р и т м о вНа рис. 3 и 4 приведены результаты сравнения эффективности алгоритмовДЛО, ДР, ДМ и ДРМ при обслуживании потока из M = 200 задач. Поток задач по-ступал на подсистему Xeon80, локальные окрестности диспетчеров имели струк-туру полного графа.Рис. 3. Сравнение эффективности алгорит-мов ДЛО и ДР: 1 - Алгоритм ДЛО; 2 - Ал-горитм ДР, m = 2; 3 - Алгоритм ДР, m = 3;4 - Алгоритм ДР, m = 6Рис. 4. Сравнение эффективности алгорит-мов ДЛО, ДМ и ДРМ: 1 - Алгоритм ДМ; 2 -Алгоритм ДЛО; 3 - Алгоритм ДРМ, m = 2;4 - Алгоритм ДРМ, m = 3Пропускная способность системы при использовании алгоритма ДР дляm  {2, 3} выше пропускной способности при использовании алгоритма ДЛО. Де-градация показателей при больших значениях m связана с увеличением загрузки ка-налов связи при передаче входных файлов одной задачи на несколько сегментов.В алгоритмах ДМ и ДРМ интервал поиска подсистемы ƒ = 30 с, условие ми-грации ƒ = 0,2. Наименьшие среднее время обслуживания задач и среднее времяожидания в очереди достигнуты при использовании алгоритмов ДЛО и ДМ(рис. 4), при этом большая пропускная способность системы получена для ДМ.Алгоритмы ДР и ДРМ рекомендуется применять в случае малой интенсивностипотоков задач или небольших размеров входных данных.Рис. 5. Влияние структур локальных окрест-ностей диспетчеров на эффективность дис-петчеризации: 1 - полный граф; 2 - звезда;3 - кольцо; 4 - решетка; 5 - 2D-тор; 6 - D2-графРис. 6. Сравнение эффективности диспетче-ров GBroker и GridWay: 1 - GBroker; 2 -GBroker, полный граф; 3 - GBroker, 2D-тор;4 - GridWayПри большой интенсивности потока задач значительно возрастает время дос-тавки входных данных вследствие повышения загрузки каналов связи и сетевойфайловой системы на сегментах. Это приводит к снижению пропускной способ-ности системы и увеличению времени обслуживания задач (ожидания в очереди)для всех алгоритмов диспетчеризации.4 . 2 . В ы б о р с т р у к т у р ы л о к а л ь н ы х о к р е с т н о с т е йд и с п е т ч е р о вВыполнено исследование влияния структуры локальных окрестностей диспет-черов на эффективность диспетчеризации. В эксперименте на вход всех диспетче-ров одновременно поступали потоки из M = 50 задач. Рассматривались локальныеокрестности в виде полных графов, колец, решёток, звёзд, 2D-торов и D2-графов [1].На рис. 5 показано влияние структуры локальных окрестностей диспетчеровна эффективность обслуживания потоков задач алгоритмом ДМ. Высокие значе-ния пропускной способности, помимо полносвязной структуры, были полученыдля конфигураций на основе 2D-тора, решётки и D2-графа, при этом для двух по-следних были достигнуты наибольшие значения. Использование неполносвязныхструктур при формировании локальных окрестностей диспетчеров не приводит кзначительному снижению показателей эффективности диспетчеризации. Такиеструктуры могут быть образованы при отсутствии прямых линий связи между от-дельными подсистемами, например в случае отказов некоторых подсистем. В ка-честве структур локальных окрестностей могут быть рекомендованы торы или Dn-графы, которые обладают малым (средним) диаметром.4 . 3 . С р а в н и т е л ь н ы й а н а л и з д и с п е т ч е р о вGBr o k e r и G r i dWa yВыполнено сравнение эффективности обслуживания потоков задач централизо-ванным диспетчером GridWay и созданным децентрализованным пакетом GBroker.Для диспетчера GBroker проведено два эксперимента. В ходе первого на подсис-тему Xeon80 поступал поток из M = 300 задач. Во втором эксперименте моделиро-валось распределённое обслуживание задач: одинаковые потоки из M = 50 задачодновременно поступали в очереди диспетчеров всех 6 подсистем. При этом в каче-стве структур логических связей диспетчеров использовались 2D-тор и полныйграф, а в качестве алгоритма диспетчеризации - ДМ. Пакет GridWay установлен насегменте Xeon80 и настроен в соответствии с рекомендациями разработчиков.На рис. 6 видно, что пропускная способность диспетчера GBroker при обслу-живании нескольких потоков превосходит пропускную способность пакетаGridWay. Среднее время обслуживания и среднее время пребывания задач в оче-реди близки с GridWay и незначительно возрастают при централизованном об-служивании.ЗаключениеПо сравнению с централизованным подходом, предложенные алгоритмы де-централизованной диспетчеризации существенно снижают сложность поиска ре-сурсов и обеспечивает живучесть пространственно-распределённых ВС. По срав-нению с централизованным диспетчером GridWay была достигнута более высокаяпропускная способность (с использованием алгоритма ДМ), при сопоставимыхзначениях среднего времени обслуживания задачи.Механизм миграции, реализованный в алгоритмах ДМ, ДРМ, может использо-ваться для повышения пропускной способности системы (по отношению к ДЛО).При репликации задач на несколько подсистем (алгоритмы ДР, ДРМ) возрастаютнакладные расходы на доставку данных, что приводит к увеличению времени об-служивания задач.Созданный пакет GBroker является свободно распространяемым. Для органи-зации децентрализованной диспетчеризации задач в пространственно-распреде-лённой ВС достаточно установить пакет GBroker на всех подсистемах и выпол-нить конфигурацию диспетчеров в соответствии с выработанными рекоменда-циями. При формировании локальных окрестностей диспетчеров рекомендуетсяиспользовать структуры малого диаметра.

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