In this paper, a review of various high-level models of networks-on-chip, their performance capabilities, and characteristics was carried out. As a result, the BookSim simulator was chosen. Application of circulant topologies for implementation of communication subsystems in networks-onchip (NoCs) as alternatives to other regular topology was proved. The process of modifying the BookSim simulator described allowed high-level modeling of NoCs with any topologies (including two-dimensional circulants), as well as testing new routing algorithms in such networks.
Nowadays, the use of multiprocessor systems is becoming an increasingly common solution. The growing complexity of
tasks requires that computer systems continually improve performance. In multicore systems with a small amount of cores
(2-10 cores), communication between computing cores and other components of a chip occurs successfully with the help of
the common bus. The bus is an infrastructure for data transmission between the core blocks (for example, AMBA [
Acknowledged and widespread approach is usage of core communication options by creation of NoC [
Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
A topical area for research of NoCs is the search for optimal topologies and routing algorithms for them. Classical
topologies (mesh [
An approach, that uses low-level modeling in the context of developing networks on a chip with circulant topologies,
was applied in [
The first table routing algorithm allows routing based on a previously calculated route table between each network node. The table stores the port numbers to which the packet is to be sent so that it reaches the correct node. The table is stored in a distributed form so that each router stores only one step of the complete route. For the algorithm to work, it is necessary for the head fleet of the packet to store the destination node number. The router here is a digital apparatus which from the head fleet, takes the node number of the destination and uses it as an index to refer to a line of the table stored in the router from which it takes the port’s number to send the packet.
The second and third algorithms do not store routing data, but iteratively calculate the number of the next node in the route. The second algorithm calculates the router and the port connected to it as follows: according to certain rules, the direction of transmission of the packet is hourly or counterclockwise after which a transition takes place along a large or small generatrix of the circulant with a mandatory approach to the destination node. The third algorithm is a development of the second algorithm in which, for the sake of simplification, optimal paths between nodes are not always chosen. By introducing additional checks on the choice of the direction and the generatrix, as well as taking into account situations where the optimal route contains a cyclic network traversal, the calculation of the optimal routes in the network was achieved. The third algorithm is a development of the second algorithm in which, due to its simplicity, the optimal route between the nodes were not always calculated. Introducing additional checks on the choice of direction and the generatrix, and also considering that with a certain configuration of the topology, there may be cases when the optimal route contains a cyclical bypass of the network, the calculation of the optimal routes in the network was achieved.
Low-level modeling was performed in the Verilog language [
Simulators of general purpose networks – designed to simulate any network as a whole, but can be used for NoC
as well: Gem5, Graphite, Sniper, Hornet, Fusionsim, Esesc, Wattch, Hotspot, NS2, NS3, Omnet ++, Netsim,
Orion [
Simulators designed specifically for modeling NoC: BookSim, WormSim, Vnoc, Matrics, SICOSYS, Garnet,
Ocintsim, Noxim, Nostrum, Nirgam, Occn, Nocsim, Access Noxim, NoCTweak, Atlas, gpNoCsim, Xmulator,
Phoenixsim, SUNMAP, NOCMAP, ReliableNoC, MapoNoC [
In general, the structure of NoC simulators can be represented as follows (Figure 3): 1. Setting up the simulator (model initialization, setting limits on simulation time and warm-up time, selection of simulation mode); 2. Setting parameters of synthetic tests (size and structure of the network, traffic profile, location of hot spots of the network, etc.); 3. Selection of parameters for embedded tests (determination of the characteristic graph of the problem and the algorithm for projecting the graph of the problem onto the core); 4. Configuring traffic (number of streams, packet length, packet rate); 5. Configuring the router (type of routers, number and length of packet buffers); 6. Routing configuration (routing algorithm); 7. Selection of measured parameters (network bandwidth, energy consumption, packet transmission delays). Let’s consider a number of the most common NoC simulators.
BookSim [
Vnoc [
Noxim [
Nostrum [
Nirgam [
NoCTweak [
NOCMAP [
Thus, on the basis of the in-depth analysis of the considered NoC simulators (Table 1), we can conclude that 2D-mesh topology is the prevailing topology in most common high-level NoC models. At the same time, the topology is often the basis of the program code, all the basic model calculations and its structure of classes and interactions between them depend Simulator
Language
Among the NoC simulators considered, BookSim [
BookSim [
consumption Delays Energy consumption Bandwidth
capability Delays Use of links Delays Bandwidth capability Capacity Bandwidth capability Delays Energy consumption
No No Yes No No Yes
No
The simulator can be divided into 7 modules: a module describing topologies, a module describing routers, a module describing allocators, a module for arbitrating access to router resources, a module describing traffic, a module for analyzing power consumption. A module is a set of classes inherited from a general class. This is done to simplify modification of the simulator.
The topology description module contains a base class in which variables common for topologies, such as the number of
nodes, the size of the network, the number of channels, are then redefined when forming the topology. The module also
contains general functions that do not depend on the selected topology, for example, creating allocators and reading /
writing data to channels. It calls the topology class specified in the configuration file to calculate specific topology
parameters. Currently, developers support 10 topologies: mesh [
The module of description of routers contains a list of channels and other variables for the router operation, and functions for adding input and output channels. One can use 3 types of routers: input-queue router, event-driven router, and chaos router.
The module of description of the allocators contains a description of the methods of distributing the resources of routers among their customers, each of which can use one or several resources. Multiple type blockers are supported: iSLIP separable allocator, parallel iterative matching (pim), separable output-first allocator, lonely output allocator (loa), wavefront allocator, separable input-first allocator.
The arbitration description module contains algorithms for distributing access to router resources. The following arbitration algorithms are possible: round-robin, matrix, tree, priority.
The traffic description module controls how the packets will go to the network, how fast and which nodes will generate the traffic. It is possible to set uniform generation of traffic by all nodes, according to a specific algorithm, as well as random generation.
The power consumption analysis module allows analyzing energy consumption of the network being modeled depending on the specified parameters of the chip production processes.
All these modules are united by the main module to the input of which a configuration file with a description of the simulated network arrives. It directly creates and configures the network, starts the simulation, selects a routing algorithm, and collects statistics.
Configuring the simulator is made through the configuration file. This definitely structured file contains the definition of
all the necessary parameters for the simulator operation [
BookSim conducts a simulation in three phases: warming up, measurement, analysis. The duration of these phases depends on the parameters set in the configuration file. Delay and throughput are displayed after each phase, and at the end, the average for these values is calculated. After the warm-up phase is completed, a message is displayed, and the simulator moves to the next measurement phase, reconfiguring all the parameters. The statistical data of the simulated topology is displayed before each next phase of the simulation. Upon completion of the simulation, BookSim generates an output file in which all simulation results are recorded.
In order to use BookSim to model circulant topologies, it was necessary to make certain changes to its source code. To begin with, a description of the topology was created. All structures, in which topologies supported by the simulator are described, are built on the same principle: there is a class in which the main characteristics of the topology are stored. Also, the topology class has a set of functions that, when called, will calculate the size of the network, calculate the total number of physical channels, and configure individual network routers. The class also contains functions for building a network and creating links between routers.
All classes describing topologies are descendants of the general Network class which contains general information about the network (number of nodes, number of channels, number of network cycles, etc.). It is used to configure parameters of the virtual channels and the mechanism for confirming transfers using credits, as well as selecting the necessary class for implementing the topology described in the configuration file and registering the routing algorithm for the topology. At this layer of the model, there is a choice of algorithms for distributing traffic over the virtual channels of routers. An instance of the Network class controls reading and writing of flits to ports defined by the routing algorithm and controls reading and writing of credits.
Thus, the Network class is an intermediary between the topology classes and the rest of the simulator logic. This is an important advantage of the BookSim simulator, since, unlike many other simulators, the interface for connecting new NoC topologies is implemented.
Thus, the first thing done was the creation of a new class called Circulant which stores the number of network nodes and the list of generators. Also, in the developed class, functions for calculating the size of the circulant network and number of channels calculating the numbers of the nearest nodes (with the distance to the selected node equal to one hop) were implemented. Next, changes were made to Network class by adding connection condition of the developed new topology class, when it is mentioned in the configuration file.
BookSim supports modeling of various topologies among which there are many variations of mesh and torus topologies.
For most of these variations, one can use the same routing algorithms. Therefore, instead of setting up a routing algorithm
in each class, the developers created a separate Routerfunc class which collects all the routing algorithms for all possible
topology classes as functions. To implement the selection of the required routing algorithm, gRoutingFunctionMap,
container is used; it stores references to the routing algorithms. In the configuration file, in the part of the topology setting,
the name of selected algorithm is specified, and then when setting up the routers, it is selected. In this file, the algorithms,
given in [
Since the definition of settings of the simulator occurs through the configuration file, the data is read from it in a certain way and the corresponding variables are initialized. In order for the simulator to correctly read the configuration file to simulate the circulant topology, changes were made to the class that implements processing of the read data from the configuration file booksim_config. These changes might not be made; however, in this case, the possibility of describing the generatrices in the form of a string, separated by a comma, is lost, which complicates the use of the simulator to simulate circulant topologies with a large number of generatrices. At the same time, the classes, in which the configuration file parser was implemented, did not need to be changed, since it simply read lines and distributes data from them into several associative arrays. The read string with the generatrices is stored in a string variable and is further divided into an array of numbers. An example of a configuration file for circulant network modeling is presented in Figure 5.
To test the operation of the modified simulator, modeling and comparison of networks with mesh, torus, and circulant topologies was performed. The optimal shapes of the mesh, torus, and circulant topologies were chosen for testing in order to eliminate the influence of the geometric shape of the topologies on the result. For the circulant topology, restrictions were imposed on the choice of the number of nodes in the network. They are calculated by the formula ܰ ൌ ݊ ଶ , where ܰ – number of nodes in the network, ݊ – natural number. Thus, mesh(10x10), torus(10x10), and circulant ܥͳͲሺǢ ͳǡ ͳͺሻ networks were simulated. The topology ܥͳͲሺǢ ͳǡ ͳͺሻ , obtained as a result of synthesis using the generatrix proposed in [42], is optimal and characterized by the best values of diameter and average distance between nodes for circulants with 100 nodes [43]. The comparison was carried out on the average rate of transmission and reception of fleets when changing the rate of generation of packets. The simulation was carried out with the following model parameters: Packet length – 10 flits; Warming up period – 3; Sampling period – 1000; Number of virtual channels – 8; Traffic type – uniform;
Rate of traffic generation – from 0.05 to 1.0.
The simulation results are shown in Figures 6 and 7.
Figure 7 – Dependence of average packet latency on injection rate
The results obtained demonstrate that with the selected topology configuration, the throughput of mesh(10x10) topology
stabilized at 0.3; torus(10x10) – at 0.35; circulant ܥ ሺ ͳͲǢ ͳǡ ͳͺ ሻ – at 0.55. Also, the saturation of NoC with the circulant
topology occurs later than in mesh and torus topologies. These results confirm the previously obtained results [
Thus, a review of high-level NoC simulators was conducted. It showed that most high-level simulators support the implementation of NoC modeling only with mesh and torus topologies. Meanwhile, it is the BookSim simulator which is capable to carry out topology simulations not only of mesh and torus, but also their modifications, as well as other topologies. It was the key feature for choosing a simulator for further modification. The facts of the BookSim (it is an open source code, it is written in C++, and it can simulate various characteristics of networks) confirmed the correctness of the choice of this simulator. The changes, proposed to the structure of simulator, ensured development of a class describing the circulant topology; routing algorithms, allowed simulation of NoC with two-dimensional circulant topologies and a comparative analysis of the results of their modeling with other topologies, were also added. To test the operation of the modified simulator, networks with mesh, torus and two-dimensional circulant networks were simulated, and data were obtained on the delays of receiving and transmitting fleets in the network. This makes it possible to conduct high-precision modeling of NoCs with high-level circulant topologies.
The research leading to these results has received funding from the Basic Research Program at the National Research University Higher School of Economics.