Введение к работе
Актуальность темы. Уровень развития современной технологии СБИС обеспечивает возможность реализации многопроцессорных систем на одном кристалле. Причем интегральное воплощение возможно не только для SMP-систем, содержащих несколько процессорных ядер, но и для NUMA-мультипроцессоров, объединяющих десятки модулей (Raytheon MONARCH, Tilera TILE64, TILEPro64, TILE-Gx). NUMA-системы такого рода, называемые однокристальными мультипроцессорами (ОМП), уже сегодня способны масштабироваться до 100-процессорных конфигураций (TILE-Gx).
Межмодульное взаимодействие в современных ОМП осуществляется через коммуникационную среду (КС) с непосредственными связями. В коммерческих мультипроцессорах, как правило, применяются КС с матричной или тороидальной топологической структурой, отличающиеся простотой СБИС-реализации и обеспечивающие множество альтернативных маршрутов передачи информации (Tilera TILE64, TILEPro64, TILE-Gx). Такие КС используют параллельные каналы связи (разрядностью данных 64 бита и выше), что позволяет выполнять межмодульный информационный обмен словами (пакетами) (Y. Chen, J. Liu, P.P. Pande).
Рост степени интеграции ОМП является причиной увеличения вероятности возникновения на кристалле дефектных областей (снижается процент выпуска годных СБИС), а также появления отказов и сбоев в модулях и каналах связи в процессе функционирования мультипроцессора, что приводит к необходимости повышения его отказоустойчивости. При этом, поскольку значительную часть площади кристалла мультипроцессора занимает КС, существенная часть аномалий (дефектов, отказов и сбоев) приходится на коммутационные блоки управления маршрутизацией. Одно из их проявлений – искажение маршрутов передачи пакетов, приводящее к потере передаваемой информации и нарушающее ход вычислительного процесса в ОМП.
Повышение отказоустойчивости мультипроцессоров и их коммутационной среды традиционно обеспечивается применением различных алгоритмов обхода отказов (дефектов) при маршрутизации пакетов. Они отличаются правилами обхода отказов, уровнем реализации (программный, аппаратный, смешанный), сложностью и комбинаторными возможностями (R.V. Boppana, S. Chalasani, C.-L. Chen, G.-M. Chiu, J. Duato, J. Wu и др.). Однако указанные алгоритмы предполагают достаточно грубый контроль состояния процессорных модулей (из-за чрезвычайно высокой сложности организации полного контроля) и не чувствительны к ошибкам в работе отдельных блоков управления маршрутизацией. Как результат, вполне возможно, что признанный работоспособным модуль будет выдавать пакеты в неверных направлениях. Исходя из этого, существует объективная необходимость совершенствования средств управления маршрутизацией пакетов ОМП в части организации контроля блоков управления маршрутизацией и автоматической коррекции (восстановления) искаженных маршрутов передачи пакетов.
Научно-технической задачей диссертации является разработка метода, алгоритма и аппаратных средств управления маршрутизацией пакетов, обеспечивающих контроль и автоматическую коррекцию искаженных маршрутов с целью снижения вероятности возникновения ошибок в коммутационной среде однокристальных матричных мультипроцессоров.
Объект исследования: методы, алгоритмы и устройства управления маршрутизацией пакетов в коммутационной среде однокристальных матричных мультипроцессоров (матричных ОМП).
Предмет исследования: процессы функционирования коммутационных устройств матричных ОМП в условиях наличия дефектов, отказов и сбоев, искажающих маршруты передачи информации.
Диссертационная работа выполнена в рамках плана НИР Курского государственного технического университета по единому заказ-наряду Министерства образования и науки РФ в 2006-2009 годах.
Цель диссертации: уменьшение вероятности возникновения ошибок в коммутационной среде матричных однокристальных мультипроцессоров на основе разработки метода и аппаратных средств управления маршрутизацией пакетов с автоматической коррекцией искаженных маршрутов.
Задачи исследований:
-
Разработка правил преобразования адресной части пакетов при их маршрутизации в коммутационной среде матричных ОМП, обеспечивающих автоматическую коррекцию искаженных маршрутов.
-
Создание метода управления маршрутизацией пакетов в коммутационной среде матричных ОМП с автоматической коррекцией искаженных маршрутов при дефектах, отказах и сбоях в отдельных коммутационных блоках на основе разработанных правил преобразования.
-
Разработка структурно-функциональной организации устройства управления маршрутизацией пакетов в коммутационной среде матричного ОМП, реализующей созданный метод. Оценка аппаратной сложности и избыточности разработанных схемных решений.
-
Экспериментальное исследование функционирования разработанного устройства в составе коммутационной среды матричного мультипроцессора повышенной надежности с целью сравнительной оценки вероятности нарушения маршрутов передачи пакетов.
Научная новизна результатов исследований:
-
Создан метод управления маршрутизацией пакетов в коммутационной среде матричных ОМП, отличающийся использованием распределённого мажоритарного сопоставления трёх маршрутных кодов текущего шага маршрута и позволяющий реализовать автоматическую коррекцию маршрутов при искажении маршрутных кодов вследствие дефектов, отказов и сбоев в коммутационных блоках.
-
Разработана структурно-функциональная организация устройства управления маршрутизацией пакетов, новизна которой заключается в наличии блоков для определения маршрутных кодов текущего и двух последующих шагов маршрута, а также блоков для вычисления фактического маршрутного кода текущего шага на основе кодов, поступивших от двух предшествующих модулей и от текущего модуля.
-
Синтезирована имитационная модель разработанного устройства, включающая новые элементы для компактного описания правил выбора направлений выдачи пакетов и позволяющая выполнить статистическое моделирование однокристального матричного мультипроцессора при наличии локальных отказов, дефектов и сбоев и оценить вероятность нарушения маршрутов передачи пакетов при использовании данного устройства в качестве коммутационного модуля.
Достоверность результатов диссертации обеспечивается корректным и обоснованным применением положений и методов математической логики, теории множеств и графов, теории вероятностей и математической статистики, теории систем и сетей массового обслуживания, теории проектирования ЭВМ и систем, а также подтверждается совпадением теоретических выводов с результатами имитационного моделирования.
Практическая ценность результатов исследований:
-
Созданный метод управления маршрутизацией пакетов в коммутационной среде матричных ОМП позволяет снизить вероятность нарушения средних и длинных маршрутов (длины 3 и более) не менее чем в 1.4 раза, что обусловливает повышение надёжности КС мультипроцессора.
-
Разработанная структурно-функциональная организация устройства управления маршрутизацией пакетов характеризуется невысокой аппаратной избыточностью, составляющей не более 14% для всех практически значимых случаев. Реализация разработанных схем предполагают небольшое увеличение разрядности межмодульных каналов связи (10 дополнительных разрядов на канал, или примерно 18-21% от разрядности канала с 32-битным полем данных), что позволяет сохранить приемлемую сложность СБИС ОМП в целом.
-
Предложенные схемные решения способны работать с различными алгоритмами фиксированной маршрутизации пакетов (XY-, YX-маршрутизация) и могут применяться при построении не только двумерных, но и многомерных матричных КС (гиперкубов), объединяющих модули с большим числом входов / выходов (до 16).
На защиту выносятся следующие научные результаты:
-
Правила преобразования адресной части пакетов при их маршрутизации в коммутационной среде матричных ОМП, позволяющие синтезировать алгоритм и аппаратные средства, реализующие автоматическую коррекцию искаженных маршрутов в КС мультипроцессора.
-
Метод управления маршрутизацией пакетов в коммутационной среде матричных ОМП, впервые использующий для формирования кода фактического направления выдачи пакета мажоритарное сопоставление трёх маршрутных кодов текущего шага передачи, вычисленных данным модулем и двумя его предшественниками.
-
Структурно-функциональная организация устройства управления маршрутизацией пакетов матричного ОМП, включающая новые блоки определения маршрутных кодов текущего и двух последующих шагов маршрута, а также блоки вычисления фактического маршрутного кода текущего шага на основе кодов, поступивших от двух предшествующих модулей и от текущего модуля.
-
Имитационная модель разработанного устройства на расширенном языке Q-схем, отличающаяся наличием новых элементов (обобщённых массовых контроллеров), моделирующих правила выбора направлений выдачи пакетов на уровне модуля, и позволяющая осуществлять статистическое моделирование коммуникационной среды матричного ОМП при наличии в ней локальных отказов, дефектов и сбоев и оценивать вероятность нарушения маршрутов передачи пакетов.
-
Зависимости вероятности нарушения маршрутов при передаче пакетов в коммуникационной среде матричного ОМП от длины маршрутов при фиксированной интенсивности локальных отказов, выведенные аналитически и полученные в результате имитационного моделирования.
Практическое использование результатов работы. Основные научные результаты и выводы диссертационной работы использованы при построении многомашинного территориально распределенного вычислительного комплекса автоматизации планирования размещения и переразмещения взаимосвязанных задач по рабочим станциям (ООО «Компания «ДЕМОС», г. Москва), в автоматизированном вычислительном комплексе контроля функционирования мультимикроконтроллерной системы (ООО «Фактор-ТС», г. Москва), а также в учебном процессе на кафедре вычислительной техники КурскГТУ в рамках дисциплины «Теоретические основы проектирования отказоустойчивых мультимикропроцессоров».
Апробация работы. Основные положения, результаты и выводы диссертации обсуждались и получили положительную оценку на VIII Международной научно-технической конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» (г. Курск, 2008 г.), на VIII Международной научно-практической конференции «Микропроцессорные, аналоговые и цифровые системы: проектирование и схемотехника, теория и вопросы применения» (г. Новочеркасск, 2008 г.), на VI Всероссийской конференции «Проблемы развития технологических систем государственной охраны, специальной связи и информации» (г. Орёл, 2009 г.), на региональной научно-методической конференции «Современные проблемы высшего профессионального образования» (г. Курск, 2009 г.), а также на научных семинарах кафедры вычислительной техники КурскГТУ в период с 2006 по 2009 год.
Публикации по теме диссертации. Содержание диссертации опубликовано в 9 работах, среди которых имеется 3 статьи в научных изданиях по перечню ВАК Минобрнауки РФ, а также 1 свидетельство о Государственной регистрации программы для ЭВМ.
Личный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В опубликованных в соавторстве работах по теме диссертации личный вклад соискателя сводится к следующему: в [1, 4, 6] разработана методика оценки характеристик коммутатора с отказоустойчивой маршрутизацией сообщений (пакетов), в [2] предложен вариант формализованного описания коммутирующего элемента, в [3] изложен подход к управлению маршрутизацией пакетов на уровне коммутационного узла, в [8] описана методика построения проектов имитационного моделирования аппаратных средств, в [9] разработан ряд классов, шаблонов и функций для моделирования коммутационных элементов ОМП.
Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, приложений и списка литературы, включающего 97 наименований. Диссертация содержит 145 страниц текста (включая 2 приложения) и поясняется 29 рисунками и 14 таблицами.
Области возможного использования. Результаты диссертационной работы могут быть использованы при построении высоконадежных многопроцессорных систем с регулярной топологической структурой, включая системы на кристалле, а также крупномасштабные вычислительные системы такие, как мультикомпьютеры.
