Метод, алгоритм и устройство коммутации с параллельно-конвейерной диспетчеризацией пакетов в матричных мультипроцессорах тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат наук Мохаммед Ажмаль Джамиль Абдо

• Мохаммед Ажмаль Джамиль Абдо
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Мохаммед Ажмаль Джамиль Абдо

ВВЕДЕНИЕ

1. МЕТОДЫ И УСТРОЙСТВА КОММУТАЦИИ ПАКЕТОВ В МАТРИЧНЫХ МУЛЬТИПРОЦЕССОРАХ

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

1.2. Архитектура современных матричных СБИС-мультипроцессоров

1.3. Коммутационные средства матричных СБИС-мультипроцессоров

Выводы

2. МЕТОД И АЛГОРИТМ КОММУТАЦИИ С ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНОЙ ДИСПЕТЧЕРИЗАЦИЕЙ ПАКЕТОВ. СТРУКТУРНАЯ МОДЕЛЬ КОММУТАЦИОННОГО УСТРОЙСТВА

2.1. Общие особенности разработанного метода коммутации пакетов

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

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

2.4. Алгоритм коммутации с параллельно-конвейерной диспетчеризацией пакетов

2.5. Оценка эффективности использования матрицы регистров коммутационного устройства

2.6. Оценка быстродействия коммутационного устройства при использовании

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

Выводы

3. ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК КОММУТАЦИОННОГО УСТРОЙСТВА С ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНОЙ ДИСПЕТЧЕРИЗАЦИЕЙ ПАКЕТОВ

3.1. Методика исследования характеристик коммутационного устройства

3.2. Построение имитационной модели коммутационного устройства

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

3.4. Исследование пропускной способности коммутационного устройства

3.5. Оценка полного времени прохождения пакетов через коммутационное

устройство

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

3.7. Оценка средней загрузки матрицы регистров

Выводы

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

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

4.2. Требования к функциональным блокам коммутационного устройства

4.3. Структура и формат передаваемых пакетов

4.4. Функциональные схемы блоков коммутационного устройства

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

Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ

СПИСОК ЛИТЕРАТУРЫ

Приложение

Приложение

Приложение

Приложение

Приложение

Введение диссертации (часть автореферата) на тему «Метод, алгоритм и устройство коммутации с параллельно-конвейерной диспетчеризацией пакетов в матричных мультипроцессорах»

ВВЕДЕНИЕ

Актуальность темы. Коммутационные устройства (КУ) занимают важное место в структуре современных вычислительных систем (ВС) широкого класса. Они используются в микропроцессорах рабочих станций (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-буферы и только затем коммутируются на требуемые выходы. Такие КУ не предъявляют жестких требований к быстродействию коммутирующей части и, как правило, обладают низкой аппаратной сложностью, что позволяет ис-

пользовать их при большом числе входов/выходов. Однако доказано (M.J. Karol, M.G. Hluchyj, S.P. Morgan), что подобные устройства (без модификации дисциплин обслуживания буферов) практически не могут обеспечить пропускную способность выше 0.64 из-за возникновения блокировок пакетов в головных регистрах буферов (HOL blocking).

Наибольшая пропускная способность (до 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-буферы на входах и матрицу регистров (буферизованный переключатель) на выходе. Они обладают относительно низкой аппаратной сложностью (асимптоти-

ка которой представляет собой квадрат от числа входов/выходов п) и имеет простую коммутирующую часть, работающую с той же скоростью, что и внешние каналы КУ. Тем не менее, пропускная способность и быстродействие этих устройств в практически значимых случаях значительно ниже соответствующих скоростных показателей УОР-аналогов. Также в матричных мультипроцессорах применяются КУ с гибридной коммутацией (Р. Ьо1й-Катгап, М. Моёаггевв1, А. Магнит!, Н. БагЬагьАгаё). Однако они демонстрируют высокую эффективность лишь при определенных видах рабочей нагрузки мультипроцессора.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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. МЕТОДЫ И УСТРОЙСТВА КОММУТАЦИИ ПАКЕТОВ В МАТРИЧНЫХ МУЛЬТИПРОЦЕССОРАХ

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

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

Матричные мультипроцессоры (ММП) - один из перспективных подклассов параллельных вычислительных систем, способных эффективно решать как отдельные сложные сильно связанные задачи, так и комплексы независимых или слабо связанных задач [92]. В основе архитектуры ММП лежит множество идентичных процессорных модулей (ядер), объединенных коммуникационной сетью (КС) с матричной топологией [64]. Конструктивная однородность ММП существенно упрощает и удешевляет их проектирование, изготовление и последующее программирование [3]. Также значительно упрощается решение задач, нацеленных на обеспечение повышенной надежности и гибкости систем на основе ММП [1, 58, 126].

В качестве ядер ММП могут выступать процессоры самой разной архитектуры. Это могут быть как относительно простые процессоры с сокращенным набором инструкций (МБС-процессоры) [112], так и традиционные процессоры с полным набором команд (ОБС-процессоры) [122, 123, 125]. КС ММП чаще всего имеет двумерную пространственную организацию с незамкнутыми границами («классическая» двумерная матрица), однако известны примеры мультипроцессоров (или проекты ММП) с многомерной матричной топологией и/или с замкнутыми границами [15, 34, 37, 42, 45, 60, 113, 119, 127, 130].

Концепция матричных мультипроцессоров известна уже длительный период времени и восходит к систолическим и волновым процессорам, созданным в 80-х годах прошлого века [3, 58]. Возрождение повышенного интереса к ММП в последние годы связано, прежде всего, с появившейся возможностью их полноценной СБИС-реализации [63, 124]. Действительно, современная технология производства сверхбольших интегральных схем (СБИС) позволяет выпускать микросхемы, содержащие более 10 млрд. транзисторов на кристалле, чего достаточно для размещения нескольких десятков и даже сотен мощных процессорных узлов, нескольких контроллеров памяти и дополнительной аппаратуры (устройств ввода-вывода, модулей сжатия данных, шифрования и т.д.) [5, 115, 122]. Это дает возможность создания компактных и энергоэффективных встраиваемых систем, соизмеримых по производительности с суперкомпьютерами, выпущенными 10-15 лет назад [16].

Спектр выпускаемых современной промышленностью СБИС ММП весьма широк и представлен многими известными производителями. К их числу относятся Intel (мультипроцессор Xeon W-3175X, объединяющий 28 ядер [91]), Cavium (СБИС ThunderX2 CN99XX, включающая 32 ядра [121]), Mellanox (72-ядерная система TILE-Gx72 [122]), Adapteva (СБИС Epiphany V на основе 1024 RISC-ядер [112]). Имеются также многочисленные технические решения и проекты однокристальных ММП [25, 43, 47, 48, 87, 104, 130, 132].

1.2. Архитектура современных матричных СБИС-мультипроцессоров

Особенности архитектуры современных СБИС ММП хорошо иллюстрируются приборами Epiphany V фирмы Adapteva [112] и TILE-Gx фирмы Mellanox (изначально - компании Tilera, впоследствии прошедшей слияние с фирмой Mellanox) [122, 125].

СБИС-мультипроцессор Epiphany V реализуется по 16-нанометровой микроэлектронной технологии. Он состоит из массива процессоров размерностью 32 х 32, взаимодействующих через высокоскоростную матричную коммуникаци-

онную сеть, и имеет физически распределенную, но логически разделяемую память с 64-разрядной адресацией. Каждый узел мультипроцессора представляет собой RISC-процессор, поддерживающий 64-разрядные операции с плавающей точкой и способный работать под управлением отдельной операционной системы в режиме MIMD. Epiphany использует линейную кэш-память, доступную для чтения и записи всем процессорам системы.

На рис. 1.1 изображена обобщенная структура системы Epiphany V.

Рисунок 1.1. Обобщенная структура СБИС Epiphany V: RISC CPU - процессорное ядро; NOC - коммутационный узел; MEMORY - локальная память

Использование четырех 128-разрядных настраиваемых портов ввода-вывода (South IO, North IO, West IO, East IO) позволяет объединять множество СБИС Epiphany в систему более высокого уровня иерархии. Результирующая СБИС-система может содержать до 1 миллиарда процессорных ядер и иметь емкость распределенной памяти до 1 петабайта (см. рис. 1.2).

32X32 RISC ARRAY (64MB)

1 1

32x32 RISC ARRAY (64MB)

32x32 RISC ARRAY (64MB)

Рисунок 1.2. Схема соединения СБИС Epiphany V в систему более высокого уровня интеграции

Особый интерес представляет коммуникационная подсистема мультипроцессора Epiphany. В ее основе лежит матричная сеть пакетной коммутации emesh, объединяющая 3 независимых 136-разрядных сети, обеспечивающих раздельную передачу запросов чтения и записи. Транслируемые в сети emesh пакеты имеют разрядность 136 бит и передаются между соседними процессорами за 1.5 такта (такие пакеты называют флитами [98]). Формат каждого пакета включает 64-разрядное поле данных, 64-разрядное поле адреса и 8-разрядное управляющее поле, причем поле данных в некоторых случаях может использоваться для передачи дополнительного адреса возврата. Маршрутизация пакетов осуществляется на основе статического алгоритма XYZ-маршрутизации [64]. Коммутация пакетов в каждом процессоре обеспечивается коммутационным узлом с простыми FIFO-буферами и циклическим арбитром. Предусмотрена аппаратная блокировка потери пакетов при высокой нагрузке на сеть.

Особенностью рассмотренных выше СБИС-мультипроцессоров Epiphany является использование относительно простых ядер, что позволило объединить свыше тысячи процессоров на кристалле. В отличие от Epiphany, мультипроцессоры TILE корпорации Mellanox содержат «всего лишь» несколько десятков процессорных ядер, однако в случае TILE это высокопроизводительные трехконвей-ерные CISC-процессоры с двумя уровнями кэш-памяти каждый [122].

Линейка СБИС-систем TILE, выпускаемых в последние годы, охватывает 72-ядерные мультипроцессоры TILE-Gx8072 (содержащие 9 х 8 ядер), 64-ядерные системы TILE64 и TILEPro64 (имеющие 8 х 8 ядер), 36-ядерные приборы TILEPro36, TILE-Gx8036 (включающие 6 х 6 ядер), 16-ядерные мультипроцессоры TILE-Gx8016 (объединяющие 4 х 4 ядер) и 9-ядерные системы TILE-Gx8009 (содержащие 3 х 3 ядер). С точки зрения архитектуры все указанные системы довольно близки друг к другу, поэтому изучить их особенности можно на примере одной СБИС.

Структурная организация СБИС-мультипроцессора TILE-Gx8036 приведена на рис. 1.3 [122, 125]. Прибор TILE-Gx8036 объединяет 36 процессорных ядер (ПЯ), взаимодействующих через матричную коммутационную сеть iMesh с конфигурацией 6 х 6. Все ядра функционируют на частотах от 1 до 1.2 ГГц. Каждое ПЯ содержит 64-разрядный 3-конвейерный процессор, кэш-память двух уровней (объемом 32 и 256 кбайт соответственно), а также коммутационное устройство для подключения к среде iMesh. Каждое ядро способно независимо работать под управлением автономной операционной системы или во взаимосвязи с другими ядрами под управлением мультипроцессорной версии Linux. В системе также имеется кэш-память третьего уровня объемом 9 Мбайт.

Коммуникационная подсистема TILE-Gx8036 представлена матричной сетью iMesh. Сеть iMesh объединяет пять параллельно работающих высокоскоростных матричных сетей, имеющих суммарную пропускную способность 60 Тбит/сек. Аналогично сети emesh мультипроцессора Epiphany, сеть iMesh реализует параллельную передачу пакетов (флитов). Маршрутизация пакетов осу-

ществляется на основе метода сШ-Шш^И-маршрутизации, что позволяет снизить время передачи пакета за 1 такт.

■< ■

■и ■

* Ю

8 ^ з О.

од■

* :о

Ь- ■<■

■Контроллер памяти DDR3 '(О)

i

I

I

I

I

<—►

«-►

<-►

«-►

<-►

I

I

I

I

I

' Контроллер памяти DDR3 '(1) .

Рисунок 1.3. Структурная организация СБИС TILE-Gx8036

Мультипроцессор TILE-Gx8036 включает не только процессорные ядра с коммуникационной сетью, но и объединяет множество контроллеров памяти и интерфейсов ввода-вывода. В частности, прибор содержит два 72-разрядных контроллера синхронной динамической памяти DDR3, что дает возможность подключения до 512 Гбайт оперативной памяти. Имеется также 3 контроллера PCI

Express (PCIE), порт SPI, 4 порта I2C, 10 Gigabit Ethernet (XAUI), до 16 портов SGMII, отладочный интерфейс периферийного сканирования JTAG. Также система содержит модули шифрования и сжатия данных MiCA. Еще одной особенностью прибора TILE-Gx8036 является поддержка технологии динамического распределенного кэша (Dynamic Distributed Cache - DDC), что позволяет реализовать когерентность кэш-памяти по всей матрице ядер на аппаратном уровне. Благодаря DDC, СБИС TILE-Gx8036 способна выполнять многопоточные приложения с разделяемой памятью как ccNUMA-мультипроцессор. Потребляемая мощность мультипроцессора TILE-Gx8036 составляет от 20 до 28 Вт.

1.3. Коммутационные средства матричных СБИС-мультипроцессоров

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

КС ММП представляет собой матрицу идентичных коммутационных устройств, каждое из которых соединено со своими ближайшими соседями согласно топологической структуре сети (см., например, рис. 1.3). Коммутационные устройства (КУ), применяемые в современных мультипроцессорах, чаще всего используют режим пакетной коммутации (packet switching) [69, 73, 78, 110, 114], реже - схемную коммутацию (circuit switching), отдельно либо в сочетании с пакетной коммутацией [70, 81, 83, 101-103]. Они во многом подобны ATM-коммутаторам вычислительных сетей, абонентских систем и мультикомпьютеров, реализующим принцип wormhole-маршрутизации [34-37, 67, 68, 76, 80, 107, 111]. Основным отличием КУ ММП является то, что пакеты имеют значительно меньшую длину (длина ATM-пакета, согласно стандарту, составляет 64 байта [107]) и разбиваются на фрагменты одинаковой разрядности, которые передаются по шинам в параллельном коде за один-два такта. Указанные фрагменты (называемые

флитами, flit) могут группироваться (режим групповой передачи) либо передаваться независимо друг от друга (режим независимой передачи) [42, 74, 84, 116]. При независимой передаче разрядность флитов получается несколько больше, чем при групповой передаче, поскольку адрес приемника содержится в каждом флите, однако процедуры маршрутизации и коммутации значительно проще, так как не требуется поддержка механизма виртуальных каналов wormhole-маршрутизации, что приводит к более простым схемотехническим решениям [24, 29, 33, 42, 56].

КУ ММП включает множество входов (входных портов), множество выходов (выходных портов) и состоит из коммутирующей и буферизующей. Коммутирующую часть нередко называют переключателем, а буферизующую - внутренней памятью КУ. Поступая на один из входов, каждый пакет обрабатывается коммутирующей частью и согласно адресу, указанному в заголовке или адресном поле пакета, выдается в определенный выходной порт. Из-за особенностей архитектуры КУ может иметь либо не иметь возможности передавать все входящие пакеты на выходы одновременно. Если такой возможности нет, то поступающие пакеты должны быть организованы в очереди во избежание потери пакетов, что является функцией буферизующей части.

Возможны различные варианты взаимного расположения коммутирующей и буферизующей частей в структуре КУ, существенно влияющие на ключевые характеристики устройства (рис. 1.4).

В устройствах с входным расположением буферов (см. рис. 1.4,а) пакеты со входов первоначально поступают в соответствующие FIFO-буферы и только затем коммутируются на требуемые выходы [27, 32, 95]. Такие КУ не предъявляют жестких требований к быстродействию коммутирующей части и, как правило, обладают низкой аппаратной сложностью, что позволяет использовать их при большом числе входов/выходов. Однако доказано [94], что подобные устройства (без модификации дисциплин обслуживания буферов) практически не могут обеспечить пропускную способность выше 0.64 из-за возникновения блокировок пакетов в головных регистрах буферов (Head of line blocking = HOL blocking). Их

Список литературы диссертационного исследования кандидат наук Мохаммед Ажмаль Джамиль Абдо, 2019 год

СПИСОК ЛИТЕРАТУРЫ

1. Андреев А.М., Можаров Г.П., Сюзев В.В. Многопроцессорные вычислительные системы: теоретический анализ, математические модели и применение: учеб. Пособие. - М.: Изд-во МГТУ им. Н. Э. Баумана, 2011. - 332 с.

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

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

4. Градштейн И.С., Рыжик И.М. Таблицы интегралов, сумм, рядов и произведений. 4-е изд. - М.: Физматгиз, 1963. - 1100 с.

5. Елизаров Г.С., Корнеев В.В., Тарасов И.Е., Советов П.Н. Основные тенденции развития архитектур специализированных многоядерных процессоров // Известия высших учебных заведений. Электроника. 2018. Т. 23. № 2. С. 161-172.

6. Емельянов С.Г., Зотов И.В., Титов В.С. Архитектура параллельных логических мультиконтроллеров. - М.: Высшая школа, 2009. - 233 с.

7. Зотов, И.В. Визуальная среда для имитационного моделирования коммутаторов и коммуникационных сетей / Перспективы развития систем управления оружием: сборник докладов IV научно-практической конференции, Курск, 19-20 сентября 2007 г. М.: Изд-во «Бедретдинов и Ко», 2007. С. 71-82.

8. Зотов И.В., Мохаммед А.Д. Коммутационное устройство с параллельно-конвейерной диспетчеризацией пакетов для матричных мультипроцессоров / Научный форум: Технические и физико-математические науки: сб. ст. по материалам XXVI Международной научно-практической конференции (12-14 августа 2019 г.). - № 7(26). - М., Изд-во «МЦНО», 2019. С. 19-27.

9. И.В. Зотов, Мохаммед А.Д. Коммутационный процессор с параллельно-конвейерно-параллельной обработкой пакетов / «ИСТ-2019» (20 мая 2019 г.). -Курск: ЗАО «Университетская книга», 2019 г. С. 6-8.

10.Зотов И.В., Мохаммед Ажмаль. Метод параллельно-конвейерно-параллельной коммутации пакетов для матричных мультипроцессоров // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2018. Т.8, №3 (28). С. 6-15.

11.Зотов И.В., Мохаммед А.Д. Параллельно-конвейерно-параллельный коммутатор для матричных СБИС-мультипроцессоров / Наука сегодня: вызовы и решения: Материалы Международной научно-практической конференции (30 января 2019 года) - Вологда: ООО «Маркер», 2019. С. 19-21.

12.Зотов, И.В. Теоретические основы синтеза схем быстродействующих устройств распределенной децентрализованной координации параллельных микропрограмм в мультиконтроллерах: дис. ... д-ра техн. наук: 05.13.05: защищена 07.12.06: утв. 15.03.07 / Зотов Игорь Валерьевич. Курск, 2007. 383 с.

13.Зотов И.В., Шаршов А.В., Мохаммед А.Д. Алгоритм отказоустойчивой маршрутизации пакетов с динамической модификацией направлений передачи для матричных СБИС-систем // Информационно-измерительные и управляющие системы. 2017. Т.15. №5. С. 17-23.

14.Каляев И.А., Дордопуло А.И., Левин И.И., Федоров А.М. Развитие отечественных многокристальных реконфигурируемых вычислительных систем: от воздушного к жидкостному охлаждению // Труды СПИИРАН. 2017. № 1 (50). С. 5-31.

15.Каравай М.Ф., Подлазов В.С. Расширенный обобщенный гиперкуб как отказоустойчивая системная сеть для многопроцессорных систем / Управление большими системами: сборник трудов. 2013. № 45. С. 344-371.

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

17.Кремер, Н.Ш. Теория вероятности и математическая статистика [Текст]: Учеб. для вузов - 3-е изд. перераб. и доп. - М.: «ЮНИТИДАНА», 2004. - 573 с.

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

19.Мохаммед А.Д., Зотов И.В. Алгоритм параллельно-конвейерно-параллельной коммутации пакетов в матричных мультипроцессорах / Интеллектуальные информационные системы: тенденции, проблемы, перспективы: Материалы докладов VI всероссийской очной научно-практической конференции «ИИС-2018» (23 ноября 2018 года) - Курск: ЗАО «Университетская книга», 2018. С. 121-125.

20.Мохаммед А.Д., Зотов И.В. Исследование пропускной способности па-раллельно-конвейерно-параллельного коммутационного устройства // Телекоммуникации. 2019. №6. С. 2-9.

21.Мохаммед А.Д., Зотов И.В., Передельский Г.И. Метод и алгоритм парал-лельно-конвейерно-параллельной коммутации пакетов в мультипроцессорах // Известия ВУЗов. Приборостроение. 2019. Т.62, №6. С. 524-533.

22.Мохаммед А.Д. Метод и устройство параллельно-конвейерно-параллельной коммутации пакетов для матричных мультипроцессоров / Интеллектуальные информационные системы: тенденции, проблемы, перспективы: Материалы докладов VI всероссийской очной научно-практической конференции «ИИС-2018» (23 ноября 2018 года) - Курск: ЗАО «Университетская книга», 2018. С. 125-129.

23.Новоселов С.И. Специальный курс элементарной алгебры. - М.: Высшая школа, 1962. - 564 с.

24.Пат. №2103729 Рос. Федерация. Матричный коммутатор / Ерохин А.В., Фрадкин Б.Г., Левин И.И., Рыжих О.А.; опубл. 27.01.98.

25.Пат. №2134448 Рос. Федерация. Однородная вычислительная среда с двуслойной программируемой структурой / Бачериков Г.И., Геворкян В.И., Кро-хин В.М.; опубл. 10.08.99.

26.Пат. №2168204 Рос. Федерация. Модуль матричного коммутатора / Попов К.А., Зотов И.В., Титов В.С.; опубл. 27.05.01.

27.Пат. №2168755 Рос. Федерация. Модуль матричной коммуникационной сети / Зотов И.В.; опубл. 10.06.01.

28.Пат. №2178584 Рос. Федерация. Модуль коммуникационной сети, предназначенный для передачи сообщений, обмена сообщениями и организации вещательных режимов обмена сообщениями / Беляев Ю.В., Зотов И.В.; опубл. 20.01.02.

29.Пат. №2194302 Рос. Федерация. Ячейка матричного коммутатора с потоковой настройкой / Карандин В.Н., Морозов А.В., Нежурина М.И., Щербина И.Е.; опубл. 10.12.02.

30.Пат. №2222044 Рос. Федерация. Модуль для ретрансляции сообщений в коммутационной структуре / Беляев Ю.В., Анпилогов Е.Г., Зотов И.В.; опубл. 20.01.04.

31.Пат. №2249848 Рос. Федерация. Модуль для передачи и вещания сообщений в матричном коммутаторе / Анпилогов Е.Г., Беляев Ю.В., Зотов И.В.; опубл. 10.04.05.

32.Пат. №2249849 Рос. Федерация. Модуль для обмена сообщениями / Иванов А.А., Анпилогов Е.Г., Зотов И.В. [и др.]; опубл. 10.04.05.

33.Пат. №2251792 Рос. Федерация. Матричный коммутатор с программируемой логикой / Жила В.В., Осовский А.В., Кутузов Д.В.; опубл. 10.05.05.

34.Пат. N5151996 США. Multi-dimensional message transfer router / Hillis W.D. (США); опубл. 29.09.92.

35.Пат. N5333279 США. Self-timed mesh routing chip with data broadcasting / Dunning D. (США); опубл. 26.07.94.

36.Пат. N7058062 США. Packet switching system having self-routing switches / Tanabe S., Suzuki T., Gohara S. [et al.] (Япония); опубл. 06.06.06.

37.Пат. N7080156 США. Message routing in a torus interconnect / Lee W.S., Talagala N., Chong F. (Jr.) [et al.] (США); опубл. 18.07.06.

38.Пат. N7852866 США. Low Complexity Scheduling Algorithm for a Buffered Crossbar Switch with 100% Throughput / H.J. Chao, S.S. Panwar, Y. Shen (США); опубл. 14.12.10.

39.Пат. N8006025 США. Architecture for an Output Buffered Switch with Input Groups / W. Olesinski, H. Eberle, N. Gura (США); опубл. 23.08.11.

40.Пат. N8352669 США. Buffered Crossbar Switch System / E. Wu, T. Zhou, S. Pollok (США); опубл. 08.01.13.

41.Пат. N8379658 США. Deferred Queuing in a Buffered Switch / S.G. Schmidt, A.G. Tornetta, H.V. Paul, H.J. Gonzalez (США); опубл. 19.02.13.

42.Пат. N8531943 США. Mesh Network / A. Olofsson (США); опубл.

10.09.13.

43.Пат. N8656141 США. Architecture and Programming in a Parallel Processing Environment with Switch-Interconnected Processors / A. Agarwal (США); опубл.

18.02.14.

44.Пат. N8737414 США. Scheduling, Including Distributed Scheduling, for a Buffered Crossbar Switch / S. Ye, Y. Shen, S.S. Panwar (США); опубл. 27.05.14.

45. Пат. N9275002 США. Tile-Based Processor Architecture Model for High-Efficiency Embedded Homogeneous Multicore Platforms / P. Manet, B. Rousseau (Бельгия); опубл. 01.03.16.

46.Пат. N10218625 США. Method and Apparatus for Alleviating Congestion at a Switch, Such as a Shallow Buffered Switch / H.J. Chao, K.-Y. Chen, Y. Xu (США); опубл. 26.02.19.

47.Пат. заявка N2010/0281236 США. Apparatus and Method for Transferring Data within a Vector Processor / S.S. Rakib, M. Ahmed, M. Schaub (США); опубл. 04.11.10.

48. Пат. заявка N2014/0006714 США. Scalable Coherence for Multi-Core Processors / N. Cherukuri, M. Azimi (США); опубл. 02.01.14.

49. Подлазов B.C. Обобщенные кросскольца - мультикольца с уменьшенной степенью узла // Автоматика и телемеханика. 2007. № 1. С. 175-186.

50.Подлазов В.С. Расширенное мультикольцо с диаметром 2 // Проблемы управления. 2015. № 4. С. 35-40.

51.Подлазов В.С., Соколов В.В. Однокаскадные коммутаторы большой размерности для многопроцессорных и многомашинных вычислительных систем // Проблемы управления. 2006. № 6. С. 19-24.

52. Свидетельство о регистрации программы для ЭВМ №2006610308. Библиотека классов для имитационного моделирования коммуникационных сетей / Э.И.Ватутин, И.В.Зотов (РФ). - М.: РосПатент; заявлено 22.10.05; дата регистрации 16.01.06.

53. Свидетельство о регистрации программы для ЭВМ №2007611310. Визуальная среда имитационного моделирования VisualQChart / И.В. Зотов и др. (РФ). - М.: РосПатент; заявлено 13.02.07; дата регистрации 27.03.07.

54.Советов Б.Я., Яковлев С.А. Моделирование систем: учеб. пособие. - М.: Высшая школа, 2019. - 343 с.

55.Сусин П.В., Беляев Ю.В., Зотов И.В. Коммутатор с двойными кольцевыми распределенными выходными очередями / Системы управления и информационными технологии / Межвузовский сборник научных трудов. Выпуск 9. - Воронеж: Центрально-Черноземное книжное издательство, 2002. - С.70-75.

56.Сусин П.В., Зотов И.В., Титов В.С. Матричная коммутационная сеть для организации взаимодействия параллельной системы логического управления с коллективом объектов / Материалы 4-й Международной научно-технической конференции «Новые информационные технологии и системы», Пенза, ПГУ, 2000. - С. 94-95.

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

800 с.

58. Хорошевский В.Г. Архитектура вычислительных систем: Учеб. пособие. 2-e изд., перераб. и доп. M.: Изд-во МГТУ им. H3. Баумана, 2008. - 520 c.

59.B. Agrawal. Generalized Hypercube and Hyperbus Structures for a Computer Network // IEEE Trans. Comput., Vol. C-33, no. 4, pp. 323-333. 1984.

60. Y. Ajima, S. Sumimoto, T. Shimizu. Tofu: A 6D Mesh/Torus Interconnect for Exascale Computers // Computer, Vol. 42, pp. 36-40, 2009.

61.Al-Azzeh J.S., Mohammed A.G., Zotov I.V. A parallel pipelined packet switch architecture for mesh-connected multiprocessors with independently routed flits // Jordanian Journal of Computers and Information Technology. Vol. 05. No. 02. pp. 146-162. Aug. 2019.

62.T. Anderson, S.S. Owicki, J.B. Saxe, C.P. Thacker. High-Speed Switch Scheduling for Local-Area Networks // ACM Trans. Comput. Syst., Vol. 11, no. 4, pp. 319-352, 1993.

63. L. Benini, G. De Micheli G. Networks on chips: a paradigm // IEEE Transactions on Computers, Vol. 35, no. 1, pp. 70-78, 2002.

64.T. Bjerregaard, S. Mahadevan. A survey of research and practices of network-on-chip // ACM Computing Surveys, Vol. 38, no 1, pp. 1-51, 2006.

65. J. M. Camara, M. Moreto [et al]. Twisted Torus Topologies for Enhanced Interconnection Networks // IEEE Trans. Parallel Distrib. Syst., Vol. 21, no. 12, pp. 17651778, 2010.

66.C.-S. Chang, D.-S. Lee, C.-Y. Yue. Providing Guaranteed Rate Services in the Load Balanced Birkhoff-Von Neumann Switches // IEEE/ACM Trans. Networking, Vol. 14, no. 3, pp. 644-656, 2006.

67.D. Chen [et al.] Looking under the hood of the IBM Blue Gene/Q network / in Proc. of the International Conference on High Performance Computing, Networking, Storage and Analysis, ser. SC '12. Los Alamitos, CA, USA: IEEE Computer Society Press, 2012, pp. 69:1-69:12.

68.D. Chen [et al.] The IBM Blue Gene/Q interconnection network and message unit / in Proc. of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, ser. SC '11. New York, NY, USA: ACM, 2011, pp. 26:1-26:10.

69.D.X. Chen, J.W. Mark. SCOQ: A Fast Packet Switch with Shared Concentration and Output Queueing // IEEE/ACM Trans. Networking, Vol. 1, no. 1, pp. 142-151. 1993.

70.G. Chen, M.A. Anders [et al]. A 340 mV-to-0.9 V 20.2 Tb/s Source-Synchronous Hybrid Packet/Circuit-Switched 16x16 Network-On-Chip in 22 nm Tri-Gate CMOS // IEEE J. Solid-St. Circ., Vol. 50, no. 1, pp. 59-67, 2015.

71.M. Chen, N.D. Georganas, O.W.W. Yang. A Fast Algorithm for MultiChannel/Port Traffic Assignment / Proc. IEEE Supercom/ICC '94, 1-5 May 1994, pp. 96-100.

72.C.-S. Chang, D.-S. Lee, Y.-S. Jou. Load Balanced Birkhoff-Von Neumann Switches, part I: One-stage buffering // Comput. Commun., Vol. 25, no. 6, pp. 611-622, 2002.

73. J. Chao. Saturn: A Terabit Packet Switch Using Dual Round Robin // IEEE Commun. Mag., Vol. 38, no. 12, pp. 78-84, Dec. 2000.

74. Y. Chen. Cell Switched Network-On-Chip-Candidate for Billion-Transistor System-On-Chips / 2006 IEEE Int'l SOC Conf., 2006. pp. 57-60.

75.S.-T. Chuang, A. Goel, N. McKeown, B. Prabhakar. Matching Output Queue-ing with a Combined Input/Output-Queued Switch // IEEE J. Sel. Areas Commun., Vol. 17, no. 6, pp. 1030-1039, 1999.

76.J.P. Coudreuse, M. Servel. Prelude: An Asynchronous Time-Division Switched Network / Proc. IEEE Int'l Conf. Commun. '87, 1987, vol.2. pp. 769-773.

77.L. Deng, W.S. Wong [et al]. Delay-Constrained Input-Queued Switch // IEEE J. Selected Areas Commun., Vol. 36, no. 11, pp. 2464-2474, 2018.

78.Z. Dong, R. Rojas-Cessa, E. Oki. Buffered Clos-Network Packet Switch with Per-Output Flow Queues // Electronics Letters, Vol. 47, no. 1, pp. 32-34, 2011.

79.S. Durkovic, Z. Cica. Birkhoff-Von Neumann Switch Based on Greedy Scheduling // IEEE Comput. Archit. Letters, Vol. 17, no. 1, pp. 13-16, 2018.

80.N. Endo, T. Kozaki, T. Ohuchi, H. Kuwahara, S. Gohara. Shared Buffer Memory Switch for an ATM Exchange // IEEE Trans. Commun., Vol. 41, no. 1, pp. 237-245, Jan. 1993.

81.M. FallahRad, A. Patooghy, H. Ziaeeziabari, E. Taheri. CirKet: A Performance Efficient Hybrid Switching Mechanism for NoC Architectures / 2016 Euromicro Conference on Digital System Design (DSD), 31 Aug.-2 Sept. 2016, pp. 123-130.

82. C. Fallin, X. Yu, G. Nazario, O. Mutlu. A High-Performance Hierarchical Ring On-Chip Interconnect with Low-Cost Routers / SAFARI Technical Report No. 2011-007 (September 6, 2011). 21 p.

83.M.H. Foroozannejad, M. Hashemi [et al]. Time-Scalable Mapping for Circuit-Switched GALS Chip Multiprocessor Platforms // IEEE Trans. Computer-Aided Design of Integr. Circ. and Syst., Vol. 33, no. 5, pp. 752-762, 2014.

84. Y. Ganjali, A. Keshavarzian, D. Shah. Cell Switching Versus Packet Switching in Input-Queued Switches // IEEE/ACM Trans. Networking. Vol. 13, no. 4, pp. 782789, 2005.

85. S. Goodman. Hypertree: A Multiprocessor Interconnection Topology // IEEE Trans. Comput., Vol. C-30, no. 12, pp. 923-933, 1981.

86.M. Han, Y. Kim. Unpredictable 16 Bits LFSR-Based True Random Number Generator / 2017 International SoC Design Conference (ISOCC), 5-8 Nov. 2017, pp. 284-285.

87.J. Howard, S. Dighe [et al]. A 48-Core IA-32 Processor in 45 nm CMOS Using On-Die Message-Passing and DVFS for Performance and Power Scaling // IEEE J. Solid-State Circ., Vol. 46, no. 1, pp. 173-183, Jan. 2011.

88.B. Hu, K.L. Yeung. Feedback-Based Scheduling for Load Balanced Two-Stage Switches // IEEE/ACM Trans. Networking, Vol. 18, no. 4, pp. 1077-1090, 2010.

89.B. Hu, K. L. Yeung, Q. Zhou, C. He. On Iterative Scheduling for Input-Queued Switches with a Speedup of 2-1/N // IEEE/ACM Trans. Networking, Vol. 24, no. 6, pp. 3565-3577, 2016.

90.A. Huang, S. Knauer. Starlite: A Wideband Digital Switch / Proc. GLOBECOM '84, 26-29 November 1984, pp. 121-125.

91.Intel Xeon W-3175X Processor Available: Powerhouse Built for the Most Demanding Professional Applications / News Byte, Jan. 30, 2019. URL: https://newsroom.intel.com/news/intel-xeon-w-3175x-processor-available/#gs.shox2m (дата обращения: 30.07.2019).

92.A.A. Jerraya, W. Wolf. Multiprocessor Systems-on-Chips. - San Francisco: Elsevier Inc., 2005. - 608 p.

93. K. Kang, K.-J. Park, L. Sha, Q. Wang. Design of a Crossbar VOQ Real-Time Switch with Clock-Driven Scheduling for a Guaranteed Delay Bound // Real-Time Systems, Vol. 49. no. 1, pp. 117-135, 2013.

94.M. Karol, M. Hluchyj, S. Morgan. Input Versus Output Queueing on a SpaceDivision Packet Switch // IEEE Trans. Commun., Vol. 35, no. 12, pp. 1347-1356, 1987.

95.M. Karol, M. Hluchyj. Queueing in high-performance packet switching // IEEE J. Select. Areas Commun., Vol. 6, no. 12, pp. 1587-1597, Dec. 1988.

96.H.-I. Lee, S.-W. Seo. Matching Output Queueing with A Multiple Input/Output-Queued Switch // IEEE/ACM Trans. Networking, Vol. 14, no. 1, pp. 121132, 2006.

97.J. Lee, C. Nicopoulos, S.J. Park, M. Swaminathan, J. Kim. Do we need wide flits in Networks-On-Chip? / 2013 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), 5-7 Aug. 2013, pp. 2-7.

98.C.E. Leiserson. Fat-Trees: Universal Networks for Hardware-Efficient Supercomputing // IEEE Trans. Comput., Vol. C-34, no. 10, pp. 892-901, 1985.

99. M. Lin, N. McKeown. The Throughput of a Buffered Crossbar Switch // IEEE Commun. Let., Vol. 9, no. 5, pp. 465-467, 2005.

100. K. Li, Y. Mu, K. Li, G. Min. Exchanged Crossed Cube: A Novel Interconnection Network for Parallel Computation // IEEE Trans. Parallel Distrib. Syst., Vol. 24, no. 11, pp. 2211-2219, 2013.

101. S. Liu, A. Jantsch, Z. Lu. Analysis and Evaluation of Circuit Switched NoC and Packet Switched NoC / 2013 Euromicro Conference on Digital System Design, 4-6 Sept. 2013, pp. 21-28.

102. P. Lotfi-Kamran, M. Modarressi, H. Sarbazi-Azad. An Efficient Hybrid-Switched Network-On-Chip for Chip Multiprocessors // IEEE Trans. Comput., Vol. 65, no. 5, pp. 1656-1662, 2016.

103. A. Mazloumi, M. Modarressi. A Hybrid Packet/Circuit-Switched Router to Accelerate Memory Access in NoC-Based Chip Multiprocessor / 2015 Design, Automation & Test in Europe Conference & Exhibition (DATE), 2015, pp. 908-911.

104. M. McKeown, Y. Fu [et al]. Piton: A Manycore Processor for Multitenant Clouds // IEEE Micro, Vol. 37, no. 2, pp. 70-80, Mar.-Apr. 2017.

105. N. McKeown, V. Anantharam, J. Walrand. Achieving 100% Throughput in an Input-Queued Switch / in Proc. 15th IEEE INFOCOM, San Francisco, CA, USA, Mar. 1996, pp. 296-302.

106. N. McKeown. The iSLIP Scheduling Algorithm for Input-Queued Switches // IEEE/ACM Trans. Networking, Vol. 7, no. 2, pp. 188-201, 1999.

107. S. Misra, S. Goswami. Network Routing: Fundamentals, Applications, and Emerging Technologies. - John Wiley & Sons, Inc., 2017. - 536 p.

108. S. Mneimneh. Matching from the First Iteration: An Iterative Switching Algorithm for an Input Queued Switch // IEEE/ACM Trans. Networking, Vol. 16, no. 1, pp. 206-217, Feb. 2008.

109. M. Nabeshima. Performance Evaluation of a Combined Input- and Crosspoint-Queued Switch // IEICE Trans. Commun., Vol. E83-B, pp. 737-741, 2000.

110. M.J. Neely, E. Modiano, Y.-S. Cheng. Logarithmic Delay for NxN Packet Switches Under the Crossbar Constraint // IEEE/ACM Trans. Networking, Vol. 15. no. 3, pp. 657-668, 2007.

111. L.M. Ni, P.K. McKinley. A Survey of Wormhole Routing Techniques in Direct Networks // IEEE Computer, Vol. 26, Issue 2, pp. 62-76, 1993.

112. A. Olofsson. Epiphany-V: A 1024 Processor 64-bit RISC System-on-Chip / Adapteva, Inc. URL: https://www.parallella.org/docs/e5_1024core_soc.pdf (дата обращения: 24.07.2019).

113. C. Panem, R.S. Gad, U.V. Rane, V.R. Gad. Evaluation of 3D & 4D Two Layer Mesh NoC for Fault Tolerance over Combinations of Vertical Channel / 2018 International Conference on Current Trends towards Converging Technologies (IC-CTCT), 1-3 March 2018, pp. 1-7.

114. R. Poovendran, S. Muniraj, A. Nandakumar. On Chip Implementation of Packet Switched Network [Text] // IOSR Journal of Electronics and Communication Engineering (IOSR-JECE), Vol. 9, Issue 2, pp. 38-42, 2014.

115. A. Psarras, J. Lee, P. Mattheakis, C. Nicopoulos, G. Dimitrakopoulos. A Low-Power Network-On-Chip Architecture for Tile-Based Chip Multi-Processors / 2016 International Great Lakes Symposium on VLSI (GLSVLSI), 18-20 May 2016, pp. 335-340.

116. Z. Qian, S.M. Abbas, C.-Y. Tsui. FSNoC: A Flit-Level Speedup Scheme for Network on-Chips Using Self-Reconfigurable Bidirectional Channels // IEEE Trans. Very Large Scale Integr. (VLSI) Syst., Vol. 23, no. 9, pp. 1854-1867, Sept. 2015.

117. Y. Shen, S.S. Panwar, H.J. Chao. SQUID: A Practical 100% Throughput Scheduler for Crosspoint Buffered Switches // IEEE/ACM Trans. Networking, Vol. 18, no. 4, pp. 1119-1131, 2010.

118. O.T. Sule, R. Rojas-Cessa, Z. Dong, C.-B. Lin. A Split-Central-Buffered Load-Balancing Clos-Network Switch with In-Order Forwarding // IEEE/ACM Trans. Networking, Vol. 27, no. 2, pp. 467-476, April 2019.

119. C. Sun, L. Chang, R.P. Dick. Three-dimensional multiprocessor system-on-chip thermal optimization / 5th IEEE/ACM international conference on hardware/software codesign and system synthesis. 30 September -3 October, 2007. pp. 117122.

120. Y. Tamir, G. Frazier. High Performance Multi-Queue Buffers for VLSI Communication Switches / Proc. 15th Annu. Symp. Comput. Archit., June 1988, pp. 343-354.

121. ThunderX2 ® CN99XX Product Brief / Cavium, Inc., 2018. URL: https://www.marvell.com/documents/cmvd78bk8mesogdusz6t/ (дата обращения: 30.07.2019).

122. Tile Processor Architecture Overview for the TILE-Gx Series / Tilera Corp., 2012. URL: http://www.mellanox.com/repository/solutions/tile-scm/docs/UG130-ArchOverview-TILE-Gx.pdf (дата обращения: 24.07.2019).

123. S.R. Vangal, J. Howard [et al]. An 80-Tile Sub-100-W TeraFLOPS Processor in 65-nm CMOS // IEEE J. Solid-State Circ., Vol. 43, no. 1, pp. 29-41, Jan. 2008.

124. Z. Wang. VLSI. - InTech, 2010. - 464 p.

125. D. Wentzlaff, P. Griffin [et al]. On-Chip Interconnection Architecture of the Tile Processor // IEEE Micro, Vol. 27, no. 5, pp. 15-31, Sept.-Oct. 2007.

126. J. Wu, T. Srikanthan. Fast Reconfiguring Mesh-Connected VLSI Arrays / Proc. Int'l Symp. Circuits and Systems, ISCAS '04, 23-26 May 2004. Vol.2. pp. 949952.

127. J. Wu, D. Xie, L. Tang, H. Wang. Cost Evaluation of Three-Dimensional Network-On-Chip / 2013 Fourth International Conference on Emerging Intelligent Data and Web Technologies, 9-11 Sept. 2013, pp. 133-136.

128. T. Ye, T.T. Lee, W. Hu. AWG-Based Non-Blocking Clos Networks // IEEE/ACM Trans. Networking, Vol. 23, no. 2, pp. 491-504, 2015.

129. Z. Yu, R. Xiao [et al]. A 16-Core Processor with Shared-Memory and Message-Passing Communications // IEEE Trans. Circ. Syst. I: Regular Papers, Vol. 61, no. 4, pp. 1081-1094, 2014.

130. Y. Zhang, J. Hu. A DFTR Router Architecture for 3D Network On Chip / 2010 3rd International Conference on Computer Science and Information Technology, 9-11 July 2010, pp. 337-342.

131. I.V. Zotov. Distributed Virtual Bit-Slice Synchronizer: A Scalable Hardware Barrier Mechanism for N-Dimensional Meshes // IEEE Trans. Comput., Vol. 59, no. 9, pp. 1187-1199, Sep. 2010.

132. D. Zydek, H. Selvaraj, L. Gewali. Synthesis of Processor Allocator for Torus-Based Chip Multiprocessors / 2010 Seventh Int'l Conf. on Information Technology: New Generations, 2010. pp. 13-18.

Приложение 1

Листинг программы вычисления значения Q1 по формуле (2.9)

(let ((x 0))

(defun fact(n) (cond

)

(defun C(n i) (cond

)

(defun A(n i) (cond

)

(defun X(f)

(cond

)

((< n 2) 1)

(t (* n (fact (- n 1))))

((< n i) 1)

(t (/ (fact n) (* (fact i) (fact (- n i)))))

((< n i) 1)

(t (/ (fact n) (fact (- n i))))

((<= f 0) 1) (t f)

(defun Q(l n p)

(let ((outer_sum 0) (inner_sum 0) (inner_term 0) (term 0) (i_max 0) (prod_C 0) (r_max 0)) (cond

((<= l 0) 1) ((eq l 1) (A p n)) ((eq l n) p) (t

(setq outer_sum 0) (setq i_max (\ n l)) (dotimes (i i_max outer_sum) (setq prod_C 1) (dotimes (j (add1 i) prod_C)

(setq prod_C (* prod_C (C (- n (* j l)) l)))

)

(setq term (* prod_C (C p (add1 i)))) (setq r_max (- l 1))

(if (> r_max (- n (* (add1 i) l))) (setq r_max (- n (* (add1 i) l))) nil) (setq inner_sum 0) (dotimes (r r_max inner_sum) (setq inner_sum (+ (Q (add1 r) (- n (* (add1 i) l)) (- p (add1 i))) inner_sum))

)

(setq term (* term (X inner_sum))) (setq outer_sum (+ outer_sum term))

)

))

)

)

(defun QQ(n l) (cond

((<= l 1) (fact n)) (t (Q l n n))

)

)

)

)

)

(defun P(n l)

(setq (setq (loop

)

)

(defun T1(n)

(setq tt1 0) (setq l 1) (loop

(if (> l n) (return (/ tt1 n)) nil) (setq tt1 (+ tt1 (* l (P n l)))) (setq l (add1 l))

)

)

(defun main(n_min n_max) (setq tt1 0) (loop

(if (> n_min n_max) (return tt1) nil) (setq tt1 (T1 n_min)) (printline tt1)

(setq n_min (add1 n_min))

)

) )

pow_n_n 1) i 1)

(if (> i n) (return (/ (QQ n l) pow_n_n)) nil) (setq pow_n_n (* pow_n_n n)) (setq i (add1 i))

Приложение 2

Листинг программы вычисления значения Q1- по формуле (2.22)

(let ((x 0))

(defun fact(n) (cond

)

(defun C(n i) (cond

)

(defun deg(n p) (cond

((< n 2) 1)

(t (* n (fact (- n 1))))

((< n i) 1)

(t (/ (fact n) (* (fact i) (fact (- n i)))))

((zerop p) 1)

(t (* n (deg n (- p 1))) )

)

(defun Q2(n_ l p n)

(let ((outer_sum 0) (inner_sum 0) (inner_term 0) (term 0) (i_max 0) (prod_C 0) (r_max 0) (i 0)) (cond

((< n_ (+ p (- l 1))) 0) ((> n_ (* p l)) 0) ((eq l 1) (deg n p)) (t

(setq outer_sum 0) (setq i 1)

(if (< i (\ n_ p)) (setq i (\ n_ p)) nil)

(setq i_max (\ n_ l))

(loop

(if (> i i_max) (return outer_sum) nil)

(if (< (- n_ (* i l)) (- p i)) (return outer_sum) nil)

(setq prod_C 1)

(dotimes (j i prod_C)

(setq prod_C (* prod_C (C n l)))

)

(setq term (* prod_C (C p i))) (setq r_max (- l 1))

(if (> r_max (- n_ (* i l))) (setq r_max (- n_ (* i l))) nil)

(setq inner_sum 0)

(dotimes (r r_max inner_sum)

(setq inner_sum (+ (Q2 (- n_ (* i l)) (add1 r) (- p i) n) inner_sum))

)

(setq term (* term inner_sum)) (setq outer_sum (+ outer_sum term)) (setq i (add1 i))

)

))

)

)

(defun sum_Q2(n_ n)

(let ((i 0) (s 0)) (setq s 0) (dotimes (i n s)

(setq s (+ s (Q2 n_ (add1 i) n n)))

))

)

;;(defun P(n_ n l s) (/ (Q2 n_ l n n) s)) (defun T2(n n_ s)

)

)

)

)

(setq tt2 0) (setq l 1) (loop

(if (> l n) (return (/ tt2 n_)) nil) (setq tt2 (+ tt2 (* l (/ (Q2 n_ l n n) s)))) (setq l (add1 l))

)

(defun main(n)

(let ((n_ 0) (tt2 0) (s 0))

(setq n_ n)

(loop

))

(if (> n_ (* 2 n)) (return 'done) nil)

(setq s (sum_Q2 n_ n))

(print n) (prints " ") (print n_) (prints " ")

(setq tt2 (T2 n n_ s))

(printline tt2)

(setq n_ (add1 n_))

Приложение 3

Листинг функции управления контроллеров МС_), используемых в Р-схеме на рис. 3.1

void OldestReqFirstCtrlFunc(

const CCustomMassGateController::AssocControllers_t & AssocControllers, CCustomMassGateController::GateStatesMap_t & GateStatesMap )

{

// insert gate control function code here /* retrieving the ids for the gates under control */ GATESTATESMAP_ITERATOR it = GateStatesMap.begin();

int id 1 = t -> f rst; ++it;

int id2 = t -> f rst; ++it;

int id3 = t -> f rst; ++it;

int id4 = t -> f rst; ++it;

int id5 = t -> f rst;

/* getting the req timestamps for the queues */ size_t timestamps[5];

TREAT_AS_QUEUE(AssocControllers[0]).GetMinReqInitTimeStamp(timestamps[0])

TREAT_AS_QUEUE(AssocControllers[1]).GetMinReqInitTimeStamp(timestamps[1])

TREAT_AS_QUEUE(AssocControllers[2]).GetMinReqInitTimeStamp(timestamps[2])

TREAT_AS_QUEUE(AssocControllers[3]).GetMinReqInitTimeStamp(timestamps[3])

TREAT_AS_QUEUE(AssocControllers[4]).GetMinReqInitTimeStamp(timestamps[4])

/* searching for the maximum timestamp */

size_t maxtimestamp = 0, max_id = 0;

for ( size_t i= 0; i < 5; ++i )

if ( timestamps[i] >= maxtimestamp ) { maxtimestamp = timestamps[i]; max_id = i;

}

/* setting a combination of control states */ GateStatesMap[id1] = 0; GateStatesMap[id2] = 0; GateStatesMap[id3] = 0; GateStatesMap[id4] = 0; GateStatesMap[id5] = 0; if ( max_id == 0 ) GateStatesMap[id1] = 1; else

if ( max_id == 1 ) GateStatesMap[id2] = 1; else

if ( max_id == 2 ) GateStatesMap[id3] = 1; else

if ( max_id == 3 ) GateStatesMap[id4] = 1; else

if ( max_id == 4 ) GateStatesMap[id5] = 1; return (void)0;

}

Приложение 4

Листинг программы PPP Switch Simulator, используемой для визуализации процесса моделирования КУ

// файл PPPSimul.cpp - точка входа в приложение

//---------------------------------------------------------------------------

#include <vcl.h> #pragma hdrstop

#include <tchar.h> //---------------------------------------------------------------------------

USEFORM("mainwnd.cpp", MainWindow);

USEFORM("szwnd.cpp", SizeWindow); //---------------------------------------------------------------------------

int WINAPI _tWinMain(HINSTANCE, HINSTANCE, LPTSTR, int) {

try

{

Application->Initialize(); Application->MainFormOnTaskBar = true;

Application->CreateForm(_classid(TMainWindow), &MainWindow);

Application->CreateForm(_classid(TSizeWindow), &SizeWindow);

Application->Run();

}

catch (Exception &exception) {

Application->ShowException(&exception);

}

catch (...)

{

try

{

throw Exception("");

}

catch (Exception &exception) {

Application->ShowException(&exception);

}

}

return 0;

}

//---------------------------------------------------------------------------

// файл MainWnd.h - определение класса основного окна

//---------------------------------------------------------------------------

#ifndef mainwndH

#define mainwndH //---------------------------------------------------------------------------

#include <System.Classes.hpp> #include <Vcl.Controls.hpp> #include <Vcl.StdCtrls.hpp> #include <Vcl.Forms.hpp> #include <Vcl.ExtCtrls.hpp> #include <Vcl.ComCtrls.hpp>

#include <Vcl.Grids.hpp> //---------------------------------------------------------------------------

#include <vector> #include <deque> #include <algorithm>

class TMainWindow : public TForm {

__published:

// controls TPanel *SimulPanel; TPanel *CtrlPanel; TStatusBar *StatusBar; TStringGrid *RegMatrGrid;

TStringGrid *InpQueGrid; TStringGrid *OutputGrid; TButton *StartButton; TButton *ResetButton; TRadioGroup *ModeGroup; TTimer *Timer;

TTrackBar *SimulSpeedTrackBar; TLabel *SimulSpeedLabel; TLabel *PctStrRateLabel; TTrackBar *PctStrRateTrackBar; TGroupBox *StatGroupBox; TMemo *StatMemo; TLabel *TimeLabel; TLabel *PhaseLabel; TLabel *TimeTitleLabel; TLabel *PhaseTitleLabel; TEdit *ThresholdEdit; TLabel *ThresholdLabel; TButton *SizeButton; TStringGrid *OutTitleGrid; TStringGrid *InpTitleGrid; TLabel *SizeLabel; TRadioGroup *MethodGroup; // event handlers

void_fastcall StartButtonClick(TObject *Sender);

void_fastcall ResetButtonClick(TObject *Sender);

void_fastcall PctStrRateTrackBarChange(TObject *Sender);

void_fastcall ModeGroupClick(TObject *Sender);

void_fastcall TimerTimer(TObject *Sender);

void_fastcall SimulSpeedTrackBarChange(TObject *Sender);

void_fastcall FormCreate(TObject *Sender);

void_fastcall SizeButtonClick(TObject *Sender);

void_fastcall RegMatrGridTopLeftChanged(TObject *Sender);

void_fastcall InpQueGridTopLeftChanged(TObject *Sender);

void_fastcall OutputGridTopLeftChanged(TObject *Sender);

void_fastcall ThresholdEditChange(TObject *Sender);

public:

typedef enum sm_t { sm_idle, sm_auto, sm_trace, sm_batch_size, sm_batch_rate } sm_tag; typedef enum stat_t { st_throughput, st_rm_time, st_full_time, st_rm_load, st_pct_col } stat_tag;

_fastcall TMainWindow(TComponent* Owner);

inline short GetCurSize() const { return_size; }

private:

// simulation-related data & functions

sm_t_simulation_mode;

short_size;

long_time;

long_tick;

long_time_threshold;

short __phase;

long_packets_issued;

long __packets_processed;

long long_sum_ticks_spent;

double_packet_stream_rate;

double_sum_RM_time;

double_throughput;

double_mean_relay_time;

double_mean_reg_matr_relay_time;

long long_sum_RM_load;

double_aver_RM_load;

double_sum_aver_packets_per_col ;

double_time_aver_packets_per_col;

short_round_robin_selector;

std::vector<int>_packets_in_queue;

std::vector<short>_routing_dir;

std::vector<bool>_lock_dir;

std::vector<int>_packets_processed_row;

std::vector<short>_max_i;

std::vector<short>_selected_packet_i;

std::vector< std::vector<long> >_time_in_matrix;

std::vector<long>_max_time_in_matrix;

std ::vector<double>_throughput_readings;

std ::vector<double>_mean_RM_time_readings;

std ::vector<double>_aver_RM_load_readings;

std ::vector<double>_mean_relay_time_readings;

std ::vector<double>_time_aver_pct_col_readings;

std::vector< std::deque<long> >_packet_issue_ticks;

std::vector< std::vector<long> >_packet_reg_matr_ticks;

bool __SimulationStep();

inline bool __RegMatrixEmpty() const;

int __PacketsInRegMatrixRow(short row) const;

int __PacketsInRegMatrixCol(short col) const;

int __PacketsInRegMatrix() const;

bool __RearrangeControls();

void __SaveStat(stat_t stat_kind = st_throughput);

};

//---------------------------------------------------------------------------

extern PACKAGE TMainWindow *MainWindow;

//---------------------------------------------------------------------------

#endif

// файл MainWnd.cpp - реализация класса основного окна

//---------------------------------------------------------------------------

#include <vcl.h> #include <windows.h> #pragma hdrstop

#include "mainwnd.h"

#include "szwnd.h"

//---------------------------------------------------------------------------

#pragma package(smart_init) #pragma resource "*.dfm"

TMainWindow *MainWindow;

//---------------------------------------------------------------------------