Модель и подход к планированию распределения ресурсов в гетерогенных Грид-системах
Запропоновано модель і підхід до планування обчислювальних ресурсів у дворівневій Грід-системі. Розроблено динамічну процедуру планування розподілу ресурсів у гетерогенному середовищі на базі розв’язання задачі про найменше покриття, а також програмний продукт, що реалізує імітаційну дискретно-подій...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Назва видання: | Проблемы управления и информатики |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/207534 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Модель и подход к планированию распределения ресурсов в гетерогенных Грид-системах / С.В. Листровой, С.В. Минухин // Проблемы управления и информатики. — 2012. — № 5. — С. 120–133. — Бібліогр.: 33 назви. - рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-207534 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-2075342025-10-12T00:16:33Z Модель и подход к планированию распределения ресурсов в гетерогенных Грид-системах Модель і підхід до планування розподілу ресурсів у гетерогенних Грід-системах Model and Approach to Scheduling Resources in Heterogeneous Grid-Systems Листровой, С.В. Минухин, С.В. Методы обработки информации Запропоновано модель і підхід до планування обчислювальних ресурсів у дворівневій Грід-системі. Розроблено динамічну процедуру планування розподілу ресурсів у гетерогенному середовищі на базі розв’язання задачі про найменше покриття, а також програмний продукт, що реалізує імітаційну дискретно-подійну модель планування. Наведено обчислювальні експерименти на основі програмної реалізації моделі, які обгрунтовують ефективність запропонованої моделі планування розподілу ресурсів у гетерогенних системах у вибраних метриках продуктивності роботи системи. Показано, що запропонована процедура планування дозволяє максимізувати завантаженість гетерогенних ресурсів системи, зменшити час виконання всієї черги завдань в Грід-системі порівняно з поширеним методом FCFS. Розглянуто реалізацію запропонованого методу в планувальнику MAUI. The model and approach to scheduling of computing resources in two-level Gridsystem is offered. Dynamic procedure of scheduling resources in the heterogeneous environment on the basis of the solution to the problem on the minimal co v er is developed. The software product realizing discrete-event model of scheduling is developed. Computing experiments on the basis of model program realization proving efficiency of offered model of scheduling resources in heterogeneous environments in chosen metrics of system performance are made. It is shown that the proposed procedure of scheduling allows maximizing the load of heterogeneous system resources, reducing the time allotted to perform the entire task queue in Grid-system compared to the method of FCFS. The realization of the proposed method in the MAUI sch eduler is presented. 2012 Article Модель и подход к планированию распределения ресурсов в гетерогенных Грид-системах / С.В. Листровой, С.В. Минухин // Проблемы управления и информатики. — 2012. — № 5. — С. 120–133. — Бібліогр.: 33 назви. - рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207534 518.854 10.1615/JAutomatInfScien.v44.i10.40 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Методы обработки информации Методы обработки информации |
| spellingShingle |
Методы обработки информации Методы обработки информации Листровой, С.В. Минухин, С.В. Модель и подход к планированию распределения ресурсов в гетерогенных Грид-системах Проблемы управления и информатики |
| description |
Запропоновано модель і підхід до планування обчислювальних ресурсів у дворівневій Грід-системі. Розроблено динамічну процедуру планування розподілу ресурсів у гетерогенному середовищі на базі розв’язання задачі про найменше покриття, а також програмний продукт, що реалізує імітаційну дискретно-подійну модель планування. Наведено обчислювальні експерименти на основі програмної реалізації моделі, які обгрунтовують ефективність запропонованої моделі планування розподілу ресурсів у гетерогенних системах у вибраних метриках продуктивності роботи системи. Показано, що запропонована процедура планування дозволяє максимізувати завантаженість гетерогенних ресурсів системи, зменшити час виконання всієї черги завдань в Грід-системі порівняно з поширеним методом FCFS. Розглянуто реалізацію запропонованого методу в планувальнику MAUI. |
| format |
Article |
| author |
Листровой, С.В. Минухин, С.В. |
| author_facet |
Листровой, С.В. Минухин, С.В. |
| author_sort |
Листровой, С.В. |
| title |
Модель и подход к планированию распределения ресурсов в гетерогенных Грид-системах |
| title_short |
Модель и подход к планированию распределения ресурсов в гетерогенных Грид-системах |
| title_full |
Модель и подход к планированию распределения ресурсов в гетерогенных Грид-системах |
| title_fullStr |
Модель и подход к планированию распределения ресурсов в гетерогенных Грид-системах |
| title_full_unstemmed |
Модель и подход к планированию распределения ресурсов в гетерогенных Грид-системах |
| title_sort |
модель и подход к планированию распределения ресурсов в гетерогенных грид-системах |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2012 |
| topic_facet |
Методы обработки информации |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/207534 |
| citation_txt |
Модель и подход к планированию распределения ресурсов в гетерогенных Грид-системах / С.В. Листровой, С.В. Минухин // Проблемы управления и информатики. — 2012. — № 5. — С. 120–133. — Бібліогр.: 33 назви. - рос. |
| series |
Проблемы управления и информатики |
| work_keys_str_mv |
AT listrovojsv modelʹipodhodkplanirovaniûraspredeleniâresursovvgeterogennyhgridsistemah AT minuhinsv modelʹipodhodkplanirovaniûraspredeleniâresursovvgeterogennyhgridsistemah AT listrovojsv modelʹípídhíddoplanuvannârozpodíluresursívugeterogennihgrídsistemah AT minuhinsv modelʹípídhíddoplanuvannârozpodíluresursívugeterogennihgrídsistemah AT listrovojsv modelandapproachtoschedulingresourcesinheterogeneousgridsystems AT minuhinsv modelandapproachtoschedulingresourcesinheterogeneousgridsystems |
| first_indexed |
2025-10-12T01:08:49Z |
| last_indexed |
2025-10-13T01:09:14Z |
| _version_ |
1845826949275975680 |
| fulltext |
© С.В. ЛИСТРОВОЙ, С.В. МИНУХИН, 2012
120 ISSN 0572-2691
МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ
УДК 518.854
С.В. Листровой, С.В. Минухин
МОДЕЛЬ И ПОДХОД К ПЛАНИРОВАНИЮ
РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
В ГЕТЕРОГЕННЫХ ГРИД-СИСТЕМАХ
Введение
Технологии Грид используются для создания географически распределенной
вычислительной инфраструктуры, объединяющей различные типы ресурсов с
коллективным доступом к ним в рамках виртуальных организаций. Отметим ак-
туальность исследований, проводимых в направлении повышения эффективности
Грид-систем, которая подтверждается многочисленными научными работами
отечественных и зарубежных авторов [1–9]. Одной из наиболее важных и слож-
ных задач организации распределенных вычислений в Грид-системе является
распределение заданий на ресурсы. В условиях коллективного характера процес-
сов функционирования Грид-системы планирование, т.е. распределение ресурсов
для выполнения заданий пользователей, являясь частью системы диспетчериза-
ции [6–10], предназначено для координации процессов планирования ресурсов для
выполнения на них заданий. Сложность задачи распределения ресурсов или дина-
мического планирования обусловлена неоднородностью как объекта распр еделения
(ресурсов), так и распределяемых заданий. Если учитывать свойство неоднородно-
сти Грид-системы, то такое распределение не всегда приводит к равномерной за-
грузке ресурсов [11] и требует применения в современных планировщиках новых
процедур планирования, учитывающих и приоритетность выполняемых заданий,
и неоднородность элементов системы. Выделим методы планирования, использу-
ющие пакетные режимы, в которых задания выбираются и планируются пакетами,
исследованные в работах [12–14].
Отметим, что анализ таких сложных процессов в настоящее время проводит-
ся на основе моделирования Грид-систем [15, 16], осуществляемого на реальных
данных используемой Грид-инфраструктуры и реальных данных работы Грид-
систем. Как показали полученные в этих работах результаты, имеющие теорети-
ческое и практическое значение, моделирование становится эффективным ин-
струментом исследования новых подходов и к планированию ресурсов.
Постановка задачи
Основная идея, положенная в основу предлагаемого в данной работе подхо-
да, заключается в использовании в качестве процедуры планирования задачи о
наименьшем покрытии (ЗНП), представляющей собой задачу линейного булевого
программирования [6], постановка которой предлагается в таком виде:
min)(
1
kj
n
j
t txL (1)
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 5 121
при ограничениях
,1)(
1
kjij
n
j
tx ;,1 mi };1,0{ij }.1,0{)( kj tx (2)
Здесь m — количество заданий, подлежащих планированию; n — количество ре-
сурсов исследуемой системы, доступных и свободных на момент планирования;
].,[ 0 nk TTt
Планирование осуществляется на интервале времени ],,[ 0 nTT где 0T — вре-
мя начала планирования; nT — время окончания планирования заданий.
Задачу (1), (2) можно рассматривать как задачу определения минимального
числа столбцов в булевой матрице В, покрывающего единицами все строки дан-
ной матрицы, элементы которой в контексте планирования интерпретируются
следующим образом: столбцам соответствуют свободные на момент планирова-
ния ресурсы системы, а строкам — задания, подлежащие планированию и кото-
рые должны быть решены на этих ресурсах.
Подход базируется на следующих положениях, характеризующих его отли-
чительные особенности.
1. Система планирования организована в виде двухуровневой структуры, на
первом уровне выбираются задания (пакет заданий), подлежащие планированию,
к ним применяется метод решения задачи (1), (2); затем задания, выбранные как
результат ее решения, назначаются на доступные и свободные на момент плани-
рования ресурсы и решаются на них под управлением локального планировщика.
2. Метод планирования на каждом шаге планирования максимально загружает
минимальное количество ресурсов, свободных и доступных на момент планирова-
ния. Таким образом, для последующего распределения заданий очереди количество
ресурсов для возможного назначения на них заданий будет максимальным.
3. Алгоритм решения задачи (1), (2) должен иметь малую временную слож-
ность его реализации для минимизации времени, отводимого на процесс планиро-
вания заданий для их решения на ресурсах.
4. Система планирования использует пакетную технологию: задания, органи-
зованные в форме пакета (пула) заданий, выбираются из глобальной очереди, по
мере их планирования на ресурсы помещаются в пакет заданий на назначенный
ресурс (ресурсы) и передаются на решение на этот ресурс (ресурсы).
5. На моменты планирования kt задания m независимы и n ресурсов в систе-
ме доступны и свободны.
Таким образом, цель исследования — разработать новый подход к планиро-
ванию ресурсов в Грид-системе на основе математической модели ЗНП (1), (2),
положений подхода (1)–(5) и обосновать его эффективность на основе метрик
производительности работы Грид-системы.
Базовая конструкция и принципы работы модели
Для описания конструкции и работы предлагаемой модели используем сле-
дующие понятия и определения. В качестве базовой архитектуры модели выбир а-
ется архитектура вычислительной Грид-системы, использующая двухуровневую
структуру: на первом уровне находится система планирования ресурсов (класте-
ров) Грид-системы (планировщик первого уровня), на втором — локальном
уровне — осуществляется локальное планирование заданий на ресурсе (локаль-
ный планировщик), предназначенное для планирования решения назначенных на
данный ресурс заданий [17–22].
122 ISSN 0572-2691
В двухуровневой архитектуре Грид-системы предлагается использовать сле-
дующие компоненты:
— глобальная очередь, которая формируется по мере поступления заданий
пользователей для их решения в Грид-систему; глобальная очередь характеризу-
ется размером LGlQuer , — количеством заданий, поступивших на их решение в
Грид-систему за время формирования очереди TGlQuer;
— промежуточный пул заданий, выбранных из глобальной очереди, имеет раз-
мер Lpool (Lpool ≤ LGlQuer), размер пула может определяться, например, периодичн о-
стью процесса планирования, интенсивностью входного потока заданий и т.д.;
— пакет заданий, формируемый как результат обработки заданий пула на ос-
нове решения задачи о наименьшем покрытии, имеющий определенный размер
Lpacket;
— ресурсы ,jR представляющие собой кластеры Грид-системы, на которых
будут решаться задания, спланированные планировщиком первого уровня.
Последовательность обработки заданий, находящихся в глобальной очереди,
представляет циклический процесс планирования, который можно представить
в виде динамической процедуры D, состоящей из следующих этапов.
Процедура D.
1. Из глобальной очереди в соответствии с приоритетами заданий выбирают-
ся задания до тех пор, пока пул заданий не будет полностью заполнен. После пла-
нирования очередь заданий, находящаяся в пуле, разбивается на k пакетов неко-
торой фиксированной длины, где k — число гетерогенных кластеров, на которые
должны отправляться пакеты заданий.
2. Заполнение пакетов заданий осуществляется на основе решения ЗНП, при
этом исходными данными для ее решения является таблица соответствия, постр о-
енная для заданий, вошедших в пул. На этом этапе определяется минимальное ко-
личество кластеров, на которых задания, вошедшие в пул, могут быть выполнены.
При этом сначала формируется пакет заданий на кластер, который вошел в
наименьшее покрытие, и на нем возможно решение наибольшего количества за-
даний, далее формируется пакет на кластер из покрытия с наибольшими возмож-
ностями по решению заданий среди оставшихся кластеров, принадлежащих по-
крытию, и т.д. Если очередь заданий начинает превышать размер пакета заданий
на кластер (т.е. пакет заданий на данный кластер сформирован), задание помеща-
ется в любой другой пакет, соответствующий тому кластеру, на котором его мож-
но выполнить. Если все пакеты сформированы, то задание отправляется обратно в
пул заданий для последующего распределения совместно с заданиями, которые
поступили в пул из общей (глобальной) очереди.
3. Далее по мере освобождения ресурсов (кластеров) задания из пакетов за-
даний отправляются на решение локальным планировщиком.
Процесс планирования на основе процедуры D в цикле повторяется до тех пор,
пока вся глобальная очередь заданий не будет обслужена. Новизна предлагаемого
подхода заключается в использовании процесса планирования Грид-системы на ос-
нове предлагаемого метода планирования, использующего двухуровневую структу-
ру и пакетный режим планирования (в отличие от Грид-систем, работающих непо-
средственно с очередями, в которых реализован централизованный планировщик,
например FCFS (First Come First Served), SJF (Shortest Job First), и задания из очереди
выбираются по одному и сразу же отправляются на любой доступный и свобо дный
ресурс). Учитывая, что начало следующего действия обработки каждого задания
непосредственно начинается после окончания предыдущего и происходит только в
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 5 123
заданной последовательности, можно сделать
вывод, что в условиях нестационарности посту-
пающих заданий предлагаемая модель относится
к классу дискретно-событийных имитационных
моделей. Отметим, что такие модели рассмотре-
ны в работах [24, 25] и показали свою эффектив-
ность при использовании в Грид-системах.
Будем рассматривать гетерогенную среду, состоящую из различных типов ре-
сурсов }{ jR и в которую поступает поток различных типов заданий }{ itask (рис. 1).
В общей очереди заданий каждое задание характеризуется набором требова-
ний–характеристик )...,,( 21
task
m
tasktask , в качестве которых может быть тип
процессора, объем требуемой для выполнения заданий памяти, тип ОС, требова-
ния к времени решения и т.д. Гетерогенность системы проявляется в том, что за-
дания }{ itask имеют различные характеристики и могут выполняться только на
определенных типах ресурсов из множества }{ jR . Задания глобальной очереди
распределяются на основе принципа раздельного распределения заданий на ре-
сурсы jR (рис. 2).
Глобальная
очередь
Пул заданий
планировщик
Пакет заданий на ресурс
Локальная очередь 1
Пакет заданий на ресурс
Локальная очередь 2
Пакет заданий на ресурс
Локальная очередь n
1R
2R
nR
Рис. 2
Рассмотрим процесс формирования пакетов заданий, имеющих ограниченные
размеры, т.е. очередей на ресурсы (кластеры).
Формирование очередей реализуем с помощью таблицы (матрицы) соответ-
ствия, показывающей, какие задания на каком ресурсе могут быть решены (вы-
полнены) с учетом того, что на одном ресурсе может выполняться несколько за-
даний (табл. 1).
Таблица 1
Задания
Ресурсы
Задания
Ресурсы
1R
2R
3R
4R
5R
6R
7R
8R
1R
2R
3R
4R
5R
6R
7R
8R
1task 1 13task 1
2task 1 1 1 14task 1
3task 1 1 15task 1 1 1
4task 1 1 16task 1
5task 1 1 1 17task 1 1 1
6task 1 1 18task 1
7task 1 1 19task 1
8task 1 1 20task 1 1 1
9task 1 21task 1 1 1 1
10task 1 1 1 22task 1
11task 1 1 23task 1 1 1 1
12task 1 1 1 24task 1
}{ jR Среда обмена
информацией }{ itask
Рис. 1
124 ISSN 0572-2691
В ячейках {i, j} таблицы соответствия проставляется значение «1», если зада-
ние itask может быть выполнено на ресурсе jR . При использовании для плани-
рования алгоритмов типа FCFS — очередь формируется последовательно, задания
отправляются в соответствии с их приоритетом на имеющийся на данный момент
времени свободный ресурс (кластер), позволяющий решать данный тип задания.
Особенность работы гетерогенной системы с большим количеством ресурсов за-
ключается в том, что некоторые задания могут быть выполнены только на опре-
деленных типах ресурсов, а другие — на этих же типах ресурсов и еще дополни-
тельно на нескольких других типах ресурсов. Поэтому при произвольном разме-
щении заданий в пакеты может возникать неравномерность загрузки кластеров.
Для устранения этих проблем предлагается задания распределять на класте-
ры на предыдущем шаге планирования таким образом, чтобы подготовить на по-
следующем шаге максимально большее количество свободных кластеров для вы-
полнения на них поступающих заданий. Для этого предлагается метод отображе-
ния процесса разрешения заданий глобальной очереди на локальные очереди на
ресурсы на основе динамического решения ЗНП (1), (2) с использованием мето-
дов, рассмотренных в [6].
Модель планирования на основе ЗНП, вычислительный эксперимент
и анализ полученных результатов
Для пояснения работы предлагаемого подхода и модели рассмотрим следу-
ющий пример.
Пример. Пусть глобальная очередь содержит 24 задания, а размер пула зада-
ний — не больше 12 заданий. Формирование локальных очередей осуществляется
в пакетах, позволяющих разместить в них не больше четырех заданий. На первом
этапе формирования локальных очередей в пул заданий планировщик из общей
очереди на основе приоритетов выбирает набор заданий (1–12) (см. табл. 1).
Для сравнения рассмотрим два варианта формирования локальных очередей
к кластерам.
Вариант 1. По табл. 1 на основе процедуры типа FCFS будем формировать
пакеты заданий на кластеры. Для удобства упорядочим этот процесс: сначала
назначим все возможные задания на
первый кластер, и если очередь превы-
шает размер пакета, то переносим зада-
ние на следующий кластер, который в
соответствии с табл. 1 может его вы-
полнить. Затем процедуру повторяем
для второго кластера и так до тех пор,
пока не выберем все задания из пула.
Далее из глобальной очереди загружа-
ем в пул следующие задания из очере-
ди (13–24) (см. табл. 1) и по этой же
схеме формируем пакеты на остальные кластеры. В результате получаем пакеты
заданий (табл. 2). Как видно из табл. 1, задания (13, 22, 14, 18, 19, 24) в пакет за-
даний на кластер не попадают и отправляются обратно в пул.
Вариант 2. Формируем очереди на основе решения ЗНП. Как видно из табл. 1,
наименьшее покрытие определяется кластерами .;; 531 RRR Они могут решать по
одинаковому количеству заданий, поэтому заполняем очереди заданий на них
в произвольном порядке: например, сначала формируем очередь к 1R (1, 3, 6, 12),
затем — к 3R (2, 4, 5, 10) и к 5R (7, 8, 9, 11). Далее в пул на основе решения ЗНП
перегружаются оставшиеся в очереди задания (13–24) (табл. 3). Снова формируем
Таблица 2
1R 1 3 6 12 13 22
2R 2 5 10 11 14 18 19 24
3R 4
4R 16 23
5R 7 8 9 21
6R 20
7R 15 17 23
8R
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 5 125
очереди на основе решения ЗНП — в дан-
ном случае наименьшее покрытие вклю-
чает кластеры ;1R ;2R ;4R .7R Здесь
максимальное число заданий решается на
кластере ,7R поэтому формирование
очереди начинаем к нему (15, 17, 20, 21).
При этом задание 23 не попадает в пакет
заданий на данный кластер и после пе-
репланирования ставим его в очередь
к .4R Далее выстраиваем очередь к кластерам 2R (14, 18, 19, 24), 4R (16) и кла-
стеру 1R (13, 22). Они в пакет заданий не могут попасть, поскольку он сформиро-
ван, и поэтому возвращаются обратно в пул для последующего распределения на
основе предложенной процедуры.
Далее планирование выполнения заданий, находящихся в очередях к класте-
рам, может быть реализовано программными средствами планировщиков MAUI
и, например, PBS (Portable Batch System) или TORQUE
Таким образом, из сравнения табл. 2 и 3 следует, что при случайном формиро-
вании локальных очередей на основе метода FCFS задания (13, 22, 14, 18, 19, 24)
получают дополнительную задержку , и свободным для последующей работы
остается только кластер 8R , а во втором случае дополнительную задержку полу-
чат только задания (13, 22). Это обусловлено наличием большего количества за-
даний, требующих для их выполнения кластер 1R . Во втором случае количество
освобожденных кластеров оказывается на один больше.
Рассмотренный пример показывает, что случайное формирование локальных
очередей на основе метода FCFS в гетерогенных системах может привести к
большой неравномерности загрузки ресурсов и их неэффективному использова-
нию, а применение процедуры D для планирования очередей на основе решения
ЗНП обеспечивает максимальную загрузку каждого кластера.
Для практической реализации процедуры D выбран эффективный прибли-
женный алгоритм решения ЗНП, рассмотренный в работе [6]. Для проверки э ф-
фективности предложенного подхода к планированию ресурсов разработана про-
граммная реализация модели GRID_Scheduler_Model, реализующая имитацио н-
ную дискретно-событийную модель функционирования гетерогенной Грид-сис-
темы (рис. 3), включающую следующие функциональные элементы.
1. Глобальная очередь заданий — задания (заявки, требования, приложения),
которые подаются на систему для моделирования процесса работы системы.
2. Промежуточный пул заданий — буфер, в который загружаются задания из
глобальной очереди, для которых осуществляется планирование ресурсов.
3. Планировщик — программный модуль, который распределяет на основе
выбранного метода планирования задания, находящиеся в пуле, по пакетам для
отправки на свободные ресурсы (кластеры).
4. Модель времени (модельное время) — в качестве модели времени выбрана
условная единица времени работы системы — такт; один такт включает выполне-
ние в модели трех операций:
операция № 1 — помещение входных заданий в пул;
операция № 2 — распределение заданий пула между ресурсами и возврат
не назначенных на ресурсы заданий обратно в пул;
операция № 3 — имитация решения заданий ресурсами, на которые они
были распределены.
Таблица 3
1R 1 3 6 12 13 22
2R 14 18 19 24 14 18
3R 2 4 5 10
4R 23 16
5R 7 8 9 11
6R
7R 15 17 20 21
8R
126 ISSN 0572-2691
5. Модель задания — определяется сложностью задания, задаваемой в тактах:
более сложное задание требует для его выполнения большего количества тактов.
6. Пакет заданий — набор заданий, направляемых на те ресурсы, на которых
данные типы заданий могут быть выполнены.
7. Ресурсы — элементы, моделирующие процесс выполнения заданий, кото-
рые были на них распределены, производительность которых определяется чис-
лом тактов, необходимых для выполнения задания.
8. Задержка — характеризует коммуникационную задержку передачи дан-
ных, приложений, используемых в информационной системе, передаваемых из
пакета заданий для выполнения на кластеры, определяется в тактах.
User
Пользо-
ватель
Глобальная
очередь
заданий
Промежу-
точный
пул
заданий
Задания Плани-
ровщик
Формиро-
вание пакета
заданий
на ресурс
Пакет заданий
на ресурс
сформирован?
Пакет
заданий
Да
Ресурс
(кластер)
Domain
Пакет заданий
на ресурс
сформирован?
Пакет
заданий
Да
Ресурс
(кластер)
Domain
Пакет заданий
на ресурс
сформирован?
Пакет
заданий
Да
Ресурс
(кластер)
Domain
Операция № 1
Помещение заданий в пул
Операция № 2
Распределение заданий между
ресурсами и возврат не
поместившихся заданий в пул
Операция № 3
Обработка заданий
Формиро-
вание пакета
заданий
на ресурс
Формиро-
вание пакета
заданий
на ресурс
Нет
Нет
Нет
Рис. 3
Для моделирования процесса планирования использовалась прямоугольная
матрица, строки которой соответствуют номерам заданий, столбцы — номерам
ресурсов. При этом если значение ячейки таблицы ,1ijm то это означает, что
i-е задание решается j-м ресурсом. Количество ресурсов, с помощью которых мо-
жет быть решено im -е задание, задается по одному из случайных законов (равно-
мерному, Пуассона, экспоненциальному). Количество ресурсов, с помощью кото-
рых может быть решено im -е задание, в рассмотренной модели задается по одному
из случайных законов (равномерному, нормальному), постоянной величине и опре-
деляется параметром «универсальность задания», который задается как определен-
ный процент общего количества ресурсов, на которых может быть выполнено дан-
ное задание.
Для сравнительного анализа эффективности предложенного метода с други-
ми в программе GRID_Scheduler_Model реализованы следующие методы плани-
рования:
FCFS (First Come First Served) — метод распределяет задания по принципу
«первый пришел — первым обслужился», т.е. в порядке их поступления (в порядке
очереди), выбирая при этом для задания свободный и доступный ресурс и центра-
лизованный метод планирования ресурсов в Грид [14, 23]. Планировщик выбирает
первое задание из пула и пробует поместить его в пакет заданий на один из свобод-
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 5 127
ных ресурсов, на котором оно может быть решено. Если операция выполнена
успешно, то планировщик переходит к новому заданию, если нет — возвращает его
в пул, при этом оно остается первым в пуле и переходит к следующему заданию.
MC (Minimal Cover) — метод, основанный на реализации процедуры D.
Постановка эксперимента и анализ результатов
на основе метрик производительности работы системы
В качестве метрик производительности работы модели системы использова-
лись среднее время выполнения задания, время выполнения всех заданий очереди
и коэффициент использования ресурсов [14, 26].
Для данной модели время выполнения одного задания определяется по фо р-
муле: ,runpackageschedpoolexecutive iiiii ttttt где poolit — время нахождения
i-го задания в пуле, в тактах; schedit — время планирования i-го задания, в тактах;
packageit — время нахождения i-го задания в пакете, в тактах; runit — время ре-
шения i-го задания, в тактах.
Тогда среднее время выполнения одного задания определится по форм уле:
,
1
executive
1
ecutiveav_time_ex i
N
i
t
N
t
где N — количество заданий, находящихся в
глобальной очереди.
Время выполнения всех заданий очереди ,NT в тактах, рассчитывается по
формуле: ,firstlast TTTN т.е. это время работы имитационной модели, начиная
от момента поступления первого задания при формировании глобальной оч ереди
и заканчивая моментом завершения выполнения последнего задания .lastT
Коэффициент использования (загрузки) ресурса jR определяется по форму-
ле: ,util / NR TTK
j
где
jRT — время выполнения всех заданий глобальной оче-
реди на ресурсе jR , в тактах.
Кроме этого, рассчитывался коэффициент выигрыша по времени выполнения
всех заданий в очереди: ),MC(/)FCFS(gain NN TTK где )FCFS(NT — время вы-
полнения очереди заданий при использовании в качестве планировщика процеду-
ры FСFS; )MC(NT — время выполнения той же очереди заданий при использо-
вании в качестве планировщика процедуры МС.
При моделировании исследовались зависимости времени выполнения всех за-
даний глобальной очереди, исходя из количества заданий в очереди при различных
сложностях решаемых заданий и различной производительности ресурсов, а также
зависимость коэффициента использования ресурсов гетерогенной Грид-систем ы от
количества решаемых заданий. При этом коэффициент использования гетерогенной
Грид-системы рассчитывался как отношение общего количества тактов, выполнен-
ных ресурсами, работающими на каждом такте выполнения заданий, к общему ко-
личеству тактов, которое может быть выполнено всеми ресурсами системы за время
выполнения всех заданий глобальной очереди. Анализ полученных зависимостей
проведен для различных законов поступления и обслуживания заданий — равно-
мерного закона, закона Пуассона и экспоненциального.
Результаты экспериментальных исследований получены с доверительной веро-
ятностью 95 %, приведены в виде графиков на рис. 4, 5 при таких исходных данных:
сложность решаемых заданий — 1000 тактов, количество ресурсов в системе — 100,
производительность каждого ресурса, в тактах — 100; размер пула, характеризую-
щий максимальное количество заданий, которые система м ожет принять для даль-
нейшей обработки, и размер пакета заданий на ресурс равны 100.
На рис. 4 видно, что для метода MC при небольшом количестве заданий
наибольшее время выполнения заданий у потока с равномерным законом, а при
128 ISSN 0572-2691
большом — у экспоненциального (наибольшая очередь перед ресурсами). Анало-
гично у метода FCFS наиболее трудоемким является экспоненциальный закон рас-
пределения (см. рис. 5).
0
1
2
3
4
5
6
7
2000 4000 6000 10000 12000
Количество заданий
TN 10
4
, такт
экспоненциальный
равномерный
8
9
10
8000
Пуассона
Рис. 5
На рис. 6 приведена динамика ко-
эффициента использования для системы
при изменении количества кластеров от
10 до 90, из которого следует, что коэф-
фициент загрузки при использовании
процедуры планирования типа FCFS
меньше, чем в случае применения проце-
дуры МС. При этом использование мето-
да MC позволяет уменьшить время вы-
полнения всех заданий, а выигрыш со-
ставляет )MC(/)FCFS(gain NN TTK
,4,165337/92633 где )FCFS(NT — время выполнения очереди заданий при
использовании в качестве планировщика процедуры FCFS; )MC(NT — время
выполнения той же очереди заданий при использовании в качестве планировщика
процедуры МС, время задано в тактах работы ресурсов. Экспериментальное ис-
следование показало, что данный выигрыш может достигать значения 10 и больше.
На рис. 7, 8 показаны зависимости среднего времени выполнения задания и
коэффициента использования ресурсов от количества заданий в глобальной оч е-
реди, из которых следует, что среднее время выполнения задания при использо-
вании процедуры планирования на основе МС по сравнению с FCFS в четыре раза
меньше и при этом коэффициент использования ресурсов больше.
0
0,1
0,2
0,3
0,4
0,5
0,6
Kutil
1000 3000 5000 7000 9000
Количество заданий
MC, 10 ресурсов
FCFS, 10 ресурсов
Рис. 8
0
1
2
3
4
5
6
7
2000 4000 6000 8000 10000 12000
Количество заданий
TN 10
4
, такт
экспоненциальный
Пуассона
равномерный
Рис. 4
0
0,1
0,2
0,3
0,4
0,5
0,6
10 20 30 40 50 60 70 80 90
Количество ресурсов
Kutil
MC
FCFS
Рис. 6
0
1
2
3
4
5
6
7
8
9
1000 3000 5000 7000 9000
Количество заданий
MC, 10 ресурсов
FCFS, 10 ресурсов
Tav_time_executive 10
2
Рис. 7
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 5 129
Таким образом, сравнительный анализ планировщиков на основе процедуры MC
и FCFS при моделировании их работы в Грид-системе показывает, что планирование
на основе процедуры MC позволяет обеспечить выигрыш во времени выполнения
всех заданий, находящихся в глобальной очереди Грид-системы, и обеспечивает
большую загрузку всех ресурсов по сравнению с процедурой планирования на основе
FСFS.
Поскольку равномерный закон распределения оказался наиболее «тяжелым»
для планирования, то для него приведены результаты исследования зависимости
таких характеристик планирования, как время разрешения очереди (время выпол-
нения всех заданий очереди) и коэффициента использования ресурсов от размера
пакета заданий и количества ресурсов системы. Трехмерные графики, отражаю-
щие взаимосвязь перечисленных характеристик, построенные с помощью пакета
STATISTICA, представлены на рис. 9, 10. Так, на рис. 9 приведен график зависи-
мости времени выполнения заданий (Z) от размера пакета заданий (y) и количе-
ства ресурсов (x) при использовании планировщика МС и равномерном законе
распределения характеристик системы:
,0,0030,0030,0052,43,5893,2 22 yxyx yxZ
а на рис. 10 — график зависимости коэффициента использования ресурсов (Z) от
размера пакета заданий (y) и количества ресурсов (x) при использовании процеду-
ры планирования МС и равномерном законе распределения:
.yxyxyxZ 22 0,00000630,00000710,0000130,00060,00130,43
Анализ графиков, приведенных на рис. 9, 10, позволяет сделать важные для
последующих исследований выводы.
Аналитические выражения поверхностей полученных зависимостей (см. рис. 9, 10)
имеют квадратичный характер, функции поверхностей выпуклы и имеют локаль-
ный минимум. Следовательно, по результатам моделирования реальной Грид-
системы можно определить оптимальные соотношения между моделируемыми
параметрами на основе определения значений, доставляющих им минимум , и та-
ким образом повысить ее производительность.
Задавая требуемые ограничения (требования) на значения параметров произ-
водительности (например, коэффициента загрузки и врем ени решения всех зада-
ний), можно моделировать и прогнозировать значения отдельных параметров моде-
лируемых Грид-систем с учетом возможной динамики потоков заданий, например
размеры пакета заданий и пула, в зависимости от интенсивности поступающего
в глобальную очередь Грид входного потока заданий пользователей.
Z
x
y
0
100
200
300
400
500
600
0,1
0,2
0,3
0,4
0,5
100 200 300
400 500
0
600
Рис. 10
Z
x
y
0
100 200
300 400 500 600
0
200
400
600
800
1000
1200
1400
1600
100
200
300
400
500
Рис. 9
130 ISSN 0572-2691
Программная реализация предложенного подхода и модели в пакете GridSim
[27] продемонстрировала хорошее совпадение результатов моделирования в Grid-
Sim [28] с результатами, полученными в данной работе. При этом, как показали
исследования на реальных потоках заданий, выполнявшихся на коммерческих
кластерах Грид [29] за период 2005–2006 гг., планировщик на основе процедуры
MC при динамике изменений нагрузки 20–50 % обеспечивает равномерность за-
грузки ресурсов, а планировщик на основе процедуры планирования FCFS может
оставлять незагруженными до 40 % общего количества ресурсов.
Динамическая балансировка загрузки ресурсов. Важным вопросом, требую-
щим решения, является проблема балансировки загрузки. К настоящему времени
имеется значительное количество публикаций, среди которых отметим [10, 30, 31],
а также статьи, посвященные разработке гибридных методов балансировки [32].
Для данного подхода можно предложить следующий вариант политики балан-
сировки загрузки. Триггерная политика определяет период начала балансировки.
В данном случае ее можно реализовать, например, на основе комбинации статич е-
ской и динамической балансировки, используя принцип порогового значения.
Пороговое значение. Время нахождения в пакете заданий: определить
среднее время ожидания в пакете заданий на протяжении нескольких тактов пла-
нирования; если на текущем такте планирования время нахождения в пакете пр е-
высит среднюю за предыдущие такты или некоторую пороговую величину, нео б-
ходимо в процессе выбора ресурса (решения ЗНП) из нескольких подхо дящих
выбрать тот, на котором количество заданий в пакете на момент планирования
минимально.
Более конкретно разработка методов балансировки загрузки с учетом особен-
ностей предлагаемого подхода будет рассмотрена в дальнейших исследованиях.
Организация подключения алгоритма в планировщик MAUI. Алгоритм
планирования может быть встроен в планировщик MAUI, который сможет рас-
пределять задания по кластерам (ресурсам) и передавать их на менеджеры рас-
пределенных ресурсов TORQUE вычислительных кластеров.
Особенность планировщика MAUI заключается в том, что для Грид-кластера
он является внешним, поэтому в полном объеме не может выполнять метаплани-
рование на уровне Грид-системы. Вместе с тем он позволяет планировать распре-
деление заданий на уровне гетерогенных кластеров нескольких организаций или
нескольких виртуальных кластеров одной организации, что и составляет возмож-
ность практической реализации разработанного метода планирования.
Разработанный алгоритм планирования может быть добавлен в открытый код
программы MAUI 3.3.1 в рамках бесплатной версии OpenSource, а также в maui-3.3.1\
src\moab\MLocal.c для управления заданиями очереди MLocalQueueScheduleIJobs [33].
Приведем фрагмент программы вызова алгоритма планирования.
/* #include "../../contrib/sched/XXX.c" */
int MLocalQueueScheduleIJobs(
int *Q,
mpar_t *P)
{
mjob_t *J;
int jindex;
if ((Q == NULL) || (P == NULL))
{
return(FAILURE);
}
/* NOTE: insert call to scheduling algorithm here */
int MShed_MC(mjob_t *PackJ, mcres_t *PackR)
for (jindex = 0;Q[jindex] != -1;jindex++)
{
J = MJob[Q[jindex]];
/* NYI */
DBG(7,fSCHED) DPrint("INFO: checking job '%s'\n",
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 5 131
J->Name);
}
/* END for (jindex) */
return(FAILURE);
}
/* END MLocalQueueScheduleIJobs() */
/* END MLocal.c */
Вызов алгоритма может осуществляться различными способами: вставкой
программного кода по тексту или результатом вызова функции, которая передает
порядок заданий на свободные ресурсы.
Настройка структуры очередей и подключение планировщика приведена ниже.
pbs_server -t create
qmgr -c "set server scheduling=true"
qmgr -c "create queue batch queue_type=execution"
qmgr -c "set queue batch started=true"
qmgr -c "set queue batch enabled=true"
qmgr -c "set queue batch resources_default.nodes=1"
qmgr -c "set queue batch resources_default.walltime=3600"
qmgr -c "set server default_queue=batch"
В данном случае инициализируется настроечный алгоритм и активируется
планировщик (используя «scheduling=true»). Чтобы в очереди могли выполняться
задачи, нужно установить режим «execution». Дополнительные настройки (напри-
мер, установка параметров очереди «started» и «enabled») позволяют принимать за-
явки на выполнение задач и запускать поставленные в очередь задачи.
Заключение
В настоящей работе рассмотрен подход к планированию распределением ре-
сурсов в двухуровневой гетерогенной Грид-системе на основе решения ЗНП. Пред-
ложена базовая модель и общая схема работы двухуровневой гетерогенной Грид-
системы, использующая матрицу соответствия назначения заданий на доступные и
свободные ресурсы. Показано, что для нее можно использовать подход к планир о-
ванию выбора ресурсов на базе ЗНП. Основные особенности рассмотренного под-
хода заключаются в реализации процесса планирования с использованием пула за-
даний, выбираемых из глобальной очереди, пакета заданий, формируемого для вы-
полнения на кластеры и процедуры планирования на базе ЗНП, в совокупности
обеспечивающих преимущества метода, позволяющего максимизировать загрузку
ресурсов и оптимизировать временные характеристики работы Грид-системы.
Вычислительные эксперименты, проведенные с использованием програм м-
ной реализации рассмотренной модели, подтвердили эффективность предложен-
ного подхода по сравнению с известным и используемым в современных Грид-
системах методом FСFS на основе рассмотренных метрик производительности
Грид-системы.
С.В. Лістровий, С.В. Мінухін
МОДЕЛЬ І ПІДХІД ДО ПЛАНУВАННЯ РОЗПОДІЛУ
РЕСУРСІВ У ГЕТЕРОГЕННИХ ГРІД-СИСТЕМАХ
Запропоновано модель і підхід до планування обчислювальних ресурсів у дво-
рівневій Грід-системі. Розроблено динамічну процедуру планування розподілу
ресурсів у гетерогенному середовищі на базі розв’язання задачі про найменше
покриття, а також програмний продукт, що реалізує імітаційну дискретно-по-
дійну модель планування. Наведено обчислювальні експерименти на основі
132 ISSN 0572-2691
програмної реалізації моделі, які обгрунтовують ефективність запропонованої
моделі планування розподілу ресурсів у гетерогенних системах у вибраних мет-
риках продуктивності роботи системи. Показано, що запропонована процедура
планування дозволяє максимізувати завантаженість гетерогенних ресурсів сис-
теми, зменшити час виконання всієї черги завдань в Грід-системі порівняно з
поширеним методом FCFS. Розглянуто реалізацію запропонованого методу
в планувальнику MAUI.
S.V. Listrovoy, S.V. Minukhin
MODEL AND APPROACH TO SCHEDULING
RESOURCES IN HETEROGENEOUS GRID-SYSTEMS
The model and approach to scheduling of computing resources in two-level Grid-
system is offered. Dynamic procedure of scheduling resources in the heterogeneous
environment on the basis of the solution to the problem on the minimal co v er is de-
veloped. The software product realizing discrete-event model of scheduling is devel-
oped. Computing experiments on the basis of model program realization provin g e f -
ficiency of offered model of scheduling resources in heterogeneous environments in
chosen metrics of system performance are made. It is shown that the proposed proce-
dure of scheduling allows maximizing the load of heterogeneous system resources,
reducing the time allotted to perform the entire task queue in Grid-system compared
to the method of FCFS. The realization of the proposed method in the MAUI sch ed-
uler is presented.
1. Грід — нова інформаційна обчислювальна технологія для науки / А.Г. Загородній, Г.М. З і-
нов’єв, Є.С. Мартинов, С.Я. Свістунов, В.М. Шадура // Вісник НАН України. — 2005. —
№ 6. — С. 17–25.
2. Integrating Ukraine into European Grid infrastructure / A. Zagorodny, M. Zgurovsky, G. Zino-
vjev, E. Martynov, A. Petrenko // Системні дослідження та інформаційні технології. — 200 9 .
— № 2. — С. 35–49.
3. Петренко А.І. Застосування Грід-технологій в науці і освіті. — Київ : Політехніка, 2009. —
145 с.
4. Куссуль Н.Н., Шелестов А.Ю. Grid-системы для задач исследования Земли. Архитектура,
модели и технологии. — Киев : Наук. думка, 2008. — 452 с.
5. Шелестов А.Ю., Куссуль Н.Н., Скакун С.В. Грид-технологии в системах мониторинга на
основе спутниковых данных // Проблемы управления и информатики. — 2006. — № 1–2.
— С. 259–270.
6. Пономаренко В.С., Листровой С.В., Минухин С.В., Знахур С.В. Методы и модели планиро-
вания ресурсов в GRID-системах. — Харьков : ИД «ИНЖЭК», 2008. — 408 с.
7. Коваленко В.Н., Семячкин Д.А. Методы и алгоритмы управления параллельными задания-
ми в Гриде с ресурсами в форме кластеров // Вестник Южного научного центра РАН. —
2008. — 4, № 3. — С. 23–34.
8. Коваленко В.Н., Коваленко Е.И., Корягин Д.А., Семячкин Д.А. Управление параллельными
заданиями в Гриде с неотчуждаемыми ресурсами. — М., 2007. — 28 c. — (Препр. / ИПМ
РАН; № 63).
9. Грид-диспетчер: реализация службы диспетчеризации заданий в Грид-системах / В.Н. Ко-
валенко, Е.И. Коваленко, Д.А. Корягин, Э.З. Любимский, Е.В. Хухлаев, О.Н. Шорин // Тр.
Междунар. конф. «Распределенные вычисления и Грид-технологии в науке и образова-
нии», Дубна: ОИЯИ, 2004. — C. 133–138.
10. Петренко А.І., Свістунов С.Я., Свірін П.В. Алгоритми балансування навантаження в Грід-
системах // Системні дослідження та інформаційні технології. — 2011. — № 4. — С. 21–36.
11. Симоненко В.П. Теоретические основы проектирования динамических пространственных
планировщиков неоднородных GRID систем // Электронное моделирование. — 2011. — 33,
№ 5. — С. 57–71.
12. Мамойленко С.М., Ефимов А.В. Алгоритмы планирования решения масштабируемых задач
на распределенных вычислительных системах // Вестник СибГУТИ. — 2010. — № 2. —
С. 66–78.
13. Xhafa F., Barolli L., Duressi A. Evaluation of batch mode methods for scheduling in Grid systems
// MoMM & iiWAS2000 Workshop Proc. — P. 27–38.
14. Xhafa F., Abraham A. Meta-heuristics for Grid scheduling problems // Meta. for Sched. in Distri.
Comp. Envi., SCI 146, 2008. — P. 1–37.
15. Петренко А.І. Комп’ютерне моделювання Грід-систем // Электроника и связь. Тематиче-
ский выпуск «Электроника и нанотехнологии». — 2010. — № 5. — С. 40–48.
Международный научно-технический журнал
«Проблемы управления и информатики», 2012, № 5 133
16. Грушин Д.А., Поспелов А.И. Система моделирования Grid: реализация и возможности при-
менения. — www.ispras.ru/ru/proceedings/docs/2010/18/isp_18_2010_243.pdf.
17. Comparison of scheduling heuristics for Grid resource broker / S. Zhuk, A. Tchernykh, N. Ku-
zjurin, A. Pospelov, A. Shokurov, A. Avetisyan, S. Gaissaryan, D. Grushin // Proc. of the
PCS2004 Third Intern. Conf. on Parallel Computing Systems. Colima, Mexico, September 20–2 4
(in conjunction with ENC’04 Mexican International Conference in Computer Science), IEEE
Computer Society Press, 2004. — P. 388–392,
18. Two level job-scheduling strategies for a computational Grid / A. Tchernykh, J. Ramírez, A. Ave-
tisyan, N. Kuzjurin, D. Grushin, S. Zhuk // In Parallel Processing and Applied Mathematics,
Wyrzykowski et al. (Eds.) // The Second Grid Resource Management Workshop (GRMW'2005)
in conjunction with the Sixth International Conference on Parallel Processing and Applied Mat h -
ematics — PPAM 2005. Poznan, Poland, September 11-14, 2005, LNCS 3911, Springer-Verlag,
2006. — P. 774–781.
19. Resource manager for Grid with global job queue and with planning based on local schedules /
V.N. Kovalenko, E.I. Kovalenko, D.A. Koryagin, E.Z. Ljubimskii, A.V. Orlov, E.V. Huhlaev //
VIII International Workshop on Advanced Computing and Analysis Techniques in Physics Re-
search, ACAT’2002 Book of Abstracts, 24–28 June, 2002, Moscow. — P. 31.
20. Кулаков Ю.А., Русанова О.В., Шевело А.П. Иерархический способ планирования для GRID
// Вісник НТУУ «КПІ». Інформатика, управління та обчислювальна техніка. — 2009. —
№ 51. — C. 13–21.
21. Santoso J., van Albada G.D., Nazief B.A.A., Sloot P.M.A. Hierarchical job scheduling for clusters
of workstations // ASCI 2000, ASCI, Delft, June 2000. — P. 99–105.
22. Zikos S., Karatza H.D. Resource allocation strategies in a 2-level hierarchical Grid system // Pro-
ceedings of the 41th Annual Simulation Symposium (ANSS), IEEE Computer Society Press,
SCS, April 13–16, 2008, Ottawa, Canada. — P. 157–174.
23. Li M., Baker M. The Grid. Core technologies. — Southern Gate, Chichester : John Wiley & Sons
The Atrium, 2005. — 423 p.
24. Klusacek D. Dealing with uncertainties in Grids through the event -based scheduling approach //
Fourth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
(MEMICS 2008). 1. vydání. Brno : Ing. Zdeněk Novotný CSc., Ondráčkova 105, 628 00 Brno,
2008. — P. 91–98.
25. Klusacek D. Event-based Grid scheduling. Faculty of Informatics, Masaryk University, 2011.
Submitted PhD Thesis. — http://is.muni.cz/publikace/publikace_simple.pl?lang=en;id=935026.
26. Shan H., Oliker L. Job superscheduler architecture and performance in computational Grid envi-
ronments // Proc. of the 2003 ACM/IEEE Conference on Supercomputing (SC), November
15–21, 2003, Phoenix, Arizona, USA. — P. 44–58.
27. Buyya R., Murshed M. GridSim: a toolkit for the modeling and simulation of distributed resource
management and scheduling for grid computing // Сoncurrency and Computation: Practice and
Experience. — 2002. — 14. — P. 1175–1220.
28. Минухин С.В., Коровин А.В. Моделирование планирования ресурсов GRID средствами па-
кета GridSim // Системи обробки інформації. Інформаційні технології та комп’ютерна ін-
женерія. — 2011. — Вип. 3(93). — С. 62–68.
29. The Grid Workloads Archive. — http://gwa.ewi.tudelft.nl/pmwiki/pmwiki.php?n=Workloads.Gwa-t-4.
30. Sandip S. Patil, Preeti Singh. Design and implementation of efficient load balancing algorithm in
Grid environment // Intern. Journ. of Comput . Sci. and Inform. Technol. — 2011. — 2, N 5. —
P. 2159–2164.
31. Abderezak Touzene, Hussein Al Maqbali. Analytical model for performance evaluation of load
balancing algorithm for Grid computing. — http://faculty.kfupm.edu.sa/EE/sbaiyat/events/IEEEG
CC2007/d1_s3_p4_1569048217.pdf.
32. Leyli Mohammad Khanli, Behnaz Didevar. A new hybrid load balancing in Grid computing sys-
tems // Int. J. Sci. Imerging Tech. — 2001. — 6, N 2. — P. 304–309.
33. Документация MAUI. — http://www.adaptivecomputing.com/resources/docs/maui/mauiadmin.php.
Получено 07.07.2011
После доработки 12.03.2012
http://is.muni.cz/publikace/publikace_simple.pl?lang=en;id=935026
http://gwa.ewi.tudelft.nl/pmwiki/pmwiki.php?n=Workloads.Gwa-t-4
http://faculty.kfupm.edu.sa/EE/sbaiyat/events/IEEEG
|