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



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

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

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

Специальность: 05.13.01- Системный анализ, управление и обработка информации (вычислительная техника и информатика)

Автореферат

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

005567516

Таганрог — 2013 г.

005567516

Работа выполнена в федеральном государственном автономном образовательном учреждении высшего профессионального образования «Южный федеральный университет»

Научный консультант:

Официальные оппоненты:

Ведущая организация:

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

доктор технических наук, профессор Барский А.Б.

(ФГБОУ ВПО «Московский государственный университет путей сообщения», г. Москва)

доктор технических наук, профессор Варламов О.О.

ФГБОУ ВПО «Московский автомобильно-дорожный государственный технический университет (МАДИ)», г. Москва

заслуженный деятель науки РФ, доктор технических наук, профессор Заково ротный В Л.

ФГБОУ ВПО «Донской государственный технический университет», г. Ростов-на-Дону

ФГБОУ ВПО «Волгоградский государственный технический университет»

Защита состоится «24» апреля 2014 г. в 14 час. 20 мин. на заседании диссертационного совета Д 212.208.22 по защите диссертаций при ФГОУ ВПО «Южный федеральный университет» по адресу: 347928, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан «5-/ »

Учёный секретарь

диссертационного совета Д212.20^Й доктор технических наук, профессор^0

А.Н. Целых

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Астуальность работы. Всё возрастающая потребность пользователей в вычислительной мощности стимулировала переход в конце 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); А.И. Аветисян, С.С. Гайсарян, Д.А. Грушин, H.H. Кузюрин, A.B. Шокуров, С.Н. Жук, А.И. Поспелов, А.Н. Черных (упаковка прямоугольников- заявок в несколько полос, Multiple Strip Packing Problem). Среди зарубежных ученых следует выделить Baker, В., Coliman, Е., Rivest, R., Garey, М., Johnson, D., Taijan, R., Hofri, M., Sleator, D-, Brown, D., Katseff, H., Drozdowski, M., Lodi, A., Martello, S., Monaci, M., Feitelson, D. и др. (Strip Packing Problem); Schwiegeishohn, U., Yahyapour, R., Bougeret,M., Dutot, P.-F.,. Trystram, D. (Multiple Strip Packing Problem); Hifl, M., Ouaíi, 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 г.г.); на У-УН Международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права» (Москва, МГАПИ 2002 - 2004 г.г.); Международных конференциях «Интеллектуальные системы» (А18'04-А18'10) (Дивноморское, 2004-2010 г.г.); Международных конгрессах «Интеллектуальные системы и информационные технологии» (18ГГ11-18ГГ13) (Дивноморское, 2011-2013 г.г.); Международных научно-технических конференциях «Суперкомпьютерные технологий: разработка, программирование, применение» (СКТ-2010, СКТ-2012) (Геленджик,

g

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе формулируется фундаментальный принцип паритетности ресурсов и предлагается паритетная ресурсная модель неограниченного координатного квадранта (рис.1).

время

Рис. 1. Модель в условиях паритетности ресурсов Определим среду диспетчирования. При представлении заявки пользователя для обслуживания диспетчером Grid- системы введём понятие «ресурсный прямоугольник». Ресурсным прямоугольником назовём фигуру (рис.2), у которой горизонтальное и вертикальное измерения принимаются равными числу единиц ресурса времени и процессоров, требуемому для обработки заявки, соответственно. Символом a{jx)y.b{j\) или [(a(/i))J обозначим j\- ю заявку, требующую a(/i) единиц времени и b(j\) единиц процессоров.

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

Меру ресурсного прямоугольника 0(71)* ¿(Л) определим величиной

вСлКлЫЧ/.)-^)?] 1 , (Ь(й)-а(1\)1

аОМЛ) 24лКлГ' назьшаемои звристическои

мерой, состоящей из площади о^/, )•£>(/,). и показателя асимметрии прямоугольника (¿>(/1)- аО'1))2, учитывающего его форму.

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

1) Операция сложения ресурсных прямоугольников. Введём уровневую функцию У = 6(0) ресурсного прямоугольника [(а(0),б(0))], К = 60) ресурсного прямоугольника [(а(1),б(1))]. Операцию сложения двух ресурсных прямоугольников в среде диспетчирования определим как горизонтальную »суперпозицию с уровневой функцией у(л(о)) = ¿(о), Я40) = ¿0). 40) = 0> Л(1)=я(о). Отметим,

к-1

что линейная полиэдраль заявок пользователей иКа(л)>б(л))] определяется

Л=о

результатом сложения составляющих её ресурсных прямоугольников [(а^),¿(у']))] в среде диспетчирования с уровневой функцией у{л(д)) = Л(0)=0,

Л-1 / л 4-1

Аа)= И «1/1А ^0(7']), к- количество заявок (рис.3).

Л= 0 71=0

12 1

Рис.3. Линейная полиэдраль ресурсных прямоугольников 2) Операция умножения ресурсных прямоугольников. Операцию умножения двух ресурсных прямоугольников в среде диспетчирования определим как такое размещение этих прямоугольников, у которых объемлющий ресурсный прямоугольник имеет минимальную эвристическую меру

. 1

тт-

1-Н

(¿-я)2

21 а-Ь + Л-р а-Ь + Х-р

(рис.4). Объемлющий ресурсный прямоугольник- это

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

Я

О'

/I

Рис.4. Операция умножения двух ресурсных прямоугольников

А Р —> Н

Ъ а

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

¿1 = «(л +0 ~а0\)> д2 =¿(/1+1)-Чл)-

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

При Д1 ■ Д2 > 0 пара ресурсных прямоугольников является сравнимой (рис.5), а при Д] • Д2 < 0 - несравнимой (рис.6).

