Communication Optimization in Iterative Numerical Algorithms: An Algorithm-Architecture Interaction
File(s)
Author(s)
Rafique, Abid
Type
Thesis
Abstract
Trading communication with redundant computation can increase the silicon efficiency of common hardware accelerators like FPGA and GPU in accelerating sparse iterative numerical algorithms. While iterative numerical algorithms are extensively used in solving large-scale sparse
linear system of equations and eigenvalue problems, they are challenging to accelerate as they
spend most of their time in communication-bound operations, like sparse matrix-vector multiply (SpMV) and vector-vector operations. Communication is used in a general sense to mean
moving the matrix and the vectors within the custom memory hierarchy of the FPGA and
between processors in the GPU; the cost of which is much higher than performing the actual
computation due to technological reasons. Additionally, the dependency between the operations
hinders overlapping computation with communication. As a result, although GPU and FPGA
are offering large peak floating-point performance, their sustained performance is nonetheless
very low due to high communication costs leading to poor silicon efficiency.
In this thesis, we provide a systematic study to minimize the communication cost thereby
increase the silicon efficiency. For small-to-medium datasets, we exploit large on-chip memory
of the FPGA to load the matrix only once and then use explicit blocking to perform all iterations at the communication cost of a single iteration. For large sparse datasets, it is now
a well-known idea to unroll k iterations using a matrix powers kernel which replaces SpMV
and two additional kernels, TSQR and BGS, which replace vector-vector operations. While this
approach can provide a Θ(k) reduction in the communication cost, the extent of the unrolling
depends on the growth in redundant computation, the underlying architecture and the memory model. In this work, we show how to select the unroll factor k in an architecture-agnostic
manner to provide communication-computation tradeoff on FPGA and GPU. To this end, we
exploit inverse-memory hierarchy of the GPUs to map matrix power kernel and present a new
algorithm for the FPGAs which matches with their strength to reduce redundant computation to allow large k and hence higher speedups. We provide predictive models of the matrix
powers kernel to understand the communication-computation tradeoff on GPU and FPGA. We
highlight extremely low efficiency of the GPU in TSQR due to off-chip sharing of data across
different building blocks and show how we can use on-chip memory of the FPGA to eliminate
this off-chip access and hence achieve better efficiency. Finally, we demonstrate how to compose
all the kernels by using a unified architecture and exploit on-chip memory of the FPGA to share
data across these kernels.
Using the Lanczos Iteration as a case study to solve symmetric extremal eigenvalue
problem, we show that the efficiency of FPGAs can be increased from 1.8% to 38% for small-
to-medium scale dense matrices whereas up to 7.8% for large-scale structured banded matrices.
We show that although GPU shows better efficiency for certain kernels like the matrix powers
kernel, the overall efficiency is even lower due to increase in communication cost while sharing
data across different kernels through off-chip memory. As the Lanczos Iteration is at the heart of
all modern iterative numerical algorithms, our results are applicable to a broad class of iterative
numerical algorithms.
linear system of equations and eigenvalue problems, they are challenging to accelerate as they
spend most of their time in communication-bound operations, like sparse matrix-vector multiply (SpMV) and vector-vector operations. Communication is used in a general sense to mean
moving the matrix and the vectors within the custom memory hierarchy of the FPGA and
between processors in the GPU; the cost of which is much higher than performing the actual
computation due to technological reasons. Additionally, the dependency between the operations
hinders overlapping computation with communication. As a result, although GPU and FPGA
are offering large peak floating-point performance, their sustained performance is nonetheless
very low due to high communication costs leading to poor silicon efficiency.
In this thesis, we provide a systematic study to minimize the communication cost thereby
increase the silicon efficiency. For small-to-medium datasets, we exploit large on-chip memory
of the FPGA to load the matrix only once and then use explicit blocking to perform all iterations at the communication cost of a single iteration. For large sparse datasets, it is now
a well-known idea to unroll k iterations using a matrix powers kernel which replaces SpMV
and two additional kernels, TSQR and BGS, which replace vector-vector operations. While this
approach can provide a Θ(k) reduction in the communication cost, the extent of the unrolling
depends on the growth in redundant computation, the underlying architecture and the memory model. In this work, we show how to select the unroll factor k in an architecture-agnostic
manner to provide communication-computation tradeoff on FPGA and GPU. To this end, we
exploit inverse-memory hierarchy of the GPUs to map matrix power kernel and present a new
algorithm for the FPGAs which matches with their strength to reduce redundant computation to allow large k and hence higher speedups. We provide predictive models of the matrix
powers kernel to understand the communication-computation tradeoff on GPU and FPGA. We
highlight extremely low efficiency of the GPU in TSQR due to off-chip sharing of data across
different building blocks and show how we can use on-chip memory of the FPGA to eliminate
this off-chip access and hence achieve better efficiency. Finally, we demonstrate how to compose
all the kernels by using a unified architecture and exploit on-chip memory of the FPGA to share
data across these kernels.
Using the Lanczos Iteration as a case study to solve symmetric extremal eigenvalue
problem, we show that the efficiency of FPGAs can be increased from 1.8% to 38% for small-
to-medium scale dense matrices whereas up to 7.8% for large-scale structured banded matrices.
We show that although GPU shows better efficiency for certain kernels like the matrix powers
kernel, the overall efficiency is even lower due to increase in communication cost while sharing
data across different kernels through off-chip memory. As the Lanczos Iteration is at the heart of
all modern iterative numerical algorithms, our results are applicable to a broad class of iterative
numerical algorithms.
Version
Open Access
Date Issued
2013-11
Date Awarded
2014-02
Copyright Statement
Attribution NoDerivatives 4.0 International Licence (CC BY-ND)
Advisor
Constantinides, George
Publisher Department
Electrical and Electronic Engineering
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)