Scheduling high-level blocks for functional simulation

ABSTRACT

This paper presents a method for scheduling high-level blocks for functional simulation under the assumptions that circuits may be cyclic (due to element grouping), and that blocks cannot be broken down into simpler elements. The solution presented here may simulate one block many times per clock period. Obtaining a minimal schedule for a cyclic circuit is shown to be NP-complete, and two approximation algorithms are presented, along with empirical data to evaluate their effectiveness.

REFERENCES

• 1: R.L. Wadsack, "Design Verification :and Testing of the WE 32100 CPUs," IEEE Design &Test of Computers, Aug. 1984, pp. 66-75.
• 2: J.P. Hayes, "An Introduction to Switch-Level Modeling," IEEE Design & Test of Computers, Aug: 1987, pp.18-25.
• 3: Kit Tham , Rob Willoner , David Wimp, Functional design verification by multi-level simulation, Proceedings of the 21st conference on Design automation, p.473-478, June 25-27, 1984, Albuquerque, New Mexico, United States
• 4: M.A. Breuer, A. D. Friedman, Diagnosis and Reliable Design of Digital Systems, Computer Science Press, Woodland Hills, CA, 1976.
• 5: L.-T. Wang , N. E. Hoover , E. H. Porter , J. J. Zasio, SSIM: a software levelized compiled-code simulator, Proceedings of the 24th ACM/IEEE conference on Design automation, p.2-8, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37889]
• 6: Z Wang, P. Maurer, "Scheduling High-Level Blocks for Functional Simulation," University of South Florida Department of Computer Science and Engineering Technical Report Number CSE-88-24, 1988.
• 7: S.A. Szygenda, E. W. Thompson, "Digital Logic Simulation in a Time Based Table Driven Environment," Computer, March 1975.
• 8: David Maier, The Complexity of Some Problems on Subsequences and Supersequences, Journal of the ACM (JACM), v.25 n.2, p.322-336, April 1978 [doi>10.1145/322063.322075]
• 9: Daniel S. Hirschberg, Algorithms for the Longest Common Subsequence Problem, Journal of the ACM (JACM), v.24 n.4, p.664-675, Oct. 1977 [doi>10.1145/322033.322044]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Simulation

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Design, Verification