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

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

Гуз Денис Сергеевич

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

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2005

Работа выполнена на кафедре математических основ управления Московского физико-технического института (государственного университета)

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

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

Фуругян Меран Габибуллаевич

Официальные оппоненты: доктор физико-математических наук Андрианов Александр Николаевич кандидат технических наук Костенко Валерий Алексеевич

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

Институт проблем управления им. В.А. Трапезникова Российской академии наук

Защита состоится jJ/U^-- 2005 г. в час.

на заседании диссертационного совета К 212.156.02 при Московском физико-техническом институте (государственном университете) по адресу: 141700, Московская обл., г. Долгопрудный, Институтский пер., 9.

С диссертацией можно ознакомиться в библиотеке МФТИ(ГУ).

Автореферат разослан

Ученый секретарь диссертационного совета к.ф.-м.н.

О.С. Федько

//Ш ' ЖУЗМ-

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность работы.

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

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

Построение расписаний в системах реального времени, как часть более общей теории планирования вычислений, начала активно развиваться с начала 70-х годов XX века в связи с практическими потребностями в массовом проектировании и эксплуатации подобных систем. В разные годы в СССР и России этой задачей занимались Танаев B.C., Шкурба В.В., Гордон B.C., Шафранский B.C., Головкин Б.А., Барский А.Б., Сотсков Ю.Н., Струсевич В.А., Мищенко A.B., Сушков Б.Г., Костенко B.Ä. и др. Среди зарубежных ученых следует отметить Jbo (Liu), Лейланда (Layland), Мартеля (Martel), Станковича (Stankovic), Рамамритама (Ramamritham), Бернса (Bums), Федергрюна (Federgruen), Греневельта (Groenevelt), Гонзалеса (Gonzales), Сахни (Sahni), Коффмана (Koffinan), Одели (Audsley), Ричардсона (Richardson), Мока (Мок), Веллингса (Wellings) и Дертузоса (Dertouzos) и др.

Несмотря на то, что для математических моделей однопроцессорной системы известны точные алгоритмы решения задачи поиска допустимого расписания, ни один из них не гарантирует topgëîcjj^ocrgeraeffi^^ случае

3 I библиотека**"I

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

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

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

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

Дели работы.

Целями настоящей диссертационной работы являются:

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

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

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

Научная новизна работы.

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

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

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

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

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

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

Методы исследований.

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

Практическая ценность работы.

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

Апробация работы.

Результаты диссертации и материалы исследований докладывались и обсуждались на:

- XLV, XLVI и XLVII научных конференциях Московского физико-технического института (государственного университета), (Долгопрудный, 2002, 2003,2004);

- X, XI и XII международных конференциях "Проблемы управления безопасностью сложных систем" (Москва, 2002,2003,2004);

- IV международной конференции по исследованию операций (Москва, 2004);

- научных семинарах кафедры математических основ управления Московского физико-технического института (государственного университета);

- научных семинарах сектора проектирования систем реального времени Вычислительного центра им. A.A. Дородницына Российской Академии Наук.

Публикации. По материалам диссертации опубликовано 13 печатных работ. Список работ приведен в конце автореферата.

Структура и объем работы.

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

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

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

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

Имеется вычислительная система, состоящая из т процессоров. Каждый процессор у (у' = 1 ,—,т) характеризуется скоростью выполнения работ скоростью загрузки данных /у и объемом памяти Имеется п работ, каждая из которых определяется своим директивным сроком начала г, и директивным сроком окончания с11, другими словами, директивным интервалом (/;,</,], 1 = 1,...,и, а также сложностью р1, (г = 1,...,«) и объемом данных V,, который необходимо загрузить в процессор для ее выполнения. Все параметры задачи полагаются целыми. Работа сложности р1 может быть

выполнена на процессореу за время ^. Время загрузки данных /-й работы на

у

у'-й процессор равно —. До начала выполнения работы / в память процессора

Ь

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

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

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

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

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

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

Для этой математической модели Федергрюн и Греневельт предложили точный полиномиальный алгоритм, основанный на совмещении идеи поиска максимального потока в сети специального вида для распределения частей работ по всем интервалам с инвариантным множеством выполнимых работ /, (если г0 <г, <...<тк- все различные значения rt и dt, i = 1,...,и. то /, =(г/_1;г/], / = 1,..., И) с алгоритмом, предложенным Гонзалесом и Сахни для поиска допустимого расписания на каждом таком интервале, где у всех выполнимых на нем работ общий директивный интервал. Несмотря на то, что предложенный алгоритм находит точное решение за полиномиальное время (Ö(/nV)), вычислительная сложность этого метода является слишком большой для его практического применения в задачах достаточно большой размерности, имеющих, тем не менее, практический смысл. Например, уже в случае 64 процессоров и всего лишь 500 работ данный алгоритм, запущенный на современном ПК, искал допустимое расписание более 11 часов.

Поэтому для практического применения в задачах большой размерности в данном случае оправдано применение эвристических алгоритмов. В диссертации было разработано два эвристических алгоритма, относящихся к известному классу EDF (earliest deadline first). Первый алгоритм, получивший название Эвристика 1 работает следующим образом:

1) Каждой г'-й работе назначается приоритет, равный -dt.

2) По очереди рассматриваются все моменты времени начал и концов директивных интервалов работ г, и dt, начиная с min г, и заканчивая maxcf,

3) Работа, ставшая доступной в текущий рассматриваемый момент времени, назначается на самый быстрый из свободных процессоров. Если таких процессоров нет, и имеется работа с меньшим приоритетом, то она прерывается, и работа ставшая доступной назначается на выполнение этим процессором вместо нее.

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

Вычислительная сложность Эвристики 1 0(пт) (Лемма 2), Эвристики 2 - 0(п21оё п) (Лемма 3). Проведенные численные эксперименты показали, что в случае 64 процессоров и 500 работ (на котором ранее запускался точный алгоритм), алгоритмы Эвристика 1 и Эвристика 2 работали в среднем, соответственно, 3.45 с и 14.60 с, что является очень существенным выигрышем в производительности.

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

С целью поиска границ применимости предложенных алгоритмов было проведено около 25 ООО сравнительных численных экспериментов при различных параметрах задачи, которые показали, что области некорректной работы алгоритмов Эвристика 1 и Эвристика 2 компактны на множестве этих параметров, средний уровень некорректной работы Эвристики 1 составил 20%, Эвристики 2 - всего 2%. Отсюда, несмотря на то, что Эвристика 2 обладает большей вычислительной сложностью, чем Эвристика 1, делается вывод, что именно этот алгоритм имеет смысл рекомендовать к практическому применению в крупномасштабных системах жесткого реального времени. Также дается ряд практических рекомендаций по совместному применению точных и эвристических алгоритмов.

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

со

пропорционально скорости соответствующего процессора } и равно —,

®>0), и смешанная (время переключения равно —+П и имеет как

постоянную, так и переменную компоненты).

Согласно Лемме 1, такая задача М>-трудна, поэтому для ее решения на, практике оправдано применение эвристических алгоритмов. Для этого построенные в предыдущей главе алгоритмы Эвристика 1 и Эвристика 2 были модифицированы для учета в своей работе временных затрат. При этом идеи работы алгоритмов остались неизменными. С целью учета временных затрат, при выполнении этих алгоритмов считалось, что в случае, когда происходит переключение или прерывание, к оставшейся части работы,

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

Было показано, что модифицированные алгоритмы, получившие названия, соответственно, Эвристика П1 и Эвристика П2, в рассчитываемых ими расписаниях генерируют столько же прерываний, сколько и их прототипы из предыдущей главы. Максимальное значение количества прерываний для Эвристики П1 таким образом равно (я-1) (Лемма 2), и 2 (п-1 )т для Эвристики П2 (Лемма 3). Показано, что вычислительная сложность модифицированных алгоритмов равна вычислительной сложности исходных и составляет 0(пт) и 0(п log п).

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

временных затрат была выбрана величина у] = -^уу, во втором - у2 = , в

третьем варианте рассматривались обе этих величины, так как величина затрат на прерывания в нем зависит от двух численных параметров Q и оз. h

Z'.

Здесь (7,) = ^-.

