Алгоритмы планирования вычислений и организации рестартов в системах реального времени тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Гречук, Богдан Васильевич

• Гречук, Богдан Васильевич
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Гречук, Богдан Васильевич

Введение.

Глава 1. Исследование задачи планирования вычислений в многопроцессорных системах с неполным графом связей.

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

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

1.3. ЫР-трудность некоторых задач.

1.3.1. Задача с издержками на переключения.

1.3.2. Задача с издержками на прерывания на одном процессоре.

1.3.3. Случай неидентичных процессоров. ф 1.3.4. Случай произвольного графа связей.

1.3.5. Случай двух отдельных полных компонент.

1.4. Формулировка основной задачи. Некоторые упрощения.

1.5. Алгоритм решения основной задачи.

1.5.1. Задача преобразования расписания.

1.5.2. Задача преобразования таблицы.

1.5.3. Полиномиальное сведение.

1.5.4. Масштабирование.

1.6. ИР-трудностъ основной задачи в общем случае.

1.7. Учет издержек на прерывания и переключения.

1.7.1.1чПР-трудность.

1.7.2. Случай полного графа связей.

1.7.3. Метод последовательных приближений.

1.7.4.0бщий случай. ф 1.8. Специальная задача с учетом некоторых переключений.

1.8.1. Формулировка задачи.

1.8.2. Эквивалентная задача.

1.8.3. Сведение к задаче булевого линейного программирования.

1.8.4. Сведение к задаче целочисленного линейного программирования.

Глава 2. Алгоритмы организации рестартов в системах реального времени.

2.1. Формулировка задачи.

2.2. Простейший случай.

2.2.1. Упрощающие предположения.

2.2.2. Предварительные результаты.

2.2.3. Одинаковое число модулей-буферов и модулей контроля. ф 2.2.4. Один модуль-буфер.

2.2.5. Два модуля-буфера.

2.2.6. Произвольное число модулей-буферов.

2.3. Случай нескольких параллельных цепочек рабочих модулей.

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

2.3.2. Разделение модулей контроля по одинаковым цепочкам.

2.3.3. Разделение модулей контроля по цепочкам при заданном разделении модулей-буферов.

2.3.4. Приближенный алгоритм расстановки модулей.

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

2.4. Расположение модулей контроля для случая ориентированного дерева.

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

2.4.2. Связь расстановок модулей контроля в дереве и в цепочке.

2.4.3. Алгоритм для построения оптимальной расстановке модулей контроля в дереве.

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

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

2.5.2. КР-трудность в сильном смысле задачи расстановки модулей контроля для случая произвольного графа.

2.5.3. Применение метода "ветвей и границ".

2.5.4. Альтернативная стратегия при обнаружении ошибки.

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

• 2.6.1. Вычисление математического ожидания.

2.6.2. Оптимальное расположение модулей контроля для случая цепочки.

2.6.3. Случай равных паралельных цепочек.

2.6.4. Случай произвольных паралельных цепочек.

Введение диссертации (часть автореферата) на тему «Алгоритмы планирования вычислений и организации рестартов в системах реального времени»

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

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

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

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

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

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

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

Работы [4-11] посвящены разработке алгоритмов планирования вычислений в многопроцессорных системах реального времени.

Основополагающими работами теории составления расписаний в многопроцессорных системах являются работы [4], [5], [6]. В [4] разработан полиномиальный алгоритм для построения оптимального 6 расписания в многопроцессорной системе, состоящей из идентичных процессоров, при произвольных директивных интервалах. В [7] предполагается, что процессоры могут иметь различную производительность, но директивные интервалы всех работ одинаковые. В [6], [8] рассматривается система с процессорами различной производительности и произвольными директивными интервалами. Для этого случая также получены полиномиальные алгоритмы для построения оптимального расписания. В [9] разработаны алгоритмы построения расписаний, основаны на назначении работам статистических приоритетов. В [10] предполагается, что требования на выполнения работ поступают периодически, а в [11] требования могут поступать как периодически, так и не периодически; директивные интервалы произвольные. Хорошим руководством по современному состоянию теории расписаний может служить книга [12].

Как отмечалось выше, во всех указанных публикациях предполагается, что граф связей между процессорами полный, т.е. все процессоры соединены между собой и работы могут непосредственно переключаться с любого процессора на любой другой. В работах [13], [14], [15] рассматривается многопроцессорная система с неполным графом связей между процессорами, работа которых рассматривается как набор дискретных последовательных тактов, синхронизированных во времени. Для построения расписания в этом случае получены эвристические алгоритмы, основанные на построении многопродуктовой потоковой сети специального вида. В [16] доказано, что в общем случае эта задача является ИР-трудной [17].

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

