Predictable accelerator design with time-sensitive affine types

Rachit Nigam, Sachille Atapattu, Samuel Thomas, Zhijing Li, Theodore Bauer, Yuwei Ye, Apurva Koti, Adrian Sampson, Zhiru Zhang

Introduction

High-Level Synthesis (HLS) tools promise to transform high-level C++ code into custom hardware for Field-Programmable Gate Arrays (FPGAs). While this abstraction simplifies development, it often introduces a "black box" effect. Minor code adjustments can trigger complex, opaque heuristics in the compiler, leading to counterintuitive performance drops or bloated resource usage. This paper introduces Dahlia, a programming language designed to eliminate this unpredictability by baking physical hardware constraints directly into its type system.

The Dahlia Methodology

Dahlia's core innovation is the use of time-sensitive affine types. In hardware, resources like memory ports are finite; an affine type system ensures a resource is used at most once. Dahlia extends this by making the system aware of clock cycles.

  1. Affine Resources: Hardware components (e.g., a single-port memory bank) are treated as affine. Attempting to access the same memory twice in a way that exceeds its physical ports results in a compile-time error.
  2. Time-Sensitivity: Resources are not permanently consumed. Dahlia distinguishes between unordered composition (parallel execution where resources cannot be shared) and ordered composition (sequential execution where resources are "refreshed" for reuse).
  3. Memory Views: To support complex access patterns like sliding windows, Dahlia uses "views" to explicitly describe memory partitioning, allowing the type checker to prove the safety of parallel accesses.
Dahlia toolchain compared to a traditional HLS flow.

As shown in the toolchain overview, Dahlia acts as a predictability filter. It validates the program's hardware logic before generating HLS-friendly C++ with the necessary #pragma directives already inserted, bypassing the fragile heuristics of traditional HLS frontends.

Key Insights: Codifying "Unwritten Rules"

The unpredictability of HLS often stems from "unwritten rules." For instance, for a design to be efficient, a loop's unrolling factor must typically divide the memory banking factor. If these don't align, HLS tools silently insert multiplexing logic that degrades performance. Dahlia turns these implicit requirements into explicit type-checking errors. By prioritizing predictability over automation, Dahlia forces developers to design sound hardware architectures from the outset rather than relying on the compiler to "fix" inefficient code.

Key Results and Evaluation

The researchers evaluated Dahlia using the MachSuite benchmark and exhaustive design space exploration (DSE) of a blocked matrix multiplication kernel.

  • Design Space Pruning: In a case study with 32,000 possible configurations, Dahlia's type system rejected over 98% of the space, accepting only 354 (1.1%) configurations.
  • Pareto Optimality: The accepted designs were almost exclusively on the Pareto frontier, representing the optimal trade-offs between execution speed and chip area.
  • Resource Efficiency: When compared to other high-level hardware languages like Spatial, Dahlia-generated designs used up to 10x fewer Look-Up Tables (LUTs) by avoiding the resource-heavy multiplexing logic common in unpredictable designs.
Predictability of hardware resources and runtime using Dahlia.

As illustrated in the performance analysis, Dahlia successfully identifies "Predictable points" (orange triangles) that follow a logical performance trend. It rejects "Unpredictable points" (blue circles) and "Incorrect hardware" (green crosses) that would otherwise lead to erratic runtime or excessive resource consumption.

Limitations and Future Work

While Dahlia significantly improves predictability, it currently operates under a "closed-world" assumption, requiring the entire program for type checking. Future work aims to support modular design and account for "pipelining"—where loop iterations overlap in time. Additionally, the authors envision a future where Dahlia bypasses commercial HLS backends entirely to generate raw Register-Transfer Level (RTL) code, further tightening the link between source code and physical hardware.

Summary updated

BibTeX
@inproceedings{nigam2020predictable,
  author = {Rachit Nigam and Sachille Atapattu and Samuel Thomas and Zhijing Li and Theodore Bauer and Yuwei Ye and Apurva Koti and Adrian Sampson and Zhiru Zhang},
  title = {{Predictable accelerator design with time-sensitive affine types}},
  booktitle = {PLDI},
  year = {2020},
  doi = {10.1145/3385412.3385974},
}
Figure