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

ВВЕДЕНИЕ.

ГЛАВА 1. ПОДХОД К САМОСИНХРОНИЗАЦИИ ОТКАЗОУСТОЙЧИВЫХ МУЛЬТИМИКРОКОНТРОЛЛЕРОВ.

1.1. Структурная и алгоритмическая организация отказоустойчивых мул ьтимикроконтролл еров.

1.2. Анализ процесса реконфигурации мультимикроконтроллеров.

1.3. Подход к самосинхронизации мультимикроконтроллеров.

1.4. Выводы к главе.

ГЛАВА 2. РАЗРАБОТКА АЛГОРИТМОВ САМОСИНХРОНИЗАЦИИ

МУЛЬТИМИКРОКОНТРОЛЛЕРОВ.

2.1. Графовые модели для решенияЪаДач самосинхронизации.

2.2. Формирование маршрутов передачи синхронизирующих сообщений.

2.3. Разработка клеточного автомата обработки синхронизирующих сообщений.

2.4. Формирование маршрутов обновления контекстов.

2.5. Разработка клеточного автомата обновления контекстов.

2.6. Выводы к главе.

ГЛАВА 3. РАЗРАБОТКА АЛГОРИТМА ОТКАТОУСТОЙЧИВОГО

ФОРМИРОВАНИЯ КОНТЕКСТА САМОСИНХРОНИЗАЦИИ.

3.1. Определение мощности компонент контекста микроконтроллера.

3.2. Организация откатоустойчивого формирования контекста самосинхронизации.

3.3. Разработка клеточного автомата формирования изменений контекста.

3.4. Оценка характеристик отказоустойчивого мультимикроконтроллера со средствами самосинхронизации.

3.5. Выводы к главе.

ГЛАВА 4. РАЗРАБОТКА АППАРАТНЫХ СРЕДСТВ

САМОСИНХРОНИЗАЦИИ МУЛЬТИМИКРОКОНТРОЛЛЕРОВ.

4.1. Организация многофункционального микроконтроллера.

4.2. Функциональная организация отказоустойчивого самосинхронизирующегося мультимикроконтроллера.

4.3. Выводы к главе.

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

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

ПЛИС представляют собой микропрограммируемые или программируемые устройства управления, сочетающие высокое быстродействие управляющих устройств с жесткой логикой и гибкость программируемых логических контроллеров. Объединение ПЛИС в регулярную сеть, представляющую собой мультимикроконтроллер (ММК), позволяет реализовать групповое логическое управление и эффективно реализовывать сложные логические алгоритмы.

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

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

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

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

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

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

Для достижения поставленной цели в диссертационной работе решались следующие задачи:

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

2. Разработка алгоритма распределенной обработки синхронизирующих сообщений в микроконтроллерной сети с отказами.

3. Разработка алгоритмов распределенной подстройки когерентности копий состояний управляющих процессов в микроконтроллерах скользящего резерва и формирования контекста управляющего процесса.

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

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

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

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

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

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

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

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

Реализация и внедрение результатов диссертационной работы. Данная работа выполнена в соответствии с программой П.Т.614 «Многопроцессорные ЭВМ с параллельной структурой и системы виртуальной реальности» (приказ министерства общего и профессионального образования № 572 от 02.03.98 г.) по направлению «Самоорганизующиеся отказоустойчивые многопроцессорные устройства».

Полученные в диссертационной работе результаты были внедрены на предприятии ОАО «Электроагрегат» (г. Курск).

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих семинарах: на 23-й Всероссийской молодежной научной конференции «Гагаринские чтения» (г. Москва, 1997 г.) , III Международной научно-технической конференции «Новые информационные технологии и системы» (г. Пенза, 1998 г.), I Всероссийской научно-техническая конференция «Компьютерные технологии в науке, проектировании и производстве» (г. Нижний Новгород, 1999 г.), III Международной научно-технической конференции «Вибрационные машины и технологии» (г. Курск, 1997 г.), 3-й Международной конференции «Распознавание — 97» (г. Курск, 1997 г.), V Научно-технической конференции с международным участием «Материалы и упрочняющие технологии — 97» (г. Курск,

1997г.), Международной технической конференции «Медико-экологические информационные технологии» (г. Курск, 1998 г.), VI Российской научно-технической конференции «Материалы и упрочняющие технологии — 98» (г. Курск, 1998 г.).