Каждый численный эксперимент для первой и второй схемы образования временных затрат заключался в том, что для выбранного значения /, или у2 случайным образом генерировались условия задачи и среди 6000 испытаний, проводимых для каждого выбранного значения, отмечались случаи, когда Эвристика П1 находила допустимое расписание, а Эвристика П2 - нет (количество таких случаев обозначалось как Q, (х,) или Qi(y2)), количество же случаев, когда все происходило наоборот, т.е. Эвристика П1 не находила допустимого расписания, зато его находила Эвристика П2 обозначалось как 62(/i) или Q2(y2)- На пересечении экспериментально построенных зависимостей Q,(y,) и Q2(/i) (при первой схеме образования временных затрат) и Q{(у2) и Q2(/2) (при второй схеме образования временных затрат) и находилось то искомое граничное значение параметров = 0.02 и у2 =0.07, при превышении которых Эвристика П1

становилась более предпочтительным для практического применения алгоритмом, чем Эвристика П2 (см. рис. 1 и рис. 2).

120?

тооо

015 02

Рис 1. Зависимое i и Qi(7,) и СЬ(/|) в случае 1-го варианта модели обраюванин временных iaipat на прерывания и возобновления рабок

'200

035

Рис 2. Зависимости 0.\(у- ) и Ог(у:) в случае 2-го варианта модели образования временных затрат на прерывания и возобновтения работ.

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

построены зависимости 0.[{УпУг) и 62(^1 >7г) (смысл величин 0и ()г такой же, как и в двух ранее рассмотренных случаях). На рис.3 изображена плоскость (УрТг)» на которой светлым обозначена полученная экспериментально область 0, > Qг (предпочтительно применение алгоритма Эвристика П1), темным - область < ()2 (предпочтительно применение алгоритма Эвристика П2).

О 18 г—---■--г-—^—-

О 141

О 12

£•0 08

0 061

аИИШЙВЕ

им®®аг

----НЯНИ!

mm

а »к г—

ISSSi.__

1евюгшвавт»ашв8в1

888i81SIISIt8SB88li liSSnSSSISfiltSSSSiS _______

в ШШ Hats ШхЗЩ ШШШШ sals Ш шШ BBeffiBtS Ш

»»18111Ш88Ш1В8Г

----И1Г----------

ЪШЩШЩШШI

„,_______asBsasQi

J 0ДИЯЧ»ЯИ1В1В1______

ТиввипишниаишЕзоша

ЙЯвмвя!!®! ввн "ПЮЯВДЯИП:

-----1евшяа@ваи-

„лтттт—— _ . is«se ~

О 02 0 04

ЭШЕ.___

_ 9f?H§fS6§B________

т&твтттттвтш

ээившЕЕШвизвн ~1в®кшш»»явва шнаянвегаива

о 1В

Рис 3. Экспериментально полученные области предпочтительного применения Эвристики 111 и Эвриешки П2 па плоскости (7,,v,) в случае 3-го варианта модели образования временных затрат на прерывания и возобновления работ.

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

Имеется однопроцессорная система и п работ, которые нужно выполнить за время, не превосходящее Работа / (/ = 1,...,и) имеет сложность /?, которая определяется как время ее выполнения (так как процессор в рассматриваемой системе один, его скорость без ограничения общности можно считать единичной). До начала исполнения работы / в память процессора должны быть загружены соответствующие данные. Предполагается, что время загрузки данных для работы / прямо

пропорционально загружаемому объему памяти. Поэтому без ограничения общности можно считать, что оно равно их объему. Обозначим эту величину ¿,(/ = 1,...,«). Объем памяти также удобно определить во временных единицах, будем считать, что всю память процессора можно полностью загрузить за время Я. Память может быть загружена (частично или полностью) некоторыми данными уже в начальный момент времени. Удаление данных из памяти происходит мгновенно сразу после выполнения соответствующей работы. Считается, что архитектура системы такова, что загрузка данных в память процессора и выполнение им работ - независимые процессы, которые могут идти параллельно, не влияя друг на друга.

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

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

Шаг 1 Положить Ь„ = гтш ;£?„ = ^; В = {Ь„}.

Шаг г. Пусть на предыдущих (г - 1) шагах определены величины Ьп_г+2,...,ьп, е„_г+2,...,£?„ И множество В = {Ьп г+г,...,Ьп]. Тогда, если существует такое I г В, что р, < , то положить Ьп_г+1 = /0, £?„_г+1 = 0лм2 - рк , + Г4, где г0 таково, что одновременно выполнены соотношения р^ = шах р, и р1а <<Зп_г+2, (т.е. среди пока не принадлежащих множеству В номеров ищем номер г0 такой работы, которая имеет максимальную, но при этом не превышающую 0,п_г+г сложность р^). Если же такого I не существует, то положить г>„_,+1 = /,, = ^, где таково, что рн = т тр,.

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

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

Теорема 1. Построенный алгоритм всегда корректно решает задачу поиска допустимого расписания в рассматриваемой в данной Главе однопроцессорной системе реального времени и обладает вычислительной сложностью 0{пг\о%п}.

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

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

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

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

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

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

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

Вычислительная сложность построенного эвристического алгоритма составляет 0(пгт\о%п).

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

при различных значениях которого были проведены серии по 100 экспериментов, в каждом из которых на его основании случайным образом генерировались параметры решаемой алгоритмом задачи. Эти эксперименты показали, что при ¡3 < 0.3 количество случаев некорректной работы эвристического алгоритма не превышает 10% от общего количества испытаний, при этом при ¡5 > 0.9 количество таких случаев было около 30%.

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

В четвертой главе рассматривается задача поиска допустимого расписания в наиболее общем, сформулированном в начале данной работы случае. Единственными упрощениями математической модели исходной постановки задачи является допущение, что все процессоры работают одинаковыми синхронизованными тактами, а время загрузки данных пренебрежимо мало. Следует обратить внимание на то, что рассматриваемые такты - не интерпретация элементарных тактов работы реальных процессоров, а способ дискретизации изначально рассматриваемой непрерывной (именно из-за малой продолжительности реальных тактов) задачи. Поэтому длительность рассматриваемых тактов много больше тактов работы реальных процессоров, и можно полагать, что их уменьшение приближает задачу к непрерывному случаю. Без ограничения общности можно считать, что все г1,йг натуральные числа (т.е. начала и концы всех директивных интервалов задают номера соответствующих тактов работы процессоров) и тт/;=0, тахл?, = Т (т.е. рассматривается Г тактов работы

процессоров). Таким образом, - это количество работы, выполняемой

Р _ /=1У

шах

М, ,п

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

процессорами могут меняться во времени, что определяется массивом / размером тхТхтхТ, при этом 1{]1,кх,]г,к2) = \, если при выполнении работы на процессоре_/! в конце такта к\ ее можно прервать и возобновить на процессореу'2 в начале такта к2, и = если такое переключение

невозможно (1 < у',,_/2 < т\ 1<к1<к2<Т).

Для решения сформулированной выше задачи строится многопродуктовая потоковая сеть N = (V, Е). Множество вершин сети Р(Л0 состоит из и источников и;, и2,...,и„ и и стоков и*/, м>2,...,м>п по количеству задач; Т ярусов (каждый по т пар вершин) соответствующих рассматриваемым в задаче тактов. Обозначим эти пары вершин как (*)».?))>./-!>■•» Щ к = 1,.., Т. Множество дуг Е(Ы) будет состоит из дуг,

соединяющих пары [х* ,у*) в каждом из Г ярусов; дуг (к,.**), соединяющих, для каждого / источник и,со всеми вершинами х*,/ = 1,..., т, к е (гД); дут (/,*>,), соединяющих для каждого I сток и», со всеми вершинами у*,7 = 1,..., от Аге^,^); дуг Для каждого г соединяющих

всевозможные ^ с х*', такие, что к; < к2 и =1, е(г(,с/,),

у„;2 = 1,..., от.

Количество вершин в построенной сети |К| = 2и + 2»гГ, количество дуг

Каждая дуга сети N имеет два параметра: пропускную способность и стоимость единицы потока по дуге. Пропускные способности всех дуг полагаем равными 1. Стоимость прохождения единицы потока по дуге

и,

Рис 4. Фрагмент сети N.

(л:*,у*)полагаем равной sJ, по дуге (д^,^)- равной , а по дугам (к,,х*)и (у*,™,) - равной 0.

Теорема 2. Допустимое расписание существует тогда и только тогда, когда в сети N существует п-продуктовый поток, обладающий следующими свойствами:

