Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
International Journal of Parallel Programming
Published in: International Journal of Parallel Programming 6/2016

01-12-2016

Transparent Speculative Parallelization of Discrete Event Simulation Applications Using Global Variables

Authors: Alessandro Pellegrini, Sebastiano Peluso, Francesco Quaglia, Roberto Vitali

Published in: International Journal of Parallel Programming | Issue 6/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Parallelizing (compute-intensive) discrete event simulation (DES) applications is a classical approach for speeding up their execution and for making very large/complex simulation models tractable. This has been historically achieved via parallel DES (PDES) techniques, which are based on partitioning the simulation model into distinct simulation objects (somehow resembling objects in classical object-oriented programming), whose states are disjoint, which are executed concurrently and rely on explicit event-exchange (or event-scheduling) primitives as the means to support mutual dependencies and notification of their state updates. With this approach, the application developer is necessarily forced to reason about state separation across the objects, thus being not allowed to rely on shared information, such as global variables, within the application code. This implicitly leads to the shift of the user-exposed programming model to one where sequential-style global variable accesses within the application code are not allowed. In this article we remove this limitation by providing support for managing global variables in the context of DES code developed in ANSI-C, which gets automatically parallelized. Particularly, we focus on speculative (also termed optimistic) PDES systems that run on top of multi-core machines, where simulation objects can concurrently process their events with no guarantee of causal consistency and actual violations of causality rules are recovered through rollback/recovery schemes. In compliance with the nature of speculative processing, in our proposal global variables are transparently mapped to multi-versions, so as to avoid any form of safety predicate verification upon their updates. Consistency is ensured via the introduction of a new rollback/recovery scheme based on detecting global variables’ reads on non-correct versions. At the same time, efficiency in the execution is guaranteed by managing multi-version variables’ lists via non-blocking algorithms. Furthermore, the whole approach is fully transparent, being it based on automatized instrumentation of the application software (particularly ELF objects). Hence the programmer is exposed to the classical (and easy to code) sequential-style programming scheme while accessing any global variable. An experimental assessment of our proposal, based on a suite of case study applications, run on top of an off-the-shelf Linux machine equipped with 32 CPU-cores and 64 GB of RAM, is also presented.
previous article Parallel Implementations of the Cooperative Particle Swarm Optimization on Many-core and Multi-core Architectures
next article Czip: A Fast Lossless Compression Algorithm for Climate Data

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
An anti-event is an exact copy of the corresponding event, or of its digest, except for a single-bit value.
 
2
The only limitation to unbounded speculation is represented by storage constraints for keeping the speculatively processed/produced data records [25].
 
3
Figures are drawn with data taken from http://​www.​top500.​org as of March 2014.
 
4
Thread-local storage data rely on segment registers to identify data positioning in memory. However, thread-local storage is out of the scope of our proposal, due to its non-global nature.
 
5
To check if the space is up, a counter of available free nodes is kept as well in shared memory, which is managed via an atomic decrement operation.
 
6
generate_mark can of course return two equal values when the counter overflows, but this situation can happen after a significant wall-clock-time is elapsed, so we consider it to be statistically non-significant for the ABA problem.
 
7
All the samples reported in the experimental study result as the average over 5 observations collected in different runs and with different seeds for pseudo-random generation.
 
8
Clearly, these synchronization dynamics are mixed with—hence additional to—those already induced via the simulation of the passage of vehicles across different SOBJs.
 
