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

ВВЕДЕНИЕ.

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

1.1. Структурная и функциональная организация матричного мультиконтроллера

1.2. Методы и алгоритмы отказоустойчивой маршрутизации.

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

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

2.1. Среда самоорганизации мультиконтроллера с размещением резерва по периметру.

2.1.1. Функции среды самоорганизации.

2.1.2. Алгоритм репродуцирования программы поведения мультиконтроллера.''.

2.2. Среда самоорганизации мультиконтроллера с гибким размещением столбца резервных элементов.

2.2.1. Механизм самоорганизации мультиконтроллера.

2.2.2. Клеточный алгоритм самоорганизации мультиконтроллера.

2.2.3. Функциональная организация среды самоорганизации мультиконтроллера.

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

ГЛАВА 3. РАЗРАБОТКА КОММУНИКАЦИОННОЙ СРЕДЫ САМООРГАНИЗАЦИИ ОБМЕННЫХ ВЗАИМОДЕЙСТВИЙ.

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

3.1.1. Модель конфигурированной среды с отказавшими элементами.

3.1.2. Содержательное описание поиска при неизвестном начальном состоянии среды.

3.1.3. Функции маршрутизатора коммуникационной среды.

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

3.1.5. Функциональная организация маршрутизатора.

3.1.6. Пример самоорганизации маршрута при отказах.

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

3.2.1. Содержательная характеристика метода поиска.

3.2.2. Параллельный алгоритм самоорганизации маршрута в конфигурированной среде с отказавшими элементами.

3.2.3. Пример поиска программного модуля в конфигурированной коммуникационной среде.

3.3. Алгоритм маршрутизации с локальной информацией об отказах

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

ГЛАВА 4. МОДЕЛИРОВАНИЕ И ИССЛЕДОВАНИЕ АЛГОРИТМОВ ОТКАЗОУСТОЙЧИВОЙ МАРШРУТИЗАЦИИ.

4.1. Исследование маршрутизации при неизвестном начальном состоянии среды.

4.2. Исследование маршрутизации при известном начальном состоянии среды.

4.3. Сравнительная оценка характеристик маршрутизации.

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

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

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

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

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

Для обеспечения функциональной целостности мультиконтроллера со сложной структурной организацией (в которых межмодульное взаимодействие осуществляется на основе транзитной передачи сообщений) требуется введение средств коммуникационного уровня, реализующих функции транспортного интерфейса для множества микроконтроллеров [4, 5]. Коммуникационная подсистема мультиконтроллера включает две составляющие, предназначенные для реализации процедур маршрутизации и ретрансляции сообщений. Функции указанных средств сводятся к следующему. Целью первой из названных процедур является выбор траектории (маршрута) передачи сообщения в пределах среды мультиконтроллера и непосредственное обеспечение перемещения по данному маршруту. Учитывая наличие множества вариантов доставки сообщений между одной и той же парой микроконтроллеров, средства маршрутизации должны обеспечивать выбор оптимального маршрута. Важным требованием к средствам маршрутизации является также обеспечение множества различных конфигураций маршрутов и возможность их динамического изменения в процессе функционирования мультиконтроллера [4].

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

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

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

Диссертационная работа выполнялась в рамках тематического плана госбюджетных НИР по Единому заказ-наряду Госкомвуза РФ Курского государственного технического университета.

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

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

1. Разработка подхода к поиску абонента по его логическому адресу (адресу программного модуля) с учётом метода самоорганизации.

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

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

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

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

6. Исследование разработанных алгоритмов маршрутизации.

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертационной работы обсуждались на: международной технической конференции «Медико-экологические информационные технологии» (Курск, 1998, 2001, 2003); второй Всероссийской научно-технической конференции «Информационные технологии в науке, проектировании и производстве» (Н.Новгород, 2000); научно-технической конференции «Распознавание» (Курск, 2001); четвёртой Всероссийской научно-технической конференции «Информационные технологии в науке, проектировании и производстве» (Н.Новгород, 2002); международной научной конференции «XXVIII Гагаринские чтения» (Москва, 2002); международной научно-технической конференции «Интеллектуальные САПР» (Таганрог, 2002).

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

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

1. Подход к поиску абонента по его логическому адресу с учётом метода самоорганизации

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

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

