?
Разработка алгоритма маршрутизации в сетях на кристалле с топологией мультипликативный циркулянт
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.