Публикации. Основные результаты диссертационной работы опубликованы в 2 статьях, 12 тезисах и материалах докладов и защищены 2 патентами.

Основные научные положения, выносимые на защиту.

1. Модель распределенной самосинхронизации отказоустойчивого мультимикроконтроллера.

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

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

4. Структурно-функциональная организация отказоустойчивого самосинхронизирующегося мультимикроконтроллера и результаты сравнительного анализа отказоустойчивых самосинхронизирующихся структур.

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

4.3. Выводы к главе

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

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

ЗАКЛЮЧЕНИЕ

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

При решении задачи в диссертационной работе получены следующие результаты.

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

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

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

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

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

123

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

1. Надежность технических систем: Справочник / Ю.К. Беляев, В.А. Богатырев, В.В. Болотин; Под. ред. H.A. Ушакова. М.: Радио и связь, 1985. 608 с.

2. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах / Под ред. В.И. Варшавского. М.: Наука, 1986.

3. Sami M.G., Stefaneiii R. Reconfigurable architectures for VLSI processing.arrays. // Proceedings of the IEEE. 1986, May, pp. 712—722.

4. Сами M., Стефанелли P. Перестраиваемые архитектуры матричных процессорных СБИС // ТИИЭР. — 1986. — №5. — С.107—118.

5. Кун С. Матричные процессоры на СБИС. М.: Мир, 1991. 672 с.

6. Каган Б.М. Электронные вычислительные машины и системы. — М.: Энергоатомиздат, 1985. — 552 с.

7. Каган Б.М., Мкртумян И.Б. Основы эксплуатации ЭВМ. — М.: Энергоатомиздат, 1985. — 552 с.

8. Корнеев В.В. Архитектура вычислительных систем с программируемой структурой. —Новосибирск: Наука, 1985. — 176 с.

9. Лазарев В.Г., Пийль Е.И., Турута E.H. Построение программируемых управляющих устройств. —М.: Энергоатомиздат, 1984. — 192 с.

10. Баумс A.K. Оценка распределенных систем реального времени по их относительной гибкости // Автоматика и вычислительная техника. — 1996.6. — С. 45—53.

11. Баумс А.К. О планировании задач и времени реакции распределенных систем реального времени // Автоматика и вычислительная техника. — 1998. — №3, — С. 50—59.

12. И.Денисов С.Г., Турута E.H. Восстановление вычислительных процессов в многопроцессорной системе на основе их реактивизации // Управление ресурсами в интегрированных сетях. М.: Ин-т проблем передачи информации. — 1991. — С. 117—129.

13. Мамедли Э. М., Соболев Н. А. Механизмы операционных систем, обеспечивающие отказоустойчивость в управляющих многомашинных вычислительных системах // Автоматика и вычислительная техника. — 1995. — № 8.— С. 3—63.

14. Мишель Ж. Программируемые контроллеры: Архитектура и применение.

15. М.: Машиностроение, 1992. — 320 с.

16. Эванз Р., Макхуэртер Дж. Иерархическая стратегия тестирования самоорганизующихся отказоустойчивых матриц / Систолические структуры:i

17. Пер. с англ. / Под ред. У. Мура, Маккейба, Р. Уркхарта. — М.: Радио и связь, 1993. — С. 264—276.

18. Димитриев Ю.К. Самодиагностика модульных вычислительных систем. Новосибирск: ВО «Наука». Сибирская издательская фирма, 1993. — 293 с.

19. Согомонян Е.С., Слабаков Е.В. Самопроверяемые и отказоустойчивые системы. — М.: Радио и связь, 1989. — 208 с.

20. Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.454с.21.0ре О. Теория графов. — М.: Наука. Главная редакция физико?математической литературы, 1980. — 336с.

21. Мальцев А.И. Алгоритмы и рекурсивные функции. — М.: наука, 1965.

22. Тоффоли Т., Марголус Н. Машины клеточных автоматов: Пер. с англ. М.: Мир, 1991.280 с.

23. Preston К., Duff M.J.B., Levialdi S., Norgren Ph.E., Toriwaki J. Basics of Cellular Logic with Some Applications in Medical Image Processing. // Proceedings of the IEEE. 1979, May, pp. 826—856.

