Reconfigurable dataflow accelerators (CGRAs) are blazing fast on REGULAR parallelism because they wire the hardware to match a program's repeated communication pattern, but they choke on TASK-parallel workloads — graph algorithms, sparse math, nearest-neighbor search — where work is spawned dynamically and, once tasks are handed to cores as independent black boxes, all the structure BETWEEN tasks (which ones pipeline into each other, which ones read the same data, which ones are big) is flattened away and lost; TaskStream (UCLA) makes tasks and their dependence edges first-class in the hardware, annotating each edge with a little metadata so the accelerator can RECOVER that lost structure — balancing load by a work hint, streaming a producer's output straight into its consumers instead of through memory, and multicasting one memory fetch to all the tasks that share it — for a 2.2x speedup over an equivalent structure-blind accelerator at just 3.6% extra chip area.
The argument in one glance
-
Problem
Dataflow accelerators are fast because they exploit structure — which task parallelism hides
Reconfigurable dataflow accelerators and CGRAs (coarse-grained reconfigurable arrays) get their enormous efficiency by configuring the hardware to match a program's STRUCTURE: they wire a dedicated path between two instructions that always communicate (exploiting the temporal structure of a repeated pattern), and they run many identical operations at once as a vector (exploiting spatial structure). This is a spectacular fit for REGULAR parallelism — dense loops, streaming pipelines — where the pattern is fixed and known ahead of time. But an enormous class of real workloads is TASK-parallel: graph algorithms, sparse linear algebra, nearest-neighbor search, where the work is created and scheduled dynamically at runtime based on the data. These workloads do not hand the hardware a fixed pattern to configure to, and that is exactly what these accelerators need.
-
What people did
Add a task model — spawn tasks and schedule them to cores
The natural fix is to give the accelerator a task model, borrowed from CPUs and GPUs: let the program dynamically SPAWN tasks, and have a scheduler assign each task to whichever execution resource is free. This buys the three things task parallelism is good for — dynamic work creation based on runtime logic, load balancing when task sizes vary, and running different task types concurrently on heterogeneous resources. Spawn tasks, hand them to cores, and the accelerator can finally handle irregular, dynamic work.
-
Why it fell short
Independent tasks throw away the structure the accelerator lives on
The catch is that scheduling tasks INDEPENDENTLY flattens away all the structure BETWEEN them — and that inter-task structure is precisely what a dataflow accelerator needs to be fast. Three kinds vanish. PIPELINING: when one task produces data that ordered consumer tasks need, independent scheduling forces that data out through slow shared memory instead of streaming it directly task-to-task. READ-SHARING: when many tasks read the same data, independent scheduling fetches it redundantly instead of multicasting one fetch to all. LOAD BALANCE: when tasks are different sizes, distributing them uniformly leaves some cores idle while others grind. On top of this, naive task scheduling causes excess reconfiguration and high-latency memory traffic. The task model recovers dynamism but destroys the very structure the hardware was built to exploit.
-
This paper's idea
Make tasks and their dependences first-class, and recover the structure
TaskStream (UCLA — Dadu and Nowatzki) makes TASKS and their communication structure FIRST-CLASS primitives in the hardware. Instead of opaque independent tasks, it annotates the dependence EDGES between tasks with a little metadata, so the accelerator can RECOVER the inter-task structure it would otherwise never see. A CREATION edge carries a sizehint (relative work), enabling work-aware load balancing. A STREAMING edge carries which producer instance feeds which consumer, enabling a direct data pipeline between tasks that bypasses memory. A BATCHING edge carries an identifier for shared read data, enabling co-scheduling and MULTICAST of one fetch to many tasks. Layered as a hierarchical dataflow model (tasks over instruction-level dataflow), it recovers pipelining, read-sharing, and load balance at extremely low cost: a 2.2x speedup over an equivalent structure-blind accelerator, for only 3.6% extra area.
Why this problem is worth solving
Dataflow accelerators are among the most efficient ways to
compute, but their efficiency is conditional on the program handing
them structure to lock onto, and task-parallel programs seem to
withhold it. The efficiency comes from exploiting
the two kinds
of regularity a dataflow accelerator configures itself to. TEMPORAL
structure is a communication pattern that repeats over time: if two
instructions always pass a value to each other every iteration, the
hardware wires a dedicated path between them once and reuses it,
avoiding any general-purpose routing. SPATIAL structure is
operations that can happen at the same time: if the same operation
applies to many data elements, the hardware runs them together as a
vector. Both must be known and fixed so the accelerator can be
CONFIGURED to them ahead of execution — the configuration is the
source of the speed, and it assumes the pattern will hold
The subtle point TaskStream makes is that task-parallel programs
DO have exploitable structure — it is just structure that lives
BETWEEN tasks, and a naive task model discards it at exactly the
moment of scheduling. The loss happens through
the act of
treating each spawned task as an opaque, self-contained unit of
work to be placed on whatever resource is free, with no recorded
relationship to the tasks around it. This is what a conventional
task scheduler does, and it is convenient — but it erases three
relationships the hardware could have used. It erases which task
PIPELINES into which (so a producer’s output, which could have
streamed straight to its consumer, is instead dumped to shared
memory and read back). It erases which tasks SHARE a read (so the
same data is fetched from memory once per task instead of fetched
once and multicast). And it erases which tasks are LARGE (so
variable work is spread blindly and unevenly). The information
existed in the program; scheduling threw it away
What people did before, and where it broke
- Regular-only dataflow accelerators / CGRAs. Configure the hardware to a fixed, known communication pattern and stream data through. Superbly efficient on dense, regular parallelism, but they simply cannot express workloads whose work is created and shaped at runtime, so task-parallel programs are off-limits.
- Bolt a conventional task model onto the accelerator. Spawn tasks dynamically and schedule each independently to a free resource (the CPU/GPU approach). This recovers dynamism, but by scheduling tasks as opaque units it flattens away inter-task pipelining, read-sharing, and size information — the structure the accelerator needs — so it wastes memory traffic and imbalances load.
- Shared-memory inter-task communication. Let tasks communicate by writing and reading shared memory. Correct and general, but every producer-to-consumer handoff becomes a high-latency memory round trip, and every shared read is fetched redundantly, throttling exactly the pipelined and read-sharing patterns that are common in these workloads.
- Specialized graph or sparse accelerators. Hard-wire one irregular pattern (say, graph traversal) into custom hardware. Fast for that pattern, but narrow — a new task-parallel workload needs a new accelerator, whereas the goal is one flexible dataflow fabric that handles many.
- The gap. No prior model let a general reconfigurable dataflow accelerator both express dynamic task parallelism AND recover the inter-task structure (pipelining, read-sharing, load balance) that independent scheduling destroys. TaskStream does both by making tasks and their dependence edges first-class and annotating them with just enough metadata.
How TaskStream works
Type the task edges, recover the structure, and execute hierarchically
-
Model the program as a task graph with typed edges new
Tasks become first-class primitives, and the dependences between them are explicit, TYPED edges carrying metadata: creation edges (spawning), streaming edges (pipelined producer-to-consumer data), and batching edges (shared reads). This exposed structure is what the hardware will exploit — the program tells the accelerator not just what tasks exist but how they relate.
-
Load-aware creation with a size hint new
A creation edge can carry a sizehint — a task argument indicating relative work per instance. The task scheduler routes each new task to the core with the least accumulated work, then adds this task's hint to that core's counter. Variable-sized tasks (like the differently-sized tiles of a triangular matrix in Cholesky) are balanced instead of spread blindly.
-
Streaming recovery: pipeline through ports, not memory new
A streaming edge carries which producer instance feeds which consumer (a dependence distance) and how many bytes. The producer and its consumer tasks are scheduled concurrently, and the producer's output flows directly from its output ports into the consumer's input ports — bypassing shared memory entirely. A reduction that once had every core update a shared variable through memory now pipelines partial results core-to-core.
-
Batching recovery: multicast one fetch to many tasks new
A batching edge tags a task with a DataID for the shared data it reads. Tasks with the same DataID are held in a CAM-indexed buffer and, once enough are ready, co-scheduled across cores so a SINGLE memory fetch is multicast to all of them. In nearest-neighbor search, queries hitting the same leaf node are reordered to run together; in a GCN, all tasks reading the same weight matrix share one fetch.
-
Execute as hierarchical dataflow new
TaskStream sits atop a decoupled-dataflow ISA: the high level is the task graph, and each task is itself a graph of dataflow instructions and memory streams with FIFO ports. When a task is scheduled its inputs arrive at its ports and trigger instruction-level execution — and task-level and instruction-level work overlap, so the next task prefetches its memory while the current one computes and the prior one streams out its results.
-
Add cheap hardware, and keep it deadlock-free new
The additions are small: a task creation unit (an SRAM argument buffer with a scheduler), a task batching unit (a banked SRAM plus a CAM to detect duplicate DataIDs), and a stream table tracking active streams — 3.6% area total. Deadlock is prevented structurally: self-loop streams put producer and consumer instances in mutually-exclusive virtual partitions, and multicast acquires ports in core-ID order to avoid cycles.
The idea
Do not discard the structure the program already has — expose it and let the hardware recover it. A task-parallel program knows which tasks feed which, which tasks read the same data, and which tasks are big, but a conventional scheduler throws all of that away the instant it treats each task as an independent unit. TaskStream’s central move is to REIFY that inter-task structure — make tasks and their dependence edges first-class objects the hardware can see — by annotating each edge with a few bytes of metadata. Once the structure is visible, the accelerator can act on it. This is the reify-the-implicit discipline the site rewards again and again: the GNN-operator page turns a scheduling decision into a selectable object, the tensor-program page makes task mapping first-class, the heterogeneous-serving page literally “recovers” structure by casting serving as a graph — and here a task scheduler stops flattening the program into black boxes and instead carries the relationships forward so they can be exploited. The information was always there; the contribution is refusing to lose it.
Keep the data on the chip — stream it and share it instead of routing it through memory. Two of the three recoveries are really about the same thing: not sending data on a needless trip to memory. Streaming recovery pipelines a producer’s output directly into its consumers’ ports, so a producer-consumer handoff never touches shared memory. Batching recovery multicasts a single fetch to every task that reads the same data, so shared reads are fetched once rather than once per task. The result is that more than half of what would have been memory traffic becomes on-chip network traffic. This is the keep-data-off-the-memory-path discipline the site keeps meeting — the persistent-memory KV-store page merging by pointers instead of copying, the GPU-microservice page passing a handle instead of a tensor — with multicast adding the amortize-one-fetch- across-many-consumers twist that turns redundant loads into shared reuse.
A tiny hint beats a blind heuristic when the program knows something the hardware cannot infer. The sizehint is a single number, but it converts blind round-robin scheduling into work-aware load balancing, because the program knows a task’s relative size and the hardware, seeing only opaque tasks, does not. The whole philosophy is this trade: the program pays a small annotation cost to hand the hardware information it could not otherwise recover, and the hardware turns that information into pipelining, multicast, and balance. It is the same cheap-hint-beats-expensive-guessing logic the site sees when a scheduler is fed a work estimate or a locality hint — and TaskStream measures it directly, with sizehint beating round-robin by 1.63x on Cholesky while a purely spatial hint barely helps and can even restrict balancing.
Three kinds of structure a naive task model throws away
What independent scheduling loses, and how TaskStream recovers it
Task-parallel workloads on a dataflow accelerator. Numbers from TaskStream's evaluation.
Step 1 of 5
Tasks handed to cores as black boxes
A conventional task model spawns tasks and schedules each independently onto a free core. The accelerator sees a stream of opaque work units with no recorded relationships, so it cannot tell which tasks pipeline, which share reads, or which are large — the very structure a dataflow fabric configures itself to exploit is invisible.
the three benefits sought — dynamic creation, load balance, heterogeneity — come at the cost of lost structure naive scheduling also causes excess reconfiguration and high-latency shared-memory traffic
Why it works
- Dataflow accelerators run fast only by exploiting program structure, and independent task scheduling flattens inter-task structure away → making tasks and their dependence edges first-class lets the hardware see that structure → it can configure to the pipelining and sharing it was blind to.
- A producer-to-consumer handoff through shared memory is a slow round trip → a streaming edge pipes the producer’s output directly into concurrently-scheduled consumers’ ports → the memory round trip vanishes and data stays on-chip.
- Many tasks reading the same data fetch it redundantly → a batching edge groups same-DataID tasks via a CAM and multicasts one fetch to all → over half of memory traffic becomes on-chip network traffic and redundant loads collapse.
- The program knows each task’s relative size but the hardware, seeing opaque tasks, cannot → a one-number sizehint lets the scheduler route each task to the least-loaded core → variable work is balanced, beating round-robin by 1.63x on Cholesky.
- The recovered structure raises how busy the cores are → core utilization climbs 3 to 7x → the accelerator finally runs irregular task-parallel work near its regular-workload efficiency, at 3.6% area.
What it costs
- The programmer must expose the structure. TaskStream frees the programmer from manual scheduling but requires them to identify task types, dependence edges and their kinds, and the hints (sizehint, dependence distance, DataID). It is not onerous (tiled Cholesky is 210 lines versus 163 for static-parallel), but it is real annotation work.
- No compiler yet. Automating the extraction of tasks and edge types from a high-level language is future work, and dynamic dependences (sparse, kNN) may always need programmer annotation, so today the structure is hand-supplied.
- Task granularity is a manual trade-off. Small tasks incur management overhead; large tasks are hard to load-balance. There is no automatic granularity selection — the programmer tunes it.
- Batching needs reorderable tasks. Multicast recovery works by reordering tasks so same-data readers run together, which is only valid when tasks are commutative or order-independent; strictly ordered workloads cannot batch, and a small CAM bounds how many distinct shared-read patterns can be tracked.
- It only helps where inter-task structure exists. The three recoveries do not cover every irregular pattern, and where a workload’s reuse is already captured statically (SpMM’s outer-product tiling) TaskStream adds nothing — its 1.0x on SpMM is an honest reminder that structure recovery pays only where structure was being lost.
The evaluation
Five task-parallel workloads — nearest-neighbor search (kNN), tiled Cholesky factorization, a database-plus-ML join/kmeans pipeline, sparse matrix multiply (SpMM), and a graph convolutional network (GCN) — on the Delta dataflow accelerator (16 cores, 28nm, 256 GB/s), compared against an equivalent static-parallel CGRA and a 24-core CPU with optimized libraries.
Running task-parallel work on a dataflow accelerator
| Property | Static-parallel CGRA | Independent tasks (structure lost) | TaskStream (structure recovered) |
|---|---|---|---|
| Dynamic work creation | |||
| Load balance (variable sizes) | |||
| Pipelined dependence | |||
| Shared reads | |||
| Speedup / area |
Check yourself
Check your understanding
1. Adding a conventional task model lets a dataflow accelerator handle dynamic, irregular work — yet the paper says scheduling tasks independently destroys the accelerator's advantage. Predict why.
2. TaskStream's core move is to annotate task dependence EDGES with metadata (sizehint, dependence distance, DataID) rather than optimizing tasks in isolation. Predict why edge annotation is the right abstraction.
3. Two of TaskStream's three recoveries — streaming and batching — both cut memory traffic, converting over half of it to on-chip network traffic. Predict what these two mechanisms have in common.
4. TaskStream gives 1.8-2.2x on kNN and Cholesky and a large boost on GCN, but exactly 1.0x (no improvement) on SpMM. Predict what the SpMM result reveals about when structure recovery helps.
Sources
- ACM DL: TaskStream: Accelerating Task-Parallel Workloads by Recovering Program Structure — ASPLOS 2022 (full text read via the ACM PDF; no arXiv preprint).