Zamlog: a parallel algorithm for fault simulation based on Zambezi

ABSTRACT

We present a new multiprocessor sequential circuit fault simulator, Zamlog, based on a novel uniprocessor simulator, Zambezi. Both the fault and test sets are partitioned for multiprocessor simulation. The parallelization technique, designed to preserve the efficiency of Zambezi, is simple to implement and has low communication requirements. Experimental results indicate that Zamlog can obtain speedups of up to 95. The speedups obtained and the scalability are between 3 and 10 times better than any reported in the literature. Furthermore, the speed-ups obtained are with respect to a uniprocessor algorithm which is superior, by an average of 40%, to those used to gauge the speed-ups of previous parallel systems.

REFERENCES

• 1: T. M. Nierman, W. T. Cheng, and J. H. Patel, "Proofs: A fast memory efficient sequential circuit fault simulator," IEEE T-CAD, 1992.
• 2: N. Gouders and R. Kaibel, "Paris: A parallel pattern fault simulator for synchronous sequential circuits," in Proc. ICCAD, 1991.
• 3: M. B. Amin , B. Vinnakota, ZAMBEZI: a parallel pattern parallel fault sequential circuit fault simulator, Proceedings of the 14th IEEE VLSI Test Symposium (VTS '96), p.438, April 28-May 01, 1996
• 4: N. Ishiura, M. Ito, and S. Yajima, "Dynamic two-dimensional parallel simulation technique for high-speed fault simulation on a vector processor," IEEE T-CAD, pp. 868-875, August 1990.
• 5: S. Patil and P. Banerjee, "Performance trade-offs in a parallel test generation/fault simulation environment," IEEE T-CAD, pp. 1542-1558, December 1991.
• 6: Vinod Narayanan , Vijay Pitchumani, Fault simulation on massively parallel SIMD machines: algorithms, implementations and results, Journal of Electronic Testing: Theory and Applications, v.3 n.1, p.79-92, Feb. 1992 [doi>10.1007/BF00159833]
• 7: Abdulla Bataineh , Füsun Özgüner , Imre Szauter, Parallel logic and fault simulation algorithms for shared memory vector machines, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.369-372, November 1992, Santa Clara, California, United States
• 8: S. E. Tai and D. Bhattacharya, "Pipelined fault simulation on parallel machines using the circuit flow graph," in Proc. ICCD, 1993.
• 9: R. B. Mueller-Thuns, D. G. Saab, R. F. Damiano, and J. A. Abraham, "VLSI logic and fault simulation on general-purpose parallel computers," IEEE T-CAD, pp. 446-460, March, 1993.
• 10: Minesh B. Amin , Bapiraju Vinnakota, Data parallel fault simulation, Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors, p.610-615, October 02-04, 1995
• 11: Steven Parkes , Prithviraj Banerjee , Janak Patel, A parallel algorithm for fault simulation based on PROOFS, Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors, p.616, October 02-04, 1995
• 12: M. B. Amin and B. Vinnakota, "Data parallel sequential circuit fault simulation," in Proc. IS- CAS'96, 1996.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Sequential circuits

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Parallel

General Terms:
Algorithms, Design, Performance

Keywords:
Zambezi, Zamlog, fault simulation, logic testing, multiprocessor simulation, parallel algorithm, sequential circuit fault simulator, test sets, uniprocessor simulator