4. Новая структурно-функциональная организация клеточной отказоустойчивой среды маршрутизации мультиконтроллера.

5. Новая структурно-функциональная организация клеточной среды восстановления логической структуры отказоустойчивого мультиконтроллера.

Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения и списка литературы, включающего 92 источника, 18 из которых -отечественные, 74 - зарубежные. Работа изложена на 150 страницах, содержащих 78 рисунков и 18 таблиц.

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

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

2. Проведены исследования работы разработанных программных моделей при:

- различных формах отказовых ситуаций:

- различном расположении источника и приёмника относительно друг друга;

- различном количестве отказов;

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

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

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

5. Показаны существенные преимущества разработанных методов маршрутизации по сравнению другими известными алгоритмами.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

2. Клеточная самоорганизация программируемых отказоустойчивых муль-тимикроконтроллеров / М.В. Медведева, А.В. Медведев, B.A. Колосков, Ф.А. Старков, Курск, гуманит-техн. ин-т. Курск, 2000. 200 с.

3. Технология параллельных вычислений в распределённых средах реструктуризации мультикомпьютеров / В.А. Колосков, М.В. Медведева, Ф.А. Старков, Курск, гуманит-техн. ин-т. Курск, 2002

4. Организация и синтез микропрограммных мультимикроконтроллеров / И.В. Зотов, В.А. Колосков, B.C. Титов, К.А. Сапронов, А.П. Волков, Курск: Изд-во «Курск», 1999. 368 с.

5. Колосков В.А. Основы теории и принципы построения отказоустойчивых самоорганизующихся логических мультимикроконтроллеров / Дисс. на соискание учёной степени д-ра техн. наук. Курск, КГТУ, 1998. 367 с.

6. Jia W., Zhao W., Xuan D., XuAn G. Efficient Fault-Tolerant Multicast Routing Protocol with Core-Based Tree Techniques // IEEE Transactions on Parallel and Distributed Systems. 1999. - Vol. 10.-№ 10. - P. 984-1000

7. Choo H., Yoo S.-M., Youn H.-Y. Processor Scheduling and Allocation for 3D Torus Multicomputer Systems // IEEE Transactions on Parallel and Distributed Systems. 2000. - Vol. 11. - № 5. - P. 475-484

8. Kaufmann M., Sibeyn J.F. Randomized multi-packet routing and sorting on meshes // Algorithmica. 1997. - Vol. 17. - P. 224-244

9. Hauck S., Borriello G., Ebeling C. Mesh Routing Topologies for FPGA Arrays // Proceedings of the 2nd International Workshop on Field-Programmable Gate Arrays. 1994. - P. 170-177

10. O.Park H., Agrawal D.P. Generic Methodologies for Deadlock-Free Routing // Proceedings of the 10th International Parallel Processing Symposium. 1996. -P. 638-643

11. Chang C.-Y., Mohapatra P. An Efficient Method for Approximating Submesh Reliability of Two-Dimensional Meshes // IEEE Transactions on Parallel and Distributed Systems. 1998. - Vol. 9. - № 11. - P. 1115-1124

12. Strieker T. Message Routing on Irregular 2D-meshes and Tori. // Proceeding of the 6th Distributed Memory Computing Conference. 1991. - P. 170-177

13. Stout Q.F. Ultrafast Parallel Algorithms and Reconfigurable Meshes // Proceeding of the DARPA Sortware Technology Conference. 1992. - P. 184188

14. DeHon A., Knight T.J., Minsky H. Fault-Tolerant Design for Multistage Routing Networks // Proceeding of the International Symposium on Shared Memory Multiprocessing. 1991. - P. 483-501

15. Avizienis A. Toward Systematic Design of Fault- Tolerant Systems // IEEE Computer. 1997.-Vol. 30.-№4.-P. 51-58

16. Chiu G.-M. The Odd-Even Turn Model for Adaptive Routing // IEEE Transactions on Parallel and Distributed Systems. 2000. - Vol. 11. - № 7. - P. 729-738

17. Choi Y., Pinkston T.M. Evaluation of Crossbar Architectures for Deadlock Recovery Routers // Journal of Parallel and Distributed Computing. 2001. -Vol. 61. - № 1. - P. 49-78

18. Mudawwar M. A Switch-Free Router for k-ary m-way Networks // Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications. 2000. - P. 977-983

