Routing is one of the major challenges of FPGA compilation. PathFinder is a ubiquitous FPGA routing algorithm used in industry and academia due to its ability to adapt to arbitrary routing architectures and user circuits. However, to this day, we do not fully understand why PathFinder works so well and what its limitations are. When a circuit fails to route, it is difficult to pinpoint the problem: architecture or algorithm. Usually, in such cases, either Pathfinder is fine-tuned or routing resources are added to the architecture to improve routability, thereby ignoring the inherent inefficiencies that may exist in Pathfinder, which further prevents us from designing silicon-efficient architectures. In this work, to pinpoint the problem, we construct constrained routing problems where nets have access to limited but specific routing resources that guarantee a legal routing solution. Yet, even with a state-of-the-art implementation, PathFinder fails to find the guaranteed routing solution or any other solution, highlighting issues specific to PathFinder. The reduced search space makes the underlying behavior more accessible for analysis and reasoning, allowing us to identify inefficiencies in the current PathFinder paradigm and propose a solution to address them. We uncovered that PathFinder's greedy approach of routing individual connections yields an inefficient route tree, in terms of the total number of nodes. We then transfer this insight-through a simple yet effective algorithm-from the constrained to the standard setting, where the search space is not reduced. By constructing more efficient route trees, the routed wirelength and the number of routed connections were reduced by 6.4% and 3.6%, respectively, on average.

The use of domain-specific accelerators is becoming prominent for a variety of emerging domains such as graph analytics and HPC, where most of the computations revolve around Sparse Matrix-Vector (SpMV) Multiplication. Many of the existing SpMV accelerators do not scale well on FPGA fabric and exhibit significant performance and area overheads [1]–[3]. With the increased external memory bandwidths supported by FPGA platforms, SpMV accelerator design sizes are growing rapidly and exhibit timing closure challenges in physical implementation [4], [5]. To utilize all the High Bandwidth Memory (HBM) channels on the FPGA device, accelerator designers rely on the reuse and replication of the processing elements (PEs). As the number of PEs in a design grows, the achieved frequency of these large designs is often much lower than a single PE design [4], [5]. In this paper, we present a modular and lean architecture for the SpMV workload enabling elastic communication between building blocks. The proposed SpMV accelerator uses single-precision floating-point arithmetic (FP32) and achieves a frequency of 465 MHz for single-instance implementation. The lean nature of the design enables the scaling of the accelerator to sixteen instances, which utilizes all of the 32 HBM pseudo-channels available on the Alveo U280 FPGA platform. The accelerator design with sixteen SpMV instances, spanning multiple FPGA dies, can close timing at 310 MHz which is 80% higher than GraphLily [4] and 40% higher than HiSparse [5]. We demonstrate up to 50 GFLOPS performance on the Alveo U280 FPGA Platform which is 2.5× of GraphLily [4].

We identified that in modern commercial FPGAs, routing signals from the general interconnect to the inputs of the CLB primitives through a very sparse input interconnect block (IIB) represents a significant runtime bottleneck. This is despite academic research often neglecting the runtime of last-mile routing through the IIB. We propose a two-step routing approach that allows resolving this bottleneck by leveraging massive parallelism of today's compute infrastructure. The main premise that enables massive parallelization is that once the signals are legally routed in the general interconnect-only reaching the inputs of the IIB, but not the final targets-the remaining last-mile routing through the IIB can be completed independently for each FPGA tile.

We identified that in modern commercial FPGAs, routing signals from the general interconnect to the configurable logic blocks (CLBs) through a very sparse input interconnect block (IIB) represents a significant runtime bottleneck. This is despite academic research usually altogether neglecting the runtime of last-mile routing through the IIB. To alleviate this bottleneck, we combine computer-aided design (CAD) and FPGA architecture enhancements. We propose a multi-stage FPGA routing approach, based on the premise that once the signals are legally routed in general interconnect-only reaching the inputs of the IIB, but not the final targets-the remaining last-mile routing through the IIB can be completed efficiently and independently for each FPGA tile. Then, the final routing solution can simply be built by joining the previously obtained partial solutions. However, we observe that some properties of modern IIB architectures limit the success rate of the intra-CLB routing, creating the need for revisiting the routing in the general interconnect and inevitably impairing the multi-stage routing runtime gains. We show that an enhanced IIB architecture mitigates the issue at a minimal cost. With ISPD16 benchmarks and an FPGA architecture model closely resembling AMD UltraScale FPGAs, we demonstrate the dominant contribution of last-mile routing to the router's runtime. After applying our multi-stage routing approach and the proposed enhancements, we show that the observed bottleneck can be mitigated, resulting in 4.94× faster routing on average.

