GPU-LMDDA: a bit-vector GPU-based deadlock detection algorithm for multi-unit resource systems. Issue 6 (1st November 2016)

• Record Type: Journal Article
• Authors: Abell, Stephen; Do, Nhan; Lee, John Jaehwan
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 31:Issue 6(2016)
• Page Start: 562
• Page End: 590
• Publication Date: 2016-11-01
• Subjects: Deadlock detection -- resource allocation graph (RAG) -- GPU -- CUDA -- bit vector; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2016.1140761
• Languages: English
• ISSNs: 1744-5760

Abstract

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.