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, speech recognition, fluid flow simulation, etc. A computational approach is composed of many computational tasks, and the time taken to perform a functional task using a computational approach depends on the time taken to process the underlying computational tasks of that computational approach. Furthermore, the time taken to perform a computational task depends on three factors: the computing machine, algorithm and data structures, and the input to the computational task. Improved run time performance for a computational task can be obtained by co-designing algorithm and data structures while being aware of the target computing machine and the input. A computational approach, when applied to a functional task, achieves a certain level of accuracy and takes a certain amount of time to perform. While accuracy is independent of the computing machine, time is dependent on the choice of the computing machine. Hence, better computational approaches can be designed by being aware of the computing machine. The proposed research work is categorized into two themes: 1) Design efficient algorithms and data structures for a computational task on a given instance of (computing machine, input class). 2) Design efficient computational approaches for a functional task on a given computing machine. In these themes, there are choices to be made on the computing machine, computational tasks, and computational approaches. We chose GPU for the computing machine due to its high throughput, high memory bandwidth, and its applicability in accelerating a wide variety of computational tasks from different application domains. We chose sparse matrix operations for the computational tasks, as they play a crucial role in computational approaches that are used to solve problems in application domains like scientific computing, artificial intelligence(AI), and graph analytics. We chose Artificial Neural Networks(ANN) for the computational approach, as it is able to achieve human-level accuracy for many functional tasks in the AI domain. The GPU computing machine and ANN computational approach have kickstarted the AI revolution, and we made these choices because of the opportunity it offers and the potential impact that can be created using our proposed co-design approach.