Полиномиальная диспетчеризация множественным компьютерным обслуживанием

• Автор: Саак, Андрей Эрнестович
• Шифр специальности: 05.13.01
• Научная степень: Докторская
• Год защиты: 2013
• Место защиты: Таганрог
• Количество страниц: 286 с. : ил.

Оглавление
Введение

Глава 1. Среда диспетчирования

1.1. Анализ задач диспетчирования вычислительно- временными ресурсами

1.2. Среда ресурсных прямоугольников

1.3. Классификация массивов заявок

1.4. Принцип эвристики в многоцелевой оптимизации

1.5. Выводы

Глава 2. Массивы заявок кругового типа

2.1. Однородный алгоритм

2.2. Начально- кольцевой алгоритм
2.3. Вершинно- кольцевой алгоритм
2.4. Уровневый алгоритм
2.5. Угловой алгоритм
2.6. Алгоритм последовательных приближений
2.7. Сравнительный анализ полиномиальных алгоритмов диспетчирования
2.8. Выводы
Глава 3. Массивы заявок гиперболического типа
3.1. Центрально- кольцевой алгоритм
3.2. Уровневый алгоритм по высоте и протяжённости
3.3. Угловой алгоритм для гиперболических заявок
3.4. Полиэдрали со свойством монотонности
3.5. Выводы
Глава 4. Массивы заявок параболического типа
4.1. Алгоритм со среднересурсным уровнем
4.2. Начально- уровневый алгоритм
4.3. Возвратный и ступенчатый алгоритмы
4.4. Полиэдрали параболической однородности и монотонной составности
4.5. Синтез ресурсных оболочек
4.6. Выводы
Глава 5. Анализ взаимодействия сторон компьютерного обслуживания
5.1. Аддитивная, ординарная, дополняемая формы базисного задания комбинаторного эксперимента
5.2. Усечение круговых, гиперболических и параболических моделей
5.3. Модель спроса
5.4. Модель предложений ресурсов
5.5. Взаимодействие сторон спроса и предложения ресурсов
5.6. Выводы
Заключение
Список литературы
Приложения

Введение
Актуальность работы. Всё возрастающая потребность пользователей в вычислительной мощности стимулировала переход в конце 90- х годов от многопроцессорных систем, кластерных систем, метакомпьютинга к Grid-компьютингу (Grid computing), который развивается и в настоящее время, наряду с другими парадигмами распределённых вычислений, такими как облачные вычисления (cloud computing) и вычислительные джунгли (jungle computing). Эффективность функционирования таких систем во многом определяется распределением вычислительных ресурсов, управлением задачами в условиях множественности. При этом диспетчирование заявками пользователей, требующих каждая для своего обслуживания несколько процессоров одновременно, выходит за рамки классической теории расписаний. Принцип оптимизации, как машинный поиск наилучшего распределения, выявил трудоёмкость по времени, делающей невозможным использование этих методов при управлении ресурсами Grid. Существующая классификация систем диспетчирования задач (job scheduling) и управления ресурсами Grid (Grid resource management systems) выделяет три базовые архитектуры: централизованная (centralized), иерархическая (hierarchical) и распределённая (decentralized, distributed), различающиеся способом принятия решения об управлении ресурсами и задачами. Так, в централизованной структуре диспетчерское решение осуществляется центральным диспетчером, обладающим всей полнотой информации о вычислительных ресурсах и задачах. В Grid-системах различают два вида диспетчирования по способу объединения вычислительных ресурсов для решения задачи: одно- сайтное диспетчирование (single- site scheduling) и мульти- сайтное диспетчирование (multi- site scheduling). При одно- сайтном диспетчировании задача выполняется в пределах сайта, не выходя за границы параллельной системы. Тогда как при мульти- сайтном
диспетчировании задача может выполняться одновременно на нескольких сайтах, выходя за границы параллельных систем.
В настоящее время диспетчирование Grid-систем с системой диспетчирования задач и управления ресурсами, имеющей централизованную архитектуру, поддерживающую мульти- сайтное выполнение задач недостаточно разработано, поэтому актуальным является предложение эвристических алгоритмов распределения ресурсов, учитывающих свойства массива заявок пользователей, с оценкой качества расписания.
Эвристические алгоритмы диспетчирования планарными ресурсами, активно разрабатывавшиеся в конце прошлого и начале нынешнего века, недостаточны как по результативности, так и по эмпиричности подходов. До настоящего времени не предложен формальный аппарат среды диспетчирования, который должен позволить выявить закономерности множества заявок, ввести их типизацию и предложить эвристические алгоритмы, адаптированные под соответствующие типы с оценкой качества. Разработка такого формального аппарата является актуальной задачей.
Исследования в области диспетчирования заявок пользователей и распределения вычислительно- временных ресурсов, как упаковки прямоугольников, были начаты с 80-х годов прошлого столетия. Среди отечественных авторов можно отметить следующие работы А.Б. Барский,
B.Ю. Бакенрот, A.B. Каляев, О.Б. Макаревич, А.Г. Чефранов и др. (упаковка прямоугольников- заявок в одну полосу, Strip Packing Problem); А.И. Аветисян,
C.С. Гайсарян, Д.А. Грушин, H.H. Кузюрин, A.B. Шокуров, С.Н. Жук, А.И. Поспелов, А.Н. Черных (упаковка прямоугольников- заявок в несколько полос, Multiple Strip Packing Problem). Среди зарубежных ученых следует выделить Baker, В., Coffman, E., Rivest, R., Garey, M., Johnson, D., Tarjan, R., Hofri, M., Sleator, D., Brown, D., Katseff, H., Drozdowski, M., Lodi, A., Martello, S., Monaci, M., Feitelson, D. и др. (Strip Packing Problem); Schwiegelshohn, U., Yahyapour, R., Bougeret, M., Dutot, Р.-F., Trystram, D. (Multiple Strip Packing Problem); Hifi, M., Ouafi, R., Korf, R., Huang, E., Moffitt, M., Pollack, M.,

Крутизна уровневой функции - меньше крутизны хорды

*£0-1 / ( (рисунок 1.36). Если выполнено неравенство (1.5) и неравенство
а(0) + а(1)
то пара граней относится к круговому квадратичному типу. Имеет место медленное убывание уровней и сравнимость граней б(1)<б(0), а(1)<о(о). Если выполнено неравенство (1.5) и неравенство а(1) > а(0), то пара граней относится к гиперболическому квадратичному типу. Имеет место медленное убывание уровней и несравнимость граней б(1) < Ь(о), а(1)>а(0).
При противоположном соотношении крутизны уровневой функции и хорды > ЩР, й(1) < у[а(о)] (рисунок 1.37), имеем быстрое убывание левых отсчётов и параболический квадратичный тип пары граней убывающих уровней.

Рис. 1.37. Крутизна уровневой функции больше крутизны хорды
Понятие уровневой функции левых отсчётов граней упорядоченной
линейной полиэдрали У2 = )]4-, А(у])= ^ , и крутизны уровневой

функции
.... «Я(л).*£йШ±а
а(0) а(1) аи)
д =0,1,...,к-2, распространяются на общее количество граней полиэдрали и
соответствующую хорду (1.4) с крутизной tgP = ~~. При ,