авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 |
-- [ Страница 1 ] --

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

На правах рукописи

Саак Андрей Эрнестович

Полиномиальная диспетчеризация

множественным компьютерным обслуживанием

Специальность: 05.13.01- Системный анализ, управление и

обработка информации (вычислительная техника и информатика)

Диссертация на соискание учёной степени доктора технических наук

Научный консультант: заслуженный деятель науки РФ, доктор технических наук, профессор Виктор Михайлович Курейчик Таганрог, 2013 г.

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

А.И. Аветисян, С.С. Гайсарян, Д.А. Грушин, Н.Н. Кузюрин, А.В. Шокуров, С.Н. Жук, А.И. Поспелов, А.Н. Черных (упаковка прямоугольников- заявок в несколько полос, Multiple Strip Packing Problem). Среди зарубежных ученых следует выделить Baker, B., 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, 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, B. (модели упаковки прямоугольников в объемлющий квадрат минимальной площади, 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 Международной конференции «Параллельные вычисления и задачи управления» (PACO’2004, PACO’2006, PACO’2008, PACO’2010, PACO’2012) (Москва, ИПУ РАН 2004, 2006, 2008, 2010, 2012 г.г.);

на V-VII Международной научно- практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права»

(Москва, МГАПИ 2002 - 2004 г.г.);

Международных конференциях «Интеллектуальные системы» (AIS’04-AIS’10) (Дивноморское, 2004-2010 г.г.);

Международных конгрессах «Интеллектуальные системы и информационные технологии» (ISIT’11-ISIT’13) (Дивноморское, 2011-2013 г.г.);

Международных научно-технических конференциях «Суперкомпьютерные технологии:

разработка, программирование, применение» (СКТ - 2010, СКТ - 2012) (Геленджик, 2010г., 2012г.);

6-й Всероссийской Мультиконференции по проблемам управления «Управление в распределенных и cетевых системах»

(МКПУ - 2013) (Геленджик, 2013г.);

на научно- технических конференциях профессорско-преподавательского состава ТРТУ, ЮФУ (Таганрог, 1998-2013г.г.).

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

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

Диссертация содержит 271 страниц текста, 29 таблиц, 217 рисунков.

Глава 1. Среда диспетчирования 1.1. Анализ задач диспетчирования вычислительно- временными ресурсами Вс возрастающая потребность пользователей в вычислительной мощности стимулировала переход в конце 90- х годов от многопроцессорных систем, кластерных систем, метакомпьютинга к Grid- компьютингу (Grid computing) [1], который развивается и в настоящее время [2-10,92-96], наряду с другими парадигмами распределнных вычислений [11], такими как облачные вычисления (cloud computing) [12] и вычислительные джунгли (jungle computing) [13].

Эффективность функционирования Grid- систем во многом определяется распределением вычислительных ресурсов, управлением задачами в условиях множественности. Выделяют вычислительные (computation- intensive) задачи, требующие преимущественно вычислительных ресурсов, и коммуникативные задачи, требующие преимущественно коммуникационных (data- intensive) ресурсов и памяти для обработки больших объмов данных [14-17]. Различают четыре типа задач в зависимости от того, пользователь или система, и, при предоставлении задачи или в процессе выполнения, задат число выделяемых процессоров [18]. В настоящей работе рассматриваются вычислительные задачи, в которых число требуемых процессоров определяет пользователь при подаче в систему- жсткие задачи (rigid job).

системы принято классифицировать на вычислительные Grid (computational Grid), интенсивной обработки данных (data Grid), сервисные (service Grid), обработки знаний (knowledge Grid), семантические (semantic Grid) [1-3,19,20]. В настоящей работе рассматриваются вычислительные Grid- системы (далее- Grid- системы), состоящие из сайтов или кластеров, содержащих параллельные системы [1-4,19].

Для систем диспетчирования задач (job scheduling) и управления ресурсами Grid (Grid resource management systems) [19] в 2000 г. [21] были предложены три базовые архитектуры: централизованная (centralized), иерархическая (hierarchical) и распределнная (decentralized, distributed), лежащие в основе существующих классификаций [2-4,17,19,22-24]. В монографии [19] эти топологии систем диспетчирования были названы парадигмами. Централизованная, иерархическая и распределнная структуры различаются способом принятия решения об управлении ресурсами и задачами. Так, в централизованной структуре диспетчерское решение осуществляется центральным диспетчером, обладающим всей полнотой информации о вычислительных ресурсах и задачах. В иерархической структуре диспетчерское решение происходит иерархическим способом: центральный диспетчер распределяет задачи по локальным диспетчерам, которые и производят их назначение в пределах соответствующего сайта. В распределнной структуре диспетчерское решение распределено между локальными диспетчерами сайтов, которые обмениваются между собой информацией, принимая решение о назначении. Отметим, что примерами систем управления ресурсами централизованной структуры могут служить KOALA, EGEE WMS, PlanetLab [25].

В [21] также было предложено различать два вида диспетчирования по способу объединения вычислительных ресурсов для решения задачи: одно сайтное диспетчирование (single- site scheduling) и мульти- сайтное диспетчирование (multi- site scheduling). При одно- сайтном диспетчировании задача выполняется в пределах сайта, не выходя за границы параллельной системы. Тогда как, при мульти- сайтном диспетчировании задача может выполняться одновременно на нескольких сайтах, выходя за границы параллельных систем. Для организации одновременного выделения процессоров на нескольких сайтах при решении задачи используется техника ко- аллокации (co- allocation), развиваемая в ряде работ [21,26-41]. Отметим, что примерами систем управления ресурсами, поддерживающими ко- аллокацию могут служить KOALA, GARA, GridARS [41]. В настоящей работе рассматриваются Grid диспетчеры (Grid- scheduler) централизованной архитектуры, поддерживающие мульти- сайтное выполнение задач.

В Grid- диспетчировании выделяют четыре основных этапа: выявление ресурсов (resource discovery), выбор ресурсов (resource selection), генерация расписания (schedule generation), выполнение задачи (job execution) [19]. Основное внимание в настоящей работе сосредоточено на этапе генерации расписания алгоритмом диспетчирования (scheduling При этом алгоритм algorithm).

диспетчирования определяет способ, которым задачи назначаются на ресурсы, а под расписанием понимается назначение задач на ресурсы в определнные периоды времени [42]. Считаем, что задачи требуют только процессоры и не включаем в рассмотрение другие виды ресурсов Grid- системы [38].

Анализ публикаций показал, что в качестве геометрической интерпретации параллельной системы (Grid- система с одним сайтом [38]) использовалась модель неограниченной полосы (Strip Packing Problem) [43-51,97] (рисунок 1.1), а для Grid- систем с иерархической структурой системы диспетчирования и без ко аллокации ресурсов (одно- сайтное диспетчирование) была предложена модель множества полос (Multiple Strip Packing Problem) [52-64,98-99] (рисунок 1.2). Эти модели соответствуют приоритету одного из пары вычислительных ресурсов.

процессоры время процессоры...

процессоры время время Рис. 1.1. Модель с процессорным Рис. 1.2. Модель множества полос с критическим ресурсом процессорным критическим ресурсом Задача пользователя представлялась прямоугольником, со сторонами равными числу процессоров и времени решения, и составление расписания решения задач рассматривалось как упаковка прямоугольников в полосу (множество полос) с условиями параллельности сторон прямоугольников соответствующим сторонам полосы, неналожения друг на друга, не пересечения сторон полос и минимизацией занятой части полос [43-64,97-99].

Диспетчирование заявками пользователей, требующих каждая для своего обслуживания несколько процессоров одновременно, выходит за рамки классической теории расписаний [65]. Принцип оптимизации как машинный поиск наилучшего распределения выявил трудомкость по времени [66-71,86-88], делающей невозможным использование этих методов в Grid- диспетчере.

Эвристические алгоритмы диспетчирования планарными ресурсами, активно разрабатывавшиеся в конце прошлого и начале нынешнего века [49,50,65,72,73,97-99], недостаточны как по результативности, так и по эмпиричности подходов.

По мере развития технологии, росту числа процессоров, увеличения быстродействия телекоммуникационных сетей учт ресурсов в Grid- системах должен становиться вс более сбалансированным, а ресурсы- равноправными, паритетными. Это позволяет сформулировать фундаментальный принцип паритетности ресурсов и предложить для Grid- систем с централизованной структурой системы диспетчирования и ко-аллокацией ресурсов (мульти- сайтное диспетчирование) паритетную модель ресурсного квадранта [74-81] (рисунок 1.3).

процессоры время Рис. 1.3. Модель паритетности ресурсов В результате приходим к необходимости определить среду диспетчирования- основу формального аппарата предлагаемой работы [81].

Указанная среда позволяет выявить три квадратичных типа массивов задач [75, 76,81] и осуществить адаптацию полиномиальных алгоритмов диспетчирования к свойствам массивов [75-81].

1.2. Среда ресурсных прямоугольников При представлении заявки пользователя для обслуживания Grid- системой введм понятие «ресурсный прямоугольник». Ресурсным прямоугольником назовм фигуру (рисунок 1.4), у которой горизонтальное и вертикальное измерения принимаются равными числу единиц ресурса времени и процессоров, требуемому для обработки заявки, соответственно. Символом a j1 b j1 или a j1, b j1 обозначим j1 - ю заявку, требующую a j1 единиц времени и b j единиц процессоров.

b j a j Рис. 1.4. Ресурсный прямоугольник Несмотря на визуальное сходство ресурсного прямоугольника с геометрическим, сами они принципиально различаются. Звенья- измерения геометрического прямоугольника имеют размерность единиц длины, одного рода однородны. В тоже время звенья- измерения ресурсного прямоугольника имеют размерность единиц ресурса одного рода (процессоры) и другого рода (время) разнородны.

Чтобы отличить ресурсные звенья- измерения от геометрических величин, вводим символику унодных импульсов 1- го, 2- го рода a j1 a j1 (1) j1, b j1 b j1 ( 2) j2, ' ' j j 1 с коэффициентами гомотетии a j1, b j1 в качестве упомянутых звеньев. Здесь 1, j1 j1, ( 2) ' 1, j2 j2, ' ' (j1 ) j j2 ' ' 1 ' j 0, j1 j1, 2 0, j2 j2.

Основной моделью Z 1 - среды диспетчирования полагаем полосу граней (рисунок 1.5) единичной высоты и оснований- звеньев- измерений 1- го рода a j1 (1) j1 1.

' j...

a(1) a(2) a(0) Рис. 1.5. Линейная полиэдраль граней единичной высоты При убывании звеньев- измерений оснований a j1, j1, используем алгебраизацию Z 1 - кругового квадратичного типа с Z- разностью 1 S1 1, где S1 - единичный сдвиг S1Y j1 Y j1 1;

круговыми унодными импульсами (1) j ' j с гармоническим изображением W1 j1, W1 exp i.

k При возрастании звеньев- измерений оснований a j1, j1, используем алгебраизацию Z co - гиперболического квадратичного типа с Z co - разностью 1 j1 (j1) j1' co S1 1 и гиперболическими унодными импульсами с гармоническим изображением W1 j1.

Дополнительно предполагается выполнение условия ограниченности оснований граней единичной высоты (малые основания) a j1'.

k max a j1 Ak, Ak 0 j1 k j1 ' max a j1 Ak Грани единичной высоты с большими основаниями 0 j1 k Z1 относим к параболической алгебраизации с разностью Z pa pa pa j1 1S1j1 1 j1S1j1, j1 0, 1,, k 1 и параболическими унодными 1 j1 j1 (j1) j1', j1 1, 2,, k импульсами с изображениями гармониками с линейно возрастающей амплитудой j1 W1 j1.

k 1 k Ck Круговой Z 1 - первообразной 1- го порядка сопоставляется j1 k k k 1 j1 1 k Ck2, третья итерация 1 j вторая итерация j1 0 j 2 0 j1 j1 j1 k 1 j1 1 j 2 1 k 1 j1 1 k 1 j2 j1 0 j 2 0 j3 0 j1 0 j 2 0 j1 j1 j1 1 j1 2 k k 1k 2 C 3, k j1 1 j1 j1 k j1 0 6 6 и т.д. Сумма k Ck j1 f j1 (1.1) j1 определяет k- кратную круговую первообразную Z 1 - функции f j1.

Соответственно, выражение k 1 1 Ck j1 f j j (1.2) j1 определяет k- кратную первообразную в гиперболической Z co - алгебраизации.

Для параболического случая первообразная в Z 1 - алгебре имеет вид pa k j1 f j1 усреднения по отношению к распределению интегрирования, j1 а k- кратная первообразная – вид k - j1 k f j.

k j (1.3) k!

j1 Z 1 - среда граней единичного измерения 2- го рода с указанными элементами и действиями определяет среду диспетчирования линейных полиэдралей таких ресурсных элементов (рисунок 1.5).

Для полного определения параболического типа линейной полиэдрали a j1 1 (рисунок 1.6) необходимо множество граней единичной высоты расширить альтернативным множеством граней единичных оснований 1 b j (рисунок 1.7).

b j a j1 Рис. 1.6. Грань единичной высоты Рис. 1.7. Грань единичного основания 1Y j1 1, Y 0 0 Y j1 j Тогда получаем модельную кинетику линейного роста амплитуды и грани единичных оснований 1 j1 (рисунок 1.8). Y1 обозначает ось ресурса времени, Y2 - ось ресурса процессоров.

Y (k,k)...

... k 0 2 Y Рис. 1.8. Линейная полиэдраль граней единичных оснований 1 j Покажем, что данные грани имеют высокие вертикальные измерения в k max b j1 Bk, Bk b j1.

соответствии с условием Имеем 1 j1 k j1 k k k k Bk b j1 j1 Bk k 1. Следовательно, для 2 k j1 1 j1 k максимальной высоты bk k справедлива оценка k 1, k 2 и грани k имеют высокие вертикальные измерения.

1 b j1, b j1 j1, Заметим, что грани сублинейного уровня b0 0, bk k имеют высокие вертикальные измерения k k max b j1 k b j1 Bk j1 и относятся к параболической 1 j1 k j1 1 j1 квадратичной типизации.

Z1 В основу определения модельной квадратичной алгебраизации распределений полагаем наклонную форму линейного канонического полигона (рисунок 1.9).

j k j + j =...

k...

...

11 0 k k j линейный канонический полигон Рис. 1.9. Наклонная форма линейного канонического полигона j2 k j Уровневая функция указывает левые отсчты граней с единичными основаниями 1 k j1 модельной линейной параболической полиэдрали (рисунок 1.10).

j k...

011 j 1k Рис. 1.10. Левые отсчты граней с единичными основаниями Распределение граней 1 b j1 с левыми отсчтами сублинейного роста b j1 k j1, j1 0, k Z 1, относим к параболическому квадратичному типу линейных полиэдральных массивов по признаку быстрого убывания высот граней (рисунок 1.11).

Y k быстрое изменение высот граней...

k Y Рис. 1.11. Грани с быстрым убыванием высот Распределение граней 1 b j1 с левыми отсчтами суперлинейного роста b j1 k j1, j1 0, k Z 1, относим к круговому или гиперболическому квадратичному типу линейных полиэдральных массивов по признаку медленного убывания высот граней (рисунок 1.12).

Y k медленное изменение высот граней...

011 1 k Y Рис. 1.12. Грани с медленным убыванием высот В итоге, Z 1 - среда элементов диспетчирования образована гранями a j1 1 и гранями единичных оснований 1 b j1 с единичной высоты указанными выше действиями над ними и метрированием Z- интегралами Z 1, Z co, Z 1 - алгебраизаций. На этой основе возникает линейная полиэдраль граней pa a j1 b j1 в качестве основной модели Z 2 - среды диспетчирования (рисунок 1.13).

Y Y Рис. 1.13. Линейная полиэдраль ресурсных прямоугольников a j1 b j Меру ресурсного прямоугольника определим величиной 1 a j1 b j1 b j1 a j1 2 1 b j1 a j1 называемой эвристической, a j1 b j1 2a j1 b j 2 a j1 b j мерой, состоящей из площади и показателя асимметрии прямоугольника b j1 a j1 2, учитывающего его форму [81].

Определим операции сложения, умножения, дифференцирования и динамического интегрирования ресурсных прямоугольников, ориентированные на диспетчирование множественного компьютерного обслуживания [81].

1) Операция сложения ресурсных прямоугольников. Введм уровневую a0, b0, Y b1 ресурсного функцию Y b0 ресурсного прямоугольника a1, b1.