19. Ejnioui A., Ranganathan N. Routing on Switch Matrix Multi-FPGA Systems // Proceedings of the International Conference on VLSI Design. 2000. - P. 248-253

20. Seo S.-W., Feng T.-Y., Lee H.-I. Permutation Realizability and Fault Tolerance Property of the Inside-Out Routing Algorithm // IEEE Transactions on Parallel and Distributed Systems. 1999. - Vol. 10. - № 9. - P. 946-957

21. Sum J., Shen H., Young G.H., Wu J., Leung C.-S., Analysis on extended ant routing algorithms for network routing and management // The Journal of Su-percomputing. 2003. -Vol. 24.-№3.-P. 327-340

22. Lee D., Moon D., Yun I., Kim H. A Fault-Tolerant Deadlock-Free Routing Algorithm in a Meshed Network // IEICE Transactions on Information and Systems. 2002. - Vol. E85-D. - № 4. - P. 722-726

23. Nesson Т., Johnsson S.L. ROMM Routing on Mesh and Torus Networks // Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures. 1995. - P. 275-287

24. Takabatake Т., Kitakami M., Ito H. Escape and Restoration Routing: Suspensive Deadlock Recovery in Interconnection Networks // IEICE Transactions on Information and Systems. 2002. - Vol. E85-D. - № 5. - P. 824-832

25. Suh Y.-J., Yalamanchili S. Configurable Algorithms for Complete Exchange in 2D Meshes // IEEE Transactions on Parallel and Distributed Systems. -2000. Vol. 11. - № 4. - P. 337-356

26. Moh S., Yu C., Lee В., Youn H.Y., Han D., Lee D. Four-Ary Tree-Based Barrier Synchronization for 2D Meshes without Nonmember Involvement // IEEE Transactions on Computers. 2001. - Vol. 50.-№ 8.-P. 811-823

27. Zhou J., Lau F.C.M. Adaptive Fault-tolerant Wormhole Routing in 2D Meshes // Proceedings of the 15th International Parallel & Distributed Processing Symposium. 2001. - P. 56-64

28. Olson A., Shin K.G. Fault-Tolerant Routing in Mesh Architectures // IEEE Transactions on Parallel and Distributed Systems. 1994. - Vol. 5. - № 11.-P. 1225-1232

29. Soch M., Tvrdik P. Time-Optimal Gossip of Large Packets in Noncombining 2D Tori and Meshes // IEEE Transactions on Parallel and Distributed Systems. 1999.-Vol. 10.-№ 12.-P. 1252-1261

30. Vaidya A.S., Das C.R., Sivasubramaniam A. A Testbed for Evaluation of Fault-Tolerant Routing in Multiprocessor Interconnection Networks // IEEE Transactions on Parallel and Distributed Systems. 1999. - Vol. 10. - № 10. -P. 1052-1066

31. Chen H.-L., Hu S.-H. Submesh Determination in Faulty Tori and Meshes // IEEE Transactions on Parallel and Distributed Systems. 2001. - Vol. 12. -№ 3. - P. 272-282

32. Meyer U., Sibeyn J.F. Oblivious Gossiping on Tori. // Algorithms. 2002. -Vol. 42.-№ l.-P. 1-19

33. Tseng Y.-C., Yang M.-H., Juang T.-Y. Achieving Fault-Tolerant Multicast in Injured Wormhole-Routed Tori and Meshes Based on Euler Path Construction // IEEE Transactions on Computers. 1999. - Vol. 48. - № 11. - P. 12821296

34. Chen Y.-S., Chen C.-Y., Tseng Y.-C. Multi-Node Broadcasting in a Wormhole-Routed 2-D Torus Using an Aggregation-then-Distribution Strategy // Proceedings of the International Workshops on Parallel Processing. 1999. -P. 50-51

35. Yang Y., Funahashi A., Jouraku A., Nishi H., Amano H., Sueyoshi T. Recursive Diagonal Torus: An Interconnection Network for Massively Parallel Computers // IEEE Transactions on Parallel and Distributed Systems. 2001. -Vol. 12.-№ 7.-P. 701-715

36. Dolter J.W., Ramanathan P., Shin K.G. Performance Analysis of Virtual Cut-Through Switching in HARTS: A Hexagonal Mesh Multicomputer // IEEE Transactions on Computers. 1991. - Vol. 40. - № 6. - P. 669-680

37. Tsai M.-J., Wang S.-D. Adaptive and Deadlock-Free Routing for Irregular Faulty Patterns in Mesh Multicomputers // IEEE Transactions on Parallel and Distributed Systems. 2000. - Vol. 11. - № 1. - P. 50-63

38. Shin K.-G., Chou C.-C., Kweon S.-K. Distributed Route Selection for Establishing Real-Time Channels // IEEE Transactions on Parallel and Distributed Systems. 2000. - Vol. ll.-№3.-P. 318-335

39. Chen C.-L., Chiu G.-M. A Fault-Tolerant Scheme for Meshes with Noncon-vex Faults 11 IEEE Transactions on Parallel and Distributed Systems. 2001. -Vol. 12. -№5.-P. 467-475

40. Kim S.-P., Han T. Fault-Tolerant Wormhole Routing in Mesh with Overlapped Solid Fault Regions // Parallel Computing. 1997. - Vol. 23. - P. 1937-1962

41. Kim J., Kim J.-Y., Yoon H., Maeng S.R., Cho J.W. A Fault-Tolerant Worm-hole Routing Algorithm in Two Dimensional Mesh Networks // IEICE Transactions on Information and Systems. 1998. - Vol. E81-D. - № 6. - P. 532544

42. Park S., Youn J.-H., Bose B. Fault-Tolerant Wormhole Routing Algorithms in Meshes in the Presence of Concave Faults // Proceedings of the 14th International Parallel and Distributed Processing Symposium. 2000. - P. 633-640

43. Suh Y.-J., Dao B.V., Duato J. Software-Based Rerouting for Fault-Tolerant Pipelined Communication // IEEE Transactions on Parallel and Distributed Systems. 2000. - Vol. ll.-№3.-P. 193-211

44. Khan G.N., Wei G. Fault-tolerant Wormhole Routing using a Variation of Distributed Recovery Block Approach // IEE Proceeding Computers and Digital Techniques. 2000. - Vol. 147. - № 6. - P. 397-402

45. Boppana R.V., Chalasani S. Fault-Tolerant Communication with Partitioned Dimension-Order Routers // IEEE Transactions on Parallel and Distributed Systems. 1999. - Vol. 10. - № 10. - P. 1026-1039

46. Halwan V., Ozguner F., Dogan A. Routing in Wormhole-Switched Clustered Networks with Applications to Fault Tolerance // IEEE Transactions on Parallel and Distributed Systems. 1999. - Vol. 10. -№ 10. - P. 1001-1011

47. Su C.-C., Shin K.G. Adaptive Deadlock-Free Routing in Multicomputers Using Only One Extra Virtual Channel // Proceedings of the International Conference on Parallel Processing. 1993. - P. 227-231

48. Horita Т., Takanami I. A System for Efficiently Self-Reconstructing 1,5-Track Switch Torus Arrays // IEICE Transactions on Information and Systems. -2001.-Vol. E84-D.-№? 11.-P. 1801-1809

49. Dao B.V., Duato J., Sudhakar Y. Dynamically Configurable Message Flow Control for Fault-Tolerant Routing // IEEE Transactions on Parallel and Distributed Systems. 1999. - Vol. 10. - № 1. - P. 7-22

50. Qiao W., Lionel L.M., Rokicki T. Adaptive-Trail Routing and Performance Evaluation in Irregular Networks Using Cut-Through Switches // IEEE Transactions on Parallel and Distributed Systems. 1999. - Vol. 10. - № 11. - P. 1138-1158

51. Suh Y.-S., Shin K.G. Efficient All-to-All Personalized Exchange in Multidimensional Torus Networks // Proceedings of the International Conference on Parallel Processing. 1998. - P. 468-476

52. Wu J. Fault-Tolerant Adaptive and Minimal Routing in Mesh-Connected Multicomputers Using Extended Safety Levels // IEEE Transactions on Parallel and Distributed Systems. 2000. - Vol. 11.-№2. -P. 149-159

53. Типикин А.П., Малышев A.B., Тараненко К.Ю. Самообучение автоассоциативной модели нейронной сети высокого порядка // Известия Курского государственного технического университета, 1998. №2. С. 63-69

