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

Содержание к диссертации

Введение

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

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

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

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

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

1.5. Выводы 47

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

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

2.2. Начально- кольцевой алгоритм 55

2.3. Вершинно- кольцевой алгоритм 69

2.4. Уровневый алгоритм 77

2.5. Угловой алгоритм 96

2.6. Алгоритм последовательных приближений 110

2.7. Сравнительный анализ полиномиальных алгоритмов диспетчирования 143

2.8. Выводы 153

Глава 3. Массивы заявок гиперболического типа 154

3.1. Центрально- кольцевой алгоритм 154

3.2. Уровневый алгоритм по высоте и протяжнности 160

3.3. Угловой алгоритм для гиперболических заявок 173

3.4. Полиэдрали со свойством монотонности 181

3.5. Выводы 185

Глава 4. Массивы заявок параболического типа 186

4.1. Алгоритм со среднересурсным уровнем 186

4.2. Начально- уровневый алгоритм 195

4.3. Возвратный и ступенчатый алгоритмы 203

4.4. Полиэдрали параболической однородности и монотонной составности 225

4.5. Синтез ресурсных оболочек 231

4.6. Выводы 243

Глава 5. Анализ взаимодействия сторон компьютерного обслуживания 244

5.1. Аддитивная, ординарная, дополняемая формы базисного задания комбинаторного эксперимента 244

5.2. Усечение круговых, гиперболических и параболических моделей 248

5.3. Модель спроса 256

5.4. Модель предложений ресурсов 261

5.5. Взаимодействие сторон спроса и предложения ресурсов 266

5.6. Выводы 269

Заключение 270

Список литературы

• Среда ресурсных прямоугольников
• Вершинно- кольцевой алгоритм
• Угловой алгоритм для гиперболических заявок
• Полиэдрали параболической однородности и монотонной составности

Введение к работе

Актуальность работы. Всё возрастающая потребность пользователей в вычислительной мощности стимулировала переход в конце 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-х годов прошлого столетия. Среди отечественных авторов можно отметить следующие работы А.Б. Барский, В.Ю. Бакенрот, А.В. Каляев, О.Б. Макаревич, А.Г. Чефранов и др. (упаковка

прямоугольников- заявок в одну полосу, Strip Packing Problem); А.И. Аветисян, С.С. Гайсарян, Д.А. Грушин, Н.Н. Кузюрин, А.В. Шокуров, С.Н. Жук, А.И. Поспелов, А.Н. Черных (упаковка прямоугольников- заявок в несколько полос, Multiple Strip Packing Problem). Среди зарубежных ученых следует выделить Baker, В., Coffman, Е., Rivest, R., Garey, М., 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, P.-F., Trystram, D. (Multiple Strip Packing Problem); Hifi, M., Ouafi, R., Korf, R., Huang, E., Moffitt, M., Pollack, M., Clautiaux, F., Simonis, H., O'Sullivan, В. (модели упаковки прямоугольников в объемлющий квадрат минимальной площади, Square Packing и в объемлющий прямоугольник минимальной площади, Rectangular Packing).

Анализ публикаций показал, что в качестве геометрической интерпретации Grid- системы использовались модели неограниченной полосы и множества полос, что соответствует приоритету одного из пары вычислительных ресурсов. По мере развития технологии, росту числа процессоров, увеличения быстродействия телекоммуникационных сетей учёт ресурсов в Grid- системах должен становиться всё более сбалансированным, а ресурсы- равноправными, паритетными. Актуальной является задача предложить модели паритетности ресурсов.

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

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

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

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

Для достижения цели диссертационной работы необходимо решить задачи:

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

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

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

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

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

6. разработать и исследовать полиномиальные алгоритмы диспетчирования массивами заявок гиперболического типа.

7. разработать и исследовать полиномиальные алгоритмы диспетчирования массивами заявок параболического типа.

8. определить понятие и условия равновесия взаимодействующих сред спроса- предложения при множественном компьютерном обслуживании.

