research-article

GPU accelerated three-stage execution model for event-parallel simulation

Authors:

Stephen John TurnerAuthors Info & Claims

SIGSIM PADS '13: Proceedings of the 1st ACM SIGSIM Conference on Principles of Advanced Discrete Simulation

Pages 57 - 66

https://doi.org/10.1145/2486092.2486100

Published: 19 May 2013 Publication History

Abstract

This paper introduces the concept of event-parallel discrete event simulation (DES) and its corresponding implementation on the GPU platform. Inspired by the typical spatial-parallel DES and time-parallel DES, the event-parallel approach on GPU uses each thread to process one of the N events, where N is the total number of events. By taking advantage of the high parallelism of GPU threads, this approach achieves greater speedup. The GPU architecture is adopted in the execution of the event-parallel approach, so as to take advantage of the parallel processing capability provided by the massively large number of GPU threads. A three-stage execution model composing of generating events, sorting events and processing events in parallel is proposed. This execution model achieves good speedup. Compared with the event scheduling approach on CPU, we achieve up to 22.80 speedup in our case study.

References

[1]

A. Bleiweiss. Multi agent navigation on the GPU. White paper, Game Developers Conference, 9, 2009.

[2]

K. Chandy and R. Sherman. Space-time and simulation. In Proceedings of the SCS Multiconference on Distributed Simulation, pages 53--57, 1989.

[3]

R. M. Fujimoto. Parallel and Distributed Simulation Systems. John Wiley & Sons Inc, 2000.

Digital Library

[4]

T. Kiesling. Progressive time-parallel simulation. In Proceedings of the ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation, pages 82--91, 2006.

Digital Library

[5]

T. Kiesling and J. Luthi. Towards time-parallel road traffic simulation. In Proceedings of the ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation, pages 7--15, 2005.

Digital Library

[6]

T. Kiesling and S. Pohl. Time-parallel simulation with approximative state matching. In Proceedings of the ACM/IEEE/SCS Workshop on Parallel and Distributed Simulation, pages 195--202, 2004.

Digital Library

[7]

G. Kunz, D. Schemmel, J. Gross, and K. Wehrle. Multi-level parallelism for time-and cost-efficient parallel discrete event simulation on gpus. In Proceedings of the ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation, pages 23--32, 2012.

Digital Library

[8]

C. Macal and M. North. Tutorial on agent-based modelling and simulation. Journal of Simulation, 4(3):151--162, 2010.

[9]

D. Merrill and A. Grimshaw. High performance and scalable radix sorting: A case study of implementing dynamic parallelism for gpu computing. Parallel Processing Letters, 21(02):245--272, 2011.

[10]

H. Nguyen. GPU Gems 3. Addison-Wesley Professional, 2007.

Digital Library

[11]

NVIDIA. Nvidia cuda programming guide. http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html. {Online}.

[12]

NVIDIA. Thrust | nvidia developer zone. https://developer.nvidia.com/thrust. {Online}.

[13]

H. Park and P. Fishwick. A gpu-based application framework supporting fast discrete-event simulation. Simulation, 86(10):613--628, 2010.

Digital Library

[14]

H. Park and P. Fishwick. An analysis of queuing network simulation using gpu-based hardware acceleration. ACM Transactions on Modeling and Computer Simulation, 21(3):18, 2011.

Digital Library

[15]

N. Pelechano, J. Allbeck, and N. Badler. Controlling individual agents in high-density crowd simulation. In Proceedings of the ACM SIGGRAPH/Eurographics symposium on Computer animation, pages 99--108, 2007.

Digital Library

[16]

K. Perumalla. Discrete-event execution alternatives on general purpose graphical processing units (gpgpus). In Proceedings of the ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation, pages 74--81, 2006.

Digital Library

[17]

S. Robinson. Simulation: the Practice of Model Development and Use. Wiley, 2004.

Digital Library

[18]

D. Strippgen and K. Nagel. Multi-agent traffic simulation with cuda. In Proceedings of the International Conference on High Performance Computing & Simulation, pages 106--114, 2009.

Cited By

Tang WCai WYao YSong XZhu F(2019)An alternative approach for collaborative simulation execution on a CPU+GPU hybrid systemSIMULATION10.1177/0037549719885178(003754971988517)Online publication date: 14-Nov-2019
https://doi.org/10.1177/0037549719885178
Xiao JAndelfinger PEckhoff DCai WKnoll A(2019)A Survey on Agent-based Simulation Using Hardware AcceleratorsACM Computing Surveys10.1145/329104851:6(1-35)Online publication date: 28-Jan-2019
https://dl.acm.org/doi/10.1145/3291048
Liu XAndelfinger PCai WMeng TWilsey PJin K(2017)Time Warp on the GPUProceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3064911.3064912(109-120)Online publication date: 16-May-2017
https://dl.acm.org/doi/10.1145/3064911.3064912
Show More Cited By

