分別在可決定性與不可決定性觀點下測試向量產生器在共享式記憶體系統上平行化技術之研究

隨著電路尺寸與錯誤模型複雜度的增大，測試向量產生所花費時間的重要性日益增加。多引線運算系統為此問題開啟一扇窗。但運算流程改變導致了測試向量膨脹的問題，而膨脹問題直接對應測試成本的提升。因此，如何在平行化測試向量產生器下又能同時抑制測試向量膨脹儼然成為極重要之課題。本論文分別在可決定性與不可決定性觀點下研究測試向量產生器在共享式記憶體系統上平行化之影響。在可決定性觀點下，為了產生不變的測試向量，高度相關的計算任務導致處理器產生過多的閒置。因此，開發重排程的演算法來節省運算資源，並達到有效的加速。而不可決定性觀點下，高度相關的計算順序將被打破以追求極致的加速效果，新的平行流程演算法被提出，用來抑制測試向量膨脹與實現更高的平行度。

關鍵字

測試向量產生器；平行化；共享式記憶體系統

並列摘要

Shared-memory systems enable parallel computing for Automatic Test Pattern Generation (ATPG). Although existing parallel ATPG can reach near-linear speedup, the problem of test inflation becomes a critical issue to its practicality. This thesis consisting of a deterministic ATPG and a non-deterministic ATPG focuses on minimizing test inflation and accelerating runtime. For deterministic perspective, a deterministic parallel test pattern generation (TPG) engine was realized and generated the same test pattern set as the serial ATPG does during acceleration. However, for retaining the determinism, tremendous idle time is observed when different tasks were synchronized among threads. Therefore, a new parallel TPG engine called P4-TPG is developed and incorporates preemptive, proactive and preventive schedulings to further save/reuse the idle time during acceleration. Experimental results show that P4-TPG not only generates the same test pattern set as the serial TPG does but also achieves averagely 10.36X speedups using 12 threads on 17 benchmark circuits. For non-deterministic perspective, since the speedup of a deterministic parallel TPG is limited by determinism, a multi-thread test pattern generation called MT-TPG is proposed to suppress test inflation and accelerate fault processing, simultaneously, to achiever higher parallelism. According to our experimental results, MT-TPG can successfully suppress test inflation to < 4% on 17 benchmark circuits and achieve 13.7X speedup using 16 threads on average. As a result, MT-TPG is proven effective at unleashing parallelism with minimal test inflation on shared-memory systems.