Max-plus matrix multiplication library for GPUs - MPMML
Date
2019
Authors
Ghalsasi, Prerana Prakash, author
Rajopadhye, Sanjay, advisor
Bohm, Wim, committee member
Pasricha, Sudeep, committee member
Journal Title
Journal ISSN
Volume Title
Abstract
Max-Plus algebra finds its applications in discrete event simulations, dynamic programming, biological sequence comparisons etc. Although there exist highly tuned libraries like CUDA Linear Algebra Subprograms (CuBLAS) [1] for matrix operations, they implement the standard matrix-multiplication (multiply-add) for floating points. We found no standard library for Max- Plus-Matrix-Multiplication (MPMM) on integers. Hence,we developed a highly tuned parallelized MPMM library kernel. We chose GPUs as hardware platform for this work because of their significantly more parallelism and arithmetic functional units as compared to CPUs. We designed this kernel to be portable across three successive Nvidia GPU architectures and it achieves performance in the range 3065 GOPs/S - 3631 GOPs/S on all of these architectures. We closely followed the benchmarking approach described by Volkov et al. [2] when they contributed to cuBLAS. This MPMM kernel can be part of a max-plus algebra library for GPUs and can help speed up Biological Sequence comparison applications like BPMax.
Description
Rights Access
Subject
matrix multiplication
tropical algebra
max-plus algebra
GPUs