使⽤模式匹配及對稱性解析單位元件功能

Reconstructing Cell Functions from Sequential Truth Tables Using Pattern Matching and Symmetries

卓旻科(Ming-Ko CHO)

指導教授 ： 郭斯彥

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2016年)

https://doi.org/10.6342/NTU201601621

摘要

未知值(Xs)可能在存在於未初始化暫存器器或是未通電的區塊內。
此種未知值可能會造成X-bugs，X悲觀或X樂觀。
當我們要解決這些X-bugs時，我們必須從暫存器的輸入端追溯回前級的元件。
透過解析元件功的輸入功能，我們可以得到元件的額外資訊，進而篩選出我們進一步追溯下去的輸入端，可以有效減少搜尋的空間。
這篇論文提出了一個分析序向使用者定義元件(sequential UDPs)的方法，其中使用到模式匹配及對稱性的技巧。
我們在商業軟體上的實驗結果顯示出此方法十分有效且快速。

關鍵字

未知值 ； 閘位準邏輯模擬 ； 序向使用者定義單元 ； 對稱性

並列摘要

Unknown value (Xs) may exist in a design due to uninitialized registers or blocks that are powered down.
Such Xs may cause X bugs known as X-pessimism and X-optimism.
When we are solving X-pessimism problems, we have to trace along the fan-ins of a register's input.
By reconstructing cell functions,
the procedure above will get extra information of the cells encountered and thus can reduce its search space.
To analyze the cell properly and provide the exact cell functions information,
we proposed a methodology including pattern matching and symmetry detecting techniques which reveals the functional information about SUDP inputs.
Our experimental results on commercial designs show that the proposed method is effective and efficient.

並列關鍵字

X-pessimism ； Gate-level logic simulation ； sequential user-defined primitives ； graph symmetry

參考文獻

[1] Ieee standard for verilog hardware description language. IEEE Std 1364-2005 (Revi- sion of IEEE Std 1364-2001), page 108, 2006.

[3] T. Junttila and P. Kaski. Engineering an efficient canonical labeling tool for large and sparse graphs. In D. Applegate, G. S. Brodal, D. Panario, and R. Sedgewick, edi- tors, Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics, pages 135–149. SIAM, 2007.

[2] K. H. Chang and C. Browy. Improving gate-level simulation accuracy when unknowns exist. In Design Automation Conference (DAC), 2012 49th ACM/EDAC/IEEE, pages 936–940, June 2012.