Заметим, что в отличие от работ [14], [15], в настоящей работе не предполагается наличие ограничений по памяти процессоров, что позволило разработать для решения поставленной задачи точный полиномиальный алгоритм.

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

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

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

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

Задача оптимального расположения модулей-буферов при различных условиях была широко исследована в работах [18-29]. В работах [18], [19] предполагалось, что модули-буферы надо расставлять равномерно, и получена оптимальная частота их расположения. В работе [18] вероятность возникновения сбоя или ошибки предполагалась малой, а в работе [19] величина оптимального интервала между последовательными модулями-буферами была найдена приближенно. Точная формула для длины оптимального интервала была получена в работах [20], [21]. В работе [22] рассматривается неравномерное расположение модулей-буферов для случая, когда вероятность возникновения ошибки не является постоянной. В работах [23], [24] получен алгоритм для расположения модулей-буферов в предположении, что вероятность ошибки в одном и том же месте системы может изменяться после перезапуска. В работе [25] предлагается эвристическая расстановка модулей-буферов, основанная на увеличении интервала между последовательными модулями-буферами, если некоторое время не было ошибки. В работе [26] получена расстановка модулей-буферов в предположении, что вероятность возникновения ошибки не является постоянной, а также ошибка может возникать во время записи данных в буфер. В работе [27] был применен метод стохастического динамического программирования для вычисления оптимального расположения модулей-буферов между задачами заданной длины. В [28] рассмотрена многопроцессорная система и получено расположение модулей-буферов, при котором вероятность выполнить работу до выхода из строя всех процессоров максимальна. В [29] получен алгоритм динамической расстановки модулей-буферов во время работы системы, в зависимости от изменения обстоятельств.

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

Во-вторых, в работах [18-29] предполагается, что задания выполняются последовательно в строго оговоренном заранее порядке. На практике, однако, некоторые задания являются независимыми по данным, и при выполнении мы можем менять их местами. В общем случае все задания могут быть связаны произвольным графом зависимости по данным. Такая модель организации рестартов в системах реального времени была рассмотрена Белым Д.В. и Сушковым Б.Г. в [31]. В этой работе вычислительная система реального времени рассматривается как граф, вершинами которого являются рабочие модули (которые и выполняют задания), модули контроля и модули-буферы. Также в [31] строится зона рестарта - минимальная область программы, подлежащая перезапуску после обнаружения ошибки некоторым модулем контроля. Именно эта модель Белого Д.В. и Сушкова Б.Г. взята за основу в настоящей работе.

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

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

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

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

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

Научная новизна данной работы состоит в том, что

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

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

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

Результаты диссертации опубликованы в работах [32-40], докладывались на ХЬУ научной конференции МФТИ, на 4-й Московской И международной конференции по исследованию операций, на 12-й международной конференции "Проблемы управления безопасностью сложных систем", на научных семинарах кафедры математических основ управления МФТИ и сектора проектирования систем реального времени ВЦ РАН.

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Гречук, Богдан Васильевич

Заключение

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Гречук, Богдан Васильевич, 2006 год

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

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

3. Baruah S., Howell R.R., Rosier L.E. Algorithms and Complexity Concerning the Preemptive Scheduling of Periodic, Real-Time Tasks on One Processor // Real-time systems, 2, 1990. C. 301-324.

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

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

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

7. Gonzales Т., Sahni S. Preemptive Scheduling of Uniform Processor Systems // Journal of the Association for Computing Machinery. 1978 - V. 25, N 1. - P. 92-101.

8. Federgruen A., Groenevelt H. Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Technique // Management Science. 1986 - V.32, N 3. - P. 341-349.

9. Audsley N., Burns A., Richardson M., Tindell K., Wellings A.J. Applying # New Scheduling Theory to Static Priority Preemptive Scheduling //

10. Software Eng. 1993 - V.8, N 5. - P. 284-292.

11. Marco Spurt Analysis of Deadline Scheduled Real-Time Systems // Technical Report No. 2772, INDIA, 1996.

12. Banus J.M., Arenas A., Labarta J. Dual Priority Algorithm to Schedule Real-Time Tasks in a Shared Memory Multiprocessor // Workshop on Parallel and Distributed Rael-Time Systems, 2003.

