«СИНТЕЗ АРХИТЕКТУР ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ С УЧЕТОМ ОГРАНИЧЕНИЙ НА ВРЕМЯ ВЫПОЛНЕНИЯ И ТРЕБОВАНИЙ К НАДЕЖНОСТИ ...»

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

имени М.В. Ломоносова

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

ЗОРИН Даниил Александрович

СИНТЕЗ АРХИТЕКТУР ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

РЕАЛЬНОГО ВРЕМЕНИ С УЧЕТОМ ОГРАНИЧЕНИЙ НА ВРЕМЯ

ВЫПОЛНЕНИЯ И ТРЕБОВАНИЙ К НАДЕЖНОСТИ

05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук

Научный руководитель:

кандидат технических наук, В.А. Костенко МОСКВА – Оглавление Введение

Постановка задачи

Содержательное описание задачи

1. Модель входных данных

1. Механизмы обеспечения надежности

1. Модель расписания

1. Вычисление времени выполнения расписания

1. Вычисление надежности

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

1. Выводы

1. Обзор возможных подходов к построению алгоритмов решения задачи и алгоритмов решения близких задач

Цель обзора

2. Полный перебор

2. Метод ветвей и границ

2. Жадные алгоритмы

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

2. Генетические алгоритмы

2. Выводы

2. Алгоритм построения расписания

Общая схема алгоритма

3. Операции преобразования расписания

3. Стратегии применения операций.

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

Исследование свойств алгоритма

Асимптотическая сходимость алгоритма

Метрика в пространстве расписаний

Метрика L(A, B)

Метрика H(A, B)

Связь между метриками L(A, B) и H(A, B)

Оценка для L(A, B)

Экспериментальное исследование алгоритма

Оценка точности на модельных данных

Оценка точности на совместимых исходных данных.......... Сравнение законов понижения температуры

Выводы

Инструментальная система

Требования к системе

Описание системы

Описание архитектуры системы

Графический пользовательский интерфейс

Подсистема для построения вычислительных систем для обработки данных от фазированных антенных решеток

Выводы

Заключение

Литература

Приложение А. Способы оценки надежности

А.1 Надежность процессоров. Резервирование

А.2 Надежность программ. N-версионное программирование........ Приложение Б. Модели среды передачи данных

Б.1 Вычисление времени для системы без конфликтов на портах.. Б.2 Вычисление времени для системы с общей шиной или коммутатором

Приложение В. Вычисление времени выполнения с помощью имитационного моделирования

Приложение Г. Описание задачи обработки данных от фазированных антенных решеток

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

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

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

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

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

Наличие одновременно двух ограничений (время выполнения программы и надежность вычислительной системы);

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

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

Для достижения поставленной цели необходимо решить следующие задачи:

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

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

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

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

Работа состоит из введения, пяти глав, заключения и четырех приложений.

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

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

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

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

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

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

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

В Приложении А описаны различные схемы оценки надежности вычислительных систем.

В Приложении Б приведено детальное описание моделей среды передачи данных, которые могут быть использованы в сочетании с предложенными алгоритмами: полносвязной модели, модели с общей шиной, модели коммутируемой сети Fibre Channel.

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

В Приложении Г приведено подробное описание задачи определения координат источника сигнала с помощью фазированных антенных решеток.

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

1 Постановка задачи 1.1 Содержательное описание задачи Задача структурного синтеза в самом общем виде состоит в поиске оптимальной конфигурации вычислительных систем реального времени. В данной работе рассматривается класс многопроцессорных вычислительных систем реального времени [89]. Такая система состоит из вычислителей (процессоров) и среды передачи данных, объединяющей эти вычислители. Также в системе могут присутствовать устройства для ввода или вывода данных, но в дальнейшем рассматривается задача выбора минимально необходимого числа процессоров.

В данной работе рассматриваются только однородные системы [33][87][88], то есть системы, в которых процессоры одинаковые по производительности и надежности. Программа, выполняемая в системе, представляется ориентированным ациклическим графом потока данных [41][42][78]. Программа состоит из конечного множества взаимодействующих заданий, каждое из которых представляет собой подпрограмму, принимающую и передающую данные от других подпрограмм. Для каждого из заданий известно, какие вычисления оно производит и каков объем результата, получаемого на выходе и передаваемого другим заданиям. Таким образом, вершины графа соответствуют заданиям, а ребра – зависимостям по данным между заданиями. Формально модель системы введена в подразделе 1.2.

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

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

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

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

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

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

1.2 Модель входных данных Формально модель системы состоит из следующих объектов.

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

