臺灣博碩士論文加值系統

可重組式計算不但提供了在硬體加速運算的能力來增加效能，也同時保留軟體使用的彈性。由於單一晶片的可重組式系統無法負荷大量的應用，因此多FPGA之可重組式系統應運而生。透過切割，應用對應至多個FPGA上執行。在多FPGA之可重組式系統中，FPGA間的I/O頻寬是有限制的，在系統中使用I/O頻寬必須謹慎。
本篇論文的目的，主要是開發在多FPGA之可重組式系統中資料流處理的潛在效能。我們提出了兩個資料流排程和切割的方法。第一個方法能在特定成本函式的要求下，透過對資料流程圖的處理，找出針對資料流程圖最理想的FPGA，包含FPGA大小和I/O頻寬，以利多FPGA之可重組式系統之設計。第二個方法針對給定的多FPGA之可重組式系統，利用對資料流程圖排程和切割的方法，減少系統執行時FPGA之間通訊的負擔來提高執行效能。在我們的模擬中，使用數位信號處理的核心演算法為基準評量方法，此二方法的結果是可被證實的。

The reconfigurable computing offers computation ability in hardware to increase performance, but also keeps the flexibility in software solution. The multi-FGPA reconfigurable system provides means for dealing with the applications that are too large to fit within a single FPGA, but may be partitioned over multiple FPGA available. The systems have a limited number of I/O pins that connect the FPGAs together, and therefore I/O pins must be used carefully.
The object of this thesis is to exploit potential throughput of stream processing in multi-FPGA reconfigurable system. We proposed two approaches that schedule data flow graph onto the multi-FPGA system. The first method makes use of data flow graph to find the ideal size and connectivity of FPGA for multi-FPGA reconfigurable system. And the second approach increases the throughput by decreasing the communication overhead in current multi-FPGA reconfigurable system. In our simulation, we use kernel algorithms of DSP as benchmark. The results are promising.

Contents
摘要 I
ABSTRACT II
誌 謝 III
CONTENTS IV
LIST OF FIGURES VI
CHAPTER 1 INTRODUCTION 1
1.1 Observations and Motivations 1
1.2 Proposed Approaches 2
1.3 Introduction to Reconfigurable Computing System 4
1.4 Stream Processing 5
1.5 Organization of The Thesis 6
CHAPTER 2 BACKGROUND 7
2.1 Data Flow Graph Model 7
2.2 Reconfigurable Architecture Model 8
2.3 Basic Time Constrained Scheduling 11
2.4 Basic Hardware Constrained Partitioning 15
2.5 Summary 17
CHAPTER 3 PROPOSED DATA FLOW GRAPH SCHEDULING 18
3.1 Overview of Proposed Data Flow Graph Scheduling Flow 19
3.2 Scheduling Data Flow Graph with Cost Consideration 21
3.2.1 Overview of the Scheduling Data Flow Graph with Consideration 22
3.2.2 Earliest Latest-time First Scheduling 24
3.3 Scheduling Data Flow Graph with Constraints 30
3.3.1 The Flowchart of Earliest Execution Time First Partitioning 30
3.3.2 The Detailed Steps of Earliest Execution Time First Partitioning 32
3.4 Summary 35
CHAPTER 4 SIMULATION RESULT AND ANALYSIS 36
4.1 Simulation Environment 36
4.2 Evaluation of Simulation 37
4.3 Results and Analysis 38
4.4 Summary 42
CHAPTER 5 CONCLUSIONS 43
REFERENCES 45

References
[1]. Katherine. Compton, Scott. Hauck, Reconfigurable Computing: A Survey of System and Software, ACM Computing Survey, June 2002.
[2]. Vinoo Srinivasan, Sriram Govindarajan, and Ranga Vemuri, Fine-Grained and Coarse-Grained Behavioral Partitioning with Effective Utilization of Memory and Design Space Exploration for Multi-FPGA Architectures, IEEE Transactions On Very Large Scale Integration (VLSI) Systems, February 2001
[3]. Karthikeya M. Gajjala Purna, and Dinesh Bhatia, Temporal Partitioning and Scheduling Data Flow Graphs for Reconfigurable Computers, IEEE Transactions On Computers, June 1999
[4] Michael I. Gordon, William Thies, Michal Karczmarek, Jasper Lin, Ali S. Meli, Andrew A. Lamb, Chris Leger, Jeremy Wong, Henry Hoffmann, David Maze, and Saman Amarasinghe, A Stream Compiler for Communication-Exposed Architectures, ASPLOS, 2002
[5] “TMS320C62x DSP Library Programmer's Reference”, Texas Instruments Incorporated, April 2002
[6] “TMS320C62x Image-Video Processing Library Programmer's Reference”, Texas Instruments Incorporated, April 2002
[7] Robert Stephens, A survey of stream processing, Acta Informatica, February 1997
[8] Michael I. Gordon, William Thies, Michal Karczmarek, Jasper Lin, Ali S. Meli, Andrew A. Lamb, Chris Leger, Jeremy Wong, Henry Hoffmann, David Maze, and Saman Amarasinghe, A Stream Compiler for CommunicationExposed Architectures, ASPLOS 2002
[9] P.G.. Paulin and J.P. Knight, Force-Directed Scheduling for the Behavioral Synthesis of ASIC’s, IEEE Transaction on Computer-Aided Design of Integrated Circuits and System, June 1989