簡易檢索 / 詳目顯示

回結果列表
研究生： 劉忠瑋
Liu, Chung-Wei
論文名稱： 適用於序向電路的分時多工現場可規劃邏輯陣列
New Time-Multiplexed FPGA Architecture for Sequential Circuits
指導教授： 賴源泰
Lai, Yen-Tai
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 電機工程學系
Department of Electrical Engineering
論文出版年： 2006
畢業學年度： 94
語文別： 英文
論文頁數： 53
中文關鍵詞： 序向電路 、電路切割 、優先次序限制 、分時多工現場可規劃邏輯陣列
外文關鍵詞： FPGA, time-multiplexed, circuit partition, precedence constraint, sequential circuit
相關次數： 點閱：172  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 動態可重組的現場可規劃邏輯陣列(DRFPGAs)進化的速度很快，而且越來越受到歡迎，因為它提供了一種高效能且具有彈性的超大型積體電路(VLSI)設計技術。而在這些動態可重組的現場可規劃邏輯陣列中，最廣為流傳的架構就是Xilinx的分時多工現場可規劃邏輯陣列(TMFPGA)。這個架構有一種潛在的能力可以透過分時共用邏輯的方式來提升邏輯的使用率，而且在可重組計算(RC)這個領域中，它已經成為了一個很活躍的研究。
    在本論文中，我們提出一個適用於序向電路切割的分時多工現場可規劃邏輯陣列架構，用以解決傳統的分時多工現場可規劃邏輯陣列在進行序向電路切割時所產生的問題。在傳統的優先次序限制(Precedence Constraint)底下進行序向電路切割時，往往都會造成被切割的子電路間需要許多的暫存器來進行資料的儲存，而我們所提出的這個架構目的是在於修改傳統的優先次序限制，以便使得原本切割序向電路時需要耗費許多暫存器的情況得以改善。

    Dynamically Reconfigurable FPGAs (DRFPGAs) are evolving rapidly, and they are more and more popular, because they offer flexibility and high performance for the VLSI design technology. In these DRFPGAs, the most popular architecture is the Xilinx Time-Multiplexed FPGA (TMFPGA). This architecture has a potential to improve logic utilization by time-sharing logic dramatically, and have become an active research for reconfigurable computing (RC).
    In this thesis, we present a new TMFPGA architecture for sequential circuits to solve the problem of the traditional TMFPGA when partitioning sequential circuits. Under the traditional precedence constraints, it needs many registers to save data between two sub-circuits when partitioning sequential circuits. For this reason, we propose the new architecture to modify the traditional precedence constraints so that it can decrease the utilization rate of the registers when partitioning sequential circuits.

    ABSTRACT CONTENTS LIST OF FIGURES LIST OF TABLES Chapter 1 Introduction 1 1.1 Background 1 1.2 Static RC and Dynamic RC 2 1.3 Spatial and Temporal Partitioning 3 1.4 Thesis Organization 6 Chapter2 Previous Works for Time-Multiplexed FPGA 7 2.1 Time-Multiplexed FPGA 7 2.2 Node Modeling 10 2.3 Circuit Partitioning for Time-Multiplexed FPGA 12 2.4 Previous Works for Partition Algorithms 15 2.5 Restriction of Traditional Precedence Constraints 17 Chapter 3 New TMFPGA Architecture 21 3.1 New TMFPGA Architecture 21 3.2 Operation of TMFPGA 23 3.3 Design Concepts 26 3.4 Operation of Two Registers 31 Chapter 4 Functionality Verification 33 4.1 An example 33 4.2 Timing Verification 40 4.3 Verification Problem 42 Chapter 5 Simulation Results 46 5.1 Simulation Flow Chart 46 5.2 Simulation results 47 Chapter 6 Conclusions 50 REFERENCES 51 LIST OF FIGURES Fig. 1.1 (a) Static RC, (b) Dynamic RC 3 Fig. 1.2 (a) Large circuit, (b) Spatial bi-partitioning, and (c) Temporal bi-partitioning 4 Fig. 2.1 Time-Multiplexed FPGA architecture 8 Fig. 2.2 Time-Multiplexed FPGA configuration model 9 Fig. 2.3 CLB architecture of Time-Multiplexed FPGA 10 Fig. 2.4 Combinational node model 11 Fig. 2.5 Flip-flop node model 11 Fig. 2.6 Temporal partitioning model for Time-Multiplexed FPGA 12 Fig. 2.7 Example of traditional precedence constraint 1 14 Fig. 2.8 Example of traditional precedence constraint 2 14 Fig. 2.9 Example of traditional precedence constraint 3 15 Fig. 2.10 Communication cost of traditional precedence constraint (3) 17 Fig. 2.11 Communication cost in the worst case 18 Fig. 2.12 A circuit ready to be partitioned 18 Fig. 2.13 An optimum solution for partition 19 Fig. 2.14 A solution under traditional precedence constraints 19 Fig. 2.15 Ideal precedence constraints 20 Fig. 3.1 Improved TMFPGA architecture 21 Fig. 3.2 The circuit with two flip-flops in series and its timing diagram 23 Fig. 3.3 The partitioned circuit and its timing diagram 24 Fig. 3.4 A correct result after partition 25 Fig. 3.5 A general circuit with three flip-flops 27 Fig. 3.6 Partitioned circuit of Fig.3.5 28 Fig. 3.7 Timing diagram of Fig. 3.6(a) with D1 enable signal 29 Fig. 3.8 Data variance before and after the clock triggered 30 Fig. 3.9 Proposed registers 31 Fig. 3.10 Write operation of two registers 31 Fig. 3.11 Read operation of two registers 32 Fig. 3.12 Execution order of one stage 32 Fig. 4.1 Test circuit and its timing diagram 33 Fig. 4.2 Two-partition circuit 34 Fig. 4.3 Stage 1 implementation 34 Fig. 4.4 Timing diagram of TMFPGA in stage 1 of user cycle 1 35 Fig. 4.5 Stage 2 implementation 36 Fig. 4.6 Timing diagram of TMFPGA in stage 2 of user cycle 2 36 Fig. 4.7 Data saved by reg1 and reg2 in user cycle 1 37 Fig. 4.8 Timing diagram of TMFPGA in stage 1 of user cycle 2 38 Fig. 4.9 Timing diagram of TMFPGA in stage 2 of user cycle 2 39 Fig. 4.10 Data saved by reg1 and reg2 in user cycle 2 40 Fig. 4.11 Circuit of ak = bk+ck-1 40 Fig. 4.12 Two paths from PO to PIs 41 Fig. 4.13 Input a passing through n flip-flops in series 42 Fig. 4.14 n combinational gates connected in series 42 Fig. 4.15 Deductive result of the combinational path 43 Fig. 4.16 Partitioning result of Fig. 4.13 44 Fig. 4.17 Observance of stage 1 operation 44 Fig. 4.18 Deductive result of the flip-flop path 45 Fig. 5.1 Simulation flowchart 46 LIST OF TABLES Table 1.1 Comparison of computing architectures 2 Table 2.1 Comparison of spatial and temporal partitioning 5 Table 5.1 Benchmark circuit characteristics 48 Table 5.2 Comparison results of the communication cost 49

    [1] A. DeHon, “DPGA-coupled microprocessors: Commodity ICs for the 21st Century”, Proc. IEEE Workshop on FPGAs for Custom Computing Machines, pp. 31-39, 1994.

    [2] A. DeHon, “DPGA utilization and application”, Proc. ACM Int. Symp. FPGAs, pp. 115-121, 1996.

    [3] A. DeHon, “Reconfigurable architecture for general purpose computing”, PhD thesis, Massachusetts Institute of Technology, October 1996.

    [4] B. K. Fawcett, “Taking advantage of reconfigurable logic”, ACM Int. Work. On FPGAs, 1994.

    [5] D. Chang and M. Marek-Sadowska, “Buffer minimization and time- multiplexed I/O on dynamically reconfigurable FPGAs”, Proc. ACM Int. Symp. FPGA, pp. 142-148, 1997.

    [6] D. Chang and M. Marek-Sadowska, “Partitioning sequential circuit on dynamically reconfigurable FPGAs”, IEEE Transactions on Computer, vol. 48, pp. 565-578, June 1999.

    [7] D. Jones and D. M. Lewis, “A time-multiplexed FPGA architecture for logic emulation”, Proc. IEEE Custom Integrated Circuits Conference, pp. 495-49, 1995.

    [8] E. Canto, J. M. Moreno, J. Cabestany, I. Lacadena, and J. M. Insenser, “A temporal bipartitioning algorithm for dynamically reconfigurable FPGAs”, IEEE Transactions on Very Large Scale Integration Systems, vol. 9, no. 1, pp. 210-218, February, 2001.

    [9] G. M. Wu, J. M. Lin, and Y. W. Chang, “Generic ILP-based approaches for time-multiplexed FPGA partitioning”, IEEE Transactions on Computer-Aided Design, vol. 20, pp. 1266-1274, October, 2001.

    [10] H. Liu and D. F. Wong, “Network flow based circuit partitioning for time-multiplexed FPGAs”, Proc. IEEE/ACM Int. Conf. Computer-Aided Design, pp. 497-504, 1998.

    [11] H. Liu and D. F. Wong, “Circuit partitioning for dynamically reconfigurable FPGAs”, Proc. Int. Symp. Field Programmable Gate Arrays, Monterrey, CA, pp. 187-194, February, 1999.

    [12] H. Yang and D. F. Wong, “Efficient network flow based min-cut balanced partitioning”, Proc. IEEE/ACM Int. Conference Computer- Aided Design, pp. 50-55, 1994.

    [13] H. Yang and D. F. Wong, “New algorithm for min-cut replication in partitioned circuits”, Proc. IEEE/ACM Int. Conference Computer-Aided Design, pp.216-222, 1995.

    [14] M. C. T. Chao, G. M. Wu, I. H. R. Jiang, and Y. W. Chang, “A clustering- and probability-based approach for time-multiplexed FPGA partitioning”, Proc. IEEE/ACM International Conference on Computer-Aided Design, pp. 364-368, Nov. 1999.

    [15] N. B. Bhat, K. Chaudhary, and E.S. Kuh, “Performance-oriented fully routable dynamic architecture for a field programmable logic device”, Memorandum No. UCB/ERL M93/42, university of California, Berkeley, 1993.

    [16] P. Andersson and K. Kuchcinski, “Performance oriented partitioning for time-multiplexed FPGAs”, Euromicro Conference, 2000. Proceedings of the 26th, Volume: 1, pp. 60-66, Sept. 2000.

    [17] S. Trimberger, “A time-multiplexed FPGA”, Proc. IEEE Symp. FPGAs for Custom Computing Machines. pp. 22-28, March, 1997.

    [18] S. Trimberger, “Scheduling Designs into a Time-multiplexed FPGA”, Proc. ACM Int. Symp. FPGA, pp. 153-160, 1998.

    [19] W. K. Mak and E. F. Y. Young, “Temporal logic replication for dynamically reconfigurable FPGA partitioning”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and System, vol. 22, No.7, July 2003.

    [20] Xilinx, The Programmable Logic Data Book, 1996.

    下載圖示 校內：2007-07-19公開
    校外：2007-07-19公開
    QR CODE