Cited By
View all- Prasad SCao ZFerrin DMorrice D(2003)Parallel distributed simulation and modeling methodsProceedings of the 35th conference on Winter simulation: driving innovation10.5555/1030818.1030933(872-880)Online publication date: 7-Dec-2003
Parallelizing a sequential logic simulator using an optimistic framework based on a global parallel heap event queue: an experience and performance report
Pages 111 - 118
Abstract
We have parallelized the Iowa Logic Simulator, a gate-level fine-grained discrete-event simulator, by employing an optimistic algorithm framework based on a global event queue implemented as a parallel heap. The original code and the basic data structures of the serial simulator remained unchanged. Wrapper data structures for the logical processes (gates) and the events are created to allow rollbacks, all the earliest events at each logical processes are stored into the parallel heap, and multiple earliest events are simulated repeatedly by invoking the simulate function of the serial simulator. The parallel heap allowed extraction of hundreds to thousands of earliest events in each queue access. On a bus-based shared-memory multiprocessor, simulation of synthetic circuits with 250,000 gates yielding speedups of 3.3 employing five processors compared to the serial execution time of the Iowa Logic Simulator, and limited the number of rollbacks to within 2,000. The basic steps of parallelization are well-defined and general enough to be employable on other discrete-event simulators.
References
[1]
Bailey, M. L., and Lin, Y. -B. 1993. Synchronization strategies for parallel logic- level simulation. International Journal on Computer Simulation. 3, 3, 211-230.
[2]
Bajaj, L., R. Bargrodia, and R. Meyer. 1998. Case study: parallelizing a sequential simulation model, PADS'98 Proceedings of the 12th workshop on Parallel and Distributed Simulation, Pages 29 - 36.
[3]
Casas, J., Yang, H., Khaira, M., Joshi, M., Tetzlaff, T., Otto, S., Seligman, E. 1999. Logic verification of very large circuits using Shark. Proceedings Twelfth International Conference on VLSl Design. Goa, India, p.310-17.
[4]
Chen, Y.-A., Jha, V., Bagrodia, 1997. R. A multidimensional study on the feasibility of parallel switch-level circuit simulation. Proceedings. 11th Workshop on Parallel and Distributed Simulation, Lockenhaus, Austria, p.46-54.
[5]
Cben, Y.-A., Bagrodia, R. 1998. Shared memory implementation of a parallel switch-level circuit simulator. Proceedings. Twelfth Workshop on Parallel and Distributed Simulation PADS '98, Banff, Canada, p.134-41.
[6]
Deo, N., and Prasad, S. 1992. Parallel heap: An optimal parallel priority queue. Journal of Supercomputing, 6: 87-98.
[7]
Jefferson, D. R. 1985. Virtual Time. ACM Transactions on Programming Languages and Systems. 7 (July), 405-425.
[8]
Hirsch, H., Chawla, R, Carter, H.W. 1998. Parallel simulation of VHDL-AMS models. Proceedings of the IEEE 1998 National Aerospace and Electronics Conference. NAECON 1998. Dayton, p.545-51.
[9]
Hsieh, W.-H., Jou, S.-J., Su, C.-C. 1996. Parallel eventdriven MOS timing simulator on distributed memory multiprocessors. IEE Proceedings-Circuits, Devices and Systems, vol. 143, (no.4), p.207-12.
[10]
Kravitz, S. A., Byrant, R. E., and Rutenbar, R. A. 1991. Massively parallel switch-level simulation: A feasibility study. IEEE Transactions on CAD Integrated Circuits and Systems, 10, 7, 871-894.
[11]
Krishnaswamy, V., and Banerjee, R 1996. Actor based parallel VHDL simulation using Time Warp. Proceedings. Tenth Workshop on Parallel and Distributed Simulation. PADS 96. Philadelphia, p. 135-42.
[12]
Liebrock, L.M., Kennedy, K. 1997. Automatic data distribution for composite grid applications. Scientific Programming, vol.6, (no.l), Wiley, p.95-113.
[13]
Manjikian, N. and Loucks, W. M. 1993. High performance parallel logic simulation on a network of workstations. Proceedings of Parallel and Distributed Simulation. 76-84.
[14]
Mueller-Thuns, R. B., Saab, D. G., Damiano, R. E and Abraham, J. A. 1993. VLSI logic and fault simulation on general purpose parallel computers. IEEE Transactions on CAD Integrated Circuits and Systems. 12, 3,446-460.
[15]
Nicol, D. and Heidelberger, R 1995. On extending parallelism to serial simulators, PADS'95 Proceedings of the 9th workshop on Parallel and Distributed Simulation, Pages 60 -67
[16]
Prasad, S. K. 2000. Practical Global-Event-Queue-based Optimistic Simulation Algorithms with One Backup State Vector and Low Rollback Overheads, To appear in Procs. The First International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT'2000), IEEE, May 22-24, Hong Kong.
[17]
Prasad, S. K. 2000. Space-Efficient Algorithms based on Global Event Queues for Parallelization of Existing Discrete Event Simulators, To appear in Procs. The First International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT'2000), IEEE, May 22-24, Hong Kong.
[18]
Prasad, S., and Naqib, B. 1995. Effectiveness of Global Event Queues in Rollback Reduction and Load Balancing. Proceedings of the 9th Workshop on Parallel and Distributed Simulation, Lake Placid, NY, pp. 187-190.
[19]
Prasad, S., and Sawant, S. 1995. Parallel Heap: A practical priority queue for fine-to-medium-grained applications on small multiprocessors. Procs. Symp. on Parallel and Distributed Processing, San Antonio, TX, pp. 328-335.
[20]
Rao, V. N., and Kumar, V. 1988. Concurrent access of priority queues. IEEE Transitions on Computers, 37, 12 (December) 1657-1665. Parallel analog simulation on distributed memory
[21]
Sawant, S. and Prasad, S. K. 1997. An Experimental Comparison Among Shared-Event-Queue-Based Optimistic, Conservative, and Time-Stepped Logic Simulators. Procs. ISCA 12th Intl. Conf. Computers and Their Applications, March 13-15, Tempe, AZ, pp. 238-241.
[22]
Soule, L., and Gupta, A. 1991. An evaluation of the Chandy- Misra-Byrant algorithm for digital logic simulation. ACM Transactions on Modeling and Computer Simulation. 1, (4): 308-47.
[23]
Soule, L. 1992. Parallel logic simulation: An evaluation of centralized-time and distributed-time algorithms. CSL-TR- 92-527. Stanford University, Stanford, CA.
[24]
Todesco, A.R.W., Meng, T.H.-Y. 1996. Symphony: a simulation backplane for parallel mixed-mode co-simulation of VLS1 systems. Proceedings of 33rd Design Automation Conference, Las Vegas, p. 149-54.
[25]
Tsai, J-J. 1994. Automatic Parallelization of Discrete-Event Programs. Ph.D. Diss., College of Computing, Georgia Tech.
Index Terms
- Parallelizing a sequential logic simulator using an optimistic framework based on a global parallel heap event queue: an experience and performance report
Recommendations
Time-parallel multi-delay logic simulation
TMS-DEVS '16: Proceedings of the Symposium on Theory of Modeling & SimulationMulti-delay logic simulation may perform many logic simulations for each gate in the circuit during the simulation of a single input vector. Conventional event driven simulation will perform each of these gate-simulations as a separate operation, ...
Parallel shared-memory simulator performance for large ATM networks
A performance comparison between an optimistic and a conservative parallel simulation kernel is presented. Performance of the parallel kernels is also compared to a central-event-list sequential kernel. A spectrum of ATM network and traffic scenarios ...
Parallel discrete event simulation for DEVS cellular models using a GPU
HPC '12: Proceedings of the 2012 Symposium on High Performance ComputingThe discrete event systems specification (DEVS) simulation has been studied to analyze complex homogeneous systems which is represented by the cellular models. In the simulation of large-scale DEVS cellular model, it requires a high-performance ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- SCS: Society for Computer Simulation
- SIGSIM: ACM Special Interest Group on Simulation and Modeling
- IEEE-CS\TCSIM: TC on Simulation
Publisher
IEEE Computer Society
United States
Publication History
Published: 01 May 2000
Check for updates
Author Tags
Qualifiers
- Article
Conference
PADS00
Sponsor:
- SCS
- SIGSIM
- IEEE-CS\TCSIM
Acceptance Rates
PADS '00 Paper Acceptance Rate 19 of 36 submissions, 53%;
Overall Acceptance Rate 398 of 779 submissions, 51%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 327Total Downloads
- Downloads (Last 12 months)46
- Downloads (Last 6 weeks)4
Reflects downloads up to 16 Jan 2025
Other Metrics
Citations
Cited By
View all- Prasad SCao ZFerrin DMorrice D(2003)Parallel distributed simulation and modeling methodsProceedings of the 35th conference on Winter simulation: driving innovation10.5555/1030818.1030933(872-880)Online publication date: 7-Dec-2003
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in