Содержание к диссертации
Введение
Глава 1 Принципы организации и функционирования сетевых информационно-управляющих систем (СИУС) мехатронных объектов 21
1.1 Обобщенная структура и классификация мехатронных объектов 21
1.2 Задача управления мехатронным объектом 26
1.3 Способы организации информационно-управляющих систем мехатронных объектов 29
1.4 Способы организации вычислительного процесса в сетевой информационно-управляющей системе 43
1.5 Методы обеспечения надежности СИУС 54
1.5.1 Способы резервирования, применяемые в современных технических системах 54
1.5.2 Анализ возможности применения существующих способов резервирования в бортовых СИУС 61
1.6 Выводы 71
Глава 2 Метод обеспечения надежности СИУС за счет резерва производительности процессорных узлов 73
2.1 Способ резервирования производительности 73
2.2 Исследование влияния вычислительной нагрузки на вероятность безотказной работы отдельного процессорного узла 83
2.3 Метод повышения надежности СИУС за счет выравнивания вычислительной нагрузки отдельных процессорных узлов 86
2.4 Сравнение способов резервирования производительности и скользящего структурного резервирования 98
2.5 Способ повышения надежности коммутационной сети СИУС за счет резерва пропускной способности 111
2.6 Выводы 114
Глава 3 Методы и алгоритмы диспетчирования СИУС 118
3.1 Способы организации диспетчера СИУС 118
3.1.1 Реализация диспетчера с помощью выделенного процессорного узла 118
3.1.2 Способ организации распределенного диспетчера СИУС 121
3.2 Особенности функционирования СИУС с распределенным диспетчером 123
3.2.1 Диспетчирование СИУС при однопроцессорном способе организации вычислительного процесса 124
3.2.2 Диспетчирование СИУС при параллельном способе организации 127
вычислительного процесса
3.2.3 Диспетчирование СИУС при конвейерном способе организации вычислений 128
3.3 Алгоритмы работы локального диспетчера 132
3.4 Особенности организации информационного обмена в СИУС 136
3.5 Выводы 142
Глава 4 Методы и алгоритмы реконфигурации СИУС 144
4.1 Постановка задачи реконфигурации СИУС 144
4.2 Формализация задачи размещения подзадач по процессорным узлам 147
4.3 Алгоритмы размещения при параллельном способе организации вычислительного процесса в СИУС 151
4.3.1 Алгоритм полного перебора 151
4.3.2 Алгоритм имитации отжига 153
4.3.3 Алгоритм поярусного размещения 158
4.3.4 Алгоритм частичного размещения 165
4.4 Алгоритмы размещения при конвейерном способе организации ычислений в СИУС 169
4.5 Выводы 178
Глава 5 Разработка и исследование программных средств децентрализованного диспетчирования СИУС 181
5.1 Программные средства локального диспетчера СИУС 181
5.1.1 Структура программных средств локального диспетчера 181
5.2 Механизмы информационного взаимодействия, реализуемые программными средствами локального диспетчера 187
5.3 Программная модель СИУС 189
5.3.1 Структура программной модели 189
5.3.2 Работа с программной моделью СИУС 191
5.3.3 Исследование работоспособности алгоритмов работы программных средств локального диспетчера с помощью программной модели СИУС 196
5.4 Результаты тестирования программных средств локального диспетчера на макете СИУС 198
5.5 Выводы 202
Глава 6 Практические аспекты проектирования и создания децентрализованных СИУС сложных мехатронных объектов 204
6.1 СИУС машины перегрузочной атомного реактора 204
6.2 СИУС авиационного комплекса дальнего радиолокационного обнаружения 211
6.3 Применение программных средств локального диспетчера в СИУС интегрированной модульной авионики 221
6.3.1 Особенности организации СИУС интегрированной модульной авионики 221
6.3.2 Способы «преодоления» ограничений стандартов ARINC 653 и ARINC 664 226
6.3.3 Организация программных средств локального диспетчера СИУС интегрированной модульной авионики 228
6.3.4 Результаты исследований возможности применения реконфигурации и выравнивания нагрузки для повышения надежности СИУС интегрированной модульной авионики 230
6.4 Выводы 230
Заключение 233
Список сокращений 239
Список литературы
- Задача управления мехатронным объектом
- Исследование влияния вычислительной нагрузки на вероятность безотказной работы отдельного процессорного узла
- Способ организации распределенного диспетчера СИУС
- Алгоритмы размещения при параллельном способе организации вычислительного процесса в СИУС
Задача управления мехатронным объектом
Достоверность и обоснованность научных исследований подтверждается теоретическим обоснованием, основанным на использовании классического математического аппарата, и практически полным совпадением теоретических результатов с результатами испытаний прототипов информационно-управляющих систем.
Реализация результатов работы. Основные результаты диссертационных исследований были использованы в следующих работах.
1. НИР "Разработка аппаратно-программных средств повышенной надежности для модернизированной машины перегрузочной энергоблоков АЭС с реактором типа ВВЭР на основе технологии многопроцессорных вычислительных систем с программируемой архитектурой" в рамках межотраслевой научно технической программы сотрудничества Минобразования и Минатома России по направлению «Научно-инновационное сотрудничество» (НИИ МВС ТРТУ, г/б № 524306, шифр Мезонин, № ГР 01.0.40 001165), 2003 г.
2. ОКР Разработка и изготовление комплекса технических средств системы управления машины перегрузочной энергоблока №1 Волгодонской АЭС (НИИ МВС ТРТУ, х/д 524232, шифр «Контроль»), 2002–2005 гг.
3. НИР «Разработка теоретических основ построения децентрализованных мультиагентных систем поиска и обработки информации в телекоммуникационных и компьютерных сетях на базе принципов коллективного принятия решений» (НИИ МВС ТРТУ, г/б 556139, шифр «Агент», №ГР0120.0511688), 2005–2008 гг.
4. НИР «Создание методов и алгоритмов построения распределенных вычислительных систем без централизации функций управления» в рамках ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002–2006 годы» (НИИ МВС ТРТУ, шифр «Децентрализация», №ГР 0120.0603027), 2005–2006 гг. 5. НИР «Разработка технологии организации отказоустойчивых распределенных вычислений в системах реального времени на основе мультиагентного взаимодействия» в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007–2012 годы» (НИИ МВС ЮФУ, г/к 02.514.11.4003, шифр «Децентрализация 2», №ГР 01.2.007 06420), 2007 г.
6. НИР «Разработка методов и средств повышения безопасности и эффективности функционирования распределенных информационно-управляющих систем сложных технических объектов» в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007–2012 годы» (НИИ МВС ЮФУ, г/к 02.514.11.4085, шифр «Децентрализация 3», №ГР 01200852907), 2008–2009 гг.
7. НИР «Разработка методов и алгоритмов повышения надежности и эффективности бортовых информационно-управляющих систем» (НИИ МВС ЮФУ, г/б 302/23153, шифр «Агент 2», №ГР 01201263488), 2012–2014 гг.
8. НИР «Разработка методов и алгоритмов децентрализованной обработки информации и управления в многопроцессорных вычислительно-управляющих системах сложных, распределенных объектов на основе принципов мультиагентного взаимодействия» (грант РФФИ №05-08-33501а, шифр «Поиск»), 2005–2007 гг.
9. НИР «Разработка методов и алгоритмов децентрализованного распределения ресурсов в GRID-структурах» (грант РФФИ №08-07-00249а, шифр «Поиск 2»), 2008–2010 гг.
10. НИР «Разработка научных основ создания сетецентрических информационно-управляющих систем» (грант РФФИ №11-07-00542а, шифр «Сети», №ГР01201164291), 2011–2013 гг. 11. НИР «Исследования по формированию облика программно-аппаратных средств для построения современных авиационных распределенных информационно-диагностических и управляющих систем» (НИИ МВС ЮФУ, х/д 302/25211, шифр «ИМА конструктор – МВС», №ГР01201274298), 2012 г. 12. СЧ ОКР «Разработка программных средств организации вычислительного процесса на базе мультиагентного диспетчера» (НИИ МВС ЮФУ, х/д 593220, шифр «Премьер – ОВП ФПО»), 2009 – 2017 гг.
Апробация работы. Основные результаты диссертационной работы были представлены на - Всероссийской научно-технической конференции с международным участием «Компьютерные технологии в инженерной и управленческой деятельности», г. Таганрог, 2002 г. - Международной научно-технической конференции «СуперЭВМ и многопроцессорные вычислительные системы», Таганрог, 2002 г. - Первой научной молодежной школе «Интеллектуальные мехатронные робототехнические системы», п.Кацивели, Крым, Украина, 2002 г. - Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы–2003», с. Дивноморское, 2003 г. - Международной научно-технической конференции «Искусственный интеллект. Интеллектуальные и многопроцессорные системы», с.Кацивели, Украина, 2004 г. - Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы–2005», с Дивноморское, 2005 г. - Седьмой Международной научно-технической конференции «Искусственный интеллект. Интеллектуальные и многопроцессорные системы – 2006», с. Кацивели, Украина, 2006 г. - Международной научно-практической конференции «Прогресс транспортных средств – 2009». г.Волгоград, 2009. - Международной научно-технической конференции «Суперкомпьютерные технологии: разработка, программирование, применение» (СКТ–2010), с. Дивноморское, 2010 г. - 4-й Всероссийской мультиконференции по проблемам управления (МКПУ–2011), с.Дивноморское, 2011 г. - Международной научно-практической конференции «Теория активных систем», Москва, 2011 г.. - 2-й Всероссийской научно-технической конференции «Суперкомпьютерные технологии» (СКТ–2012), с. Дивноморское, 2012 г. - 1-м Международном симпозиуме «Гибридные и синергетические интеллектуальные системы: теория и практика», г.Калининград, 2012 г. - 7-й Всероссийской научно-практической конференции «Перспективные системы и задачи управления», п.Домбай, 2012 г. - III Международной конференции «Инфокоммуникационные и вычислительные технологии и системы», г.Улан-Удэ, 2010 г.
Авторство, новизна и полезность принципиальных технических решений защищены двумя патентами РФ на полезную модель и шестью свидетельствами об официальной регистрации программ на ЭВМ.
Из работ, выполненных в составе коллектива авторов, в диссертации использованы результаты, полученные автором лично.
Публикации. Научные и практические результаты диссертации отражены в 75 публикациях. Основные результаты опубликованы в 24 работах в рецензируемых изданиях, из которых 1 монография [5] (авторский вклад 50%); 15 статей [30–44] общим объемом 118 стр. (авторский вклад 40%) в ведущих научных журналах и изданиях (14 в журналах, включенных в перечень ВАК); 2 патента РФ на полезную модель [82, 83] (авторский вклад 50%); 6 свидетельств об официальной регистрации программ для ЭВМ [84–89] (авторский вклад 19%).
Кроме того, результаты диссертации отражены в 2 коллективных монографиях [24], [29] (авторский вклад 3,5%); 12 зарегистрированных отчетах о НИР общим объемом 1900 стр., из них 550 стр. авторских; 37 тезисах докладов и статьях в сборниках трудов конференций [45–81] общим объемом 159 стр. (авторский вклад 40%). Внедрение результатов. Результаты работы были внедрены и используются в следующих организациях: ОАО «Концерн «Вега» (г.Москва), ОАО «ВНИИАМ» (г.Москва), ФГУП «ГосНИИАС» (г.Москва), НИИ многопроцессорных вычислительных систем ЮФУ (г. Таганрог).
Структура и краткое содержание диссертации. Диссертация состоит из введения, шести глав, заключения, списка литературы и приложений. Содержание работы изложено на 265 страницах, работа содержит 120 рисунков и 12 таблиц, список использованной литературы из 153 наименований. Во введении обоснована актуальность темы, сформулирована цель и основные задачи исследования.
В первой главе рассмотрены принципы организации и особенности функционирования современных ИУС на примере ИУС МО. Проведен анализ мехатронных объектов различного назначения и выделен класс мехатронных объектов мобильного и критического применения, к которым предъявляются повышенные требования по надежности и безопасности функционирования, малым массогабаритным размерам и энергопотреблению. Показано, что основную роль в обеспечении надежности и безопасности функционирования мехатронного объекта играет его информационно-управляющая система, функции которой заключаются в решении задачи управления МО.
На основе анализа особенностей функционирования ИУС МО сформулированы предъявляемые к ним требования, в число которых входят требования по быстродействию (т.е. решению задачи управления МО за допустимое время), требования по надежности (вероятность безотказной работы и гамма-процентная наработка) и стоимостные требования.
Исследование влияния вычислительной нагрузки на вероятность безотказной работы отдельного процессорного узла
Будем считать, что каждой вершине a &Q графа G(Q X) соответствует некоторая подзадача, вычислительная сложность которой определяется величиной Dj (т.е. количеством элементарных вычислительных операций, необходимых для решения этой подзадачи на ПУ).
Дуги множества х графа G(Q, X) определяют пересылки данных между подзадачами, соответствующими вершинам множества Q . При этом если две вершины q. иqy графа G(Q, X) соединены дугой x(qi,q.) , то это означает, что выходные данные, полученные в результате реализации вершины (подзадачи) q., являются входными данными, необходимыми для реализации подзадачи q; . Будем считать, что каждой дуге xfq qJeX приписана величина WtJ , определяющая количество (объем) данных, передаваемых от вершины (подзадачи) qt к вершине (подзадаче) qj.
Кроме того, будем считать, что задача управления должна решаться за некоторое ограниченное время Греш, не превышающее некоторое максимально допустимое время решения задачи управления Tцз, что обуславливается требованием соблюдения режима реального времени при функционировании МО. Фактически, это означает, что ИУС за это время, не превышающее максимально допустимое Tцз, должна успеть получить исходные данные от информационной подсистемы, выполнить действия, предусмотренные операционными вершинами (т.е. произвести вычисления, предписанные операционными вершинами, и выполнить передачи данных, предписанные дугами графа задачи) и передать полученные управляющие воздействия на исполнительные механизмы МО. Если по каким-то причинам ИУС перестает вырабатывать управляющие воздействия и пребывает в таком состоянии более некоторого максимально допустимого времени (времени восстановления – TВВПз), то фиксируется ее отказ. Отказ ИУС означает отказ всего МО. Это обуславливает повышенное внимание, уделяемое вопросам надежности при разработке ИУС МО, т.к. надежность всего МО в целом, в первую очередь, характеризуется способностью ИУС выполнять свои функции (т.е. решать задачу управления за отведенное время) в течение всего срока эксплуатации МО.
Для мобильных МО большое значение имеют также массогабаритные характеристики, поэтому разработчики ИУС таких объектов должны стремиться максимально уменьшить объем используемого оборудования. Кроме того, уменьшение объема оборудования практически всегда позволяет снизить энергопотребление, что также важно для ИУС, используемых в мобильных МО.
Еще одним фактором, который необходимо учитывать при создании ИУС, является ее стоимость. Из двух ИУС с одинаковыми характеристиками потребитель выберет менее дорогую.
Рассмотрим способы организации ИУС мехатронных объектов, исходя из выше обозначенных требований.
Способы организации информационно-управляющих систем мехатронных объектов Для решения задачи управления в состав ИУС должны входить (рисунок 1.10): – вычислительное устройство, служащее для реализации алгоритма решения задачи управления, т.е. выполнения действий, предусмотренных вершинами множества Qоп графа задачи; – интерфейсное устройство, служащее для обмена данными и командами управления с источниками информации и исполнительными устройствами, т.е. взаимодействия с вершинами множеств Qвх и Qвых. зо В зависимости от способов организации вычислительной и интерфейсной частей будет соответственно изменяться и общая организация ИУС. Рассмотрим и сравним различные способы организации ИУС МО. ИУС Вычислительное устройство Интерфейс J Х От ИИ К ИУ ИИ - источники информации ИУ - исполнительные устройства Рисунок 1.10 - Обобщенная структура ИУС МО Для того чтобы провести такое сравнение, необходимо уточнить критерии, по которым оно должно осуществляться. Как это было показано выше, к ИУС МО могут предъявляться различные требования: - требования к быстродействию; - требования к надежности; - требования (ограничения) по уровню аппаратных затрат (или требования к стоимости и массогабаритным характеристикам) и т.п.
Отметим, что выделенные требования являются наиболее распространенными при проектировании МО [3, 4], так как другие требования (например, требования к массе, габаритам и потребляемой мощности ИУС) с ними взаимосвязаны.
Для однозначности дальнейших рассуждений необходимо определить, что мы будем понимать под быстродействием, надежностью и стоимостью (уровнем аппаратных затрат) ИУС МО.
Под быстродействием ИУС будем понимать величину, обратно пропорциональную времени Греш решения задачи управления. Чем меньше будет это время, тем выше будет быстродействие ИУС. Очевидно, что время решения задачи управления на ИУС складывается из времени приема исходных данных от ИИ, времени реализации алгоритма управления и времени передачи команд управления на ИУ. Поэтому быстродействие ИУС в целом зависит как от быстродействия вычислительной части, так и от быстродействия интерфейсной части.
Надежность - это свойство системы сохранять во времени способность выполнения требуемых функций [96-98].
В нашем случае под требуемой функцией следует понимать способность ИУС решать задачу управления за время, не превышающее максимально допустимое 7цз. Очевидно, что эта способность будет зависеть от способности интерфейсной части передавать данные между источниками информации (ИИ) и исполнительными устройствами (ИУ) МО и вычислительной частью ИУС, а также от способности вычислительной части устройства ИУС реализовать вычислительные процедуры, приписанные вершинам подмножества Qоп за максимально допустимое время Тцз. Иными словами, надежность ИУС также «складывается» из надежности вычислительного устройства и интерфейсной части.
Для количественной оценки надежности используют различные критерии, такие как вероятность безотказной работы, средняя наработка до отказа, средняя наработка на отказ, гамма-процентная наработка на отказ. Из перечисленных показателей для характеристики надежности ИУС, работающих в критических условиях, наиболее удобно применять (и они широко применяются) показатели вероятности безотказной работы и гамма-процентной наработки, т.к. именно они отражают и способность ИУС выполнять заданные функции в течение заданного периода эксплуатации.
Вероятность безотказной работы (Р) - это вероятность того, что в пределах заданного времени (продолжительности) работы системы отказ не произойдет. В нашем случае под отказом следует понимать невозможность ИУС выполнять требуемую функцию за допустимое время 7цз. Будем считать, что уровень надежности ИУС достаточный, если вероятность ее безотказной работы выше заданной в течение заданного периода эксплуатации.
Гамма-процентная наработка на отказ (ty) - время работы ИУС, в течение которого вероятность безотказной работы будет выше заданной (наработка, в течение которой отказ объекта не возникнет с вероятностью, выраженной в процентах).
Под уровнем аппаратных затрат ИУС будем понимать количество процессорных (7V) и коммуникационных устройств (Е), требуемых для реализации вычислительной и интерфейсной частей ИУС соответственно.
Под стоимостью ИУС будем понимать стоимость аппаратных средств, требуемых для ее реализации. Очевидно, что стоимость ИУС складывается из стоимости аппаратных средств вычислительной и интерфейсной частей, которые, в свою очередь, зависят от количества и качества последних.
Способ организации распределенного диспетчера СИУС
Отметим, что при больших N при фиксированном 5 повышается эффективность использования ресурсов СИУС, т.к. снижается доля резерва в их общем объеме. Однако при этом вероятность безотказной работы ВУ СИУС снижается, поэтому при определенном значении N Р примет значение меньшее, чем минимально допустимое. Поскольку значениям Рмин порядка 0,999 соответствует начало «ямы» (рисунок 2.16), то по мере увеличения N будет увеличиваться и АР. Приведенные в таблице 2.2 данные показывают, что эффект от выравнивания нагрузки (в плане повышения вероятности безотказной работы) сопоставим с эффектом от добавления дополнительного резервного ПУ. Таким образом, выравнивание нагрузки можно использовать для повышения эффективности использования ресурсов СИУС в плане повышения надежности.
Можно привести еще один пример эффективного использования выравнивания нагрузки для снижения стоимости СИУС. Пусть необходимо построить СИУС, обладающую вероятностью безотказной работы не ниже 0,999 с заданным временем работы 10000 часов. Будем считать, что параметры задачи управления известны (число подзадач, их трудоемкость, информационные потоки и объемы передаваемых данных) и имеются два варианта распределения подзадач по ПУ, один из которых обеспечивает равную нагрузку ПУ, а другой предполагает работу 3-х ПУ с повышенной (с температурой на 15C выше) и 3-х ПУ с пониженной нагрузкой (с температурой на 15C ниже). При построении СИУС предполагается использовать ПУ, которые по истечении заданного времени работы будут обладать вероятностью безотказной работы 0,9.
Если провести расчеты вероятности безотказной работы для различных сочетаний N и В при равномерной и неравномерной нагрузке ПУ, то получится, что в диапазоне #є[6;15] (по условию N не может быть меньше 6, т.к. имеется 3 ПУ с повышенной и пониженной нагрузкой, всего рассматривается 10 вариантов) допустимыми будут следующие сочетания: - при равной нагрузке - (#є[6;9], 5=4), (#є[10;13], 5=5), (#є[14;15], В=6); - при неравной нагрузке - (#є[6;8], В=4), (#є[9;11], В=5), (#є[12;15], В=6). То есть, если для решения задачи управления при заданных условиях минимально необходимо 5, 7 или 8 ПУ, то выравнивание нагрузки позволяет «сэкономить» один ПУ (если, например, N=9 и 5=4, то минимально необходимое для решения задачи число ПУ равно 5).
Более того, если для СИУС с равной нагрузкой уменьшить РПУ до 0,89, то такая система по-прежнему будет превосходить систему с неравной нагрузкой, в которой использованы ПУ с вероятностью безотказной работы 0,9, если для решения задачи необходимо 7 ПУ. При этом наработка на отказ ПУ, имеющих РПУ=0,89, будет примерно на 10% ниже (86000 часов против 95000 часов).
Во многих случаях требования к надежности СИУС задаются в виде периода работы, в течение которого вероятность безотказной работы должна быть выше некоторого минимального значения, т.е. в виде гамма-процентной наработки на отказ. На третьем этапе исследований эффективности применения выравнивания нагрузки для повышения вероятности безотказной работы ВУ СИУС были получены данные об увеличении гамма-процентной наработки на отказ. Исходные данные для исследований были выбраны на основе результатов первых двух этапов:
В ходе исследований были выполнены расчеты гамма-процентной наработки на отказ для всех сочетаний перечисленных выше исходных данных. Исследования показали, что: - зависимость увеличения гамма-процентной наработки на отказ от числа парируемых отказов при использовании выравнивания нагрузки имеет вид, показанный на рисунке 2.17, при этом максимальное значение разности наработки при выравнивании и без выравнивания нагрузки достигается при B=[N/2]+1, т.е. At =t -+max при Я = ГіУ/2І+1, у у р Y нр - -І где ґур - гамма-процентная наработка на отказ при реализации выравнивания нагрузки; Yнр - гамма-процентная наработка на отказ без реализации выравнивания нагрузки. - в процентном соотношении ((/Гр-/гнр)//гр 100%) (вид зависимости от числа парируемых отказов представлен на рисунке 2.18) эффект от применения выравнивания нагрузки в некоторых случаях достигает 10% (таблица 2.3) в точке максимального значения разности наработки, что позволяет говорить о целесообразности применения выравнивания нагрузки как альтернативы добавлению одного ПУ в СИУС, если при этом удается достичь требуемых значений вероятности безотказной работы; - увеличение N+ и AT приводит к увеличению эффекта от использования выравнивания
В таблице 2.3 приведены расчетные данные, демонстрирующие эффект от применения выравнивания нагрузки. Серым цветом выделены ячейки, в которых содержатся результаты, которые могут представлять интерес при разработке СИУС (увеличение гамма-процентной наработки составляет не менее 5%).
Проведем сравнение двух альтернативных способов резервирования из описанных выше. Пусть в состав вычислительной части СИУС входит N ПУ, из которых Я являются «основными» ПУ, а B=N-H - резервными. Будем считать, что в случае выделения резервных ПУ нагрузка на «основные» ПУ и резервные ПУ отличается и, соответственно, равна DOCH и Dpe3, а при организации СИУС без выделения резервных ПУ все процессорные устройства имеют равную нагрузку DPaeH (вычислительная нагрузка представляет собой количество вычислительных операций в единицу времени). Пусть для решения задачи управления достаточно Нтіп ПУ, работающих с полной нагрузкой Dmaxny, а для поддержания в готовности одного резервного ПУ (резервных ресурсов) к «подхвату» вычислений в случае отказа необходимо выполнять Dpe3ny операций на цикл расчетов. Тогда нагрузка ПУ для рассматриваемых случаев составит
На основании приведенных выше формул докажем, что использование способа резервирования производительности в сочетании с методом выравнивания нагрузки позволяет повысить вероятность безотказной работы ВУ СИУС по сравнению со способом структурного скользящего резервирования.
Утверждение. Применение резервирования производительности в сочетании с выравниванием нагрузки ПУ вычислительного устройства СИУС повышает вероятность его безотказной работы.
Ограничения: N 2; =0; H=Hmin, нагрузка всех основных и резервных ПУ при скользящем резервировании равна Досн и Dрез соответственно; нагрузка всех ПУ при резервировании производительности равна .Оравн Запишем с учетом ограничений формулы для расчета вероятности
Поскольку в системе со скользящим резервированием имеется две группы ПУ с разной нагрузкой, в соответствии с леммой из параграфа 2.3 система с использованием резервирования производительности и выравнивания нагрузки будет обладать большей вероятностью безотказной работы. Что и требовалось доказать.
Проиллюстрируем вышесказанное для B=1 и N=3. Формулы для вычисления вероятности безотказной работы для ВУ СИУС со скользящим резервированием и резервированием производительности с выравниванием нагрузки примут вид:
Алгоритмы размещения при параллельном способе организации вычислительного процесса в СИУС
В данной главе проведены исследования способов диспетчирования работы СИУС. На основании результатов проведенных исследований можно сделать следующие выводы.
1. Для организации отказоустойчивого функционирования СИУС на базе резервирования производительности необходимо обеспечить выполнение процедуры перераспределения подзадач задачи управления на исправных П У. Данная процедура не тривиальна и требует применения специального компонента системы – диспетчера. Основная задача диспетчера – отслеживание работоспособности ПУ, определение работоспособной конфигурации в случае отказа и перераспределение подзадач задачи управления на исправных ПУ.
2. Показано, что наиболее очевидным способом реализации диспетчера является добавление в систему специального устройства, однако данный способ не может быть применен в высоконадежных СИУС, так как: - требует добавления в состав системы одного ПУ; - приводит к существенному снижению вероятности безотказной работы, т.к. отказ единственного диспетчера приводит к отказу СИУС в целом.
3. Проведен анализ возможности повышения вероятности безотказной работы выделенного диспетчера с помощью резервирования, который показал: - резервирование диспетчера в еще большей степени увеличивает аппаратные затраты; - для резервированного диспетчера требуется свой «диспетчер»; - все равно уменьшает вероятность безотказной работы СИУС, т.к. данная величина будет вычисляться путем перемножения двух величин, меньших 1, – вероятности безотказной работы ВУ и вероятности безотказной работы диспетчера.
4. Предложен способ распределенной организации диспетчера, лишенный перечисленных выше недостатков. Показано, что данный способ не требует ввода в состав СИУС дополнительных устройств для диспетчирования, так как предполагает наличие на всех ПУ СИУС специального локального диспетчера, который, взаимодействуя с ЛД других П У, осуществляет диспетчирование «своего» узла в «интересах» системы в целом.
5. Проведен анализ особенностей функционирования СИУС с распределенным диспетчером при различных способах организации вычислительного процесса в СИУС и получены оценочные выражения, определяющие временные затраты на реализацию основных режимов диспетчирования (тестирование, цикл управления, восстановление вычислительного процесса). Показано, что данные выражения могут быть использованы для выбора того или иного способа организации вычислительного процесса и его восстановления в случае возникновения отказа в зависимости от заданных значений времени Tц цикла управления, времени Tввп восстановления вычислительного процесса и времени Tп потери управления.
6. Выделены основные режимы функционирования локального диспетчера: тестирование, реконфигурация, решение задачи управления. Для каждого из режимов разработан алгоритм работы ЛД, реализуемый на отдельном ПУ.
7. Проведен анализ особенностей организации информационного обмена в СИУС с распределенным диспетчером, который показал, что из рассмотренных вариантов (обмен по принципу «каждый с каждым», обмен по принципу «каждый со всеми», обмен посредством выделенных «досок объявлений») наиболее подходящими являются обмен по принципу «каждый со всеми» (если имеется возможность передачи широковещательных сообщений) и обмен с использованием «досок объявлений» (при отсутствии возможности передачи широковещательных сообщений). Обмен по принципу «каждый с каждым» может быть использован только при небольшом числе ПУ в СИУС.
Постановка задачи реконфигурации СИУС Как показано в предыдущей главе, наиболее сложным этапом работы СИУС при возникновении отказа является этап реконфигурации, т.е. перераспределения подзадач графа G(Q,X) по работоспособности ПУ. От времени выполнения процедуры реконфигурации зависит время Т восстановления вычислительного ввп процесса в СИУС. Поскольку, как правило, на время Т наложены ограничения, ввп то время выполнения процедуры реконфигурации также должно быть ограничено, т.е. Трек Гзвп , где Гзвп - заданное время восстановления вычислительного процесса в СИУС. В общем виде задачу реконфигурации СИУС можно представить в следующем виде. Допустим, что в состав СИУС входит я основных ПУ, задействованных в решении задачи G(Q,X), и в резервных ПУ. Будем считать, что задача G(Q,X) каким-то образом была изначально распараллелена по основным ПУ, причем ПУ? (i = \,2,...,H) было «поручено» решение множества подзадач О О . Пусть произошел отказ L основных ПУ, задействованных в решении задачи управления G(Q,X) . Необходимо таким образом перераспределить (разместить) подзадачи множества О =Q по работоспособным ПУ (основным и резервным), чтобы время т цикла управления не превышало заданной величины Тцз , а вычислительная загрузка всех ПУ, задействованных в решении задачи управления, была приблизительно одинаковая, т.е. Результатом такого перераспределения (размещения) должна стать модифицированная таблица Т2, содержащая информацию о новом закреплении вершин графа G(Q,X) за ПУ, входящими в состав СИУС, которая будет использована при последующей реализации процедуры решения задачи управления на СИУС (см. параграф 3.3).
Следует отметить, что проблеме оптимального распределения (размещения) вершин графа задачи по процессорам многопроцессорной вычислительной системы посвящено достаточно большое число исследований [27], [116], [119,120], [142]. Однако большинство этих исследований ориентировано на реализацию разрабатываемых методов и алгоритмов с помощью центрального (специально выделенного) диспетчера. Нас же будут интересовать методы и алгоритмы распределения, реализуемые с помощью распределенного диспетчера, т.е. множества локальных диспетчеров ЛД,- (j = 1,2,...,Н - L) , установленных на отдельных ПУ.
Алгоритмы работы локальных диспетчеров при решении задачи реконфигурации СИУС будут в значительной степени зависеть как от соотношения числа я основных, в резервных и ь отказавших ПУ [121], так и от способа организации вычислительного процесса в СИУС.
Рассмотрим принципы организации процедуры реконфигурации при различных соотношениях я , В и L.
Сначала рассмотрим простейший случай, когда в L, т.е. число вышедших из строя (отказавших) основных ПУ меньше числа резервных ПУ. Для простоты рассуждений допустим, что L = 1, т.е. вышел из строя один основной ПУ, например ПУ?.
