SPIN-PAC: test compaction for speed-independent circuits

ABSTRACT

SPIN-PAC is a static test compaction method for Speed-Independent circuits. We demonstrate how the test sets can be compacted by combining multiple consecutive test vectors within a test sequence into a vector pair of higher Hamming distance, and by eliminating or pruning independent test sequences. We discuss the exponential nature of optimally solving this problem, we propose an efficient algorithm to approximate it, and we evaluate its performance through experiments.

REFERENCES

• 1: C. J. Myers, Asynchronous Circuit Design, John Wiley and Sons, Inc., New York, 2001.
• 2: Feng Shi , Yiorgos Makris, SPIN-SIM: Logic and Fault Simulation for Speed-Independent Circuits, Proceedings of the International Test Conference on International Test Conference, p.597-606, October 26-28, 2004
• 3: Feng Shi , Yiorgos Makris, Fault simulation and random test generation for speed-independent circuits, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA [doi>10.1145/988952.988984]
• 4: Feng Shi , Y. Makris, SPIN-TEST: automatic test pattern generation for speed-independent circuits, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.903-908, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382703]
• 5: Kwang-Ting Cheng , Vishwani D. Agrawal, A Simulation-Based Method for Generating Tests for Sequential Circuits, IEEE Transactions on Computers, v.39 n.12, p.1456-1463, December 1990 [doi>10.1109/12.61065]
• 6: F. Corno , P. Prinetto , M. Rebaudengo , M. Sonza Reorda, New Static Compaction Techniques of Test Sequences for Sequential Circuits, Proceedings of the 1997 European conference on Design and Test, p.37, March 17-20, 1997
• 7: M. Dimopoulos and P. Linardis, "Accelerating the compaction of test sequences in sequential circuits through problem size reduction," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 22, no. 10, pp. 1443--1449, 2003.
• 8: Petros Drineas , Yiorgos Makris, Independent Test Sequence Compaction through Integer Programming, Proceedings of the 21st International Conference on Computer Design, p.380, October 13-15, 2003
• 9: Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
• 10: M. Berkelaar, "Linear programming solver," Available from http://www.cs.sunysb.edu/algorith/implement/1psolve/implement.shtml.
• 11: J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and A. Yakovlev, "Petrify: a tool for manipulating concurrent specifications and synthesis of asynchronous controllers," IEICE Transactions on Information and Systems, vol. E80-D, no. 3, pp. 315--325, 1997.
• 12: J. E. Chen, C. L. Lee, and W. J. Shen, "Single-fault fault-collapsing analysis in sequential logic circuits," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 10, no. 12, pp. 1559--1568, 1991.