基於錯誤效應驅動決策樹以提高自動測試圖樣生成演算法之效能以及其實作範例

D-Drive History Tree to Enhance ATPG Efficiency and its Implementation Examples

陳敬元(Ching-Yuan Chen)

指導教授 ： 黃俊郎

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

https://doi.org/10.6342/NTU201704159

摘要

西元一九六六年，自動化測試圖樣產生演算法的始祖—錯誤效應演算法（D-Algorithm）首次發表。自此，大量的研究成果隨之而來，並在演算法加速以及產生圖樣品質上取得巨大的成果。即便如此，在演算法加速以及測試品質上仍存有許多進步空間 。
我們提出錯誤效應驅動決策樹以取代傳統算法中的決策樹。其紀錄每一次錯誤驅動(D-drive)程序中候選以及選中以傳遞錯誤效應之邏輯閘。該決策樹有助於減少測試圖樣產生過程中衍生多餘的邏輯值指定（Redundant Signal Assignment）,並提供更精細錯誤驅動策略的可能性。這意味著更好的算法加速以及測試圖樣品質。於本論文中，我們提供兩個基於錯誤效應驅動決策樹的實作範例—深度優先 （DF-PODEM）以及錯誤效應傳播最大化之路徑導向決策演算法（PM-PODEM）。前者達到最高32%之演算法加速，而後者達到最高11%之測試圖樣壓縮率。根據實驗結果，兩個測試圖樣產生演算法皆提供更好的算法加速、測試涵蓋率（Test Coverage）、以及測試圖樣壓縮率。
值得注意的是，錯誤效應驅動決策樹相當易於整合至現有各式自動化測試圖樣系統，同時也易於擴展以達到更好的算法加速以及針對各式品質指標的測試圖樣品質優化。

關鍵字

決策樹 ； 錯誤驅動 ； 回溯修正 ； 測試壓縮 ； 路徑導向決策演算法 ； 自動化測試圖樣產生

並列摘要

Since the first publication of D-algorithm (DALG) in 1966, lots of following works on automatic test pattern generation (ATPG) algorithm have been proposed to achieve higher speed-up and quality of generated test set. Though big progress has been made through decades, it still has lots of room for improvement in speed-up and generated test quality of ATPG.
In this thesis, we propose D-drive History Tree (D-Tree) to replace the assignment decision tree in the conventional ATPG, which keeping track of all the candidates and the chosen gate(s) to propagate fault effect for each D-drive process. This D-tree helps eliminate the possibility of producing redundant signal assignments (RSAs) and makes more sophistical D-drive strategies possible, thus enhance the ATPG efficiency and/or the test quality. Two implementation examples based on PODEM algorithm—Depth-First PODEM (DF-PODEM) and Propagation Maximization PODEM (PM-PODEM) are proposed to show its power to immediate boost both performance and/or pattern quality of ATPG. DF-PODEM turns out to achieve up to 32% speed-up, along with higher fault coverage and/or compacted test length, on ISCAS'89 and ITC'99 benchmark circuits. PM-PODEM achieve up to 11% shorter test length, along with higher fault coverage and/or lower run-time, on the same set of circuits under test (CUT).
Also, as to be shown, D-tree could not only easily be integrated with pre-existed ATPG-improving strategies, but also quite flexible thus could easily be extended to gain even higher speed-up and higher quality specifically for different quality metrics.

並列關鍵字

decision tree ； D-drive ； backtrack ； test compaction ； PODEM ； test pattern generation

參考文獻

J. P. Roth, “Diagnosis of Automata Failures: A Calculus and a Method,” IBM Journal of Research and Development, vol. 10, no. 4, pp. 278–291, July 1966.

P. Goel, "An implicit enumeration algorithm to generate tests for combinational logic circuits", IEEE Trans. Comput., vol. C-30, pp. 215-222, Mar. 1981.

H. Fujiwara and T. Shimono, "On the Acceleration of Test Generation Algorithms," in IEEE Transactions on Computers, vol. C-32, no. 12, pp. 1137-1144, Dec. 1983.

M. H. Schulz, E. Trischler, and T. M. Sarfert, "SOCRATES: A highly efficient automatic test pattern generation system," IEEE Transactions on Computer-Aided Design, vol. 7, no. I, pp. 126-137, January 1988.

U. Mahlstedt, T. Grüning, C. Özcan, and W. Daehn, “CONTEST: A Fast ATPG Tool for Very Large Combinational Circuits,” International Conference on Computer-Aided Design, pp. 222-225, 1990.