9. разработать и исследовать комбинаторные модели взаимодействующих сред спроса-предложения для согласования параметров на этапе предпроектных исследований.

Область исследования соответствует п. 1. «Теоретические основы и методы системного анализа, оптимизации, управления, принятия решений и обработки информации»; п.4. «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации»; п.5. «Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации» специальности 05.13.01- Системный анализ, управление и обработка информации (по отраслям).

Объектом исследования являются: модели и методы распределения вьшислительно- временных ресурсов, поставляющая и потребляющая компьютерный сервис среды.

Предметом исследования являются: алгоритмы диспетчирования множественным компьютерным обслуживанием, взаимодействие сред-поставляющей и потребляющей компьютерный сервис.

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

Теоретическая и практическая значимость диссертационной работы.

Теоретическую значимость имеют: принцип эвристики решения задач диспетчирования, являющийся альтернативной заменой принципа оптимизации;

формальный аппарат среды диспетчирования, включающий определение ресурсного прямоугольника, как модели заявки пользователя, операции в среде диспетчирования над этими ресурсными прямоугольниками, эвристическая неэвклидова мера, учитывающая как меру площади, так и меру ассиметрии занятой ресурсной области;

квадратичная типизация линейных полиэдралей ресурсных прямоугольников;

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

Практическую значимость имеют: алгоритмическое обеспечение диспетчирования, основанное на введённых операциях динамического интегрирования ресурсных прямоугольников (по горизонтали, по вертикали,

продольное), имеющее полиномиальную трудоёмкость, адаптированное под соответствующий квадратичный тип массива заявок;

аналитическая оценка качества, отличающаяся неэвклидовостью и выраженная формулой для эвристической меры;

условие равновесия, согласование параметров взаимодействующих сред спроса- предложения при множественном компьютерном обслуживании;

условие достоверности компьютерного обслуживания.

Научная новизна выполненных исследований заключается в следующем:

сформулирован принцип эвристики, состоящий в программном задании алгоритма диспетчирования с оценкой его качества, взамен существующего принципа оптимизации с машинным поиском наилучшего распределения массива ресурсных прямоугольников высокой вычислительной сложности;

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

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

разработана формула для эвристической меры оценки качества алгоритмов диспетчирования, учитывающая как меру площади, так и меру асимметрии занятой ресурсной области;

разработаны полиномиальные алгоритмы распределения вычислительно-временных ресурсов, которые отличаются от существующих алгоритмов диспетчирования вычислительных систем адаптацией к квадратичным типам заявок пользователей;

введено понятие равновесия взаимодействующих сред спроса-предложения при множественном компьютерном обслуживании и получено условие их равновесия;

получено условие достоверности двухстадийного однородового компьютерного обслуживания в эксперименте спроса- предложения модельных ресурсных элементов.

Основные результаты и выводы, выносимые на защиту.

1. Принцип эвристики решения задач диспетчирования, который состоит в программном задании алгоритма диспетчирования с оценкой его качества вместо машинного поиска оптимального распределения массива заявок.

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

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

4. Эвристическая мера объемлющего ресурсного прямоугольника, содержащего в себе распределенный исходный массив заявок, учитывающая как меру площади, так и меру асимметрии занятой ресурсной области.

5. Разработанные полиномиальные алгоритмы: начально-кольцевой, уровневый, угловой и алгоритм последовательных приближений, адаптированные

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

6. Разработанные полиномиальные алгоритмы: центрально-кольцевой, уровневый по высоте и протяженности, угловой, адаптированные к диспетчированию массивами заявок гиперболического типа и результаты их исследования.

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

8. Понятие равновесия и условия равновесия взаимодействующих сред спроса- предложения при множественном компьютерном обслуживании.

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

