施吉昇Shih, Chi-Sheng臺灣大學:資訊工程學研究所邱奕升Chiu, Yi-ShengYi-ShengChiu2010-05-172018-07-052010-05-172018-07-052009U0001-1808200911460100http://ntur.lib.ntu.edu.tw//handle/246246/183382由於現今多媒體程式的運算需求越來越高，因此異質性多核心平台漸漸的被廣泛使用。在異質性多核心平台上，管線設計技術常被運用以提升效能。但在多媒體程式中，常存在著許多資料相依性，這些資料相依性常使得管線設計技術無法適當的發揮。在這篇論文中，我們針對多個多媒體程式與異質性多核心平台提出了一個類似拼磚行為的演算法，目的是在建立出一個具有重複性與高效能的管線排程表，並且符合每個多媒體程式的需求。我們將我們所提出的演算法與最佳解，模擬退火法和貪婪法作比較，在一連串的實驗下我們可以印證我們所提出的設計方法的效力。Heterogeneous multi-core platforms has become the trend for the high performance requirement of multimedia pplications. The pipeline techniques are widely used in the multi-core platforms to lead performance elevation, but the data dependencies of multimedia applications often make pipelined design unsatisfied. In this thesis, we target on multimedia streaming applications described as conditional data flows on heterogeneous multi-core platforms, and we design a ”Tile Piecing Algorithm” for pipelined schedule synthesis within the targeted applications and platforms. The approach gives an efficient way to construct a pipelined schedule. The performance evaluation result prove the proposed ”Tile Piecing Algorithm” could reduce the runtime overhead and derive a well-designed pipelined schedule.List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiist of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiist of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixhapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Objective and Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6hapter 2 Background and RelatedWork . . . . . . . . . . . . . . . . . . . . . . 7.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1.1 Multi-Core Platform . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1.2 Virtualization Environment . . . . . . . . . . . . . . . . . . . . . . 8.1.3 Pipelined Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9hapter 3 Workload Model and Problem Definition . . . . . . . . . . . . . . . 12.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.2 Application Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.3 Pipelined Schedule Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 16.4 Problem Definition and Hardness . . . . . . . . . . . . . . . . . . . . . . . 17.4.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 17.4.2 Problem Hardness . . . . . . . . . . . . . . . . . . . . . . . . . . . 19hapter 4 Pipelined Schedule Synthesis for Periodic Conditional Data Flows 20.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20.2 Observation of Applications with Data Dependency . . . . . . . . . . . . 21.2.1 Data Partition and Functional Partition . . . . . . . . . . . . . . . 21.2.2 Data Dependencies within H.264 decoding . . . . . . . . . . . . . 22.3 Tile Piecing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23.3.1 WallWidth Calculation . . . . . . . . . . . . . . . . . . . . . . . . 24.3.2 Tile Shapes Creation . . . . . . . . . . . . . . . . . . . . . . . . . . 26.3.3 TiledWall Construction . . . . . . . . . . . . . . . . . . . . . . . . 38hapter 5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 42.1 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Experiment Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45.2.1 Simulation for Various Data Dependency Graphs . . . . . . . . . 45.2.2 Simulation for H.264 Decoding . . . . . . . . . . . . . . . . . . . . 48hapter 6 Conclusion and FutureWork . . . . . . . . . . . . . . . . . . . . . . . 52.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 FutureWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52eferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54application/pdf2664863 bytesapplication/pdfen-US管線管線排程資料流資料相依性異質性多核心平台多媒體程式效能pipelinepipelined scheduledata flowdata dependencyheterogeneous multi-core platformmultimedia applicationperformancethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/183382/1/ntu-98-R96922111-1.pdf