liw-j/atpg-eda-challenge

2023 EDA Challenge P1 : Parallel Acceleration of Fault Simulation for Multi-core processor Architectures

FAN ATPG

version 2023
Laboratory of Dependable Systems, Graduate Institute of Electronics Engineering, National Taiwan University, Taiwan

FAN (fan-out-oriented) ATPG (Automatic Test Pattern Generation) and Fault Simulation command line tool

Youtube Tutorial »

User Guide »

This tool's main algorithm is implemented based on the following paper:
Fujiwara and Shimono, "On the Acceleration of Test Generation Algorithms," in IEEE Transactions on Computers, vol. C-32, no. 12, pp. 1137-1144, Dec. 1983.

Table Contents

1. Introduction
2. Directory Structure
3. Environment Requisites
4. Usage
5. Experimental Result
6. Revision History
7. Authors
8. References
9. Contact
10. License

Introduction

This project is a FAN (fan-out-oriented)[1] ATPG (Automatic Test Pattern Generation) and Fault Simulation command line tool.

This project includes the implementation of

1. Fault Collapsing
2. Parallel Fault Fault Simulation
3. Parallel Pattern Fault Simulation
4. Automatic Test Pattern Generation
5. Static Test Compression
6. Dynamic Test Compression
7. Writing pattern in different format:
   - STIL : Support Fault Simulation with the commercial tool TetraMAX
   - ASCII : Support Fault Simulation with the commercial tool FastScan
   - .pat : Support Fault Simulation with this tool FAN_ATPG
8. Multiple Fault Orderings
   Note: This feature is now moved to branch MFO, should be integrated as an additional command line opption in the future.
   This is a heuristic we implemented in v2023. It tries a rational number of fault list orderings that differ to one another as much as possible with rational run time. With different fault list orderings, we choose the fault list ordering that generate test pattern set with the highest Fault Coverage and the lowest Test Length (if same Fault Coverage).
   

We make this project open source in the hope of helping anyone who is learning ATPG. If you have any suggestion for the source code or new features for this project, feel free to fork this repo and create a pull request. Any contribution to this project would be very much appreciated!

We would also be extremely grateful if you star this project!

[back to top]

Directory Structure

• bin/ : Binary - Store binaries after compilation
• include/ : Store header files included in and copied from pkg/
• lib/ : Library - Store library binaries after compilation
• mod_netlist/, netlist/ : Store the benchmark circuits[2]
• pat/ : Patterns - Store the patterns generated by ATPG
• pkg/ : Package - All of the source code
  • common/ : Common Linux command line instructions support
  • core/ : Main ATPG algorithm and the Fault Simulation procedure
  • fan/ : The ATPG commands and entry point of the program
  • interface/ : The interface for reading benchmark circuits
• rpt/ : Report - Store the report after ATPG or Fault Simulation
• script/ : Scripts for running ATPG and Fault Simulation
• techlib/ : The cell libraries for benchmark circuits
• utility/ : The utilities files, e.g. convert STIL to .pat
• ATPG_UserGuide.pdf : The User Guide
• copyHeader.sh : Copy header files from pkg/ to include/
• Makefile : The top makefile for the whole project
• common.mk : Define the project layout for Makefile, e.g. directory structure, C++ version, Lex&Yacc.
• info.mk : Define package name, type and dependency, e.g. fan, libcommon.a
• rule.mk : Define rules for make targets, which folder the binary should be generated or copied to.

[back to top]

Environment Requisites

Prerequisites

• Operating System : Linux
  
• Compiler : Support std C++11
  
• Other tools : Bison, Lex
  

Requisites Installation

sudo apt install bison
sudo apt install lex

Check requisites Installation

bison --version
lex --version

[back to top]

Usage

Installation

After the following commands are executed, an executable binary fan will be generated under ./bin/opt/.

1. Clone the repo

   git clone https://github.com/NTU-LaDS-II/FAN_ATPG.git

2. Change directory

   cd FAN_ATPG/

3. Compile

   make

Clean Installed Files

make clean

Run ATPG

./bin/opt/fan -f script/fanScripts/atpg_s27.script