13. Brucker P. Scheduling Algorithms Springer, 3rd ed. New York, 2001 -377 p.

14. Фуругян М.Г. Некоторые алгоритмы распределения ресурсов в ф многопроцессорных системах реального времени: Препринт / ВЦ1. РАН. М., 1996.-24 с.

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

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

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

18. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. // М.: Мир, 1982. 416 с.

19. Chandy К. A survey of analytic models of roll-back and recovery strategies. // Computer 1975 - V.8, N 5. - P.40-47.

20. Young J. W. A first-order approximation to the optimum checkpoint * interval. // Comm. ACM 1974 - V.17, N 9. - P. 530-531.

21. Gelembe E. On the Optimum Checkpoint Interval I I J. ACM 1979 - V. 26 - P. 259-270.

22. Duda A. The Effects of Checkpointing on Program Execution Time. // Information Processing Letters. 1983 - V. 16, N 5. - P. 221-229.

23. Grassi V., Donatiello L., Tucci S., On the Optimal Checkpointing of Critical Tasks and Transaction-Oriented Systems. // IEEE Trans. Software Eng. 1992 - V. 18, N 1. - P. 72-77.

24. Leung C., Choo Q. On the Execution of Large Batch Programs in Unreliable Computing Systems // IEEE Trans. Software Eng. 1984 -V.10,N4.-P. 444-450.

25. Coffman E., Gilbert E. Optimal Strategies for Scheduling Checkpoints and Preventive Maintenance // IEEE Trans. Reliability 1990 - V.39, N 1 -P. 9-18.

26. Benczur A, Kramlin A. An example for an adaptive control method providing database integrity. // In Proceedings of the Fourth International Symposium on Modeling and Performance Evaluation of Computer Systems 1979 -P. 249-262.

27. Tantawi A., Ruschitzka M. Performance Analysis of Checkpointing Strategies. // ACM Trans. Computer Systems-1984-V.2,N 2- P. 123-144.

28. Toueg S., Babaoglu O., On the Optimum Checkpoint Selection Problem I I SIAM J. Computing 1984 - V. 13, N 3. - P. 630-649.

29. Bruno J.L., Coffman E.G., Optimal Fault-Tolerant Computing on Multiprocessor Systems // Acta Informatica 1997 - V.34 - P. 881-904.

30. Ecuyer P., Malenfant J. Computing optimal checkpointing strategies for rollback and recovery systems // IEEE Trans. Computers 1988 - V.37, N4.-P. 491-496.

31. Луганская М.И., Сушков Б.Г. Контроль данных в системах реального времени. // Математические методы управления обработкой информации. М.: МФТИ, 1986. С. 18 24.

32. Белый Д.В., Сушков Б.Г. Модель организации рестартов в системах реального времени: Препринт / ВЦ РАН. М., 1996. - 32 с.

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

34. Гречук Б. В., Фуругян М. Г. Составление оптимальных расписаний с прерываниями в многопроцессорных системах с неполным графом связей. // Кибернетика и системный анализ, 3, 2005, С. 94-102.

35. Гречук Б.В., Фуругян М.Г. Алгоритмы организации рестартов в системах реального времени: Препринт / ВЦ РАН. М., 2004. - 32 с.

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

37. Гречук Б.В., Фуругян М.Г. Планирование вычислений в многопроцессорных системах с неполным графом связей // Моделирование процессов управления: Сб.ст./Моск.физ.-тех. ин-т. -М., 2004.-С. 155-161.

38. В. V. Grechuk, M. G. Fourougian Optimal Scheduling of Incomplete Communication Graph Multiprocessor Systems. // Труды 4-й Московской международной конференции по исследованию операций, Москва, 2004. С. 98-100.

39. Гречук Б.В., Фуругян М.Г. Алгоритмы организации рестартов в системах реального времени. // Материалы 12-й международной конференции "Проблемы управления безопасностью сложных систем", Москва, 2004. С. 234-237.

40. Гречук Б.В. Эффективные алгоритмы для приближенного решения задачи о кратчайшем пути с ограничением по весу // Компьютерная математика, 1,2006-С. 140-151.

41. ALON, N. A simple algorithm for edge-coloring bipartite multigraphs. Inf. Proc. Lett. Computers 2003 - V.85, N 6. - P. 301-302.

42. Кормен Т., Лейзерсон 4., Pueecm Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2001 960 с.