Search

FPGAs allow custom memory hierarchy and flexible data movement with highly fine-grained control. These capabilities are critical for building high performance and energy efficient domain-specific architectures (DSAs), especially for workloads with irregular memory access and data-dependent communication patterns. Sparse linear algebra operations, especially sparse matrix vector multiplication (SpMV), are examples of such workloads and are becoming important due to their use in numerous areas of science and engineering. Existing FPGA-based DSAs for SpMV do not allow customization through plug and play of the building blocks. For example, most of these DSAs require switching network/crossbar architecture as a building block for routing matrix data to banked vector memory blocks. In this paper, we first present an approach where a custom network is built using simple blocks arranged in a regular fashion to exploit low-level architecture details. Further, we make use of this network to replace expensive crossbars employed in GEMX SpMV engine and develop an end-to-end tool-flow around mixed IP approach (HLS/RTL). Due to the modularity of our design, our tool-flow allows us to insert an additional block in the design to guarantee zero-stall from the accumulation stage. On Alveo U200, we report performance numbers of up to 4.4 GFLOPS (92% peak bandwidth utilization) using our accelerator (attached with one DDR4).

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+(TM) devices 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.

Many FPGA designs contain soft IP tightly connected to hard blocks such as on-chip Processor, PCIE or IOs. Generally, these soft IPs pose significant timing closure challenges. In this paper, we propose a timing-driven Place and Route flow based on Boolean Satisfiability (SAT). Its main advantages over previous SAT-based approaches are its improved scalability and its timing awareness. We validate our flow using an IP targeting the emulation market. We demonstrate that our flow can significantly improve the usable bandwidth of FPGA IOs. Since the proposed flow is SAT based, the performance does not depend on specific ways in which more traditional place and route are usually tuned.

This paper describes the methodology and algorithms behind extra pipeline analysis tools released in the Xilinx Vivado Design Suite version 2015.3. Extra pipelining is one of the most effective ways to improve performance of FPGA applications. Manual pipelining, however, often requires significant efforts from FPGA designers who need to explore various changes in the RTL and re-run the flow iteratively. The automatic pipelining approach described in this paper, in contrast, allows FPGA users to explore latency vs. performance trade-offs of their designs before investing time and effort into modifying RTL. We describe algorithms behind these tools which use simple cut heuristics to maximize performance improvement while minimizing additional latency and register overhead. To demonstrate the effectiveness of the proposed approach, we analyse a set of 93 commercial FPGA applications and IP blocks mapped to Xilinx UltraScale+ and UltraScale generations of FPGAs. The results show that extra pipelining can provide from 18% to 29% potential Fmax improvement on average. It also shows that the distribution of improvements is bimodal, with almost half of benchmark suite designs showing no improvement due to the presence of large loops. Finally, we demonstrate that highly-pipelined designs map well to UltraScale+ and UltraScale FPGA architectures. Our approach demonstrates 19% and 20% Fmax improvement potential for the UltraScale+ and UltraScale architectures respectively, with the majority of applications reaching their loop limit through pipelining.

Boolean Satisfiability (SAT)-based routing offers a unique advantage over conventional routing algorithms by providing an exhaustive approach to find a solution. Despite that advantage, commercial FPGA CAD tools rarely use SAT-based routers due to scalability issues. In this paper, we revisit SAT-based routing and propose two SAT formulations independent of routing architecture. We then demonstrate that SAT-based routing using either formulation dramatically outperforms conventional routing algorithms in both runtime and robustness for the clock routing of Xilinx UltraScale devices. Finally, we experimentally show that one of the proposed SAT formulations leads to a routing 18x faster and produces formulas 20x more compact than the other. This framework has been implemented into Vivado and is now currently used in production.