54. Иванов С.Н., Малышев А.В., Типикин А.П. Макси-минная обработка распознаваемых речевых сигналов // Медико-экологические информационные технологии: Сборник материалов международной технической конф. Курск: КГТУ, 1998. С. 154-156

55. Малышев А.В., Миневич JI.M., Колосков В.А. Метод маршрутизации сообщений в отказоустойчивом мультимикроконтроллере // Сборник материалов н.-т. конф. «Медико-экологические информационные технологии». Курск, 2001. С. 216-217

56. Малышев А.В., Миневич JI.M., Колосков В.А. Маршрутизация сообщений в отказоустойчивом мультимикроконтроллере // Сборник материалов н.-т. конф. «Распознавание». Курск, 2001.

57. Колосков В.А., Медведева М.В., Малышев А.В. Клеточная самоорганизация и отказоустойчивость // Сборник материалов Международной н.-т. конф. «Интеллектуальные САПР». Таганрог, 2002. С. 525-531

58. Савенков Н.А, Малышев А.В., Колосков В.А. Алгоритм маршрутизации в самоорганизующихся управляющих структурах // Сварка и родственные технологии в машиностроении и электронике. Курск: КГТУ, 2003.

59. Малышев А.В., Медведева М.В., Колосков В.А. Поиск абонента в мультиконтроллере с репродуцированной программой поведения // Телекоммуникации. 2002, №5

60. Малышев А.В., Колоскова Г.П. Алгоритмы передачи сообщений в коммутационной перестраиваемой среде // Сборник материалов н.-т. конф. «Медико-экологические информационные технологии». Курск, 2003. С. 220-224

61. Колосков В.А., Малышев А.В. Нейронная сеть самоорганизации мульти-микроконтроллера // Тез. докл. второй Всероссийской н.-т. конф. «Информационные технологии в науке, проектировании и производстве». Н.Новгород, 2000. С. 1

62. Малышев А.В. Адаптационный алгоритм самоорганизации обменных взаимодействий в мультимикроконтроллерной сети // Тез. докл. Международной научной конференции «XXVIII Гагаринские чтения». Москва, 2002.

63. Патент Российской Федерации №2185656. Распределённая система для программного управления // А.В. Малышев, М.В. Медведева, J1.M. Ми-невич, В.А. Колосков. Изобретения, 2002.

64. Патент Российской Федерации №2177169. Ячейка однородной среды процессорных элементов // А.В. Малышев, М.В. Медведева, J1.M. Мине-вич, В.А. Колосков. Изобретения, 2000.

65. Duato J., Pinkston Т.М. A General Theory for Deadlock-Free Adaptive Routing Using a Mixed Set of Resources // IEEE Transactions on Parallel and Distributed Systems.-2001.-Vol. 12.-№ 12.-P. 1-17

66. Sun J., Modiano E. Capacity Provisioning and Failure Recovery in Mesh-Torus Networks with Application to Satellite Constellations // Proceedings of the Seventh International Symposium on Computers and Communications. -2002. P. 77-84

67. Wu. J. A Fault-Tolerant Adaptive and Minimal Routing Approach in n-D Meshes 11 Proceedings of the International Conference on Parallel Processing. -2000.-P. 431-438

68. Lau F.C.M., Cheng P.K.W., Tse S.S.H. An Algorithm for the 2-Median Problem on Two-Dimensional Meshes // The Computer Journal. 2001. - Vol. 44.- № 2. P. 101-108

69. Tsuda N. Fault-Tolerant Ring- and Toroidal Mesh-Connected Processor Arrays Able to Enhance Emulation of Hypercubes // IEICE Transactions on Information and Systems. -2001. Vol. E84-D. -№ 11. - P. 1452-1461

70. Fleury E., Fraigniaud P. A General Theory for Deadlock Avoidance in Worm-hole-Routed Networks // IEEE Transactions on Parallel and Distributed Systems. 1998. - Vol. 9. - № 7. - P. 626-638

71. AlMohammad B.F.A., Bose B. Fault-Tolerant Communication Algorithms ir Toroidal Networks // IEEE Transactions on Parallel and Distributed Systems- 1999. Vol. 10. - № 10. - P. 976-983