Внедрение результатов. Теоретические и практические результаты диссертационной работы использованы при выполнении госбюджетной НИР № 301*38-11/2013-7 «Разработка теории и принципов интеллектуального анализа данных при построении систем поддержки принятия решений» (заказчик Минобрнауки РФ), при выполнении гранта РФФИ № 13-07-00450 «Разработка информационной системы грузового терминала на основе распараллеливания работ и приоритетного обслуживания», гранта РФФИ № 11-01-00122 «Разработка теории и принципов построения интеллектуальных гибридных нечетких генетических, эволюционных и адаптивных методов принятия решений при проектировании и оптимизации» в инженерно- технологической академии Южного федерального университета (ИТА ЮФУ).

Результаты, полученные в ходе выполнения диссертационной работы внедрены в учебный процесс ИТА ЮФУ (на кафедре систем автоматизированного проектирования факультета автоматики и вычислительной техники) по дисциплинам «Автоматизация конструкторского и технологического проектирования», «Интеллектуальные системы» специальности 230104 «Системы автоматизированного проектирования», направления 230100 «Информатика и вычислительная техника».

Апробация работы. Основные результаты работы докладывались и обсуждались на ряде всероссийских, международных научно-технических конференциях, в том числе: II-VI Международной конференции «Параллельные вычисления и задачи управления» (РАСО'2004, РАСО'2006, РАСО'2008, РАСО'2010, РАСО'2012) (Москва, ИПУ РАН 2004, 2006, 2008, 2010, 2012 г.г.); на V-VII Международной научно- практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права» (Москва, МГАПИ 2002 - 2004 г.г.); Международных конференциях «Интеллектуальные системы» (AIS'04-AIS'IO) (Дивноморское, 2004-2010 г.г.); Международных конгрессах «Интеллектуальные системы и информационные технологии» (ISIT' 11-ISIT' 13) (Дивноморское, 2011-2013 г.г.); Международных научно-технических конференциях «Суперкомпьютерные технологии: разработка, программирование, применение» (ОСТ-2010, ОСТ-2012) (Геленджик,

2010г.₉ 2012г.); 6-й Всероссийской Мультиконференции по проблемам управления «Управление в распределенных и сетевых системах» (МКПУ - 2013) (Геленджик, 2013г.); на научно-технических конференциях профессорско-преподавательского состава ТРТУ, ЮФУ (Таганрог, 1998-20ІЗг.г.).

Публикации. По результатам исследований, выполненных в диссертации опубликовано 43 работы, включая 25 публикаций в рецензируемых научных журналах, входящих в Перечень изданий, рекомендуемых ВАК Минобрнауки РФ.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и библиографического списка из 135 наименований. Диссертация содержит 271 страниц текста, 29 таблиц, 217 рисунков.

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

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

Приведм базовые примеры массивов заявок гиперболического типа:

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

