Local Grouping Algorithm for Synthesizing Low-Cost Parameter Extractor of Low-Power Pre-computation-Based Content Addressable Memory

因為內容可定址記憶體的高速特性，使得它在許多需要高速的設備中扮演著重要的角色，但是它的耗電量也非常的高。在這篇論文中我們提出一個合成演算法用來合成低功率預先計算型內容可定址記憶體上的參數擷取器，使得資料能夠被均勻的映射到每個參數，而且硬體的成本也較少。此外我們也提出一個方法去減少當一些資料在區塊中大部分是相同時，對參數擷取器所帶來的影響。實驗結果顯示，當和Gate-Block Selection演算法比較時，我們的方法可以減少58.88%的功率消耗，也可以省下0.53%的CMOS電晶體數目。如果用我們提出的捨去及交錯法去改善Gate-Block Selection演算法時，我們的方法仍然可以減少13%的功率消耗。Content addressable memory (CAM) plays an important role on the performance of some devices due to the high speed of CAM. But the power consumption of CAM is also high. In this work, we propose a synthesis algorithm to synthesize the parameter extractor for low-power pre-computation-base CAM (PB-CAM) such that the data can be mapped to parameters uniformly and the cost of the parameter extractor can also be lower. Moreover, we also propose a method to reduce the impact on mapping data to parameters when most data are identical in some data blocks. In the experimental results, the average reduction of the power consumption can achieve 58.88% and the number of CMOS transistors can save 0.53% when compared with Gate-Block Selection algorithm. If the Gate-Block Selection algorithm is also enhanced by our proposed discard and interlaced method (DAI method) then the power consumption can still be reduced by 13%.口試委員會審定書 i謝 ii要 iiibstract ivontents vist of Figures viiist of Tables ixhapter 1 Introduction 1.1 Power Dissipation in CMOS VLSI Circuit 1.1.1 Switching Power Dissipation 2.1.2 Short-Circuit Power Dissipation 2.1.3 Leakage Power Dissipation 3.2 Concept of Content Addressable Memory 4.2.1 Content Addressable Memory 4.2.2 Applications of Content Addressable Memory 5.2.3 CAM Cell 6.2.4 Write Operation of a CAM Cell 7.2.5 Read Operation of a CAM Cell 9.2.6 Search Operation of a CAM Cell 10.2.7 Match Line Structure 11hapter 2 Related Work 14.1 Selective Pre-charge Scheme 16.2 Pre-computation Scheme 17.2.1 Ones Count Scheme 18.2.2 Block-XOR Scheme 21.2.3 Gate-Block Selection Algorithm 22.3 Motivation and Objective 25hapter 3 Proposed Approach 26.1 The Benefit of Distributing the Data Uniformly 26.2 Local Grouping Algorithm 28.2.1 Definition of the Variables 28.2.2 Top Level of Local Grouping Algorithm 29.2.3 Grouping Function 31.2.4 Find Gate Function 36.2.5 Demonstration of Local Grouping Algorithm 40.2.6 Time Complexity of Local Grouping Algorithm 43.3 Discard and Interlaced Method 45hapter 4 Experimental Results 48.1 Experimental Environment 48.2 Results 52.2.1 Experimental Results of Random Data 52.2.2 Experimental Results of MiBench 56hapter 5 Conclusion 63eferences 6