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

На правах рукописи

Крикунов Олег Васильевич

ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНОЕ КОММУТАЦИОННОЕ УСТРОЙСТВО ДЛЯ ОРГАНИЗАЦИИ МАССОВОГО ИНФОРМАЦИОННОГО ОБМЕНА В МУЛЬТИПРОЦЕССОРАХ

05 13 05 - Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Курск - 2007

003177443

Работа выполнена в ГОУ ВПО «Курский государственный технический университет» на кафедре вычислительной техники в совместной научно-исследовательской лаборатории Центра информационных технологий в проектировании РАН и Курского государственного технического университета «Информационные распознающие телекоммуникационные интеллектуальные системы»

Научный руководитель

доктор технических наук, доцент Зотов Игорь Валерьевич

Официальные оппоненты

доктор технических наук, профессор 4такищев Очег Игоревич

кандидат технических наук Сусин Павел Викторович

Защита состоится 27 декабря 2007 г в 14-00 часов на заседании совета по защите докторских и кандидатских диссертаций Д212 105 02 при Курском государственном техническом университете по адресу 305040, Курск, ул 50 лет Октября, 94 (конференц-зал)

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

Ведущая организация Воронежский государственный технический университет

Автореферат разослан 27 ноября 2007 г

Ученый секретарь совета по защите докторских и кандидатских диссертаций Д 212 105 02

Е А Титенко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

приемника Для временного хранения пакетов в каждом устройстве организуются (локальные) буферы соответствующей разрядности и длины

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

са и характеризуется простотой комплексирования и наращивания по числу входов и выходов

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

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

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

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

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

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

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

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

Личный вклад соискателя Все выносимые на защиту научные результаты получены соискателем лично В работах по теме диссертации, опубликованных в соавторстве, личный вклад соискателя определяется следующим образом в [1,2] предложена структурно-функциональная модель параллельно-конвейерного коммутационного устройства (процессора), выполнена ее верификация на основе аппарата сетей Петри, а также исследованы зависимости вероятности блокировки пакетов от интенсивности их поступления, в [6] разработана процедура обслуживания транзитных пакетов коммутационным устройством (не включая процесса их маршрутизации), в [5] описаны функциональные схемы основных блоков параллельно-конвейерного коммутационного устройства, в [7] получены формулы для оценки их аппаратной сложности, в [8] разработан ряд специализированных программных модулей среды имитационного моделирования коммутационных устройств

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Функционирование многопроцессорных систем порождает коммутационные процессы различных видов (межпроцессорный обмен данными, взаи-

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

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

Коммутирующая часть коммутационных устройств, применяемых в высокопроизводительных мультипроцессорах (как SMP, так и NUMA), строится чаще всего на основе матричного переключателя (crossbar switch), который обеспечивает высокую пропускную способность и малое время передачи пакетов (латентность) Однако аппаратная избыточность переключателя часто вынуждает разработчиков применять другие архитектурные решения В частности, нередко выбор делается в пользу многокаскадных динамических коммутаторов (например, коммутаторов Клоса и баньян-сетей) Они обладают меньшей аппаратной сложностью по сравнению с переключателем, но в то же время имеют более высокую латентность Кроме того, коммутирующую часть можно реализовать в виде статического коммутационного устройства, что также обеспечивает снижение ее аппаратной сложности Однако такой вариант приемлем лишь в том случае, если устройство способно осуществлять параллельную обработку пакетов, поступающих на разные входы, и характеризуется простотой комплексирования (в противном случае пропускная способность коммутирующей части будет неприемлемо низкой)

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

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

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

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

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

Сплошными линиями на схеме показаны информационные потоки (потоки пакетов), пунктирные линии отображают управляющие воздействия (управляющая среда, вырабатывающая эти воздействия, условно не показана) Через Ш„М2, ,/Л'„ обозначены входы коммутационного устройства, через О,,02, ,Оп - его выходы, символами <•/>,, <р-, , <рн и //,, //,, , //„ обозначены соответственно входные демультиплексоры и выходные мультиплексоры пакетов, символы рп, (х=1 ,п, у = \,п) соответствуют демультиплексорам распределения пакетов, символы Вч (у = 1л, у = 1,/я) обозначают регистры локальных буферов, т - длина буфера Каждый из регистров Вч способен хранить один пакет Состояние регистра Вч определяется индикаторной функцией 5 В->{0,1}, В = {ВЧ} 5(вч) = 1, если этот регистр содержит пакет, 5(вч) = 0 иначе

Процесс обработки пакетов коммутационным устройством носит циклический характер Очередная группа пакетов /•;, г2 , /■„ поступает на входы /Л',, /Л',, , /Л'„ соответственно и после обработки распределяется на выходы 0„02, ,0„ Демультиплексор <р, (х = \,п) реализует выбор направления <рЛ^) выдачи пакета Г, согласно заданному алгоритму маршрутизации ^Д/^е {1,2, ,п) Демультиплексор Рп (х = \,п, у = \,п ) обеспечивает выбор направления /?„(/%) передачи пакета Рх в один из регистров в,,, В>г, Вт с учетом значений ^(В,,), 5(ва), 5(в,„) А, {В„,В12, Мультип-

лексор ( V = 1,я) осуществляет коммутацию пакета из очередного регистра Вч такого, что 5(В1;) = 1, на выход О, (в направлении у) согласно некоторой приоритетной дисциплине ^

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

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

НАЧАЛО ПРОЦЕДУРЫ «Цикл коммутации пакетов»

ВЫПОЛНЯТЬ ПАРАЛЛЕЛЬНО ВЫПОЛНЯТЬ ПАРАЛЛЕЛЬНО для всех х = \,~п ПРИНЯТЬ пакет с входа /А', ВЫЧИСЛИТЬ значение кх =

ЕСЛИ л5'(в,1;) = 1,ТО

БЛОКИРОВАТЬ пакет Рх до выполнения условия ;) = 0

