Due to the growing demand on high performance and low power in embedded systems, many core architectures are proposed the most suitable solutions. While the design concentration of many core embedded systems is switching from computation-centric to communication-centric, Network-on-Chip (NoC) is one of the best interconnect techniques for such architectures because of the scalability and high communication bandwidth. Formalized and optimized system-level design methods for NoC-based many core embedded systems are desired to improve the system performance and to reduce the power consumption. In order to understand the design optimization methods in depth, a case study of optimizing many core embedded systems based on 3-Dimensional (3D) NoC with irregular vertical link distribution topology through task mapping, core placement, routing, and topology generation is demonstrated in this chapter. Results of cycle-accurate simulation experiments prove the validity and efficiency of the design methods. Specific to the case study configuration, in maximum 60% vertical links can be saved while maintaining the system efficiency in comparison to full vertical link connection 3D NoCs by applying the design optimization methods.
TopIntroduction
Since NoCs are promoted to be the one of the best interconnect techniques for many core embedded systems, it is important to improve the NoCs performance and to reduce the communication overhead in order to optimize the system configuration. From the perspective of hardware, developing the efficient and complex NoCs routers architectures that support multi-casting communication, various Quality-of-Service (QoS) modes, adaptive routing mechanisms and optimized hardware based flow control methods, etc. is the key to the success (Duato, Yalamanchili, & Ni, 2003). However, implementing these functions on hardware certainly leads to more overheads in terms of hardware area and power consumption. Depending on the characteristics of different target software applications, the improvement of performance might be sometimes less than expected. Nevertheless, many NoCs routers architectures with the complex and advanced hardware functions are still proposed and claimed to gain the performance and power advantage for the entire system with the unpredictable running applications such as Chip Multi-Processor (CMP) and soft real-time systems.
On the other hand, if the characteristics of the target applications are known in advance, such as in mobile communication, automation and other hard real-time systems applications, the entire system can achieve excellent performance and cost efficiency by employing proper design optimization methods. Therefore, the hardware implementations of the NoC routers can be simplified. Then, the area and power overhead is reduced accordingly.
Several design configurations such as task mapping, core placement, routing and topology have to be determined to deliver the final system configuration based on the given system specification. Among the various patterns of different design configurations, designers should optimize each design configuration and build the final system configuration at the best trade-off point. The best trade-off point of NoC system is always the most balancing point between communication overhead and performance with respect to the communication bandwidth requirement, NoC transaction latency, communication energy consumption, NoC link throughput and so forth. In this chapter, formalized system level design optimization methods for NoC based many core embedded systems are introduced and demonstrated. Four design configurations (task mapping, core placement, routing and topology) are optimized in order to deliver the final system configuration at the best trade-off point.
Simulated Annealing (SA), Genetic Algorithm (GA) and Tabu Search (TS) are applied as the design optimization algorithms. All of the three algorithms are meta-heuristic searching algorithms. Hence, the efficient and correct cost functions are needed to lead the optimization to the right direction. In this chapter, four different cost functions such as Link Utility Distribution Degree (LUDD), NoC Communication Energy (ENG), Global Routing Path Length (GRPL) and Guaranteed Bandwidth (GBW) are demonstrated. Different possible combinations of all cost functions and algorithms are employed to optimize the entire NoC system through task mapping, core placement, routing and topology.
A Hybrid Constructive Heuristic (HyCH) algorithm is also introduced in order to optimize the NoC system, because the constructive heuristic is more computation time efficient in comparison to meta-heuristic algorithms. However, the optimization degree is limited by the characteristics of constructive heuristic algorithms when multiple solution elements are floating and to be determined. Therefore, in this chapter, the HyCH algorithm is proposed to optimize single NoC design configuration only. For instance, the HyCH is utilized to optimize the NoC core placement, when the task mapping, routing and topology design configurations are fixed and unchangeable.
Besides introducing the design optimization methods, the utilization flow of the proposed methods are also demonstrated. Four system evaluation metrics as flit latency, flit data rate, NoC area and system efficiency factor (SEF) are applied to evaluate the final determined system configuration. SEF is the novel concept to evaluate the entire NoC system efficiency, which considers both the performance and cost numbers. The detailed explanation of these metrics is given in the following section.