Введение к работе
Актуальность темы исследования определяется важностью решения проблем разработки перспективных высокопроизводительных многопроцессорных вычислительных систем (МВС) - суперкомпьютеров. Среди них одной из центральных остается проблема разработки наращиваемых коммуникационных сетей и коммутаторов с высокой пропускной способностью и быстродействием. Они решают задачу организации эффективной параллельной передачи данных. Критериями эффективности служат бесконфликтность и быстрота передачи данных, и сложность сети или коммутатора, которые противоречат друг другу. Исследования по этой задаче ведутся уже в течение нескольких десятилетий, но еще не дали универсального высокоэффективного решения. Недаром в 1994 г. Национальный научный фонд США включил ее в число наиболее приоритетных задач на следующее десятилетие. Это десятилетие уже заканчивается, а в научной литературе не спадает интерес к «коммутаторной» тематике Прогнозируемое число процессоров (десятки и более тысяч) в перспективных МВС обостряет проблему и бросает вызов разработчикам. Развитие микроэлектроники и оптоэлектроники за счет повышения сложности электронных схем, и числа и свойств каналов открывает новые возможности в разработке новых структур коммутаторов и/или способов их функционирования.
Цель работы. Целью работы является решение крупной народнохозяйственной проблемы обеспечения наращиваемости и повышение пропускной способности и быстродействия коммутаторов для современных и перспективных многопроцессорных вычислительных систем с учетом принятых ограничений на их сложность.
Для достижения этой цели необходимо провести разработку и исследование новых структур коммутаторов и новых эффективных способов организации в них параллельной и бесконфликтной передачи данных. При этом необходимо рассматривать способы передачи, которые эффективны не в асимптотической по числу узлов (портов) области, а рабочей области до сотен тысяч узлов.
Объектами исследования являются распределенные (прямые) коммутаторы, которые имеют наибольшие возможности для обеспечения наращиваемости МВС по сравнению с наиболее развитыми сосредоточенными (выделенными - в виде единого устройства) коммутаторами, и детерминированные способы параллельной бесконфликтной передачи данных, которые обеспечивают соблюдение гарантированных времен передачи.
Решаемые задачи. Общей задачей, решаемой в диссертации, является достижение для распределенных коммутаторов не меньшего быстродействия, чем для выделенных коммутаторов в рабочей области числа узлов. Эта задача решается в сетевой и перестановочной моделях передачи данных. Для сетевой модели решается задач
ПЧЯШЩЙЬИ/ШЯЯааРрания
наращиваемого мультикольцевого коммутатора со статическими расписаниями, пропускная способность которого пропорциональна числу узлов при малом числе колец. Для перестановочной модели решается задача разработки и исследования способов бесконфликтной реализации по статическим расписаниям произвольной перестановки пакетов данных. Она решается раздельно для коротких и длинных пакетов данных для широкого класса симметричных по узлам коммутаторов.
Методика исследования основана на выделении следующих базовых категорий, в которых осуществляется исследование: сетевая (с произвольным отображением адресов с входа на выход) и перестановочная (с отображением адресов один в один) модели передачи данных; выделенные (сосредоточенные) и прямые (распределенные) коммутаторы различной сложности; пакетная и канальная коммутация; неблокируемые и перестраиваемые коммутаторы; самомаршрутизируемые, забывчивые (в частности - по статическим расписаниям) и рандомизированные способы передачи. Для решения основной задачи выделены такие критерии эффективности как быстрота доставки, вероятность бесконфликтной передачи, пропускная способность, время бесконфликтной реализации произвольной перестановки и сложность коммутатора.
До настоящего времени отсутствуют разработки по некоторым структурам коммутаторов и способам параллельной передачи данных, которые потенциально способны иметь высокие характеристики. Это некоммутируемые сети в сетевой модели и забывчивые способы маршрутизации для прямых коммутаторов в перестановочной модели. Для заполнения таких «белых пятен» в работе предлагается новая сетевая структура (некоммутируемое мультикольцо) и для прямых коммутаторов развиваются способы передачи с использованием простых статических расписаний. Эти способы распространяются на широкий класс симметричных по узлам прямых коммутаторов (со структурой графов Кэли). Проведен сравнительный анализ характеристик разработанных способов и выявлены области их превосходства над известными способами.
Научная новизна.
Создана теория и разработана новая оригинальная структура наращиваемых многокольцевых коммутаторов (некоммутируемых мультиколец). Показано, что пропускная способность некоммутируемых колец в сетевой модели передачи пропорциональна квадрату числа колец и пропорционально числу узлов N при числе колец не больше чем №N.
Разработан новый способ применения некоммутируемых мультиколец со всеми их свойствами для локальных и региональных сетей за счет использования многополосного оптоволоконного кабеля.
Разработан новый оригинальный способ бесконфликтной реализации произвольной перестановки коротких пакетов по статическим расписаниям
малого размера и создана их теория для класса прямых коммутаторов со структурами, восходящими к мультиколыгу и гиперкубу.
- Разработан единый способ бесконфликтной реализации произвольной перестановки длинных пакетов по статическим расписаниям для широкого класса прямых коммутаторов со структурой графов Кэли.
Обоснованность научных положений, теорем и выводов. Научные положения, теоремы и выводы диссертации строго обоснованы с использованием методов теории множеств, теории расписаний, математической логики, алгебры, теории коммутационных сетей, логического и имитационного моделирования и многочисленных экспериментов на разработанных автором программных средствах поиска и моделирования оптимальных мультиколец.
Практическая значимость работы заключается в разработке простых и эффективных способов параллельной передачи данных для МВС с общей памятью и неоднородным доступом (системы SMP cc-NUMA) и способов бесконфликтной параллельной передачи данных для массивно-параллельных МВС (системы МРР). Кроме того, способы передачи по некоммутируемому мультикольцу могут обеспечить значительное повышение пропускной способности локальных и муниципальных кольцевых сетей при использовании многополосного оптоволоконного канала.
Реализация результатов. Результаты и положения диссертации приняты к использованию в ЦНИИМАШ (некоммутируемые и коммутируемые мультик ольца для МВС), в ИНФОТЕХ и ВЛДДИНФО г. Владимир (оптоволоконные мультикольца для региональных сетей), в фирме ProLAN (имитатор многокольцевых сетей). ЦНИИМАШ — акт об использовании результатов диссертации в отраслевых инструментальных средствах для отработки и экспериментального исследования бортовых информационно-управляющих вычислительных комплексов для перспективных изделий. ИНФОТЕХ - акт об использовании результатов диссертации в разработках компании. ВЛАДИНФО - акт об использовании результатов диссертации для проведения усовершенствования узла доступа к Internet. ProLAN - акт о выполнении заказной работы по способам использования мультиколец в коммутируемых локальных сетях и об использовании программы-имитатора мультиколец.
Апробация работы. Основные результаты работы опубликованы в ряде отечественных изданий и докладывались на 17 семинарах и конференциях, в том числе: на Международной конференции РАСО 2001 «Параллельные вычисления и задачи управления», Москва, 2001 (два доклада); и на Второй международной конференции по проблемам управления, Москва, 2003, (двадоклада).
Публикации. По теме диссертации опубликовано 20 печатных работ. Все результаты, представленные в диссертации, получены автором самостоятельно.
Структура и объем работы. Диссертация состоит из Введения, пяти Глав и Приложения. Объем диссертации 246 страниц.
