Data-dependent Wire Permutation for Crosstalk Minimization

隨著製程減小到進入奈米規模，由鄰近導線所引起的耦合電容快速地增大，並且對於積體電路上的訊號完整度有著很顯著的影響。在這篇論文中，我們在一般的匯流排上提出一個合併訊號變動的演算法。首先，我們發現在資料匯流排上確實有資料相依性的存在。在加入米勒效應的考量下，我們估算資料與資料間傳送時的相依性，並且希望減小由於鄰近導線所引起寄生的耦合電容。藉由分析在資料匯流排上傳送的資料，我們透過排線重排的方式減少訊號變動的數目。實驗數據顯示平均來說在執行檔會有5%的改進，在.pdf檔有4.3%，在.txt檔會有20%。As technology shrinks to nanometer eras, coupling capacitances between adjacent wires grow rapidly, and have a significant impact on signal integrity of an integrated circuit. In this thesis, we propose an algorithm for merging the simultaneous switching behavior on a general bus. First of all, we find there is indeed data dependency on data bus. Due to the Miller Effect considering data dependency, we minimize the coupling capacitance induced between adjacent wires. By analyzing the data transmitted on data bus, we reduce the numbers of the worst case of the switching patterns through wire reordering. Experimental results demonstrate that we can achieve 5% improvements on average in the bin files, 4.3% in the .pdf files, and 20% in the .txt files.Acknowledgements ii 摘要 iii Abstract iv Content v List of Tables vi List of Figures vii Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Our Contribution 5 1.3 Organization of the Thesis 7 Chapter 2 Preliminaries 8 2.1 Crosstalk Introduction 8 2.2 Bus Model 10 2.3 Miller Effect 12 2.4 Terminology 14 2.5 Related Work on Crosstalk Minimization 15 2.6 Problem Formulation 18 Chapter 3 Algorithm 21 3.1 Algorithm Overview 21 3.2 SoC Architecture 22 3.3 Wrapper Algorithm 24 3.3.1 Objective 24 3.3.2 Total Crosstalk Induced on Bus 25 3.3.3 The Minimum Hamiltonian Path 28 3.4 Further Discussion 31 3.4.1 Data Types 31 3.4.2 Permutation Transmission Mechanism 31 3.4.3 Tradeoff between Overhead and Area 33 Chapter 4 Experimental Results 35 4.1 Results 35 4.2 Justification 48 Chapter 5 Conclusions and Future Work 51 Bibliography 5