臺灣博碩士論文加值系統

中文論文摘要
在現今積體電路的設計上，因為IC晶片的各項功能持續的增加，對於電路的功能性和時脈驗證顯得相當重要。在電路的模擬中，會產生一個與電路模擬相關的信號波形資料檔以供電路設計者在模擬結束後，透過波形軟體觀看信號波形加以除錯。然而，在現今的電路設計中，因為電路的複雜度和模擬時脈的增加，產生的波形檔很容易就佔據相當大的硬碟空間。
Cadence公司所定義的Value Change Dump檔案格式為這種波形檔建立了一個清晰的標準，使得各種公司開發的模擬器可以產生標準的VCD波形檔供設計者除錯。這篇論文中描述如何以VCD格式的波形資料檔為標的進行壓縮，最後產生一個較小的波形檔儲存在硬碟空間中。如我們所知，一些著名的壓縮技巧當然可以將波形檔壓縮的更小，然而在壓縮的同時也會需要過多的CPU執行時間；我們嘗試從電路設計者的設計模組中，在電路編譯時找出一些資訊來引導這些波形資料的壓縮方法。
在一個電路訊號的轉態中，在波形檔裡面要記錄的是發生的時間和其新值，我們試著對每個訊號把這兩個值（時間，新值）依照產生的順序分別儲存，並對個別區塊套用不同的壓縮方法；對於訊號的時間區塊中，我們主要是根據擷取於電路設計模組的資料對各個訊號產生一個”預測信號轉態生成基準（transition generator base）”，加以消弭各訊號的產生記錄，達到資料減少的目的。對於訊號的新值區塊中，我們著重於記錄該訊號據以生成的行為，而非生成後的新值，以達到壓縮的目的。經過實際以程式執行的結果，我們根據自己設計的電路和其對應的波形資料VCD檔加以壓縮，約略可以達到20%~50%的壓縮比率，這個輸出經過壓縮後的波形資料檔，可在經由一些非失真的壓縮程式處理之後，達到更加的壓縮率。

Abstract
Among VLSI circuit design, functional verification has become an important part due to rapid extension of circuits functionalities in many consumer and industry products. During circuit simulation, a very large trace file is written,
containing value-changes for every node in the design, or a subsystem within the design. Upon completion, the designer could watch the entire simulation history through a waveform tool to achieve the verification tasks.
Verilog's VCD file format has created a competitive market for waveform tools, which greatly improve the quality. However, the waveform data in VCD file format is too large. Some common compression algorithms may be used to decrease the file size of a waveform database, but they also consume a significant amount of computation power at the same time.
Here we adopt a new idea to make use of the properities of waveform data. By exploiting the HDL source codes in compile time, we try to find out hints to guide the compression. A file, which is named signal dependency file, could be created
to contain signal dependency rules among the source codes in circuit designes. "Time-value separation" is the key idea in our compression techniques. All signals transitions are separated into time sections and value sections in transition order. Then we could implement our compression ideas in each section separately. And of course, on decoompression tasks, we have to restore and merge these two parts in original transition order. In time section, our idea is based on some prediction strategies; in value section, our main idea is to replace the signal value by the corresponding behavior function for this signal to apply to. After our experiment processing, we could almost achieve 50% to 20% compression ratio comparing to the size of target VCD format waveform database.

Contents
Abstract i
List of Figures v
Chapter 1 Introduction 1
Chapter 2 Value Change Dump File Format 5
Chapter 3 Compression Techniques 11
3.1 Time-Value Separation . . . . . . . . . . . . . . . . . 12
3.2 Value Compression Techniques . . . . . . . . . . . . . . 13
3.2.1 Pattern Matching . . . . . . . . . . . . . . . . . . . 13
3.2.2 Strength Reduction . . . . . . . . . . . . . . . . . . 15
3.2.3 Cross Signal Strength Reduction . . . . . . . . . . .. 17
3.3 Time Compression Techniques . . . . . . . . . . . . . .. 22
3.3.1 Transition Estimation . . . . . . . . . . . . . .. . . 23
3.3.2 Time Value Transformation . . . . . . . . . . . . . .. 32
Chapter 4 Experimental Results 35
4.1 Dependency File Format . . . . . . . . . . . . . . . . 36
4.2 Output File format. . . . . . . . . . . . . . . . . . 38
4.3 Compression. . . . . . . . . . . . . . . . . . . . . 42
4.4 Discussion. . . . . . . . . . . . . . . . . . . . .. .45
Chapter 5 Conclusion 48
Bibliography 50

1. Edwin Naroska , "Waveform compression technical report" , Computer Engineering Institute , Dortmund University , Germany.
2. Joshua Marantz,"Enhanced Visibility and Performance in Functional Verification by Reconstruction", DAC 1998 , pp 164-169.
3. "IEEE Standard VHDL Language Reference Manual"
IEEE Std 1076-1993, IEEE Standards, ISBN 1-55937-376-8, 1994
4. Cadence Design Systems Inc., "Verilog-XL Reference Manual",
Version 2.3, 1995.
5. Khalid Sayood, "Introduction to Data Compression", 2nd ed. , pp 308-335, ISBN 1-55860-558-4.
6. N.S. Jayant and P. Noll , "Digital Coding of Waveforms", Englewood Cliffs, NJ: Prentice Hall, 1984.
7. D. Kirovski ,M . Potkonjak , "A Quantitative Approach to Functional Debugging ", ICCAD 1997 , pp 170-173.
8. Jacob Ziv , Abraham Lempel , "A Universal Algorithm for Sequential Data Compression" , IEEE 1977 .
9. Jacob Ziv , Abraham Lempel , "Compression of Individual Sequences via Variable-Rate Coding" , IEEE 1978 .
10. Terry Welch , "A Technique for High-Performance Data Compression", IEEE 1984 .
11. John R. Levine , Tony Mason , Doug Brown ,"Lex & yacc" ,
O'Reilly & Associates, Inc. ,1992 .