Parallel and Vector Logic and Fault Simulation Algorithms on the Cray Y-MP Supercomputer

Abstract

In this paper, we present parallel algorithms for logic and fault simulation, developed for and implemented on the Cray Y-MP supercomputer, a general purpose shared- memory parallel machine with vector processors. The parallel-and-vector version of the event-driven logic simulation algorithm achieves a speedup of 52 on the Cray Y-MP with 8 processors, with a maximum performance of about 2 million events per second. These results are comparable to the performance of hardware simulation engines and can be implemented on other parallel machines without major modifications. The second algorithm is a parallel and vector version of the parallel fault simulation algorithm. Experimental results on benchmark circuits [1] show that very high evaluation rates (20 to 32×10⁹ evaluations/s.) can be achieved. Speedup factors of 45 to 69 are observed between the scalar and the parallel and vector execution of the fault simulator.

Keywords

parallel processing vector processing logic simulation fault simulation

References

Brglez, F. and H. Fujiwara , "A Neutral Netlist of 10 Combinational Benchmark Circuits and a Target Translator in Fortran." in Proc. IEEE Int. Symp. Circuits Syst.; Special Session on ATPG and Fault Simulation, June 1985.

Levendel, Y. and P.R. Menon , "Fault simulation," in Fault-Tolerant Computing: Theory and Techniques ( D. K. Pradhan , ed.), pp. 184-264, Prentice-Hall, 1986.

Takasaki, S. , F. Hirose , and A. Yamada , "Logic simulation engines in Japan," IEEE Design and Test of Computers, vol. 6, pp. 40-49, Oct. 1989.

Denneau, M. "The Yorktown simulation engine," Proceedings of the 19th DAC, pp. 55-59, June 1982.

Blank, T. "A survey of hardware accelerators used in computer-aided design," IEEE Design and Test of Computers, vol. 1, pp. 21-39, August 1984.

Ishiura, N. , H. Yasuura , and S. Yajima , "High speed logic simulation on vector processors," IEEE Trans. on Computer-Aided Design, vol. Cad-6, pp. 305-320, May 1987.

Daoud, R. and F. Ozguner. "Highly vectorizable fault simulation on the CRAY X-MP supercomputer," IEEE Transactions on Computer-Aided Design , vol. 8, pp. 1362-1365, Dec. 1989.

Ulrich, E. "Table look-up techniques for fast and flexible digital logic simulation,"

in Proceedings of the 17th DAC, June

1980,pp. 560-563.

Breuer, M.A. and A.D. Friedman. Diagnosis and Reliable Design of Digital Systems. Rockville, MD: Computer Science Press, 1976.

10.

Greer, D.L. "The quick simulator benchmark," VLSI Systems Design, pp. 2-7, Nov. 1987.