動態可重組的現場可規劃邏輯陣列進化的速度很快，而且越來越受到歡迎，因為它提供了一種高效能且具有彈性的超大型積體電路設計技術。而在這些動態可重組的現場可規劃邏輯陣列中，最廣為流傳的架構就是Xilinx的分時多工現場可規劃邏輯陣列。這個架構有一種潛在的能力可以透過分時共用邏輯的方式來提升邏輯的使用率，而且在可重組計算這個領域中，它已經成為了一個很活躍的研究。

　　在本論文中，我們提出一個改良式分時多工現場可規劃邏輯陣列架構去解決傳統的分時多工現場可規劃邏輯陣列的優先次序限制問題，而我們所提出的這個架構，不僅可以增加傳統分時多工現場可規劃邏輯陣列的彈性，而且還可以改善傳統分時多工現場可規劃邏輯陣列的效率。而在本論文中，我們針對這個改良式分時多工現場可規劃邏輯陣列也提出了的一個新穎的兩階段電路切割演算法，去使得被切割出來的級數最小，以及平衡每一級的面積。而在這個電路切割演算法中，我們還提出了一個IALAP排程演算法去改善傳統ALAP排程演算法不能排程序向電路的問題。最後，實驗結果證實了我們所使用的演算法是相當有效的。

　　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 propose an improved TMFPGA (iTMFPGA) architecture to solve the precedence constraint problem of the traditional TMFPGA. This iTMFPGA not only increases the flexibility of the traditional TMFPGA but also improves the efficiency of the traditional TMFPGA. In this thesis, we also propose a novel two phase circuit partitioning algorithm for this iTMFPGA architecture to minimize the number of partitioned stage and balance the area of every stage. In this circuit partitioning algorithm, we propose an IALAP scheduling algorithm to improve the problem of traditional ALAP scheduling algorithm that can not schedule the sequential circuit. Finally, the experimental results for the benchmark circuits 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 ａpplication”, 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
　　Transactionson 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
　　partitioningfor 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. FPGA, Monterrey,
　　CA, pp. 187-194,February, 1999.

[12] H. Yang and D. F. Wong, “Efficient network flow based
　　min-cutbalanced 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-AidedDesign, pp.216-222, 1995.

[14] M. C. T. Chao, G. M. Wu, I. H. R. Jiang, and Y. W. Chang,
　　“A clusteringandprobability-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
　　Circuitsand System, vol. 22, No.7, July 2003.

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