Алгоритм и устройство маршрутизации в логической структуре отказоустойчивого мультиконтроллера
Диссертация
Следует отметить, что существующие мультиконтроллерные устройства управления, спроектированные без учета возможных последствий отказов и даже построенные на основе высоконадежных элементов, не в полной мере удовлетворяют требованиям отказоустойчивости. Мультиконтроллер должен обеспечивать восстановление логической структуры на аппаратном (микроархитектурном) уровне организации, не затрагивая… Читать ещё >
Содержание
- ГЛАВА 1. АНАЛИЗ ПРОБЛЕМ МАРШРУТИЗАЦИИ В
- МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СРЕДАХ
- 1. 1. Существующие многопроцессорные архитектуры
- 1. 2. Задачи маршрутизации
- 1. 3. Маршрутизация в отказоустойчивых самоорганизующихся системах
- 1. 4. Обзор и классификация существующих алгоритмов маршрутизации
- 1. 5. Выводы к главе
- ГЛАВА 2. РАЗРАБОТКА АЛГОРИТМА МАРШРУТИЗАЦИИ В ОТКАЗОУСТОЙЧИВОМ РЕКОНФИГУРИРУЕМОМ МУЛЬТИКОНТРОЛЛЕРЕ
- 2. 1. Механизм взаимодействия среды самоорганизации и маршрутизации
- 2. 2. Алгоритм самоорганизации мультиконтроллера
- 2. 3. Алгоритм адаптивной маршрутизации
- 2. 3. 1. Содержательное описание алгоритма маршрутизации
- 2. 3. 2. Формирование таблиц достижимости
- 2. 3. 3. Графовая модель процесса маршрутизации
- 2. 3. 4. Клеточный алгоритм адаптивной маршрутизации
- 2. 4. Пример применения алгоритма адаптивной маршрутизации
- 2. 5. Выводы к главе
- ГЛАВА 3. УСТРОЙСТВО МАРШРУТИЗАЦИИ ОДНОРОДНОЙ СРЕДЫ ПРОЦЕССОРНЫХ ЭЛЕМЕНТОВ
- 3. 1. Структурная организация процесса маршрутизации
- 3. 2. Функциональная схема маршрутизатора
- 3. 3. Организация однородной среды обмена сообщениями
- 3. 4. Выводы к главе
- ГЛАВА 4. МОДЕЛИРОВАНИЕ И ИССЛЕДОВАНИЕ СРЕДЫ РЕКОНФИГУРАЦИИ И МАРШРУТИЗАЦИИ
- 4. 1. Моделирование среды реконфигурации мультиконтроллера
- 4. 2. Исследование характеристик ячейки реконфигурации
- 4. 3. Программная модель устройства маршрутизации
- 4. 4. Исследование алгоритма маршрутизации при различных конфигурациях отказов МК
- 4. 5. Исследование характеристик маршрутизации
- 4. 6. Выводы к главе 1
- ЗАКЛЮЧЕНИЕ
- СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
Список литературы
- В. Корнеев Будущее высокопроизводительных вычислительных систем // Открытые системы. 2003. № 5.
- Сами М., Стефанелли Р. Перестраиваемые архитектуры' матричных процессорных СБИС // ТИИЭР. 1986. № 5. С. 107−118.
- Организация и синтез микропрограммных мультимикроконтроллеров / И. В. Зотов, В. А. Колосков, B.C. Титов, К. А. Сапронов, А. П. Волков, Курск: Изд-во «Курск», 1999. 368 с.
- Колосков В.А. Основы теории и принципы построения отказоустойчивых самоорганизующихся логических мультимикроконтроллеров / Дисс. на соискание учёной степени д-ра техн. наук. Курск, КГТУ, 1998. 367 с.
- В.А. Колосков, B.C. Титов Архитектура отказоустойчивых сетей самонастраиваемых микроконтроллеров / Курск: Курск, гос. техн. унт, 1995. 176 с.
- Д. Кефарт, Д. Чесс Концепция саморегулирующихся вычислений // Открытые системы. 2003. № 5.
- Адаптивные системы от Fujitsu Siemens // Открытые системы. 2003. № 10.
- В. Воеводин, М. Филамофитский Суперкомпьютер на выходные // Открытые системы. 2003. № 5.
- Савенков Н.А., Колосков В. А. Исследование самоорганизации мультимикроконтроллера с плавающим столбцом резервных элементов // Сборник материалов 5-й международной конференции «Распознавание 2001». — КГТУ, Курск, 2001
- В.А. Колосков, М. В. Медведева Модели активной среды самоорганизации отказоустойчивого мультиконтроллера // Программирование. 2001. № 6. с. 67−76.
- А. Савельев Современные протоколы маршрутизации // LAN/Журнал сетевых решений. 1998. № 12.
- А. Богданов, В. Мареев, Е. Станкова, В. Корхов Архитектуры и топологии многопроцессорных вычислительных систем // Электронный учебник http://www.informatika.ru
- Э. Таненбаум, Архитектура компьютера. СПб, Из-во «Питер», 2002 г.
- К. Хамахер, 3. Вранешич, С. Заки, Организация ЭВМ. СПб, Из-во «Питер», 2003 г.
- JT. Черняк Ревизия первооснов конец застой? // Открытые системы. 2003. № 5.
- И.В. Зотов, В. А. Колосков, B.C. Титов, К. А. Сапронов, А. П. Волков организация и синтез микропрограммных мультимикроконтроллеров. Курск: Изд-во Курск, 1999. 368 с.
- М. Кульгин На перекрестках сетей // LAN/Журнал сетевых решений. 1996. № 8.
- И. Труб Алгоритмическое обеспечение распределенных WEB-серверов // открытые системы. 2003. № 5.
- Хелеби С., Мак-Ферсон Д. Принципы маршрутизации в Internet: Пер. с англ. 2-е изд. М.: Издательский дом «Вильяме», 2003. 448с.
- S. Cheung, М. LAU Routing with Locality on Meshes with Buses // Journal of parallel and distributed computing. 1996. P.84−90.
- В. Митрофанов, А. Слуцкин, К. Ларионов, JI. Эйсымонт Направления развития отечественных высокопроизводительных систем // Открытые системы. 2003. № 5.
- Колосков В.А., Медведева М. В., Малышев А. В. Клеточная самоорганизация и отказоустойчивость // Сборник материалов Международной н.-т. конф. «Интеллектуальные САПР». Таганрог, 2002. С. 525−531.
- Колосков В.А., Малышев А. В. Нейронная сеть самоорганизации мультимикроконтроллера // Тез. докл. второй Всероссийской н.-т. конф. «Информационные технологии в науке, проектировании и производстве». Н. Новгород, 2000. С. 1.
- Малышев А.В., Миневич JI.M., Колосков В. А. Метод маршрутизации сообщений в отказоустойчивом мультимикроконтроллере // Сборник материалов н.-т. конф. «Медико-экологические информационные технологии». Курск, 2001. С. 216−217.
- Малышев А.В., Миневич Л. М., Колосков В. А. Маршрутизация сообщений в отказоустойчивом мультимикроконтроллере // Сборник материалов н.-т. конф. «Распознавание». Курск, 2001.
- Савенков Н.А., Колосков В. А. Клеточная модель адаптивной маршрутизации в среде с мигрирующими программными модулями // Известия ТулГУ. Серия «Вычислительная техника, информационно-технологические системы управления». Вып. 3. Тула, 2005 г. С. 93−101.
- Савенков Н.А., Медведева М. В., Колосков В. А. Алгоритм адаптивной маршрутизации в мультиконтроллере с репродуцируемой программой поведения // Телекоммуникации. 2003. № 6. С. 20−24.
- Савенков Н.А., Колосков В. А. Алгоритм отказоустойчивой маршрутизации // Материалы 3-й международной научно-технической конференции «Измерение, контроль, информатизация 2002», -Барнаул, АГТУ, 2002, 144с.
- Апраксин Ю.К., Запевалин А. А., Кирюхин В. В. Алгоритмы маршрутизации для сетей с коммутацией сообщений // А и ВТ.- 1982. -№ 2.-С. 87−92.
- Herbordt М.С., Corbett J.C., Weems С.С. Practical algorithms for online routing on fixed and reconfigurable meshes // J. Paral. Distrib. Comput. -1994.-vol.20, No.3. -PP.341−356.
- Kunde M. Packet routing on grids of processors / Lecture Notes in Computer Science. New York: Spinger-Verlag. — 1988. — Vol.401. -PP.129−136.
- Лукьянов A.B., Первозванский A.A. Адаптивное управление маршрутизацией в коммуникационных сетях с коммутацией пакетов // А и ВТ. 1983. — № 1. -С.60−65.
- Шеметов В.В. Гибридный алгоритм маршрутизации для информационно-вычислительных сетей // А и ВТ. 1984. — № 1. — С50−53.
- Kaufmann М., Sibeyn J.F. Randomized multi-packet routing and sorting on meshes //Algorithmica. 1997. — Vol. 17. — P. 224−244.
- 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. 9 841 000.
- 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.
- 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.
- 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.
- 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 Supercomputing. 2003. — Vol. 24. — № 3. — P. 327−340.
- Вишневский В.М., Пороцкий С. М. Динамическая маршрутизация в ATM сетях проблемы и решения //Автоматика и телемеханика. 2003. № 6.
- 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.
- 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. 11. — № 3. — P. 318−335.
- Chen C.-L., Chiu G.-M. A Fault-Tolerant Scheme for Meshes with Nonconvex Faults // IEEE Transactions on Parallel and Distributed Systems. 2001. — Vol. 12. — № 5. — P. 467−475.
- 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.
- 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.
- Valiant L.G., Brebner G.J. Universal schemes for parallel computation / Proc. 13th ACM Symp. Theory of Comput. 1981. — PP.88−92.
- Leighton F.T., Makedon F., Tollis I. A2n-2 step algorithm for routing in nxn array with constant size queues / Proc. 1th ACM Symp. Parallel Alg. and Archit. 1989. — PP.328−335.
- H. Олифер Маршрутизация в составных сетях // LAN/ Журнал сетевых решений. 2001. № 5.
- Савенков Н.А., Колосков В. А. Адаптивная маршрутизация в реконфигурируемом мультиконтроллере // Медико-экологические информационные технологии 2004: Сборник материалов VII
- Международной научно-технической конференции / Курск, гос. техн. ун-т. Курск, 2004. 207с.
- 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. ll.-№ 2.-P. 149−159.
- 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.
- Малышев A.B., Медведева M.B., Колосков В. А. Поиск абонента в мультиконтроллере с репродуцированной программой поведения // Телекоммуникации. 2002, № 5.
- Патент Российской Федерации № 2 185 656. Распределённая система для программного управления // А. В. Малышев, М. В. Медведева, JI.M. Миневич, В. А. Колосков. Изобретения, 2002.
- Малышев А.В. Адаптационный алгоритм самоорганизации обменных взаимодействий в мультимикроконтроллерной сети // Тез. докл. Международной научной конференции «XXVIII Гагаринские чтения». Москва, 2002.
- Малышев А.В. Клеточные алгоритмы и среды отказоустойчивой маршрутизации самоорганизующегося мультиконтроллера / Дисс. на соискание ученой степени кандидата технических наук. Курск. КГТУ, 2003, 148с.
- Протокол состояния связей OSPF. http//www.psati.ru
- А.В. Тимофеев, А. В. Сырцев Модели и методы маршрутизации потоков данных в телекоммуникационных системах с изменяющейся динамикой // Приложение к журналу «Информационные технологии». № 8. 2005 г.
- Басанер Р., Саати Т. Конечные графы и сети. М.: Наука, 1973. 368с.
- Вишневский В.М., Левнер Е. В., Федотов Е. В. Математические модели исследования алгоритмов маршрутизации в сетях передачи данных // Информационные процессы. 2001. Т.1. № 2. С. 103−126.
- Timofeev А. V. Intelligent control applied to non-linear system and neural networks with adaptive architecture // International Journal on Intelligent Control, Neurocomputing and Fuzzy Logic. 1996. P. 1−18.
- Технология параллельных вычислений в распределённых средах реструктуризации мультикомпьютеров / В. А. Колосков, М. В. Медведева, Ф. А. Старков, Курск, гуманит-техн. ин-т. Курск, 2002.
- Choo Н., 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.
- 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.
- W.J. Dally, C.L. Seitz The torus routing chip // Journal of distributed computing. Vol. 1. No. 3, pp. 187−196, 1986.
- Клеточная самоорганизация программируемых отказоустойчивых мультимикроконтроллеров / М. В. Медведева, А. В. Медведев, В. А. Колосков, Ф. А. Старков, Курск, гуманит-техн. ин-т. Курск, 2000. 200с.
- Савенков Н.А., Малышев А. В., Колосков В. А. Алгоритм маршрутизации в самоорганизующихся управляющих структурах //
- Сварка и родственные технологии в машиностроении и электронике, Курск: КГТУ, 2003 г.
- Г. Г. Стецюра Возможность технической реализации клеточных автоматов с дальними связями и групповыми операциями // Автоматика и телемеханика. № 8, 2004. С. 174−184.
- Тоффоли Т. Маргалус Н. Машины клеточных автоматов. М.: Мир, 1991.
- Савенков Н.А., Колосков В. А., Медведева М. В. Маршрутизация по логическому адресу в реконфигурируемом мультиконтроллере // Приборы и управление / Сборник статей молодых ученых ТулГУ. Выпуск 2. Издательство ТулГУ, г. Тула, 2004 г.
- Савенков Н.А., Колосков В. А., Медведева М. В. Разработка реконфигурируемых мультиконтроллеров с отказоустойчивым функционированием // Известия ТулГУ. Серия. Проблемы машиностроения. Вып.7. Часть 2. Тула: Изд-во ТулГУ, 2004. — 419с.
- Савенков Н.А. Алгоритм передачи сообщений в реконфигурируемом мультиконтроллере // XXXI Гагаринские чтения. Тезисы докладов Международной молодежной конференции. Москва, 5−9 апреля 2005 г. М.: МАТИ, 2005. Т.4, 134 с.
- Савенков Н.А. Алгоритм обмена в реконфигурируемых многопроцессорных структурах // Решетневские чтения: материалы IX Междунар. науч. конф., посвящ. 45-летию Сиб. гос. аэрокосмич. ун-т. Красноярск, 2005. — 392 с.
- Однородные структуры / Варшавский В. И., Мараховский В. Б., Песчанский В. А., Розенблюм Л. Я., М., 1973 г.
- JT. Наумов, А. Шалыто Клеточные автоматы реализация и эксперименты // Мир ПК, 2003. № 8.
- Sarkar P., A brief history of cellular automata // ACM Comput. Surveys. 2000. V. 32. № 1. P. 81−107.
- Патент Российской Федерации № 2 175 144 Устройство для формирования маршрута сообщения // П. В. Сусин., И. В. Зотов, B.C. Титов. 2001.
- Титов B.C., Колосков В. А., Зотов И. В. Организация средств ретрансляции сообщений в алгоритмически распределенных системах // Изв. КГТУ. 1998. — № 2. — С. 69−77.
- Волгин Л.И. Представление функций непрерывной логики в предикатной алгебре выбора и синтез реляторных процессоров // Электронное моделирование. 1998. № 2. С. 3−21.
- Волгин Л.И., Зарукин А. И. Развитие элементного базиса реляторной схемотехники // Датчики и системы. 2002, № 3.
- Савенков Н.А., Колосков В. А. Организация маршрутизации в реконфигурируемом мультиконтроллере // Известия КурГТУ. 2005. № 1(14) Курск. Изд-во КурГТУ, 2005 г.
- Положительное решение о выдаче патента на изобретение (Россия), МПК 7 G 06 F. Ячейка маршрутизации однородной среды процессорных элементов. / Савенков Н. А., Колосков В. А., Колоскова Г. П. (Россия). Заявка № 2 004 132 649, приоритет от 9 ноября 2004 г.
- 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.