Ant-Colony Optimization-based Adaptive Routing Algorithms and Architectures in Network-on-Chips Systems
Date Issued
2014
Date
2014
Author(s)
Hsin, Hsien-Kai
Abstract
As semiconductor technology continues to advance, increasing complexity and interconnection delay are becoming limiting factors in system-on-chip (SoC) designs. To increase the efficiency of interconnections and meet data transfer requirements, network-on-chip (NoC) systems have proven to be a flexible, scalable, and reusable solution for chip multiprocessor (CMP) systems. To achieve a high system throughput rate, the packet-switched NoC multiplexes packets on channels and shares network resources among these packet flows.
However, the packet congestion problem in channels results in unpredictable delays for each packet flow. As the system size increases, the network traffic load tends to become unbalanced with various applications. The congestion in channels increases queuing delays in the routing path, which not only causes network congestion but also dissipates additional energy. Congestion problem cause severely degradation on the overall system performance, especially in real-time applications with strict latency requirements. Therefore, to overcome the problem of traffic congestion, packet routing is a critical design challenge for high-performance NoC.
An effective adaptive routing algorithm can help minimize network congestion through load balancing. However, conventional adaptive routing schemes only use current channel-based information to detect the congestion status. Because of the lack of historical network information, channel-based information has difficulty showing the real congestion status under time-variant traffic patterns.
To predict temporal network congestion, we apply a bio-inspired approach, Ant Colony Optimization (ACO), to identify the near-future non-congested path to a desired target according to historical network information. Distributed artificial ant agents migrate from node to node and emulate laying of pheromone by updating the corresponding entries in the routing (or pheromone) tables in different nodes which record. However, conventional ACO-based adaptive routing have not consider the integration of spatial/temporal information and multiple congestion factors includes deadlock and faulty nodes.
There are three main topics in this work. First, we use additional temporal and spatial information provides better approximation of network status for global load-balancing. In spatial domain, to acquire the spatial range of congestion information, we record historical buffer information from routers within two-hop of distances, which helps to extend spatial pheromone coverage. In temporal domain, we adopt the concept of Exponential Moving Average (EMA) from stock market to use multiple pheromone for capturing hidden-state dependencies of upcoming congestion status
In the second part of this dissertation, we establish a framework on analyzing the network information and showed how to integrate the spatial and temporal network information. The proposed framework can indicate arbitrary combinations of network information and corresponding routing algorithms. Based on this framework, we use the concept of diffusive pheromone to integration the information and show that we can reconfigure the ACO-PhD algorithm to each routing algorithm in its subsets by adjusting the parameter settings.
In the third part of this dissertation, we integrate the congestion-awareness, deadlock-awareness, and fault-awareness information in channel evaluation function to avoid the hotspot around the faulty router. The three steps behavior of an ant colony while facing an obstacle (failure in NoC) as 1) encounter, 2) search, and 3) select is transformed into effective detouring mechanisms to increase the system throughput and faulty tolerance under faulty network.
In summary, the proposed routing schemes can effectively mitigate the spatial and temporal traffic congestion in NoC and achieve good performance with feasible cost.
Subjects
晶片網路系統
路由演算法
蟻群最佳化
SDGs
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-103-F98943019-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):9c81f407ef84794260475ca6d336d37d