Development of Routing Algorithms in Networks on Chip with a Multiplicative Circulant Topology

Shchegoleva M.A., Romanov A. (National Research University Higher School of Economics)
Abstract - Nowadays, construction of multi-core processors is becoming one of the most popular areas of investigation in computer science field; transition to multi-core processors allows overcoming the performance decrease, observed in complex single-core system design. Increase in core number, however, raise the issue of choosing the best topology, because classic topologies (mesh, hypercube, torus) fail to meet the requirements of modern networks with numerous cores. In this paper, multiplicative circulants, as a possible topology for networks-on-chip, are considered. Comparison of main characteristics of chosen type of circulants with characteristics of widely used mesh topology, makes it possible to consider multiplicative circulants to be a better topology for multi-core systems and to suggest the packet design for simple static routing technique based on classic breadth first search (BFS) algorithm. However, universal solutions have never been the best for a certain class of objects, so a specialized routing algorithm, taking into account the peculiarities of multiplicative circulants, was elaborated. By utilizing only mathematic operations, the developed algorithm managed to avoid exponential dependency on number of nodes inherent to BFS algorithm and demonstrated good performance even for networks with hundreds of nodes. Moreover, the presented algorithm required less service data in the packet, because only the target node number was needed for proper work.

Keywords - network on chip, network on-chip topology, multiplicative circulant, routing algorithm.

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

Щеголева М.А., Романов А. (Национальный исследовательский университет «Высшая школа экономики», г. Москва)
Аннотация - Разработка многоядерных процессорных систем является востребованным направлением науки и техники. Появление процессоров с десятками и сотнями ядер ставит перед разработчиками вопрос о выборе оптимальной топологии, способной обеспечить эффективную маршрутизацию в сети с большим количеством узлов. В настоящей работе рассматривается возможность применения мультипликативных циркулянтов в качестве топологии для сетей на кристалле. Предлагается способ организации адресного поля пакета при статической маршрутизации на основе стандартного алгоритма поиска кратчайшего пути в сети с циркулянтной топологией. Разработан специализированный алгоритм маршрутизации в сетях с топологией мультипликативный циркулянт, учитывающий особенности топологии и имеющий высокие показатели масштабируемости.

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