In this paper we describe Xilinx's Versal-Adaptive Compute Acceleration Platform (ACAP). ACAP is a hybrid compute platform that tightly integrates traditional FPGA programmable fabric, software programmable processors and software programmable accelerator engines. ACAP improves over the programmability of traditional reconfigurable platforms by introducing newer compute models in the form of software programmable accelerators and by separating out the data movement architecture from the compute architecture. The Versal architecture includes a host of new capabilities, including a chip-pervasive programmable Network-on-Chip (NoC), Imux Registers, compute shell, more advanced SSIT, adaptive deskew of global clocks, faster configuration, and other new programmable elements as well as enhancements to the CLB and interconnect. We discuss these architectural developments and highlight their key motivations and differences in relation to traditional FPGA architectures.

FPGAs take advantage of 2.5D stacking technology to manufacture large capacity and high performance heterogeneous devices at reasonable costs. EDA tools need to be aware of and exploit physical characteristics of such devices, for example the reduced connection count between SLRs, the infrequency of SLL channel occurence in the fabric, and the aspect ratios of individual SLRs. We implement a partition driven placer to explore various EDA options to take advantage of architectural features in 2.5D FPGAs. We improve the routability of designs by optimizing the placer for discrete SLL channels and reduced connection counts. We propose a cut schedule for the partitioner to orient the placement with awareness of the aspect ratio of SLRs to improve track demands within each SLR.

2.5D stacking technology allows us to build high performance and high capacity FPGA devices at reasonable costs. The communication between multiple dies happen on a passive silicon interposer at high speed, which pose several interesting challenges. Due to clock skew characteristics across multiple dies and increase in the min-max spread of delays, place-and-route tools need to address inter-die hold violations and optimize for performance. We implement a tractable SAT based methodology to achieve this by minimally detouring data paths to meet all hold requirements while optimizing performance. We also confine the solution to a small window around each inter-die (Laguna) channel to reduce routing resource utilization, congestion, and scale the methodology to any Laguna channel utilization. We improve performance across the interface by 11% compared to a state-of-the-art commercial flow and meet a 500MHz spec on Xilinx(R) UltraScale+TMdevices in 2E speedgrade. We address the scalability concerns of SAT and show how we can use this in practice with negligible runtimes in implementation tools. Our solution paves the way for FPGA-as-a-service platforms where fast inter-die communication, that does not interfere with user specific logic, is pivotal to their success.

Dynamic power management for multi-core system on chip (MPSoC) platforms has become an increasingly critical design problem. In this paper, we present EmPower, an FPGA based emulation, validation and prototyping framework for dynamic power management research targeted at MPSoC platforms. EmPower supports two advanced power management features -- per-core dynamic frequency scaling and clock gating, and power-aware thread migration. We also provide two fully-functional parallel applications for benchmarking -- video encoding and software-defined radio. Our experimental results indicate that EmPower provides up to 36 -- improvement in run-time compared to cycle-accurate software simulations, and enables accurate and efficient exploration of the design space of power management algorithms.

Dynamic power management for multi-core system on chip (MPSoC) platforms has become an increasingly critical design problem. In this paper, we present EmPower, an FPGA based rapid prototyping framework for dynamic power management algorithms targeted at MPSoC platforms. EmPower supports two advanced power management techniques (per-core dynamic frequency scaling and clock gating, and thread migration), enables software based expression of the power management algorithm, and provides on-chip power measurement capabilities. EmPower also includes two fully-functional parallel applications for benchmarking - video encoding and software-defined radio. We demonstrate the use of EmPower in rapid exploration of the large design space of power management algorithms using two illustrative case studies.

