Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

• Введение
• 1. Описание предметной области
• 1.1 Понятие о вычислительных системах
• 1.2 Распределенная вычислительная система
• 1.3 Режимы работы
• 1.4 Описание масштабируемой задачи
• 2. Теория расписаний
• 2.1 Теория расписаний
• 2.2 Целевые функции в задачах ТР
• 2.3 Дискретное программирование
• 2.4 Методы решения задач дискретной оптимизации
• 2.5 Эвристические алгоритмы
• 2.6 Метод динамического программирования
• 2.7 Метаэвристические методы
• 2.8 Классификация алгоритмов решения
• 3. Алгоритм имитация отжига
• 4. математическая постановка задачи
• 5. Реализация алгоритма имитация отжига
• 5.1 Заполнение начального словаря
• 5.2 Основные функции
• 6. Моделирование
• результаты
• Заключение


Введение

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

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

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

1. Описание предметной области

1.1 Понятие о вычислительных системах

Два направления развития вычислительной техники:

1. Электронные вычислительные машины (ЭВМ) и простейшие вычислительные системы.

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

2. Вычислительные системы.

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

ВС базируется на трех принципах:

массовый параллелизм;

программируемость структуры;

конструктивная однородность;

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

Рисунок 1. Виды вычислительных систем.

1.2 Распределенная вычислительная система

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

Распределенная ВС объединение пространственно удаленных друг от друга сосредоточенных ВС, основанное на принципах:

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

* программируемости структуры (т. e. возможности автоматически настраивать сеть связи между сосредоточенными ВС);

* гомогенности состава (т. e. программной совместимости различных сосредоточенных ВС и однотипности элементарных машин в каждой из них)[1].

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

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

Более развитым вариантом распределенных ВС являются системы, структура сети связи которых в целом являются нерегулярной и которые компонyются из программно-совместимых ЭМ. B данном случае сеть связи организуется посредством программно-совместимых системных устройств. B топологическом плане такие ВС классифицируются как централизованные, децентрализованные, кольцевые и радиально-кольцевые системы.

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

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

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

1.3 Режимы работы

B зависимости от сложности задач и характера их поступления можно выделить следующие основные режимы работы ВС c программируемой структурой:

* решение одной сложной задачи;

* обработка набора задач;

* обслуживание потока задач.

Первый режим монопрограммный, т. e. для решения задачи используются все ресурсы ВС. Задача представляется в виде параллельной программы, число ветвей в которой либо фиксировано, либо допускает варьирование в заданном диапазоне. B качестве единицы ресурса выступает элементарная машина ВС. Все машины используются для решения задачи. Если максимальное количество ветвей в параллельной программе менее общего количества ЭМ в системе, то избыточные машины используются для повышения надежности функционирования ВС.

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

При организации функционирования ВС в случае набора задач учитывается не только количество задач, но их параметры: число ветвей в программе (точнее, число машин, на которых она будет выполняться), время решения или вероятностный закон распределения времени решения и др. Алгоритмы организации функционирования ВС задают распределение задач по машинам и последовательность выполнения задач на каждой машине. B результате становится известным, в какой промежуток времени и на каких машинах (или на какой подсистеме) будет решаться любая задача набора. Этот режим, безусловно, является обобщением мультипрограммных режимов для ЭВМ, и он более сложный. B самом деле, при мультипрограммировании ресурсы ЭВМ (прежде всего процессор) делятся между несколькими последовательными программами. При обработке наборов параллельных задач ресурсы ВС (множество элементарных машин) также распределяются между задачами, однако в любой момент времени задачи решаются на непересекающихся подмножествах машин. Следовательно, мультипрограммные режимы работы ЭВМ реализуются путем разделения времени процессора, в то время как обработка наборов задач на ВС осуществляется посредством разделения «пространства» машин.

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

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

1.4 Описание масштабируемой задачи

