On Determining How Many Computers to Use in Parallel VLSI Simulation

ABSTRACT

Parallel discrete event simulation has been established as a technique which has great potential to speed up the execution of gate level circuit simulation. A fundamental problem posed by a parallel environment is the decision of whether it is best to simulate a particular circuit sequentially or on a parallel platform. Furthermore, in the event that a circuit should be simulated on a parallel platform, it is necessary to decide how many computing nodes should be used on the given platform. In this paper we propose a machine learning algorithm as an aid in making these decisions. The algorithm is based on the well-known K-Nearest Neighbor algorithm. After an extensive training regime, it was shown to make a correct prediction 99% of the time on whether to use a parallel or sequential simulator. The predicted number of nodes to use on a parallel platform was shown to produce an average execution time which was not more than 12% of the smallest execution time. The configuration which resulted in the minimal execution time was picked 61% of the time.

REFERENCES

• 1: K.-H. Chang, H.-W. Wang, Y.-J. Yeh, and S.-Y. Kuo. Automatic partitioner for distributed parallel logic simulation. In Modelling, Simulation, and Optimization, volume 429, 2004.
• 2: Chau-Shen Chen , C. L. Liu , Ting Ting Hwang, Architecture driven circuit partitioning, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.2, p.383-390, April 2001 [doi>10.1109/92.924060]
• 3: Jong-Sheng Cherng, Sao-Jie Chen, Chia-Chun Tsai, and Jan-Ming Ho. An efficient two-level partitioning algorithm for vlsi circuits. Asia and South Pacific Design Automation Conference, pages 69-72, 1999.
• 4: H. Avril and C. Tropper. Scalable clustered time warp and logic simulation. VLSI Design, Special Issue on Current Advances in Logic Simulation, Gordon-Breach, vol. 19, no. 3, lpp. 291-313, 1999.
• 5: M.D Hutton, J.S Rose, and D.G. Corneil. Automatic generation of synthetic sequential benchmark circuits. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions, pages 928-940, 2002.
• 6: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 7: D. Jefferson and H. Sowizral. Fast concurrent simulation using the time warp mechanism, part ii: Global control. Technical Report TR-83-204, Rand Corporation, 1983.
• 8: Hong K. Kim , Jack S. N. Jean, Parallel Optimistic Logic Simulation with Event Lookahead, Proceedings of the 1998 International Conference on Parallel Processing, p.20-27, August 10-14, 1998
• 9: Lijun Li , Carl Tropper, A Design-Driven Partitioning Algorithm for Distributed Verilog Simulation, Proceedings of the 21st International Workshop on Principles of Advanced and Distributed Simulation, p.211-218, June 12-15, 2007 [doi>10.1109/PADS.2007.4]
• 10: Tun Li , Yang Guo , Si-Kun Li, Design and Implementation of a Parallel Verilog Simulator: PVSim, Proceedings of the 17th International Conference on VLSI Design, p.329, January 05-09, 2004
• 11: Friedemann Mattern, Efficient algorithms for distributed snapshots and global virtual time approximation, Journal of Parallel and Distributed Computing, v.18 n.4, p.423-434, Aug. 1993 [doi>10.1006/jpdc.1993.1075]
• 12: Octavian Procopiuc, Pankaj K. Agarwal, Lars Arge, and Jeffrey Scott Vittery. Bkd-tree: A dynamic scalable kd-tree. In Proc. International Symposium on Spatial and Temporal Databases, pages 46-65, 2003.
• 13: 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]
• 14: Dale E. Martin , Radharamanan Radhakrishnan , Dhananjai M. Rao , Malolan Chetlur , Krishnan Subramani , Philip A. Wilsey, Analysis and simulation of mixed-technology VLSI Systems, Journal of Parallel and Distributed Computing, v.62 n.3, p.468-493, March 2002 [doi>10.1006/jpdc.2001.1805]
• 15: S.J. Turner and M.Q. XU. Performance evaluation of the bounded time warp algorithm. 6th Workshop on Parallel and Distributed Simulation, pages 117-126, 1992.
• 16: P. Wilsey and A. Palaniswamy. Rollback relaxation: A technique for reducing rollback costs in optimistically synchronized parallel simulators. In Proceedings of the Intl. Conf. on Simulation and Hardware Descritption Languages, 1994.
• 17: Qing Xu , Carl Tropper, XTW, A Parallel and Distributed Logic Simulator, Proceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation, p.181-188, June 01-03, 2005 [doi>10.1109/PADS.2005.40]
• 18: Qing Xu and Carl Tropper. Towards large scale optimistic vlsi simulation. Journal of Simulation Modelling Practice and Theory, 14(6):695- 711, 2006.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory