A hybrid systolic-dataflow architecture for inductive matrix algorithms

Jian Weng, Sihao Liu, Zhengrong Wang, Vidushi Dadu, Tony Nowatzki

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

44 Scopus citations

Abstract

Dense linear algebra kernels are critical for wireless, and the oncoming proliferation of 5G only amplifies their importance. Due to the inductive nature of many such algorithms, parallelism is difficult to exploit: parallel regions have fine-grain producer/consumer interaction with iteratively changing depen-dence distance, reuse rate, and memory access patterns. This makes multi-threading impractical due to fine-grain synchronization, and vectorization ineffective due to the non-rectangular iteration domain. CPUs, DSPs, and GPUs perform order-of-magnitude below peak. Our insight is that if the nature of inductive dependences and memory accesses were explicit in the hardware/software interface, then a spatial architecture could efficiently execute parallel code regions. To this end, we first develop a novel execution model, inductive dataflow, where inductive dependence patterns and memory access patterns (streams) are first-order primitives. Second, we develop a hybrid spatial architecture combining systolic and tagged dataflow execution to attain high utilization at low energy and area cost. Finally, we create a scalable design through a novel vector-stream control model which amortizes control overhead both in time and spatially across architecture lanes. We evaluate our design, REVEL, with a full stack (compiler, ISA, simulator, RTL). Across a suite of linear algebra kernels, REVEL outperforms equally-provisioned DSPs by 4.6×-37×. Compared to state-of-the-art spatial architectures, REVEL is mean 3× faster. Compared to a set of ASICs, REVEL is only 2× the power and half the area.

Original languageEnglish (US)
Title of host publicationProceedings - 2020 IEEE International Symposium on High Performance Computer Architecture, HPCA 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages703-716
Number of pages14
ISBN (Electronic)9781728161495
DOIs
StatePublished - Feb 2020
Event26th IEEE International Symposium on High Performance Computer Architecture, HPCA 2020 - San Diego, United States
Duration: Feb 22 2020Feb 26 2020

Publication series

NameProceedings - 2020 IEEE International Symposium on High Performance Computer Architecture, HPCA 2020

Conference

Conference26th IEEE International Symposium on High Performance Computer Architecture, HPCA 2020
Country/TerritoryUnited States
CitySan Diego
Period02/22/2002/26/20

Keywords

  • Digital Signal Processor
  • Reconfigurable Accelerator
  • Software/Hardware Codesign
  • Spatial Architecture

ASJC Scopus subject areas

  • Artificial Intelligence
  • Hardware and Architecture
  • Safety, Risk, Reliability and Quality

Fingerprint

Dive into the research topics of 'A hybrid systolic-dataflow architecture for inductive matrix algorithms'. Together they form a unique fingerprint.

Cite this