72. Barcaccia P., Bonuccelli M.A., Ianni M.D. Complexity of Minimum Lengtl Scheduling for Precedence Constrained Messages in Distributed Systems /

73. EE Transactions on Parallel and Distributed Systems. 2000. - Vol. 11.-№ 10.-P. 1090-1102

74. Aronson L.D. Homogeneous Routing for Homogeneous Traffic Patterns on Meshes // IEEE Transactions on Parallel and Distributed Systems. 2000. -Vol. 11. - № 8.-P. 781-793

75. Bock S., Meyer F., Scheideler C. Optimal Wormhole Routing in the (n,d)-Torus // Proceedings of the 11th International Parallel Processing Symposium. 1997.-P. 326-332

76. Karri R., Kim K., Potkonjak M. Computer Aided Design of Fault-Tolerant Application Specific Programmable Processors // IEEE Transactions on Computers. -2000. -Vol. 49. -№ п. p. 1272-1284

77. Bertossi A.A., Mei A. A Residue Number System on Reconfigurable Mesh with Applications to Prefix Sums and Approximate String Matching // IEEE Transactions on Parallel and Distributed Systems. 2000. - Vol. 11. - № 11. -P. 1186-1199

78. Shigei N., Miyajima H. Reconfiguration Classes and an Optimal Reconfiguration Method within a Reconfiguration Class // IEICE Transactions on Information and Systems. 2002. - Vol. E85-D. - № 12. - P. 1909-1917

79. Hayashi Т., Nakano K, Olariu S. An 0((log log n)2) Time Algorithm to Compute the Convex Hull of Sorted Points on Reconfigurable Meshes // IEEE Transactions on Parallel and Distributed Systems. 1998. - Vol. 9. - № 12. -P. 1167-1179

80. Towles В., Dally W.J. Worst-case traffic for oblivious routing functions // Proceedings of the ACM Symposium on Parallel Algorithms and Architectures. 2002. - P. 1-8

81. Moritz C.A., Frank M.I. LoGPC: Modeling Network Contention in Message-Passing Programs // IEEE Transactions on Parallel and Distributed Systems. -2001.-Vol. 12.-№4. p. 404-415

82. Azizoglu M.C., Egecioglu О. Lower Bounds on Communication Loads and Optimal Placements in Torus Networks // IEEE Transactions on Computers. -2000. Vol. 49. - № 3. - P. 259-266

83. Nitzberg В., Kuszmaul C., Stockdale I., Becker J., Jiang J., Wong P. The P-Mesh-A Commodity-based Scalable Network Architecture for Clusters // Proceedings of the Thirty-second Annual Hawaii International Conference on System Sciences. 1999. - P. 8039

84. Wang S.-Y., Tseng Y.-C., Ni S.-Y., Sheu J.-P. Circuit-Switched Broadcast in Multi-Port 2D Tori // Proceedings of the 7th International Conference on High-Performance Computing and Networking. 1999. - P. 1159-1162

85. Wang S., Tseng Y.-C. Algebraic Foundations and Broadcasting Algorithms for Wormhole-Routed All-Port Tori // IEEE Transactions on Computers. -2000. Vol. 49. - № 3. - P. 246-258

86. Suh Y.-J., Shin K.G. All-to-All Personalized Communication in Multidimensional Torus and Mesh Networks // IEEE Transactions on Parallel and Distributed Systems.-2001.-Vol. 12.-№ 1.-P. 38-59

87. Dolter J.W., Ramanathan P., Shin K.G. Performance Analysis of Virtual Cut-Through Switching in HARTS: A Hexagonal Mesh Multicomputer // IEEE Transactions on Computers. 1991. - Vol. 40. - № 6. - P. 669-680

88. DeHon A. Scan-Based Testability for Fault-Tolerant Architectures // Proceedings of the IEEE International Workshop on Defect and Fault Tolerance in VLSI Systems. 1992. - P. 90-99

89. Bertossi A.A., Mei A. Constant Time Dynamic Programming on Directed Re-configurable Networks // IEEE Transactions on Parallel and Distributed Systems. 2000. - Vol. 11. - № 6. - P. 529-536

90. Low C.P. An Efficient Reconfiguration Algorithm for Degradable VLSI/WSI Arrays // IEEE Transactions on Computers. 2000. - Vol. 49. - № 6. - P. 553-559