Pongstorn Maidee

Field-programmable gate arrays (FPGAs) require a much longer compilation cycle than conventional computing platforms such as CPUs. In this article, we shorten the overall compilation time by co-optimizing the HLS compilation (C-to-RTL) and the back-end physical implementation (RTL-to-bitstream). We propose a split compilation approach based on the pipelining flexibility at the HLS level, which allows us to partition designs for parallel placement and routing. We outline a number of technical challenges and address them by breaking the conventional boundaries between different stages of the traditional FPGA tool flow and reorganizing them to achieve a fast end-to-end compilation. Our research produces RapidStream, a parallelized and physical-integrated compilation framework that takes in a latency-insensitive program in C/C++ and generates a fully placed and routed implementation. We present two approaches. The first approach (RapidStream 1.0) resolves inter-partition routing conflicts at the end when separate partitions are stitched together. When tested on the Xilinx U250 FPGA with a set of realistic HLS designs, RapidStream achieves a 5 to 7× reduction in compile time and up to 1.3× increase in frequency when compared with a commercial off-the-shelf toolchain. In addition, we provide preliminary results using a customized open-source router to reduce the compile time up to an order of magnitude in cases with lower performance requirements. The second approach (RapidStream 2.0) prevents routing conflicts using virtual pins. Testing on Xilinx U280 FPGA, we observed 5 to 7× compile time reduction and 1.3× frequency increase.

Access to detailed timing information for FPGA resources is essential to achieving the highest performance. Yet, for commercial FPGAs, much of this information is not published or available. At the same time, deploying large, fine-grained timing datasets adversely affects the speed of timing-driven place and route algorithms. We propose a nimble timing model for RapidWright that delivers high fidelity timing approximations while enabling faster algorithms through a frugal memory footprint. By leveraging a combination of architectural knowledge, repeating patterns and extensive analysis of Vivado timing reports, we obtain a slightly pessimistic, lumped delay model within 2% average accuracy of Vivado for UltraScale+ devices. We validate the results with over 240 designs and the proposed model shows high fidelity to Vivado with a Spearman's value of 0.99. By open sourcing the proposed model and describing the process, we empower the community to leverage and extend this work for customized domains, other device families, and additional accuracy.

FPGA capacity has grown rapidly and emerging applications comprise a large number of compute modules. The communication among these modules and external memory will cause routing congestion in fabric interconnect. This problem is more pronounced with process scaling since the technology is not improving wire resistance. High-speed data compute modules along with faster local storage enable efficient kernels running at 500-800 MHz on the newer devices. FPGA system performance at those high frequencies will require efficient global data movement across the chip from/to an external memory. We propose a system-level solution for global data movement in FPGAs, called LinkBlaze, to address these issues. LinkBlaze leverages both general Network-on-Chip (NoC) techniques and FPGA architecture for reducing resource usage. This work explores different router architectures and provides insights for the user on how to best utilize and share the global links on the FPGA. Our results indicate 640 MHz performance on Ultrascale+ for an optimized 3-port soft NoC. We further extend those results to implement a global data movement overlay operating as high as 1 GHz, by restricting the number of clients and leveraging flexible FPGA placement. Our proposed solution enables 8GB/s system-level throughput in Ultrascale+ for a 64-bit instance, while using underutilized resources in FPGAs. Our results indicate how to scale our solution to implement more than 52GB/s access to external memory using 2-3X less fabric resources. We recommend an architecture and a preferred location for our proposed interconnect overlay and intend to make the solution available for the FPGA application community.

FPGA capacity has grown rapidly and emerging large applications comprise a large number of hard and soft modules. The communication among these modules requires high demand from fabric interconnect, causing routing congestion and performance degradation. This problem will be more pronounced with process scaling since the technology is not improving wire resistance. A general technique to reduce interconnect demand is sharing the wires; Network-on-Chip (NoC) is a systematic method for sharing wires. Several NoC implementations have been proposed for FPGAs in the literature, but most are designed with assumptions carried over from ASIC NoCs. In this work we examine these assumptions and modify them when necessary to customize a soft NoC for FPGAs. We developed a NoC that is tuned for FPGAs and compared it to existing NoCs in the literature. The proposed soft NoC provides 12% to 58% higher throughput per link depending on the settings. This additional throughput comes with 5% to 19% reduction in area.

