GPU-LMDDA: a bit-vector GPU-based deadlock detection algorithm for multi-unit resource systems

Abstract

This article presents the detailed description of a GPU-based multi-unit deadlock detection methodology, GPU-LMDDA with 12 pieces of pseudo code. Our design utilises the massively parallel hardware of the GPU to perform computations of deadlock detection in multi-unit resource systems. As a result, it is able to overcome the major limitations of prior software and hardware-based solutions by handling thousands of processes and resources concurrently. GPU-LMDDA employs a bit-vector technique with a novel bit-matrix multiplication algorithm to store and perform computations on algorithm matrices, thus decreasing the memory footprint and maximizing throughput. Our design treats deadlock detection as a service to the operating system by requiring minimal interaction with the CPU. By treating deadlock detection as an interactive service, all matrix management and algorithm computation are handled by the GPU, freeing CPU compute cycles. Our algorithm is implemented on three GPU cards: Tesla C2050, Tesla K20c, and Titan X, which showed speedups of 3-434X against single-threaded CPU equivalents.

Graphical Abstract

As an interactive service to the CPU and with bit-vector technique, GPU-LMDDA provides significant speedups against CPU implementation for increasing number of resources and processes.

Keywords:

• Deadlock detection
• resource allocation graph (RAG)
• GPU
• CUDA
• bit vector

Notes

No potential conflict of interest was reported by the authors.