• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Modeling of networks on a chip with a communication subsystem based on circulant topologies

2019
Department: Laboratory of Computer-aided Design Systems
The project has been carried out as part of the HSE Program of Fundamental Studies.

Цель работы

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

Используемые методы

Хотя идея применения циркулянтных топологий в качестве основы СтнК в работах по данной проблематике не рассматривалась, проведенный нами предварительный анализ характеристик известных циркулянтных топологий позволяет говорить о том, что они имеют лучшие характеристики, чем наиболее распространенные регулярные топологии mesh и torus. В работах Э.А. Монаховой отмечается сложность задачи синтеза циркулянтов для большого количества узлов; она была частично решена на предыдущем этапе исследования путем разработки программных средств для синтеза циркулянтных топологий, что позволило получить необходимые топологии с количеством узлов, достаточным для реализации СтнК. Также были выделены некоторые наиболее перспективные классы циркулянтов для применения в СтнК и разработан ряд алгоритмов маршрутизации в них. В рамках работы были улучшены программные средства для синтеза циркулянтных топологий, разработаны новые алгоритмы маршрутизации в СтнК на основе циркулянтных топологий, а также созданы и адаптированы существующие модели различного уровня абстракции для моделирования и синтеза СтнК на основе циркулянтных топологий, для чего были использованы современные методы математического анализа, методы распараллеливания вычислений и др.

Эмпирическая база исследования

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

В 2018 году были разработаны средства для синтеза различных циркулянтных топологий, синтезировано несколько классов циркулянтов, предложены алгоритмы маршрутизации в СтнК на основе этих топологий и выполнены первые шаги по разработке HDL-реализаций СтнК (на основе собственного процессорного ядра schoolMIPS и маршрутизатора NoCSimp) для оценки аппаратурных затрат на реализацию таких топологий.

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

Результаты работы

В рамках научного проекта были рассмотрены циркулянтные топологии и алгоритмы маршрутизации в них как основы для построения подсистем связи СтнК.

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

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

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

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

Полностью подготовлена инфраструктура для разработки гибридной модели, которая бы объединяла в себе несколько моделей разного уровня абстракции. Это позволит осуществлять весь цикл проектирования СтнК: начиная с первичного быстрого оценочного моделирования СтнК с помощью высокоуровневых моделей, и заканчивая моделированием на уровне RTL и прототипированием на FPGA.

Степень внедрения, рекомендации по внедрению или итоги внедрения результатов НИР

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

В рамках НИР подготовлено и получено 3 свидетельства на Программы для ЭВМ.

Результаты научного проекта могут являться основой для разработки гибридной модели, которая бы объединяла в себе несколько моделей разного уровня абстракции. Гибридная модель обеспечит весь цикл реализации топологического подхода к проектированию СтнК: от первичного быстрого оценочного моделирования СтнК с целью подбора ее характеристик до моделирования на уровне RTL и прототипирования на FPGA.

Publications:


Romanov A.Yu., Sidorenko M.V., Lezhnev E.V. Routing in Networks-on-Chip with Circulant Topology with Three Generatrices of Type C(N;S1,S2,S3), in: 2019 International Russian Automation Conference (RusAutoCon). IEEE, 2019. P. 1-6. doi
Romanov A., Lezhnev E., Amerikanov A. Modification of the BookSim simulator for modeling networks-on-chip based on two dimensional circulant topologies, in: Proceedings of the 6th International Conference Actual Problems of System and Software Engineering (APSSE) Moscow, Russia, 12-14 November, 2019. / Ed. by A. R. Cavalli, B. Pozin, A. Petrenko. Vol. 2514. CEUR-WS, 2019. Ch. 107. P. 182-192.