This paper proposes two set-of-pairs-of-functions-to-be-distinguished (SPFD)-based rewiring algorithms to be used in a multi-tier rewiring framework, which employs multiple rewiring techniques. The first algorithm has two unique features: 1) a satisfiability problem (SAT) instance was devised so that an unsuccessful rewiring can be identified very quickly, and 2) unlike binary decision diagram-based methods that require all pairs of SPFD, our algorithm uses a few SAT instances to perform rewiring for a given wire without explicitly enumerating all SPFDs. Experimental results show that the runtime of our algorithm is about three times faster than that of a conventional one under a simulated setting of such a framework and it scales well with the number of candidate wires considered. The efficacy of the framework can be further improved by the second proposed algorithm. The algorithm relies on a theory presented herein to allow adding a new wire outside of the restricted set of dominator nodes, a feature common in automatic-test-pattern-generation-based rewiring, but absent in existing SPFD-based ones. Although this algorithm may suffer from long runtimes in the same way conventional SPFD-based techniques do, experiments show that the number of wires which can be rewired increases 13% on average and the number of alternative wires also increases.

Circuit rewiring can be used to explore a larger solution space by modifying circuit structure to suit a given optimization problem. Among several rewiring techniques that have been proposed, SPFD-based rewiring has been shown to be more effective in terms of solution space coverage. However, its adoption in practice has been limited due to its long runtime. We propose a novel SAT-based algorithm that is much faster than the traditional BDD-based methods. Unlike BDD-based methods that completely specify all pairs of SPFD using BDDs, our algorithm uses a few SAT instances to perform rewiring for a given wire without explicitly enumerating all SPFDs. Experimental results show that our algorithm's runtime is only 13% of that of a conventional one when each wire has at most 25 candidate wires and the runtime scales well with the number of candidate wires considered. Our approach evaluates each rewiring instance independently in the order of milliseconds, rendering deployment of an SPFD-based rewiring inside the optimization loop of synthesis tools a possibility.

Field-programmable gate arrays (FPGAs) have gained wide acceptance among low- to medium-volume applications. However, there are gaps between FPGA and custom implementations in terms of area, performance and power consumption. In recent years, specialized blocks - memories and multipliers in particular - have been shown to help reduce this gap. However, their usefulness has not been studied formally on a broad spectrum of designs. As FPGAs are prefabricated, an FPGA family must contain members of various sizes and combinations of specialized blocks to satisfy diverse design resource requirements. We formulate the family selection process as an ldquoFPGA family compositionrdquo problem and propose an efficient algorithm to solve it. The technique was applied to an architecture similar to Xilinx Virtex FPGAs. The results show that smart composition technique can reduce the expected silicon area up to 55%. The benefit of providing multiplier blocks in FPGAs is also shown to reduce total area by 20% using the proposed algorithm.

Traditionally, logic synthesis constrains the solution space of later design steps, such as physical design, because they are applied in sequence. Rewiring is a technique to restructure a circuit while maintaining its functionality. Since design properties and objectives can be considered during post-synthesis rewiring, it can help relieve constraints put forth by decisions made at earlier design steps. The extent of rewiring of a rewiring algorithm has a great impact on the success of the design flow. This paper presents a powerful rewiring technique that in addition to unifying all previously proposed set-of-pairs-of-functions-to-be-distinguished based rewiring techniques, it can perform rewiring with more than one wire which increases our ability to circumvent poorly-decided early design constraints. With this ability, the rewiring ability of using different numbers of wires is reported for the first time in this paper. Our technique can be used for run-lime/quality trade-off in any given rewiring application.

According to the ITRS predictions, controlling manufacturing yield is going to be a challenging task in future technologies. The effective yield of future FPGA architectures considering configurable logic blocks, switch boxes, connection boxes and routing segments is estimated in this paper. The results show that some degree of redundancy for logic blocks, routing and switch boxes is necessary. However, no more than one spare logic block per cluster, and at most one spare wire is required to obtain a satisfactory effective yield. The results also indicate that it is beneficial to increase logic cluster size of future FPGA architectures for better yield.

In traditional field programmable gate array (FPGA) placement methods, there is virtually no coupling between placement and routing. Performing simultaneous placement and detailed routing has been shown to generate much better placement qualities, but at the expense of significant runtime penalties (Nag and Rutenbar, 1998). We propose a routing-aware partitioning-based placement algorithm for FPGAs in which a looser but effective coupling between the placement and routing stages is used. The placement engine incorporates a more accurate FPGA delay model and employs effective heuristics that minimize circuit delay. Delay estimations are obtained from routing profiles of selected circuits that are placed and routed using the timing-driven versatile place and route (TVPR) (Betz and Rose, 1997), (Marquardt et al., 2000). As a result, the delay predictions during placement more accurately resemble those observed after detailed routing, which in turn leads to better delay optimization. An efficient terminal alignment heuristic for delay minimization is applied during placement to further optimize the delay of the circuit. These two techniques help maintain harmony between placement and routing-delay optimization stages. Simulation results show that the proposed partitioning-based placement combined with more accurate delay models and the alignment heuristic can achieve postrouting circuit delays comparable to those obtained from TVPR, while achieving a fourfold speedup in total placement runtime. In another experiment, we augmented the original TVPR algorithm with the terminal alignment heuristic, and achieved, on average, a 5% improvement in circuit delay with negligible runtime penalty.