Под задачей будем понимать требование выполнить параллельную программу на ресурсах ВС. Исследования показывают, что 98 % вычислительных задач обладают возможностью адаптироваться под доступные конфигурации ресурсов ВС перед началом решения [4]. Такие задачи называют масштабируемыми (moldable)[5]. Пример задачи, которая используется в рамках данной работы, показан на рисунке 2.

Рисунок 2. Масштабируемая задача.

Пользователь направляет задачу в очередь СУР в виде паспорта (скрипта) для оболочки (shell), содержащего требования к ресурсам, атрибуты задания и набор команд, которые необходимо выполнить.

Для представления допустимых вариантов конфигураций ресурсов в паспорте масштабируемой задачи необходимо использовать атрибут «-L» с аргументом, содержащим список запросов, перечисленных через «,». Каждый запрос request_i - один из вариантов конфигурации ресурсов для решения масштабируемой задачи, для описания которого предусмотрены следующие параметры:

nodes = value@ppn = value@weight = = value@walltime = value,

где nodes - число узлов или ЭМ (обязательный параметр);

ppn - число процессорных ядер на каждом узле;

weight - приоритет данного запроса относительно других запросов (натуральное число);

walltime - максимальное время использования ресурсов запроса в формате часы:минуты:секунды.

Параметры ppn, weight и walltime - не обязательны.



2. Теория расписаний

2.1 Теория расписаний

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

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

Другой тип задач заключается в поиске допустимого расписания, удовлетворяющего всем условиям.

Решение задач теории расписаний усложняется тем фактом, что большинство из них являются NP-трудными, т.е. алгоритмы их решения, реализованные на ЭВМ, могут требовать неприемлемо большое время работы для решения практических задач «большой размерности».

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

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

2.2 Целевые функции в задачах ТР

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

2.3 Дискретное программирование

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

Под задачей дискретного программирования (дискретной оптимизации) понимается задача математического программирования, в которой обычно необходимо минимизировать (или максимизировать) значение некоторой функции f(x) на множестве допустимых решений G.

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

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

2.4 Методы решения задач дискретной оптимизации

Метод решения задач дискретной оптимизации - это общая идея, применимая к широкому классу задач. Алгоритм решения - это реализация метода решения для конкретной задачи.

Различают следующие методы решения:

* Эвристические алгоритмы (в т.ч. вероятностные алгоритмы и локальный поиск);

* Метод динамического программирования;

* Метод Ветвей и Границ;

* Метаэвристические методы;

* Графический метод и т.д.

2.5 Эвристические алгоритмы

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

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

2.6 Метод динамического программирования

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

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

2.7 Метаэвристические методы

В 70-90-е годы прошлого века в результате совершенствования эвристических алгоритмов появились т.н. метаэвристические методы, например,

Генетические алгоритмы(Genetic algorithms), метод имитации отжига(Simulated annealing), метод муравьиных колоний(Ant Colony Optimization) и др. Идеи этих методов были «заимствованы» из разных областей науки. Например, идея Генетического алгоритма из генетики, идея метода муравьиных колоний из биологии и т.д.

Метод муравьиные колонии основан на следующем наблюдении из жизни муравейника. Муравьи пытаются отыскать пищу поближе к муравейнику. О том, где находится ближайшая пища, они сообщают друг другу следующим образом. При своем передвижении муравьи оставляют на поверхности «феромонные следы», «запах» которых могут чувствовать другие муравьи. Очередной муравей при поиске пищи ориентируется на феромонный след других муравьев и старается с небольшими отклонениями следовать в том направлении, куда ведет большинство следов. Небольшие отклонения от общего направления позволяют строить новые маршруты и находить новую пищу, а накопление феромона позволяет двигаться в разумном (локально оптимальном) направлении.

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

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

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

* В результате их работы последовательно строятся несколько решений;

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

2.8 Классификация алгоритмов решения

Далее приводятся некоторые классификации алгоритмов решения задач дискретной оптимизации:

По трудоёмкости:

* Полиномиальные алгоритмы;

* Псевдо-полиномиальные алгоритмы;

* Экспоненциальные алгоритмы.

По точности:

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

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

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

* Приближенные алгоритмы, с регулируемой точностью. Время работы таких алгоритмов зависит от выбранной пользователем необходимой точности. Например, нас может, устроит отклонение от оптимума не больше чем на 1%.



3. Алгоритм имитация отжига

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

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

Теперь выделим основные черты отжига, которые необходимо смоделировать при поиске решения:

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

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

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

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

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

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



4. математическая постановка задачи

Имеются РВС, состоящая из N элементарных машин, и набор J из L масштабируемых задач. Каждая задача j ?{1, 2,..., L} описывается вектором параметров = (,, ,…,).

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

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

Требуется построить расписание выполнения программ на вычислительной системе:

(1)

такое, что:

(2)

при ограничениях:

, (3)

, (4)

, , (5)

(6)

(7)

(8)

(9)

где - номер элемента вектора (варианта значений параметров ), выбранного для выполнения -й программы, - время начала выполнения -ой программы, - множество номеров элементарных машин, выделенных для выполнения -ой программы, - множество программ, выполняющихся в момент времени , - допустимая средняя степень «удовлетворенности» пользователей, - время выполнения всех программ набора. Ограничение (5) определяет, что каждой программе с учетом должно быть выделено столько элементарных машин, сколько требуется для её выполнения. При этом ограничения (6) и (7) соответственно требуют, чтобы ветви параллельной программы назначались на разные элементарные машины, и в каждый момент времени элементарная машина была назначена на выполнение одной ветви только одной параллельной программы. Ограничение (8) задает максимально возможное количество ветвей параллельных программ, выполняемых в каждый момент времени.



5. Реализация алгоритма имитация отжига

5.1 Заполнение начального словаря

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

Рисунок 3. Схема алгоритма.

На первом этапе происходит считывание входного файла набора задач, представленного в виде XML файла. Считываются необходимые параметры по тегам, таким как:

ARRIVALTIME - номер прибытия задачи в набор

COUNTREQUESTS - количество конфигураций у задачи

NODES - количество запрашиваемых узлов в конфигурации

TIME - время выполнения задачи

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

На втором этапе задается начальная температура T и минимальная температура T_min. Эти параметры отвечают за количество итераций, которое совершит алгоритм. В качестве формулы понижения температуры используется распределение Коши:

T = (10)

Где:

T_0 - начально заданная температура count_t - счетчик итераций алгоритма

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

На третьем этапе, после выставления параметров температуры программа проверяет условие выхода T <= T_min. Т.е. выясняем, достигла ли программа минимума температуры. Это самый крупный этап, так как если условие останова не выполнено, то переходим к основным функциям программы.

5.2 Основные функции

Первоначально, строиться рабочий словарь work_dict на основе dict_jobs. Отличительная особенность нового словаря заключается в том, что в качестве значения, будет использоваться не список конфигураций, а одна выбранная случайным образом конфигурация. А так же при составлении словаря учитываются данные из списка list_pass, в нем хранятся индексы задач, которые не должны быть включены в рабочий словарь, более подробно об этом будет описано дальше.

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

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

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

container_index - индекс контейнера

V_container - площадь контейнера

V_left - оставшееся место в контейнере

computer_count - количество узлов в РВС

time_max - ограничение по времени в контейнере

container_data - расписание составленное из задач поместившихся в контейнер

Параметры контейнера выставляются при его генерации, за основу берется задача, которая либо не поместилась в уже существующие контейнеры, либо она первая из набора. Начальная задача, определяет основные параметры контейнера, такие как его площадь V_container и границу по времени time_max, так же изменяет параметр оставшегося места в контейнере V_left и записывается в container_data. Последующие задачи меняют исключительно параметр V_left и container_data.

Заполнение контейнера происходит следующим образом. Поступившая задача, проходится по полю container_data и считывая данные из него. Начинается проверка ряда условий:

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

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

После упаковки всех задач по контейнерам, сгенерированное расписание отправляется на вход функции энергии, задача которой рассчитать значение целевой функции, а так же определить наполненность каждого контейнера. Оба эти действия выполняются путем считывания данных с контейнера. Значение целевой функции записывается в переменную cel_t, а контейнеры показатель наполненности которых превышает 99% записываются в список best_cont, задачи из контейнеров, помещенных в этот цикл, попадают в list_pass. Тем самым следующее расписание будет составляться без этих задач. В список t_cont помещается текущая версия расписания.

Следующим шагом является сравнение сгенерированного расписания с предыдущим. Критерием отбора, является значение целевой функции. Если cel_t <= best_cel, то сгенерированное расписание лучше прошлого. В этом случае значению переменной best_cel присваивается значение cel_t, а так же в список лучшего расписания, помещается значения из t_cont. Так же существует вероятность принятия более плохого расписания в качестве лучшего, тем самым избегая ловушки локального минимума.

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



6. Моделирование

Для демонстрации работы алгоритма, необходимо сгенерировать набор задач. Программа generate, написанная на языке Cи, генерирует набор задач исходя из моделей рабочей загрузки [6]. Входные параметры программы:

-s - количество элементарных машин в системе, для которой генерируется набор;

-j - количество задач в наборе;

-r - процент масштабируемых задач в наборе.

-o - имя файла, в который нужно записать набор.

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

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



результаты

Гистограмма показывает зависимость времени решения набора задач, от количества задач в наборе. Проводится сравнение алгоритма BFDH с алгоритмом Имитация отжига. Результаты представлены на рисунке 4.

Рисунок 4. Зависимость времени решения набора от количества задач.

Из гистограммы видно, что алгоритм Имитация отжига уменьшает время решения наборов задач, в среднем на 20%.

В таблице 1 отражено время работы алгоритмов BFDH и Имитации отжига в зависимости от количества задач в наборе.

Таблица 1. Демонстрация времени работы программ.

Количество задач	400	800	1100	1600	2000	2600	3200
BFDH	0,749	3,775	10,422	19,481	32,994	70,634	120,907
Имитация отжига	2,493	7,501	21,769	45,573	67,877	99,432	139,654



По результатам таблицы можно сделать вывод, что алгоритм имитации отжига работает в среднем в два раза дольше, чем BFDH, при запуске на одинаковых наборах задач.

Зависимость времени решения набора задач от процента масштабируемых задач, продемонстрирована на рисунке 5.

Рисунок 5. Зависимость времени решения набора задач от процента масштабируемых задач.

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

На рисунке 6 показано сравнение работы алгоритма Имитация отжига на разных конфигурациях РВС.

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



Рисунок 6. Зависимость времени решения набора задач от количества задач в наборе, на различных конфигурациях РВС.



Заключение

Был реализован алгоритм имитация отжига для планирования решения наборов масштабируемых задач на распределенных вычислительных системах. Каждый из наборов представлен различными характеристиками, такими как процент масштабируемых задач, количества задач в наборе, и на каком количестве ЭМ будет работать набор. Был проведен сравнительный анализ работы алгоритма имитация отжига со стандартным алгоритмом планирования BFDH. В результате было установлено, что реализованный алгоритм формирует расписание решения набора масштабируемых задач в среднем на 22% эффективнее, чем стандартный алгоритм упаковки BFDH.



Библиография

1. Хорошевский В. Г. Распределённые вычислительные системы с программируемой структурой Вестник СибГУТИ. 2010. №2. С. 3-41.

2. Лопатин А. С. Метод отжига // Стохастическая оптимизация в информатике. СПб. : Изд-во СПбГУ, 2005. Вып. 1. С. 133-149.

3. Перышкова Е. Н., Ефимов А. В., Мамойленко С. Н. Инструментарий решения масштабируемых задач на распределённых вычислительных системах // Вестник СибГУТИ. 2015. №4. С. 82-89.

4. Lifka D. The ANL/IBM SP scheduling system // Job Scheduling

Strategies for Parallel Proc. LNCS. Springer-Verlag, 1995. Vol. 949. P. 295-303.

5. Feitelson, D. G. Toward convergence in job schedulers for parallel supercomputers / D. G. Feitelson, L. Rudolph // Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science. - 1996. - Vol. 1162. - P. 1 - 26.

6. Cirne W., Berman F. A model for moldable supercomputer jobs. 15th Intl. Parallel & Distributed Processing Symp. 2001.

Приложение А

Листинг

#!/usr/bin/python

# -*- coding: utf-8 -*-

import xml.etree.ElementTree as etree

import random

tree = etree.parse('9x800x50.jobs')

root = tree.getroot()

all_links = tree.findall('.//REQUEST')

max_computer = 20

def generate_list_config(variable_arrival_time):

list_nodes_time = []

start_count = 0

count_end = 0

for options_task in root:

list_config = []

count_end += int(options_task.attrib['COUNTREQUESTS'])

if int(options_task.attrib['ARRIVALTIME']) == variable_arrival_time:

for i in range(start_count, count_end):

list_nodes_time.append(all_links[i].attrib['NODES'])

list_nodes_time.append(all_links[i].attrib['TIME'])

list_config.append(list_nodes_time)

list_nodes_time = []

return list_config

start_count = count_end

def generate_work_dict(input_dict, list_pass):

variable_options = []

output_config = []

number_task = []

for i in input_dict:

if (i in list_pass) == 0:

number_task.append(i)

variable_options = input_dict[i]

choise = random.randint(1, len(variable_options))

output_config.append(variable_options[choise - 1])

return number_task, output_config

def container_data(Task, index, bias, start):

test_list = []

for i in range(1 + bias, (int(Task[0]) + 1) + bias):

test_list.append(i)

param_task = [index, start, int(Task[1]) + start, test_list]

return param_task

def parameter_container(Task, index):

list_data = []

param_task = container_data(Task, index, 0, 0)

list_data.append(param_task)

container = {

'container_index' : index,

'V_container' : max_computer * int(Task[1]),

'V_left' : max_computer * int(Task[1]) - int(Task[0]) * int(Task[1]),

'computer_count' : max_computer,

'time_max' : int(Task[1]),

'container_data' : list_data

}

return container

def add_new_container(index, work, list_container, max_v_left_in_container):

container = parameter_container(work, index)

list_container.append(container)

if container['V_left'] >= max_v_left_in_container:

max_v_left_in_container = container['V_left']

return container, list_container, max_v_left_in_container

def record_func(container_add, Task_add, index, start, bias):

test_list = container_data(Task_add, index, bias, start)

list_cont = container_add['container_data']

list_cont.append(test_list)

container_add['container_data'] = list_cont

container_add['V_left'] = container_add['V_left'] - int(Task_add[0]) * int(Task_add[1])

return container_add

def add_data_container(container_add, Task_add, index):

for i in range(len(container_add['container_data'])):

work_list = container_add['container_data'][i]

if int(Task_add[1]) >= int(container_add['time_max'] - work_list[2]) and i == len(container_add['container_data']) - 1:

bias = work_list[3][len(work_list[3]) - 1]

if bias + int(Task_add[0]) <= container_add['computer_count'] and container_add['time_max'] >= int(Task_add[1]):

start = 0

container_add = record_func(container_add, Task_add, index, start, bias)

else:

return "ERROR"

if work_list[1] == 0:

max_nod = len(work_list[3])

if int(container_add['time_max'] - work_list[2]) >= int(Task_add[1]) and i == len(container_add['container_data']) - 1:

if container_add['V_left'] - int(Task_add[0]) * int(Task_add[1]) >= 0 and int(Task_add[0]) <= max_nod and container_add['time_max'] >= int(Task_add[1]):

bias = work_list[3][0] - 1

if bias + int(Task_add[0]) <= container_add['computer_count']:

start = int(work_list[2])

container_add = record_func(container_add, Task_add, index, start, bias)

