動態可重組的現場可規劃邏輯陣列(DRFPGAs)進化的速度很快，而且越來越受到歡迎，因為它提供了一種高效能且具有彈性的超大型積體電路設計技術。而在這些動態可重組的現場可規劃邏輯陣列中，最廣為流傳的架構就是Xilinx 的分時多工現場可規劃邏輯陣列(TMFPGA)。這個架構有一種潛在的能力可以透過分時共用邏輯的方式來提升邏輯的使用率，而且在可重組計算(RC)這個領域中，它已經成為了一個很活躍的研究。
在本論文中，我們以一個新型分時多工現場可規劃邏輯陣列架構(New TMFPGA)去解決傳統的分時多工現場可規劃邏輯陣列的優先次序限制(Precedence Constraint)問題，而這個新型的架構，不僅可以增加傳統分時多工現場可規劃邏輯陣列的彈性，而且還可以改善傳統分時多工現場可規劃邏輯陣列的效率，並改正了傳統架構上執行電路的延遲問題。而在本論文中，我們針對這個新式分時多工現場可規劃邏輯陣列提出了一個創新的電路切割演算法(Circuit Partitioning Algorithm)，使得被切割出來的通訊成本最小，並在此通訊成本下，再去最小化級數，使得電路重組次數能減少。最後，實驗的結果證實了我們所使用的演算法是相當有效的。

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. Among 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 use a new TMFPGA (nTMFPGA) architecture to solve the precedence constraint problem of the traditional TMFPGA. This nTMFPGA not only increases the flexibility and improves the efficiency of the traditional TMFPGA but also correct the function delay problem with the traditional TMFPGA. In this thesis, we also propose two novel circuit partitioning algorithms for this nTMFPGA architecture to minimize the communication costs and the number of partitioned stages without increase
the communication costs. Finally, the experimental results demonstrate the effectiveness of our algorithm.

[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 timemultiplexed 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. 8 0
[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 clusteringand 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. 8 1
[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.