– граф потока данных программы, ориентированный – множество вершин, соответствующих заданиям.;

принимает на вход результаты работы задания ;

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

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

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

1.3 Механизмы обеспечения надежности Надежность есть свойство системы работать без отказов на некотором промежутке времени [20]. Подробно вопросы формализации понятия надежности рассмотрены в приложении А; в данном разделе считается, что время работы системы ограничено, и надежность от времени не зависит.

Поэтому в дальнейшем будет использоваться следующее определение.

Определение 1.1. Надежность – это вероятность (число от 0 до 1) того, что вычислительная система проработает безотказно.

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

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

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

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

При N-версионном программировании (NVP) создается версий реализации какого-либо задания [49]. Число версий всегда нечетно (обычно либо 5), и результаты подвергаются простому сравнению, итоговым результатом объявляется тот, который выдали больше половины версий. Таким образом, при отказе не более чем версий отказа не происходит. Разные версии обычно разрабатываются разными группами программистов для того, чтобы по возможности неисправности были различны в разных версиях. Предполагается, что если неисправности различны, то версии отказывают на разных входных данных.

Для определения надежности системы должны быть заданы следующие исходные данные.

– функция, задающая количественные характеристики надежности каждой версии.

Формулы для вычисления надежности системы приведены в разделе 1.6.

1.4 Модель расписания Будем считать, что для программы задано расписание, если для каждого из заданий определена привязка – однозначно определено, на каком процессоре оно выполняется, и задан порядок – для каждого процессора известно, в какой очередности выполняются задания.

Если используется многоверсионное программирование, то помимо указания задания, необходимо указывать номер его версии, то есть привязка и порядок задаются не для задания, а для пары «задание-версия».

Определение 1.2. Расписание (для системы с резервированием и многоверсионным программированием) определяется как пара, где – – мультимножество, состоящее из элементов множества процессоров процессора в мультимножестве.

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

Мультимножество задает резервируемые процессоры.

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

Определение 1.3. Элемент расписания будем называть зависимым от, если либо, либо. Иначе говоря, зависит от, если не может начать выполняться раньше из-за зависимости по данным или из-за порядка выполнения на процессоре.

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

Определение 1.4. Расписание является корректным, если его граф является ациклическим.

Рисунок 1.1. Пример некорректного расписания.

В дальнейшем будем рассматривать только корректные расписания.

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

Пример некорректного расписания приведен на рисунке 1.1. Задание не зависит на графе программы от задания 4, а задание 3 – от задания 2, но из-за неправильного порядка на процессорах четыре задания зависят друг от друга циклически.

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

Определение 1.5. Будем говорить, что для корректного расписания определена временная диаграмма, если определены две функции:

удовлетворяющие следующим условиям:

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

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

Функции и неявно зависят от функций и, введенных в разделе 1.2. Эта связь задается функцией интерпретации.

Определение 1.6. Функцией интерпретации времени называется вычислимая функция, по произвольному корректному расписанию однозначно строящая временную диаграмму:

Определение 1.7. Время выполнения t(S) – это время завершения последнего задания во временной диаграмме:

Рисунок 1.2. Визуальное представление функции интерпретации.

На рисунке 1.2 приведено наглядное представление функции интерпретации, которое будет использоваться на иллюстрациях в дальнейшем.

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

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

Полносвязная модель [23], когда любая передача данных может быть начата в любой момент времени, т.е. не существует конфликтов в среде передачи данных (приложение Б.1);

Модель шины [26], когда в любой момент времени во всей системе может быть только одна передача данных (приложение Б.2);

Модель коммутируемой сети Fibre Channel [21], когда любой процессор может одновременно участвовать только в одной передачу данных (приложение Б.2);

Интерпретация с помощью имитационного моделирования [17] (приложение В).

1.6 Вычисление надежности Определение 1.8. Функция оценки надежности задания – функция, определяющая надежность задания с учетом всех его версий:

Функция оценки надежности учитывает, какие из версий задания используются в расписании, и их характеристики Определение 1.9. Надежность системы – это следующая величина [100]:

Первый множитель соответствует совокупной надежности процессоров.

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

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

Пусть также фиксированы функция интерпретации и функция оценки надежности задания.

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

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

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

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

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

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

Утверждение 1.2. Задача (1) является NP-трудной.

Доказательство. Сформулируем задачу определения свойства, соответствующую задаче (1):

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

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

Во-вторых, нужно доказать, что любая задача из класса NP сводится к нашей задаче [13].

Рассмотрим задачу о разбиении: даны числа, требуется ответить на вопрос, существует ли разбиение этих чисел на две группы, так что сумма чисел в каждой из групп одинакова? Задача о разбиении является NP-полной, так как сводится к задаче выполнимости [13].

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

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

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

