ВВЕДЕНИЕ

Актуальность темы. Коммутационные устройства (КУ) занимают важное место в структуре современных вычислительных систем (ВС) широкого класса. Они используются в микропроцессорах рабочих станций (Intel, AMD, PowerPC), мультипроцессорах с общей памятью (Sun, HP, Compaq), матричных мультипро­цессорах (Mellanox, IntellaSys, Adapteva) и мультикомпьютерах (Cray, Lenovo, IBM).

Вопросы построения, исследования характеристик и совершенствования коммутационных устройств ВС нашли отражение в работах многих российских и зарубежных ученых. Наиболее значимый вклад внесли В.В. Воеводин, Вл.В. Вое­водин, Э.В. Евреинов, А.В. Каляев, И.А. Каляев, М.Ф. Каравай, В.В. Корнеев, И.И. Левин, Э.В. Мельник, В.С. Подлазов, А.П. Типикин, В.С. Харченко, В.Г. Хо­рошевский, Э.А. Якубайтис, A. Agarwal, L. Benini, M. Chen, E. Cote, G. De Micheli, G. Frazier, N.D. Georganas, C.R. Graunke, M.G. Hluchyj, A. Huang, M.J. Karol, S. Knauer, N. Manjikian, N. McKeown, A. Mekkittikul, S.P. Morgan, S. Murali, M. Na- beshima, H. Obara, S.S. Panwar, F.P. Preparata, Y. Tamir, D. Tougaw, D.I. Wheeler, J.D. Will и др.

Коммутационные устройства, применяемые в современных матричных мультипроцессорах, чаще всего используют режим пакетной коммутации (packet switching), реже - схемную коммутацию (circuit switching). Различные варианты построения КУ отличаются, прежде всего, расположением буферов (очередей), необходимых для временного хранения передаваемых пакетов. В устройствах с входными буферами пакеты со входов первоначально поступают в соответству­ющие FIFO-буферы и только затем коммутируются на требуемые выходы. Такие КУ не предъявляют жестких требований к быстродействию коммутирующей ча­сти и, как правило, обладают низкой аппаратной сложностью, что позволяет ис­

пользовать их при большом числе входов/выходов.

Наибольшая пропускная способность (до 1) достигается в КУ с выходными FIFO-буферами. В подобных устройствах пакеты сразу коммутируются на требу­емые выходы и затем сохраняются в выходных буферах перед выдачей, что ис­ключает блокировки пакетов. Однако такие КУ характеризуются повышенной ап­паратной сложностью и предъявляют серьезные требования к скорости работы коммутирующей части (внутренней скорости КУ), которая должна в несколько раз превышать интенсивность потока пакетов на входах. В связи с этим их приме­нение возможно при небольшом числе входов/выходов nи/или при условии сни­жения внешней скорости работы КУ (скорости работы каналов связи).

Серьезные недостатки устройств, имеющих входные или выходные FIFO- буферы, привели к необходимости поиска комбинированных решений. Наиболее известным из них является коммутатор с виртуальными выходными очередями VOQ (Y. Tamir, N. McKeown, A. Mekkittikul). Идея VOQ-коммутатора нашла от­ражение в устройствах Биркхоффа - фон-Неймана (C.-S. Chang, W.-J. Chen, H.-Y. Huang), в параллельных КУ с множественными входными/выходными очередями PMIOQ (H.-I. Lee, S.-W. Seo) и ряде других. VOQ-коммутаторы способны обеспе­чить максимальную пропускную способность (до 1), однако это требует выполне­ния ряда жестких условий, в частности, удвоенной внутренней скорости КУ. Так­же VOQ-устройства обладают повышенной аппаратной сложностью, асимптоти­ческая оценка которой составляет примерно куб от числа входов/выходов n,что затрудняет их применение в матричных мультипроцессорах.

Альтернативой VOQ-коммутаторам являются коммутаторы с буферизован­ным переключателем (N. McKeown, M. Nabeshima), которые используют простые FIFO-буферы на входах и матрицу регистров (буферизованный переключатель) на выходе.

ка которой представляет собой квадрат от числа входов/выходов п) и имеет про­стую коммутирующую часть, работающую с той же скоростью, что и внешние каналы КУ. Тем не менее, пропускная способность и быстродействие этих устройств в практически значимых случаях значительно ниже соответствующих скоростных показателей VOQ-аналогов. Также в матричных мультипроцессорах применяются КУ с гибридной коммутацией (P. Lotfi-Kamran, M. Modarressi, A. Mazloumi, H. Sarbazi-Azad). Однако они демонстрируют высокую эффективность лишь при определенных видах рабочей нагрузки мультипроцессора.

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

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

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

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

Работа выполнена в соответствии с планом НИР ЮЗГУ в 2015-2019 гг.

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

Для достижения сформулированной цели необходимо решить следующие частные задачи:

1.

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

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

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

Результаты, выносимые на защиту, и их научная новизна:

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

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

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

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

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

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

Практическая значимость работы.

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

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

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

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

Апробация работы. Основные идеи, положения, результаты и выводы дис­сертационной работы были заслушаны и получили положительную оценку на XXVI Международной научно-практической конференции «Научный форум: тех­нические и физико-математические науки» (г. Москва, 2019 г.), на Международ­ной научно-практической конференции «Наука сегодня: вызовы и решения» (г. Вологда, 2019 г.), на VI всероссийской научно-практической конференции «Ин­теллектуальные информационные системы: тенденции, проблемы, перспективы» (г. Курск, 2018 г.), а также на научных семинарах кафедры информационных си­стем и технологий ЮЗГУ, проводившихся с 2015 по 2019 гг.

Публикации по теме диссертации. Результаты диссертационной работы отражены в 10 публикациях, в числе которых 1 статья в научном журнале, входя­щем в международную базу Scopus, а также 4 статьи, опубликованные в научных изданиях из Перечня центральных рецензируемых журналов и изданий.

Личный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В опубликованных в соавторстве работах личный вклад соискателя сводится к следующему: в [10, 21, 61] сформулированы ключе­вые особенности разработанного метода коммутации пакетов, выполнена теоре­тическая оценка времени прохождения пакетов через матрицу регистров; в [8, 9, 20] изложены особенности имитационного моделирования разработанного устройства, результаты оценки его скоростных характеристик; в [11, 13] описана структурная организация коммутационного устройства; в [19] сформулирован ал­горитм коммутации пакетов.

Объем и структура работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка сокращений и условных обозначений, списка литературы и приложений. Работа содержит 187 страниц текста (с учетом 5 приложений) и поясняется 56 рисунками и 9 таблицами; список литературы включает 132 наименования.

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

1.