!/'(«Ь- I

при всех г = 1,..., и, т.е. суммарная стоимость потока г-го продукта составляет не менее ;

1,Г, г1<к<г2 г-1

при всех у = 1,..., т; к = 1,..., Т, т.е. на каждом такте выполнено ограничение по объему памяти каждого процессора.

Для построения допустимого расписания поток г-го продукта по дугам сети N интерпретируется следующим образом: по дуге (и,,*)) - начало

выполнения работы г (на такте к)\ по дуге - выполнение работы г

процессором у на такте к; по дуге ) - прерывание выполнения работы /

процессором у, на такте Л, и ее переключение на процессор 72 на такте к2;

по дуге (у*,™^ - конец выполнения работы / (на такте к).

Лемма 7. Сформулированная задача поиска многопродуктового потока ЫР-трудна.

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

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

o|(и65от5r5+и35m8rí)(7я57'5 + и5)log|27и(7' + l)шax/7JjJ. Так как полином

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

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

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

интервалом А\ = (г,,г/,], г = 1,...,», а также сложностью р,, г = 1,...,и и объемом данных, которые необходимо загрузить в память процессора для ее выполнения у,, /= 1Имеется /и процессоров различной вычислительной мощности = и различного объема памяти Ку,/ = 1,...,т. Работа

сложности р1 может быть выполнена на процессоре вычислительной мощности SJ за время Ц - р,1 зг В фиксированный момент времени каждая работа может выполняться не более чем одним процессором, и каждый процессор может выполнять не более одной работы. Для выполнения работы (или какой-либо ее части) на каком-либо процессоре все ее данные должны быть загружены в память этого процессора в полном объеме. При выполнении работ допускаются прерывания и переключения с одного процессора на другой. Затраты процессоров на прерывания, а также на загрузку и выгрузку работ из памяти процессоров пренебрежимо малы. Без ограничения общности можно считать, что у, >... > у„ и я, >...>$я.

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

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

Пусть т0<тх<...<тк- все различные значения и <5?,, г = 1.....п,

I, = (гы;г,], I = 1,..., А. Пусть 8Г длина интервала N - множество индексов работ.

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

неравенство:

где к{1, N0 = гат(т, от'), т' - число работ г е , доступных в интервале I,,

Пусть Щ.0 0 е N )- множество всех интервалов /,, в которых работа i доступна. Для всех 15 /, <, /2 < А определим следующие множества:

к

(17)

к

щ, =

'VI

Л^, если и =

0 в противном случае если и т = %

0 в противном случае

Далее показано, что допустимое расписание в рассматриваемой системе существует в том и только в том случае, когда неравенство (17) справедливо для всех 1\, 1г (1 < /, ^ /2 < /г) и всех подмножеств /У1 с Л^,

Л^2 с ^, для которых У £>(г) = /Д , /5(0 = . С учетом этого замечания

' /еЯ1

можно переписать (17) для подмножеств ТУ,, где _/ принадлежит некоторому множеству индексов У (|/| < й(й+1)):

k{Sx+k{S2+...+klSm>Q',jzJ, (18)

где к' = X ^ 0= 1,-,'«); ^ = 1 А-

Лемма 8. Неравенство (18) справедливо тогда и только тогда, когда

5„>тах—--, (20)

8>тах& (21)

' м

где 7Г = {у е У,^ +... + Л/ ^ 0}, г = 1,..., т -1.

Лемма 9. Пусть = ^ + 52+---+ ^ (к = 1,2,..., те). Для того, чтобы по заданным величинам ..., 5т можно было определить величины «ь ..., такие, что 5, > >... >5га > 0 необходимо и достаточно выполнение неравенств:

25г > 5Г_, + 5,+1 (г = 2,..., т -1).

Из утверждений лемм 8 и 9 следует, что для определения допустимых производительностей процессоров необходимо и достаточно определить величины 5ь-.которые задаются следующими неравенствами:

5„ > шах-

» Ц+- + К

5,,, >5, >тах

тах

, г = 2, ...,т-1

$¿>$¡2 тах

шах—-а-и-—

М 2

Для поиска допустимых решений нужно решить эту систему неравенств и найти вектор (51;...,5т), затем определить искомые величины ж,,...,^. Решение же различных оптимизационных задач (например, минимизация суммы производительностей процессоров) в данном случае сводится к решению задачи целочисленного линейного программирования.

Далее рассматривается случай ограничений на объем памяти процессоров.

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

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

/' -ю работу можно выполнять на j -м процессоре (то есть У/ > V,), и Еи = 0 в

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

Теорема 3. Для того, чтобы в рассматриваемой многопроцессорной системе реального времени с ограничениями по памяти, существовало допустимое расписание, необходимо и достаточно, чтобы была выполнена

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

г . . \

*(' "Л

5! X

(для любого А^ с N )

Еи ~ - °> ' = 1>-'" — 1; У = 1>-,т

(38)

(39)

(40)

(41)

м

V >(Е-Е')Т\

где V- вектор, образованный упорядоченными объемами памяти процессоров У„...,Ут, V — вектор, образованный упорядоченными объемами данных всех

работ у,,...,ул; = , то есть номер работы с минимальным

объемом данных, если рассматривать только работы из множества N. Матрица Е имеет размер пхт, ее элементы Ед е {0,1}. Размеры матрицы Е' совпадают с размерами матрицы Е, а каждый ее элемент получается из

соответствующего элемента матрицы Е следующим образом: £,'у = Е1} для _/ = 1 ,...,т\ если Е</ = 0, то Е'ч = 0 для / = 2,..-.,я,и j = l,...,m; если Е(/= 1 и

=0,то =0 для /' = 2,...,и и /=1,¿¿язА"Ец = 1 и =1,то Е[ =1 для/ = 2,...,и и у =1,...,т. ..

Отсюда для поиска допустимых решений нужно решить систему неравенств (38)-(40) относительно производительностей процессоров ($,,...,5Я) и всех элементов матрицы Е, а затем из (41) определить допустимые объемы памяти процессоров Ух,...,Ут. Решение же различных оптимизационных задач (например, минимизация суммы производительностей процессоров и суммарногоу объема памяти процессоров) в данном случае сводится к решению задачи целочисленного квадратичного программирования с булевскими переменными, для решения которой известно несколько алгоритмов на основе метода ветвей и границ. '

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

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

Основные результаты диссертационной работы заключаются в следующем:

1. Построен и исследован ряд' Математических моделей систем жесткого реального времени.

2. Для задачи построения допустимого расписания в системах жесткого реального времени разработаны два эвристических алгоритма, эффективно решающие эту задачу в случае отсутствия ограничений по памяти, полного графа связей между процессорами и отсутствии временных затрат на прерывания работ, а также их модификации для случая ненулевых затрЫ- на прерывания, найдены их вычислительные сложности 0(тп) и Ь{пг\о£п}.

Проведены численные эксперименты, показавшие высокую степень корректности их работы (80% и 98%), даны рекомендации по их практическому применению в случае различных моделей образования временных затрат.

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

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

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

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

Основные результаты исследований, проведенных в рамках диссертации, опубликованы в работах:

1. Гуз Д.С. Быстрые алгоритмы составления расписаний в многопроцессорных системах //Современные проблемы фундаментальных и прикладных наук. Часть VII. Прикладная математика и экономика: Труды XLV научной конференции. /Моск. физ. - техн. ин-т. - М. - Долгопрудный, 2002.-С. 56-57.

2. Гуз Д.С., Фуругян М.Г. Разработка и сравнительный анализ точных и приближенных алгоритмов составления расписаний с прерываниями в многопроцессорных системах // Моделирование обработки информации и процессов управления: Сб.ст./Моск.физ.-тех. ин-т. -М., 2002. - С. 296-306.

3. Гончар Д.Р., Гуз Д.С., Красовский Д.В., Фуругян М.Г. Эффективные алгоритмы планирования вычислений в многопроцессорных системах. // Проблемы управления безопасностью сложных систем: Труды 10-й международной конференции. Книга 2. /ИПУ РАН. - М., 2002 - С. 207-211.

4. Гуз Д.С., Красовский Д.В., Фуругян М.Г. Некоторые алгоритмы составления расписаний в многопроцессорных системах //Проблемы управления безопасностью сложных систем: Труды 11-й международной конференции. /ИПУ РАН. - М., 2003 - С. 12-14.

5. Гуз Д.С., Фуругян М.Г. Сведение задачи о поиске допустимого расписания в многопроцессорной системе реального времени к задаче о многопродуктовом потоке в сети // Моделирование и обработка информации: Сб.ст./Моск.физ.-тех. ин-т. - М., 2003. - С. 87-95.

6. Гуз Д.С., Фуругян М.Г. Возможность применения алгоритма поиска многопродуктового потока для составления расписаний в многопроцессорных системах жёсткого реального времени //Современные проблемы фундаментальных и прикладных наук. Часть VII. Прикладная

математика и экономика: Труды XLVT научной конференции. /Моск. физ. -техн. ин-т. - М. - Долгопрудный, 2003. - С. 65-66.

7. Гуз Д.С., Красовский Д.В., Фуругян М.Г. Эффективные алгоритмы планирования вычислений в многопроцессорных системах реального времени: Препринт / ВЦ РАН. - М., 2004. -65 с.

8. ГузД.С., Фуругян М.Г. Составление расписаний выполнения заданий и загрузки памяти для однопроцессорных систем жесткого реального времени // Моделирование процессов управления: Сб.ст./Моск.физ.-тех. ин-т. -М., 2004.-С. 162-169.

9. Гуз Д. С., Фуругян М.Г. Алгоритмы составления допустимых расписаний для системы жесткого реального времени с ограничениями по объему памяти //Проблемы управления безопасностью сложных систем: Труды 12-й международной конференции. /ИПУ РАН. - М., 2004 - С. 96-98.

10. Guz D., Krasovskiy D., FurugianM. Effective scheduling algorithms for multiprocessor real-time systems //Proceedings of IV Moscow International Conference on Operations Research. /ВЦ PAH. - M., 2004 - C. 100-103.

11. Гуз Д.С., Фуругян М.Г. Разработка эффективных алгоритмов планирования вычислений в системах жесткого реального времени с учетом ограничений по памяти //Современные проблемы фундаментальных и прикладных наук. Часть VII. Прикладная математика и экономика: Труды XLVII научной конференции. /Моск. физ. - техн. ин-т. - М. - Долгопрудный, 2004.-С. 96-98.

12. Гуз ДС., Фуругян М.Г. Планирование вычислений в многопроцессорных АСУ реального времени с ограничениями на память процессоров // Автоматика и телемеханика. - 2005. - №2 - С. 138-147.

13. Гуз Д.С., Фуругян М.Г. Эвристический алгоритм составления расписаний для многопроцессорных систем с ограничениями по объему памяти // Процессы и методы обработки информации: Сб.ст./Моск.физ.-тех. ин-т.-М., 2005.-С. 4-10.

ЛИЧНЫЙ ВКЛАД

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

>16940

РНБ Русский фонд

2006-4 11561

Гуз Денис Сергеевич

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

Подписано в печать 07.09.05 Формат 60x84 1/16. Бумага офсетная. Усл. печ. л. 1,0. Тираж 70 экз. Заказ № 427

Московский физико-технический институт (государственный университет) НИЧ МФТИ

141700, Московская обл., Долгопрудный, Институтский пер., 9

Введение.

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

Глава 1. Связи — полный граф. Отсутствие ограничений по памяти. Переключения без затрат.

1.1 Точный алгоритм.

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

1.2.1 Эвристика 1.

1.2.2 Эвристика 2.

1.3 Сравнительный анализ алгоритмов Эвристика 1 и Эвристика 2.

Глава 2. Переключения с затратами. Связи — полный граф. Отсутствие ограничений по памяти.

2.1 Алгоритм Эвристика П1.

2.2 Алгоритм Эвристика П2.

2.3 Сравнительный анализ алгоритмов Эвристика П1 и Эвристика П2.

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

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

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

Глава 3. Ограничения по памяти и скорости загрузки. Связи - полный граф. Общий директивный интервал.

3.1 Однопроцессорный случай.

3.1.1 Постановка задачи и предварительные соображения.

3.1.2 Построение оптимального порядка выполнения работ.

3.1.3 Алгоритм построения однопроцессорного расписания.

3.2 Многопроцессорный случай.

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

3.2.2 NP-трудность.

3.2.3 Эвристический алгоритм.

3.2.4 Анализ предложенного алгоритма.

Глава 4. Ограничения по памяти. Произвольный граф связей. Переключения с затратами. Время - дискретные такты.

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

4.2 Построение сети.

4.3 NP-трудность.

4.4 Необходимые и достаточные условия существования допустимого расписания.

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

Глава 5. Задача синтеза.

5.1 Отсутствие ограничений на память процессоров.

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

5.1.2 Построение области допустимых параметров процессоров.

5.2 Учет ограничений на память процессоров.

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

5.2.2 Построение области допустимых параметров процессоров.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Составление расписаний с прерываниями обычно применяется в системах, в которых невелико время переключения контекста. Примерами систем реального времени, в которых реализованы многопроцессорные расписания с прерываниями, могут служить RT-Mach [8] и LynxOS [9]. Большинство систем реального времени с возможностью прерывания работ используют диспетчеризацию с приоритетным управлением, как и большинство систем, рассмотренных и предложенных в данной работе. Поэтому остановимся подробнее именно на этом классе алгоритмов.

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

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

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

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

1. Для класса статических приоритетов они предложили семейство алгоритмов, названное RM (Rate-Monotonic, «алгоритм монотонных коэффициентов»). Основная идея этих алгоритмов состоит в том, что всем работам назначаются неизменные приоритеты, которые вычисляются по некой формуле 7 коэффициенту) исходя из известных характеристик работ. Например, в [10] такие коэффициенты обратно пропорциональны периоду возникновения работ, и доказано, что в однопроцессорном случае, когда директивный интервал для каждой работы равен периоду ее возникновения подобный RM-алгоритм поиска допустимого расписания является точным, а в [23] рассмотрен случай, когда директивный интервал может быть меньше, чем период возникновения и для такого случая предложен RM-алгоритм, коэффициенты приоритетов работ в котором обратно пропорциональны соответствующим дедл айнам.

2. Для класса динамических приоритетов было предложено семейство алгоритмов, названное EDF (earliest deadline first, «вначале - ближайший срок завершения»). Основная идея этих алгоритмов заключается в том, что самой приоритетной в каждый момент времени среди доступных в этот момент работ считается та работа, директивный срок окончания которой наступит раньше всех остальных. В [24] показано, что в однопроцессорном случае оптимальным с точки зрения минимизации общего времени выполнения работ будет являться то расписание, которое в каждый момент времени выполняет ту работу, директивный срок завершения выполнения которой наступит ранее остальных.

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

Щей двух классов алгоритмов, предложенных Лю и Лейландом в 1973 году, оказались очень жизнеспособными, и по сей день в этом отношении не было изобретено ничего принципиально нового, то есть все разработанные до настоящего времени алгоритмы являются лишь усовершенствованными и дополненными RM и EDF. Недавно, например, один из RM-алгоритмов был выбран для составления расписаний на выполнение множества независимых автоматических работ, возникающих на Международной Космической 8

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

Несмотря на то, что для однопроцессорной системы RM является оптимальным алгоритмом в случае периодически возникающих задач, a EDF - в апериодическом случае, ни один из них не является оптимальным в случае многопроцессорной системы. Более того, даже для однопроцессорных систем до сих пор не были решены задачи построения допустимых расписаний в случае, когда есть одновременно периодические и апериодические задачи (в данной работе рассматривается только чисто апериодический случай), а также случай построения синхронизованных расписаний ввода-вывода и вычислений (в Главе 3 настоящей работы впервые построен точный алгоритм для одного из частных случаев такой задачи). Изолированная задача распределения памяти при заданном расписании выполнения работ в однопроцессорной системе реального времени была изучена Сушковым и Логиновой в [17] и [49].

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

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

Решение задачи построения вычислительных систем выполняется, как правило, поэтапно. В соответствии с рассматриваемой детализацией аппаратных и программных средств вычислительной системы выделяется несколько уровней проектирования. Как правило, таких уровней три: абстрактный, системный и уровень регистровых передач [25, 26, 27, 28]. На абстрактном уровне рассматриваются ограничения на сроки выполнения прикладной программы и аппаратные ресурсы и анализируется возможность построения системы с учётом выполнения этих ограничений. На системном уровне определяются характеристики основных структурных ко мпонентов вычислительной системы, например, процессоров и устройств ввода-вывода. На уровне регистровых передач происходит проектирование системы с использованием конкретной элементной базы для дальнейшей непосредственной реализации системы. К задачам регистрового уровня построения вычислительных систем относятся, например, задачи автоматического проектирования микросхем, трассировки плат и размещения микросхем на плате.

К настоящему времени уже разработан ряд промышленных систем, автоматизирующих решение задачи синтеза вычислительных систем на уровне регистровых передач [29, 30, 31]. Однако методов, полностью автоматизирующих решение задачи построения структур вычислительных систем на системном и абстрактном уровне, на данный момент не известно. Указанные причины обуславливают актуальность задачи разработки методов, которые позволили бы автоматизировать и ускорить процесс синтеза структур вычислительных систем. В [18] приведены ограничения на необходимые и достаточные производительности процессоров системы жесткого реального времени в случае периодически возникающих работ и отсутствия ограничения по памяти процессоров, задача синтеза системы в этом случае свелась к задаче целочисленного линейного программирования, в [32], [33], [34] и [35] предложены генетические алгоритмы синтеза рассматриваемых систем.

Целями настоящей диссертационной работы являются:

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

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

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

Заключение.

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

В Главе 1 была рассмотрена задача поиска решений в многопроцессорной системе реального времени, в которой разрешены прерывания и переключения работ, переключения работ не требуют дополнительных затрат, связи между процессорами образуют полный граф, а ограничения по памяти отсутствуют. Для этого случая приведен известный точный полиномиальный алгоритм, который, однако, бывает затруднительно применять на практике в системах большой размерности из-за достаточно высокой степени полинома вычислительной сложности (0{тъпъj). Поэтому в данной главе были предложены два более быстрых эвристических алгоритма (0(тп) и При помощи значительного количества более 20000) численных экспериментов при различных значениях параметров задачи исследованы границы корректности применения предложенных эвристических алгоритмов, получена сравнительная статистическая информация относительно некорректной работы алгоритмов (второй алгоритм медленнее, чем первый, зато обеспечивает в среднем в несколько раз меньший процент некорректной работы - 3% против 20%), даны рекомендации по их практическому применению.

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

В Главе 3 рассмотрен ранее неисследованный вариант задачи о поиске допустимого расписания в многопроцессорной системе с ограничениями по памяти процессоров и конечной скоростью ввода-вывода данных, в котором процессоры, помимо скорости выполнения работ, характеризуются скоростью загрузки данных. Рассмотрен случай одинаковых директивных интервалов для всех работ. Для однопроцессорного случая построен точный алгоритм, решающий задачу за полиномиальное время 0{n2\ogn} и теоретически обоснована его корректность. Далее рассмотрен многопроцессорный случай этой задачи, доказана ее NP-трудность как в случае когда переключения работ с процессора на процессор разрешены, так и в случае когда они не допускаются. Поэтому для ее практического решения был разработан эвристический алгоритм вычислительной сложности 0{n2m\ogri), котрый, как показали проведенные численные эксперименты, эффективно решает задачу, в случае, когда максимальные длительности выполнения работ и загрузки данных существенно меньше, чем длина общего директивного интервала всех работ. Представлено теоретическое объяснение этого полученного эмпирически свойства алгоритма, даны рекомендации по его практическому применению. Для выявления случаев некорректной работы эвристического алгоритма для рассмотренной в данной главе задачи был также построен точный алгоритм и дано теоретическое обоснование его корректности.

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

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

Наиболее перспективным представляется развитие предложенных в данной работе методов и подходов по следующим направлениям:

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

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

1. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука, 1984.

2. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. — М.: Радио и Связь, 1983.

3. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. М.: Радио и связь, 1990.

4. С. Martel Preemptive scheduling with release times, deadlines and due times // Journal of the ACM. 1982. V. 29, №3. P. 812-829.

5. K. Ramamritham andJ. A. Stankovic, Scheduling Algorithms and Operating Systems Support for Real-Time Systems, Proceedings of the IEEE, 82(1): 55-67, Jan 1994.

6. A. Burns, Scheduling Hard Real-Time Systems: A Review, Software Engineering Journal, 6(3): 116-128, May 1991.

7. J.A. Stankovic, et. al., Implications of Classical Scheduling Results for RealTime Systems, IEEE Computer Society Press, 1995.

8. H. Tokuda, T. Nakajima and P. Rao, Real-Time Mach: Toward a Predictable Real-Time System, Proceedings of USENOX Mach Workshop, Oct 1990.

9. Lynx Programmer's Reference Manual, Version 2.4, Lynx Real-Time Systems, San Jose, CA, 1996.

10. C.L. Liu and J. W. Layland, Scheduling Algorithms for Multiprogramming in Hard Real-Time Environment, Journal of the ACM, 20(1): 46-61, Jan 1973.

11. A. Federgruen, H. Groenevelt. "Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Technique". Management Science Vol. 32, No. 3, March 1986.

12. T. Gonzales, S. Sanhi. "Preemptive Scheduling of Uniform Processor Systems". Journal of the Association for Computing Machinery, Vol. 25, No. 1, January 1978.

13. Т. Кормен, Ч. Лейзерсон, P. Pueecm. «Алгоритмы: построение и анализ» М. МЦНМО, 1999.

14. Э.Г. Коффман. Введение в детерминированную теорию расписаний. В кн.: Теория расписаний и вычислительные машины / Под ред. Коффмана Э.Г. М. Наука, 1984, с. 9-64.

15. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.

16. P.M. Vaidya. Speeding up linear programming using fast matrix multiplication. In "Proceedings of the 30th Annual Symposium on Foundations of Computer Science", pages 332-337, 1989.

17. Логинова И.В., Сушков Б.Г. Динамическое распределение памяти в системах реального времени при имеющемся расписании центрального процессора // В сборнике «Теория и реализация систем реального времени», ВЦ АН СССР, стр. 49-69,1984.

18. Фуругян М.Г. Некоторые алгоритмы анализа детерминированных систем реального времени. М. ВЦ РАН 1989.

19. Е.С. Horvath, S. Lam, R. Sethi. A level algorithm for preemptive scheduling. J. ACM 24 (Jan 1977), 32-43.

20. Киселев В.Д., Карелин Д.В. Метод ветвей и границ для решения задач целочисленного квадратичного программирования с булевыми переменными // Известия Тульского Государственного Университета, 1995, Том 1, выпуск 3, Информатика.

21. A.KMok Fundamental Design Problems of Distributed Systems for the Hard Real-Time Environment, Ph.D Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1983.

22. N.Audsley, A.Burns, M.Richardson and A.Wellings Hard Real-Time Scheduling: The Deadline Monotonic Approach, IEEE Workshop on RealTime Operating Systems, 1992.

23. M.L.Dertouzos Control Robotics: The Procedural Control of Physical Processes, Information Processing 74, North-Holland Publishing Company, 1974.

24. Hessel F., Coste P., Nicolescu G., LeMarrec P., Zergainoh TV., Jerraya A. A. Communication Synthesis of Multilanguage Specification // Research Report, TIMA Laboratory, ISRN TIMA-RR-00/06-1-FR, ISSN 1292-8062.

25. Baghdady A., Zergainoh N-E., Cesario W., Roudier Т., Jerraya A. Design Space Exploration for Hardware/Software Codesign of Multiprocessor Architectures // Research Report, TIMA Laboratory, ISRN TIMA-RR-00/02-4-FR, ISSN 1292-8062.

26. Сверхбольше интегральные схемы и современная обработка сигналов // Под ред. Гуна С., Уайтхауза X., Кайлата Т., М.: Радио и связь, 1989.

27. Майоров С.А., Новиков Г.И. Принципы организации цифровых машин -Л.: Машиностроение, 1974.

28. Valderrama С. et al. Hardware and Software Co-design : Principles and Practice KLUWER. Chap. COSMOS : A Transformational Codesign Tool for Multiprocessor Architectures, 1997, p. 307-357.

29. Ernst R., Henkel J., Benner Th., Trawny M. The COSYMA Environment for Hardware/Software Cosynthesis, Journal of Microprocessors and Microsystems, Butterworth-Heinemann, 1995.

30. Ben-Ismail Т., O'Brien K., Jerraya A. PAR-TIF: Interactive System-level Partitioning, VLSI Design Vol. 3 №3-4, pp. 333-345, 1995.

31. Костенко B.A., Трекин А.Г. Генетические алгоритмы решения смешанных задач целочисленной и комбинаторной оптимизации при синтезе архитектур ВС // Искусственный интеллект (Донецк), 2000, №2, С.90-96.

32. Костенко В.А., Смелянский Р.Л., Трекин А.Г. Синтез структур вычислительных систем реального времени с использованием генетических алгоритмов// Программирование, 2000, №5.

33. Трекин А.Г. Структурный синтез вычислительных систем с помощью генетических алгоритмов // диссертация на соискание ученой степени кадидата физ.-мат. наук, М., 2002.

34. Гуз Д.С., Красовский Д.В., Фуругян М.Г. Некоторые алгоритмы составления расписаний в многопроцессорных системах //Проблемы управления безопасностью сложных систем: Труды 11-й международной конференции. /ИПУ РАН. М., 2003 - С. 12-14.

35. Гуз Д.С., Фуругян М.Г. Сведение задачи о поиске допустимого расписания в многопроцессорной системе реального времени к задаче о многопродуктовом потоке в сети // Моделирование и обработка информации: Сб.ст./Моск.физ.-тех. ин-т. М., 2003. — С. 87-95.

36. Гуз Д.С., Красовский Д.В., Фуругян М.Г. Эффективные алгоритмы планирования вычислений в многопроцессорных системах реального времени: Препринт / ВЦ РАН. М., 2004. -65 с.

37. Гуз Д.С., Фуругян М.Г. Составление расписаний выполнения заданий и загрузки памяти для однопроцессорных систем жесткого реальноговремени // Моделирование процессов управления: Сб.ст./Моск.физ.-тех. ин-т. М, 2004. - С. 162-169.

38. Guz D., Krasovskiy D., Furugian M. Effective scheduling algorithms for multiprocessor real-time systems //Proceedings of IV Moscow International Conference on Operations Research. /ВЦ PAH. M., 2004 - C. 100-103.

39. Гуз Д. С., Фуругян М.Г. Планирование вычислений в многопроцессорных АСУ реального времени с ограничениями на память процессоров // Автоматика и телемеханика. 2005. — №2 — С. 138-147.

40. Гуз Д. С., Фуругян М.Г. Эвристический алгоритм составления расписаний для многопроцессорных систем с ограничениями по объему памяти // Процессы и методы обработки информации: Сб.ст./Моск.физ.-тех. ин-т. М., 2005. - С. 4-10.

41. Логинова И. В. Алгоритмы динамического распределения памяти в системах реального времени // автореферат диссертации на соискание ученой степени кандидата физико-математических наук М., 1985.