Literature
1.
2.
Adya, A., Liskov, B.: Lazy consistency using loosely synchronized clocks. In: PODC, pp. 73–82 (1997)
3.
Antonacci, F., Pellegrini, A., Quaglia, F.: Consistent and efficient output-stream management in optimistic simulation platform. In: Proceedings of the 2013 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation, pp. 315–326. ACM (2013)
4.
5.
6.
Bauer, D.W., Yaun, G., Carothers, C.D., Yuksel, M., Kalyanaraman, S.: Seven-o’clock: a new distributed gvt algorithm using network atomic operations. In: Proceedings of the 19th Workshop on Parallel and Distributed Simulation, pp. 39–48. IEEE Comp. Soc. (2005)
7.
Bernstein, P.A., Hadzilacos, V., Goodman, N.: Concurrency Control and Recovery in Database Systems. Addison-Wesley Longman Publishing Co. Inc., Boston (1986)
8.
Brown, R.: Calendar queues: a fast O(1) priority queue implementation for the simulation event set problem. Commun. ACM 31, 1220–1227 (1988)CrossRef
9.
Bruce, D.: The treatment of state in optimistic systems. In: Proceedings of the 9th Workshop on Parallel and Distributed Simulation, pp. 40–49. IEEE Comp. Soc. (1995)
10.
Burns, J., Lynch, N.A.: Mutual exclusion using invisible reads and writes. In: Proceedings of the 18th Annual Allerton Conference on Communication, Control, and Computing, pp. 833–842 (1980)
11.
12.
Cai, W., Turner, S.J., Lee, B.S., Zhou, J.: An alternative time management mechanism for distributed simulations. ACM Trans. Model. Comput. Simul. 15(2), 109–137 (2005)CrossRef
13.
Carothers, C.D., Bauer, D.W., Pearce, S.: ROSS: a high performance modular Time Warp system. In: Proceedings of the 14th Workshop on Parallel and Distributed Simulation, pp. 53–60. IEEE Comp. Soc. (2000)
14.
Carothers, C.D., Bauer, D.W., Pearce, S.: ROSS: a high-performance, low-memory, modular time warp system. J. Parallel Distrib. Comput. 62(11), 1648–1669 (2002)CrossRefMATH
15.
Carothers, C.D., Fujimoto, R.M.: Efficient execution of time warp programs on heterogeneous, NOW platforms. IEEE Trans. Parallel Distrib. Syst. 11(3), 299–317 (2000)CrossRef
16.
Carothers, C.D., Perumalla, K.S.: On deciding between conservative and optimistic approaches on massively parallel platforms. In: Winter Simulation Conference, pp. 678–687 (2010)
17.
Carothers, C.D., Perumalla, K.S., Fujimoto, R.M.: Efficient optimistic parallel simulations using reverse computation. ACM Trans. Model. Comput. Simul. 9(3), 224–253 (1999)CrossRef
18.
Case, R.P., Padegs, A.: Architecture of the IBM system/370. Commun. ACM 21, 73–96 (1978)CrossRef
19.
Chandy, K.M., Misra, J.: Distributed simulation: a case study in design and verification of distributed programs. IEEE Trans. Softw. Eng. SE-S 5(5), 440–452 (1979)MathSciNetCrossRefMATH
20.
Chandy, K.M., Sherman, R.: Space–time and simulation. In: Proceedings of the SCS Multiconference on Distributed Simulation, pp. 53–57 (1989)
21.
Chen, L.L., Lu, Y.S., Yao, Y.P., Peng, S.l., Wu, L.D.: A well-balanced time warp system on multi-core environments. In: Proceedings of the 2011 IEEE Workshop on Principles of Advanced and Distributed Simulation, PADS, pp. 1–9. IEEE Comp. Soc. (2011)
22.
Cingolani, D., Pellegrini, A., Quaglia, F.: Transparently mixing undo logs and software reversibility for state recovery in optimistic PDES. In: Proceedings of the 3rd ACM Conference on SIGSIM-Principles of Advanced Discrete Simulation, London, United Kingdom, June 10–12, 2015, pp. 211–222 (2015)
23.
Corporation, I.B.M.: IBM System/370 Extended Architecture, Principles of Operation. IBM Publication No. SA22-7085 (1983)
24.
Cucuzzo, D., D’Alessio, S., Quaglia, F., Romano, P.: A lightweight heuristic-based mechanism for collecting committed consistent global states in optimistic simulation. In: IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications, vol. 0, pp. 227–234. IEEE Comp. Soc., Los Alamitos, CA (2007)
25.
Das, S.R., Fujimoto, R.M.: Adaptive memory management and optimism control in Time Warp. ACM Trans. Model. Comput. Simul. 7(2), 239–271 (1997)CrossRefMATH
26.
Easton, W.B.: Process synchronization without long-term interlock. SIGOPS Oper. Syst. Rev. 6(1/2), 95–100 (1972)CrossRef
27.
Fabbri, A., Donatiello, L.: Sqtw: a mechanism for state-dependent parallel simulation. description and experimental study. In: Proceedings. 11th Workshop on Parallel and Distributed Simulation, 1997, pp. 82–89 (1997). doi:10.​1109/​PADS.​1997.​594590
28.
Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)MathSciNetCrossRefMATH
29.
Fujimoto, R.M.: Parallel discrete event simulation. Commun. ACM 33(10), 30–53 (1990)CrossRef
30.
Fujimoto, R.M.: Performance of Time Warp under synthetic workloads. In: Proceedings of the Multiconference on Distributed Simulation, pp. 23–28. Society for Computer Simulation (1990)
31.
Fujimoto, R.M.: Feature article: Parallel discrete event simulation: Will the field survive? INFORMS J. Comput. 5(3), 213–230 (1993)CrossRef
32.
Fujimoto, R.M.: Exploiting temporal uncertainty in parallel and distributed simulation. In: Proceedings of the 13th Workshop on Parallel and Distributed Simulation, pp. 46–53. IEEE Comp. Soc. (1999)
33.
Fujimoto, R.M., Hybinette, M.: Computing global virtual time in shared-memory multiprocessors. ACM Trans. Model. Comput. Simul. 7(4), 425–446 (1997)CrossRefMATH
34.
Gan, B.P., Low, M.Y.H., Wei, J., Wang, X., Turner, S.J., Cai, W.: Synchronization and management of shared state in HLA-based distributed simulation. In: Proceedings of the 2003 Winter Simulation Conference, vol. 1, pp. 847–854. IEEE Computer Society (2003)
35.
Ghosh, K., Fujimoto, R.M.: Parallel discrete event simulation using space-time memory. In: Proceedings of the 1991 International Conference on Parallel Processing, pp. 201–208 (1991)
36.
Glazer, D.W., Tropper, C.: On process migration and load balancing in time warp. IEEE Trans. Parallel Distrib. Syst. 4(3), 318–327 (1993)CrossRef
37.
Guerraoui, R., Kapalka, M.: On the correctness of transactional memory. In: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP, pp. 175–184. ACM (2008)
38.
Harris, T.: A pragmatic implementation of non-blocking linked-lists. In: Welch, J. (ed.) Distributed Computing. Lecture Notes in Computer Science, vol. 2180, pp. 300–314. Springer, Berlin (2001)
39.
Harris, T.: A pragmatic implementation of non-blocking linked-lists. In: Welch, J. (ed.) Distributed Computing, vol. 2180, pp. 300–314. Springer, Berlin (2001)CrossRef
40.
Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124–149 (1991)CrossRef
41.
Herlihy, M., Shavit, N.: On the nature of progress. In: OPODIS, pp. 313–328 (2011)
42.
Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990)CrossRef
43.
44.
IEEE Std 1516-2000: IEEE Standard for Modeling and Simulation (M&S) High Level Architecture (HLA)—Framework and Rules. Tech. rep., Institute of Electrical and Electronics Engineers, Inc., New York, NY (2000)
45.
IEEE Std 1516.1-2000: IEEE Standard for Modeling and Simulation (M&S) High Level Architecture (HLA)—Federate Interface (FI) Specification. Tech. rep., Institute of Electrical and Electronics Engineers, Inc., New York, NY (2000)
46.
Intel Corporation: IA-32 Intel(R) Architecture Software Developer’s Manual, Volume 2: Instruction Set Reference
47.
48.
Kandukuri, S., Boyd, S.: Optimal power control in interference-limited fading wireless channels with outage-probability specifications. IEEE Trans. Wireless Commun. 1(1), 46–55 (2002)CrossRef
49.
50.
Low, M.Y.H., Gan, B.P., Wei, J., Wang, X., Turner, S.J., Cai, W.: Shared state synchronization for hla-based distributed simulation. Simulation 82(8), 511–521 (2006)CrossRef
51.
Martin, D.E., McBrayer, T.J., Wilsey, P.A.: WARPED: a Time Warp simulation kernel for analysis and application development. In: HICSS ’96: Proceedings of the 29th Hawaii International Conference on System Sciences (HICSS’96) Volume 1: Software Technology and Architecture, p. 383. IEEE Comp. Soc. (1996)
52.
Martin, D.E., McBrayer, T.J., Wilsey, P.A.: WARPED: a time warp simulation kernel for analysis and application development. In: Proceedings of the 29th Hawaii International Conference on System Sciences - Volume 1: Software Technology and Architecture, p. 383. IEEE Computer Society, Washington, DC, USA (1996)
53.
54.
Mehl, H., Hammes, S.: How to integrate shared variables in distributed simulation. SIGSIM Simul. Dig. 25(2), 14–41 (1995)CrossRef
55.
Michael, M.M.: Hazard pointers: Safe memory reclamation for lock-free objects. IEEE Trans. Parallel Distrib. Syst. 15(6), 491–504 (2004)CrossRef
56.
Nicol, D.M., Liu, X.: The dark side of risk (what your mother never told you about time warp). In: Proceedings of the 11th Workshop on Parallel and Distributed Simulation, PADS, pp. 188–195. IEEE Computer Society (1997)
57.
Pellegrini, A.: Hijacker: Efficient static software instrumentation with applications in high performance computing (poster paper). In: Proceedings of the 2013 International Conference on High Performance Computing & Simulation, HPCS, pp. 650–655. IEEE Computer Society (2013)
58.
Pellegrini, A., Quaglia, F.: Transparent multi-core speculative parallelization of DES models with event and cross-state dependencies. In: SIGSIM Principles of Advanced Discrete Simulation, SIGSIM-PADS ’14, Denver, CO, USA, May 18–21, 2014, pp. 105–116 (2014)
59.
Pellegrini, A., Quaglia, F.: Wait-free global virtual time computation in shared memory time warp systems. In: Proceedings of the 29th IEEE International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), Paris, France (2014)
60.
Pellegrini, A., Vitali, R., Quaglia, F.: Autonomic state management for optimistic simulation platforms. IEEE Trans. Parallel Distrib. Syst. 26(6), 1560–1569 (2015)CrossRef
61.
Peluso, S., Didona, D., Quaglia, F.: Supports for transparent object-migration in PDES systems. J. Simul. 6(4), 279–293 (2012)CrossRef
62.
Preiss, B.R., Loucks, W.M., MacIntyre, D.: Effects of the checkpoint interval on time and space in Time Warp. ACM Trans. Model. Comput. Simul. 4(3), 223–253 (1994)CrossRefMATH
63.
Quaglia, F.: A cost model for selecting checkpoint positions in Time Warp parallel simulation. IEEE Trans. Parallel Distrib. Syst. 12(4), 346–362 (2001)CrossRef
64.
65.
Quaglia, F., Santoro, A.: Non-blocking checkpointing for optimistic parallel simulation: description and an implementation. IEEE Trans. Parallel Distrib. Syst. 14(6), 593–610 (2003)CrossRef
66.
Romano, P., Palmieri, R., Quaglia, F., Carvalho, N., Rodrigues, L.E.T.: On speculative replication of transactional systems. J. Comput. Syst. Sci. 80(1), 257–276 (2014)MathSciNetCrossRefMATH
67.
Shavit, N., Touitou, D.: Software transactional memory. In: Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing. PODC ’95, pp. 204–213. ACM, New York, NY (1995)
68.
69.
Vincent, R., Fox, D., Ko, J., Konolige, K., Limketkai, B., Morisset, B., Ortiz, C., Schulz, D., Stewart, B.: Distributed multirobot exploration, mapping, and task allocation. Ann. Math. Artif. Intell. 52(2–4), 229–255 (2008)MathSciNetCrossRefMATH
70.
Vitali, R., Pellegrini, A., Quaglia, F.: Benchmarking memory management capabilities within root-sim. In: Proceedings of the 13th IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications. IEEE Comp. Soc. (2009)
71.
Vitali, R., Pellegrini, A., Quaglia, F.: Load sharing for optimistic parallel simulations on multi core machines. SIGMETRICS Perform. Eval. Rev. 40(3), 2–11 (2012)CrossRef
72.
Wang, J., Jagtap, D., Abu-Ghazaleh, N.B., Ponomarev, D.: Parallel discrete event simulation for multi-core systems: analysis and optimization. IEEE Trans. Parallel Distrib. Syst. 25(6), 1574–1584 (2014)CrossRef
73.
Young, C.H., Radhakrishnan, R., Wilsey, P.A.: Optimism: not just for event execution anymore. In: Proceedings of the Thirteenth Workshop on Parallel and Distributed Simulation, PADS ’99, Atlanta, GA, USA, May 1–4, 1999, pp. 136–143 (1999)
Metadata
Title
Transparent Speculative Parallelization of Discrete Event Simulation Applications Using Global Variables
Authors
Alessandro Pellegrini
Sebastiano Peluso
Francesco Quaglia
Roberto Vitali
Publication date
01-12-2016
Publisher
Springer US
Published in
International Journal of Parallel Programming / Issue 6/2016
Print ISSN: 0885-7458
Electronic ISSN: 1573-7640
DOI
https://doi.org/10.1007/s10766-016-0429-2

Other articles of this Issue 6/2016

International Journal of Parallel Programming 6/2016 Go to the issue

OriginalPaper

A Parallelization Approach for Hard Real-Time Systems and Its Application on Two Industrial Programs

OriginalPaper

A Parallel Yet Pipelined Architecture for Efficient Implementation of the Advanced Encryption Standard Algorithm on Reconfigurable Hardware

OriginalPaper

A Cross-ISA Kernelized High-Performance Parallel Emulator

OriginalPaper

Czip: A Fast Lossless Compression Algorithm for Climate Data

OriginalPaper

Combining Data and Computation Distribution Directives for Hybrid Parallel Programming : A Transformation System

OriginalPaper

Parallel Implementations of the Cooperative Particle Swarm Optimization on Many-core and Multi-core Architectures

Premium Partner

    Image Credits