The increasing diffusion of shared-memory multi core machines has given rise to a change in the design of Parallel Discrete Event Simulation (PDES) platforms. In particular, the possibility to share large amounts of memory by many worker threads has lead to a boost in the adoption of non-blocking coordination algorithms, which have been proven to offer higher scalability when compared to their blocking counterparts based on critical sections. In this article we present an innovative non-blocking algorithm for computing Global Virtual Time (GVT) namely, the current commit horizon in multi-thread PDES engines to be run on top of multi-core machines. Beyond being non-blocking, our proposal has the advantage of providing a logarithmic (rather than linear) number of per-thread memory operations read/write operations of values involved in the reduction for computing the GVT value vs the amount of threads participating in the GVT computation. This allows for keeping low the actual CPU time that is required for determining the new GVT value. We compare our algorithm with a literature solution, still based on the non-blocking approach, but entailing a linear number of memory operations, quantifying the advantages from our proposal especially for very large numbers of threads participating in the GVT computation.

Ianni, M., Marotta, R., Pellegrini, A., Quaglia, F. (2017). A Non-blocking Global Virtual Time Algorithm with Logarithmic Number of Memory Operations. In Proceedings of the IEEE/ACM 21st International Symposium on Distributed Simulation and Real Time Applications (DS-RT) (pp.17-24). 345 E 47TH ST, NEW YORK, NY 10017 USA : IEEE [10.1109/DISTRA.2017.8167662].

A Non-blocking Global Virtual Time Algorithm with Logarithmic Number of Memory Operations

Ianni, M;Marotta, R;Pellegrini, A;Quaglia, F
2017-10-01

Abstract

The increasing diffusion of shared-memory multi core machines has given rise to a change in the design of Parallel Discrete Event Simulation (PDES) platforms. In particular, the possibility to share large amounts of memory by many worker threads has lead to a boost in the adoption of non-blocking coordination algorithms, which have been proven to offer higher scalability when compared to their blocking counterparts based on critical sections. In this article we present an innovative non-blocking algorithm for computing Global Virtual Time (GVT) namely, the current commit horizon in multi-thread PDES engines to be run on top of multi-core machines. Beyond being non-blocking, our proposal has the advantage of providing a logarithmic (rather than linear) number of per-thread memory operations read/write operations of values involved in the reduction for computing the GVT value vs the amount of threads participating in the GVT computation. This allows for keeping low the actual CPU time that is required for determining the new GVT value. We compare our algorithm with a literature solution, still based on the non-blocking approach, but entailing a linear number of memory operations, quantifying the advantages from our proposal especially for very large numbers of threads participating in the GVT computation.
21st IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications
Roma
2017
ACM
Rilevanza internazionale
ott-2017
Settore ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
English
Intervento a convegno
Ianni, M., Marotta, R., Pellegrini, A., Quaglia, F. (2017). A Non-blocking Global Virtual Time Algorithm with Logarithmic Number of Memory Operations. In Proceedings of the IEEE/ACM 21st International Symposium on Distributed Simulation and Real Time Applications (DS-RT) (pp.17-24). 345 E 47TH ST, NEW YORK, NY 10017 USA : IEEE [10.1109/DISTRA.2017.8167662].
Ianni, M; Marotta, R; Pellegrini, A; Quaglia, F
File in questo prodotto:
File Dimensione Formato  
Ian17b.pdf

solo utenti autorizzati

Tipologia: Documento in Post-print
Licenza: Copyright dell'editore
Dimensione 728.3 kB
Formato Adobe PDF
728.3 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/200452
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 6
social impact