24. Randell B. System structure for software fault-tolerance // IEEE Trans. Soft. Eng. — 1975. — Vol. SE-1, № 1. — P. 220—232.

25. Merlin P.M., Randell В. State restoration in distributed systems // Proc. FTCS-8, — 1978, —P. 129—137.

26. Антола А., Скаработолло H. Ретроспективное устранение ошибок в распределенных системах // Автоматика и вычислительная техника. — 1986.2, —С. 25—32.

27. Arora A., Gouda M.G. Distributed reset // ШЕЕ Trans, on Comp. Sep. — 1994.

28. V. 43 — № 9. — P. 1026—1038.

29. Васильев B.P., Романовский А.Б., Штурц И.В. Динамические беседы асинхронных процессов // Автоматика и вычислительная техника. — 1990.3. —С. 26—33.

30. Гостилова C.B., Никитин А.И. Глобальное состояние распределенной базы данных и глобальная контрольная точка // Управляющие системы и машины. — 1991. — № 8. — С. 68—76.

31. Карпов Ю.Г. Синтез алгоритмов распределенного завершения // Автоматика и телемеханика. — 1991. — № 1. — С. 174—184.

32. Штурц И.В., Романовский А.Б., Васильев В.Р. Программные методы и средства повышения отказоустойчивости управляющих вычислительных систем // Управляющие системы и машины. — 1988. — № 3. — С. 30—36.

33. Штурц И.В., Романовский А.Б., Васильев В.Р. Модель отката асинхронных процессов в вычислительных сетях // Автоматика и вычислительная техника, — 1989. — № 4. — С. 63—68.

34. Иыуду К.А. Надежность, контроль и диагностика вычислительных машин и систем. — М.: Высшая школа, 1989. — 216 с.

35. Иыуду К.А., Кривощеков С.А. Математические модели отказоустойчивых вычислительных систем. — М.: Изд-во МАИ, 1989. — 144 с.

36. Харченко B.C., Мельников В.А. и др. Микропрограммное устройство управления / A.c. 1133595 СССР G 06 F 9/22; G 06 F 11/00; опубл. 07.01.85, БИ№1.

37. Харченко B.C., Улитенко В.П. и др. Микропрограммный модуль / A.c. 1427366 СССР G 06 F 9/22; опубл. 30.09.88, БИ № 36.

38. Харченко B.C., Тимонькин Г.Н. и др. Модульное устройство для программного управления и контроля / A.c. 1647519 СССР G 05 В 19/18; опубл. 07.05.91, БИ №17.

39. Харченко B.C., Никольский С.Б. и др. Микропрограммное устройство управления / A.c. 1168936 СССР G 06 F 9/22; опубл. 23.07.85, БИ №27.

40. Улитенко В.П., Тимонькин Г.Н. и др. Микропрограммное устройствоIуправления модуля распределенной параллельной вычислительной системы / A.c. 1252775 СССР G 06 F 9/22; опубл. 23.08.86, БИ №31.

41. Гремальский A.A. Мультимикропрограммная управляющая система /A.c. 1631542 СССР G 06 F 9/22, 9/00; опубл. 28.02.91, БИ №8.

42. Гремальский A.A. Микропрограммное устройство управления / A.c. 1647566 СССР G 06 F 9/22; опубл. 07.05.91, БИ №17.

43. Мельников В.А., Харченко B.C. и др. Устройство для формирования маршрута сообщения в однородной вычислительной системе / A.c. 1508228 СССР G 06 F 15/16; опубл. 15.09.89, БИ № 34.

44. Мельников В.А., Харченко B.C. и др. Распределенная система для программного управления технологическими процессами / A.c. 1605212 СССР G 05 В 19/18; опубл. 07.11.90, БИ№41.

45. Колосков В. А. Однородные управляющие самодиагностируемые сети с оперативной перестройкой // Микропроцессорные системы связи и управления на ж/д транспорте (тезисы докл. школы — семинара.). — Харьков, 1994, —С. 37.

46. Колосков В.А., Титов B.C. Архитектура отказоустойчивых сетей самонастраиваемых микроконтроллеров. — Курск: КГТУ, 1995. — 176 с.

47. Функционально-топологическая организация микропрограммных мультимикроконтроллеров группового логического управления / И.В. Зотов,

