A novel adaptive congestion-aware and load-balanced routing algorithm in networks-on-chip

Abstract

Congestion-aware routing algorithms attempt to have more diversity in routes to be chosen and avoid congested areas in networks-on-chip. In this paper, a novel fully adaptive congestion-aware routing algorithm called zigzag routing algorithm (ZRA) along with a new load-balanced method is proposed. ZRA presents a new way for transmitting congestion information, which allows a better view on congestion compared to other algorithms. Furthermore, the load-balanced method recognizes a forbidden area in the network according to betweenness centrality parameter. Fortifying ZRA with this novel load-balanced scheme yields more improvement in performance compared with the previous work. On average, we have accomplished 20.8% and 12.4% improvement in SPLASH-2 benchmark in contrast to DyAD and CATRA algorithms, respectively. It can be claimed that the proposed routing scheme does not consume more power than DyAD and CATRA. Moreover, a new parameter is suggested for comparing load-balanced algorithms, called the variance of crossbar activity.

Introduction

In recent years, network-on-chip (NoC) has been a suitable alternative to bus-based and peer-to-peer architectures for communicating among IPs in systems-on-chip (SoC). NoC allows the system to send data between multiple pairs of cores simultaneously. Additionally, in a system with a network-based design, there is no need for changing and redesigning the entire infrastructure when a new core is added. This advantage, called scalability, is very important in computer systems [1]. According to the International Technology Roadmap for Semiconductors (ITRS) report in 2011, multi-core systems-on-chip (McSoCs) might accumulate up to hundreds of connected cores on a chip using NoC communication infrastructure [2]. On the other hand, with applications getting more complex, the number of the packets moving through the network increases [3], the network congestion be remarkably increased. Due to numerous problems caused by congestion in the network, it is vital to set policies to control it on NoCs.

In a network, congestion occurs when the demand on a network component such as node or link exceeds its capacity. Packets whose destination is a congested node are forced to remain in their position and hold onto the resources they have occupied. Hence, all packets in that region face shortage in resources and get congested [4]. In other words, congestion in this case spreads in the network like a tree, which called congestion tree. Generally, congestion in the NoC increases the time for the packets to reach the destination. Thus, the network delay will increase and network performance will decrease, which increases the power consumption [5]. Average latency increase, performance decrease and increased power consumption is not acceptable in NoCs. There are various ways in which congestion can be controlled in NoC including the use of congestion-aware adaptive routing algorithms [6], dynamic change of packet injection rate [7], improvement in router architecture [8], adding more buffers to the routers [1], altering buffer structure [9], allocating dynamic memory to buffers [10], [11], using mathematical modeling [12], etc. Some of these methods such as those working on the size of buffer incur a great hardware overhead. Moreover, some methods such as changing packet injection rate are only feasible under certain circumstances. One of the best methods with the least overhead is using a congestion-aware routing algorithm. In this paper, a novel congestion-aware algorithm is proposed to control the congestion problem in NoC.

Routing algorithms are divided into two classes: deterministic and adaptive. The difference between these algorithm classes is in the path they choose among all the possible routes from source node to destination node. In deterministic routing algorithms, although there are many routes to be taken, the route is not selected according to the network states. Even though these algorithms have simple logical circuits, they perform very poorly in coming across a situation of load imbalance. Oblivious algorithms are one of the types of deterministic routing. In these algorithms, there is a variety of choices in routes, and the new packet might not be sent over the same route as the previous packet, while the decision they make is not based on network state. In other words, as inferred from the name of these algorithms, they are oblivious to the state of the network regarding congestion or fault, and randomly choose one of the possible routes from source to destination. Another class of routing algorithms includes adaptive algorithms. These algorithms adapt themselves to the state of the network. For instance, when the network is congested, only less congested routes are chosen by routing algorithms for delivering packets to the destination nodes. Therefore, they have better performance in congestion states, despite having more complex logical circuits than deterministic algorithms [13]. From another perspective, routing algorithms are divided into two groups: minimal and non-minimal. Minimal algorithms choose a route from a set of shortest paths between source and destination. In non-minimal algorithms, any route can be chosen from the possible routes regardless of its length. Non-minimal algorithms have better load distribution compared to minimal algorithms. Not only they benefit from more variety in selecting packet routes, but they also suffer from livelock and circuit complexity issues. Thus, they might choose a path that could get the packet even farther from destination [14].

Effective adaptive routing algorithms can have a crucial role in solving the congestion issue. These algorithms can prevent packets from crossing congested regions by adaptively changing their paths so that these packets reach their destination with less latency and congested nodes exit congestion state faster. In addition, network load will be efficiently distributed in the network. Proper balance in the network can decrease the power consumption as well [15].

The organization of the paper is structured as follows. The related literature is reviewed in Section 2. In Section 3, a novel congestion-aware adaptive routing algorithm as well as a new load distribution scheme is presented. In Section 4, performance evaluation results are explained. Finally, in Section 5, the concluding remarks are drawn.