прямоугольника Операцию сложения двух ресурсных прямоугольников в среде диспетчирования (рисунок 1.14) определим как горизонтальную суперпозицию с уровневой функцией y A0 b0, y A1 b1, A0 0, A1 a0.

b(0) a(0) b(0) Y(0) = b(0) b(1) Уровневая функция первого a(1) a(0) ресурсного прямоугольника Y(A(0)) = b(0), Y(A(1)) = b(1), A(0) = 0, A(1) = a(0) b(1) Уровневая функция суммы двух a(1) ресурсных прямоугольников Y(0) = b(1) Уровневая функция второго ресурсного прямоугольника Рис. 1.14. Операция сложения двух ресурсных прямоугольников Отметим, что введнная выше линейная полиэдраль заявок пользователей k a j1, b j1 определяется результатом сложения составляющих е ресурсных j1 a j1, b j прямоугольников в среде диспетчирования с уровневой функцией j1 1 k y A j1 b j1, A0 0, A j1 a j1, Ak a j1, k- количество заявок.

' j1 j1 ' 2) Операция умножения ресурсных прямоугольников. Операцию умножения двух ресурсных прямоугольников в среде диспетчирования определим как такое размещение этих прямоугольников, у которых объемлющий ресурсный прямоугольник имеет минимальную эвристическую меру L H 1 LH min 1.15). Объемлющий ресурсный (рисунок 2 a b a b прямоугольник- это ресурсная оболочка, имеющая минимально возможную протяжнность и высоту и содержащая исходные прямоугольники, упорядоченные некоторым образом. Внутри ресурсной оболочки заявки пользователей размещаются по правилам аддитивности (неналожения), ориентированности (сохранения координатности, без поворотов) и целостности грани [49,65].

H H b b, a a L L Рис. 1.15. Операция умножения двух ресурсных прямоугольников 3) Операция дифференцирования ресурсных прямоугольников. Обозначим 1 a j1 1 a j1, 2 b j1 1 b j1.

Операцию дифференцирования двух ресурсных прямоугольников в среде диспетчирования определим как 1 2.

При 1 2 0 пара ресурсных прямоугольников является сравнимой (рисунок 1.16), а при 1 2 0 - несравнимой (рисунок 1.17).

a j a j b j b j1 b j1 b j1 a j1 1 a j1 Рис. 1.16. Сравнимая пара Рис. 1.17. Несравнимая пара ресурсных ресурсных прямоугольников прямоугольников 4) Операции динамического интегрирования ресурсных прямоугольников.

Интегрирование называем динамическим, т.к. заранее не известно сколько и каких граней будет в суперпозиции. Наилучшее приближение протяженности L с j a j1 L недостатком посредством горизонтальной суперпозиции граней j1 j a j1, b j1 (рисунок 1.18) назовм операцией динамического интегрирования j1 ресурсных прямоугольников по горизонтали.

Y b(1) b j...

b(2) a j 0 L Y a(1) a(2) приближаемая протяженность Рис. 1.18. Операция динамического интегрирования по горизонтали j b j1 H Наилучшее приближение уровня с недостатком H j1 j a j1, b j посредством вертикальной суперпозиции граней (рисунок 1.19) j1 назовм операцией динамического интегрирования ресурсных прямоугольников по вертикали.

Y приближаемый H уровень b j a j...

b(2) a(2) b(1) a(1) 0 Y Рис. 1.19. Операция динамического интегрирования по вертикали Наилучшее приближение рамки протяженности L и уровня H с недостатком j a j1, b j посредством продольной суперпозиции граней (рисунок 1.20) с j1 j0 j a j1 L 0, b j1 H проекциями назовм операцией продольного j1 1 j1 динамического интегрирования ресурсных прямоугольников.

Y приближаемый H уровень b j a j...

b(2) a(2) b(1) a(1) 0 L Y приближаемая протяженность Рис. 1.20. Операция продольного динамического интегрирования Таким образом, определена среда диспетчирования множественного компьютерного обслуживания заявок пользователей как формальный аппарат управления распределением вычислительно- временных ресурсов. Введнные операции являются базовыми для диспетчирования. Как отмечалось выше, линейная полиэдраль заявок пользователей, является результатом операции сложения. Операции дифференцирования, используемые при определении сравнимости прямоугольников, лежат в основе квадратичной типизации линейных полиэдралей заявок пользователей следующего параграфа 1.3.

Аппаратом полиномиальных алгоритмов диспетчирования в главах 2-4 служит динамическое интегрирование. В основе эвристической меры оценки качества алгоритмов диспетчирования лежит операция умножения.

1.3. Классификация массивов заявок k a j1, b j Упорядочим линейную полиэдраль последовательных j1 ресурсных прямоугольников по убыванию высот граней b j1, j1. Определим левый отсчт ресурсного прямоугольника как левую верхнюю вершину (рисунок 1.21).

левый отсчет ресурсного прямоугольника Рис. 1.21. Левый отсчт ресурсного прямоугольника Введм понятие хорды данной графики как линейной функции от левой верхней вершины до правой нижней вершины упорядоченной линейной полиэдрали (рисунок 1.22).

k 1, b0 max b j1, Ak x y a j1.

(1.4) Ak b0 j1 j1 Y хорда Y Рис. 1.22. Хорда линейной полиэдрали На основе данного построения выделяются два типа:

1) класс линейных полиэдралей, все левые отсчты граней которых превышают хорду в общей точке A j1 на горизонтали a j1', j1 b A j1 y A j1, A j j1 ' 2) класс линейных полиэдралей, все левые отсчты граней которых мажорируются уровнями хорды в общих точках bA j1 yA j1.