We reconsider guarded evaluation as a means to reduce FPGA dynamic power consumption. We augment and evaluate guarded evaluation as proposed in [1] after different stages of the FPGA CAD flow. Guarding later in the flow provides more feedback to the algorithm and yields a more effective cost-benefit analysis of newly added signals. Numerical results show that guarding later in the flow yields slightly less power savings versus guarding after technology mapping. However, fewer guards are inserted which results in fewer netlist changes and less impact on routing resource usage.

Guarded evaluation is a power reduction technique that involves identifying subcircuits (within a larger circuit) whose inputs can be held constant (guarded) at specific times during circuit operation, thereby reducing switching activity and lowering dynamic power. The concept is rooted in the property that under certain conditions, some signals within digital designs are not “observable” at design outputs, making the circuitry that generates such signals a candidate for guarding. Guarded evaluation has been demonstrated successfully for application-specific integrated circuits (ASICs); in this paper, we apply the technique to field-programmable gate arrays (FPGAs). In ASICs, guarded evaluation entails adding additional hardware to the design, increasing silicon area and cost. Here, we apply the technique in a way that imposes minimal area overhead by leveraging existing unused circuitry within the FPGA. The primary challenge in guarded evaluation is in determining the specific conditions under which a subcircuit's inputs can be held constant without impacting the larger circuit's functional correctness. We propose a simple solution to this problem based on discovering gating inputs using “noninverting” and “partial noninverting” paths in a circuit's AND-inverter graph representation. Experimental results show that guarded evaluation can reduce switching activity on average by as much as 32% and 25% for 6-input look-up table (6-LUT) and 4-LUT architectures, respectively. Dynamic power consumption in the FPGA interconnect is reduced on average by as much as 24% and 22% for 6-LUT and 4-LUT architectures, respectively. The impact to critical path delay ranges from 1% to 43%, depending on the guarding scenario and the desired power/delay tradeoff.

We leverage properties of the logic synthesis netlist to define both a new field-programmable gate-array (FPGA) logic element (function generator) architecture and an associated technology mapping algorithm that together provide improved logic density. We demonstrate that an “extended” logic element with slightly modifiedK-input lookup tables (LUTs) achieves much of the benefit of an architecture withK+1-input LUTs, while consuming silicon area close to aK-LUT (aK-LUT requires half the area of aK+1-LUT). We introduce the notion of “non-inverting paths” in a circuit's and-inverter graph (AIG) and show their utility in mapping into the proposed logic element architectures. We propose a general family of logic element architectures, and present results showing that they offer a variety of area/performance tradeoffs. One of our key results demonstrates that while circuits mapped to a traditional 5-LUT architecture need 15% more LUTs and have 14% more depth than a 6-LUT architecture, our extended 5-LUT architecture requires only 7% more LUTs and 5% more depth than 6-LUTs, on average. Nearly all of the depth reduction associated with moving fromK-input toK+1 -input LUTs can be achieved with considerably less area using extendedK-LUTs. We further show that 6-LUT optimal mapping depths can be achieved with a small fraction of the LUTs in hardware being 6-LUTs and the remainder being extended 5-LUTs, suggesting that a heterogeneous logic block architecture may prove to be advantageous.

Guarded evaluation is a power reduction technique that in-volves identifying sub-circuits (within a larger circuit) whose inputs can be held constant (guarded) at specific times dur-ing circuit operation, thereby reducing switching activity and lowering dynamic power. The concept is rooted in the property that under certain conditions, some signals within digital designs are not “observable ” at design outputs, mak-ing the circuitry that generates such signals a candidate for guarding. Guarded evaluation has been demonstrated successfully for custom ASICs; in this paper, we apply the technique to FPGAs. In ASICs, guarded evaluation entails adding additional hardware to the design, increasing sili-con area and cost. Here, we apply the technique in a way that imposes minimal area overhead by leveraging existing unused circuitry within the FPGA. The primary challenge in guarded evaluation is in determining the specific condi-tions under which a sub-circuit’s inputs can be held con-stant without impacting the larger circuit’s functional cor-rectness. We propose a simple solution to this problem based on discovering “non-inverting paths ” in the circuit’s AND-inverter graph representation. Experimental results show that guarded evaluation can reduce switching activity by 22%, on average, and can reduce power consumption in the FPGA interconnect by 14%.