Efficient Parallel Algorithms for Sparse Matrix Operations on a GPU with Applications

Abstract

Computational approaches use computing machines to perform functional tasks like image classification, newlinespeech recognition, fluid flow simulation, etc. A computational approach is composed of newlinemany computational tasks, and the time taken to perform a functional task using a computational newlineapproach depends on the time taken to process the underlying computational tasks of that computational newlineapproach. Furthermore, the time taken to perform a computational task depends on three newlinefactors: the computing machine, algorithm and data structures, and the input to the computational newlinetask. Improved run time performance for a computational task can be obtained by co-designing newlinealgorithm and data structures while being aware of the target computing machine and the input. newlineA computational approach, when applied to a functional task, achieves a certain level of accuracy newlineand takes a certain amount of time to perform. While accuracy is independent of the computing newlinemachine, time is dependent on the choice of the computing machine. Hence, better computational newlineapproaches can be designed by being aware of the computing machine. The proposed research newlinework is categorized into two themes: 1) Design efficient algorithms and data structures for newlinea computational task on a given instance of (computing machine, input class). 2) Design efficient newlinecomputational approaches for a functional task on a given computing machine. In these themes, newlinethere are choices to be made on the computing machine, computational tasks, and computational newlineapproaches. We chose GPU for the computing machine due to its high throughput, high memory newlinebandwidth, and its applicability in accelerating a wide variety of computational tasks from different newlineapplication domains. We chose sparse matrix operations for the computational tasks, as they play newlinea crucial role in computational approaches that are used to solve problems in application domains newlinelike scientific computing, artificial intelligence(AI), and graph analytics. We chose Artificial Neural newlineNetworks(ANN) for the computational ap