Communications of the ACM
New Areas for Application of Self-Organizing Routing
Very often, ideas and technologies that have proven themselves in one area can be successfully used in a completely new area. Such creative borrowing facilitates, cheapens, and accelerates developing a new technology and also makes it possible to predict its prospects. Before starting to create a technology from scratch, it is necessary to study close and distant analogies in order to take advantage of existing developments. In our opinion, there are many similar analogies, but not all of them are actively used. For example, the DECT standard could be used as a date transmission network for various IoT applications. However, in this article we would like to discuss the search for analogs for routing in networks-on-chip (NoCs).
The main way to increase the performance of modern processors has become the creation of multiprocessor chips. With that, the number of processors on a single chip is growing rapidly and can already reach tens of thousands of computational cores. So, the WSE2 chip from Cerebras, made according to a 7 nanometer process technology, consists of 850,000 computational cores [1].
To organize the productive work of such systems, it is necessary to establish an efficient distribution of computational processes between computational cores. Implementation of appropriate communications requires the development of the theory of NoCs and provides its practical application [2].
In the classical theory of computer networks, lots of routing algorithms, methods, and protocols have been developed, and they could become the basis for NoCs. From our point of view, one of the areas close to NoCs is the routing algorithms and methods that were developed for wireless self-organizing networks [3].
Further, we will try to draw analogies and concretize the main provisions of routing in Nocs. So far, our group consists of a team of a small laboratory - two leading researchers and several graduate and undergraduate students. One of us (Andrei Sukhov) is an expert in self-organizing wireless routing. The second team member (Aleksandr Romanov) is developing NoCs and designing embedded systems based on FPGA.
Since the structure of connections between the cores in a NoC is fixed, the network (although it may consist of hundreds or thousands of nodes) remains static. The invariability of NoC topology determines the advisability of using virtual coordinates which allow assigning a unique address to each network node. Moreover, such an assignment can be carried out in advance, at the stage of chip production. Therefore, it is necessary to start with the study of methods for constructing virtual coordinate systems.
First of all, it is necessary to conduct research and determine the rules for specifying a virtual coordinate system by analogy with wireless self-organizing networks. It is planned to use the neighborhood method to mark coordinates, and the neighborhood number can be used as a coordinate. This approach avoids the weakness of virtual coordinate routing methods where positive and negative directions are specified. In our proposed routing method, only positive values will be used as coordinates.
The study of the dependence of the virtual coordinate systems on the topology of the arrangement of cores on the chip will be carried out. In addition to mesh topologies, it is planned to study a new promising class of NoC topologies – circulant graphs whose using is described in [4].
In our opinion, the greedy advance method can be used to build a route between computational cores. In the course of the research, various metrics which describe the distance between any two cores on a chip will be selected and the rules by which the next node of the route is determined will be formulated. These rules will allow selecting the next node from neighbors of the current node. In this case, the new node should be located closest to the final node of the route. These rules can determine the next node even if nodes fail due to their overload in the network, when one or another part of the network is unavailable. An illustration of bypassing a temporarily inoperative node is shown in Fig. 1.
Fig. 1 Routing procedure with congestions
Special attention will be paid to the development of the mathematical aspects of self-organizing routing methods. One of these aspects is the choice of the centers of the hierarchies which will serve as reference points of virtual coordinates, as well as the determination of their number for the unambiguous assignment of coordinates.
The tasks set are quite complex, and a sufficiently large team is required to solve them. Therefore, one of the goals of this post is to find like-minded people. We are ready to consider various options for cooperation and financing. One of the opportunities for cooperation is participation in the competition for the creation of international laboratories at our university: https://www.hse.ru/en/contest_labs//. We ask potential partners to make an entry in the comments to the blog or write by e-mail, and we will try to contact you.
References
[1] Cerebras' New Monster AI Chip Adds 1.4. (April 20, 2021). Trillion Transistors IEEE Spectrum advertisement. https://spectrum.ieee.org/tech-talk/semiconductors/processors/cerebras-giant-ai-chip-now-has-a-trillions-more-transistors.
[2] Bjerregaard, T., & Mahadevan, S. (2006). A survey of research and practices of network-on-chip. ACM Computing Surveys (CSUR), 38(1), 1-es.
[3] Abolhasan, M., Wysocki, T., & Dutkiewicz, E. (2004). A review of routing protocols for mobile ad hoc networks. Ad hoc networks, 2(1), 1-22.
[4] Romanov, A. (2019). Development of routing algorithms in networks-on-chip based on ring circulant topologies. Heliyon, 5(4), e01516.
Andrei Sukhov ([email protected]) is a Professor and Head of the Network Security Research and Study Group of HSE University, Moscow, Russia. In 2020, he was elected as a senior member of the ACM. Aleksandr Romanov ([email protected]) is an Associate Professor and Head of CAD Laboratory of HSE University, Moscow, Russia.
No entries found