 |
|
|
|
以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數：42 、訪客IP：3.148.106.0
姓名 胡詠鈞(Yong-Jyun Hu) 查詢紙本館藏 畢業系所 電機工程學系 論文名稱 內容定址記憶體之三維架構探索與測試
(Three-Dimensional Architecture Exploration and Testing of Content Addressable Memories)相關論文 檔案 [Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
摘要(中) 三維積體電路之晶片設計 (3-D IC design) 技術，已被公認是一項可行的晶片設計技術。相較於現今二維積體電路，三維積體電路的優點在於小外觀 (small form factor，SFF)、高效能、高功能性、及低功率消耗。三維積體電路技術非常適合應用於具有規律特性的記憶體電路，這其中就包括內容定址記憶體 (content addressable memory，CAM)。內容定址記憶體目前已廣泛地應用在數位系統中，包括網路應用、密碼學 (cryptography)、資料壓縮、及快取記憶體等。如何提升內容定址記憶體的效能及降低其功率消耗是設計內容定址記憶體時的兩大關鍵。內容定址記憶體的最小單元包含了儲存單元和比較器兩部份，以致於它可以實現其平行比對 (parallel comparison)的功能，但也造成它的面積和複雜度比一般的靜態隨機存取記憶體 (SRAM) 還要高很多。因此，當設計一個大儲存容量的內容定址記憶體，可利用三維積體電路的技術來進一步提升其速度並降低其能量消耗及面積腳位。
在論文的第一部份提出了三種擁有三維架構的內容定址記憶體和優先權位址編碼器 (priority address encoder，PAE)，分別為搜尋線分割 (searchline-partitioned) 三維內容定址記憶體架構、命中線分割 (matchline-partitioned) 三維內容定址記憶體架構、及搜尋線-命中線混合分割(searchline-matchline hybrid-partitioned) 三維內容定址記憶體架構 (以下分別簡稱SPCAM3D、MPCAM3D、及SMHPCAM3D)。實驗結果顯示，假設在搜尋線大小為1024單位、雙層晶粒 (die) 堆疊的情況下，SPCAM3D架構可使內容定址記憶體的搜尋時間比二維架構時降低29.13%；而假設在命中線大小為128-位元、雙層晶粒堆疊的情況下，MPCAM3D架構可使內容定址記憶體的搜尋時間比二維架構時降低23.21%；而假設在記憶體大小為1024x128-位元、四層晶粒堆疊的情況下，SMHPCAM3D架構可使內容定址記憶體的速度比二維架構時提升最多66.78%。除此之外，我們也提出了兩種應用了前看 (lookahead) 及折疊 (folding) 技術的三維架構優先權位址編碼器，且實驗結果顯示在大小為1024-128位元、雙層晶粒堆疊的情況下，相較於傳統的二維架構之優先權位址編碼器，可分別降低45.78%和42.35%的關鍵延遲時間 (critical delay time)。最後，我們提出可重新裝配 (reconfigurable) 之內容定址記憶體架構，在單一顆晶粒時可實現二元內容定址記憶體 (binary CAM) 之功能；而當複數顆的晶粒運用三維技術堆疊之後，則可實現三元內容定址記憶體 (ternary CAM) 之功能。
論文的第二部份則針對擁有非對稱性單位結構 (asymmetric cell structure) 之三元內容定址記憶體，我們定義並模組化它在執行比較 (Compare) 動作時可能發生的比較錯誤 (comparison fault)。為了有效測得所定義的比較錯誤，我們提出兩個類行軍式 (march-like) 測試演算法，分別為TACHit和TACPAE。當測試一個大小為NxB-位元之非對稱性且只擁有擊中結果輸出器 (Hit output) 的三元內容定址記憶體時，可使用TACHit測試演算法進行測試。此時需要執行8N次寫入 (Write) 動作及3N+2B次比較動作來測得100%所定義之比較錯誤。而當測試一個大小為NxB-位元之非對稱性且擁有擊中結果輸出器和優先權位址編碼器的三元內容定址記憶體時，則可執行TACPAE測試演算法進行測試。此時只需要執行4N次寫入動作及3N+2B次比對動作來測得100%所定義之比較錯誤。
論文的最後部份則針對SPCAM3D與MPCAM3D兩個三維內容定址記憶體架構提出測試方案。兩種內建自我測試 (built-in self-test，BIST) 電路加上平行測試介面 (parallel test scheme) 分別被提出。兩種測試方案可配合二維內容定址記憶體的類行軍式測試演算法，來更有效率地測試前述SPCAM3D與MPCAM3D兩種三維內容定址記憶體架構中的比較錯誤。進一步分析及比較的結果可得知，由於平行測試介面的關係，兩種測試方案可以有效地降低測試複雜度。
摘要(英) Three-dimensional (3-D) integrated chip (IC) design technology is now widely acknowledged as one of the future chip design technologies. A 3-D IC has many benefits over a conventional 2-D IC, such as small form factor, high functionality, high performance, and low power consumption. Due to the regularity of a memory circuit, it is a very good candidate for 3-D technology. Content addressable memories (CAMs) are widely used in digital systems, such as networking, cryptography, compression, cache memory, etc. How to improve the performance and reduce the power of the CAM are two of key design issues. On the other hand, the area of a CAM cell is much larger than that of an SRAM cell because of that a CAM cell consists of a storage element and a comparator for executing parallel comparison. Therefore, if a large-capacity CAM is needed, then the footprint of the CAM is very large. 3-D integration technology can be used to reduce the power and the footprint of a large-capacity CAM.
In the first part of this thesis, three 3-D architectures for the CAM and priority address encoder (PAE) are proposed. The first is the Searchline-Partitioned 3-D CAM architecture (SPCAM3D), and the second is the Matchline-Partitioned 3-D CAM (MPCAM3D) architecture, and the third is the Searchline-Matchline Hybrid-Partitioned 3-D CAM (SMHPCAM3D). Moreover, a 3-D PAE with lookahead and folding techniques is introduced. Compared with the 2-D CAM architecture, simulation results show that the proposed SPCAM3D architecture with two 3-D layers gets about 29.13% improvement on search time when the number of words of the CAM is 1K; the MPCAM3D architecture with two 3-D layers gets about 23.21% improvement on search time when the word width of the CAM is 128; and the SMHPCAM3D architecture with four 3-D layers gets 66.78% performance improvement when the configuration of the CAM is 1K×128 bits. For the proposed 3-D PAE and 3-D folding PAE with two 3-D layers, simulation results show that they can provide 45.78% and 42.35% performance improvement, respectively, on critical delay time in comparison with the 2-D PAE if the size of PAE is 1K-bit. Finally, a reconfigurable CAM architecture for realizing a binary CAM or ternary TCAM is proposed. The reconfigurable CAM architecture can be implemented in a die as a binary CAM. On the other hand, one can stack multiple reconfigure CAM dies to realize a ternary CAM.
In the second part of this thesis, the comparison faults of ternary CAMs with asymmetric cells are defined first. Then, two march-like test algorithms are proposed to cover the defined comparison faults. The first test algorithm TACHit requires 8N Write operations and (3N+2B) Compare operations to detect 100% comparison faults for an N×B-bit TCAM with asymmetric cells and Hit output only. The second test algorithm TACHit requires 4N Write operations and (3N+2B) Compare operations to detect 100% comparison faults for an N×B-bit TCAM with asymmetric cells and Hit and PAE outputs.
In the last part of this thesis, test procedures for CAMs with the SPCAM3D and the MPCAM3D architectures are presented. A built-in self-test (BIST) scheme is proposed to test CAMs with SPCAM3D architecture. On the other hand, a BIST scheme is proposed to test CAMs with MPCAM3D architecture. Both the BIST schemes for 3-D CAMs can generate the March-like test algorithms for 2-D CAMs. The experimental results shows that the test time of 3-D BISTs for SPCAM3D and MPCAM3D are only 51.21% and 79.07%, respectively, of the test time of 2-D BIST.
關鍵字(中) ★ 三維架構
★ 三維積體電路
★ 內容定址記憶體
★ 測試演算法
★ 記憶體測試
★ 錯誤模型
★ 可靠性設計關鍵字(英) ★ 3-D IC
★ content addressable memory
★ test algorithm
★ fault model
★ memory testing
★ design-for-reliability論文目次 1 Introduction 1
1.1 Three-Dimensional (3-D) Integrated Chip . . . . . . . . . . . . . . . . . . . . 1
1.2 Content Addressable Memories . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Ternary Content Addressable Memory . . . . . . . . . . . . . . . . . . . . . 2
1.3.1 Symmetric TCAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.2 Asymmetric TCAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Priority Address Encoder of CAM . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 3-D Integration Technology . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Architecture Exploration of 3-D CAM 8
2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Searchline-Partitioned 3-D CAM . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Matchline-Partitioned 3-D CAM . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Searchline-Matchline Hybrid-Partitioned 3-D CAM . . . . . . . . . . . . . . 15
2.5 3-D Priority Address Encoder with Lookahead and Folding Technique . . . . 17
2.5.1 PAE with Lookahead Technique . . . . . . . . . . . . . . . . . . . . . 18
2.5.2 PAE with Folding Technique . . . . . . . . . . . . . . . . . . . . . . . 20
2.5.3 3-D Folding PAE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.6 Experimental Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . 24
2.6.1 MPCAM3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.6.2 SPCAM3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.6.3 3-D PAE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.6.4 SMHPCAM3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.6.5 3-D Folding PAE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.7 Reconfigurable CAM Architecture . . . . . . . . . . . . . . . . . . . . . . . . 32
2.7.1 3-D TCAM Matchline Structure with Left- and Right-Cell Separated 32
2.7.2 Reconfigurable CAM Architecture . . . . . . . . . . . . . . . . . . . . 35
3 Modeling and Testing Comparison Faults of TCAMs with Asymmetric Cell 41
3.1 Previous Works and Motivation . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2 Cell Level Fault Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.2.1 Definition of Electrical Defects . . . . . . . . . . . . . . . . . . . . . . 42
3.2.2 Hspice Model for Verification . . . . . . . . . . . . . . . . . . . . . . 43
3.2.3 Comparison Faults in Asymmetric TCAM Cells . . . . . . . . . . . . 43
3.2.4 The Loading Effect on Comparison Faults . . . . . . . . . . . . . . . 50
3.3 Testing Comparison Faults of TCAMs with Asymmetric Cell . . . . . . . . . 53
3.3.1 Test for TCAMs with Hit Output Only . . . . . . . . . . . . . . . . . 53
3.3.2 Test for TCAMs with Hit and PAE Outputs . . . . . . . . . . . . . . 56
3.3.3 Analysis and Comparison . . . . . . . . . . . . . . . . . . . . . . . . 58
4 Testing 3-D CAMs with Comparison Faults 61
4.1 Test Flow for 3-D ICs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2 Testing Comparison Faults in 2-D CAMs . . . . . . . . . . . . . . . . . . . . 61
4.3 Parallel Test Scheme for Searchline-Partitioned 3-D CAMs . . . . . . . . . . 62
4.4 Parallel Test Scheme for Matchline-Partitioned 3-D CAMs . . . . . . . . . . 65
4.5 Pre-bond Test for 3-D CAMs . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.5.1 Pre-bond Test for MPCAM3D . . . . . . . . . . . . . . . . . . . . . . 68
4.5.2 Pre-bond Test for SPCAM3D . . . . . . . . . . . . . . . . . . . . . . . 69
4.6 Hardware Realization and Experimental Results . . . . . . . . . . . . . . . . 70
4.6.1 Design of the TCAM BIST Circuit . . . . . . . . . . . . . . . . . . . 71
4.6.2 Experimental Results of Hardware Implementation . . . . . . . . . . 74
5 Conclusions and Future Work 76
Bibliography 78
參考文獻 [1] Y.-J. Hu, J.-F. Li, and Y.-J. Huang, “3-D content addressable memory architectures,” in Proc. IEEE Int’l Workshop on Memory Technology, Design and Testing (MTDT), Hsinchu, Sep. 2009, pp. 59–64.
[2] C.-H. Huang, J.-S. Wang, and Y.-C. Huang, “Design of high-performance CMOS priority encoders and incrementer/decrementers using multilevel lookahead and multilevel folding techniques,” IEEE Jour. of Solid-State Circuits, vol. 37, no. 1, pp. 63–76, Jan. 2002.
[3] J.-Q. Lu, “3-D hyperintegration and packaging technologies for micronano systems,” Proceedings of the IEEE, vol. 97, no. 1, pp. 18–30, Jan. 2009.
[4] M. Koyanagi, T. Fukushima, and T. Tanaka, “High-density through silicon vias for 3-D LSIs,” Proceedings of the IEEE, vol. 97, no. 1, pp. 49–59, Jan. 2009.
[5] V. F. Pavlidis and E. G. Friedman, “Interconnect-based design methodologies for three-dimensional
integrated circuits,” Proceedings of the IEEE, vol. 97, no. 1, pp. 123–140, Jan. 2009.
[6] P. Marchal, B. Bougard, G. Katti, M. Stucchi, W. Dehaene, A. Papanikolaou, D. Verkest, B. Swinnen, and E. Beyne, “3-D technology assessment: path-finding the technology/design sweet-spot,” Proceedings of the IEEE, vol. 97, no. 1, p. 96106, Jan. 2009.
[7] T. Zhang, R. Micheloni, G. Zhang, Z. R. Huang, and J. J.-Q. Lu, “3-D data storage power delivery, and RF/optical transceiver — case studies of 3-D integration from system design perspectives,” Proceedings of the IEEE, vol. 97, no. 1, pp. 161–174, Jan. 2009.
[8] Y. Xie, G. H. Loh, B. Black, and K. Bersnstein, “Design space exploration for 3D architectures,” ACM Journal on Emerging Technologies in Computing Systems, vol. 2, no. 2, pp. 65–103, Apr. 2006.
[9] P. Jacob, A. Zia, O. Erdogan, P. M. Belemjian, J.-W. Kim, M. Chu, R. P. Kraft, J. F. Mcdonald, and K. Bernstein, “Mitigating memory wall effects in high-clock-rate and multicore CMOS 3-D processor memory stacks,” Proceedings of the IEEE, vol. 97, no. 1, pp. 108–122, Jan. 2009.
[10] V. Ravikumar, R. N. Mahapatra, and L. N. Bhuyan, “EaseCAM: an energy and storage efficient TCAM-based router architecture for IP lookup,” IEEE Trans. on Computers, vol. 54, no. 5, pp. 521–533, May 2005.
[11] M.-J. Akhbarizadeh, M. Nourani, and C. D. Cantrell, “Prefix segregation scheme for a TCAM-based IP forwarding engine,” IEEE Micro, vol. 25, no. 4, pp. 48–63, Aug. 2005.
[12] H. Che, Z. Wang, K. Zheng, and B. Liu, “DRES: dynamic range encoding scheme for TCAM coprocessors,” IEEE Trans. on Computers, vol. 57, no. 6, pp. 1–14, Jun. 2008.
[13] S. R. Ramirez-Chavez, “Encoding don’t cares in static and dynamic content addressable memories,” IEEE Trans. on Circuits and Systems II: Analog and Digital Signal Processing, vol. 39, no. 8, pp. 575–578, Aug. 1992.
[14] K. Pagiamtzis and A. Sheikholeslami, “Content-addressable memory (CAM) circuits and architectures: a tutorial and survey,” IEEE Jour. of Solid-State Circuits, vol. 41, no. 3, pp. 712–727, Mar. 2006.
[15] V. Lines, A. Ahmed, P. Ma, S. Ma, R. McKenzie, H.-S. Kim, and C. Mar, “66MHz 2.3M ternary dynamic content addressable memory,” in Proc. IEEE Int’l Workshop on Memory Technology, Design and Testing (MTDT), San Jose, Aug. 2000, pp. 101–105.
[16] N. Weste and D. Harris, CMOS VLSI Design: A Circuits and Systems Perspective, 3rd ed. Reading, Massachusetts: Addison-Wesley, 2005.
[17] W.-C. Lo, S.-M. Chang, Y.-U. Chen, T.-Y. Kuo, H.-H. Chang, and Y.-C. Shih, “3D chip-to-chip stacking with through silicon interconnects,” in Proc. Int’l Symp. on VLSI Technology, Systems, and Applications (VLSI-TSA), Apr. 2007, pp. 72–73.
[18] D. Henri, X. Baillin, V. Lapras, M. Vaudaine, J. Quemper, N. Sillon, B. Dunne, C. Hernandez, and E. Vigier-Blanc, “Via first technology development based on high aspect ratio trenches filled with doped polysilicon,” in Proc. IEEE 57th Electron. Compon. Technol. Conf. (ECTC), June 2007, pp. 830–835.
[19] M. Dreiza, A. Yoshida, K. Ishibashi, and T. Maeda, “High density PoP (package-onpackage) and package stacking development,” in Proc. IEEE 57th Electron. Compon. Technol. conf. (ECTC), June 2007, pp. 1379–1402.
[20] W.-C. Lo, Y.-H. Chen, C.-T. Ko, and M.-G. Kao, “TSV and 3D wafer bonding technologies for advanced stacking system and application at ITRI,” in Symp. on VLSI Circuits, Digest of Technical Papers, June 2009, pp. 70–71.
[21] M. Motoyoshi, “Through-silicon via (TSV),” Proceedings of the IEEE, vol. 97, no. 1, pp. 43–48, Jan. 2009.
[22] J. M. Mulder, N. T. Quach, and M. J. Flynn, “An area model for on-chip memories and its application,” IEEE Jour. of Solid-State Circuits, vol. 26, no. 2, pp. 98–106, Feb. 1991.
[23] W. R. Davis, E. C. Oh, A. M. Sule, and P. D. Franzon, “Application exploration for 3-D integrated circuits: TCAM, FIFO, and FFT case studies,” IEEE Trans. on VLSI Systems, vol. 17, no. 4, pp. 496–506, Apr. 2009.
[24] T. Yamagata, M. Mihara, T. Hamamoto, Y. Murai, T. Kobayashi, M. Yamada, and H. Ozaki, “A 288-kb fully parallel content addressable memory using a stacked-capacitor cell structure,” IEEE Jour. of Solid-State Circuits, vol. 27, no. 12, pp. 1927–1933, Dec. 1992.
[25] J.-S. Wang and C.-H. Huang, “High-speed and low-power CMOS priority encoder,” IEEE Jour. of Solid-State Circuits, vol. 35, no. 10, pp. 1511–1514, Oct. 2000.
[26] J. G. Delgado-Frias and J. Nyathi, “A high-performance encoder with priority lookahead,” IEEE Trans. on Circuits and Systems I: Fundamental Theory and Applications, vol. 47, no. 9, pp. 1390–1393, Sept. 2000.
[27] W. W. Fung, “Low power circuits for multiple match resolution and detection in ternary CAMs,” Master Thesis, University of Waterloo, Ontario, Canada, Nov. 2004.
[28] M. Nourani, D. S. Vijayasarathi, and P. T. Balsara, “A reconfigurable CAM architecture for network search engines,” in Proc. IEEE Int’l Conf. on Computer Design (ICCD), San Jose, California, Oct. 2006, pp. 82–87.
[29] X. Yang, S. Sezer, J. McCanny, and D. Burns, “A versatile content addressable memory architecture,” in IEEE International SOC Conference, Hsinchu, Sept. 2007, pp. 215–218.
[30] S. Gupta and R. Gibson, “Methods and circuitry for built-in self-testing of content addressable memories,” R.O.C. Patent No. 6609222 B1, Aug. 2003.
[31] D. Wright and M. Sachdev, “Transistor-level fault analysis and test algorithm development for ternary dynamic content addressable memories,” in Proc. Int’l Test Conf. (ITC), Sep. 2003, pp. 39–47.
[32] N. Mohan, W. Fung, D.Wright, and M. Sachdev, “Design techniques and test methodology for low-power TCAMs,” IEEE Trans. on VLSI Systems, vol. 14, no. 6, pp. 573–586, June 2006.
[33] K.-J. Lee, C. Kim, S. Kim, U.-R. Cho, and H.-G. Byun, “Modeling and testing of faults in TCAMs,” in Proc. Asian Simulation Conference, Jeju Island, Oct. 2004, pp. 521–528.
[34] J.-F. Li, “Testing comparison faults of ternary CAMs based on comparison faults of binary CAMs,” in Proc. Asia and South Pacific Design Automation Conf. (ASP-DAC), Shanghai, Jan. 2005, pp. 65–70.
[35] ——, “Testing ternary content addressable memories using march-like tests,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 26, no. 5, pp. 919–931, May 2007.
[36] Y.-J. Huang and J.-F. Li, “Testing ternary content addressable memories with active neighborhood pattern sensitive faults,” IET Proc. Computers and Digital Technqiues, vol. 1, no. 3, pp. 246–255, May 2007.
[37] J.-F. Li, “Testing comparison faults of ternary content addressable memories with asymmetric cells,” in IEEE Asian Test Symp. (ATS), Beijing, Oct. 2007, pp. 495–500.
[38] A. Al-Ard and A. J. van de Goor, “Static and dynamic behavior of memory cell array spot defects in embedded drams,” IEEE Trans. on Computers, vol. 52, no. 3, pp. 293–309, Mar. 2003.
[39] K.-J. Lin and C.-W. Wu, “Testing content-addressable memories using functional fault models and March-like algorithms,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 19, no. 5, pp. 577–588, May 2000.
[40] J.-F. Li, R.-S. Tzeng, and C.-W. Wu, “Testing and diagnosis methodologies for embedded content addressable memories,” Jour. of Electronic Testing: Theory and Applications, vol. 19, no. 2, pp. 207–215, Apr. 2003.
[41] D. L. Lewis and H.-H. S. Lee, “Testing circuit-partitioned 3D IC designs,” in Proc. IEEE Computer Society Annual Symp., May 2009, pp. 139–144.
[42] C.-F. Wu, C.-T. Huang, and C.-W. Wu, “RAMSES: a fast memory fault simulator,” in Proc. IEEE Int’l Symp. on Defect and Fault Tolerance in VLSI Systems (DFT), Albuquerque, Nov. 1999, pp. 165–173.
[43] C.-F. Wu, C.-T. Huang, K.-L. Cheng, and C.-W. Wu, “Simulation-based test algorithm generation for random access memories,” in Proc. IEEE VLSI Test Symp. (VTS), Montreal, Apr. 2000, pp. 291–296.
指導教授 李進福(Jin-Fu Li) 審核日期 2010-5-27 推文 plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
網路書籤 Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit