GPU-OSDDA: a bit-vector GPU-based deadlock detection algorithm for single-unit resource systems. Issue 5 (2nd September 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 5(2016)
• Page Start: 450
• Page End: 468
• Publication Date: 2016-09-02
• 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.2015.1100301
• Languages: English
• ISSNs: 1744-5760

Abstract

Abstract : This article presents a GPU-based single-unit deadlock detection methodology and its algorithm, GPU-OSDDA. Our GPU-based design utilizes parallel hardware of GPU to perform computations and thus is able to overcome the major limitation of prior hardware-based approaches by having the capability of handling thousands of processes and resources, whilst achieving real-world run-times. By utilizing a bit-vector technique for storing algorithm matrices and designing novel, efficient algorithmic methods, we not only reduce memory usage dramatically but also achieve two orders of magnitude speedup over CPU equivalents. Additionally, GPU-OSDDA acts as an interactive service to the CPU, because all of the aforementioned computations and matrix management techniques take place on the GPU, requiring minimal interaction with the CPU. GPU-OSDDA is implemented on three GPU cards: Tesla C2050, Tesla K20c, and Titan X. Our design shows overall speedups of 6-595X over CPU equivalents.