A GPU-based discrete event simulation kernel. (November 2013)

• Record Type: Journal Article
• Authors: Tang, Wenjie; Yao, Yiping
• Other Names: Mustafee Navonil guest-editor.; Taylor Simon J E guest-editor.
• Is Part Of: Simulation. Volume 89:Number 11(2013)
• Page Start: 1335
• Page End: 1354
• Publication Date: 2013-11
• Subjects: Parallel discrete event simulation -- GPU -- time management -- memory management -- event redistribution; Computer simulation -- Periodicals; 003.3
• DOI: 10.1177/0037549713508839
• Languages: English
• ISSNs: 0037-5497

Abstract

The graphic processing unit (GPU) can perform some large-scale simulations in an economical way. However, harnessing the power of a GPU to discrete event simulation (DES) is difficult because of the mismatch between GPU's synchronous execution mode and DES's asynchronous time advance mechanism. In this paper, we present a GPU-based simulation kernel (gDES) to support DES and propose three algorithms to support high efficiency. Since both limited parallelism and redundant synchronization affect the performance of DES based on a GPU, we propose a breadth-expansion conservative time window algorithm to increase the degree of parallelism while retaining the number of synchronizations. By using the expansion method, it can import as many as possible 'safe' events. The irregular and dynamic requirement for storing the events leads to uneven and sparse memory usage, thereby causing waste of memory and unnecessary overhead. A memory management algorithm is proposed to store events in a balanced and compact way by using a lightweight stochastic method. When events processed by threads in a warp have different types, the performance of gDES decreases rapidly because of branch divergence. An event redistribution algorithm is proposed by reassigning events of the same type to neighboring threads to reduce the probability of branch divergence. We analyze the superiority of the proposed algorithms and gDES with a series of experiments. Compared to a CPU-based simulator on a multicore platform, the gDES can achieve up to 11×, 5×, and 8× speedup in PHOLD, QUEUING NETWORK, and epidemic simulation, respectively.