«ш

¿С/1+1)

аС/1+1)

Рис.5. Сравнимая пара ресурсных

К/1+1)

«(Л+1)

Рис.6. Несравнимая пара ресурсных прямоугольников

прямоугольников

4) Операции динамического интегрирования ресурсных прямоугольников. Интегрирование называем динамическим, т.к. заранее не известно сколько и каких граней будет в суперпозиции. Наилучшее приближение протяженности Ь с

Ь

недостатком Х°СЛ) = посредством горизонтальной суперпозиции граней Л=1

(рис.7) назовём операцией динамического интегрирования

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

о

6(1)

6(2)

ЬОо)

о(1) <2)

«(/о)

I Т

Г.

приближаемая протяженность

Рис.7. Операция динамического интегрирования по горизонтали

и

Наилучшее приближение уровня Н с недостатком ]£&(/;)= Я-О

и

посредством вертикальной суперпозиции граней иСаО'Д^Сл)] (рнс.8) назовём

Л-1

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

приближаемый уровень

>Н

*0о)

Ч/о)

¿(2)

а(1)

6(1)

0 Г,

Рис.8. Операция динамического интегрирования по вертикали Наилучшее приближение рамки протяженности Ь и уровня Н с недостатком

л

посредством продольной суперпозиции граней и^О'^Сл)] (рис.9) с проекциями

Л-1

}'о

2>0;М-о, ¿>0;) — Н — 0 назовём операцией продольного динамического

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

Уг'

приближаемый уровень

Я

ЬС/о)

°0'о)

о

411

6(2)

42)

6(1)

I

т

приближаемая протяженность

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

Упорядочим линейную полиэдрапь У [(а(у,), 6 (_/',))] последовательных

Л=о

ресурсных прямоугольников по убыванию высот граней ¿0,) У. ^ ■ Определим левый отсчёт ресурсного прямоугольника как левую верхнюю вершину (рис.10)

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

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

полиэдра™ + щ = ¿(о) = шах Ь{]1), ¿я(/,) (рис.11).

хорда

Рис.11. Хорда линейной полиэдрали

На основе данного построения выделяются два типа:

1) класс линейных полиэдралей, все левые отсчёты граней которых превышают хорду в общей точке Л(_/,) на горизонтали ¿[/((у,)]^ )},

4У,)=2>0;)>

л=0

2) класс линейных полиэдралей, все левые отсчёты граней которых мажорируются уровнями хорды в общих точках )] < у[л(/,)].

Проиллюстрируем введённые определения двух классов линейных полиэдралей. Рассмотрим пару ресурсных прямоугольников с превалированием левого отсчёта второй грани над хордой ¿(1)> ><(я(0)) (рис.12). Горизонтально последовательную пару ресурсных прямоугольников с убыванием высот в случае превалирования хорды над левым отсчётом второй грани

* -+Ж) = 1.

а(0)+а(1) ¿(0)"

¿>(1)< у(а(О)) (рис.13) относим ко второму типу.

Ь( 0)

6(1) \

6(0)

¿(1)1

Ф) а(1) Ф) а( 1)

Рис.12. Пара прямоугольников первого типа Рис.13. Пара прямоугольников второго типа Уровневой функции упорядоченной линейной полиэдрали

сопоставляем полигон целых вершин (л(/,\Ь[а(/,)]), выпуклый относительно начала координат для первого типа (рис.14) и вогнутый относительно начала- для второго типа (рис. 15).

»» --------—------J ^/ии^^ИШН 1ШЛШ ил

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

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

Приведём базовые примеры массивов заявок кругового типа: натуральных ресурсных квадратов (А-у'.М*-/,), у, =0,1,...Д-1 (равные требования процессорного и временного ресурсов а(у,) = б(у,)) (рис.16), натуральных ресурсных прямоугольников горизонтальной формы [((¿-у,),(¿-у, -1))], у, =0,1,...,£-2 (преимущественные требования временного ресурса а(у'|)>б(у,)) (РисЛ7)> натуральных ресурсных прямоугольников вертикальной формы Мл^-.Л ~Ц~7,))]. У, =0,1,..., к-2 (преимущественные требования процессорного ресурса о(/1)<б(у,)) (рис.18).

Уг\

Рис.16. Круговая полиэдраль ресурсных квадратов

ч

о

о

№

V " г,

Рис.17. Круговая полиэдраль прямоугольников Рис.18. Круговая полиэдраль

горизонтальной формы прямоугольников вертикальной формы

2) Определим гиперболический тип линейных полиэдралей. Дополнительно, полагаем признак попарной последовательной несравнимости ресурсных

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

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

ресурсных прямоугольников + у,)х(ЗАг — у'Д + ^ ^- + 2,..., ^ + к (рис.19),

ресурсных прямоугольников горизонтальной формы {к + у'1)х(ЗА: — уД у, =к, к+\,..., Л + (£-1) (преимущественные требования временного ресурса «(/.)> ¿0'.)) (Рис-20), ресурсных прямоугольников вертикальной формы (Л + у',)х(ЗА-уД у, =1,2,...,Л (преимущественные требования процессорного ресурса а(у1)<А(у1)) (рис.21).

П

Рис.19. Гиперболическая полиэдраль ресурсных прямоугольников

Рис.20. Гиперболическая полиэдраль Рис.21. Гиперболическая полиэдраль

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

Приведём базовый пример массива заявок параболического типа- ресурсные прямоугольники У|х(&-У,), у, = 1,2,...Д-1 (рис.22).

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

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

В литературе рассматривались несколько классических моделей упаковки прямоугольников, в том числе: в объемлющий квадрат минимальной площади Square Packing (SP), в объемлющий прямоугольник минимальной площади Rectangular Packing (RP) или Rectangle Packing Area Minimization Problem (RPAMP). В соответствии с этими моделями и моделью паритетности ресурсов, мы предлагаем и исследуем для заданного множества ресурсных прямоугольников задачу минимизации эвристической меры.

Эвристическую меру ресурсной оболочки определим полусуммой отношений

ресурсной меры L • H и меры асимметрии оболочки (/, - Я)2 к суммарной мере

ы

lLa0i)b(j\) охватываемых планарных элементов. Здесь L - протяжённость по

у,=0

горизонтали, Я - уровень по вертикали ресурсной оболочки (рис.23), процессоры

Я

X время

Рис.23. Ресурсная оболочка перераспределённого массива заявок пользователей Целевая функция задачи минимизации эвристической меры ресурсной

оболочки имеет вид I 2

LH + (L-Hf

14/,X/,)

V >1=0

Ограничения на неналожение ресурсных прямоугольников: у,,+а{{)<ух. или уи+аО)<уу или у2,+Ь^)<у2/ или У2/ + Ь^)<у2„

/е[0Д-1]сг', у е[о,£-1]с2'.

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

Ум + > V/ е [ОД -1] с 21, у21 + ¿(/) < Н к-\]а2\ уи,у21-¿0.

Через уи, у21 - обозначены координаты левой нижней вершины ресурсного прямоугольника [(а(»), £(/))], /е[0, £-!]<= г1. Изложим принцип эвристики, альтернативный принципу оптимизации.

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

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

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

1°. Максимальным ресурсным элементом образуем начальную оболочку (рис.24).

2°. Вдоль линии У1 = а(о) производится операция динамического интегрирования ресурсных прямоугольников у [(й(у,), ¿(у,))] по вертикали,

= ь(о) - О. Здесь - число ресурсных прямоугольников (рис.25).

г, г,

Рис.24. Ресурсная оболочка первого шага Рис.25. Ресурсная оболочка второго шага 3°. На уровне У2 = 6(0) производится операция динамического

интегрирования ресурсных прямоугольников и[(а(/, )> ¿Сл))] по горизонтали,

А Ч. •!

= а(0)+а(1)-0. Здесь число ресурсньрс прямоугольников (рис.26). 4°. Вдоль линии Ух = а(0)+ о(1) производится операция динамического интегрирования ресурсных прямоугольников и [(«(у 1), ¿(у,))] п0 вертикали,

Л =9. +»2+1

¿б(у,)=б(0)+й(91 +1)-0. Здесь - число ресурсных прямоугольников (рис.27). 5°. На уровне У2 =б(0)+б(^, +1) производится операция динамического интегрирования ресурсных прямоугольников У [(<з(У1 Л ¿"О*!))] по горизонтали,

Ха1/1)=а(°)+а(1)+а(?1 +?2 + 1)-0. Здесь <74- число ресурсных прямоугольников.

Рис.26. Ресурсная оболочка третьего Рис.27. Ресурсная оболочка четвертого шага

шага

6°. Алгоритм повторяется до окончания массива (рис.28).

*<7> т Н9)

1- ад А(3) <К2) д(3) Кб) <6)

К5) Ф)

6(0) т Ю)

6(4) <*4)

г,

Рис.28. Конечная ресурсная оболочка

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

19 18 17 16 15 14 13 1 в] Д Т| т]

26 25 24' 20

30 29 27 21 22

31 28

32 23 и I 12

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

Отметим, что время работы оптимального алгоритма1 для соответствующих 32- х квадратов на компьютере 2GHz AMD Opteron 246 превышает 33 дня и 11 часов.

Сравнивается качество приведённого начально- кольцевого алгоритма с оптимальной укладкой в объемлющий прямоугольник минимальной площади. Погрешность не превосходит 31%. Эвристические меры ресурсных оболочек

начально- кольцевого алгоритма не превосходят значения ^ + 0,22.

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

величину Я = ,l£a(j,)b(j,), которую назовём среднересурсной, и примем её за

Ь-о

уровень горизонтальной полосы 0 £Y2<H.

1°. На первом шаге вдоль линии Yt = 0 вертикально суперпозируются

ресурсные прямоугольники Q [(¿¡(у, ),&(/,))] До наилучшего приближения уровня с

А-О

недостатком Я-0 (операция динамического интегрирования ресурсных

прямоугольников по вертикали). Здесь qx- число ресурсных прямоугольников (рис.30).

2°. Вдоль линии Yt = а(0) производится операция динамического

9т

интегрирования ресурсных прямоугольников (J ), b{j\))] по вертикали,

Я - 0. Здесь q2- число ресурсных прямоугольников (рис.31).

Y

¿(1)

"(1)

4(4)

¿(0)

m

m

"(3)

Ы2)

Рис.30. Ресурсная оболочка первого шага Рис.31. Ресурсная оболочка второго шага

3°. Вдоль линии У1 =о(0)+о(^,) производится операция динамического

интегрирования ресурсных прямоугольников иК^О'Д^Сл))] по вертикали,

1\ +?2

'Huang, E., Korf, R. (2012). Optimal rectangle packing: an absolute placement approach. Journal of Artificial Intelligence Research, 46,47-87.

) = Н - 0. Здесь д, - число ресурсных прямоугольников.

г, =?, +};

4 . Алгоритм повторяется до окончания массива (рис.32).

Ъ?

¿(1)

0(1)

6(4)

;«о)

6(9)

а(4)

6(8)

6(3)

Ф)

ЬО)

6(2)

о(0)

й(2)

_аС21

а(8)

о(7)

6(6)

о(6)

6(5)

Ф)

Рис.32. Конечная ресурсная оболочка Отметим, что количество операций работы уровневого алгоритма составляет к операций сложения и к операций сравнения, т.е. алгоритм является полиномиальным. Сравнивается качество приведённого уровневого алгоритма с оптимальной укладкой в объемлющий прямоугольник минимальной площади. Погрешность не превосходит 33%. Эвристические меры ресурсных оболочек

уровневого алгоритма не превосходят значения - + 0,35.

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

среднересурсную величину V = (¿0(7, )&(/,).

1 .На первом шаге максимальный ресурсный элемент [(я(о),б(о))] помещаем в начало координат (рис.33).

У2

т

а(0)

V У,

Рис.33. Центральный угловой элемент первого шага Вдоль линии У2 = 0 справа от этого элемента горизонтально

последовательно суперпозируются ресурсные прямоугольники [(<>(/,) 6 (/,))] до

л->

наилучшего приближения протяжённости с недостатком 0(о)+ ¿а(у,)= К - 0

Л-1

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

горизонтально справа от центрального углового элемента первого шага [(а(о),б(о))] (рис.34). Вдоль линии У, - 0 сверху над этим элементом вертикально последовательно суперпозируются ресурсные прямоугольники '(^[("О.^О,))] до

наилучшего приближения уровня с недостатком 6(0)+ ^'¿(/1) = К-0 (операция

динамического интегрирования ресурсных прямоугольников по вертикали). Здесь д2- число ресурсных прямоугольников, суперпозированных вертикально сверху над центральным угловым элементом первого шага [(а(о),б(о))] (рис.35).

0

У2

У\

¿(4) «(4)

т ф)

6(1) 6(2)

а(2)

К 3) а(3)

6(0) о(0)

6(1) 6(2)

я(1) а(2)

V г,

Рис.34. Приближение протяжённости с недостатком на первом шаге

°

Рис.35. Приближение уровня с недостатком на первом шаге

2. На втором шаге элемент + д2 + 1),б(<7, + <?2 +1))] вершинно-

диагонально синтезируется с центральным угловым элементом предыдущего шага [(а(0),б(0))] (операция продольного динамического интегрирования ресурсных

прямоугольников) (рис.36).

у-

|б(4) <* 4)

6( 3)

6(5) 4Ц

НО)

а(0)

6(1)

0(1)

6(2) а(2)

V У,

Рис.36. Вершинно- диагональный синтез центрального углового элемента второго шага Вдоль линии Уг = 6(0) справа от этого элемента горизонтально последовательно суперпозируются ресурсные прямоугольники "*и'[(о(у ),б(у ))]

до наилучшего приближения протяжённости с недостатком

У — О (операция динамического интегрирования

Л"*+»1+2

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

углового элемента второго шага [(0(9, +q2 +1),%, + q2 +1))]. Вдоль линии У, = а{0) сверху над этим элементом вертикально последовательно суперпозируются

ресурсные прямоугольники U[(a0'i)^0'i))] ДО наилучшего приближения

уровня с недостатком 6(0)+%, +q2 +l)+ = (операция

динамического интегрирования ресурсных прямоугольников по вертикали). Здесь Я а' число ресурсных прямоугольников, суперпозированных вертикально сверху над центральным угловым элементом второго шага [(а(<у, +q2 +1 \b(q,+q2 +l))].

3°. На следующем шаге элемент

[(a(<?i + +1 + 4s+ h + 0>Ь{Я\ + Яг +1 + Ъ + +1))] вершинно- диагонально синтезируется с центральным угловым элементом предыдущего шага + q1+l\b(ql+q1 + ]))] (операция продольного динамического интегрирования ресурсных прямоугольников).

Если a{0)+a{ql + q2 + \)+a(qi+q2+\+ql+qi+\)>V или

+ q2 +\)+b{qx + q2 + \ + qi+qi+\)>V, то укладка углом завершается и переходим к п.4°.

4 . Определяем ресурсную оболочку полученной совокупности ресурсных прямоугольников (рис.37).

Горизонтальное измерение оболочки определяется как ¿ = тах{1,,^,...,Lc), где С-количество центральных угловых элементов- шагов

укладки утлом, Ц =a(o)+f>Q'i)> L2 = a(0)+a(qt + q2 +1)+ •••

Л"1 /i=9I+?J+2

Вертикальное измерение оболочки определяется как Я = шах {Я,, Я2,..., Яс), Я, =6(0)+ §(/,), Н2 = б(0)+б(9, +q2 +l)+ ""'^¿(У,).....

Параметры qt, q2, q„qt определены выше.

5°. Эта ресурсная оболочка принимается за начальную для укладки оставшихся элементов начально- кольцевым алгоритмом.

В итоге получаем конечную ресурсную оболочку углового алгоритма (рис.38). Уг V

6(4) а<4)

О

Л" 13 1,-14

ЬО)

6(7) Ы1)

т

а( 0)

№ о(8)

6(5) о(5)

6(6) а(6)

6(4) о(4)

6(1) о(1)

6(2) "(2)

',-15

j,-t-1 _□

6(3) о(3)

6(7) £21

6(0)

а(0)

V Г,

6(5)

6(8) а{ 8)

М2) о(12

6(6) Мб)

6(1)

а(1)

4(11)

Д(И)

6(2) о(2)

«10) а(10>

6(9) сЦ9}

Рис.37. Ресурсная оболочка в пределах квадрата VxV

Рис.38. Конечная ресурсная оболочка углового алгоритма

Отметим, что количество операций работы углового алгоритма составляет к операций сложения и к операций сравнения, т.е. алгоритм является полиномиальным. Сравнивается качество приведённого углового алгоритма с оптимальной укладкой в объемлющий прямоугольник минимальной площади. Погрешность не превосходит 41,9%. Эвристические меры ресурсных оболочек

углового алгоритма не превосходят значения ~ + 0,22.

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

......Наяально-ыольцевой

--Уровкевый

- — Угловой уровыевый

-Алгоритм послеловагельныхприбзиженнй

---Однородный

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

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

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

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

прямоугольников иЮ'ЛЧл)! b{j,)l, a(j\)t,jl t. Предыдущие построения

л=о

начально- кольцевой локализации переходят в центрально- кольцевую локализацию. При этом, роль максимального, начального ресурсного элемента линейной круговой полиэдрали переходит к центральному элементу [(а(/*), 6(/,'))],

Эвристическая згера

1

1 2 ! 5 6 ^ 8 ■ 9 10 II 12 15 14 13 1« 17 18 ¡9 20 21 22 23 24 25 2« 27 28 25 30 31 32 *

......Нзчально-вшьцевой алгоритм

-^овневый алгоритм *

-^говобурояневый алгоритм

---Алгор1тапослс2оваге.1ь«ыхпрн&шженнй

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

имеющему максимально симметричные измерения |б(/')- а(у')| = пнп|А(/,)- ^(у',)!.

Данный ресурсный элемент делит массив на предшествующие элементы с номерами у, < у", больших высот и меньших оснований и последующие элементы с у, > у, противоположного свойства. Центрально- кольцевой алгоритм имеет полиномиальную трудоёмкость.

Для базового примера массива заявок гиперболического типа ресурсных

прямоугольников (Л + у,)х(ЗА-у1), у, =| + 1, ~ + ~ +к строятся

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

значения — + 0,39. 2

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

ы

ресурсных прямоугольников У [(«(у.)> ¿С/. ))1 ¿0,) аЬ\) Т. У, ^ горизонтальной

Л-0

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

Рис.41. Ресурсный прямоугольник Рис.42. Ресурсный прямоугольник

минимальной асимметрии- начальный минимальной асимметрии- конечный

Предложен и исследован уровневый алгоритм, диспетчирования линейными гиперболическими полиэдралями ресурсных прямоугольников. В частности, для линейной подиэдрали гиперболических ресурсных прямоугольников с центральным элементом минимальной асимметрии (к + у'.)х(3&-у',), к к к

7|= —+1. —+ 2,..., — + £ эвристические меры ресурсных оболочек уровневого алгоритма по высоте не превосходят значения 0,22, а уровневого алгоритма по

протяжённости не превосходят значения ^- + 0,18.

Для линейной гиперболической полиэдрали ресурсных прямоугольников горизонтальной формы с начальным элементом минимальной асимметрии у, =к,к + 1,...,к + (к-1) эвристические меры ресурсных оболочек

уровневого алгоритма по высоте не превосходят значения + 0,25, а уровневого

алгоритма по протяжённости не превосходят значения ^ + 0,23.

Для линейной гиперболической полиэдрали ресурсных прямоугольников вертикальной формы с конечным элементом минимальной асимметрии (к+у',)х (Зк - у,), у, =1,2, ...,к эвристические меры ресурсных оболочек

уровневого алгоритма по высоте не превосходят значения ■^• + 0,23, а уровневого

алгоритма по протяжённости не превосходят значения ^ + 0,25.

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

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

-Угдовойалгорнтм

---Уровневый алгоритм по высоте

---'Уровневый алгоритм по протяженности

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

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

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

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

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

UK4/.M,))]

с низкими гранями, в которых высоты всех граней не выше

А=0

среднересурсной величины Я = jnax^,)^ Я (рис.44).

гг-

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

В частности, для линейной параболической полиэдрали ресурсных прямоугольников у, х(к — у,), у, e[l,i-l]cZ" при к = 24 соответствующие построения алгоритмом со среднересурсным уровнем приведены на рис.45. Здесь в центре прямоугольника указан его номер, соответствующий значению основания. Отметим, что время работы оптимального алгоритма для соответствующих 23- х прямоугольников на компьютере 2.93GHz Intel Core 2 Duo E7500 превышает 3 дня и 22 часа.

— -

15 11 8 Г-] "ji

16 12 A 2

17 6

18 13 9 —

19 |

20 I 14 10 7 i

21 1

Рис.45. Укладка алгоритмом со среднересурсным уровнем Сравнивается качество приведённого алгоритма со среднересурсным уровнем с оптимальной укладкой в объемлющий прямоугольник минимальной

2 Huang, E., Korf, R. (2012). Optimal rectangle packing: an absolute placement approach. Journal of Artificial Intelligence Research, 46,47-87.

площади. Погрешность площади ресурсной оболочки относительно оптимального значения не превосходит 40,3%. Эвристические меры ресурсных оболочек

алгоритма со среднересурсным уровнем не превосходят значения ^+0,34.

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

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

Определяется понятие усечения полного комбинаторного эксперимента как переход от одиночного негативного исхода у, = 0, множества позитивных исходов у", е[1Д] в полном комбинаторном эксперименте, к новому негативному исходу у, =£, прямой части усечения у, е[0,i-1] и инверсной части усечения у, е [/, +в усечении полного комбинаторного эксперимента.

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

Рис.46. Полный комбинаторный эксперимент спроса- предложения Показывается, что усечение эксперимента спроса- предложения

г.-| (т _ -V

определяется формулой включения- исключения Р{к,Ь)= 1У"С^1'--и

¿»о к\

выражает объём усечённого единичного куба, существенно зависящий от обоих параметров модели: канонического параметра «Ь> и величины усечения и дающая вероятность одновременного обслуживания пользователей (рис.47).

ъ

ь

ь

ь

Рис.47. Геометрическое изображение сечения куба плоскостью общего ресурса

предложений и носитель величины Р(к,Ь) Определим равновесие взаимодействующих сред спроса- предложения при множественном компьютерном обслуживании следующим образом: вероятность обслужиться должна быть больше, чем получить отказ. Таким образом, условие

равновесия имеет вид Р{к,Ь)>]-. Показывается, что Р(к,Ь) = Р(к.к-Ь) если

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

Получим условие достоверности компьютерного обслуживания. На первой стадии обслуживания имеется £ < к неполных предложений ресурсов. На второй стадии, соответственно, потребуется (к - Ь) недостающих предложений ресурсов.

Если к — Ь<, Ь —к<,И —»¿е^-,^, те недостающие ресурсы содержатся на

повторной стадии обслуживания. При этом, двухстадийное обслуживание

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

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

В процессе проведенных исследований получены следующие научные результаты-.

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

Ь-\ = к-Ь-\, т.е. при I = —. Получаем, согласование параметров

оказывается достоверным событием

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

5) разработанные и исследованные полиномиальные алгоритмы диспетчирования в GRID-системах: начально-кольцевой, уровневый, угловой и алгоритм последовательных приближений, адаптированные к диспетчированию массивами заявок кругового типа. Статистика сравнения выявила преимущества разработанных полиномиальных алгоритмов при учёте качества заполнения ресурсной оболочки в сопоставлении с затрачиваемым временем оптимальным алгоритмом. Например, для укладки 32 последовательных ресурсных квадратов время работы оптимального алгоритма на компьютере 2GHz AMD Opteron 246 превышает 33 дня и 11 часов (работы Э. Хуанга в исследовательском центре Пало-Альто (Е. Huang, Palo Alto Research Center), Р.Корфа в Калифорнийском университете, Лос-Анджелес (R. Korf, University of California, Los Angeles)), тогда как начально- кольцевой алгоритм практически мгновенно дает решение с погрешностью 17,5%.

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

7) разработанные и исследованные полиномиальные алгоритмы диспетчирования в GRID-системах: со среднересурсным уровнем, начально-уровневый, возвратный и ступенчатый, адаптированные к диспетчированию массивами заявок параболического типа. Например, для укладки 23 ресурсных прямоугольников, с последовательно убывающими высотами и растущими основаниями, время работы оптимального алгоритма на компьютере 2.93GHz Intel Core 2 Duo E7500 превышает 3 дня и 22 часа.(работы Э. Хуанга, Р.Корфа), тогда как алгоритм со среднересурсным уровнем практически мгновенно дает решение с погрешностью 25%.

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

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

Основные публикации по теме диссертации

Приложение к журналу:

1. Саак, А.Э. Полиномиальные алгоритмы распределения ресурсов в Grid-системах на основе квадратичной типизации массивов заявок / А.Э. Саак // Информационные технологии. - 2013. №7. Приложение. - 32с.

Основные статьи в научных журналах рекомендованных ВАК РФ

2. Саак, А.Э. Определение вероятности полной загрузки системы / А.Э. Саак // Известия ТРТУ. - 1998. - № 3(9). - С. 168-170.

3. Саак, А.Э. К проблеме классификации управленческих задач распределительно- комбинаторного типа // Известия ТРТУ 2002 №1(24) с. 195-196.

4. Саак, А.Э. Полновероятностная модель функционирования многопроцессорных систем коллективного пользования / А.Э. Саак // Известия ТРТУ. - 2002. - № 4(27). - С. 128-134.

5. Саак, А.Э. Параметры вычислительного поля системы с множеством пользователей / А.Э. Саак, А.Г. Чефранов // Известия ТРТУ. - 2003 - № 5(34) -С. 219-226.

6. Саак, А.Э. Закон распределения вероятностей числа одновременно обслуживаемых пользователей вычислительной системы / А.Э Саак // Известия ТРТУ. - 2003. - № 5(34). - С. 226-228.

7. Саак, А.Э. К теории неполных комбинаторных сумм / А.Э. Саак // Известия ТРТУ. - 2004. - № 4(39). - С. 246-250.

8. Саак, А.Э. Моментные характеристики стационарной модели многопроцессорной вычислительной системы / А.Э. Саак // Известия ТРТУ -2005. - № 3(47). - С. 144-148.

9. Саак, А.Э. Индексные алгебры и моделирование многопроцессорных систем в потоке пользователей / А.Э. Саак // Известия ТРТУ. - 2005. - № 6(50) - С 150153.

10. Саак, А.Э. Тетродные отображения в моделировании МВС / А.Э. Саак // Известия ТРТУ. - 2006. - № 8(63). - С. 221-226.

11. Саак, А.Э. Система комбинаторных экспериментов в моделировании многопроцессорных систем коллективного пользования / А.Э. Саак И Известия ТРТУ. - 2006. - №10 (65). - С. 38-42.

12. Саак, А.Э. Цепная модель комбинаторных экспериментов стационарного моделирования МВС / А.Э. Саак // Известия ТРТУ. - 2007. - № 2(74). - С. 51-57.

13. Саак, А.Э. Локально-симметричные оптимальные расписания // Известия ТРТУ. - 2008. - № 4(81). - С. 141-145.

14. Саак, А.Э. Об оптимальном синтезе ресурсных прямоугольников / А.Э. Саак // Известия ЮФУ. Технические науки. - 2010. - № 4(105). - С. 223-229.

15. Саак, А.Э. Локально- оптимальный синтез расписаний для Grid- технологий / А.Э. Саак // Информационные технологии. - 2010. - № 12. - С. 16-20.

16. Саак, А.Э. Локально- оптимальные ресурсные распределения / А.Э. Саак // Информационные технологии. - 2011. - № 2. - С. 28-34.

17. Саак, А.Э. Анализ взаимодействия пользователей и обслуживающей компьютерной системы / А.Э. Саак // Известия ЮФУ. Технические науки -2011. - №7(120). - С. 224-229.

18. Саак, А.Э. Алгоритмы диспетчеризации в Grid- системах на основе квадратичной типизации массивов заявок / А.Э. Саак // Информационные технологии.-2011.-№ 11.-С. 9-13.

19. Саак, А.Э. К оценке взаимодействия пользователей и обслуживающей системы / А.Э. Саак // Известия ЮФУ. Технические науки. - 2011. - № 11(124). - С. 197204.

20. Саак, А.Э. Принцип эвристики в многоцелевой оптимизации /' А.Э. Саак // Известия ЮФУ. Технические науки. - 2012. - № 7(132). - С. 206-210.

21. Саак, А.Э. Центрально- кольцевой алгоритм диспетчеризации массивами заявок гиперболического типа / А.Э. Саак // Известия ЮФУ. Технические науки. - 2012. - № 8(133). - С. 214-222.

22. Саак, А.Э. Диспетчеризация в GRID- системах на основе однородной квадратичной типизации массивов заявок пользователей / А.Э. Саак // Информационные технологии. - 2012. - № 4. - С. 32-36.

23. Саак, А.Э. Сравнительный анализ полиномиальных алгоритмов диспетчеризации в GRID- системах / А.Э. Саак // Информационные технологии. - 2012. - № 9. - С. 28-32.

24. Саак, А.Э. Полиномиальные алгоритмы диспетчеризации массивов заявок гиперболического типа / А.Э. Саак // Информационные технологии. - 2013. -№ 3. - С. 33-36.

25. Саак, А.Э. Полиномиальные алгоритмы диспетчеризации массивов заявок параболического типа / А.Э. Саак // Информационные технологии. - 2013. -№ 5. - С. 25-29.

26. Саак, А.Э. Ступенчатый алгоритм диспетчеризации массивами заявок параболического типа / А.Э. Саак // Известия ЮФУ. Технические науки. -2013. -№6(143). -С. 139-145.

Другие статьи и материалы конференций

27. Саак, А.Э. Комбинаторная модель функционирования многопроцессорных вычислительных систем / А.Э. Саак // «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права»: труды V межд. науч.-практ. конф. - Москва: МГАПИ, 2002. - С. 155-159.

28. Саак, А.Э. Представление функционирования многопроцессорных систем комбинаторным экспериментом / А.Э. Саак // «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права»: труды VI межд. науч.-практ. конф. - Москва: МГАПИ, 2003. - С. 213-217.

29. Саак, А.Э. Анализ функционирования многопроцессорных систем коллективного пользования / А.Э. Саак // Программные системы и инструменты: Тематический сборник №4 фак-та ВМиК МГУ им. Ломоносова. Москва: МГУ, 2003. - С. 70-78.

30. Саак, А.Э. Кубическая и котетраэдная модели многопроцессорной вычислительной системы в потоке пользователей / А.Э. Саак // «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права»: труды VII межд. науч.-практ. конф. - Москва: МГАПИ, 2004. - С. 190-195.

31. Саак, А.Э. К вычислению пропускной способности многопроцессорных систем / А.Э. Саак // «Интеллектуальные системы» (IEEE AIS'04) и

«Интеллектуальные САПР» (CAD-2004): в 3 т. - TI.: труды межд. науч.-техн. конф. - М.: Физматлит, 2004. - С. 405-409.

32. Саак, А.Э. Комбинаторный эксперимент как модель многопроцессорных вычислительных систем коллективного пользования / А.Э. Саак // «Параллельные вычисления и задачи управления» (PACÓ'2004): труды II межд. конф. - М.: ИПУ РАН, 2004. - С. 871-883.

33. Саак, АЗ. Алгебро- метрологические свойства комбинаторных моделей МВС / А.Э. Саак // «Параллельные вычисления и задачи управления» (РАСО'2006): труды III межд. конф. - М.: ИПУ РАН, 2006. - С. 1452-1457.

34. Саак, А.Э. О моделировании МВС на основе комбинаторного эксперимента / А.Э. Саак // «Искусственный интеллект. Интеллектуальные системы» (ИИ-2008): в 2 т. - Т.2.: мат-лы IX межд. науч.-техн. коиф. - Донецк: ИЛИИ «Наука i осв1та», 2008. - С. 371-373.

35. Саак, А.Э. Канонические модели многопроцессорных вычислительных систем / А.Э. Саак // «Параллельные вычисления и задачи управления» (РАСО'2008): труды IV межд. конф. - М.: ИПУ РАН, 2008. - С. 1356-1384.

36. Саак, А.Э. Моделирование цепью комбинаторных экспериментов взаимодействия двух сред: поставляющей и потребляющей компьютерные услуги / А.Э. Саак // «Многопроцессорные вычислительные и управляющие системы» (МВУС-2009): в 2 т. - Т.2.: мат-лы межд. науч.-техн. конф. -Таганрог: Изд-во ТТИ ЮФУ, 2009. - С. 82-84.

37. Саак, А.Э. Некоторые числовые характеристики диспетчирования многопроцессорных вычислительных систем / А.Э. Саак // «Параллельные вычисления и задачи управления» (РАСО'2010): труды V межд. конф -М.: ИПУ РАН, 2010. - С. 1375-1382.

38. Саак, А.Э. Некоторые задачи диспетчирования МВС / А.Э. Саак // «Конгресс по интеллектуальным системам и информационным технологиям» (AIS-IT'10): в 4 т. - Т.2.: труды конгресса. - М.: Физматлит, 2010. - С. 232-236.

39. Саак, А.Э. Об оптимальном синтезе ресурсных прямоугольников в диспетчировании МВС / А.Э. Саак // «Суперкомпьютерные технологии: разработка, программирование, применение» (СКТ-2010): в 2 т. - Т.2.: мат-лы межд. науч.-техн. конф. - Таганрог: Изд-во ТТИ ЮФУ, 2010. - С. 87-91.

40. Саак, А.Э. О квадратичной факторизации массива заявок пользователей / А.Э. Саак // «Конгресс по интеллектуальным системам и информационным технологиям» (IS&1T'12): в 4 т. - Т.2.: труды конгресса. - М.: Физматлит, 2012 -С. 237-241.

41. Саак, А.Э. Полиномиальная диспетчеризация круговым типом массива заявок пользователей / А.Э. Саак // «Суперкомпьютерные технологии» (СКТ-2012): мат-лы 2-й Всеросс. науч.-техн. конф. - Ростов-на-Дону: Изд-во ЮФУ. 2012 -С. 169-173.

42. Саак, А.Э. Полиномиальные алгоритмы диспетчеризации на основе квадратичной типизации массивов заявок пользователей / А.Э. Саак // «Параллельные вычисления и задачи управления» (РАСО'2012): труды VI межд. конф. - М.: ИПУ РАН, 2012. - С. 341-347.

43. Саак, А.Э. Алгоритм последовательных приближений диспетчеризации массивами заявок кругового типа / А.Э. Саак // 6-я Всеросс. мультиконф. по проблемам управления (МКПУ-2013): в 4 т. -Т.4.: мэт-лы 6-й Всеросс. мультиконф. - Ростов-на-Дону: Изд-во ЮФУ, 2013. - С. 71-75.

Личный вклад автора в опубликованных совместных работах: в работе [5] разработка модели вычислительного поля системы с множеством пользователей.

Соискатель Л7/& А.Э. Саак

Формат 60x84 1/16. Бумага офсетная. Подписано к печати 27.12.2013г. П.л.-2,0. Тираж 100 экз. Заказ № 415 Типография ЮФУ 347928, г. Таганрог, пер. Некрасовский, 44.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

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

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

Специальность: 05.13.01- Системный анализ, управление и обработка информации (вычислительная техника и информатика)

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

Научный консультант: заслуженный деятель науки РФ,

доктор технических наук, профессор Виктор Михайлович Курейчик

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

Таганрог, 2013 г.

Оглавление

Введение ........................................................................................................................3

Глава 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

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

Приложения..................................................................................................................287

Введение

Актуальность работы. Всё возрастающая потребность пользователей в вычислительной мощности стимулировала переход в конце 90- х годов от многопроцессорных систем, кластерных систем, метакомпьютинга к Grid-компыотингу (Grid computing), который развивается и в настоящее время, наряду с другими парадигмами распределённых вычислений, такими как облачные вычисления (cloud computing) и вычислительные джунгли (jungle computing). Эффективность функционирования таких систем во многом определяется распределением вычислительных ресурсов, управлением задачами в условиях множественности. При этом диспетчирование заявками пользователей, требующих каждая для своего обслуживания несколько процессоров одновременно, выходит за рамки классической теории расписаний. Принцип оптимизации, как машинный поиск наилучшего распределения, выявил трудоёмкость по времени, делающей невозможным использование этих методов при управлении ресурсами Grid. Существующая классификация систем диспетчирования задач (Job scheduling) и управления ресурсами Grid (Grid resource management systems) выделяет три базовые архитектуры: централизованная (centralized), иерархическая (hierarchical) и распределённая (decentralized, distributed), различающиеся способом принятия решения об управлении ресурсами и задачами. Так, в централизованной структуре диспетчерское решение осуществляется центральным диспетчером, обладающим всей полнотой информации о вычислительных ресурсах и задачах. В Grid-системах различают два вида диспетчирования по способу объединения вычислительных ресурсов для решения задачи: одно- сайтное диспетчирование (single- site scheduling) и мульти- сайтное диспетчирование (multi- site scheduling). При одно- сайтном диспетчировании задача выполняется в пределах сайта, не выходя за границы параллельной системы. Тогда как при мульти- сайтном

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

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

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

Исследования в области диспетчирования заявок пользователей и распределения вычислительно- временных ресурсов, как упаковки прямоугольников, были начаты с 80-х годов прошлого столетия. Среди отечественных авторов можно отметить следующие работы А.Б. Барский,

B.Ю. Бакенрот, A.B. Каляев, О.Б. Макаревич, А.Г. Чефранов и др. (упаковка прямоугольников- заявок в одну полосу, Strip Packing Problem); А.И. Аветисян,

C.С. Гайсарян, Д.А. Грушин, H.H. Кузюрин, A.B. Шокуров, С.Н. Жук, А.И. Поспелов, А.Н. Черных (упаковка прямоугольников- заявок в несколько полос, Multiple Strip Packing Problem). Среди зарубежных ученых следует выделить Baker, В., Coffman, Е., 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); Schwiegeishohn, 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) Комбинаторные модели взаимодействующих сред спроса- предложения в виде многомерных многогранных тел для согласования параметров на этапе предпроектных исследований; понятие усечения