臺灣博碩士論文加值系統

動態可程式化邏輯陣列（dynamic PLAs）由於其延遲可預測及高速等特性，在高效能微處理器的設計中已被廣泛應用。然而，在深次微米設計中，導線延遲已成為影響整體延遲的一個主要因素。因此，在動態可程式化邏輯陣列中之長導線，會造成嚴重的延遲問題。
本篇論文提出一個有效且實際的演算法，來進一步改善動態可程式化邏輯陣列之時序延遲。在動態可程式化邏輯陣列設計中，我們觀察到，一些多餘無用的線段可以被刪除。藉由這些刪除可以減少導線的寄生電阻電容，進而改善動態可程式化邏輯陣列之延遲。我們更觀察到，輸入、輸出及乘積線之位置，會影響到可刪除的多餘無用線段 之數量，進而影響動態可程式化邏輯陣列之延遲。因此，我們提出力導向（force-directed）再排序法，來重新排序輸入、輸出及乘積線之位置。實驗結果顯示，對MCNC測試檔應用我們所提出的方法後，能改善約11.57%之延遲。

The dynamic PLA style has become popular in designing high performance microprocessors because of its high speed and predictable delay. However, the wire delay has become a dominating factor in deep sub-micron design, and thus long wires in dynamic PLAs can cause a significant delay problem. This thesis presents an efficient and practical method to improve the timing delay of dynamic PLAs. Note that we are considering mask programmable PLAs. Therefore during the PLA design, unnecessary excess wire segments in a PLA can be removed. The removal of unnecessary segments of wires can improve the timing delay of a PLA. We have observed that the amount and the length of removable wire segments depend on the ordering of input/output/product lines. We proposed a force-directed reordering method to reorder the input, output and product lines, and then prune the excess wire segments to improve the timing of a PLA. We have conducted experiments on a large set of MCNC benchmark circuits. The results show that the timing delay can be further improved by 11.57% in 32 benchmark circuits after applying our technique.

Chapter 1 Introduction 1
Chapter 2 Delay Model 6
Chapter 3 Input and Output Lines Partition 11
Chapter 4 Force-Directed Reordering 14
4.1 Timing Optimization of Input/Output Lines by Reordering Product Lines 16
4.2 Timing Optimization of Product Lines by Reordering Input/Output Lines 20
Chapter 5 Experimental Results 22
Chapter 6 Conclusions 25
Reference 26

[1] R. K. Brayton, G. D. Hachtel, C. T. McMullen, and A. L. Sangiovanni-Vincentelli, Logic Minimization Algorithms for VLSI Synthesis, Hingham, MA: Kluwer Academic, 1985.
[2] R. M. Dagenais, V. K. Agarwal, and N. C. Ruwin, “ McBOOLE: A new procedure for exact logic minimization,” IEEE Trans. Computer-Aided Design, vol. CAD-5, no. 1, pp. 229-238, Jan. 1985.
[3] C. M. Fiduccia and R. M. Mattheyses, “A linear-time heuristic for improving network partitions,” in Proc. Design Automation Conf., 1982, pp. 175-181.
[4] Y. Hsu, Y. Lin, H. Hsieh, and T. Chao, “Combining Logic Minimization and Folding for PLA’s,” IEEE Trans. Comput., vol. 40, no.6, pp. 706-713, June 1991.
[5] S. P. Khatri, R. K. Brayton, and A. Snagiovanni-Vincentelli, “Cross-talk Immune VLSI Design Using a Network of PLAs Embedded in a Regular Layout Fabric,” Proc. ICCAD, pp. 412-418, 2000.
[6] C. Liu and K. K. Saluja, “ An Efficient Algorithm for Bipartite PLA Folding,” IEEE Trans. Compuer-Aided Design, vol. 12, no. 12, pp.1839-1847, Dec. 1993.
[7] S. Posluszny et al., “Design Methology for a 1.0 Ghz Microprocessor,” Proc. ICCD, pp. 17-23, 1998.
[8] K. Tsuchiya and Y. Takefuji, “A Neural Network Approach to Folding Problems,” IEEE Trans. Computer-Aided Design, vol. 15, no. 10, pp.1299-305, Oct. 1996.