動態可重組的現場可規劃邏輯陣列(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 under proceed process, 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 improve the execution time delay problem with the traditional TMFPGA but also correct the function delay problem with the traditional TMFPGA.. In this thesis, we also propose a novel circuit partitioning algorithms for this nTMFPGA architecture to minimize the delay costs without increase the communication costs. Finally, the experimental results demonstrate the effectiveness of our approach.

[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] Chung-Kai Liu, “An Improved Time-Multiplexed FPGA and Its Circuit Partitioning Algorithm”, Master of Science thesis, National Cheng Kung University Tainan, Taiwan, R.O.C., June 2005.

[4] Chung-Wei Liu, “New Time-Multiplexed FPGA Architecture For Sequential Circuits”, Master of Science thesis, National Cheng Kung University Tainan, Taiwan, R.O.C., June 2005.

[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] 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.

[9] H. Liu and D. F. Wong, “A Graph Theoretic Optimal Algorithm for Schedule Compression in for Time-Multiplexed FPGA Partitioning”, Proc. IEEE/ACM Int. Conf. Computer-Aided Design, pp. 400-405, 1999.

[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. 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.

[12] Joao M. P. Cardoso and Horacio C. Neto, “An Enhanced Static-List Scheduling Algorithm for Temporal Partitioning onto RPUs”, Proc. IEEE Int. Conference VLSI, pp. 485-496, 1999

[13] 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.

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

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

[16] 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

[17] Xue-jie Zhang and Kam-wing Ng, “A Temporal Partitioning Approach Based on Reconfiguration Granularity Estimation for Dynamically Reconfigurable Systems”, IEEE International Conference on Field-Programmable Technology (FPT), Dec. 2003, pp. 344 - 347

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