Поскольку при сведении рассчитывалась только сумма n чисел, сведение имеет полиномиальную сложность.

Таким образом, задача о построении расписания входит в класс NP и NP-полная задача о разбиении сводится к ней, а значит, задача о построении расписания входит в класс NPC, что и требовалось доказать.

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

2 Обзор возможных подходов к построению алгоритмов решения задачи и алгоритмов решения близких задач 2.1 Цель обзора В данном разделе будет проведен аналитический обзор подходов к разработке алгоритмов построения расписаний, которые могут быть использованы для построения алгоритмов сформулированной в разделе 1 задачи. Достаточно полная классификация задач построения расписаний приводится в [34]. Между тем, значительная часть упомянутых там задач не являются NP-трудными, а значит, алгоритмы их решения неприменимы к рассматриваемой задаче.

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

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

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

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

2.3 Метод ветвей и границ Суть метода ветвей и границ [58] в ограничении полного перебора с помощью разбиения всего множества решений на подмножества и отсечения заведомо неперспективных подмножеств. Если в подмножестве нижняя граница значений целевой функции больше, чем верхняя граница в подмножестве, то подмножество можно не рассматривать, так как минимум на нем заведомо не достигается. Для некоторых задач эта процедура может существенно сузить область поиска оптимального решения.

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

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

2.4 Жадные алгоритмы Жадные алгоритмы [34] решения NP-трудных задач в общем случае дают приближенное решение. В начале работы алгоритма текущее расписание пустое. Итоговое расписание строится путем последовательного добавления заданий к текущему в соответствии с некоторым критерием.

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

В литературе достаточно часто рассматриваются алгоритмы динамического построения расписаний с учетом надежности (для фиксированного числа процессоров). Наиболее простые жадные алгоритмы DASAP (do as soon as possible) и DALAP (do as late as possible) описаны в [83]. Первый алгоритм ставит очередное задание как можно раньше, второй – как можно ближе к директивному сроку, но не превосходя его. В той же работе предложен алгоритм DRCD (Dynamic reliability cost driven), учитывающий при построении расписания надежность каждого задания. В работе [82] описан еще более сложный алгоритм eFRCD (efficient fault-tolerant reliability cost driven).

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

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

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

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

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

Пример, когда жадный алгоритм, минимизирующий время, работает некорректно. Пусть программа состоит из трех заданий, каждое фиксированной длиной 1 единицу времени, связей между заданиями нет. Резервных версий нет, надежность каждого процессора равна 0.9, надежность каждого задания равна 1. Жадный алгоритм расставит каждое из заданий на отдельный процессор, после чего потребуется использовать резервные процессоры, чтобы поднять надежность до уровня 0.9. Для этого нужно к каждому из трех процессоров добавить резерв, то есть всего процессоров будет 6. Общая надежность составит 0.993. Если рассмотреть семейство аналогичных задач с, то число резервов каждого процессора, необходимое для достижения требуемой надежности будет возрастающей функцией от, стремящейся к бесконечности при стремящемся к 1 слева. Таким образом, можно привести пример, когда результат работы жадного алгоритма будет содержать сколь угодно большое число процессоров. Однако оптимальное решение использует только один процессор, на который надо поместить все задания.

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

Общий принцип работы алгоритма имитации отжига следующий [51].

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

Алгоритм имитации отжига создавался для задач безусловной непрерывной оптимизации, однако успешно применяется для широкого круга задач, в том числе для нелинейной условной оптимизации [98]. Имеются примеры использования имитации отжига для решения задач планирования (job shop scheduling). В [15] формулируются общие принципы применения алгоритма имитации отжига для планирования: необходимо определить пространство решений, на котором идет поиск; задать структуру окрестности каждого решения, то есть, ввести операции преобразования решения; наконец, определить целевую функцию алгоритма. При соблюдении этих требований алгоритм не только будет работать на практике, но можно будет также и теоретически доказать его асимптотическую сходимость.

В работе [76] приведены экспериментальные подтверждения эффективности алгоритма имитации отжига для задачи построения расписаний (не идентичной рассматриваемой, но также связанной с построением расписания для программы, заданной ориентированным ациклическим графом потока данных). В более подробной работе [77] предлагается усовершенствованный подход к построению алгоритма, основанный на применении эвристик. В классическом алгоритме имитации отжига новое приближение выбирается в окрестности текущего случайным образом, однако, зная, что поиск идет в пространстве многопроцессорных расписаний, можно использовать эвристики, направляющие поиск. Примерами таких эвристик служит построение расписаний по критическому пути [102], топологическое перемещение заданий (задания, связанные друг с другом, по возможности перемещаются на один процессор), балансировка нагрузки на процессоры, оптимизация отдельных обособленных подграфов [76].

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

2.6 Генетические алгоритмы Генетический алгоритм моделирует природный процесс естественного отбора. Общая схема работы генетического алгоритма следующая [44]:

1. Сначала возможные решения кодируются (обычно в виде бинарных строк или строк из чисел). Далее делаются следующие шаги.

2. Создание начальной популяции из некоторого фиксированного количества решений.

3. Скрещивание – лучшие решения обмениваются отдельными частями строк, которые их кодируют, друг с другом.

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

5. Селекция – отбор лучших решений по определенному критерию 6. Переход на пункт 3 или завершение работы, если выполнен критерий останова (нет существенных изменений в течение нескольких шагов подряд либо достигнуто максимальное количество шагов).

Существует гипотеза о возможности сходимости генетического алгоритма к оптимуму [39].

Конкретная реализация генетического алгоритма зависит от задачи и тех объектов, с которыми она работает. Кодирование многопроцессорных расписаний представляет собой нетривиальную задачу. В случае, когда задания в расписании независимы, достаточно указать привязку к процессорам, и тогда расписание можно закодировать списком Если же между заданиями есть зависимости, кодировка должна быть гораздо более сложной, при этом необходимо также, чтобы операции скрещивания и мутации не порождали в результате некорректные решения [40][30]. Операции скрещивания и мутации в этом случае могут быть совершенно не похожи на традиционные операции над битовыми строками, вместо этого расписания обмениваются фрагментами, перемещение которых заведомо не нарушает корректность [45][46].

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

В работах [31], [47], [48] описаны эволюционные алгоритмы, применяемые для построения расписаний. Их нельзя определенно назвать генетическими, так как в них нет операции скрещивания в чистом виде, и решения не кодируются, а работа происходит непосредственно с расписаниями.

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

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

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

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

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

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

В следующем разделе будет описан алгоритм имитации отжига для решения рассматриваемой в работе задачи.

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

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

Ш а г 4. Найти изменение функционала оценки качества решения ухудшилось), то принять с вероятностью в качестве текущего решения новый вариант решения.

Ш а г 5. Повторить заданное число раз шаги 3 и 4 без изменения текущей температуры.

Ш а г 6. Если критерий останова выполнен, то завершение работы алгоритма.

Ш а г 7. Понизить текущую температуру в соответствии с выбранным законом и перейти к шагу 3.

Для построения алгоритма имитации отжига для решения конкретной задачи условной оптимизации требуется решить следующие задачи [109]:

1. Разработать способ представления решения и операций преобразования текущего решения на шаге 3.

2. Разработать стратегию применения операций преобразования текущего решения на шаге 3: какую операцию применять, к какому элементу, как его изменять.

3. Выбрать закон понижения температуры на шаге 7.

текущего решения на шаге 4. В него входят целевая функция и могут входить все или часть функций-ограничений.

5. Выбрать критерий останова алгоритма, используемый на шаге 6.

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

3.2 Операции преобразования расписания Введем следующие обозначения.

, т.е. множество вершин – непосредственных предшественников ;

, то есть множество вершин – непосредственных и транзитивных последователей ;

Для преобразования расписаний введены следующие операции.

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

Операция удаления резервного процессора. В исходном расписании и происходит следующая замена:

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

Операция добавления версий. Версии можно добавлять только парами в силу принципа работы NVP. Добавление одной версии эквивалентно последовательности операций: 1) добавить новый процессор ; 2) назначить версию первым заданием на этот процессор ; 3) перенести на другой процессор в соответствии с определением операции переноса задания; 4) удалить.

Операция удаления версий. Версии удаляются также парами. Из расписания удаляются два элемента, соответствующие удаляемым версиям.

Утверждение 3.1. Замкнутость системы операций. Если – корректное расписание, то после применения любой из операций также получается корректное расписание.

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

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

Добавление ребра от к также не может создать цикл: в исходном графе не могло быть пути из в, так как в нем заведомо был путь из в (они находятся на одном процессоре), но не было циклов.

Рассмотрим операцию добавления версии. Операции, используемые на шагах 1, 3, 4, как уже доказано, корректны. Шаг 2 также корректный, так как в исходном графе нет циклов по условию, а других ребер, инцидентных новой вершине, нет, так как она на процессоре одна. Операция удаления версии также корректна, так как удаление заданий не может привести к появлению циклов.