Recommendations

Time Warp on the GPU: Design and Assessment
SIGSIM-PADS '17: Proceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation

The parallel execution of discrete-event simulations on commodity GPUs has been shown to achieve high event rates. Most previous proposals have focused on conservative synchronization, which typically extracts only limited parallelism in cases of low ...
Parallel discrete event simulation
Special issue on simulation

Parallel discrete event simulation (PDES), sometimes called distributed simulation, refers to the execution of a single discrete event simulation program on a parallel computer. PDES has attracted a considerable amount of interest in recent years. From ...
Research Challenges in Parallel and Distributed Simulation

The parallel and distributed simulation field has evolved and grown from its origins in the 1970s and 1980s and remains an active field of research to this day. A brief overview of research in the field is presented. Future research topics are explored ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSIM PADS '13: Proceedings of the 1st ACM SIGSIM Conference on Principles of Advanced Discrete Simulation

May 2013

426 pages

ISBN:9781450319201

DOI:10.1145/2486092

General Chair:
Margaret L. Loper
Georgia Institute of Technology, USA
,
Program Chair:
Gabriel A. Wainer
Carleton University, Canada

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGSIM-PADS '13

Sponsor:

SIGSIM

SIGSIM-PADS '13: SIGSIM Principles of Advanced Discrete Simulation

May 19 - 22, 2013

Québec, Montr©al, Canada

Acceptance Rates

SIGSIM PADS '13 Paper Acceptance Rate 29 of 75 submissions, 39%;

Overall Acceptance Rate 398 of 779 submissions, 51%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
248
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)5

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tang WCai WYao YSong XZhu F(2019)An alternative approach for collaborative simulation execution on a CPU+GPU hybrid systemSIMULATION10.1177/0037549719885178(003754971988517)Online publication date: 14-Nov-2019
https://doi.org/10.1177/0037549719885178
Xiao JAndelfinger PEckhoff DCai WKnoll A(2019)A Survey on Agent-based Simulation Using Hardware AcceleratorsACM Computing Surveys10.1145/329104851:6(1-35)Online publication date: 28-Jan-2019
https://dl.acm.org/doi/10.1145/3291048
Liu XAndelfinger PCai WMeng TWilsey PJin K(2017)Time Warp on the GPUProceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3064911.3064912(109-120)Online publication date: 16-May-2017
https://dl.acm.org/doi/10.1145/3064911.3064912
Fujimoto R(2016)Research Challenges in Parallel and Distributed SimulationACM Transactions on Modeling and Computer Simulation10.1145/286657726:4(1-29)Online publication date: 2-May-2016
https://dl.acm.org/doi/10.1145/2866577
Fujimoto R(2015)Parallel and distributed simulationProceedings of the 2015 Winter Simulation Conference10.5555/2888619.2888624(45-59)Online publication date: 6-Dec-2015
https://dl.acm.org/doi/10.5555/2888619.2888624
Fujimoto R(2015)Parallel and distributed simulation2015 Winter Simulation Conference (WSC)10.1109/WSC.2015.7408152(45-59)Online publication date: Dec-2015
https://doi.org/10.1109/WSC.2015.7408152
Chen HYao YTang WMeng DZhu FFu YYao Y(2015)Can MIC find its place in the field of PDES?Proceedings of the 19th International Symposium on Distributed Simulation and Real Time Applications10.1109/DS-RT.2015.23(41-49)Online publication date: 14-Oct-2015
https://dl.acm.org/doi/10.1109/DS-RT.2015.23
Andelfinger PHartenstein HBuckley SMiller J(2014)Exploiting the parallelism of large-scale application-layer networks by adaptive GPU-based simulationProceedings of the 2014 Winter Simulation Conference10.5555/2693848.2694281(3471-3482)Online publication date: 7-Dec-2014
https://dl.acm.org/doi/10.5555/2693848.2694281
Xu YTan GLi XSong XHamilton JRiley GFujimoto R(2014)Mesoscopic traffic simulation on CPU/GPUProceedings of the 2nd ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/2601381.2601396(39-50)Online publication date: 18-May-2014
https://dl.acm.org/doi/10.1145/2601381.2601396
Liu JLiu YDu ZLi THamilton JRiley GFujimoto R(2014)GPU-assisted hybrid network traffic modelProceedings of the 2nd ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/2601381.2601382(63-74)Online publication date: 18-May-2014
https://dl.acm.org/doi/10.1145/2601381.2601382

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten