Abstraction Techniques for Design Depipelining

在利用事件驅動的方法來進行模擬的時候，管道設計中的同步控制電路反而是拖慢模擬速度的信號。因此，設計去管道化的技術在簡化管道設計中的控制電路中扮演著很重要的角色。然而，為了特定的規格或性質而實作的控制圖，控制圖上時常發生狀態爆炸。因此，這樣的技術並不適合驗證超純量暫存器轉移層次設計。這裡有各種方式去解決狀態爆炸的問題，例如分解和抽象化技術都是可行的解決方案。以抽象化技術而言，將具體的路徑映射到抽象路徑可以有效減少狀態的數量。因此，我們提出了一個設計去管道化的抽象化技術，這樣的技術將會自動產生一個網表，然後設計者就可以在這個網表上模擬電路運作。雖然，這個網表的輸出量和原本的管道化設計不同，但我們確保這兩個設計的模擬輸出結果將會是相同的。為了提高模擬的效率，我們的演算法尋找有限狀態機與使用抽象化技術。根據實驗結果，這樣的演算法能有效的提高模擬速度於管道化設計。與迴圈展開的技術做比較，我們的模擬時間將會大幅降低。For simulation-based verification, control circuits for synchronization in pipelined design are tedious, especially for the event-driven simulation. Therefore, depipelining technique plays an important role in the control logic simplification of pipelined design. However, it would cause state explosion due to the need of formulating the implementation with respect to a certain specification or property. Consequently, it is not scalable for current superscalar RTL design. To conquer these problems, the techniques utilizing various strategies such as decomposition and abstraction might be the solutions. The abstraction technique that maps concrete paths to abstract ones attempts to reduce the number of states. Therefore, we propose a design depipelining algorithm which computes approximate abstraction of pipelined design. Moreover, a netlist will be generated in our approach. Although the throughput of the netlist is different from the original design, we ensure that the simulation outputs of these two designs are identical. In addition, to enhance the efficiency, finite-state machine extraction and abstraction techniques are applied to our work. The experimental results show that our algorithm is effective in increasing simulation-speed of pipelined design. When compared to the loop-unrolling technique, the simulation of our work is much faster.誌謝 i 中文摘要 i ABSTRACT iii CONTENTS iv LIST OF FIGURES vi LIST OF TABLES viii Chapter 1 Introduction 1 1.1 Related Works 2 1.2 Contributions of the Thesis 3 1.3 Organization of the Thesis 4 Chapter 2 Preliminaries 5 2.1 Control Flow Graph 5 2.2 Finite-state Machine 6 2.3 Pipelined Design 6 2.4 Boolean Satisfiability 7 Chapter 3 Main Algorithm 8 3.1 Pipeline Control Flow Graph Extraction 9 3.2 Cared Control Signal Candidates Search 11 3.3 Dependency Graph Construction 13 3.4 State Reduction - FSM Extraction 15 3.5 Pipeline Control Flow Graph Construction 16 Chapter 4 Code Generation 19 4.1 Pipeline Control Flow Graph Abstraction 21 4.2 Datapath Generation 23 4.3 Control Logic Generation 26 4.4 Interface Implementation 28 4.5 Design Simplification 29 Chapter 5 Implementation Issues 31 Chapter 6 Experimental Results 32 6.1 Case Study - Arithmetic Pipelined Design 33 6.2 Arithmetic Pipelined Design on Pipeline Depth 43 6.3 The Comparison on Pattern Diversity 46 6.4 Design Simplification Analysis 49 Chapter 7 Conclusions and Future Works 50 REFERENCE 5