Утверждение 3.2. Для каждой операции, переводящей расписание в расписание, существует обратная операция, переводящая расписание в расписание.

Доказательство.

Для добавления процессора обратной будет операция удаления этого же процессора, и наоборот. Эти операции всегда приводят к корректным расписаниям.

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

Для добавления версии обратной будет операция удаления, и наоборот.

Так как эти операции содержат в себе операции переноса, их корректность следует из корректности операции переноса.

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

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

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

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

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

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

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

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

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

3.3 Стратегии применения операций.

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

Далее описана процедура выбора параметров для каждой операции.

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

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

Добавление резервного процессора. Аналогично добавлению версии задания, процессоры с меньшим числом резервов имеют большую вероятность добавления.

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

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

Перенос задания.

Если, то следует пытаться уменьшить число процессоров.

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

Если, то необходимо улучшить время выполнения расписания.

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

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

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

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

Пример работы стратегии приведен на рисунке 3.1. Задание 3 не зависит от задания 4, поэтому перенос задания 4 на первый процессор уменьшает задержку задания 3, и общее время выполнения также уменьшается.

Рисунок 3.1. Пример стратегии уменьшения задержек.

Стратегия заполнения простоев (сокращенно стратегия S2). Эта стратегия основана на эмпирической гипотезе: чем меньше времени в сумме простаивают процессоры, тем лучше расписание.

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

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

На рисунке 3.2 приведен пример применения данной стратегии. Между заданиями 1 и 4 большой простой, поместив туда задание 3, можно добиться уменьшения времени выполнения всей программы.

Рисунок 3.2. Пример стратегии заполнения простоев.

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

Случайная стратегия (сокращенно стратегия S0). В этой стратегии параметры для операции выбираются случайным образом.

3.4 Условие перехода к новому расписанию и критерий останова.

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

Быстрое понижение температуры уменьшает вычислительную сложность алгоритма, но может привести к быстрой сходимости алгоритма к «плохому» локальному оптимуму. Медленное понижение температуры уменьшает вероятность сходимости алгоритма к «плохому» локальному оптимуму, но при этом вычислительная сложность алгоритма может оказаться неприемлемой. Поэтому при выборе закона понижения температуры требуется находить баланс между вычислительной сложностью и точностью алгоритма [99]. Следует заметить, что при любом законе понижения температуры есть вероятность потери наилучшего решения, найденного в ходе работы алгоритма. Поэтому во всех алгоритмах имитации отжига, которые были разработаны автором для решения задач построения расписаний и структурного синтеза вычислительных систем реального времени, на 3-м шаге алгоритма была добавлена операция сохранения наилучшего решения, которое было найдено в ходе работы алгоритма. Это решение и выдавалось в качестве результата работы алгоритма при его завершении.

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

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

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

Условие останова выбрано следующее: если число совершенных итераций равно, алгоритм завершает работу. Здесь – множество заданий, Такое условие останова гарантирует завершимость алгоритма.

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

Обозначим число вершин графа программы как, а число ребер – как.

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

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

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

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

Для вычисления функции нужно объединить значения функции, но не больше раз, чем ребер в графе. Значения функции вычисляются один раз до начала работы алгоритма.

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

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

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

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

4 Исследование свойств алгоритма 4.1 Асимптотическая сходимость алгоритма Несмотря на недетерминированный характер алгоритма имитации отжига, для него возможно строгое обоснование сходимости в терминах теории вероятностей. Для этого используется теория цепей Маркова [10].

Последовательность дискретных случайных величин называется цепью Маркова, если Иначе говоря, цепь Маркова – это последовательность случайных величин, в которой значение каждой случайной величины зависит только от значения предыдущей [11].

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

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

Схему работы предложенного в разделе 3 алгоритма имитации отжига можно рассматривать как цепь Маркова. Состояния соответствуют всем возможным расписаниям. Множество состояний счетно, а если количество резервных процессоров ограничено, то конечно. Вероятность перехода из одного состояния в другое определяется в соответствии со стратегиями применения операций, описанными в разделе 3.3. По построению алгоритма вероятность выполнить ту или иную операцию зависит только от текущего расписания, что соответствует определению цепи Маркова [43].

Построенная цепь Маркова обладает двумя свойствами: неразложимостью и ацикличностью [73].

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

У цепи Маркова существует стационарное распределение, если Пусть цепь Маркова неразложима и ациклична. Тогда [61] у нее существует единственное стационарное распределение, определяемое формулами:

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

