Accelerating Energy Games Solvers on Modern Architectures

Andrea Formisano, Raffaella Gentilini, Flavio VellaIa3@sc 2017 · DOI

Introduction

In the domain of reactive systems—ranging from autonomous Mars rovers to automated factory controllers—ensuring that a system can operate indefinitely within strict energy constraints is a fundamental challenge. Energy Games provide the mathematical foundation for modeling these requirements. This research presents the first GPU-based solvers for these games, leveraging massively parallel architectures to achieve significant performance improvements over traditional sequential methods.

What Problem Does This Paper Address?

Energy Games are played by two players on a weighted directed graph. One player represents the system, while the other represents the environment. The system's goal is to maintain a non-negative running sum of weights (the energy level), while the environment attempts to force this sum below zero.

Figure 1: A sample energy game graph showing vertices for two players (circles and squares) and weighted edges.

The primary computational challenge is the initial credit problem: determining the minimum starting energy required for the system to survive indefinitely. Sequential algorithms for this problem have a complexity of $O(EVW)$, where $V$ is the number of vertices, $E$ is the number of edges, and $W$ is the maximum weight. As system models grow in complexity, these sequential solvers become a significant bottleneck in the design cycle.

Methodology: Parallelizing the Energy Progress Measure

The researchers focused on parallelizing the "Energy Progress Measure" (EPM) algorithm. This algorithm utilizes a lifting operator that iteratively updates the energy values required for each vertex until a stable fixpoint is reached. Because the lifting operator is monotonic—values only ever increase—it is inherently suited for parallel execution without the need for complex locking mechanisms.

Three parallel strategies were developed:

  1. Multi-core CPU (OpenMP): Distributes lifting operations across standard CPU cores.
  2. Vertex-Parallel GPU (GPU-v): A CUDA implementation assigning one thread per vertex.
  3. Warp-Centric GPU (GPU-w): A sophisticated CUDA approach where a 32-thread "warp" collaborates on a single vertex. This method uses warp-shuffle operations to optimize data movement and better handle vertices with high degrees of connectivity.

To further optimize performance, the team employed Compressed Sparse Row (CSR) and Compressed Sparse Column (CSC) data structures and implemented vertex sorting to minimize thread divergence.

Key Results and Insights

The solvers were evaluated against a benchmark of over 1,000 real-world game instances derived from equivalence and model checking tasks.

  • Significant Speedups: The GPU-based solvers achieved up to a 36x speedup over sequential CPU implementations. Even when compared to an optimized 8-core CPU solver, the GPU versions remained up to 5x faster.
  • Warp-Centric Efficiency: The warp-centric approach (GPU-w) proved superior to the naive vertex-parallel approach (GPU-v), offering an average 1.7x performance boost by balancing workloads more effectively across threads.
  • Scalability on Hard Instances: The parallel solvers demonstrated their greatest value on "hard" instances—complex graphs where sequential solvers typically timed out.

Conclusion

This work demonstrates that modern parallel hardware can drastically reduce the time required to solve Energy Games. While the overhead of GPU data transfer can make these solvers less efficient for very small graphs, they provide a transformative speedup for the large-scale models encountered in modern system verification. Future research will explore graph topology analysis to automatically select the optimal parallel strategy and investigate the use of Strongly Connected Component (SCC) decomposition to further accelerate convergence.

Summary updated

BibTeX
@inproceedings{formisano2017accelerating,
  author = {Andrea Formisano and Raffaella Gentilini and Flavio Vella},
  title = {{Accelerating Energy Games Solvers on Modern Architectures}},
  booktitle = {Ia3@sc},
  year = {2017},
  doi = {10.1145/3149704.3149771},
}
Figure