Modeling the consumption of limited resources, e.g., time or energy, plays a central role on the design of reactive systems such as embedded controllers. To this aim, quantitative objectives are defined on game arenas that can be easily modeled as weighted graphs. Instances of these games, called energy games, can be solved in {mathcal {O}(ert {E}ert {ċ }ert {V}ert {ċ }W)}O(|E|·|V|·W) where WW is the maximum weight. Recent work has demonstrated that sequential implementations hardly solve practical instances due to their size and the number of interactions required to converge to a solution. Recent work has demonstrated that sequential implementations hardly solve practical instances. Furthermore, emerging approaches, that have investigated the parallelism of CPUs multi-core and GPU for solving the initial credit problem for energy games, still perform poorly due to the non-trivial characteristics of these graphs. In this article we first describe a revised version of the algorithm on multi-core CPU that obtains a faster convergence time on real-world graphs with up to 30x against the serial implementation by showing good scalability overall. Second, we provide a new GPU-based parallel implementation based on warp-level primitives that allows to reduce the time-to-solution on several instances with up to 3.6x of speed-up against traditional parallel vertex-based approaches. We also discuss a methodology to build synthetic energy games to validate the scalability of parallel algorithms on two totally different settings.

Scalable Energy Games Solvers on GPUs / Formisano, A.; Gentilini, R.; Vella, F.. - In: IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS. - ISSN 1045-9219. - ELETTRONICO. - 32:12(2021), pp. 2970-2982. [10.1109/TPDS.2021.3080925]

Scalable Energy Games Solvers on GPUs

Vella F.
2021-01-01

Abstract

Modeling the consumption of limited resources, e.g., time or energy, plays a central role on the design of reactive systems such as embedded controllers. To this aim, quantitative objectives are defined on game arenas that can be easily modeled as weighted graphs. Instances of these games, called energy games, can be solved in {mathcal {O}(ert {E}ert {ċ }ert {V}ert {ċ }W)}O(|E|·|V|·W) where WW is the maximum weight. Recent work has demonstrated that sequential implementations hardly solve practical instances due to their size and the number of interactions required to converge to a solution. Recent work has demonstrated that sequential implementations hardly solve practical instances. Furthermore, emerging approaches, that have investigated the parallelism of CPUs multi-core and GPU for solving the initial credit problem for energy games, still perform poorly due to the non-trivial characteristics of these graphs. In this article we first describe a revised version of the algorithm on multi-core CPU that obtains a faster convergence time on real-world graphs with up to 30x against the serial implementation by showing good scalability overall. Second, we provide a new GPU-based parallel implementation based on warp-level primitives that allows to reduce the time-to-solution on several instances with up to 3.6x of speed-up against traditional parallel vertex-based approaches. We also discuss a methodology to build synthetic energy games to validate the scalability of parallel algorithms on two totally different settings.
2021
12
Formisano, A.; Gentilini, R.; Vella, F.
Scalable Energy Games Solvers on GPUs / Formisano, A.; Gentilini, R.; Vella, F.. - In: IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS. - ISSN 1045-9219. - ELETTRONICO. - 32:12(2021), pp. 2970-2982. [10.1109/TPDS.2021.3080925]
File in questo prodotto:
File Dimensione Formato  
Scalable_Energy_Games_Solvers_on_GPUs.pdf

Solo gestori archivio

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 4.16 MB
Formato Adobe PDF
4.16 MB Adobe PDF   Visualizza/Apri

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/11572/332868
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 2
social impact