Параллельно-конвейерное коммутационное устройство для организации массового информационного обмена в мультипроцессорах

Одной из основных тенденций развития мультипроцессоров является постоянное увеличение числа процессорных модулей. Так, современные SMP-системы способны объединять до нескольких десятков процессорных модулей (к примеру, SMP-серверы Ultra Enterprise 10 000 фирмы SUN Microsystems масштабируются до 64-процессорной конфигурации), a NUMA-архитектуры могут содержать сотни процессорных модулей (в частности, система Origin 3000 фирмы Silicon Graphics, Inc. масштабируется до 512 процессорных модулей). Для организации информационных обменов (между модулями процессоров и общей памяти) в таких системах, как правило, используются матричные переключатели, динамические многокаскадные коммутаторы или устройства на их основе (Cote Е., Manjikian N., Murali S., Benini L., De Micheli G., Graunke C.R., Wheeler D.I., Tougaw D., Will J.D. и др.). Они способны одновременно коммутировать множество пар взаимодействующих модулей и обеспечивают передачу информации параллельными словами (пакетами) фиксированной разрядности (например, в системе Ultra Enterprise 10 000 данные оформляются в 64-байтные пакеты, передаваемые 128-битными словами за 4 такта). Для временного хранения пакетов на каждом входе переключателя организуются буферы соответствующей разрядности и длины.

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

Другим подходом к построению сложных коммутаторов для SMPи NUMA-систем является их составление из множества сравнительно простых базовых статических коммутационных устройств, имеющих небольшое фиксированное число входов и выходов, но обладающих более широкими функциональными возможностями по сравнению с модулями матричных переключателей и многокаскадных коммутаторов (Харченко B.C., Мельников В. А. и др.). Для организации взаимодействия требуемого числа модулей системы такие устройства объединяются в матричные коммутаторы. Модули системы при этом ставятся во взаимно однозначное соответствие отдельным устройствам коммутатора и подключаются к ним через выделенные вход и выход. Передача информации в коммутаторах такого рода выполняется пакетами фиксированной разрядности в параллельном коде. Каждый пакет содержит как передаваемые данные, так и адрес приемника, и перемещается независимо от других пакетов через транзитные устройства до требуемого приемника. Для временного хранения пакетов в каждом устройстве организуются (локальные) буферы соответствующей разрядности и длины.

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

Объект исследования: статические коммутационные устройства мультипроцессоров.

Предмет исследования: алгоритмы функционирования, архитектура и функциональные схемы указанных коммутационных устройств.

Работа выполнена при поддержке гранта «Столетовские гранты -2003» Министерства образования РФ, а также в рамках плана НИР Курского государственного технического университета по единому заказ-наряду Министерства образования РФ в 2003;2007 годах.

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

Задачи исследований:

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

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

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

4. Сравнительная оценка аппаратной сложности разработанного коммутационного устройства.

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

Научная новизна результатов диссертации:

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

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

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

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

Практическая ценность результатов исследований:

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

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

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

На защиту выносятся следующие научные результаты:

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

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

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

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

Практическое использование результатов работы. Основные научные результаты и выводы диссертации внедрены в ООО «Нордвинд» (г. Москва) и ФГУП «Курский НИИ» МО РФ (г. Курск), а также используются в учебном процессе на кафедре вычислительной техники КурскГТУ при проведении занятий по дисциплинам «Теоретические основы проектирования отказоустойчивых мультимикропроцессоров», «Моделирование» и «Отказоустойчивые многопроцессорные платформы».

Апробация работы. Основные положения и результаты диссертации обсуждались и получили положительную оценку на следующих конференциях и семинарах: на Международной научно-технической конференции «Information and Telecommunication Technologies in Intelligent Systems» (Spain, Mallorca, 2007), на вузовской научно-технической конференции «Молодёжь и XXI век» (Курск, 2006), дважды на Международной научно-технической конференции «Медико-экологические информационные технологии» (Курск, 2006, 2007), на научных семинарах кафедры вычислительной техники КурскГТУ с 2004 по 2007 год.

Публикации. Содержание диссертации опубликовано в 8 работах, среди которых имеется статья в научном издании, входящем в перечень ВАК Минобрнауки РФ.

Личный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В работах по теме диссертации, опубликованных в соавторстве, личный вклад соискателя определяется следующим образом: в [21, 22] предложена структурно-функциональная модель параллельно-конвейерного коммутационного устройства (процессора), выполнена ее верификация на основе аппарата сетей Петри, а также исследованы зависимости вероятности блокировки пакетов от интенсивности их поступленияв [18] разработана процедура обслуживания транзитных пакетов коммутационным устройством (не включая процесса их маршрутизации) — в [88] описаны функциональные схемы основных блоков параллельно-конвейерного коммутационного устройствав [23] получены формулы для оценки их аппаратной сложностив [41] разработан ряд специализированных программных модулей среды имитационного моделирования коммутационных устройств.

Структура и объем работы. Диссертация включает введение, четыре главы, заключение, приложения и список литературы из 95 наименований. Работа содержит 135 страниц текста (с учетом приложений) и поясняется 29 рисунками и 5 таблицами.

Выводы.

1. Установлено двукратное снижение аппаратной сложности разработанного коммутационного устройства (в числе вентилей) по сравнению с лучшими известными устройствами статических коммутаторов, в частности, при размерности 3×3 сложность параллельно-последовательного коммутационного устройства составляет 13 690 ЭВ, а для разработанного параллельно-конвейерного устройства она составит 4603 ЭВ.

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

Заключение

.

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

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

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

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

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

4. Установлено двукратное снижение аппаратной сложности разработанного коммутационного устройства (в числе вентилей) по сравнению с лучшими известными устройствами статических коммутаторов.

5. Разработана имитационная модель параллельно-конвейерной процедуры коммутации, программная реализация которой в визуальной среде Visual QChart Simulator позволила автоматизировать оценку времени обработки и вероятности блокировки транзитных пакетов.

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