Проиллюстрируем введнные определения двух классов линейных полиэдралей. Рассмотрим пару ресурсных прямоугольников с превалированием левого отсчта второй грани над хордой b1 ya0 (рисунок 1.23).

b(0) b(1) a(0) a(1) Рис. 1.23. Пара прямоугольников первого типа Случай тройки ресурсных прямоугольников последовательного горизонтального синтеза с убыванием высот граней и левыми отсчтами, находящимися над хордой от левой максимальной до правой нулевой по уровню вершины полиэдрали b1 ya0, b2 ya0 a1, относим к первому типу (рисунок 1.24).

b(0) b(1) b(2) a(0) a(1) a(2) Рис. 1.24. Тройка прямоугольников первого типа Горизонтально последовательную пару ресурсных прямоугольников с убыванием высот в случае превалирования хорды над левым отсчтом второй грани yx 1 b1 ya0 (рисунок 1.25) относим ко второму типу.

x a0 a1 b b(0) b(1) a(0) a(1) Рис. 1.25. Пара прямоугольников второго типа Следуя индуктивному детерминированию, тройку ресурсных прямоугольников последовательного горизонтального синтеза с убыванием высот граней и левыми отсчтами, находящимися под хордой от левой максимальной до правой нулевой по уровню вершины полиэдрали yx 1 b1 ya0, b2 ya0 a x a0 a1 a2 b относим ко второму типу (рисунок 1.26).

b(0) b(1) b(2) a(0) a(1) a(2) Рис. 1.26. Тройка прямоугольников второго типа Уровневой функции Y2 bA j1 упорядоченной линейной полиэдрали A j1, bA j1, сопоставляем полигон целых вершин выпуклый относительно начала координат для первого типа (рисунок 1.27) и вогнутый относительно начала- для второго типа (рисунок 1.28).

Y2 Y 0 Y1 Y Рис. 1.27. Выпуклый в начале Рис. 1.28. Вогнутый в начале координат уровневый полигон координат уровневый полигон Уровневая функция с выпуклым в начале координат уровневым полигоном определяется как медленно убывающая, а с вогнутым уровневым полигоном- как быстро убывающая. Необходимо отметить, что случай линейного убывания уровневой функции, с вершинами на хорде, относится к пограничному, промежуточному типу убывания между медленным и быстрым.

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

Далее, вводятся круговой, гиперболический и параболический квадратичные типы линейных полиэдралей [75,76,81].

1) Определим круговой тип линейных полиэдралей. Дополнительно, полагаем признак попарной сравнимости 1 2 0 ресурсных прямоугольников линейной полиэдрали (параграф 1.2, операция дифференцирования ресурсных прямоугольников) и возможность упорядочивания граней по убыванию высот и оснований с возрастанием индексации, j1, определяющим свойством круговой типизации линейной полиэдрали.

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

Приведм базовые примеры массивов заявок кругового типа: натуральных k j1 k j1, j1 0, 1,, k ресурсных квадратов (равные требования процессорного и временного ресурсов a j1 b j1 ) (рисунок 1.29), натуральных k j1, k j1 1, ресурсных прямоугольников горизонтальной формы j1 0, 1,, k 2 (преимущественные требования временного ресурса a j1 b j1 ) 1.30), натуральных ресурсных прямоугольников (рисунок k j1 1, k j1, j1 0, 1,, k 2 (преимущественные вертикальной формы требования процессорного ресурса a j1 b j1 ) (рисунок 1.31).

Y Y Рис. 1.29. Круговая полиэдраль ресурсных квадратов Y Y Рис. 1.30. Круговая полиэдраль прямоугольников горизонтальной формы Y 0 Y Рис. 1.31. Круговая полиэдраль прямоугольников вертикальной формы 2) Определим гиперболический тип линейных полиэдралей.

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

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

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

ресурсных прямоугольников k j1 3k j1, j k k k 1, 2,, k (рисунок 2 2 k j1 3k j1, 1.32), ресурсных прямоугольников горизонтальной формы j1 k, k 1,, k k 1 (преимущественные требования временного ресурса a j1 b j1 ) (рисунок 1.33), ресурсных прямоугольников вертикальной формы k j1 3k j1, j1 1, 2,, k (преимущественные требования процессорного ресурса a j1 b j1 ) (рисунок 1.34).

Y 16х24 17х23 18х22 19х21 20х20 21х19 22х18 23х17 24х16 25х Y Рис. 1.32. Гиперболическая полиэдраль ресурсных прямоугольников Y 16х24 18х22 20х20 22х18 25х Y Рис. 1.33. Гиперболическая полиэдраль прямоугольников горизонтальной формы Y 25х 22х 20х 18х 16х 0 Y Рис. 1.34. Гиперболическая полиэдраль прямоугольников вертикальной формы 3) Определим параболический тип линейных полиэдралей. К параболическому квадратичному типу линейной полиэдрали относим полиэдрали с таким расположением левых отсчтов ресурсных прямоугольников, при котором левые отсчты последовательных граней располагаются под линией, соединяющей максимальную левую вершину отсчтов с минимальной, нулевой правой вершиной граней полиэдрали. В параболической квадратичной типизации ведущим фактором типа является величина рассогласования изменения измерений граней с изменением индексации граней.

Приведм базовый пример массива заявок параболического типа- ресурсные прямоугольники j1 k j1, j1 1, 2,, k 1 (рисунок 1.35).

Y 6 8 10 12 14 16 18 0 Y Рис. 1.35. Параболическая полиэдраль ресурсных прямоугольников Если пара граней убывающих уровней (рисунок 1.36) подчиняется неравенству b b0 b1 a0, (1.5) a0 a yx x 1 в то левый отсчт второй грани превышает уровень хорды a0 a1 b точке основания Y1 a0 рассматриваемого отсчта.

Y b(0) b(1) 0 a(0) a(1) Y Рис. 1.36. Крутизна уровневой функции меньше крутизны хорды b0 b Крутизна уровневой функции tg меньше крутизны хорды a b tg (рисунок 1.36). Если выполнено неравенство (1.5) и неравенство a0 a a1 a0, то пара граней относится к круговому квадратичному типу. Имеет место медленное убывание уровней и сравнимость граней b1 b0, a1 a0.

Если выполнено неравенство (1.5) и неравенство a1 a0, то пара граней относится к гиперболическому квадратичному типу. Имеет место медленное убывание уровней и несравнимость граней b1 b0, a1 a0.

При противоположном соотношении крутизны уровневой функции и хорды tg tg, b1 ya0 (рисунок 1.37), имеем быстрое убывание левых отсчтов и параболический квадратичный тип пары граней убывающих уровней.

Y b(0) b(1) 0 a(0) a(1) Y Рис. 1.37. Крутизна уровневой функции больше крутизны хорды Понятие уровневой функции левых отсчтов граней упорядоченной a j1', j1 линейной полиэдрали Y2 b A j1, A j1 и крутизны уровневой j1 ' функции b0 b1 b1 b2 b j b j1 tg 0, tg 1,, tg j1 a0 a1 a j j1 0, 1,, k 2, распространяются на общее количество граней полиэдрали и b. При tg j1 tg, соответствующую хорду (1.4) с крутизной tg Ak j1 0, 1,, k 2, имеем медленное убывание уровней и выпуклый по отношению к хорде полигон упорядоченной линейной полиэдрали граней с убывающими высотами. При tg j1 tg, j1 0, 1,, k 2, имеем быстрое убывание уровней граней и вогнутый в начале координат полигон ниже упомянутой хорды.

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

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

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

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

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


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

