臺灣博碩士論文加值系統

對串流處理應用程式來說，單位時間的運算量(throughput)是非常重要的。而多個彼此相異的特殊應用處理器(ASIP)不僅能提供充分的throughput，且相較於客製化的ASIC，還能提供較好的彈性。
本篇論文將提出一個分割與排程演算法，透過特殊應用處理器中的特殊應用指令(ASI)來達成資料之間的平行運算，並透過多個ASIP來達到工作(task)之間的平行運算及管線(pipeline)之間的平行。
在本篇論文的流程中，首先將分析一個串流應用程式之中的資料相依性，以及可能產生的候選特殊應用指令，並建立一個相對應的工作圖；接著，再將此工作圖將切割為多個部份，並透過排程演算法將工作分配到管線上，以滿足一個給定的throughput限制，並僅可能地使用較少的硬體成本。實驗數據中顯示，使用特定應用指令以平衡管線，有機會可以減少8%左右的硬體成本。

Stream processing applications demand high throughput. Multiple heterogeneous Application-Specific Instruction-set Processor (ASIP) architectures tend not to offer only sufficient throughput but also runtime flexibility, which cannot be provided by custom ASIC solutions.
In this paper, the partition and scheduling methodology has been proposed to utilize both the Application-Specific Instruction (ASI) in ASIP, to exploit fine-grain data parallelism, and multiple ASIPs, to exploit task and pipeline parallelism.
In our design flow, the data dependence of a streaming application will be analyzed with all possible ASI candidates and then to generate the corresponding task graph. The task graph will be partitioned and scheduled to the pipeline stages to achieve the desired throughput constraint with less hardware cost. The experiment results show an average hardware reduction of 8% compared to the results without using ASIs.

致謝...i
摘要...ii
Abstract...iii
目錄...iv
圖目錄...vi
表目錄...viii
第一章 導論...1
第二章 相關文獻...4
第三章 Software Pipelining on Multiple ASIPs...6
3.1 ASIP...6
3.1.1 Control Flow Graph and Data Flow Graph...6
3.1.2 Template and Candidate...8
3.2 Software Pipelining...9
3.2.1 Task Graph...10
3.2.2 Pipeline stages...10
3.3 問題定義與假設...12
第四章 Design Flow and Algorithm for Multiple ASIPs...13
4.1 CDFG Generation...14
4.1.1 GCC intermediate representation - RTL Expression...15
4.2 Directed Acyclic Task Graph Generation...17
4.2.1 Loop Clustering and Unrolling...17
4.2.2 Hierarchical Task Graph...18
4.2.3 Data Dependence in Memory...19
4.3 Template Generation...19
4.3.1 Template Generation...19
4.4 Task Partition and Scheduling Algorithm...20
4.4.1 Modulo Scheduling...20
4.5 ASI Selection...22
4.5.1 Priority Value Calculation for Candidates...23
4.6 Code Replacement for ASI...24
4.6.1 Machine Description...25
4.6.2 UNSPEC RTL Expression Type...26
第五章 實驗數據與分析...29
5.1實驗環境設定...29
5.2 ASI對硬體成本的影響...30
第六章 結論與未來展望...32
參考文獻...33

[01]Altera corp.URL : http://www.altera.com
[02]F. Sun, S. Ravi, A. Raghunathan, and N. K. Jha, "Application-Specific Heterogeneous Multiprocessor Synthesis Using Extensible Processors," IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 25, NO. 9, SEPTEMBER 2006.
[03]S. L. Shee, S. Parameswaran, "Design Methodology for Pipelined Heterogeneous Multiprocessor System," DAC’07, June 4–8, 2007.
[04]K. Vivekanandarajah, S. K. Pilakkat, "Task Mapping in Heterogeneous MPSoCs for System Level Design," 13th IEEE International Conference on Engineering of Complex Computer Systems.
[05]A. Tumeo, C. Pilato, F. Ferrandi, D. Sciuto, P. L. Lanzi, "Ant Colony Optimization for Mapping and Scheduling in Heterogeneous Multiprocessor Systems," Embedded Computer Systems: Architectures, Modeling, and Simulation, 2008. SAMOS 2008. International Conference.
[06]GNU Compiler Collection, URL : http://gcc.gnu.org/
[07]B. R. Rau, "Iterative Modulo Scheduling: An Algorithm For Software Pipelining," Proceedings of the 27th annual international symposium on Microarchitecture, 1994.
[08]M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, and R. B. Brown, "MiBench: A free, commercially representative embedded benchmark suite," in Proc. IEEE 4th Ann. Workshop Workload Characterization, 2001, pp. 3–14.
[09]Wakabayashi M, Inoue K, Amano H, "ISIS: Multiprocessor simulator library." Proc 16th IASTED Int Conf on Applied Informatics (AI''99), p198-200.