Run Fault Simulation

./bin/opt/fan -f script/fanScripts/fsim_s27.script

[back to top]

Experimental Result

• Fault Coverage (FC) -
  Fault Coverage is the most important statistic for evaluation of an ATPG tool. It indicates how well a circuit could be tested, hence the quality of a test pattern set. The calculation equation by this tool FAN_ATPG is as follow:

  $$FC = {number \ of \ \textbf{\textit{detected}} \ faults \over number \ of \ \textbf{\textit{total}} \ faults} \ * \ 100\%$$

• Test Length (TL) -
  Under the same Fault Coverage, it is essential to compress the Test Length. The definition of Test Length is the total number of test patterns in a test pattern set. Low Test Length is desired in order to reduce test data (ATE cost), test time (test cost) while maintaining the same test quality (FC).

Both Test Compression OFF

Benchmark Circuit	Fault Coverage (%)	Test Length (#)
s27	94.55	12
s208	97.43	46
s510	99.14	70
s953	97.85	123
s1196	98.84	183
s1238	96.36	193
s5378	96.04	478
s9234	94.14	647
s15850	94.62	817
s35932	87.58	1764
s38417	95.99	2428
s38584	93.33	1832

Static Test Compression On Dynamic Test Compression OFF

Benchmark Circuit	Fault Coverage (%)	Test Length (#)
s27	94.55	9
s208	97.43	36
s510	99.14	65
s953	97.85	93
s1196	98.84	155
s1238	96.36	163
s5378	96.04	327
s9234	94.14	475
s15850	94.62	583
s35932	87.58	512
s38417	95.99	1565
s38584	93.33	1177

Static & Dynamic Test Compression OFF

Benchmark Circuit	Fault Coverage (%)	Test Length (#)
s27	94.55	5
s208	97.43	29
s510	99.14	59
s953	97.85	89
s1196	98.84	134
s1238	96.36	145
s5378	96.04	117
s9234	94.14	156
s15850	94.62	133
s35932	87.58	21
s38417	96.00	105
s38584	93.33	133

[back to top]

Revision History

• v2013 - Initial release
  
• v2014 - Code modifications
  
• v2023 - Code refactor for open source project
  

[back to top]

Authors

• Lead Author
  - Lin Hio-Ting
  
  
• Original Authors
  - Lin Hio-Ting, Hsu Po-Ya, Liao Kuan-Yu
  
  
• v2013
  - Han Cheng-You, Chen Ching-Yu, Chiang Kuan-Ying, Wang Ying-Hsu, Chen Po-Hao, Lin Kuo-Yu, Pan Chun-Han, Li Chia-An, Tsai Chia-Ling, Hsu Ling-Yun
  
  
• v2014
  - He Yu-Hao, Cai Zong-Yan, How Bo-Fan, Li Yu-Qing, Huang Guan-Yan, Xiao Zhi-Long, Lin Kun-Wei, Lin Shi-Yao, Chen You-Wei, Li Guan-De
  
  
• v2023
  - Wang Wei-Shen, Chang Hsin-Tzu, Pan Yu-Hung, Liang Zhe-Jia
  
  
• Advisor
  - Professor James Chien-Mo Li

[back to top]

References

• [1] Fujiwara and Shimono, "On the Acceleration of Test Generation Algorithms," in IEEE Transactions on Computers, vol. C-32, no. 12, pp. 1137-1144, Dec. 1983.
  
• [2] Brglez, Franc, David Bryan, and Krzysztof Kozminski. "Combinational profiles of sequential benchmark circuits." 1989 IEEE International Symposium on Circuits and Systems (ISCAS). IEEE, 1989.
  
• [3] techlib/mod_nangate45.mdt and techlib/NangateOpenCellLibrary.v are under TECHLIB_LICENSE
  

[back to top]

Contact

Wang Wei-Shen - [email protected]

[back to top]

License

Distributed under the MIT License. See LICENSE for more information.

[back to top]

---

Copyright (c) Laboratory of Dependable Systems, Graduate Institute of Electronics Engineering, National Taiwan University, Taiwan. All Rights Reserved.