В основу классификации массивов триодных полиэдралей заявок a j1 b j1 j2 (рисунок 1.39), соответственно, полагаем пользователей j1 j различие медленного и быстрого убывания уровней вертикальных слов H A j1 b j1 j2 (рисунок 1.40).

j Y Y Рис. 1.39. Триодная полиэдраль заявок пользователей...

b j1 j2 H A j...

a j Рис. 1.40. Вертикальный слой заявок пользователей триодной полиэдрали j1 j2, Так, триодная полиэдраль имеет уровни j1 j2 k j1 k j1 k j, j1 быстрого убывания в каноническом H j2 0 j1 j2 k, j1, j2 0, k Z треугольнике 1.41) и уровни (рисунок j1 j2 k k 1 const k медленного поведения в каноническом квадрате H j2 j1, j2 0, k Z 1 (рисунок 1.42).

Y Y 1 2 3 1 4 3 2 1 0 Y1 Y Рис. 1.41. Триодная полиэдраль Рис. 1.42. Триодная полиэдраль канонического треугольника канонического квадрата Таким образом, в параграфе определяется и анализируется хорда линейной полиэдрали в сопоставлении со свойством согласованности, антисогласованности, рассогласованности изменения измерений граней, положенным в основу различия массивов кругового, гиперболического и параболического квадратичных типов.

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

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

В [50,82-84] рассматривались четыре классические модели упаковки прямоугольников:

1) в полосу с минимизацией занятой части Two-Dimensional Strip Packing Problem (2SP);

2) в идентичные прямоугольные рамки с минимизацией их количества Two Dimensional Bin Packing Problem (2BP);

3) в объемлющий квадрат минимальной площади Square Packing (SP);

4) в объемлющий прямоугольник минимальной площади Rectangular Packing (RP) [82] или Rectangle Packing Area Minimization Problem (RPAMP) [84].

В соответствии с этими моделями и моделью паритетности ресурсов, мы предлагаем и исследуем для заданного множества ресурсных прямоугольников задачу минимизации эвристической меры ресурсной оболочки в первом квадранте [74-81].

Эвристическую меру ресурсной оболочки определим полусуммой L H отношений ресурсной меры L H и меры асимметрии оболочки к k a j1 b j суммарной мере охватываемых планарных элементов [79,81]. Здесь j1 L - протяжнность по горизонтали, H - уровень по вертикали ресурсной оболочки (рисунок 1.43).

процессоры H время L Рис. 1.43. Ресурсная оболочка перераспределнного массива заявок пользователей Целевая функция задачи минимизации эвристической меры ресурсной оболочки имеет вид 1 LH L H min.

2 k a j1 b j j 0 1 Ограничения на неналожение ресурсных прямоугольников:

y1i ai y1 j или y1 j a j y1i или y2i bi y2 j или y2 j b j y2i, i, j, i j, i 0, k 1 Z 1, j 0, k 1 Z 1.

Ограничения на размещение внутри ресурсной оболочки:

y1i ai L, i 0, k 1 Z 1, y2i bi H, i 0, k 1 Z 1, y1i, y2i 0.

Приведнные выше ограничения аналогичны изложенным в [70,85]. Через обозначены координаты левой нижней вершины ресурсного y1i, y2i прямоугольника ai, bi, i 0, k 1 Z 1.

Рассмотрим базовый пример оптимизации пары ресурсных прямоугольников по ресурсной мере- сокращнной форме эвристической меры [74,120,123-125]. Для ресурсного прямоугольника L H, содержащего пару ресурсных прямоугольников a b, (рисунок 1.44) ставим вопрос о L H минимизации ресурсной меры надлежащим синтезом ресурсных прямоугольников в ресурсную оболочку.

H b a L Рис. 1.44. Ресурсный прямоугольник с парой ресурсных прямоугольников a b, Для пары ресурсных прямоугольников предлагается горизонтальный (рисунок 1.45, вверху) или вертикальный (рисунок 1.45, внизу) синтез с вычислением ресурсной меры ресурсной оболочки.

maxb, b a a b a, b b a maxa, Рис. 1.45. Ресурсные оболочки горизонтального и вертикального парного синтеза Для пары ресурсных прямоугольников кругового типа, упорядоченной по убыванию высот, a, b горизонтальный синтез дат ресурсную оболочку с a maxb, a b. Вертикальный синтез дат ресурсной мерой оболочку с ресурсной мерой maxa, b a b. Круговой ресурсную тип пары ресурсных прямоугольников означает превалирование левого отсчта x y b 1 y b второй грани над хордой x. Условие превалирования a b a b имеет вид b a b. Ресурсная оболочка горизонтального синтеза a a меньше чем вертикального синтеза, если a b a b, т.е. в случае, когда b a или b b горизонтальный b. Таким образом, для диапазона a a синтез является оптимальным (рисунок 1.46).

Ресурсная оболочка вертикального синтеза меньше чем горизонтального синтеза, если a b a b, т.е. в случае, когда a b или b. Таким a b образом, для диапазона вертикальный синтез является b a a оптимальным (рисунок 1.47).

b b a a Рис. 1.46. Ресурсная оболочка Рис. 1.47. Ресурсная оболочка горизонтального синтеза вертикального синтеза прямоугольников кругового типа прямоугольников кругового типа Для пары ресурсных прямоугольников гиперболического типа, упорядоченной по убыванию высот, a, b горизонтальный синтез дат a maxb, a b.

ресурсную оболочку с ресурсной мерой Вертикальный синтез дат ресурсную оболочку с ресурсной мерой maxa, b b. Гиперболический тип пары ресурсных прямоугольников также означает превалирование левого отсчта второй грани над хордой, т.е. b. Ресурсная оболочка горизонтального синтеза меньше a чем вертикального синтеза, если a b b, т.е. в случае, когда ab a a b b или b. Таким образом, для диапазона max b, a горизонтальный синтез является оптимальным. На рисунке 1.48 слева a b проиллюстрирован случай, когда max b, на рисунке 1. b, a a a a b b.

справа- max b, a Ресурсная оболочка вертикального синтеза меньше чем горизонтального синтеза, если b a b, т.е. в случае, когда ab или a b.

a b Таким образом, для диапазона b вертикальный синтез является a оптимальным (рисунок 1.49).

a b b b, a a Рис. 1.48. Ресурсная оболочка Рис. 1.49. Ресурсная оболочка горизонтального синтеза прямоугольников вертикального синтеза гиперболического типа прямоугольников гиперболического типа Для пары ресурсных прямоугольников параболического типа, упорядоченной по убыванию высот, b горизонтальный синтез дат ресурсную оболочку с ресурсной мерой a maxb, a b. Вертикальный синтез дат ресурсную оболочку с ресурсной мерой maxa, b. Параболический тип пары ресурсных прямоугольников означает превалирование хорды над левым отсчтом второй грани, т.е. b. Рассмотрим две возможные ситуации a a, a. В случае, когда a, ресурсная мера вертикального синтеза равна b. Когда a, ресурсная мера вертикального синтеза равна a b.

Ресурсная оболочка горизонтального синтеза меньше чем вертикального синтеза, если a b b в одном случае и a b a b в другом a случае. В первом случае, ab или b. Таким образом, для диапазона a b при a b горизонтальный синтез является оптимальным a (рисунок 1.50).

b a Во втором случае, или b. Таким образом, должно a b выполняться неравенство b. Однако, оно невыполнимо, т.к. не a a существует, при котором. Следовательно, для диапазона a a b a 1 при оптимальным является вертикальный синтез (в b a соответствии с рисунком 1.51).

b b a a Рис. 1.50. Ресурсная оболочка Рис. 1.51. Ресурсная оболочка горизонтального синтеза вертикального синтеза прямоугольников параболического типа прямоугольников параболического типа Ресурсная оболочка вертикального синтеза меньше чем горизонтального синтеза, если b a b в одном случае и a b a b в другом a случае. В первом случае, ab или b. Таким образом, для диапазона a 1 min b при a вертикальный синтез является оптимальным.

b, a На рисунке 1.52 слева проиллюстрирован случай, когда a a a b b b.

b, на рисунке 1.52 справа- min min b, b, a a a a a b b, Рис. 1.52. Ресурсная оболочка вертикального синтеза при a 1 min b, a b, a Во втором случае, a b или b. Таким образом, для диапазона a 1 b при a вертикальный синтез является оптимальным (рисунок a 1.53).

b a Рис. 1.53. Ресурсная оболочка вертикального синтеза при b, a a Изложим принцип эвристики, альтернативный принципу оптимизации целевого критерия [128]. Классический принцип оптимизации состоит в определении решения приведнных выше задач 2SP, 2BP, SP, RP (RPAMP) локальными динамическими переходами из некоторого начального положения массива заявок. Разработке метода динамической оптимизации планарных распределений посвящены работы [66-71,86-88].

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

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

1.5. Выводы 1. Заявка пользователя на компьютерное обслуживание формализуется понятием ресурсного (неэвклидова) прямоугольника.


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

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

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

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

Глава 2. Массивы заявок кругового типа 2.1. Однородный алгоритм Рассмотрим массивы линейных полиэдралей квадратичный тип которых обладает свойством однородности, определяемым ниже [77].

Пусть грани линейной круговой полиэдрали имеют горизонтальную форму k a j1, b j1, a j1 b j1 и парную транспонированную униаддитивность j1 измерений 2- го рода b1 bk b2 bk 1 bm bm 1 const., k 2m.

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

Пусть имеется линейная гиперболическая полиэдраль. Выделением центрального элемента с минимальной асимметрией измерений b j1, a j1, b j1 a j1 заданной линейной гиперболической полиэдрали, j1, a j1, b j разбиваем последнюю на подмножества граней левее и правее j1 k a j1, b j1.

центральности j1 j1, В случае транспонированности элементов (рисунок 2.1) симметричного расположения относительно центра a j1, j1,, b j1, j1, a j1, j1,, b j1, j1, предыдущая линейная гиперболическая полиэдраль относится к однородно гиперболическому квадратичному типу.

a b, a b Рис. 2.1. Транспонированная пара ресурсных прямоугольников Рассмотрим однородный алгоритм упорядочивания линейных полиэдралей однородно- кругового квадратичного типа в ресурсную оболочку по критерию ресурсной меры.

10. Производим попарный транспонировано- симметричный синтез граней a j1, b j1 ak j1, bk j1 суперпозицией вдоль вертикали (рисунок 2.2).

ak j bk j b j a j Рис. 2.2. Парный транспонировано- симметричный синтез Ресурсная оболочка парного синтеза имеет протяжнность по горизонтали maxa j1 ;

ak j1 и уровень по вертикали b j1 bk j1 H, где H const общее значение аддитивности транспонировано- симметричных измерений 2- го рода.

20. Построенные оболочки суперпозируем последовательно по горизонтали в полосу уровня и протяжнности (рисунок 2.3) H m maxa j1 ;

ak j1, L 2m k.

j1 H maxa1;

ak 1 maxa2;

ak Рис. 2.3. Горизонтальный синтез ресурсных оболочек k j1 j1, k 2m Для натуральных ресурсных квадратов парным j1 вертикальным транспонированным синтезом граней получаем ресурсные оболочки j1 m j1 k j1 1, j1 1, 2,, m, общего уровня k 1 (рисунок 2.4) 1 k+1 k+ k k-,,...

k k- Рис. 2.4. Ресурсные оболочки натуральных квадратов m j1 m, k Горизонтальная суперпозиция данных блоков образует j1 H k полосу уровня и протяжнности (рисунок 2.5) mm m j1 m m k L, m.

2 j1 k+ Рис. 2.5. Горизонтальный синтез блоков ресурсных квадратов k 32 H 33, L 256 136 392.

В частности, при имеем Соответствующие построения приведены на рисунке 2.6.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 Рис. 2.6. Укладка однородно- круговой линейной полиэдрали ресурсных квадратов Сравним качество приведнного однородного алгоритма с оптимальной укладкой в объемлющий прямоугольник минимальной площади, полученной в работах Приведм в таблице 2.1 результаты размещения [66-68,70,71].

однородным и оптимальным алгоритмами для последовательности натуральных ресурсных квадратов k j1 k j1, j1 0, 1,, k 1. Здесь L- горизонтальное и вертикальное измерения объемлющего прямоугольника однородного H алгоритма, Lopt, H opt - соответствующие измерения оптимального алгоритма, погрешность площади ресурсной оболочки в % относительно оптимального значения.

Таблица 2.1. Сравнение однородного и оптимального алгоритмов,%,% Lopt, H opt Lopt, H opt L, H L, H k k 12 6 47 145 5 20 19 16, 5 9 11 34 15 7 155 6 6 20 12, 22 8 176 7 14,3 21 15, 38 11 26 9 187 14 15 39 8 11,4 22 12, 210 24 64 35 9 16,7 23 15, 15 40 11 222 25 56 10 8,6 24 12, 15 247 19 51 11 19,3 25 15, 43 57 13 260 12 11,1 26 12, 23 29 70 70 14 287 22 13 17,2 27 15, 77 15 301 14 11,6 28 12, 23 45 92 16 330 15 16,4 29 15, 23 55 100 17 345 16 12,4 30 12, 28 54 117 18 376 39 17 17,4 31 20, 126 19 392 18 11,9 32 12, 31 69 Видим, что погрешность не превосходит 21%, причм на массивах с чтным числом натуральных ресурсных квадратов не более 13%, что является подтверждением целесообразности использования предложенного однородного алгоритма при диспетчировании процессорно- временными ресурсами.

Для рамочного M M распределения синтезированных блоков общего уровня H и протяжнностей maxa j1 ;

ak j1 применяем горизонтальный синтез наилучшего приближения измерения M с недостатком последовательными отрезками j1 - индексации указанных оснований. Получаем некоторый массив ресурсных оболочек M 0 H. В одной рамке размещаем M H ресурсных оболочек (рисунок 2.7).

M H...

M H H Рис. 2.7. Заполнение рамки ресурсными оболочками Условие медленного убывания высот граней линейной полиэдрали при парном синтезе транспонировано- симметричных граней в условиях однородной круговой типизации влечт за собой эвристически- контролируемое построение ресурсной оболочки по критерию заполненности. Действительно, указанный парный синтез по вертикали приводит к пустотности площадью, равной ak j1 a j1 bk j1 ak j1 a j1 b j1. Наличие нижней оценки с a j1 b j медленностью убывания сдерживает величину приращения оснований симметричных синтезируемых граней и, тем самым, уменьшает меру незаполненности упомянутой ресурсной оболочки.

