施吉昇臺灣大學：資訊工程學研究所王志亘Chih-HsuanWang2007-11-262018-07-052007-11-262018-07-052007http://ntur.lib.ntu.edu.tw//handle/246246/53640多媒體系統晶片均有產能限制的性質。所謂產能即每單位時間處理 輸入資料量的大小，這是多媒體應用固有的限制。系統晶片上多媒體應用結合了不同的軟體工作、硬體工作來完成。我們可利用管線設計技巧將應用切割成同時運行的多個階段，充分利用硬體使用率以提升產能來設計低花費的系統。然而管線設計帶來額外的負擔:額外的管線記憶體，在設計中會使用管線記憶體來達成不同工作間溝通的進行。在這篇論文中，我們提出了一個迴圈式的經驗法則設計方法，目的是在設計管線式軟硬體排程方法，使此排程使用的管線記憶體降到最少，並且符合產能限制需求。我們對這個方法做了許多不同環境下的模擬實驗，在一連串得到近似最佳解的實驗下我們可以印證我們所提出的設計方法的效力。Multimedia SoCs have property of throughput constraints. The throughput of multimedia application is the rate at which it processes input data, and this is usually the prime constraint on most multimedia applications. In order to meet the throughput constraints of these system with low cost, it is necessary to construct more efficient implementation with pipelined design. Idea of pipelined design is to divide applications into several concurrently executing stages, thus increasing its data rate. In this thesis, we presented a solution to pipelined schedule synthesis for multimedia SoCs such that pipeline buffer is minimized under throughput constraints. We proposed a three-step exploration methodology to obtain pipelined schedule with minimal pipeline buffer which meets the given throughput constraints. Performance evaluation results prove the proposed three-step exploration methodology could reduce the run-time overhead and derive a near-optimal solution.List of Figures vii Lis of Algorithms viii Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Objective and Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Chapter 2 Background and RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1 Backgroud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Chapter 3 Workload Model and Problem Definition . . . . . . . . . . . . . . . . . . 9 3.1 Architecture Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Application Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 Problem Definition and Hardness . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3.2 Problem Hardness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Chapter 4 Pipelined Schedule Synthesis for Multimedia SoC . . . . . . . . . . . . . 14 4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.2 Metrics of Pipelined Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.3 Minimum Initiation Interval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.4 List-based Pipelined Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.4.1 List-based Pipelined Schedule . . . . . . . . . . . . . . . . . . . . . . . 19 4.4.2 Task-Selected Priority Function . . . . . . . . . . . . . . . . . . . . . . . 20 4.5 Retiming Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.5.1 Cut Set Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.5.2 Retiming Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Chapter 5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.1 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.2 Experiment Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.3 Study of Real Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Chapter 6 Conclusion and FutureWork . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.2 FutureWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43520211 bytesapplication/pdfen-US軟硬體共同設計管線排程產能限制多媒體系統晶片hardware software co-designpipelined schedulethroughput constraintmultimedia SoCthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53640/1/ntu-96-R94922118-1.pdf