Towards general purpose acceleration by exploiting common data-dependence forms

Vidushi Dadu, Jian Weng, Sihao Liu, Tony Nowatzki

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

54 Scopus citations


With slowing technology scaling, specialized accelerators are increasingly attractive solutions to continue expected generational scaling of performance. However, in order to accelerate more advanced algorithms or those from challenging domains, supporting data-dependence becomes necessary. This manifests as either data-dependent control (eg. join two sparse lists), or data-dependent memory accesses (eg. hash-table access). These forms of data-dependence inherently couple compute with memory, and also preclude efficient vectorization - defeating the traditional mechanisms of programmable accelerators (eg. GPUs). Our goal is to develop an accelerator which is broadly applicable across algorithms with and without data-dependence. To this end, we first identify forms of data-dependence which are both common and possible to exploit with specialized hardware: specifically stream-join and alias-free indirection. Then, we create an accelerator with an interface to support these, called the Sparse Processing Unit (SPU). SPU supports alias-free indirection with a compute-enabled scratchpad and aggressive stream reordering and stream-join with a novel dataflow control model for a reconfigurable systolic compute-fabric. Finally, we add robustness across datatypes by adding decomposability across the compute and memory pipelines. SPU achieves 16.5, 10.3, and 14.2 over a 24-core SKL CPU on ML, database, and graph algorithms respectively. SPU achieves similar performance to domain-specific accelerators. For ML, SPU achieves 1.8-7 speedup against a similarly provisioned GPGPU, with much less area and power.

Original languageEnglish (US)
Title of host publicationMICRO 2019 - 52nd Annual IEEE/ACM International Symposium on Microarchitecture, Proceedings
PublisherIEEE Computer Society
Number of pages16
ISBN (Electronic)9781450369381
StatePublished - Oct 12 2019
Event52nd Annual IEEE/ACM International Symposium on Microarchitecture, MICRO 2019 - Columbus, United States
Duration: Oct 12 2019Oct 16 2019

Publication series

NameProceedings of the Annual International Symposium on Microarchitecture, MICRO
ISSN (Print)1072-4451


Conference52nd Annual IEEE/ACM International Symposium on Microarchitecture, MICRO 2019
Country/TerritoryUnited States

Bibliographical note

Publisher Copyright:
© 2019 Association for Computing Machinery.


  • Accelerators
  • Data-dependence
  • Dataflow
  • Generality
  • Indirection
  • Irregularity
  • Join
  • Reconfigurable
  • Systolic

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'Towards general purpose acceleration by exploiting common data-dependence forms'. Together they form a unique fingerprint.

Cite this