Communication (data movement) often dominates a computation’s runtime and energy
costs, motivating organizing an algorithm’s operations to minimize communication. We
study communication costs of a class of algorithms including many-body and matrix/tensor
computations and, more generally, loop nests operating on array variables subscripted by
linear functions of the loop iteration vector. We use this algebraic relationship between
variables and operations to derive communication lower bounds for these algorithms. We
also discuss communication-optimal implementations that attain these bounds.
Publications
Tags
2D
Accelerators
Algorithms
Architectures
Arrays
Big Data
Bootstrapping
C++
Cache Partitioning
Cancer
Careers
Chisel
Communication
Computer Architecture
CTF
DIABLO
Efficiency
Energy
FPGA
GAP
Gaussian Elimination
Genomics
GPU
Hardware
HLS
Lower Bounds
LU
Matrix Multiplication
Memory
Multicore
Oblivious
Open Space
OS
Parallelism
Parallel Reduction
Performance
PHANTOM
Processors
Python
Research Centers
RISC-V
SEJITS
Tall-Skinny QR
Technical Report
Test generation