賴飛羆臺灣大學：資訊工程學研究所彭治弘Peng, Chin-HungChin-HungPeng2007-11-262018-07-052007-11-262018-07-052005http://ntur.lib.ntu.edu.tw//handle/246246/53673對深次微米、高效能的電路而言，導線延遲在決定電路效能時佔了一個相當重要的地位。在這篇論文中，我們最小化最後連線的花費於選擇備用的邏輯元件過程以應付電路功能的改變。我們提出了一個解決方案包含下列的三個步驟：配對、覆蓋、與最小花費優先置放方法。這個解決方案以循序的方式工作，並且整合邏輯層次的資料結構與物理的元件位置資訊和快速有用的經驗法則去處理大型的功能改動次序要求。 不像傳統的技術對映基於邏輯閘延遲、面積、與功率等的估計方式，我們應用修改過後的動態規劃演算法在覆蓋這一個階段。接下來我們以不同的方式來使用最小花費優先的經驗法則來有效率的計算出最後每個ECO電路的連線花費。因此我們可以從多種排程後的策略選擇一個較好的實做方式。實驗結果顯示出我們的演算法的效率與有效性。For deep-submicron and high-performance circuits, the interconnection delay plays a very important role in determining the circuit performance. In this thesis, we minimize final interconnections cost during the process of spare cell selection for functional change. We present a scheme which consists of three steps: matching, covering, and least-cost-first placement. It works in a sequential manner and integrates logic level data structures, physical cell location information, and fast useful heuristics to handle large scale ECO functional changed lists. Unlike the traditional technology mapping that is based on the estimation of gate delays, area, and power, we apply modified dynamic programming algorithm in the covering step. Further, applying least-cost-first heuristic in different ways, we can evaluate the final interconnection cost of each ECO circuit tree more efficiently. Therefore, we can find a better implementation from various scheduling schemes. Experimental results show the efficiency and effectiveness of our algorithm.Abstract III 中文摘要 IV Table of Contents V List of Figures VII List of Tables VIII Chapter 1 1 Introduction 1 Chapter 2 4 Motivation 4 2.1 Problem Formulation 4 2.2 Problem Assumptions 5 2.3 Input File Formats 5 Chapter 3 7 Algorithms 7 3.1 Main flow to solve the problem 7 3.2 Main procedures 8 3.2.1 Create necessary NET structures 8 3.2.2 Create tree structures of a library 11 3.2.3 Technology mapping 15 3.2.4 Assemble gates 18 3.2.5 Initial placement 22 3.2.6 Branch and bound 22 3.2.7 Logic simulator/verification 23 3.3 Heuristics 30 3.3.1 Least cost first 30 3.3.2 High cell counts first 30 3.3.3 High pin counts first 31 3.3.4 Bounding box heuristic 32 Chapter 4 33 Results and Discussion 33 4.1 Test cases 33 4.2 Cost and running time analysis 33 Chapter 5 42 Conclusion and Future Works 42 Bibliography 44en-US邏輯合成技術對映配對覆蓋動態規劃工程改動次序連線花費備用元件選擇模擬Logic SynthesisTechnology MappingMatchingCoveringDynamic ProgrammingECOInterconnect CostSpare Cell SelectionSimulationthesis