Back
2026INF004.pdf
Doctoral thesis

Solver-based compilation for coarse-grained reconfigurable arrays and scalable logic synthesis

  • 2026

PhD: Università della Svizzera italiana

Compilers
Optimization
Coarse-grained reconfigurable arrays (CGRAs)
Reconfigurable architectures
Solver
Logic synthesis
Mapping
Modulo scheduling
English Coarse-Grained Reconfigurable Arrays (CGRAs) are low-power accelerators that combine the efficiency of custom hardware with a level of flexibility closer to general-purpose architectures. To exploit this hardware effectively, the compilation flow must generate efficient mappings for compute-intensive loops (CILs), whose structure exposes parallelism that a CGRA can execute at high throughput. Given an abstract representation of a CIL in the form of a data-flow graph (DFG) and a target CGRA, the compiler must produce a spatiotemporal mapping that jointly decides when each operation executes (scheduling), where it executes (placement), and how values are communicated through the interconnect (routing). These decisions are tightly coupled and constrained by finite resources. As both the DFG and the array scale, the number of candidate mappings grows combinatorially. For this reason, most existing mappers rely on heuristics that trade optimality and robustness for speed. Exact formulations can provide stronger guarantees, but are often limited by scalability and by how the mapping problem is structured. This thesis addresses this gap by exploiting modern SAT/SMT technology to obtain high-quality mappings while explicitly tackling scalability. The first part of the thesis focuses on CGRA compilation, with two complementary goals: achieving high-quality mappings (low initiation interval) and making the compilation flow scalable as both kernels and arrays grow. For mapping quality, we introduce a SAT-driven CGRA compiler that casts mapping as a decision problem: for a fixed initiation interval (II), it determines whether a feasible mapping exists, starting from the minimum II and increasing it only when necessary. The key idea is to characterize the scheduling solution space through a custom schedule representation, the Kernel Mobility Schedule (KMS), and to encode the remaining placement-and-timing constraints as a SAT instance. Across a broad set of benchmarks, this approach consistently reaches the II lower bound and improves upon state-of-the-art mappers. To address scalability, the thesis then introduces a decoupled mapping methodology that separates time from space. An SMT formulation explores the temporal dimension under constraints designed to preserve spatial feasibility, and a graph-monomorphism-based search constructs the spatial binding once a schedule is found. Compared to the SAT-based approach, this methodology preserves mapping quality while keeping compilation time consistently low as CGRA sizes grow. The second part of the thesis moves from CGRA mapping algorithms to a complementary scalability bottleneck that emerges in end-to-end accelerator toolflows: circuit optimization. This shifts the focus to the backend of hardware compilation and, more broadly, to logic-synthesis techniques in electronic design automation (EDA). We propose a multicore framework that partitions a large Boolean network into subcircuits, optimizes them concurrently using user-provided scripts, and merges the results back into a single functionally equivalent netlist. Experimental results on standard combinational benchmarks evaluate the effectiveness of this decomposition-based approach, showing that local improvements obtained on subcircuits can translate into measurable global gains after merging, while enabling more scalable optimization on large designs. Overall, this thesis delivers results across two stages of accelerator toolflows. On the CGRA side, it shows how solver-based formulations provide a practical path to high-quality and scalable compilation for CGRA accelerators. On the logic-synthesis side, it demonstrates that parallel, locality-driven optimization of subcircuits can improve the scalability of synthesis flows for large circuits, without giving up functional correctness.
Collections
Language
  • English
Classification
Computer science and technology
License
License undefined
Open access status
green
Identifiers
Persistent URL
https://n2t.net/ark:/12658/srd1335266
Statistics
Document views: 0 File downloads:
  • 2026INF004.pdf: 0