Dynamic Loop Fusion in High-Level Synthesis

Robert Szafarczyk, Syed Waqar Nabi, Wim Vanderbauwhede · 2025

Read Dynamic Loop Fusion in High-Level Synthesis by Robert Szafarczyk, Syed Waqar Nabi, Wim Vanderbauwhede (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-14631.txt.

Introduction

Robert Szafarczyk, Syed Nabi, and Wim Vanderbauwhede let sibling loops run at once in chip design tools in a paper from two thousand twenty-five. High-level synthesis turns code into circuits. Irregular code with many sibling loops is common, but tools run those loops one after another.

Their dynamic loop fusion is a joint compiler and hardware design. It needs only that memory addresses never decrease inside inner loops. A fresh schedule, borrowed from polyhedral compiler ideas, checks addresses on the fly without searching past history. Tests showed average speedups of fourteen-fold over static synthesis and four-fold over dynamic synthesis. The authors present it as a fix for a long-standing bottleneck.

Catalog record

CREATORRobert Szafarczyk, Syed Waqar Nabi, Wim Vanderbauwhede
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-14631

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Dynamic Loop Fusion in High-Level Synthesis Robert Szafarczyk, Syed Waqar Nabi, Wim Vanderbauwhede Abstract . Dynamic High-Level Synthesis (HLS) uses additional hardware to perform memory disambiguation at runtime, increasing loop throughput in irregular codes compared to static HLS. However, most irregular codes consist of multiple sibling loops, which currently have to be executed sequentially by all HLS tools. Static HLS performs loop fusion only on regular codes, while dynamic HLS relies on loops with dependencies to run to completion before the next loop starts. We present dynamic loop fusion for HLS, a compiler/hardware co-design approach that enables multiple loops to run in parallel, even if they contain unpredictable memory dependencies. Our only requirement is that memory addresses are monotonically non-decreasing in inner loops. We present a novel program-order schedule for HLS, inspired by polyhedral compilers, that together with our address monotonicity analysis enables dynamic memory disambiguation that does not require searching of address histories and sequential loop execution. Our evaluation shows an average speedup of 14 × \times over static and 4 × \times over dynamic HLS. Conference: Proceedings of the 2025 ACM/SIGDA International Symposium on Field Programmable Gate Arrays; February 27–March 1, 2025; Monterey, CA, USA Proceedings of the 2025 ACM/SIGDA International Symposium on Field Programmable Gate Arrays (FPGA ’25), February 27–March 1, 2025, Monterey, CA, USA DOI: 10.1145/3706628.3708871 ISBN: 979-8-4007-1396-5/25/02 CCS: Computer systems organization Reconfigurable computing CCS: Software and its engineering Compilers 1. Introduction for (i = 0; i < N; ++i) A[f(i)] = workA(A[f(i)]); for (j = 0; j < M; ++j) B[g(j)] = workB(A[g(j)]); (a) Two loops with non-affine access patterns. (b) Pipeline achieved by current static and dynamic HLS tools. (c) Pipeline achieved by our work. Figure 1 . Dynamic Loop Fusion enables fine-grained parallelism across loops with memory dependencies. Three sub-figures. Sub-figure a shows motivating C code. Sub-figures b shows the pipeline generated by current tools. Sub-figures c shows the pipeline generated by our work. Three sub-figures. Sub-figure a shows motivating C code. Sub-figures b shows the pipeline generated by current tools. Sub-figures c shows the pipeline generated by our work. High-Level Synthesis (HLS) increases designer productivity, makes code more maintainable, accelerates verification, and makes design space exploration easier ( Ranganathan et al., 2021 ) . However, this is usually only true for regular codes where the compiler can discover instruction- and memory-level parallelism statically ( Rau, 1994 ; Canis et al., 2014 ) . Domains like graph analytics and sparse linear algebra contain irregular codes with unpredictable memory dependencies and control flow, which break the traditional static scheduling approach. This prompted research into dynamically scheduled HLS ( Josipović et al., 2022 ) and approaches to combine it with existing industry-grade static HLS compilers ( Cheng et al., 2022c ; Szafarczyk et al., 2023a ) . Dynamic HLS uses load-store queues (LSQs) to perform memory disambiguation at runtime ( Huang et al., 2014 ; Josipovic et al., 2017 ; Szafarczyk et al., 2023b ; Gorius et al., 2024 ; Dai et al., 2017a ; Dai et al., 2017b ) . These works effectively pipeline single loops with arbitrary memory dependencies, but they have to sequentialize multiple loops if they share a memory dependency. For example, they would sequentialize the i - and j -loops in figure 1(a) , resulting in the figure 1(b) pipeline. But, as shown in figure 1(c) , there might be plenty of parallelism across the two loops. There are two reasons why current dynamic HLS tools have to sequentialize these loops. Firstly, they use a program-order schedule that relies on loops to run to completion before the next loop starts. For example, the LSQ used in Dynamatic HLS sequentializes LSQ requests based on the program order of basic blocks ( Josipovic et al., 2017 ) ; other approaches carry explicit dependencies through the pipeline, preventing downstream loops from starting without resolving the dependency ( Elakhras et al., 2023 ; Szafarczyk et al., 2023b ) . Secondly, they rely on the checking of address histories to detect hazards, without making any assumptions about the underlying address distributions. This makes them general, but requires them to wait for all addresses from one loop to be produced before they can start processing the next loop. These are two key challenges that we tackle in this paper. Static loop fusion also fails to fuse the loops in our figure 1(a) example, because the fused loop may introduce a negative dependency distance ( Kennedy and Allen, 2001 ) —the compiler gives up if it cannot prove that f(i)=g(j)\implies i<j . This is assuming that the f(i) and g(i) functions can be analyzed by the compiler in the first place. If that is not the case, e.g., if they involve an array access, then loop fusion is also not applied. Our dynamic loop fusion approach can automatically synthesize a Read After Write (RAW) check that will protect the A[g(j)] read in the figure 1 code, achieving the fine-grained inter-loop parallelism from figure 1(c) . We decouple each loop into an independently scheduled Processing Element (PE). Memory dependencies across loops are handled in a Data Unit (DU) specialized by our compiler for the program. Our only requirement is that the f(i) and g(j) functions are monotonically non-decreasing in the innermost loop (outer loops can be non-monotonic). This is a weaker requirement than the affine functions expected by static loop fusion, allowing us to fuse more loops, including codes with data-dependent addresses. To the best of our knowledge, we are the first to propose dynamic memory disambiguation that can work across loops. We make the following contributions: • A compiler pass to decouple loop nests into PEs. A PE is further decoupled into an Address Generation Unit (AGU) and a Compute Unit (DU) following the decoupled access/execute (DAE) architecture (section 2.1 ). • A compiler analysis, based on the chain of recurrences theory ( Bachmann et al., 1994 ; van Engelen et al., 2004 ) , that checks if addresses are monotonically non-decreasing in inner loops, and that detects non-monotonic outer loops (section 3 ). • A hardware-efficient program-order schedule representation that does not require sequentializing loops. We show how the compiler instruments AGUs with instructions that generate the schedule for each memory operation. We also show how non-monotonic outer loops can be integrated with our schedule (section 4 ). • A parameterizable DU performing dynamic memory disambiguation across loops. We show how the compiler can specialize the DU given the dependency graph of the program and the address monotonicity analysis. We discuss how the DU optimizes DRAM bandwidth by using dynamic coalescing and on-chip store-to-load forwarding (section 5 ). • An evaluation on irregular applications showing an average speedup of 14 \times over static HLS and 4 \times over dynamic HLS. We discuss which codes benefit from dynamic fusion and we study the impact of store-to-load forwarding (section 7 ). 2. Background In this paper, we focus on codes using DRAM, as its unpredictable latency and limited bandwidth pose greater challenges than BRAM. There is no fundamental reason why we could not protect BRAM or use a memory hierarchy with BRAM caches, which we briefly discuss in section 8 . In this section, we describe FPGA streaming

Read the complete text