Содержание к диссертации
Введение
Глава 1. Исследование задачи планирования вычислений в многопроцессорных системах с неполным графом связей 13
1.1. Постановка задачи 13
1.2. Потоковый алгоритм для случая полного графа связей 15
1.3. NP'-трудность некоторых задач 16
1.3.1. Задача с издержками на переключения 16
1.3.2. Задача с издержками на прерывания на одном процессоре 17
1.3.3. Случай неидентичных процессоров 17
1.3.4. Случай произвольного графа связей 19
1.3.5. Случай двух отдельных полных компонент 19
1.4. Формулировка основной задачи. Некоторые упрощения 22
1.5. Алгоритм решения основной задачи 27
1.5.1. Задача преобразования расписания 27
1.5.2. Задача преобразования таблицы 28
1.5.3. Полиномиальное сведение 29
1.5.4. Масштабирование 35
1.6. NP-трудность основной задачи в общем случае 40
1.7. Учет издержек на прерывания и переключения 47
1.7.1. NP-трудность 47
1.7.2. Случай полного графа связей 48
1.7.3. Метод последовательных приближений 48
1.7.4.Общий случай 49
1.8. Специальная задача с учетом некоторых переключений 50
1.8.1. Формулировка задачи 50
1.8.2. Эквивалентная задача 52
1.8.3. Сведение к задаче булевого линейного программирования ...58
1.8.4. Сведение к задаче целочисленного линейного программирования 62
Глава 2. Алгоритмы организации рестартов в системах реального времени 64
2.1. Формулировка задачи 64
2.2. Простейший случай 67
2.2.1. Упрощающие предположения 67
2.2.2. Предварительные результаты 68
2.2.3. Одинаковое число модулей-буферов и модулей контроля 73
2.2.4. Один модуль-буфер 75
2.2.5. Два модуля-буфера 77
2.2.6. Произвольное число модулей-буферов 81
2.3. Случай нескольких параллельных цепочек рабочих модулей 87
2.3.1. Постановка задачи 87
2.3.2. Разделение модулей контроля по одинаковым цепочкам 89
2.3.3. Разделение модулей контроля по цепочкам при заданном разделении модулей-буферов 93
2.3.4. Приближенный алгоритм расстановки модулей 95
2.3.5. Точный алгоритм расстановки модулей контроля и модулей-буферов в случае нескольких параллельных цепочек 99
2.4. Расположение модулей контроля для случая ориентированного дерева 102
2.4.1. Постановка задачи 102
2.4.2. Связь расстановок модулей контроля в дереве и в цепочке 105
2.4.3. Алгоритм для построения оптимальной расстановке модулей контроля в дереве 106
2.5. Расположение модулей контроля для случая произвольного графа связей между рабочими модулями 110
2.5.1. Порядок выполнения рабочих модулей при заданном расположении модулей контроля 110
2.5.2. NP-трудность в сильном смысле задачи расстановки модулей контроля для случая произвольного графа 114
2.5.3. Применение метода "ветвей и границ" 117
2.5.4. Альтернативная стратегия при обнаружении ошибки 121
2.6. Расстановка модулей контроля для случая произвольной вероятности ошибки 123
2.6.1. Вычисление математического ожидания 124
2.6.2. Оптимальное расположение модулей контроля для случая цепочки 126
2.6.3. Случай равных паралельных цепочек 130
2.6.4. Случай произвольных паралельных цепочек 134
Заключение 135
Список использованных источников 137
- Задача с издержками на прерывания на одном процессоре
- Сведение к задаче булевого линейного программирования
- Разделение модулей контроля по цепочкам при заданном разделении модулей-буферов
- Порядок выполнения рабочих модулей при заданном расположении модулей контроля
Введение к работе
Вычислительные системы реального времени широко применяются при проектировании и сопровождении сложных технических объектов (самолеты, ракеты, системы космической обороны, конвейеры), транспортных систем, систем экономического и экологического мониторинга, в других областях человеческой деятельности. Одним из наиболее важных классов этих систем являются системы жесткого реального времени, в которых задания должны быть выполнены в заранее заданные директивные сроки.
Например, современный космический аппарат является системой жесткого реального времени, так как большинство его систем управления полностью автоматизированы. Практически все задачи, которые должны быть выполнены бортовыми системами аппарата во время полета, имеют жесткий директивный срок, который не может быть нарушен.
Для своевременного определения неполадок в механических системах (от реактивных турбин до автомобильных рессор) необходимо отслеживать их динамические характеристики, такие как вибрация, шум, удары. Эта задача требует больших вычислительных ресурсов для обработки данных, а нарушение срока ее выполнения может привести к поломке механической системы.
Для нормального функционирования железной дороги необходимо хорошо продуманное расписание движения поездов, учитывающее максимально допустимую загруженность путей и железнодорожных вокзалов. Данное расписание должно не только обеспечивать своевременную доставку пассажиров и груза, но и быть гибким на случай всевозможных нештатных ситуаций. В этом смысле железная дорога также может рассматриваться как система жесткого реального времени.
Для функционирования систем жесткого реального времени необходимо иметь заранее составленное расписание их работы. Для обеспечения надежной работы систем реального времени большое значение имеет также подсистема организации рестартов, позволяющая в случае возникновения сбоев определить те программные модули, которые подлежат повторному запуску. В данной работе рассматривается задача
составления оптимальных расписаний и оптимизации структуры подсистемы контроля в вычислительных системах реального времени.
Алгоритмы решения задачи составления оптимальных расписаний для многопроцессорных систем находят широкое практическое применение. С ростом информационных потоков и появлением новой многопроцессорной вычислительной техники актуальность этих задач еще более возрастает, а также появляются новые задачи, какой является задача составления допустимых расписаний в многопроцессорных системах с неполным графом связей между процессорами. В большинстве рассмотренных ранее постановок задач составления допустимых расписаний с прерываниями предполагалось, что либо имеется один процессор, либо процессоров несколько, но граф связей между ними полный. Однако в реальных системах такие упрощения часто бывают неприемлемыми. В качестве примеров можно привести многопроцессорные системы, в которых связи образуют гиперкуб, системы с шинной связью, транспьютерные системы, в которых связи между процессорами могут изменяться во времени (при определенных ограничениях) и многие другие.
Остановимся на наиболее интересных публикациях по составлению расписаний с прерываниями. Одной из первых работ в данной области, в которой сформулированы основные положения, подходы и идеи теории расписаний, можно назвать работу Лю и Лейланда [1]. В ней авторы рассмотрели однопроцессорную систему, в которой требования на выполнение работ поступают циклически с заданными периодами. Предложенные ими алгоритмы основаны на назначении работам статических и динамических приоритетов. Дальнейшая разработка алгоритмов построения оптимальных расписаний для однопроцессорной системы была проведена, например, в [2], [3].
Работы [4-11] посвящены разработке алгоритмов планирования
вычислений в многопроцессорных системах реального времени.
Основополагающими работами теории составления расписаний в
многопроцессорных системах являются работы [4], [5], [6]. В [4]
разработан полиномиальный алгоритм для построения оптимального
расписания в многопроцессорной системе, состоящей из идентичных процессоров, при произвольных директивных интервалах. В [7] предполагается, что процессоры могут иметь различную производительность, но директивные интервалы всех работ одинаковые. В [6], [8] рассматривается система с процессорами различной производительности и произвольными директивными интервалами. Для этого случая также получены полиномиальные алгоритмы для построения оптимального расписания. В [9] разработаны алгоритмы построения расписаний, основаны на назначении работам статистических приоритетов. В [10] предполагается, что требования на выполнения работ поступают периодически, а в [11] требования могут поступать как периодически, так и не периодически; директивные интервалы произвольные. Хорошим руководством по современному состоянию теории расписаний может служить книга [12].
Как отмечалось выше, во всех указанных публикациях предполагается, что граф связей между процессорами полный, т.е. все процессоры соединены между собой и работы могут непосредственно переключаться с любого процессора на любой другой. В работах [13], [14], [15] рассматривается многопроцессорная система с неполным графом связей между процессорами, работа которых рассматривается как набор дискретных последовательных тактов, синхронизированных во времени. Для построения расписания в этом случае получены эвристические алгоритмы, основанные на построении многопродуктовой потоковой сети специального вида. В [16] доказано, что в общем случае эта задача является NP-трудной [17].
В настоящей работе продолжается исследование многопроцессорной
системы с неполным графом связей. В частности, разработан
полиномиальный алгоритм для случая, когда задержки на прерывания и
переключения не учитываются, а граф связей между процессорами -
произвольный связный граф. Строго говоря, задача решена для случая,
когда наибольший общий делитель левых и правых границ директивных
интервалов и длительностей всех работ не меньше удвоенного числа
процессоров. Отметим, однако, что произвольная задача сводится к этой
соответствующим выбором величины временного такта. Доказано, что если это условие не выполнено, то задача является NP-трудной даже при связном графе связей.
Заметим, что в отличие от работ [14], [15], в настоящей работе не предполагается наличие ограничений по памяти процессоров, что позволило разработать для решения поставленной задачи точный полиномиальный алгоритм.
При построении вышеуказанного алгоритма предполагается, что временные издержки при прерывании выполнения работ и их переключениях с одного процессора на другой не учитываются. В работах [13], [14], [15] предлагается учесть эти издержки. В настоящей работе для этого случая построены некоторые новые эвристические алгоритмы.
Частный случай указанной задачи с учетом издержек на переключения сведен к задаче поиска многопродуктового потока, удовлетворяющего некоторым дополнительным ограничениям, в сети специального вида. В отличие от [14], [15] где рассматривался общий случай, общее число вершин и дуг в данной сети ограничено полиномом от количества работ и процессоров (но не от количества тактов). Задача поиска многопродуктового потока, в свою очередь, сведена к задаче булевого линейного программирования. Также указанный частный случай исходной задачи сведен к задаче целочисленного линейного программирования с существенно меньшим числом переменных и ограничений.
При планировании вычислений в системах реального времени важно
учитывать возможность несистематического возникновения программных
сбоев и ошибок. Если система не защищена от программных сбоев, то при
их возникновении все вычисления необходимо каждый раз повторять
заново, что часто требует больших затрат времени и ресурсов.
Стандартным способом защиты от сбоев и ошибок является введение в
систему дополнительных модулей-буферов, которые сохраняют
промежуточную информацию о состоянии системы. Эти модули
используются для того, чтобы при рестарте системы воспользоваться
сохраненными данными из этих буферов, а не проводить все вычисления
заново. Таким образом, наличие модулей-буферов может существенно улучшить надежность системы и уменьшить временные задержки, вызванные несистематическими сбоями и ошибками. С другой стороны, избыточное использование модулей-буферов может привести к существенному уменьшению быстродействия и увеличению стоимости системы. Следовательно, возникает задача оптимальной частоты расположения модулей-буферов.
Задача оптимального расположения модулей-буферов при различных условиях была широко исследована в работах [18-29]. В работах [18], [19] предполагалось, что модули-буферы надо расставлять равномерно, и получена оптимальная частота их расположения. В работе [18] вероятность возникновения сбоя или ошибки предполагалась малой, а в работе [19] величина оптимального интервала между последовательными модулями-буферами была найдена приближенно. Точная формула для длины оптимального интервала была получена в работах [20], [21]. В работе [22] рассматривается неравномерное расположение модулей-буферов для случая, когда вероятность возникновения ошибки не является постоянной. В работах [23], [24] получен алгоритм для расположения модулей-буферов в предположении, что вероятность ошибки в одном и том же месте системы может изменяться после перезапуска. В работе [25] предлагается эвристическая расстановка модулей-буферов, основанная на увеличении интервала между последовательными модулями-буферами, если некоторое время не было ошибки. В работе [26] получена расстановка модулей-буферов в предположении, что вероятность возникновения ошибки не является постоянной, а также ошибка может возникать во время записи данных в буфер. В работе [27] был применен метод стохастического динамического программирования для вычисления оптимального расположения модулей-буферов между задачами заданной длины. В [28] рассмотрена многопроцессорная система и получено расположение модулей-буферов, при котором вероятность выполнить работу до выхода из строя всех процессоров максимальна. В [29] получен алгоритм динамической расстановки модулей-буферов во время работы системы, в зависимости от изменения обстоятельств.
Во всех этих работах, однако, сделано два упрощающих предположения, которые не всегда имеют место на практике. Во-первых, предполагается, что при возникновении ошибки мы сразу же можем ее обнаружить и выполнить перезапуск системы. На практике, однако, часто возникают также ошибки при вычислениях, которые невозможно обнаружить сразу. В этом случае контроль системы осуществляется специальными модулями контроля, каждый из которых определяет, принадлежит ли множество значений контролируемых им параметров заданным пределам. При этом перезапуск системы происходит не сразу при возникновении ошибки, а только после ее обнаружения некоторым модулем контроля. Подсистема контроля данных подробно рассмотрена в [30].
Во-вторых, в работах [18-29] предполагается, что задания выполняются последовательно в строго оговоренном заранее порядке. На практике, однако, некоторые задания являются независимыми по данным, и при выполнении мы можем менять их местами. В общем случае все задания могут быть связаны произвольным графом зависимости по данным. Такая модель организации рестартов в системах реального времени была рассмотрена Белым Д.В. и Сушковым Б.Г. в [31]. В этой работе вычислительная система реального времени рассматривается как граф, вершинами которого являются рабочие модули (которые и выполняют задания), модули контроля и модули-буферы. Также в [31] строится зона рестарта - минимальная область программы, подлежащая перезапуску после обнаружения ошибки некоторым модулем контроля. Именно эта модель Белого Д.В. и Сушкова Б.Г. взята за основу в настоящей работе.
В [31], однако, предполагается что модули контроля и модули-буферы уже расставлены некоторым образом. В настоящей работе рассматривается задача оптимальной расстановки модулей контроля и модулей-буферов в заданном графе, вершинами которого являются рабочие модули. Рассмотрены случаи, когда граф зависимости по данным является цепочкой (последовательное выполнение работ), когда он состоит из нескольких параллельных цепочек, когда он является ориентированным
деревом, а также случай произвольного графа. Во всех случаях, кроме
последнего, разработаны алгоритмы для оптимальной расстановки модулей контроля и модулей-буферов. В последнем случае доказано, что задача оптимальной расстановки модулей контроля является NP-трудной.
Целями настоящей диссертационной работы являются:
разработка эффективных алгоритмов составления оптимальных расписаний в многопроцессорных системах реального времени с неполным графом связей.
разработка эффективных алгоритмов построения оптимальной расстановки модулей контроля и модулей-буферов в вычислительных системах реального времени с различными графами зависимости по данным.
Научная новизна данной работы состоит в том, что
при составлении оптимальных расписаний в многопроцессорных системах реального времени рассмотрен малоисследованный случай, когда граф связей между процессорами не является полным. Для случая связного графа связей (при некоторых дополнительных предположениях) построен точный полиномиальный алгоритм. Для некоторых ранее не рассмотренных случаев доказана NP-трудность рассматриваемой задачи и построены новые эвристические алгоритмы
при оптимизации структуры подсистемы организации рестартов в вычислительных системах реального времени рассмотрена новая задача, в которой не предполагается (как в большинстве работ) что ошибка автоматически обнаруживается сразу же после возникновения. Для решения этой задачи разработан алгоритм оптимального расположения модулей контроля и модулей-буферов.
при построении оптимальной расстановки модулей контроля и модулей-буферов в вычислительных системах реального времени рассмотрен не только случай последовательного выполнения работ, но и случай произвольного графа зависимости по данным между заданиями.
Результаты диссертации опубликованы в работах [32-40],
докладывались на XLV научной конференции МФТИ, на 4-й Московской
международной конференции по исследованию операций, на 12-й международной конференции "Проблемы управления безопасностью сложных систем", на научных семинарах кафедры математических основ управления МФТИ и сектора проектирования систем реального времени ВЦ РАН.
Данная диссертационная работа состоит из введения, двух глав, заключения и списка использованных источников. Первая глава разбита на восемь разделов, а вторая - на шесть.
В главе 1 рассматривается задача составления оптимальных расписаний в многопроцессорных системах с неполным графом связей. В разделе 1.1 содержится постановка задачи. В разделе 1.2 рассмотрен случай, когда прерывания работ и их переключения между процессорами не требуют дополнительных временных затрат, а связи между процессорами образуют полный граф. Для этого случая приводится точный полиномиальный потоковый алгоритм Танаева B.C. [4]. Также в разделах 1.1-1.2 вводятся основные обозначения. В разделе 1.3 доказана NP-трудность некоторых частных случаев поставленной задачи, в частности случая, когда связи между процессорами образуют несвязный граф. В разделах 1.4-1.6 рассматривается случай, когда затраты на прерывания и переключения работ не учитываются, а связи между процессорами образуют произвольный связный граф. В разделах 1.4-1.5 построен точный полиномиальный алгоритм для решения этой задачи с дополнительным ограничением, что наибольший общий делитель левых и правых границ директивных интервалов и длительностей всех работ не меньше удвоенного числа процессоров, а в разделе 1.6 доказано, что без этого ограничения задача является NP-трудной. В разделе 1.7 построены эвристические алгоритмы для случая, когда затраты на прерывания и переключения работ учитываются. В разделе 1.8 частный случай указанной задачи с учетом издержек на переключения сведен к задачам булевого и целочисленного линейного программирования.
В главе 2 рассмотрена задача оптимальной расстановки модулей
контроля и модулей-буферов в вычислительных системах реального
времени. В разделе 2.1 описывается модель организации рестартов в
системах реального времени [31], функции модулей контроля и модулей-буферов, а также сформулирована задача их оптимальной расстановки. В разделах 2.2-2.5 рассмотрен случай, когда ошибка при выполнении каждого задания возможна, но маловероятна. В разделе 2.2 построена оптимальная расстановка модулей контроля и модулей-буферов для случая, когда задания выполняются последовательно в заранее заданном порядке, т.е. граф зависимости по данным является цепочкой. В разделе 2.3 разработан алгоритм для построения оптимальной расстановки в случае, когда существует несколько таких параллельных цепочек. В разделах 2.4-2.5 предполагается, что после каждого задания расположен модуль-буфер и рассматривается задача построения оптимальной расстановки модулей контроля. В разделе 2.4 разработан полиномиальный алгоритм для построения такой расстановки в случае, когда граф зависимости по данным является ориентированным деревом. В разделе 2.5 показано, что для произвольного графа зависимости по данным рассматриваемая задача является NP-трудной. В разделе 2.6 рассмотрена задача расстановки модулей контроля для случая, когда ошибка при выполнении заданий произвольна. Получены алгоритмы для построения оптимальной расстановки модулей контроля, если граф зависимости по данным является цепочкой или несколько параллельных цепочек.
В заключении формулируются основные результаты работы и предлагаются направления для дальнейшего исследования.
Задача с издержками на прерывания на одном процессоре
Целями настоящей диссертационной работы являются: - разработка эффективных алгоритмов составления оптимальных расписаний в многопроцессорных системах реального времени с неполным графом связей. - разработка эффективных алгоритмов построения оптимальной расстановки модулей контроля и модулей-буферов в вычислительных системах реального времени с различными графами зависимости по данным. Научная новизна данной работы состоит в том, что - при составлении оптимальных расписаний в многопроцессорных системах реального времени рассмотрен малоисследованный случай, когда граф связей между процессорами не является полным. Для случая связного графа связей (при некоторых дополнительных предположениях) построен точный полиномиальный алгоритм. Для некоторых ранее не рассмотренных случаев доказана NP-трудность рассматриваемой задачи и построены новые эвристические алгоритмы - при оптимизации структуры подсистемы организации рестартов в вычислительных системах реального времени рассмотрена новая задача, в которой не предполагается (как в большинстве работ) что ошибка автоматически обнаруживается сразу же после возникновения. Для решения этой задачи разработан алгоритм оптимального расположения модулей контроля и модулей-буферов. - при построении оптимальной расстановки модулей контроля и модулей-буферов в вычислительных системах реального времени рассмотрен не только случай последовательного выполнения работ, но и случай произвольного графа зависимости по данным между заданиями.
Результаты диссертации опубликованы в работах [32-40], докладывались на XLV научной конференции МФТИ, на 4-й Московской международной конференции по исследованию операций, на 12-й международной конференции "Проблемы управления безопасностью сложных систем", на научных семинарах кафедры математических основ управления МФТИ и сектора проектирования систем реального времени ВЦ РАН. Данная диссертационная работа состоит из введения, двух глав, заключения и списка использованных источников. Первая глава разбита на восемь разделов, а вторая - на шесть.
В главе 1 рассматривается задача составления оптимальных расписаний в многопроцессорных системах с неполным графом связей. В разделе 1.1 содержится постановка задачи. В разделе 1.2 рассмотрен случай, когда прерывания работ и их переключения между процессорами не требуют дополнительных временных затрат, а связи между процессорами образуют полный граф. Для этого случая приводится точный полиномиальный потоковый алгоритм Танаева B.C. [4]. Также в разделах 1.1-1.2 вводятся основные обозначения. В разделе 1.3 доказана NP-трудность некоторых частных случаев поставленной задачи, в частности случая, когда связи между процессорами образуют несвязный граф. В разделах 1.4-1.6 рассматривается случай, когда затраты на прерывания и переключения работ не учитываются, а связи между процессорами образуют произвольный связный граф. В разделах 1.4-1.5 построен точный полиномиальный алгоритм для решения этой задачи с дополнительным ограничением, что наибольший общий делитель левых и правых границ директивных интервалов и длительностей всех работ не меньше удвоенного числа процессоров, а в разделе 1.6 доказано, что без этого ограничения задача является NP-трудной. В разделе 1.7 построены эвристические алгоритмы для случая, когда затраты на прерывания и переключения работ учитываются. В разделе 1.8 частный случай указанной задачи с учетом издержек на переключения сведен к задачам булевого и целочисленного линейного программирования.
В главе 2 рассмотрена задача оптимальной расстановки модулей контроля и модулей-буферов в вычислительных системах реального времени. В разделе 2.1 описывается модель организации рестартов в системах реального времени [31], функции модулей контроля и модулей-буферов, а также сформулирована задача их оптимальной расстановки. В разделах 2.2-2.5 рассмотрен случай, когда ошибка при выполнении каждого задания возможна, но маловероятна. В разделе 2.2 построена оптимальная расстановка модулей контроля и модулей-буферов для случая, когда задания выполняются последовательно в заранее заданном порядке, т.е. граф зависимости по данным является цепочкой. В разделе 2.3 разработан алгоритм для построения оптимальной расстановки в случае, когда существует несколько таких параллельных цепочек. В разделах 2.4-2.5 предполагается, что после каждого задания расположен модуль-буфер и рассматривается задача построения оптимальной расстановки модулей контроля. В разделе 2.4 разработан полиномиальный алгоритм для построения такой расстановки в случае, когда граф зависимости по данным является ориентированным деревом. В разделе 2.5 показано, что для произвольного графа зависимости по данным рассматриваемая задача является NP-трудной. В разделе 2.6 рассмотрена задача расстановки модулей контроля для случая, когда ошибка при выполнении заданий произвольна. Получены алгоритмы для построения оптимальной расстановки модулей контроля, если граф зависимости по данным является цепочкой или несколько параллельных цепочек. В заключении формулируются основные результаты работы и предлагаются направления для дальнейшего исследования.
Сведение к задаче булевого линейного программирования
Рассматривается система, состоящая из т идентичных (если специально не оговорено обратное) процессоров. Задано множество работ Лґ = {1,2,...,и} с директивными интервалами (/3/,/] и длительностями выполнения tj,i є N. Все параметры предполагаются целочисленными, т.е. длительности работ и директивные интервалы состоят из целого числа единиц времени, которые мы в дальнейшем будем называть временными тактами. Без ограничения общности можно считать, что minbt = О,maxfj=T,ieN. Допускаются прерывания при выполнении работ и их переключения с одного процессора на другой. При каждом прерывании или переключении некоторой работы с процессора на процессор системой дополнительно выполняется г тактов для записи текущего состояния работы, а при возобновлении - еще г тактов на чтение. Определим граф связей между процессорами как граф, вершины которого - процессоры, а ребра - связи между ними (две вершины соединены ребром тогда и только тогда, когда работы могут напрямую переключаться между соответствующими процессорами). Предполагается, что граф связей между процессорами не обязательно полный.
Нашей задачей является построение расписания работ по процессорам. Под расписанием мы будем понимать следующее соответствие - для каждого процессора и каждого момента времени указывается работа (только одна), которая в этот момент на нем выполняется.
Расписание называется допустимым, если все переключения работ с процессора на процессор выполняются исключительно по ребрам графа связей и каждая работа успевает выполниться в пределах отведенного ей директивного интервала. Требуется определить, существует ли допустимое расписание, и найти его, если оно существует.
Алгоритм, который строит допустимое расписание, является полиномиальным, если время его работы ограничено полиномом Р(п,т,\пТ). Алгоритм, работающий за время Р{п,т,Т), является псевдополиномиальным. В этой работе мы будем рассматривать преимущественно полиномиальные алгоритмы. В связи с этим важно подчеркнуть, что если записать ответ (т.е. расписание) как функцию от процессора и момента времени, то эта запись требует псевдополиномиальное время (а именно пТ). Заметим, однако, что чтобы полностью определить расписание, достаточно просто для каждой работы указать время (т.е. номер временного такта) начала выполнения и номер процессора, время каждого переключения с одного процессора на другой с указанием номера нового процессора и времени возобновления выполнения работы, а также время начала и окончания каждого прерывания. В дальнейшем мы будем подразумевать на выходе именно такую запись ответа. Такая запись расписания может оказаться как псевдополиномиальной, так и полиномиальной, в зависимости от самого расписания. Понятно, что все предложенные в работе полиномиальные алгоритмы поиска допустимого расписания будут находить только расписания, для записи которых в вышеуказанном виде достаточно полиномиальное число символов. Полиномиальная сложность Р(п,т,\пТ) обычно получается, если запись каждого символа считать за отдельную операцию. Тогда запись не превосходящего Т числа (или, например, сложение таких чисел) имеет сложность 0(\пТ). Более общепринятым, однако, считается рассматривать каждую запись (или арифметическую операцию) как одну операцию. Мы будем придерживаться этой точки зрения, что приведет к исключению множителя In Г из оценок сложности предлагаемых алгоритмов.
Для случая, когда прерывания и переключения не сопряжены с временными затратами, а связи между процессорами образуют полный граф, известен полиномиальный алгоритм [4]. Кратко остановимся на основных его этапах. Если ,=0, = Тдля всех ieN, то необходимым и достаточным условием существования допустимого расписания является выполнение неравенства tj m. Для поиска допустимого расписания применяется алгоритм упаковки. Пусть теперь bj,fj- произвольные. Пусть d0 dx ... dp- это все различные значения bt и ft, ieN;. Обозначим Ij =(dj_l,d]; rj =dj-d_l, j = 1,2,...p. Строится потоковая сеть G, в которой s источник, t - сток, узлы /j,...,/ соответствуют интервалам, a wl}...,wn работам. В сети G определены дуги (s,Ij) для всех j = \,2,...,p, дуги (\Vj,t) - для всех ieN и дуги {Ij,wt), если І-сіф;,//]. Пропускные способности U дуг следующие: U(s,Ij) = m-rj, U(wi,t) = ti,U(IJ-,wi) = rj. Известно [4], что допустимое расписание существует тогда и только тогда, когда максимальный поток g в сети G насыщает все выходные дуги. В этом случае величина потока g(Ij,Wi) по дуге (/-,- -) определяет количество времени, выделяемого работе wt в интервале /,-. Расписание внутри каждого интервала Ij строится с помощью алгоритма упаковки. Отметим, что вычислительная сложность данного алгоритма 0{пъ).
Разделение модулей контроля по цепочкам при заданном разделении модулей-буферов
В этом разделе мы сформулируем задачу, для которой имеет смысл искать полиномиальный алгоритм построения допустимого расписания.
Как показано в предыдущем разделе, если затраты на прерывания и переключения учитываются, то задача становится NP-трудной, даже если процессор один. Если затраты на прерывания и переключения не учитываются, но производительности процессоров могут различаться, то при полном графе связей между процессорами полиномиальный алгоритм уже разработан [6], [8], а при неполном графе связей (даже если отсутствует всего одно ребро) задача уже оказывается NP-трудной. В дальнейшем в работе рассматривается только случай идентичных процессоров. Если затраты на прерывания и переключения не учитываются, а процессоры идентичные, для произвольного графа связей задача остается NP-трудной (раздел 1.3.4), поэтому на граф связей надо наложить еще дополнительное условие. В разделе 1.3.5 доказано, что даже если он зафиксирован, но состоит из двух отдельных компонент (каждая является полным графом), задача остается NP-трудной. Все это приводит нас к следующим предположениям. 1. Будем предполагать, что прерывания и переключения не сопряжены с временными затратами, т.е. г = О. 2. Будем предполагать, что граф связей между процессорами связный. Напомним также, что процессоры здесь и далее подразумеваются идентичными. Задачу, сформулированную в разделе 1.1, с предположениями 1 и 2 в дальнейшем будем называть основной задачей. Напомним (см. раздел 1.1), что без ограничения общности можно считать, что minfy = 0, max/J- = T,ieN. Очевидно, что если сумма длительностей работ превышает суммарное время на процессорах, то допустимого расписания не существует. Если же, наоборот, сумма длительностей работ меньше суммарного времени на процессорах, при построении расписаний появится время простоя некоторых процессоров. В дальнейшем, чтобы упростить разработку и запись всех алгоритмов, удобно исключить этот случай из рассмотрения. Следующая теорема позволяет нам при рассмотрении основной задачи без ограничения общности считать, что суммарная длительность всех работ в точности равна отведенному на них процессорному времени. При доказательстве теоремы показано, как построить набор фиктивных работ, которые в точности займут все время простоя процессоров. Теорема 1.1. В основной задаче без ограничения общности можно считать, что jtt=m, т.е. что суммарная длительность всех работ в точности равна отведенному на них процессорному времени. Доказательство. Предположим, что S = т-Т — ]// 0. Если мы введем дополнительную фиктивную работу с длительностью S, то новая задача может быть не эквивалентна исходной. Рассмотрим, например, систему из двух не связанных между собой процессоров и 2 работы, каждая с длительностью 2, с директивными интервалами (0,2] и (1,3] соответственно. При этом существует допустимое расписание, но 2 такта процессоры будут простаивать. При попытке добавить новую фиктивную работу с длительностью 2, мы получим, что для новой системы работ допустимого расписания не существует. Эту проблему можно решить введением S фиктивных работ с длительностями 1 и директивным интервалом (0,74. В этом случае очевидно, что новая задача эквивалентна исходной. С одной стороны, если существует допустимое расписание для новой задачи, то, исключая новые работы, получим допустимое расписание для исходной. С другой стороны, если существует допустимое расписание для исходной задачи, то новые работы с длительностями 1 можно легко назначить на времена простоя процессоров. Директивный интервал (0,Г] при этом не нарушится. Таким образом, мы построим допустимое расписание и для новой задачи. Однако так поступать тоже нельзя, так как фиктивных работ может оказаться слишком много - больше, чем полином от входных данных исходной задачи. Чтобы корректно ввести набор фиктивных работ, нам понадобятся следующие определение и лемма. Определение. Будем говорить, что набор чисел сх,с2,...,ск составляет набор di,d2,...,dr, если множество {1,2,...,} можно разбить на непересекающиеся подмножества А{,А2,...,АГ, такие что для любого j (\ j r) Y,ci=dj ieAj Лемма 1.2. Даны натуральные числа п и S. Тогда существуют натуральные числа bx,b2,...,br (r P(n,\nS), Р - полином двух переменных), такие, что ,=5, и, кроме того, для любых аі,а2,...,ап,таких что ]]#/ = S, набор b{,b2,...,br составляет набор а1,а2,...,ап. Доказательство. Сначала укажем способ выбора чисел , ,..., . Если S п, полагаем г = S, bl=b2=... = br = 1. При п S Ъп полагаем b{ =b2=... = bn=\, bn+l=bn+2=... = bk=2 и, возможно (если S-n нечетно), bk+l = 1. При Ъп S In полагаем Ьх=Ь2=... = Ъп=\, bn+l=bn+2=-=b2n=2 b2n+l=b2n+2=- = bk=4 гДе к это к максимальный номер, для которого S bj. Пусть w = S-y jbi - остаток /=1 от деления S-Зп на 4. Тогда если w = 0, то набор { } определен; если w = 1, полагаем bk+i = 1; если w = 2, полагаем Ьк+Х = 2; если w = 3, полагаем bk+l = 2, bk+2 = 1.
Порядок выполнения рабочих модулей при заданном расположении модулей контроля
Заметим, что при доказательстве мы также описали алгоритм, как именно путешественники могут попасть домой.
Следствие. Пусть 2т тактов подряд на т процессорах выполняются одни и те же т работ. Тогда при любом связном графе связей и любом распределении работ по процессорам на первом такте, на такте 2т можно получить любое другое распределение работ по процессорам.
Именно для получения этого важного следствия мы и доказали лемму 1.3. Напомним, что при построении расписания по потоковому алгоритму мы получили не более 2п блоков, в каждом из которых выполняются только т работ. Мы показали, что если длина такого блока хотя бы 2т, то мы успеваем как угодно переставить работы внутри блока. Более длинные блоки с этой точки зрения не требуются.
Заменим блоки, имеющие длину более 2т, на такие же блоки длины 2т, после чего построим соответствующую таблицу (назовем ее таблицей 2 для задачи преобразования таблицы). Пусть Т - число столбцов в полученной таблице, тогда Т 2п п 2m.
Покажем, что имеет место соответствие ответов. Пусть в задаче преобразования таблицы ответ "да", т.е. путем перестановки чисел внутри одного столбца может быть построена допустимая расстановка. Покажем, как по таблице 2 построить таблицу 1 (которая соответствует расписанию). Если в таблице 2 некоторый блок длины 2т был получен из блока (в расписании, построенном по потоковому алгоритму) длины р 2т, то первые 2т-I столбцов в этом блоке оставляем без изменения, а последний дублируем р - 2т +1 раз. Очевидно, что это расписание можно получить из исходного с помощью допустимых операций (перестановок работ по процессорам в пределах одного такта). А это означает, что в задаче преобразования расписания тоже ответ положительный.
Пусть теперь в задаче преобразования расписания ответ "да", т.е. существует такая последовательность допустимых операций, которая исходное расписание преобразует в допустимое. Докажем, что тогда такая последовательность существует и в задаче преобразования таблицы. При перестановках работ внутри одного такта, принадлежащего блоку длины, не превосходящей 2т, соответствующие перестановки выполняются и в таблице 2. В итоге внутри любого такого блока расстановка будет допустимой. Для блоков длины, большей 2т, в соответствующем блоке таблицы 2 в первом и последнем (2т-м) столбцах перестановки сохраняются, а в промежуточных столбцах используются такие перестановки, при которых результирующая расстановка внутри блока допустимая (см. лемму 1.3 и следствие из нее). Переключения между блоками также допустимые, поскольку они зависят только от первого и последнего столбцов блоков, которые менялись в соответствии с преобразованиями исходного расписания в допустимое (при решении задачи преобразования расписания). Теорема доказана.
При доказательстве теоремы мы построили алгоритм, как по задаче преобразования расписания построить эквивалентную ей задачу преобразования таблицы, в которой число столбцов ограничено полиномом от длины входного слова исходной задачи.
В предыдущем разделе (лемма 1.3) мы доказали, что если 2т тактов подряд на т процессорах выполняются одни и те же т работ, то в пределах такого блока мы успеваем как угодно переставить работы по процессорам при любом связном графе связей. Это приводит нас к следующей идее, которую мы будем называть масштабированием. Пусть А - основная задача. Поставим ей в соответствие задачу А , где все &/,./)и tj умножены на 2т, т.е. фактически каждый такт разбивается на 2т частей. Следующая теорема строит эффективный алгоритм для решения этой новой задачи. Теорема 1.3. Существует полиномиальный алгоритм решения задачи А . Доказательство. Применим потоковый алгоритм для решения задачи А. Если допустимого расписания не существует, то и в задаче А его не существует. Пусть теперь допустимое расписание для полного графа связей в задаче А существует. Умножая все параметры на 2т, получим допустимое расписание в задаче А . Строим соответствующую задачу преобразования расписания, которая по теореме 1.2 полиномиально сводится к задаче преобразования таблицы. В результате этого сведения получаем таблицу, в которой каждый столбец повторен ровно 2т раз подряд. Докажем, что для такой таблицы всегда можно построить допустимую расстановку, и укажем, как это сделать. Для этого нам понадобится следующая лемма. Лемма 1.4. Пусть G= V,E - ориентированный граф без циклов (V -занумерованное множество вершин, Е- ребра, причем i j для любого ребра (i,j)eE). Пусть степень исхода и степень захода каждой вершины не более т (при этом разрешаются кратные ребра, например все m ребер, исходящих из вершины 1, могут идти в вершину 2). Тогда ребра графа можно раскрасить т цветами так, что для любой вершины все выходящие ребра будут иметь разные цвета, и все входящие ребра также будут иметь разные цвета. При этом для получения данной раскраски существует алгоритм сложности 0(\ V \ т- log V ), где К - количество вершин в графе. Доказательство. Пусть V\,V2,...,Vk - вершины графа G. Построим по графу G неориентированный двудольный граф Н = V ,E следующим образом. V состоит из 2к вершин Vx\ V},..., V\, V{2, К,2,..., J7/, а каждому ребру (V VAeE соответствует неориентированное ребро (yt, V.- ) є Е . Так как вершины V\ ,V2,...,Vk, а также вершины vf ,V22,...,v попарно не соединены, то полученный граф Н является двудольным. При этом из построения Н следует, что максимальная степень вершины в нем равна т. Раскраски ребер в графах G и Н в т цветов назовем соответственными, если для любого ребра (V V eE ребро (Vt ,Vj )еЕ покрашено в тот же цвет. Тогда требуемая раскраска графа G соответствует раскраске графа Н, при которой любые 2 ребра, имеющие общую вершину, покрашены в разные цвета.
Похожие диссертации на Алгоритмы планирования вычислений и организации рестартов в системах реального времени