else:

return "ERROR"

else:

bias = work_list[3][len(work_list[3]) - 1]

if bias + int(Task_add[0]) <= container_add['computer_count'] and container_add['time_max'] >= int(Task_add[1]):

start = 0

container_add = record_func(container_add, Task_add, index, start, bias)

else:

return "ERROR"

return container_add

def Best_Fit_Decreasing_High():

container_count = 0; list_container = []; list_min_left = []; list_time_cont = []

for i in work_dict:

if container_count == 0:

container_count += 1

container = parameter_container(work_dict[i], i)

list_container.append(container)

max_v_left_in_container = container['V_left']

one_task = work_dict[i]

add_task = work_dict[i]

count_p = 0

for contain in list_container:

list_min_left.append(contain['V_left'] - int(add_task[0]) * int(add_task[1]))

count_zero = 0

list_min = []

for left in list_min_left:

if left <= 0:

count_zero += 1

else:

list_min.append(left)

if count_zero == len(list_min_left) and work_dict[i] != one_task:

container_count += 1

container, list_container, max_v_left_in_container = add_new_container(i, work_dict[i], list_container, max_v_left_in_container)

break

list_min.sort()

count_error = 0

for contain in list_container:

for min_c in list_min:

if contain['V_left'] - int(add_task[0]) * int(add_task[1]) == min_c and work_dict[i] != one_task:

container = add_data_container(contain, add_task, i)

if container == "ERROR":

count_error += 1

break

else:

list_min = []

break

break

if count_error == len(list_min) and count_error != 0 and work_dict[i] != one_task:

container_count += 1

container, list_container, max_v_left_in_container = add_new_container(i, work_dict[i], list_container, max_v_left_in_container)

count_error = 0

continue

list_min_left = []

return list_container

dict_jobs = {}; work_dict = {}; list_pass = []; best_s = []; best_cont = []; left_cont = []; t_cont = []

dict_jobs = { arrival_time : generate_list_config(arrival_time) for arrival_time in range(1, len(root) + 1) }

T = 300; T_min = 2; count_t = 0; best_cel = 0

T_0 = T

while T >= T_min:

number_task, output_config = generate_work_dict(dict_jobs, list_pass)

work_dict = { number_task[i] : output_config[i] for i in range(len(output_config)) }

list_container = Best_Fit_Decreasing_High()

proc = 0; rez = 0; count = 0; rez1 = 0; data_len1 = 0; count_con = []

for cont in list_container:

proc = int(cont['V_left']) / (int(cont['V_container']) / 100.0)

data_len1 += len(cont['container_data'])

if proc <= 1:

rez += len(cont['container_data'])

for best_container_data in cont['container_data']:

list_pass.append(best_container_data[0])

count += 1

best_cont.append(cont)

else:

count_con.append(proc)

rez1 += len(cont['container_data'])

left_cont.append(cont)

t_cont.extend(best_cont)

t_cont.extend(left_cont)

cel_t = 0

P = random.randint(1, 200)

for c_f in t_cont:

cel_t += c_f['time_max']

if best_cel == 0:

best_cel = cel_t

print 'start_s', cel_t

print '===================================='

if cel_t <= best_cel:

best_cel = cel_t

best_s = []

best_s.extend(best_cont)

best_s.extend(left_cont)

print '--------------------->', count, rez, len(best_s), rez1, data_len1, cel_t

elif P == 47:

T += 50

best_cel = cel_t

best_s = []

best_s.extend(best_cont)

best_s.extend(left_cont)

print 'Bad------------------>', count, rez, len(best_s), rez1, data_len1, cel_t

T = T_0 / (1 + count_t)

count_t += 1

best_cont1 = []

left_cont = []

cel = 0; count = 0; proc = 0

print '===================================='

for i in best_s:

cel += i['time_max']

proc = int(i['V_left']) / (int(i['V_container']) / 100.0)

if proc <= 1:

count += 1

print 'best_s', cel

Размещено на Allbest.ru

...