Для стандартного алгоритма имитации отжига, представленного цепью Маркова, вероятность перехода из состояния в состояние есть произведение вероятности генерации решения, если текущее решение –, и вероятности принять в качестве нового приближения [29].

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

Здесь – размер окрестности решения, – значение целевой функции на решении.

При фиксированном значении температуры стационарное распределение для заданной таким образом цепи Маркова будет иметь следующий вид, определяемый из уравнений детального баланса [62].

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

Теорема. При стремлении температуры к нулю стационарное распределение приближается к распределению, допускающему только оптимальные решения.

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

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

Определим вид элементов матрицы переходов для рассматриваемого в данной работе алгоритма имитации отжига. Пусть – множество всех расписаний, которые можно получить из текущего расписания с учетом предыдущих операций алгоритма, влияющих на применение операции переноса задания (расширенная окрестность [105]). Тогда с учетом вероятности принять полученное в результате применения операции расписание в качестве нового приближения определяется как Неоднородная цепь Маркова называется слабо эргодической, если от номера итерации.

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

Дальнейшие рассуждения опираются на следующие две теоремы [62].

Теорема. Цепь Маркова сильно эргодична, если: 1) она слабо эргодична, 2) на каждой итерации у матрицы есть собственное значение, равное 1 и собственный вектор, 3) для этих собственных векторов Сформулируем основную теорему об асимптотической сходимости алгоритма имитации отжига по аналогии с классическим алгоритмом [5][107] и докажем ее применительно к рассматриваемому алгоритму. Для этого надо учесть особенности алгоритма, выраженные во введенной выше формуле, определяющей вероятности перехода от одного состояния цепи Маркова к другому.

. Тогда цепь Маркова, соответствующая алгоритму имитации отжига, сходится к стационарному распределению вида Доказательство. Сначала докажем сильную эргодичность цепи Маркова. Как несложно видеть, условие (2) из теоремы означает существование собственного вектора q, удовлетворяющего уравнению, баланса. Проверим, что значения удовлетворяют этим уравнениям.

Запишем уравнение детального баланса для q и проверим, что они выполняются.

Получили тождество.

Проверим выполнение условия (3).

сумма ряда конечна.

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

расходится.

Осталось определить предел вектора q при стремлении температуры к нулю. Для этого рассмотрим предел Если решение – оптимальное, то знаменатель дроби всегда будет равен 1. Числитель будет равен 1, если – тоже оптимальное решение, то Если решение – не оптимальное, то в знаменателе одной из дробей доказать.

Что касается скорости сходимости, приведем основные результаты из работ [94][97].

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

Здесь – второе по модулю собственное значение матрицы кратности.

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

4.2 Метрика в пространстве расписаний 4.2.1 Метрика L(A, B) Утверждение 4.2., – метрическое пространство.

Доказательство. Нужно доказать три свойства метрики [18]:

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

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

4.2.2 Метрика H(A, B) Метрика определена теоретически, но вычисление ее очень сложно:

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

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

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

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

Определение 4.5.

Утверждение 4.3., – метрическое пространство.

Доказательство. Нужно доказать три свойства метрики:

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

Если два расписания получаются друг из друга без перестановок, то они совпадают.

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

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

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

Пусть в первом расписании процессоров, во втором –. Добавим к тому, в котором их меньше, столько процессоров, сколько надо, чтобы уравнять число.

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

Например, пусть необходимо перевести расписания, изображенные на рисунке 4.1, одно в другое.

Рисунок 4.1. Пример двух расписаний для подсчета значения метрики Так, если сопоставить первый процессор в расписании слева ( ) первому процессору в расписании справа ( ), на нем надо переставить задания 3 и 2, и недостает задания 4. Тогда на втором процессоре не хватает заданий 5 и 7. Также надо удалить по одному резервному процессору.

Итоговое число перестановок при всевозможных сопоставлениях процессоров друг другу приведено в таблице 4.1.

Таблица 4.1. Число перестановок для расписаний на рисунке 4.1.

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

Пусть дана матрица размеров. Необходимо выбрать n ее элементов так, чтобы все они находились в различных строках и столбцах, а сумма была минимальной.

Данная задача решается алгоритмом Мункреса (также называемым венгерским алгоритмом) [56][69], имеющим сложность 4.2.3 Связь между метриками L(A, B) и H(A, B) Хотя перестановки соответствуют операциям преобразования расписания, определение перестановок не гарантирует, что соответствующая операция является корректной. По этой причине реальной цепочки длины, соединяющей два расписания, может не существовать.

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

Минимальная цепочка имеет длину не меньшую, чем эта. Утверждение доказано.

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

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

Рисунок 4.2. Пример, когда перестановки не соответствуют корректным операциям.

