Содержание к диссертации
Введение
Глава 1 Анализ современных подходов при назначении и планировании заданий в распределенных системах реального времени 9
1.1 Проблема организации вычислений в распределенных системах 9
1.2 Подходы к организации вычислений в распределенной системе с совмещением процедур назначения и планирования заданий 12
1.3. Планирование при заданном размещении заданий по процессорам распределенной системы 19
1.4 Выводы 22
Глава 2 Методы назначения заданий на процессоры и каналы обмена в распределенных системах реального времени 24
2.1 Назначение заданий в безызбыточных системах 24
2.2 Назначение заданий в избыточных распределенных системах 35
2.3 Анализ эффективности алгоритмов назначения заданий 43
2.4 Выводы 46
Глава 3 Методы планирование заданий в распределенных системах реального времени 47
3.1 Постановка проблемы flow shop-планирования 48
3.2 Специальные классы flow shop-систем 52
3.3 Планирования заданий с одинаковой последовательностью посещений процессоров 55
3.4 Планирование заданий с разной последовательностью посещений процессоров з
3.5 Анализ эффективности алгоритмов планирования 83
3.6 Выводы 86
Глава 4 Результаты апробации методов назначения и планирования заданий в системе освещения обстановки
4.1 Анализ алгоритмического и программного обеспечения 88
4.2 Назначение и планирование заданий в вычислительном комплексе ГАК СОО 94
4.3 Назначение заданий в подсистемах СОО 97
4.4 Программные средства поддержки и исследования процедур назначения и планирования заданий 102
4.5 Выводы 110
Заключение 111
Список литературы 113
- Подходы к организации вычислений в распределенной системе с совмещением процедур назначения и планирования заданий
- Планирование при заданном размещении заданий по процессорам распределенной системы
- Анализ эффективности алгоритмов назначения заданий
- Назначение заданий в подсистемах СОО
Введение к работе
Актуальность темы диссертации. Проблемы проектирования систем реального времени (СРВ) широко обсуждаются в современной научно-технической литературе как в России, так и за рубежом. Этот класс систем достаточно многообразен. К нему относятся системы обработки информации, управления подвижными объектами и технологическими линиями, навигации, связи, теле- и радиовещания. Примерами таких систем могут служить инерциальные и интегрированные навигационные системы, гравиметрические комплексы, системы освещения обстановки подводных аппаратов. Обычно СРВ принято характеризовать рядом определяющих особенностей. Среди них периодичность входного потока данных и, как следствие, периодичность всего вычислительного процесса. При этом период выбирается адекватным скорости протекания анализируемых и управляемых процессов. Кроме того, обычно отмечают необходимость привязки некоторых событий в процессах управления и обработки информации к заданным точкам или интервалам на временной оси посредством назначения директивных сроков или интервалов. Важно отметить, что современные СРВ отличаются высокой сложностью программного обеспечения, что заставляет в большинстве случаев с целью увеличения производительности обращаться к концепции распределенных вычислений. Можно утверждать, что процесс проектирования и эксплуатации СРВ обладает существенными особенностями и подчас ставит перед их разработчиками сложные вопросы, связанные, в частности, с организацией вычислений. Непременными составляющими этой проблемы являются назначение выполняемых заданий на процессоры и их планирование.
Проблемам назначения и планирования заданий в научно-технической литературе посвящено большое число публикаций. Основополагающие результаты были получены в работах Liu C.L., Layland J.W., Coffman E.G., Cottet F., Stankovic J. A., Martello S., Toth P., Keller H., Топоркова В.В., Костенко В.А. и других авторов. Тем не менее, высокая размерность проблемы, характерная для рассматриваемой предметной области, необходимость проведения вычислений (а в ряде ситуаций и решения самой проблемы назначения и планирования) в реальном времени не позволяют применять многие известные подходы, нацеленные на получение оптимального результата. По этой причине широкое распространение на практике получили приближенные алгоритмы, позволяющие получить решение близкое к оптимальному за существенно меньшее время. Разработке и исследованию таких алгоритмов и посвящена настоящая диссертация, что позволяет считать ее тему актуальной.
Объектом исследования являются бортовые интегрированные системы обработки информации и управления в реальном времени.
Предметом исследования выступают методы назначения и планирования заданий в распределенных вычислительных системах обработки информации и управления в реальном времени.
Цель работы состоит в разработке и исследовании для распределенных вычислительных систем обработки информации и управления в реальном времени эффективных алгоритмов назначения и планирования заданий, близких по своим характеристикам к оптимальным при существенно меньшей вычислительной сложности.
Для достижения этой цели были поставлены и решены следующие задачи:
-
анализ современных методов назначения и планирования заданий;
-
разработка и исследование алгоритма назначения заданий на процессоры распределенных СРВ, в том числе и для избыточных систем;
-
разработка и исследование алгоритмов планирования заданий на основе концепции разрешимых классов систем;
-
разработка алгоритмов и программных средств для исследования эффективности и поддержки процедур назначения и планирования заданий распределенных СРВ;
-
подтверждение эффективности разработанных методов и программных средств по результатам их практической апробации.
Методология и методы исследования. Для решения поставленных задач использовались методы теории графов, дискретной математики, теории алгоритмов и теории надежности.
Научная новизна
-
Разработан основанный на графовом подходе приближенный алгоритм полиномиальной сложности для назначения заданий на процессоры распределенных СРВ, в том числе избыточных, отличающийся от известных приближенных алгоритмов учетом структуры заданий и позволивший повысить эффективность назначения в смысле принятого критерия в среднем на 10%.
-
Разработан метод планирования заданий для распределенных СРВ с одинаковой последовательностью посещений процессоров по критериям минимума общего времени выполнения плана и минимума максимального отклонения времен завершения заданий от их директивных сроков, представленный двумя версиями приближенного РКС-алгоритма. Алгоритмы отличаются от известных приближенных алгоритмов учетом характеристик планируемости системы и позво-
ляют при незначительном проигрыше по значению критериев существенно сократить время выполнения алгоритма.
3. Предложен комбинированный подход к назначению и планированию заданий для распределенных СРВ с разной последовательностью посещений процессоров, отличающийся от известных низкой вычислительной сложностью, а также использованием комбинации алгоритма сетевого упорядочивания и РКС-алгоритма.
Практическая значимость и внедрение результатов
-
Предложенные алгоритмы назначения и планирования заданий позволяют сокращать затраты на поиск эффективных вариантов реализации СРВ.
-
Разработанные программные средства позволяют автоматизировать процедуры назначения и планирования заданий СРВ.
-
Предложенные решения были применены при разработке в АО «Концерн «ЦНИИ «Электроприбор» систем навигации и освещения обстановки подводных аппаратов.
Основные положения, выносимые на защиту:
-
Алгоритм для назначения заданий на процессоры распределенных вычислительных СРВ, в том числе избыточных.
-
Метод планирования заданий для распределенных СРВ с одинаковой последовательностью посещений для двух критериев.
-
Комбинированный подход к назначению и планированию заданий для распределенной вычислительной СРВ с разной последовательностью посещений на основе алгоритма сетевого упорядочивания и РКС-алгоритма.
Достоверность научных результатов и выводов подтверждается использованием корректных математических приемов, сопоставлением аналитических результатов и данных, полученных в ходе математического моделирования и экспериментальных исследований, критическим обсуждением результатов работы на научно-технических конференциях.
Апробация результатов работы. Материалы диссертации докладывались и обсуждались на 6-й и 8-й Всероссийских мультиконференциях по проблемам управления (Дивноморское, 2013; 2015), на XIX Международном научно-техническом семинаре «Современные технологии в задачах управления, автоматики и обработки информации» (Алушта, 2013), на XXVIII и XXIX конференциях памяти выдающегося конструктора гироскопических приборов Н.Н. Острякова (Санкт-Петербург, 2012; 2014), на XII Всероссийском совещании по проблемам управления (Москва, 2014), на Всероссийской конференции по проблемам управления в технических системах (Санкт-Петербург, 2015). Практическая апробация
результатов диссертационной работы осуществлена при разработке цифровых вычислителей в АО "Концерн "ЦНИИ "Электроприбор" в части алгоритмических и программных средств для поддержки процедур назначения и планирования заданий и исследования эффективности полученных решений.
Публикации. По материалам диссертации опубликовано 19 работ, из них 4 публикации в ведущих рецензируемых изданиях, рекомендуемых ВАК Минобразования и науки РФ и 11 докладов в материалах всероссийских и международных конференций.
Структура и объем диссертации. Диссертация состоит из введения, четырех разделов, заключения и списка использованных источников, содержащего 97 наименований. Объем работы составляет 124 страницы, включая 35 рисунков и 16 таблиц.
Подходы к организации вычислений в распределенной системе с совмещением процедур назначения и планирования заданий
Известно, что проблемы (2.1) и (3.1) относятся к классу NP-трудных [46, 57], что означает экспоненциальный рост вычислительной сложности решения при линейном росте размерности задачи. В теории вычислительной сложности известны два направления, связанных с решением NP-трудных комбинаторных задач, нацеленные на поиск оптимальных и приближенных решений соответственно. В рамках первого направления используются в общем случае переборные алгоритмы, характеризующиеся экспоненциальной вычислительной сложностью. Второму направлению соответствуют приближенные алгоритмы, позволяющие сравнительно быстро получать удовлетворительные решения, не являющиеся оптимальными. Их иногда называют конструктивными и оптимизационными эвристиками. Применение приближенных алгоритмов оправдано при необходимости быстрой оценки выполнимости вычислений в системе, разработке прототипов вычислительных систем, а также для получения опорных решений при поиске оптимальных результатов [57].
Оптимальные алгоритмы. Самым очевидным и при этом самым затратным среди оптимальных алгоритмов по времени выполнения является алгоритм полного перебора, в котором последовательно исследуется все множество решений (вариантов назначения и/или планирования) на предмет оптимальности по заданному критерию. Для устранения недостатков, связанных со большим временем выполнения, существуют различные параллельные варианты этого алгоритма, а так же ряд других алгоритмов. Среди последних наибольшее распространение получил алгоритм ветвей и границ (Branch and Bound Algorithm) [54, 71, 80, 81].
В основе алгоритма ветвей и границ лежат две процедуры: ветвление и ограничение. Процедура ветвления заключается в разбиении всего множества решений на подмножества и их дальнейшее изучение. Подмножество решений либо отбраковывается, когда оно не содержит решения лучше известного, либо происходит его дальнейшее разбиение на подмножества до тех пор, пока не будет найдено оптимальное решение. Процесс ветвления удобно представлять в виде дерева поиска, где корень - все множество решений, а другие вершины представляют подмножества, на которые было разделено исходное множество. Листья такого дерева обычно отображают конкретные решения (варианты перестановок заданий в плане или их распределений по процессорам), а предшествующие вершины - частичные решения. Пример такого дерева для решения проблемы заданий планирования приведен на рисунке 1.1, где вершины отмечены сформированными к данному шагу перестановками заданий (где тi z-е
задание, i = l,m). Таким образом, поиск по дереву приводит к решению проблемы. Очевидно, что число вершин в дереве поиска растет экспоненциально с «глубиной» дерева поиска (т.е. размером задачи). Следовательно, необходима вторая часть алгоритма - ограничение, т.е. отсев направлений поиска (подмножеств решений), которые не приведут к решению, лучшему, чем известно на данном этапе поиска. Решения сравниваются между собой по величине используемого критерия, величина которого для некоторой подгруппы решений определяется ее нижней границей. Исходное решение для сравнения может быть найдено с помощью некоторого эвристического алгоритма до запуска алгоритма ветвей и границ, а все последующие будут сформированы уже самим алгоритмом (если новое решение лучше старого, то оно принимается в качестве эталонного). Алгоритм ветвей и границ дает оптимальное решение за довольно быстрое время, но потребуется экспоненциальное время для доказательства, что это решение оптимально наверняка. Известны также параллельные версии этого алгоритма [54].
Среди прочих следует выделить такие оптимальные подходы к решению задачи организации вычислений, как динамическое и линейное программирование, а также проблемно-ориентированные методы. Общим недостатком названных подходов является то, что они не универсальны, и в общем случае обладают не полиномиальной сложностью. Так, например проблемно-ориентированные методы решения позволяют получать оптимальное решение за полиномиальное время, но только для строго определенного класса систем, что сильно ограничивает сферу их применения. Приближенные алгоритмы. Класс приближенных алгоритмов можно условно разделить на две группы: оптимизационные и конструктивные эвристики. Первая объединяет в себе методы, основанные на различных стратегиях поиска около-оптимального решения, т.н. алгоритмы ненаправленного поиска (АННП). Во многих АННП используется поиск с набором случайных параметров, таким образом, эти алгоритмы дают корректное решение с некоторой вероятностью. В отличие от метода ветвей и границ, АННП не исследуют всю область возможных решений, поэтому обычно используются два критерия прекращения работы алгоритма. Первый отражает ситуацию, когда удовлетворяющее решение найдено, второй - если достигнут предел вычислений (время решения или количество итераций). Обычно определяющие поведение АННП параметры подстраиваются от запуска к запуску алгоритма. Среди наиболее часто встречаемых в литературе оптимизационных эвристик можно выделить метод имитации отжига, поиск со списком запретов (taboo search) и генетические алгоритмы.
Метод имитации отжига [5, 48, 70, 90]. Метод основан на случайных перестановках заданий в плане или распределении задач по процессорам, которые изменяют оценку качества получаемого результата (в литературе используется термин «энергия», что связано с особенностями физического процесса, лежащего в основе полхода). Перестановки, приводящие к снижению оценки, допустимы, в то время как перестановки, увеличивающие ее на величину АЕ, возможны с вероятностью, убывающей экспоненциально с ростом приращения АЕ. Перестановки, снижающие качество решения на величину Ау принимаются с вероятностью e Ayt, где t - эквивалент температуры (для реального физического процесса). Таким образом, вероятность принятия таких перестановок тем выше, чем больше величина параметра t, т.е. при «остывании» принятие худшего результата менее вероятно. Процедура варьирования параметра t называется cooling schedule, она отличается в зависимости от реализации алгоритмов и, как правило, включает в себя все остальные шаги алгоритма. Для каждого значения этого параметра после определенного количества приемлемых перестановок достигается «термодинамическое равновесие», т.е. состояние локального оптимума.
Планирование при заданном размещении заданий по процессорам распределенной системы
Так же как и в случае безызбыточной системы по результатам применения приведенного алгоритма, исходя из заданной пропускной способности D используемых каналов обмена, производится определение их требуемого числа. В заключении приведем особенности процедуры назначения для избыточной распределенной системы в рассмотренной постановке: - допустимый фактор использования каждого из процессоров системы меньше единицы, - суммарный для всех процессоров запас по производительности на периоде Tвх должен быть не меньше производительности одного процессора, - в память каждого процессора загружено все программное обеспечение системы для исключения значительных информационных обменов при перенастройке системы после отказа.
Исследование эффективности предложенных алгоритмов назначения осуществлялось путем сбора статистики с использованием разработанной программы случайной генерации примеров заданий. Все эксперименты проводились в одинаковой вычислительной среде (язык программирования - C++ (Microsoft Visual Studio 2010), процессор - Intel Core i7-4710HQ CPU @ 2.50 GHz, память - 12 Gb).
Конечно же, получаемая статистика может в существенной степени зависеть от применяемого набора тестовых примеров, поэтому было бы желательно, чтобы генерируемые наборы назначаемых заданий обладали бы свойствами, характерными для практических приложений. Достижение этой цели является сложной проблемой, однако опыт в разработке вычислительных систем для навигационных и гидроакустических комплексов позволяет утверждать о преобладании на практике заданий с древообразными графами, а также заданий с малым числом базовых циклов. В связи с этим в настоящей работе была использована предложенная в [3] процедура автоматической генерации примеров. На первом шаге процедуры для заданного числа вершин посредством процедуры случайной генерации строится древообразный граф. Далее по желанию разработчика этот граф либо принимается как граф задания, либо достраивается до графа с заданным числом базовых циклов. Последняя цель достигается путем добавления в дерево соответствующего числа замыкающих ребер. Наконец, на последнем этапе для всех вершин и ребер графа случайным образом генерируются веса.
Каждый из полученных примеров решался тремя способами: при помощи остовного алгоритма, кластерного алгоритма и алгоритма полного перебора. Первые два алгоритма сопоставлялись с последним, который поставлял решение, оптимальное по критерию 2.1. Идея кластерного алгоритма [3, 38, 39, 78] заключается в следующем: на один процессор назначаются в первую очередь пары задач, информационный обмен между которыми наиболее интенсивен. В результате его применения множество задач разбивается на подмножества (кластеризация) с наиболее значительными внутренними межзадачными обменами.
В процессе исследования формировались статистики примеров, отличающихся от оптимального результата не более чем на 10% и 30%. Проигрыш определялся в соответствии с выражением є = , где Jopt opt значение критерия 2.1 для оптимального результата, а Jex - значение того же критерия для варианта назначения, полученного при помощи исследуемого алгоритма. Длительности задач моделировались в условных единицах как равномерно распределенные в интервале [0.1, 10], длительности обменов - в интервале [0.1, 5] при допустимой загрузке процессора и канала обмена, равных 10. На рисунках 2.6 и 2.7 приведены ряды статистик, полученных для разных типов графов заданий. Эти рисунки соответствуют разным значениям отношения bc/ap из критерия 2.1. В первом случае (рисунок 2.6) отношения bc/ap = 0,1, во втором (рисунок 2.7) отношение bc/ap = 10. Выбор правильного соотношения между коэффициентами a и b определяется рассматриваемым практическим приложением. Аргументом в построенных графиках является число базовых циклов, присутствующих в генерируемых графах заданий. Началу координат соответствует статистика, полученная для древообразных графов (нуль циклов), точке, отмеченной единицей на оси абсцисс – статистика для графов с одним циклом и т.д. Для каждой точки моделировалось по 500 примеров, в результате при доверительной вероятности, равной 0,95, доверительный интервал составил 0,5%. Сравнивая информацию, представленную на рисунках 2.6 и 2.7, можно видеть, что эффективность методов зависит от рассматриваемого приложения (от значения bc/ap). Этот факт был опубликован в диссертации Грузликова А.М. [3]. Таким образом, в области, где доминирует остовный алгоритм (bc/ap = 0,1), последний не менее чем в 90% случаев проигрывает оптимальному алгоритму не более 30%. Дополнительно хотелось бы отметить, что зависимость эффективности алгоритмов от сложности графа задания, измеряемой числом
Анализ эффективности алгоритмов назначения заданий
В данном разделе приводятся результаты исследования эффективности приближенного РКС-алгоритма, основанного на алгоритмах для четырех классов распределенных систем, рассмотренных выше, и предназначенного для планирования по критерию минимума общей длительности плана. Его результаты сравнивались с оптимальным результатом, полученным методом полного перебора, или оценкой этого результата для примеров большой размерности [93]. t ex ot Проигрыш определялся в соответствии с выражением є =—, где topt opt минимальное время выполнения плана, tex - время выполнения плана, составленного исследуемым алгоритмом.
Кроме того, осуществлялось сопоставление с известным эвристическим NEH-алгоритмом [75]. Для анализа эффективности приближенного алгоритма была разработана программа случайной генерации примеров, таким образом, в рамках каждого из примеров генерировалось множество планируемых заданий определенной структуры. Все эксперименты проводились в одинаковой вычислительной среде (язык программирования - C++ (Microsoft Visual Studio 2010), процессор - Intel Core i7-4710HQ CPU @ 2.50 GHz, память - 12 Gb). При этом с целью получения объективного результата фактически использовались два разных подхода.
В первом случае использовалась случайная генерация как графов заданий, так и длительностей составляющих их задач. При этом генерировались примеры с числом заданий из интервала [3, 250]. Для каждой точки из этого интервала генерировалось по 500 примеров. В результате при доверительной вероятности, равной 0,95, доверительный интервал составил 0,5%. При случайном формировании любого задания сначала производилось построение ациклического направленного графа, содержащего заданное число вершин при заданном числе базовых циклов в ненаправленном аналоге. В общем случае этот граф содержит не один путь между любыми выделенными вершинами. Далее для каждой задачи полученного графа путем случайной генерации формировались длительности выполнения как реализации случайной величины, равномерно распределенной в некотором интервале. Для удобства восприятия информации в таблице 3.6 приведен лишь показательный фрагмент результатов модельного эксперимента, отражающий проигрыш исследуемых алгоритмов по отношению к оптимальному, для пяти случайно сгенерированных структур, включающих по 10 заданий с 5, 10, 15, 25 и 50 задачами.
Видно, что в этом случае средний проигрыш NEH-алгоритма не превышал 7,7%, а РКС-алгоритмов – 11,6%. Однако при этом вычислительная сложность РКС-алгоритма существенно ниже, нежели у NEH-алгоритма. В частности времена выполнения алгоритмов отличались при числе заданий, равном 250, более чем в 100 раз. Это иллюстрируется на рисунке 3.10, где графически представлена зависимость времени выполнения исследуемых алгоритмов от числа заданий в плане, при этом использованы логарифмическая шкала времени (ось ординат). Рисунок 3.10 – Времена выполнения NEH- и РКС-алгоритмов в зависимости от числа заданий
При втором подходе исследование эффективности предложенных алгоритмов было осуществлено на известном наборе тестовых примеров Тейларда [88]. Набор тестовых примеров был разработан специально для исследования эффективности эвристических алгоритмов планирования в соответствии с моделью flow shop и содержит заранее определенное множество примеров заданий, сгруппированных в блоки по 10 наборов заданий, отличающихся по количеству заданий в плане (20, 50, 100, 200, 500) и числу задач в каждом из заданий (5, 10, 20). Для этих примеров известны результаты планирования для различных эвристических алгоритмов, в частности и для NEH-алгоритма, однако результаты планирования оптимальным (переборным) методом известны не для всех заданий. В таблице 3.7 приведены значения проигрыша оптимальному алгоритму для исследуемых алгоритмов, осредненные по блокам тестовых примеров (по 10 примеров в каждом).Видно, что на наборе примеров Тейларда предлагаемый алгоритм проигрывает оптимальному в среднем 15,7%, а NEH-алгоритму – около 5,5%.
Назначение заданий в подсистемах СОО
Для назначения задач на процессоры распределенной системы и формирования планов вычислений, а также и исследования эффективности предложенных алгоритмов назначения и планирования при участии автора были разработаны программные средства на языке С++, краткое описание которых приводится ниже в настоящем параграфе.
Программа назначения задач. Алгоритмы, лежащие в основе программного обеспечения для распределения задач по процессорам распределенной системы, были довольно детально рассмотрены в главе 2, здесь же ограничимся представлением обобщенной структуры программы (рисунок 4.11).
В зависимости от выполняемой функции (статистическое исследование эффективности или поддержка процедуры назначения задач для пользовательской системы), в основном цикле программы по числу примеров (pr N, где N – количество примеров) происходит случайная генерация очередного примера для планирования, или же, в обход цикла по примерам, – чтение заданного пользователем примера. Далее для него решается проблема назначения задач при помощи остовного, кластерного и оптимального переборного алгоритмов и рассчитывается значение критерия J=apP+bcC (критерий 2.1) для приближенных алгоритмов. Затем определяется относительный проигрыш приближенных вариантов назначения оптимальному по величине критерия J, после чего осуществляется переход к следующему примеру или же представление построенного плана пользователю и выход из программы. В случае статистического исследования, после завершения цикла по примерам происходит представление полученных статистических данных пользователю.
Алгоритм процедуры назначения задач и исследования эффективности приближенных алгоритмов Поиск оптимального варианта назначения производился путем полного перебора всех возможных планов с последующим выявлением результата с наименьшей величиной критерия J.
Программа планирования заданий. В отличие от программы назначения, вспомогательные алгоритмы которой уже были разобраны ранее, программа планирования заданий требует более детального рассмотрения, так как не все алгоритмы, лежащие в ее основе, были рассмотрены в главе 3. Этому и посвящен настоящий раздел. На рисунке 4.12 приведена обобщенная блок-схема программы для исследования эффективности алгоритмов планирования и поддержки процедуры составления пользовательских расписаний. Как видно, она идентична структуре программы назначения, за исключением применяемых решений.
Таким образом, в зависимости от выполняемой функции, в основном цикле программы происходит либо случайная генерация очередного примера для планирования, либо чтение его из библиотеки тестовых примеров Тейларда [93], или же, в обход цикла по примерам, – чтение примера, заданного пользователем. Затем для него формируется план и рассчитывается его длительность при помощи РКС-алгоритма, NEH-алгоритма и оптимального переборного алгоритма (или же производится оценка оптимального результата для примеров большой размерности). Далее определяется относительный проигрыш по длительности приближенных планов по отношению к оптимальному, после чего осуществляется переход к следующему примеру или же представление построенного плана пользователю и выход из программы. В случае статистического исследования, после завершения цикла по примерам происходит представление полученных статистических данных пользователю.
Поиск оптимального плана производился путем полного перебора всех возможных планов с последующим выделением плана с наименьшей длительностью. Для примеров большой размерности (при большом количестве заданий), когда получение оптимального результата затруднительно, используется его оценка [93]. Расчет длительности плана производился с использованием max-plus алгебры [41].
Рассмотрим подробнее реализацию РКС-алгоритма планирования. Как было отмечено выше, алгоритм является рекурсивным (рисунок 4.13). При этом в каждом цикле выполняется три шага:
Поскольку критические пути для разных заданий в общем случае различны осуществляется поиск псевдокритического пути, то есть некоторого усредненного критического пути в системе С(Р,т), в соответствии с выражением?(/? ) = max е;, где et - специальная метрика для каждого из процессоров вычислительного пути pk, характеризующая времена решения задач этого процессора, а щ - длина этого пути. В качестве такой метрики была выбрана медиана, которая рассчитывается для каждого из процессоров в системе по вектору длительностей решаемых на нем задач.
Содержание второго шага зависит от длины псевдокритического пути. Возможны два варианта: при длине пути не превышающей двух процессоров и при более длинном пути. Алгоритм для первого случая тривиален -достаточно сравнить медианы Єї и е2 времен решения задач для этих двух процессоров и соотнести систему с 1 (ei вг) или 2 (еі Єї) классом.
Во втором случае (рисунок 4.14) для решения задачи осуществляется квадратичная аппроксимация методом наименьших квадратов медиан для векторов времен решения задач для каждого процессора f(i)=ai2+bi+c, где f(i) - аппроксимирующий полном, / (i = \,n)- номер процессора псевдокритического пути длинной п, а (а, Ъ, с) - коэффициенты полинома f(i). При этом, если ветви параболы направлены вниз и вершина параболы f(io) оказывается слева от интервала номеров процессоров (а 0; і0 і), то система относится к классу 1, если справа (а 0; і0 п ), то - к классу 2, если внутри интервала (а 0; 1 і0 п ), то - к классу 3. В случае если ветви параболы направлены вверх, возможны следующие варианты: класс 1 (а 0; ц п), класс 2 (а 0; ц 1), класс 4 (а 0; К ц п). Номер процессора, соответствующий вершине аппроксимирующей параболы і0 определяется согласно выражению ig= [- b/2a], с округлением к ближайшему целому, а в случае выбора классов 3 или 4 определяет процессор h находящийся на стыке убывающей и возрастающей по отношению доминирования последовательностей процессоров.