48. B.А. Колосков, B.C. Титов, И.В. Абузова; Тул. гос. ун-т. Тула. 1997. — 226 с.

49. Колосков В.А., Титов B.C. Управляющая система с самоорганизующим слоем // Автометрия. — 1997. — № 4. — С. 113—120.

50. Колосков В.А., Титов B.C. Методы самоорганизации отказоустойчивой мультимикроконтроллерной сети // Автоматика и телемеханика. — 1998. — №3. С. 173—183.

51. Колосков В.А., Колоскова Т.П., Титов B.C. Саморемонт и самосинхронизация логических микроконтроллерных сетей // Изв. вузов. Приборо-строениё. — 1997. — № 2. — С. 43-46.

52. Колосков В.А. Метод восстановления логической структуры мультимикроконтроллерной сети // Изв. КурскГТУ. — 1997. — № 1. — С. 82—89.

53. Колосков В.А., Титов B.C. Самосинхронизация адаптивной логической микроконтроллерной сети // Новые информационные технологии и системы : Материалы докладов международной конф. — Пенза: ПГТУ, 1994. —1. C. 71—72.

54. Колосков В.А. Согласованный откат параллельных взаимодействующих процессов // Сборник материалов 2-ой Международной конференции «Распознавание — 95». — Курск, 1985. — С. 235—237.

55. Миневич JI.M., Медведев A.B. Инструментальная программная система компоновки дискретных устройств из ПЛИС // Сб. 23. Гагаринские чтения. Всеросс. научн. конф. — М., 1997. — 4.1. — С. 28.

56. Колосков В.А., Миневич Л.М. Маршрутизация сообщений в отказоустойчивой микроконтроллерной сети вибрационного стенда // Вибрационные машины и технологии. Сб. докл. III Международной научно-технической конференции. — Курск: КГТУ, 1997. — С. 245—247.

57. Колосков В.А., Медведева М.В., Миневич Л.М. Адаптивная настройка процессора системы технического зрения // Сборник материалов 3-й Международной конференции «Распознавание -— 97». — Курск: КГТУ, 1997.1. С. 20Ö—203.

58. Колосков В.А., Медведева М.В., Медведев A.B., Миневич JIM., Титов

59. B.C. Графоструктуриые основы построения отказоустойчивых самоорганизующихся мультимикроконтроллеров / Курск, гос. техн. ун-т. — Курск, 1997. — 32 с. — Деп. в ВИНИТИ 14.05.97, № 1600-В97.

60. Медведева М.В., Миневич Л.М., Колоскова Г.П. Виртуальная перезагрузка логической структуры в матрице мультипроцессора // Сб. докл. Международной технической конференции «Медико-экологические информационные технологии». — Курск: КГТУ, 1998. — С.187—189.

61. Миневич Л.М. Особенности самосинхронизации отказоустойчивого матричного мультимикроконтроллера // VI Российская научно-техническая конференция «Материалы и упрочняющие технологии — 98». Тезисы и материалы докладов. — Курск: КГТУ, 1998. — С.252—254.

62. Миневич Л.М. Обновление очередей сообщений в реконфигурируемом мультимикроконтроллере // VI Российская научно-техническая конференция «Материалы и упрочняющие технологии — 98». Тезисы и материалы докладов. — Курск: КГТУ, 1998. — С.254—255.

63. Миневич JIM., Колосков В.А. Организация самовосстановления отказоустойчивых мультимикроконтроллеров // Материалы III Международной научно-технической конференции «Новые информационные технологии и системы». — Пенза: ПТУ, 1998. — С.77—78.

64. Медведева М.В., Медведев A.B., Миневич JIM., Колосков В.А. Принципыпостроения слоя самоорганизации на основе графоструктурного подхода //

65. Известия ТулГУ. Серия «Вычислительная техника. Автоматика. Управление». — Тула: ТГУ, 1998.

66. Патент РФ № 2122229. МК G 05 В 19/18, G 06 F 9/28. Распределенная система для программного управления / Миневич JI.M. и др. — Бюл. 1998. — №32.

67. Патент РФ № 2133054. МК G 05 В 19/18, G 06 F 9/28. Распределенная система для программного управления / Миневич JI.M. и др. -— Бюл. 1999. — № 19.