施吉昇臺灣大學：資訊工程學研究所陳奕安Chen, Yi-AnYi-AnChen2007-11-262018-07-052007-11-262018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/54077系統晶片的主要元件常常由處理器、特殊應用積體電路、矽智財等構成。使用哪些元件去整合成一個系統晶片對於該系統晶片的價錢、效能有非常大的影響。隨著製程不斷地進步，如何在系統層級決定一個系統晶片上的元件變成一個最重要的議題。以往的論文在運算層級討論整合演算法，在本篇論文中，我們在系統層級研究整合演算法，這些整合演算法決定了系統晶片上面硬體元件的配置、工作的分配，以及工作的排程。我們改良並比較了許多種類的整合演算法，包括指數式最佳演算法，重覆式演算法，建構式演算法，基因演算法等等。我們透過大量的模擬實驗呈現他們在不同的情況下各自的效能及結果。System-on-a-Chips are usually synthesized by a number of ASICs, IPs, and (customized or general) microprocessors to reduce design overhead and manufacture cost. Which processing elements are chosen and how the chosen processing elements are assigned to complete the tasks have significant impacts on the cost and performance of the system. As the complexity of SoC increases, how to find an optimal system-level system architecture has became a critical issue for SoC design. Earlier researches focus on the system synthesis on operation level. In this thesis, we are concerned with system synthesis on system-level. The algorithms in this thesis determine the scheduling, allocating, and mapping on system-level. We compare the performance of several types of synthesis algorithms including exponential optimal algorithms, iterative heuristic algorithms, constructive heuristic algorithms, genetic-based algorithms. We shall present their performance for different task models. The result shows that the iterative heuristic algorithms can get the near optimal solution when there are not large number of instances. As the number of instances increases, the genetic algorithm outperforms the other algorithms on cost, and its mean run-time overhead is still acceptable.Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii List of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Objective and Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Chapter 2 RelatedWork and Formal Model . . . . . . . . . . . . . . . . . . . . 5 2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Formal Model and Problem Definition . . . . . . . . . . . . . . . . . . . . 10 Chapter 3 Optimal Branch and Bound Algorithm . . . . . . . . . . . . . . . . . 16 3.1 Branch method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Bounding method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Chapter 4 Constructive Heuristic Algorithms . . . . . . . . . . . . . . . . . . . 20 4.1 Formal Model and Force Function . . . . . . . . . . . . . . . . . . . . . . 20 4.2 SAMT Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Chapter 5 Iterative Heuristic Algorithms . . . . . . . . . . . . . . . . . . . . . . 25 5.1 HW-oriented Iterative Algorithm . . . . . . . . . . . . . . . . . . . . . . . 25 5.2 SW-oriented Iterative Algorithm . . . . . . . . . . . . . . . . . . . . . . . 28 5.3 ISAMT Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Chapter 6 Genetic Based Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.1 Genetic Algorithm for SAM . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.2 Chromosome Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 6.3 Scheduling and Timing Constraint . . . . . . . . . . . . . . . . . . . . . . 37 6.4 Fitness Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 6.5 Population Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Chapter 7 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Chapter 8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48343894 bytesapplication/pdfen-US即時單晶片排程軟硬體協同設計real-timeSoCschedulingsynthesissystem-levelthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/54077/1/ntu-95-R93922095-1.pdf