Приведм базовый пример массива заявок параболического типа- ресурсные прямоугольники J1x(k-j1\ j1 =1,2,...Д-1 (рисунок 1.35). то пара граней относится к круговому квадратичному типу. Имеет место медленное убывание уровней и сравнимость граней b(\) b(0), а(\) а(0). Если выполнено неравенство (1.5) и неравенство а(\) а(0), то пара граней относится к гиперболическому квадратичному типу. Имеет место медленное убывание уровней и несравнимость граней b(\) b(o), а(\) а(0).

При противоположном соотношении крутизны уровневой функции и хорды tg/t tg/?, b(\) у[а(0)] (рисунок 1.37), имеем быстрое убывание левых отсчтов и параболический квадратичный тип пары граней убывающих уровней. Крутизна уровневой функции больше крутизны хорды Понятие уровневой функции левых отсчтов граней упорядоченной линейной полиэдрали Y2 = b[A(j\)]i, A(j\)= 2 a Jt, и крутизны уровневой

При tgA(j\) tgj3, j\ = О,1,...,k-2, имеем медленное убывание уровней и выпуклый по отношению к хорде полигон упорядоченной линейной полиэдрали граней с убывающими высотами. При tgA(j\) tg/3, j\ = 0,1,...,к-2, имеем быстрое убывание уровней граней и вогнутый в начале координат полигон ниже упомянутой хорды.

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

Рассмотрим вопрос выделения квадратичных модулей из линейной полиэдрали ресурсных прямоугольников, упорядоченных по убыванию высот [130].

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

Линейная полиэдраль первого типа при факторизации на круговые и гиперболические модули представляется ориентированными гранями, располагающимися по одну сторону от оси Z1 в случае сравнимости и по разные стороны- в случае несравнимости с непосредственно предшествующей гранью (рисунок 1.38). несравнимые грани Y Yi сравнимые грани Несравнимые последовательные пары ресурсных прямоугольников

При этом, если все указанные модули имеют по одному элементу, получаем гиперболический квадратичный тип линейной полиэдрали. Модули сравнимых граней имеют круговой квадратичный тип. Изложенные построения позволяют выделить линейные полиэдрали круговой модульной составности и гиперболической модульной составности.

Вершинно- кольцевой алгоритм

Сравнение результатов не позволяет отдать предпочтение какому- либо из алгоритмов. Для решения рамочной задачи рассмотрим версию уровневого алгоритма. С этой целью, в начальной полосе 0 Yl а{0) производим вертикальную последовательную суперпозицию ресурсных прямоугольников слева от линии до наилучшего приближения с недостатком к высоте прямоугольников по вертикали) (рисунок 2.36). Здесь q- число ресурсных прямоугольников, суперпозированных в начальной полосе. Далее, строим линию Yl = а(0) + a( i) и слева от данной линии производим предыдущее построение по отношению к оставшейся части массива Y.b(jl) = M-0 (операция динамического интегрирования ресурсных прямоугольников по вертикали). Здесь q2- число ресурсных прямоугольников следующей полосы. Циклическое повторение указанных действий приведт к исчерпанию массива и локализации последнего в полосу 0 У2 М некоторой протяжнности, составленной из предыдущих отрезков

Вертикальные линейные полиэдрали, из которых составлена полоса 0 72 М, подлежащая рамочному ресурсному распределению по правилам координатности, аддитивности и цельности, обладают свойством убывания оснований ресурсных прямоугольников вдоль вертикальной координаты j2 Т, ai. Здесь a(j1,j2)- основание полиэдральной грани в упомянутой полосе. Поэтому требуемому распределению по линейкам [0,м] подлежат звенья-измерения горизонтальной линии 72 = 0. Данная цель достигается последовательной суперпозицией с наилучшим приближением с недостатком протяжнности М-0 (операция динамического интегрирования ресурсных прямоугольников по горизонтали) посредством указанных измерительных элементов a(j1, 0)- горизонтальных оснований ресурсных прямоугольников-заявок пользователей.

Приведм и исследуем последовательно- координатный алгоритм диспетчеризации триодными полиэдралями ресурсных прямоугольников a(j\) b(j\Ji\ Л,Лє[0,к](=г1 при решении рамочной стадийной задачи на основе последовательного наилучшего приближения с недостатком по отношению к измерениям МхМ ресурсной рамки динамическим интегрированием. 1. Строим первую полосу 0 7Х 2a0i). 2 0і) = м- (операция у1=0 j\=0 динамического интегрирования ресурсных прямоугольников по горизонтали). 2. Заполняем рамки МхМ гранями первой полосы наилучшим приближением вертикального измерения рамки. Для начальной рамки имеем 0 У2 тах ZbOiJil Л [0,Яі-ї\ г\ 1 0ьУ2) = М-0 (операция Jl J2= J2= динамического интегрирования ресурсных прямоугольников по вертикали). Последующие рамки гранями первой полосы заполняются аналогично / 2(/i)-i 2 0W2) = -0 (операция динамического интегрирования ресурсных J2=Pl0l) Р2О1П прямоугольников по вертикали), Y2 = max ZKjiJil A -l Z1 Закончив распределение первой полосы, переходим ко второй, и далее, до полного исчерпания массива.