ВЫЧИСЛИТЬ значения {/?п с учетом текущих значений

{$(/>„,)} (., = М0

ЗАПИСАТЬ пакет Ря в регистр /За согласно дисциплине у КОНЕЦ ВЫПОЛНЯТЬ ПАРАЛЛЕЛЬНО для всех х = Цй ВЫПОЛНЯТЬ ПАРАЛЛЕЛЬНО для всех у =

ВЫБРАТЬ регистр Вч такой, что = 1 (у е{1,2, ,т}) ВЫДАТЬ пакет из регистра вч на выход О, СЧИТАТЬ 5'(й„) = 0

КОНЕЦ ВЫПОЛНЯТЬ ПАРАЛЛЕЛЬНО для всех V = Г" КОНЕЦ ВЫПОЛНЯТЬ ПАРАЛЛЕЛЬНО КОНЕЦ ПРОЦЕДУРЫ «Цикл коммутации пакетов»

Формальная верификация разработанной структурно-функциональной организации коммутационного устройства осуществляется на основе аппарата сетей Петри На рис 2 изображена сеть Петри Л,, моделирующая выходной тракт устройства, подключенный к выходу О,, >»£{1,2, ,п} (этот тракт включаетдемультиплексоры (х = 1,п), регистры йи, й2, Вх„ и мультиплексор с соответствующими информационными и управляющими потоками, см рис 1) В сети Л„ переход <¡«1 моделирует поступление пакета на вход /Л'( (г = I, л ), переход щ2 отображает чтение пакета из регистра Вч (J = \,m), переходы ц отражают распределение пакетов демультиплексора-ми р„ (х = 1,п) в регистры й„ (J = \,m), переход дЗ моделирует выдачу пакета мультиплексором /;, Предполагается, что инициальные переходы цх\ срабатывают в моменты дискретного времени 0, 1, 2, , соответствующие тактам работы устройства Путем композиции сетей {л,} (у = \,п) строится

объединенная сеть Петри Л, отображающая структурно-функциональную организацию устройства в целом

Для анализа поведения сети Л, при различных вариантах срабатывания переходов строятся соответствующие сети ли, л,2 и с начальными мар-

кировками. Сеть ли моделирует стационарный режим работы устройства, при котором в каждую сеть за каждый такт поступает только 1 фишка. Сети Л,., и Л,., моделируют ситуации поступления соответственно 2 и 3 фишек за каждый такт. Исследование множества достижимых маркировок объединенной сети Л позволило доказать, что при соблюдении условия безопасности позиций Рх\ (х = 1,п) во всех сетях Л, сеть Л обладает свойством безопасности, является сохраняющей и не имеет тупиков. Установлено, что сеть Л перестаёт быть безопасной, когда в некоторой подсети Л,, суммарная маркировка позиций Р\\,Р2\,...,Рп\ и Р\2,Р22....,Рт2 превышает т. Такая ситуация отражает блокировку по крайней мере одного пакета.

Рис. 2. Сеть 11етри л,.

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

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

В состав устройства входят следующие основные блоки: блоки выбора направления передачи пакетов (БВНПП); блоки организации массива пакетов (БОМП); блоки распределения пакетов в БОМП (БРП); блоки чтения пакетов (БЧП). Пунктирными линиями показаны управляющие связи, сплошными -информационные. Между блоками устройства и элементами его структурно-функциональной модели (см. рис.1) установлено следующее соответствие: БВНППЬс отображается демультиплексором <рг (х = \,п), БОМПу моделируется набором регистров Вн, Вг1, ... Вт (у = 1,я), БРПу представляется набором

демультиплексоров /?,„ (х = 1 ,п, у = \,п), БЧПу задается мультиплексором ^^v (У = й)

Каждый БОМП включает одномерный массив статических регистров с тремя состояниями выхода Любой регистр массива может хранить только один пакет Каждый из БРП реализует выбор регистра в соответствующем БОМП для записи поступающего пакета с учетом возможного присутствия нескольких пакетов, требующих выдачи в одном выходном направлении БВНПП формируют сигналы (признаки) направления выдачи пакетов в соответствии с реализуемым алгоритмом маршрутизации для настройки соответствующих БРП БЧП предназначен для считывания и выдачи пакетов, хранящихся в соответствующем БОМП, согласно заданной приоритетной дисциплине

Рис 3 Обобщенная структурная схема параллельно-конвейерного коммутационного устройства

На рис 4 изображена структурно-функциональная схема разработанного коммутационного устройства, полученная для случая п- 3 и т = 3 Данное устройство в дополнение к попарному обмену пакетами, поддерживает режим их широковещательной передачи В структуру пакета входит информационная часть, адрес приемника и управляющие поля, определяющие режим его передачи

Основными блоками устройства являются БВНПП 1 1, 1 2, 1 3 и блоки организации передачи пакетов (БОПП) 2 1, 2 2, 2 3, каждый из которых, в свою очередь, включает БОМП, БРП и БЧП Регистр 3 хранит адрес текущего устройства (модуля) в структуре матричного коммутатора Входы 7 1,81,91 используются для приема входящих пакетов, а выходы 11 1, 12 1, 13 1 для выдачи обработанных пакетов в соответствующих направлениях Входы 7 2,

8.2, 9.2 и выходы 11.2, 12.2, 13.2 служат для обмена признаками наличия пакетов. Вход 10 обеспечивает приём импульсов синхронизации от внешнего генератора. Функциональные схемы блоков 1.1-1.3, 2.1-2.3 представлены в

Рис. 4. Структурно-функциональная схема базового коммутационного устройства при п = 3 и т = 3

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

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

Я = К,,А + п ( ктмп + К,;т + К,1ЧП + Ишнпп ), (1)

где ЯГА - сложность регистра адреса, содержащего адрес текущего устройства (в структуре матричного коммутатора); ЯИ0МП, Яы.п, ЯИЧП и ЯИННПП -сложность одного БОМП, БРП, БЧП и БВНПП соответственно. Выражая сложность указанных блоков в числе ЭВ, получим:

+ + 7 + ЭВ, (2)

Яа,п = 2тп - Зп ЭВ, (3)

Я,.чп = \\т-2 ЭВ, (4)

Яе«ялл = 12я + Л" эв, (5)

где / = const - разрядность пакета, R" - функция, вычисляемая в зависимости от числа входов (выходов) устройства п по таблице (некоторые значения R" для ряда значений «приведены в таблице 1)

Таблица 1

п 3 5 9

R" 7 8 18

Из формулы (1) с учетом выражений (2)-(5), а также считая КРЛ = 8а, где а - разрядность адресной части пакета, можно получить общую формулу для расчета сложности коммутационного устройства

R = 8a + n(l2a + R" + Зmn-Зn + m(f(8 + n)) + \8m) ЭВ (6)

Из формулы (6) нетрудно вывести частные выражения для конкретных значений параметров тип Например

Я = 44а+ 231/+ 555 ЭВ, при п=3,/и =7, (7)

Л = 68а + 455/ +1110 ЭВ, при п=5, т =7, (8)

Л = 116а+ 1377/+ 3546 ЭВ, при «=9, т =9 (9)

Выражения (7)-(9) позволяют оценить сложность коммутационного устройства при определенных значениях разрядности а и / Например, при / = 24 бит, а = 8 бит и при минимальном т, исключающем блокировку пакетов, указанная сложность составит соответственно 4603 ЭВ (при и = 3), 8934 ЭВ (при /7 = 5) и 26506 ЭВ (при п = 9) Сравнение этих оценок с аналогичными оценками, полученными для других статических коммутационных устройств (Беляев Ю В , Мельников В А , Харченко ВС и др ), показывает преимущества разработанного устройства для большинства значений п (см табл 2) При этом сложность параллельно-последовательного устройства, являющегося лучшим среди аналогов по быстродействию, в 2 и более раз превышает сложность параллельно-конвейерного устройства

Таблица 2

п Аппаратная сложность коммутационного устройства (ЭВ)

Последовательное устройство (Мельников В А , Харченко В С ) Параллельно-последовательное устройство (Беляев Ю В ) Параллельно-конвейерное устройство

3 7606 13690 4603

5 12476 29942 8934

9 22216 71091 26506

Для оценки максимального времени обработки и вероятности блокировки транзитных пакетов коммутационным устройством выполнено имитационное моделирование с использованием среды Visual QChart Simulator [8] Проведено исследование моделей коммутационных устройств с организацией 3х3(л = 3), 5x5(л = 5) и 7x7(л = 7) (для их построения использовался аппарат Q-схем) В ходе моделирования варьировалась интенсивность посту-

пления пакетов Л (среднее число пакетов, приходящих на каждый из п входов устройства за 1 такт), а также длина буферов т Значения Л выбирались из диапазона от ^ (1 пакет на входе каждые 3 такта) до J/^ О пакет на входе

каждые 42 такта), а значения т принимались равными п,п + \,п + 2 Регистрировалось максимальное время обработки пакета Ттак, а также число заблокированных пакетов

В результате моделирования установлено, что для разработанного устройства с организацией 3x3 (п = т = 3) блокировки пакетов начинаются при

Л > Уд (наихудший случай), в параллельно-последовательном устройстве

блокировки имеют место при Л > При Л = ^ параллельно-конвейерное

устройство дает вероятность блокировки пакета Р равную примерно 0 005 Выяснено, что увеличение длины буферов т на 1 ведет к уменьшению указанной вероятности втрое (для m = 6 она становится практически равной нулю) С ростом числа входов (выходов) устройства п отмечено дальнейшее снижение вероятности блокировки пакетов

Величина 7тах определялась по результатам моделирования на границе интенсивности Л, вблизи которой начинаются блокировки пакетов На рис 4 представлены зависимости Ттп от интенсивности Л для п = т = 3, полученные для разработанного и параллельно-последовательного устройств Из графиков рис 4 видно, что при интенсивности Л > ^ разработанная процедура коммутации снижает время обработки транзитных пакетов в 2 и более раз

* тах

(тактов)

1

S 1—1 1 1—1 н f=i 1=1 1=1

1/3 1/6 1/9 1/12 1/15 1/18 1/21 1/24 1(27 1/30 1/33 1/39 1/42 —Параллельно-последовательнаяобработка ~*~Параллельно-конвейернаяобработка

(пакет/тактов)

Рис 4 Зависимости максимального времени обработки пакетов (в тактах) от интенсивности их поступления {такт соответствует периоду следования синхроимпульсов устройства)

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

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

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

1 Крикунов, О В Коммутационный процессор с параллельно-конвейерной обработкой сообщений [Текст] / О В Крикунов [и др ] // Телекоммуникации 2006 №10 С 11-16

Статья

2 Крикунов, О В Модель параллельно-конвейерной коммутации сообщений [Текст] / О В Крикунов, И В Зотов, Ю П Стеценко // Методы и средства систем обработки информации Сборник научных статей Курск Курск-ГТУ, 2007 Вып 4 С 13-20

Материалы конференций

3 Крикунов, О В Параллельно-конвейерный коммутатор сообщений [Текст] / О В Крикунов // Медико-экологические информационные технологии материалы IX Международной научно-технической конференции, Курск, 23-24 мая 2006 г - Курск КурскГТУ, 2006 - С 157-160

4 Крикунов О В Параллельно-конвейерный коммутатор сообщений [Текст] / О В Крикунов//Молодежь и XXI век материалы XXXIV вузовской научно-технической конференции, Курск, 16-19 мая 2006 г - Курск КурскГТУ, 2006 -С 11-13

5 Zotov, 1 V Parallelized-pipehne communication architecture [Текст] / I V Zotov, О V Krikunov [et al ] // Proc 5th Int Conf Information and Telecommunication Technologies in Intelligent Systems, Spain, Mallorca, May 31 - June 07 2007 - Mallorca, 2007 -P 66-71

6 Зотов, И В Универсальная коммуникационная процедура для параллельных вычислительных систем [Текст] /ИВ Зотов, О В Крикунов [и др ] // Медико-экологические информационные технологии материалы докладов Юбилейной Международной научно-технической конференции, Курск, 24-25 апреля 2007 г - Курск КурскГТУ, 2007 - С 163-167

7 Крикунов, О В Оценка аппаратной сложности параллельно-конвейерного коммутатора сообщений [Текст] / О В Крикунов [и др ] // Медико-экологические информационные технологии материалы докладов Юбилейной Международной научно-технической конференции, Курск, 24-25 апреля 2007 г - Курск КурскГТУ, 2007 - С 216-220

Свидетельство о регистрации программы для ЭВМ

8 Свидетельство о регистрации программы для ЭВМ №2007611310 Визуальная среда имитационного моделирования VisualQChart /ИВ Зотов, О В Крикунов [и др ] (РФ) - М РосПатент, заявлено 13 02 2007, дата регистрации 27 03 2007

Соискатель /^-/Js// О в Крикунов

Подписано в печать 26 11 2007 Формат 60x84 1/16

Печ л _Ц) Тираж 100 экз Заказ 155

Курский государственный технический университет

Издательско-полиграфический центр

Курского государственного технического университета

305040, г Курск, ул 50 лет Октября, 94

Введение.

ГЛАВА 1. Коммутационные процессы и устройства современных многопроцессорных вычислительных систем.

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

1.2. Виды коммутационных устройств.

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

1.3.1. Коммутаторы с разделяемой памятью.

1.3.2. Коммутаторы с разделяемой средой передачи.

1.3.3. Коммутаторы с полносвязной топологией.

1.3.4. Коммутаторы с пространственным разделением.

1.3.5. Статические коммутационные устройства.

Выводы.

ГЛАВА 2. Процедура коммутации с параллельно-конвейерной обработкой пакетов.

2.1. Особенности задачи разработки процедуры коммутации.

2.2 Структурно-функциональная модель коммутационного устройства.

2.3. Описание процедуры коммутации.

2.4. Доказательство корректности процедуры коммутации.

2.4.1. Синтез моделирующей сети Петри.

2.4.2. Исследование достижимых маркировок сети Петри.

Выводы.

ГЛАВА 3. Параллельно-конвейерное коммутационное устройство.

3.1. Принципы организации и архитектура коммутационного устройства.

3.2. Структурная организация коммутационного устройства.

3.2.1. Организация локальных буферов.

3.2.2. Организация блока выбора направления передачи пакетов.

3.2.3. Организация блока распределения пакетов.

3.2.4. Организация блока чтения пакетов.

3.3. Процесс функционирования коммутационного устройства.

3.3.1. Обработка одиночных пакетов.

3.3.2. Параллельная обработка групп пакетов.

3.3.3. Реализация параллельно-конвейерной обработки пакетов.

Выводы.

ГЛАВА 4. Оценка функциональной эффективности процедуры коммутации и коммутационного устройства.

4.1. Методика проведения сравнительной оценки.

4.1.1. Методика оценки аппаратной сложности устройства.

4.1.2. Методика проведения вычислительного эксперимента.

4.2. Оценка аппаратной сложности коммутационного устройства.

4.3. Организация вычислительного эксперимента.

4.3.1 Имитационная модель коммутационного устройства.

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

4.4. Результаты имитационного моделирования.

4.4.1. Оценка максимального времени обработки пакетов.

4.4.2. Оценка вероятности блокировки пакетов.

Выводы.

Одной из основных тенденций развития мультипроцессоров является постоянное увеличение числа процессорных модулей. Так, современные SMP-системы способны объединять до нескольких десятков процессорных модулей (к примеру, SMP-серверы Ultra Enterprise 10000 фирмы 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 10000 данные оформляются в 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. Установлено двукратное снижение аппаратной сложности разработанного коммутационного устройства (в числе вентилей) по сравнению с лучшими известными устройствами статических коммутаторов, в частности, при размерности 3x3 сложность параллельно-последовательного коммутационного устройства составляет 13690 ЭВ, а для разработанного параллельно-конвейерного устройства она составит 4603 ЭВ.

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

Заключение

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

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

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

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

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

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

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

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

1. Артамонов Г.Т. Топология регулярных вычислительных сетей и сред Текст. / Г.Т. Артамонов. М.: Радио и связь, 1985. - 192 с.

2. Архитектура и синтез параллельных логических мул ьтимикроконтролл еров: в 2 ч. Текст. / И.В.Зотов, В.С.Титов, В.И.Штейнберг [и др.]. Курск: КурскГТУ, 2006. - 359 с.

3. А.с. 1462344 СССР, МКИ 4 G06F15/16. Устройство для формирования маршрута сообщения в однородной вычислительной системе / В.А.Мельников, В.С.Харченко, Г.Н.Тимонькин, С.Н.Ткаченко (СССР). -№4284146/24-24; заявлено 13.07.87; опубл. 28.02.89, Бюл. №8. 10 с.

4. А.с. 1508228 СССР, МКИ 4 G06F15/16. Устройство для формирования маршрута сообщения в однородной вычислительной системе / В.А.Мельников, В.С.Харченко, П.И.Кныш, С.Б.Кальченко (СССР). -№4390961/24-24; заявлено 14.01.88; опубл. 15.09.89, Бюл. №34. 8 с.

5. А.с. 1575167 СССР, МКИ 5 G06F7/00, 15/16. Модуль матричного коммутатора / В.А.Мельников, П.И.Кныш, Ю.Н.Силантьев и др. (СССР). -№4486837/24-24; заявлено 26.09.88; опубл. 30.06.90, Бюл. №24. 6 с.

6. А.с. 1793436 СССР, МКИ 5 G06F7/00, 15/16. Модуль матричного коммутатора / В.А.Мельников, А.В.Галицкий, В.В.Копылов и др. (СССР). -№4893395/24; заявлено 30.10.90; опубл. 07.02.93, Бюл. №5. 8 с.

7. Антонов А.С. Параллельное программирование с использованием технологии MPI: Учебное пособие. М.: Изд-во МГУ, 2004. - 71с.

8. Беляев Ю. В. Параллельно-последовательный коммутатор для систем параллельной и распределенной обработки данных Текст. : автореферат диссертации на соискание ученой степени канд. техн. наук : 05.13.05 / Ю. В. Беляев. Курск, 2003. - 17 с.: ил.

9. Васильев В.В. Сети Петри, параллельные алгоритмы и модели мультипроцессорных систем Текст. / В.В.Васильев, В.В. Кузьмук. Киев: Наукова думка, 1990. - 216 с.

10. Воеводив В.В., Воеводин Вл. В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. - 608 е.: ил.

11. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука., 1986. - 296 с.

12. Зотов И.В. Процедурно-логическая модель ретрансляции сообщений для распределенных вычислительных сетей Текст. / И.В.Зотов, Ю.В.Беляев // Телекоммуникации. 2000. №6. С. 18-23.

13. Корнеев В.В. Вычислительные системы. М.: Гелиос АРВ, 2004. -512с., ил.

14. Котов В.Е. Сети Петри. М.: Наука, Гл. ред. физ.-мат. л-ры, 1984. -160 с.

15. Крикунов О.В. Коммутационный процессор с параллельно-конвейерной обработкой сообщений Текст. / О.В.Крикунов [и др.] // Телекоммуникации. 2006. -№10. С. 11-16.

16. Крикунов О.В. Модель параллельно-конвейерной коммутации сообщений Текст. / О.В.Крикунов, И.В.Зотов, Ю.П.Стеценко // Методы и средства систем обработки информации. Сборник научных статей. Курск: КурскГТУ, 2007. Вып.4. С. 13-20.

17. Крикунов О.В. Параллельно-конвейерный коммутатор сообщений Текст. / О.В. Крикунов // Медико-экологические информационные технологии: материалы IX Международной научно-технической конференции, Курск, 23-24 мая 2006 г. Курск: КурскГТУ, 2006. - С. 157160.

18. Крикунов О.В. Параллельно-конвейерный коммутатор сообщений Текст. / О.В. Крикунов // Молодёжь и XXI век: материалы XXXIV вузовской научно-технической конференции, Курск, 16-19 мая 2006 г. Курск: КурскГТУ, 2006.-С. 11-13.

19. Организация и синтез микропрограммных мультимикроконтроллеров Текст. / И.В.Зотов, В.А.Колосков, В.С.Титов [и др.]. Курск: КурскГТУ, 1999. - 368 с.

20. Патент №2116664 РФ, МКИ 6 G06F7/00, G06F15/163. Модуль матричного коммутатора / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). -№96108431/09; заявлено 24.04.96; опубл. 27.07.98, Бюл. №21. 13 с.

21. Патент №2168204 РФ, МКИ 7 G06F15/173; Н03К17/56. Модуль матричного коммутатора / К.А.Попов, И.В.Зотов, В.С.Титов (РФ). № 99119675/09; заявлено 13.09.99; опубл. 27.05.2001, Бюл. №15. - 11 с.

22. Патент №2168755 РФ, МКИ 7 G06F13/14, 15/163. Модуль матричной коммуникационной сети / И.В.Зотов (РФ). №2000106883/09; заявлено 20.03.2000; опубл. 10.06.2001, Бюл. №16.-41 с.

23. Патент №2222044 РФ, МКИ 7 G06F15/173. Модуль для ретрансляции сообщений в коммутационной структуре / Ю.В.Беляев,

24. Е.Г.Анпилогов, И.В.Зотов (РФ). №2002108943/09; заявлено 8.04.2002; опубл. 20.01.2004, Бюл. №2. - 16 с.

25. Патент №2249848 РФ, МКИ 7 G06F15/163. Модуль для передачи и вещания сообщений в матричном коммутаторе / Е.Г.Анпилогов, Ю.В.Беляев, И.В.Зотов (РФ). -№2003104071/09; заявлено 11.02.2003; опубл. 10.04.2005, Бюл. №10.-23 с.

26. Патент №2249849 РФ, МКИ 7 G06F15/163. Модуль для обмена сообщениями / А.А.Иванов, Е.Г.Анпилогов, И.В.Зотов, В.В.Ефремов (РФ). -№2003129963/09; заявлено 08.10.2003; опубл. 10.04.2005, Бюл. №10. 19 с.

27. Патент №5559970 США, МКИ 8 G06F 11/16. Multi-processor switch and main processor switching method / Yokio Kosuge, Kasumasa Takeda, (Япония). -№09/326621; заявлено 07.06.1999; опубл. 31.12.2002.

28. Патент №7058062 США, МКИ 8 H04L12/56. Packet switching system having self-routing switches / S.Tanabe, T.Suzuki, S.Gohara et al. (Япония). -№040466; заявлено 09.01.2002; опубл. 06.06.2006. 29 с.

29. Патент №7080156 США, МКИ 8 G06F15/173. Message routing in а torus interconnect / W.S.Lee, N.Talagala, F.Chong(Jr.) et al. (США). -№104923; заявлено 21.03.2002; опубл. 18.07.2006. 17 с.

30. Питерсон Дж. Теория сетей Петри и моделирование систем: пер. с англ. М.: Мир, 1984. - 264 е., ил.

31. Свидетельство о регистрации программы для ЭВМ №2007611310. Визуальная среда имитационного моделирования VisualQChart / И.В.Зотов, О.В.Крикунов и др. (РФ). М.: РосПатент; заявлено 13.02.2007; дата регистрации 27.03.2007.

32. Степанян С.О. Коммуникационные сети в многопроцессорных ЭВМ Текст. / С.О.Степанян // Автоматика и вычислительная техника. 1987. №3. С. 31-43.

33. Сусин П.В. Коммутатор с распределенными выходными очередями для параллельных систем логического управления: дис.канд. техн. наук: 05.13.05: защищена 20.06.2003: утв. 14.11.2003 / Сусин Павел Викторович. -Курск, 2003.-220 с.

34. Угрюмов Е.П. Цифровая схемотехника. СПб.: БВХ-Перербург, 2004.-528 е.: ил.

35. А 2 Gb/s 256*256 CMOS crossbar switch fabric core design using pipelined MUX Ting Wu; Chi-Ying Tsui; Hamdi, M.; Circuits and Systems, 2002. ISCAS 2002. IEEE International Symposium on Volume 2, 26-29 May 2002 Page(s):II-568 -11-571 vol.2

36. Yoo B.S., Das C.R., Jong Kim. A performance modeling technique for mesh-connected multicomputers Текст. // Parallel and Distributed Systems, 1997. Proceedings., 1997 International Conference on 10-13 Dec. 1997 Page(s):408 -413

37. A reconfigurable crossbar switch with adaptive bandwidth control for networks-on-chip Donghyun Kim; Kangmin Lee; Se-joong Lee; Hoi-Jun Yoo; Circuits and Systems, 2005. ISCAS 2005. IEEE International Symposium on 2326 May 2005 Page(s):2369 2372 Vol. 3

38. A two-dimensional scalable crossbar matrix switch architecture Jong Arm Jum; Sung Hyuk Byun; Byung Jun Ahn; Seung Yeob Nam; Dan Keun Sung; Communications, 2003. ICC '03. IEEE International Conference on Volume 3, 1115 May 2003 Page(s):1892 1896 vol.3

39. An Application-Specific Design Methodology for On-Chip Crossbar Generation Murali, S.; Benini, L.; De Micheli, G.; Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on Volume 26, Issue 7, July 2007 Page(s):1283 -1296

40. Yi Pen; Zheng, S.Q.; Keqin Li; Hong Shen. An improved generalization of mesh-connected computers with multiple buses Текст. // Parallel and Distributed Systems, IEEE Transactions on Volume 12, Issue 3, March 2001 Page(s):293 305

41. Analysis of fault-tolerant multipath crossbars Mir, N.F.; Global Telecommunications Conference, 2003. GLOBECOM '03. IEEE Volume 5, 2003 Page(s):2908 2912 vol.5

42. Application-Independent Defect-Tolerant Crossbar Nano-Architectures Tahoori, M.B.; Computer-Aided Design, 2006. ICCAD '06. IEEE/ACM International Conference on Nov. 2006 Page(s):730 734

43. Awdeh R.Y., Mouftah H.T. Survey of ATM switch architectures // Computer Networks & ISDN Systems. 1995. vol. 27. PP. 1567-1613.

44. Bhuyan L.N., Agrawal D.P. Generalized hypercube and hyperbus structures for a computer network // IEEETC. 1984. - Vol. C-33, №4. - PP. 323-333.

45. Cell Switched Network-on-Chip ~ Candidate for Billion-Transistor System-on-Chips Yuhua Chen; International SOC Conference, 2006 IEEE Sept. 2006 Page(s):57 -60

46. Chancy Т., Fingerhut J.A., Flucke M., Turner J.S. Design of a gigabit ATM switch// Proceedings of IEEE INFOCOM '97, Kobe. Japan, 7-11 April 1997. vol.1. PP. 2-11.

47. Chi H.C., Tamir Y. Starvation prevention for arbiters of crossbars with multi-queue input buffers// Proceedings of COMPCON '94, San Francisco, -February, 1994, - pp. 292-297.

48. Chi H.C., Tamir Y. Decomposed arbiters for large crossbars with multi-queue input buffers // IEEE International Conference on Computer Design: VLSI in Computers and Processors, Cambridge, - October, - 1991, - PP. 233-238.

49. Choudhury A.K., Hahne L.E. Dynamic queue length thresholds in a shared memory ATM switch// Proceedings of IEEE INFOCOM '96, San Francisco, - March, 1996, - vol.2, - PP. 679-687.

50. Chuang S.-T., Goel A., McKeown N., Prabhakar B. Matching output queuing with a combined input output queued switch // Computer Systems Technical Report CSL-TR-98-758, March 1998.

51. Design and implementation of fault-tolerant and cost effective crossbar switches for multiprocessor systems Wang, K.; Wu, C.-K.; Computers and Digital Techniques, IEE Proceedings-Volume 146, Issue 1, Jan. 1999Page(s):50-56

52. Feng, T-Y. A survey of interconnection network Текст. // IEEE Computer. 1981. - Vol. 14, № 12. - PP. 12-27.

53. Implementation of a Configurable Crossbar Switch for Prototyping of Single-Chip Multiprocessors Cote, E.; Manjikian, N.; Circuits and Systems, 2006 IEEE North-East Workshop on June 2006 Page(s):197 200

54. Implementation of a crossbar network using quantum-dot cellular automata Graunke, C.R.; Wheeler, D.I.; Tougaw, D.; Will, J.D.; Nanotechnology, IEEE Transactions on Volume 4, Issue 4, July 2005 Page(s):435 440

55. Jigang Wu Srikanthan, T. Fast reconfiguring mesh-connected VLSI arrays Текст. // Circuits and Systems, 2004. ISCAS '04. Proceedings of the 2004 International Symposium on Volume 2, 23-26 May 2004 Page(s):II 949-52 Vol.2

56. Karol M., Eng K., Obara H. Improving the performance of input-queued ATM packet switches // Proceedings of INFOCOM/92, PP.110-115.

57. Karol M., Hluchyj M. Queueing in high-performance packet-switching // IEEEJ. Selected Area Communications, Dec. 1988, - vol.6, - PP. 1587-1597.

58. Karol M., Hluchyj M., Morgan S. Input versus output queueing on a space division switch // IEEETrans. Communications, 1987, - PP.1347-1356.

59. Keshav, S. Issues and trends in router design Текст. / S.Keshav, R.Sharma//IEEE Communications Magazine. 1998. Vol.36, №5. P. 144-151.

60. Kupta P., McKeown N. Design and implementation of a fast crossbar ^ scheduler // Proceedings of Hot Interconnects 6, Stanford, - Aug 1998, - PP. 7784.

61. McKeown N., Izzard M., Mekkittikul A., Ellersick W., Horowitz M. The Tiny Tera: a packet switch core // Proceedings of Hot Interconnects IV, Stanford, -Aug 1996,-PP. 161-173.

62. McKeown N., Anantharam V., Walrand J. Achieving 100% throughput in an input-queued switch // Proceedings of INFOCOM, 1996, - PP. 296-302.

63. Mekkittikul, A. A practical scheduling algorithm to achieve 100% throughput in input-queued switches Текст. / A.Mekkittikul, N.McKeown // Proc. INFOCOM-98, San Francisco, 29 March 2 April 1998. - San Francisco, 1998, Vol.2. - P. 792-799.

64. Message Passing Interface Forum, MPI: A Message-Passing Interface Standard, Version 1.1, Jun. 1995.

65. Novel Design of Three-Dimensional Crossbar for Future Network on Chip based on Post-Silicon Devices Nomura, K.; Abe, K.; Fujita, S.; Detion, A.; Nano-Networks and Workshops, 2006. NanoNet '06. 1st International Conferencei* on Sept. 2006 Page(s): 1 5

66. OpenMP Application Programming Interface, Version 2.5, May 2005.

67. Patyra M., Maly W. Circuit design for a large area high-performance crossbar switch // Proceedings. 1991 International Workshop on Defect and Fault Tolerance on VLSI Systems, -18-20 Nov. 1991, PP. 32-45.

68. Tamir Y., Frazier G. High performance multi-queue buffers for VLSI communication switches // Proc. of 15th Ann. Symp. on Сотр. Arch., June 1988, - PP.343-354.

69. Tamir Y., Chi H.C. Symmetric crossbar arbiters for VLSI communication switches // IEEE Transactions on Parallel and Distributed Systems, Jan 1993. vol.4,-no. 1,-PP. 13-27.

70. Tobagi, F.A. Fast packet switch architectures for broadband integrated services digital networks Текст. / F.A.Tobagi // Proc. IEEE. 1990. Vol.78, №1. P. 133-167.

71. Wittie L.D. Communication structures for large networks of microcomputers // IEEE Transactions on Computers. 1981. - Vol. C-30, №4. - PP. 264273.

72. Zotov I.V. Parallelized-pipeline communication architecture Текст. /th