針對縮短錯誤狀態路徑的方法

Abstract

隋著半導體積體電路科技的進步，許多的方法被提出來確保越來越複雜的電路正確性。在組合邏輯電路部分，電路驗證可藉由測試樣品自動產生器(ATPG)和等效檢驗(Equivalence Checking)來完成。而在循序邏輯電路部分，儘管有許多方法被提出，但是大部分的方法在處理大型電路時都不實用，因為循序邏輯電路的狀態數往往是隨著狀態暫存器成指數次方成長。所以如何在短時間內快速地測試循序邏輯電路是一個越來越重要的客題。 在這篇論文中，我們提出一個有效的方法在循序邏輯電路中縮短錯誤狀態路徑的方法，它可以在短時間內找到一條較短的錯誤狀態路徑而縮短電路模擬(simulations)的時間。在第一個階段，先介紹一種有效率的方法來消除穿越重覆的狀態;而在第二階段，我們修改傳統用在象徵模型檢驗(symbolic model checking)的影像計算(image computation)建立一個連接的網路來連接各個狀態，然後應用Dijkstra的最短路徑演算法來找出最短的的錯誤路徑。實驗結果顯示對於大部分的電路，錯誤路徑可以在短時間內被找出來，而使用的記憶體也很合理。此外，錯誤路徑對應的輸入輸出也可以被自動地產生。為了方便性我們稱之為SET演算法。

The integrated circuit technology, based upon the use of semiconductor materials, has progressed tremendously. In order to ensure the correctness of larger and larger designs, several techniques were proposed. In combinational part, circuit verification can be done by ATPG and equivalence checking. In sequential part, in spite of many novel approaches has been proposed, most of those are difficult to deal with larger and larger modern circuit designs, because the number of states grows exponentially with the number of state registers. Hence, how to verify sequential circuits in a short time is a more and more important topic. In this thesis, we present a technique for shortening the error trace of sequential circuits, which can find out new short error traces and decrease the simulation time. In phase 1, we introduce an efficient approach to eliminate the duplicate state traversal on the error trace. In phase 2, we modify the traditional image computation method, popularly used in symbolic model checking, to build the connective network between states, and apply Dijkstra's shortest path algorithm to find out the shortest error trace of it. The experimental results show that not only the shorter error trace can hugely be reduced in a short time for most synchronous circuits, but also the memory requirement is quite reasonable. Moreover, the corresponding input/output test patterns can be automatically generated at the same time. For the sake of convenience, we call it SET algorithm.