An Energy-aware Dynamic Job Dispatcher for Network-on-Chip

由於深次微米技術的發展，在單一矽晶片可容納10億個電晶體的情形下，使得設計一個完整的系統在單一晶片上已成為可能。不過，在設計大型系統晶片時，處理IP間的訊息傳送將變成巨大的挑戰。晶片網路(Network-on-Chip, NoC)的架構已經被提出來，靠著提供一個更標準化和可擴展的架構以解決在將來的SoC系統裡晶片上複雜的通訊。在這篇論文裡，我們提出一個在NoC架構下同質多處理器晶片系統的功率感知演算法，可以在滿足一定的效能限制下動態的安排作業使總能源消耗減到最小。我們的工作調度演算法安排有較大通訊傳輸的工作在較接近的處理器以降低通訊能源消耗。實驗結果顯示我們提出的演算法比標準的Earliest Deadline First演算法可以節省25.11%的通訊能源消耗。With the advance of deep-submicron technology, there can be more than 1 billion transistors on a single silicon die making it possible to implement a complete system in a single chip. However, in large scale System-on-Chip designs, the inter-communication between IP cores becomes huge challenge. Network-on-chip (NoC) architectures have been proposed to mitigate the complex on-chip communication problem in future SoC systems by providing a more modular and scalable structure. In this thesis, we propose an energy-aware algorithm which dynamic schedules jobs in a NoC based homogeneous chip multiprocessor system to meet the performance constraint and minimize total energy cost. Our Job Dispatcher algorithm schedules each pair of tasks which have large communication traffic between them onto nearer processor cores to minimize communication energy consumptions. Experimental results show that the proposed algorithm can save communication energy consumption up to 25.11% comparing with standard Earliest Deadline First (EDF) algorithm.誌謝 i文摘要 iiBSTRACT iiiONTENTS ivIST OF FIGURES viIST OF TABLES viihapter 1 Introduction 1hapter 2 Background and Related Work 8.1 NoC basics 8.1.1 Topology 9.1.2 Routing Algorithm 14.2 Scheduling algorithm 16hapter 3 System Model and Problem Definition 19.1 Architecture model 19.1.1 Mesh topology model 19.1.2 NoC delay model 22.1.3 NoC energy model 23.2 The workload model 24.2.1 Communication task graph 24.2.2 Granularity of task 25.3 The scheduling model 26.4 Energy-aware dynamic jobs scheduling problem 27hapter 4 Energy-Aware Dynamic Job Dispatcher 30.1 The Scheduling algorithm 30hapter 5 Experimental Results 36.1 Experimental environment 36.2 Experimental results 37hapter 6 Conclusion 41ibliography 4