Некорректные расписания, получающиеся после устранения перестановок, приведены на рисунке 4.3.

Рисунок 4.3. Пример, когда перестановки не соответствуют корректным операциям.

4.2.4 Оценка для L(A, B) Пусть известно. Построим цепочку операций по следующему принципу. Сначала перебираются все перестановки, которые надо сделать.

Если есть возможность сделать корректную операцию, то она выполняется.

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

4.3 Экспериментальное исследование алгоритма 4.3.1 Оценка точности на модельных данных 4.3.1.1 Классификация исходных данных Возможные частные задачи рассматриваемой задачи построения расписания можно классифицировать по следующим параметрам: – число заданий, – соотношение между количеством ребер и количеством вершин в графе программы. Рассматриваются значения равное 1 (стандартное значение) и (экстремальное значение). Значение не будет рассматриваться, так как в этом случае задача фактически сводится к известной задаче о рюкзаке [27][64]. Рассмотрим еще два параметра классификации частных задач, которые определяются отношением директивного срока и оценками нижней границы времени выполнения программы и отношением требуемой надежности и оценками верхней границы надежности [4][6][106].

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

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

Жесткое:, где – время передачи данных для всех заданий критического пути.

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

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

4.3.1.2 Проверка статистических гипотез Для исследования алгоритма используется метод проверки статистических гипотез. В последующих разделах будут сформулированы гипотезы о работе алгоритма на выделенных классах исходных данных, и эти гипотезы будут проверены с заданным уровнем значимости [7][14].

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

Проверку такого типа называют -тестом.

Пусть известен тип распределения исследуемой случайной величины, но неизвестен конкретный параметр. Например, для распределения Бернулли, которое рассматривается далее, параметр есть вероятность выпадения 1. Проводится серия экспериментов, в результате каждого из которых получается некое наблюдаемое значение случайной величины. Если провести достаточно много экспериментов, то среднее арифметическое всех наблюдаемых величин должно приближаться к математическому ожиданию (закон больших чисел). Имеется некоторый уровень значимости, для которого проверяется гипотеза. В результате, если провести много экспериментов и найти вероятность получить имеющийся результат, исходя из гипотезы, тогда если эта вероятность окажется меньше, то это будет значить, что мы наблюдаем событие, которое имеет очень низкую вероятность в рамках гипотезы, то есть гипотеза признается неверной.

Формально, описанный выше алгоритм выглядит так:

1) Строится гипотеза вида «параметр ». Выбирается количество экспериментов и уровень значимости (в данной работе используются стандартные [3] для такого рода исследований значения 2) Производятся эксперименты и получается выборка. Вычисляется 3) Так как испытания независимы и проводятся в одинаковых условиях, применяется центральная предельная теорема, таким образом от 4) Строится альтернативная гипотеза, которая задает значения параметра, которые нас не устраивают. В результате критическая область имеет вид либо либо, где – это такое число, что. Непосредственное значение вычисляется напрямую с использованием функции Гаусса:

5) Вычисляется значение статистики. Если оно не попадает в критическую область, то гипотеза считается доказанной.

4.3.1.3 Оценка точности различных стратегий применения операций Для оценки точности различных стратегий было проведено около 10000 экспериментов с различными исходными данными. Число заданий варьировалось от 25 до 200 с шагом 5, также варьировались значения и для каждого значения числа заданий создавался граф программы, на нем алгоритм запускался поочередно с каждой из стратегий раз.

Число итераций алгоритма каждый раз задавалось одинаковым.

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

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

На графиках (Рисунок 4.4-4.8) приведены результаты сравнения четырех стратегий: стратегия уменьшения задержек (S1), стратегия заполнения простоев (S2), смешанная стратегия (S3), случайная стратегия (S0). Первые три графика (Рисунок 4.4-4.6) показывает среднее значение целевой функции в зависимости от числа заданий. Результаты для смешанной стратегии и стратегии уменьшения задержек почти одинаковые, стратегия заполнения простоев и случайный поиск заметно хуже.

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

Графики на рисунках 4.7-4.8 показывают попарное сравнение стратегий. Для каждой пары стратегий вычислялась разница значений целевых функций (числа процессоров). Графики показывают число экспериментов, на которых наблюдается то или иное значение этой разницы. Данные графики являются наглядным подтверждением статистической значимости результатов, проиллюстрированных на рисунках 4.4-4.6, так как разница значений целевых функций имеет распределение, близкое к нормальному.

Рисунок 4.4. Среднее значение целевой функции в зависимости от числа заданий для четырех стратегий,.