Рассмотрим алгоритм упорядочивания линейных полиэдралей однородно гиперболического квадратичного типа в ресурсную оболочку по критерию ресурсной меры. Линейная полиэдраль натуральных гиперболических ресурсных k k k прямоугольников k j1 3k j1, k 10, j1 1, 2,, k с убыванием 2 2 высот и ростом оснований относится к однородно- гиперболическому квадратичному типу. Элемент с индексацией j1 k k j1 3k j1 2k 2k является центральным. Грани симметричного расположения относительно центрального квадрата k j1 3k j1 k k j1 3k k j1 2k j1 2k j k j1 3k j1 k k j1 3k k j1 2k j1 2k j образуют транспонированную пару. Поэтому вертикальный синтез транспонированных пар указанных граней дат ресурсные оболочки общего 2k j1 2k j1 4k k j уровня и протяжнности для k k j1 1, 2,, k 1, что аналогично приведнному выше, позволяет 2 вычислить параметры оболочки горизонтального синтеза блоков. Факторизация данной полосы на допустимые протяжнности наилучшего приближения рамочного измерения M, как и выше, позволит построить требуемое рамочное распределение указанного массива ресурсных гиперболических прямоугольников.

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

Массив a j1 b j1 j2, H j1 b j1 j2 (2.1) j при условии парной униаддитивности суммарных высот H 1 H k H 2 H k 1 H m H m 1 H, k 2m транспонировано- симметричных вертикальных слов локализуется в полосу m maxa j1 ;

ak j1 H (2.2) j1 в качестве ресурсной оболочки по критерию ресурсной меры.

Парная вертикальная суперпозиция граней, образованных j1 - ым и k j1 ым вертикальными слоями триодной полиэдрали (2.1), с последующим горизонтальным синтезом блоков- оболочек maxa j1 ;

ak j1 H по формуле (2.2) дат требуемую полосу. Триодную полиэдраль (2.1) превращаем в линейную a j1 b j1 j2 a j1 b j1 j полиэдраль, принимая вертикальные слои в j2 j качестве граней- блоков. В итоге, квадратично- однородная типизация линейных полиэдралей обобщается на триодные полиэдральные массивы.

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

Делаются выводы о качестве предложенного эвристического полиномиального однородного алгоритма.

2.2. Начально- кольцевой алгоритм Приведм и исследуем начально- кольцевой алгоритм диспетчирования линейными круговыми полиэдралями ресурсных прямоугольников k a j1, b j1, b j1, a j1, j1 [81].

j1 10. Максимальным ресурсным элементом образуем начальную оболочку (рисунок 2.8).

Y b(0) a(0) Y Рис. 2.8. Начальная ресурсная оболочка 20. На втором шаге вдоль правой стороны оболочки Y1 a0 вертикально q a j1, b j суперпозируются последующие ресурсные прямоугольники до j1 q b j1 b0 наилучшего приближения уровня оболочки с недостатком j1 (операция динамического интегрирования ресурсных прямоугольников по вертикали). Здесь q1 - число ресурсных прямоугольников, суперпозированных в вертикальном слое. Строится новая ресурсная оболочка полученной совокупности ресурсных прямоугольников (рисунок 2.9).

Y b(0) b(1) a(1) a(0) Y Рис. 2.9. Первая ресурсная оболочка 30. Затем, над верхней стороной достигнутой оболочки вдоль горизонтали на упомянутом уровне Y2 b0 суперпозируются последовательно оставшиеся q1 q a j1, b j1 до наилучшего приближения с недостатком величины элементы j1 q1 q1 q a j1 a0 a1 протяжнности оболочки (операция динамического j1 q1 интегрирования ресурсных прямоугольников по горизонтали). Здесь q2 - число ресурсных прямоугольников, суперпозированных в горизонтальном слое.

Строится новая ресурсная оболочка полученной совокупности ресурсных прямоугольников (рисунок 2.10).

Y b(2) b(3) a(2) a(3) b(0) b(1) a(1) a(0) Y Рис. 2.10. Вторая ресурсная оболочка 40. На следующем шаге вновь вдоль правой стороны достигнутой оболочки Y1 a0 a1 вертикально суперпозируются последующие ресурсные q1 q 2 q a j1, b j прямоугольники до наилучшего приближения уровня j1 q1 q 2 q1 q 2 q b j1 b0 bq1 1 оболочки с недостатком (операция динамического j1 q1 q 2 интегрирования ресурсных прямоугольников по вертикали). Здесь q3 - число ресурсных прямоугольников, суперпозированных в вертикальном слое. Строится новая ресурсная оболочка (рисунок 2.11).

Y b(6) b(2) a(6) b(3) a(2) a(3) b(5) a(5) b(0) b(1) b(4) a(1) a(0) a(4) Y Рис. 2.11. Третья ресурсная оболочка 50. Далее, над верхней стороной достигнутой оболочки вдоль горизонтали Y2 b0 bq1 1 суперпозируются последовательно оставшиеся элементы q1 q 2 q3 q a j1, b j1 до наилучшего приближения с недостатком величины j1 q1 q 2 q3 q1 q 2 q3 q a j1 a0 a1 aq1 q2 1 протяжнности оболочки (операция j1 q1 q 2 q3 динамического интегрирования ресурсных прямоугольников по горизонтали).

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

60. Введнный таким образом начально- кольцевой алгоритм повторяем до полного исчерпания ресурсных прямоугольников массива. Строится конечная ресурсная оболочка (рисунок 2.12).

Y b(7) b(8) b(9) a(7) a(8) a(9) b(6) b(2) a(6) b(3) a(2) a(3) b(5) a(5) b(0) b(1) b(4) a(1) a(0) a(4) Y Рис. 2.12. Конечная ресурсная оболочка Обозначим через C- количество шагов начально- кольцевого алгоритма «справа», «сверху». Горизонтальное измерение оболочки определяется как C* L a0 a1 aq1 q2 1 aq1 q2 q3 q4 1 a q j 1, j 1 C 2, при чтном C, где C* C 1, при нечтном C.

Вертикальное измерение оболочки определяется как C* H b0 bq1 1 bq1 q2 q3 1 b q j 1, j 1 C 1, при чтном C, где C * C 2, при нечтном C.

Параметры определены выше, число ресурсных q1, q2, q3, q4 qj прямоугольников, суперпозированных на j - м шаге в вертикальном (нечтное j ) или горизонтальном (чтное j ) слое соответственно.

Приведм блок- схему начально- кольцевого алгоритма (рисунок 2.13).

Введм следующие обозначения. a j, b j - параметры требований пользователей, RA j, RB j - номера временного и k- количество заявок пользователей.

процессорного ресурсов, начиная с которых будет выделено a j, b j единиц соответствующего ресурса для j- ой заявки. AL- номер 1- го ресурса по оси Y1, одинаковый для всех прямоугольников соответствующей вертикальной полиэдрали, BL - номер 2- го ресурса по оси Y2, одинаковый для всех прямоугольников соответствующей горизонтальной полиэдрали. A, B-параметры текущей оболочки соответственно по ресурсам 1- го, 2- го рода.

Отметим, что количество операций работы начально- кольцевого алгоритма составляет k операций сложения и k операций сравнения, т.е. алгоритм является полиномиальным.

В частности, для линейной полиэдрали натуральных ресурсных квадратов при k 32 соответствующие построения приведены на рисунке 2.14. В центре квадрата указано значение его стороны.

Время работы оптимального алгоритма [71] приведено в таблице 2.2.