Таким образом, в настоящем параграфе предлагается и исследуется эвристический уровневый алгоритм диспетчирования массивами заявок кругового типа. Приводится блок- схема уровневого алгоритма распределения процессорно временных ресурсов. Устанавливается полиномиальная трудомкость предложенного уровневого алгоритма. Для базовых примеров массивов заявок кругового типа: натуральных ресурсных квадратов (к - j\)x (к- j\\ j\ = 0,1,...,k-1 (равные требования временного и процессорного ресурсов a(j1)=b(j1)), натуральных ресурсных прямоугольников горизонтальной формы [((k-JiMk-Ji-l))], j\ = 0,\,...,k-2 (преимущественные требования временного ресурса a{j\) b(j\)), натуральных ресурсных прямоугольников вертикальной формы [((к - jx -1), (к - j\))], j\ = О,1,... ,k - 2 (преимущественные требования процессорного ресурса я(Л) КЛ)) строятся объемлющие прямоугольники с вычислением ресурсных и эвристических мер. Указанные построения и вычисления сопоставляются с имеющимися в литературе оптимальными построениями ресурсных оболочек. Делаются выводы о качестве предложенного эвристического полиномиального уровневого алгоритма. Описывается последовательно- координатный алгоритм диспетчирования триодными полиэдралями ресурсных прямоугольников при решении рамочной стадийной задачи. При этом, к уровневым построениям вдоль вертикали присоединяются рамочные построения вдоль горизонтали с наилучшими приближениями измерения рамки суммарной протяжнностью перераспределяемых ресурсных прямоугольников массива.

Угловой алгоритм для гиперболических заявок

Эвристическая мера объемлющего ресурсного прямоугольника третьего шага равна 1,21. Так как эвристическая мера увеличилась, то результат предыдущего шага считаем наилучшим. Таким образом, эвристическая мера алгоритма последовательных приближений по протяжнности с параллельной структурой при упорядочивании линейной круговой полиэдрали 32- х натуральных ресурсных прямоугольников вертикальной формы имеет значение 0,66.

Эвристические меры ресурсных оболочек алгоритма последовательных приближений по протяжнности с параллельной структурой для натуральных ресурсных прямоугольников вертикальной формы приведены в таблице 2.27. Отметим, что эвристические меры ресурсных оболочек алгоритма последовательных приближений по протяжнности с параллельной структурой для прямоугольников вертикальной формы не превосходят значения — + 0,16. 142

Таким образом, в настоящем параграфе предлагается и исследуется эвристический алгоритм последовательных приближений диспетчирования массивами заявок кругового типа. Устанавливается полиномиальная трудомкость предложенного алгоритма последовательных приближений. Для базовых примеров массивов заявок кругового типа: натуральных ресурсных квадратов (к - j1 )х (к - j1), j1 = 0,1,... ,k -1 (равные требования временного и процессорного ресурсов a(j1) = b(j1)), натуральных ресурсных прямоугольников горизонтальной формы [((к - j1\(к - j1 -1))], j1 = 0,1,...,k - 2 (преимущественные требования временного ресурса a(j1) b(j1)), натуральных ресурсных прямоугольников вертикальной формы Ш-Л 1),(к-л))], Л = 0,1,...,к-2 (преимущественные требования процессорного ресурса a(j1) b(j1)) строятся объемлющие прямоугольники с вычислением ресурсных и эвристических мер. Указанные построения и вычисления сопоставляются с имеющимися в литературе оптимальными построениями ресурсных оболочек. Делаются выводы о качестве предложенного эвристического полиномиального алгоритма последовательных приближений.