Рисунок 4.5. Среднее значение целевой функции в зависимости от числа заданий для четырех стратегий,.

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

Рисунок 4.7. Сравнение стратегии уменьшения задержек и стратегии заполнения простоев (по оси OX значение ).

Рисунок 4.8. Сравнение стратегий уменьшения задержек и смешанной Следующие гипотезы имеют место при размере выборки и Результат стратегий S1 и S3 лучше результатов стратегий S2 и S Локальная оптимальность алгоритма (имеет место в 100% случаев на рассмотренных выборках).

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

Таблица 4.2. Среднеквадратичное отклонение для каждой из четырех стратегий.

4.3.1.4 Оценка скорости работы алгоритма График на рисунке 4.9 показывает число итераций алгоритма, которое потребовалось для достижения наилучшего решения. В каждом эксперименте выполнялось итераций ( – число заданий), но с определенного момента текущее приближение не улучшалось. Номер итерации, на котором было достигнуто наилучшее решение, показан по оси OY на рисунке 4.9. Эксперименты показывают, что скорость стратегий S1 и S3 практически одинаковая, S3 лишь незначительно быстрее. Стратегия S2 значительно быстрее, но это объясняется тем, что точность ее результатов гораздо ниже, значит, и число итераций, необходимое, чтобы их достичь, ниже.

Рисунок 4.9. Сравнение скорости трех стратегий.

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

Совместимые исходные создавались по следующей схеме.

1. Фиксируются число заданий, число ребер, число процессоров и директивный срок. Функция интерпретации соответствует модели коммутатора.

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

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

Значение устанавливается так, чтобы для его соблюдения было достаточно процессоров.

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

4.3.2.2 Результаты работы алгоритма на совместимых исходных данных Было проведено 15000 экспериментов с различными исходными данными (число заданий варьировалось от 10 до 150, варьировалось от 0 до 2), на каждом алгоритм запускался поочередно с каждой из стратегий. Результат работы алгоритма сравнивался с оптимальным расписанием по На рисунках 4.10 и 4.11 приведены результаты.

Рисунок 4.10. Значение метрики между оптимальным решением и решением, полученным алгоритмом, при высоком.

Рисунок 4.11. Значение метрики между оптимальным решением и решением, полученным алгоритмом, при низком.

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

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

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

4.3.3 Сравнение законов понижения температуры В данном подразделе приведены результаты экспериментальных исследований точности и вычислительной сложности алгоритмов при использовании различных законов понижения температуры. Было проведено 1500 экспериментов с различными исходными данными (число заданий варьировалось от 10 до 150), на каждом алгоритм запускался поочередно с каждым из законов понижения температуры.

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

Рисунок 4.12. Разница в точности: Больцман – смешанный.

Рисунок 4.13. Разница в точности: Больцман – Коши.

Рисунок 4.14. Разница в точности: Коши – смешанный.

Смешанный закон имеет небольшое преимущество перед законами Больцмана и Коши.

На рисунке 4.15 приведено поведение алгоритма при различных начальных значениях температуры. Исследование проводилось для фиксированного числа заданий, равного 150.

Рисунок 4.15. Зависимость точности от начальной температуры.

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

На диаграммах (рисунки 4.16-4.17) показаны результаты сравнения скорости работы алгоритма при разных режимах понижения температуры.

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

Например, если с законом Больцмана было найдено решение с 10 процессорами за 100 итераций, а с законом Коши решение с 10 процессорами было достигнуто за 110 итераций, это означает, что второй закон дает результат на 10 % медленнее. По вертикальной оси указано число экспериментов, на которых был достигнут результат.

Число экспериментов Рисунок 4.16. Сравнение скорости законов Больцмана и смешанного для случая, когда смешанный дает лучший результат.

Число экспериментов Рисунок 4.17. Сравнение скорости законов Больцмана и смешанного для случая, когда Больцман дает лучший результат.

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

Итак, когда результат, получаемый алгоритмом с законом Больцмана, точнее, он получается быстрее в среднем на 18,23 % (с дисперсией 24,79).

Когда же смешанный закон дает более точные результаты, они получаются быстрее в среднем на 11,28 % (с дисперсией 44,66). Под дисперсией понимается среднеквадратичное отклонение разницы в скорости работы алгоритма при двух разных режимах понижения температуры от её среднего значения.

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

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

5 Инструментальная система 5.1 Требования к системе На основе разработанных алгоритмов построено программное средство, позволяющее решать задачу структурного синтеза в режиме диалога с пользователем. Приведем основные требования, которым должна удовлетворять такая система:

Наличие графического интерфейса пользователя.