Таблица 2.2. Время работы оптимального алгоритма Время работы оптимального алгоритма k Linux, 2GHz AMD Opteron 246, 2GB RAM Дни Часы Минуты Секунды 27 - - 35 28 - 4 39 29 - 8 06 30 2 17 32 31 4 16 03 32 33 11 36 Видим, что время оптимальной укладки 32- х квадратов превышает 33 дня.

Начало Ввод a(j), b(j), j = 0,…,K- A = a(0), B = b(0), j = RA(0) = 0, RB(0) = AL = A A = A + a(j) S = 0, i = RA(j + i) = AL RB(j + i) = S i=i+ Нет j + i - 1 K- Да S = S + b(j + i - 1) Да SB Нет j=j+i- BL = B B = B + b(j) S = 0, i = RA(j + i) = S RB(j + i) = BL i=i+ Нет j + i - 1 K- Да S = S + a(j + i - 1) Да SA Нет j=j+i- Вывод A, B, массив RA, RB Конец Рис. 2.13. Блок- схема начально- кольцевого алгоритма 19 18 17 16 15 14 26 24 21 30 29 32 31 28 Рис. 2.14. Укладка круговой линейной полиэдрали ресурсных квадратов начально- кольцевым алгоритмом Графика оптимальной укладки приведена на рисунке 2.15 [71].

27 31 8 19 28 13 22 Рис. 2.15. Оптимальная укладка [71] Эвристические меры ресурсных оболочек оптимального по площади алгоритма приведены в таблице 2.3.

Таблица 2.3. Эвристические меры ресурсных оболочек оптимального алгоритма Эвристическая Эвристическая Эвристическая Эвристическая k k k k мера мера мера мера 1 9 17 0,50 0,57 0,52 1, 2 10 18 0,70 0,71 0,85 0, 3 11 19 0,68 0,57 0,51 1, 4 12 20 0,65 0,54 0,96 0, 5 13 21 0,99 0,67 0,88 0, 6 14 22 0,57 0,75 0,96 1, 7 15 23 0,58 0,92 0,51 0, 8 16 24 0,52 0,73 0,61 0, Видим, что эвристические меры ресурсных оболочек оптимального по площади алгоритма не превосходят величину 1,5.

Сравним качество приведнного начально- кольцевого алгоритма с оптимальной укладкой в объемлющий прямоугольник минимальной площади, полученной в работах [66-68,70,71]. В таблице 2.4 приведены результаты размещения начально- кольцевым и оптимальным алгоритмами для последовательности натуральных ресурсных квадратов k j1 k j1, j1 0, 1,, k 1. Здесь L- горизонтальное и H- вертикальное измерения объемлющего прямоугольника начально- кольцевого алгоритма, Lopt, H opt - соответствующие измерения оптимального алгоритма, - погрешность площади ресурсной оболочки в % относительно оптимального значения.

Таблица 2.4. Сравнение начально- кольцевого и оптимального алгоритмов,%,% Lopt, H opt Lopt, H opt L, H L, H k k 52 43 39 1 0 17 24, 1 1 1 23 57 2 0 18 22, 3 2 31 47 3 0 19 5 3 3 5 61 76 34 4 20 20 21, 5 7 65 98 69 5 20 21 23, 5 12 38 9 11 39 6 11 22 11 10 73 77 69 64 7 17 23 15 12 11 14 15 56 8 20 24 18 14 81 22 9 17 25 15 20 85 77 43 91 10 23,5 26 21, 25 20 15 27 70 19 27 99 11 31 27 23, 28 24 105 12 25,5 28 23, 31 27 23 29 34 30 22 38 110 13 22 29 21, 37 34 116 14 21,5 30 21, 23 45 15 25,8 31 24, 43 37 23 55 16 27 32 17, 48 40 28 54 Заметим, что погрешность не превосходит что является 31%, подтверждением целесообразности использования предложенного начально кольцевого алгоритма при диспетчировании процессорно- временными ресурсами.

Эвристические меры ресурсных оболочек начально- кольцевого алгоритма приведены в таблице 2.5.

Отметим, что эвристические меры ресурсных оболочек начально 0,22.

кольцевого алгоритма не превосходят значения Таблица 2.5. Эвристические меры ресурсных оболочек начально кольцевого алгоритма Эвристическая k Эвристическая k Эвристическая k Эвристическая k мера мера мера мера 1 9 17 0,50 0,68 0,65 0, 2 10 18 0,70 0,68 0,65 0, 3 11 19 0,68 0,68 0,63 0, 4 12 20 0,72 0,66 0,63 0, 5 13 21 0,66 0,63 0,64 0, 6 14 22 0,61 0,62 0,63 0, 7 15 23 0,68 0,66 0,62 0, 8 16 24 0,66 0,66 0,61 0, Для линейной круговой полиэдрали натуральных ресурсных k j1, k j1 1, j1 0, 1,, k прямоугольников горизонтальной формы при k 32 укладка начально- кольцевым алгоритмом приведена на рисунке 2.16.

В центрах прямоугольников указаны их горизонтальное и вертикальное измерения.

19x18 18x17 17x16 16x15 15x14 14x13 13x 26x25 20x 25x24 24x 21x20 7x 30x29 29x28 8x 27x 9x 22x 10x 32x31 31x30 11x 28x27 23x 12x Рис. 2.16. Укладка круговой линейной полиэдрали натуральных ресурсных прямоугольников горизонтальной формы начально- кольцевым алгоритмом Эвристические меры ресурсных оболочек начально- кольцевого алгоритма для натуральных ресурсных прямоугольников горизонтальной формы приведены в таблице 2.6.

Таблица 2.6. Эвристические меры ресурсных оболочек начально-кольцевого алгоритма для натуральных ресурсных прямоугольников горизонтальной формы Эвристическая k Эвристическая k Эвристическая k мера мера мера 18 23 0,68 0,63 0, 19 24 0,66 0,62 0, 20 25 0,65 0,61 0, 21 26 0,64 0,62 0, 22 27 0,64 0,65 0, Отметим, что эвристические меры ресурсных оболочек начально кольцевого алгоритма для прямоугольников горизонтальной формы не 0,18.

превосходят значения Для линейной круговой полиэдрали натуральных ресурсных k j1 1, k j1, j1 0, 1,, k 2 при прямоугольников вертикальной формы k 32 укладка начально- кольцевым алгоритмом приведена на рисунке 2.17.

18x19 17x18 16x17 15x16 14x15 13x14 12x 19x 25x26 24x25 23x24 20x 107 29x30 28x29 7x 26x27 8x 21x 9x 10x 31x32 30x31 27x28 22x 11x Рис. 2.17. Укладка круговой линейной полиэдрали натуральных ресурсных прямоугольников вертикальной формы начально- кольцевым алгоритмом Эвристические меры ресурсных оболочек начально- кольцевого алгоритма для натуральных ресурсных прямоугольников вертикальной формы приведены в таблице 2.7.

Таблица 2.7. Эвристические меры ресурсных оболочек начально-кольцевого алгоритма для натуральных ресурсных прямоугольников вертикальной формы Эвристическая k Эвристическая k Эвристическая k мера мера мера 18 0,63 23 0,62 28 0, 19 0,63 24 0,61 29 0, 20 0,63 25 0,60 30 0, 21 0,64 26 0,59 31 0, 22 0,63 27 0,61 32 0, Отметим, что эвристические меры ресурсных оболочек начально кольцевого алгоритма для прямоугольников вертикальной формы не превосходят 0,14.

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



Pages:   || 2 | 3 | 4 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.