Сравнительный анализ полиномиальных алгоритмов диспетчирования Проведм сравнительный анализ разработанных и исследованных полиномиальных алгоритмов диспетчирования линейными круговыми полиэдралями [78]. Графики погрешностей по сравнению с оптимальным алгоритмом для натуральных ресурсных квадратов приведены на рисунке 2.79. Рис. 2.79. Сравнение полиномиальных алгоритмов Как было показано ранее, погрешность начально- кольцевого алгоритма не превосходит 31%, погрешность уровневого алгоритма не превосходит 33%, погрешность углового алгоритма не превосходит 42%, погрешность алгоритма последовательных приближений не превосходит 29% и погрешность однородного алгоритма не превосходит 21%.

Оптимальная укладка в объемлющий квадрат минимальной площади получена в работах [67,70]. Сравнение эвристических мер ресурсных оболочек оптимальной укладки в объемлющий прямоугольник и квадрат минимальной площади дано на рисунке 2.80. Эвристические меры ресурсных оболочек оптимальных алгоритмов укладки в прямоугольник и квадрат Графики эвристической меры ресурсных оболочек разработанных и исследованных полиномиальных алгоритмов диспетчирования линейными круговыми полиэдралями для натуральных ресурсных квадратов показаны на рисунке 2.81.

Эвристические меры ресурсных оболочек полиномиальных алгоритмов диспетчирования линейными круговыми полиэдралями

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

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

Полиэдрали параболической однородности и монотонной составности

Вариант с меньшей эвристической мерой считаем наилучшим. В приведнном примере наиболее предпочтительным является распределение ресурсов первого шага. Видим, что эвристическая мера ресурсной оболочки синтеза полиэдралей ступенчатым алгоритмом со значением 1,03 лучше, чем алгоритмом вершинно- диагональной суперпозиции со значением 1,39 (4.1).

Рассмотрим способ синтеза указанных выше параболической (рисунок 4.66) и круговой (рисунок 4.67), с ресурсными прямоугольниками вертикальной формы, линейных полиэдралей с использованием ступенчатого алгоритма параграфа 4.3. Шаги алгоритма с соответствующими эвристическими мерами,

В рассмотренном примере диспетчеризация на втором шаге дат наименьшую эвристическую меру. Видим, что эвристическая мера ресурсной оболочки синтеза полиэдралей ступенчатым алгоритмом 1,09 лучше, чем алгоритмом вершинно- диагональной суперпозиции 1,66 (4.2). Проведнное исследование свидетельствует о целесообразности использования предложенного ступенчатого алгоритма при синтезе ресурсных оболочек.

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

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

Дополнительные треугольники перераспределяются инверсией верхнего к нижнему с синтезом вдоль гипотенузы последнего при редукции к горизонтальной оболочке (рисунок 4.78) и инверсией нижнего треугольника к верхнему с аналогичным синтезом- при редукции к вертикальной оболочке (рисунок 4.79).

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

1. Предложены, разработаны и исследованы полиномиальные алгоритмы диспетчирования, адаптированные к массивам заявок параболического квадратичного типа.

2. Приведена статистика сравнения с оптимальным алгоритмом, показывающая преимущества предложенного полиномиального алгоритма при учте качества заполнения ресурсной оболочки в сопоставлении с затрачиваемым временем на диспетчирование.

3. Проведн сравнительный анализ разработанных полиномиальных алгоритмов диспетчирования линейными параболическими полиэдралями: среднересурсного уровневого, начально- уровневого, возвратного и ступенчатого.

Основная модель среды диспетчирования введена в главе 1 в качестве предмета динамического исчисления линейных полиэдралей при решении задачи диспетчирования множественным компьютерным обслуживанием. Наряду с внутренней проблематикой оптимальных действий системы обслуживания, анализу подлежит внешняя сторона взаимодействия Grid- системы и множества пользователей вычислительным ресурсом системы. Указанное взаимодействие составляет эксперимент спроса- предложения, подлежащий формальному определению [100-119,121,122,126,127]. Комбинаторный эксперимент является категорией. Определению подлежат базисные формы комбинаторного эксперимента.