Concurrency preserving partitioning (CPP) for parallel logic simulation

ABSTRACT

Based on a linear ordering of vertices in a directed graph, a linear-time partitioning algorithm for parallel logic simulation is presented. Unlike most other partitioning algorithms, the proposed algorithm preserves circuit concurrency by assigning to processors circuit gates that can be evaluated at about the same time. As a result, the concurrency preserving partitioning (CPP) algorithm can provide better load balancing throughout the period of a parallel simulation. This is especially important when the algorithm is used together with a Time Warp simulation where a high degree of concurrency can lead to fewer rollbacks and better performance. The algorithm consists of three phases, and three conflicting goals can be separately considered in each phase so to reduce computational complexity. A parallel gate-level circuit simulator is implemented on an Intel Paragon machine to evaluate the performance of the CPP algorithm. The results are compared with two other partitioning algorithms to show that reasonable speedup may be achieved with the algorithm.

REFERENCES

• 1: Mary L. Bailey , Jack V. Briner, Jr. , Roger D. Chamberlain, Parallel logic simulation of VLSI systems, ACM Computing Surveys (CSUR), v.26 n.3, p.255-294, Sept. 1994 [doi>10.1145/185403.185424]
• 2: F. Brglez, D. Bryan, and K. Kozminski, "Combinational Profiles of Sequential Benchmark Circuits," Proc. of the IEEE International Symp. on Circuits and Systems, pp. 1929-1934, 1989.
• 3: Azzedine Boukerche , Carl Tropper, A static partitioning and mapping algorithm for conservative parallel simulations, Proceedings of the eighth workshop on Parallel and distributed simulation, p.164-172, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 4: Jack Vedder Briner, Jr. , Gershon Kedem , John L. Ellis, Parallel mixed-level simulation of digital circuits using virtual time, 1990
• 5: Roger D. Chamberlain , Cheryl D. Henderson, Evaluating the use of pre-simulation in VLSI circuit partitioning, Proceedings of the eighth workshop on Parallel and distributed simulation, p.139-146, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 6: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 7: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 8: Kevin L. Kapp , Thomas C. Hartrum , Tom S. Wailes, An improved cost function for static partitioning of parallel circuit simulations using a conservative synchronization protocol, Proceedings of the ninth workshop on Parallel and distributed simulation, p.78-85, June 13-16, 1995, Lake Placid, New York, United States
• 9: B. W. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell System Technical Journal, Vol. 49, pp. 291-307, Feb. 1970.
• 10: Pavlos Konas , Pen-Chung Yew, Parallel discrete event simulation on shared-memory multiprocessors, Proceedings of the 24th annual symposium on Simulation, p.134-148, April 1991, New Orleans, Louisiana, United States
• 11: S. A. Kravitz and B. D. Ackland, "Static vs Dynamic Partitioning of Circuits for a MOS Timing Simulator on A Message-Based Multiprocessor," Proc. of the SCS Multiconference on Distributed Simulation, pp. 136-140, 1988.
• 12: Y. H. LevendeI, P. R. Menon, and S. H. Patel, "Special Purpose Computer for Logic Simulation Using Distributed Processing," Bell System Technical Journal, Vol. 61, No. 10, pp. 2873-2909, Dec. 1982.
• 13: B. A. Malloy , E. L. Lloyd , M. L. Soffa, Scheduling DAG's for Asynchronous Multiprocessor Execution, IEEE Transactions on Parallel and Distributed Systems, v.5 n.5, p.498-508, May 1994 [doi>10.1109/71.282560]
• 14: Naraig Manjikian , Wayne M. Loucks, High performance parallel logic simulations on a network of workstations, Proceedings of the seventh workshop on Parallel and distributed simulation, p.76-84, May 16-19, 1993, San Diego, California, United States
• 15: 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 Trans. on Computer-Aided Design, Vol. 12, No. 3, pp. 446- 460, March 1993.
• 16: S. P. Smith, B. Underwood, M. R. Mercer, "An Analysis of Several Approaches to Circuit Partitioning for Parallel Logic Simulation," IEEE International Conference on Computer Design, pp. 664-667, 1987.
• 17: Christian Sporrer , Herbert Bauer, Corolla partitioning for distributed logic simulation of VLSI-circuits, Proceedings of the seventh workshop on Parallel and distributed simulation, p.85-92, May 16-19, 1993, San Diego, California, United States

INDEX TERMS

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

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

General Terms:
Algorithms, Measurement, Performance, Theory

Keywords:
Parallel Logic Simulation, Partitioning, Concurrency, Load Balancing, Time Warp