Dataflow circuits implement a handshake protocol that dynamically determines the execution of circuit components at runtime. They are particularly well-suited for applications with variable-latency operations, where accurate scheduling depends on runtime events such as memory dependencies. Recently, dataflow circuits have gained attention as targets for novel high-level synthesis (HLS) tools and have proven effective in accelerating irregular and control-dominated imperative programs.
A key feature that makes dataflow circuits attractive for HLS is their ability to explicitly represent data-dependent conditionals and loop constructs using specialized, composable components. These components enable explicit steering of data between functional units, thereby capturing runtime decisions of the program's control flow. However, implementing such data steering is nontrivial and can significantly impact not only the correctness of the resulting circuits, but also their performance and area. The primary challenge lies in extracting parallelism from the inherently sequential imperative programs.
The main contribution of this thesis is a set of techniques for exploiting parallelism in dataflow circuits generated from imperative programs through efficient steering of data between functional units. These techniques improve performance while preserving the circuit's original semantics, typically achieving faster execution with modest area overhead and, in some cases, even reduced area.
The thesis is organized into two parts.
In the first part, we present strategies for generating dataflow circuits with efficient data steering logic from imperative programs, exposing parallelism across different control-independent structures within the circuit. We then further refine the steering logic to uncover parallelism between successive invocations of individual components by tagging fine-grained regions of the circuit and applying localized reordering. This approach provides capabilities analogous to out-of-order execution in superscalar processors, yielding substantial performance improvements with modest area overhead. As a result, it broadens the applicability of dataflow circuits---particularly within streaming and multithreaded systems---and enables them to potentially interface with and benefit from out-of-order memory hierarchies.
In the second part, we leverage insights gained from efficiently generating the data steering in dataflow circuits to develop a set of circuit rewrite rules that optimize inefficient steering logic. We introduce two classes of rewrites and formally verify their functional equivalence using two verification techniques. These works represent initial steps toward systematic reasoning about the correctness of dataflow circuits by transforming them into functionally equivalent designs with more efficient data steering.
In short, this thesis identifies efficient data steering as a central mechanism for exploiting parallelism in dataf
