Search

Simulated Annealing (SA) is one of the most common FPGA placement techniques, and is used both as a standalone algorithm and to improve an initial analytical placement. While SA-based placers can achieve high-quality results, they suffer from long runtimes. In this paper, we introduce RLPlace a novel SA-based FPGA placer that utilizes both Reinforcement Learning (RL) and targeted perturbations (directed moves). The proposed moves target both wirelength and timing optimization and explore the solution space more efficiently than traditional random moves while preventing oscillation in the Quality of Results (QoR). RL techniques are used to dynamically select the most effective move types as optimization progresses. Experimental results show that RLPlace outperforms the widely-used VTR 8 placer across all run-time/quality trade-off points, achieving better QoR placement solutions in less runtime. On average across the Titan23 suite of large FPGA benchmarks, RLPlace can reduce CPU time by 2.5× with result quality comparable to VTR 8, or improve wirelength by 8% (at a high CPU time budget) to 26% (at a low CPU time budget) vs. VTR 8.0 given the same CPU time.

As the benefits of Moore's Law diminish, computing performance, and efficiency gains are increasingly achieved through specializing hardware to a domain of computation. However, this limits the hardware's generality and flexibility. Field-programmable gate arrays (FPGAs), microchips which can be reprogrammed to implement arbitrary digital circuits, enable the benefits of specialization while remaining flexible. A challenge to using FPGAs is the complex computer-aided design flow required to efficiently map a computation onto an FPGA. Traditionally, these design flows are closed-source and highly specialized to a particular vendor's devices. We propose an alternate data-driven approach, which uses highly adaptable and retargettable open-source tools to target both commercial and research FPGA architectures. While challenges remain, we believe this approach makes the development of novel and commercial FPGA architectures faster and more accessible. Furthermore, it provides a path forward for industry, academia, and the open-source community to collaborate and combine their resources to advance FPGA technology.

Hardened adder and carry logic is widely used in commercial field-programmable gate arrays (FPGAs) to improve the efficiency of arithmetic functions. There are many design choices and complexities associated with such hardening, including circuit design, FPGA architectural choices, and the computer-aided design (CAD) flow. However, these choices have not been studied much and hence we explore a number of possibilities. We also highlight front-end elaboration optimization that helps ameliorate the restrictions placed on logic synthesis by hardened arithmetic. We show that hard adders and carry chains increase the performance of simple adders by a factor of 4 or more, but on larger benchmark designs that contain arithmetic improve the overall performance by 15%. Our results also show that for complete application circuits simple hardened ripple-carry adders perform as well as more complex carry-lookahead adders. Our best non-fracturable lookup table (non-fLUT) architecture with hardened arithmetic yields 12% better area–delay product than architectures without hardened arithmetic. We also investigate the impact of fLUTs and their interaction with hardened arithmetic. We find that fLUTs offer significant (12%–15%) area reduction, which is complementary to the delay reduction of hardened arithmetic. Therefore, our best fLUT architectures which use two bits of hardened arithmetic achieve 25% better area–delay product than non-fLUT architectures without hardened arithmetic.

Timing analysis is a key step in the digital design process. By modeling device delay variations statistical static timing analysis (SSTA) reduces pessimism compared to traditional static timing analysis (STA). However, it ignores the circuit's logic which causes some timing paths to never, or only rarely, be sensitized. We introduce a general timing analysis approach and tool to calculate the probability that individual timing paths are sensitized, enabling the calculation of bounding delay distributions over all input combinations. We show how this analysis is related to the well-known #SAT problem and present approaches to improve scalability, achieving, on average, results 75% to 37% less pessimistic than STA while running 569 to 16 times faster than Monte-Carlo timing simulation.

Simulated Annealing (SA) is widely used in FPGA placement either as a standalone algorithm or a refinement step after initial analytical placement. SA-based placers have been shown to achieve high-quality results at the cost of long runtimes. In this paper, we propose an improvement of SA-based placement using directed moves and Reinforcement Learning (RL). The proposed directed moves explore the solution space more efficiently than traditional random moves, and target both wirelength and timing optimizations. The RL agent further improves efficiency by dynamically selecting the most effective move types as optimization progresses. Taken together, these enhancements allow more efficient exploration of the large solution space than traditional annealing. Experimental results on the VTR benchmark suite show that our technique outperforms the widely-used VTR 8 placer across a wide range of CPU-quality trade-off points, achieving 5-11% reduced wirelength and comparable or shorter critical path delays in a given runtime, or 33-50% shorter runtimes for a target quality point.

Developing new or improved optimization heuristics for Computer Aided Design (CAD) tools is challenging and time consuming, relying on empirical experimentation and researcher experience. In this work we study how this process can be improved by using Reinforcement Learning (RL) to learn effective and adaptive heuristics. Applying these techniques to Field Programmable Gate Array (FPGA) placement, we show our RL-enhanced algorithm outperforms the standard VTR 8 placer, achieving a better run-time & quality trade-off (up to 2× faster for equivalent quality). RL enables the placer to more efficiently explore the solution space and enables it to dynamically adapt to the specific problem instance being solved. We expect further application of advanced RL methods will improve these results, which motivates further exploration of how RL could be applied in the CAD flow.

Timing analysis is a cornerstone of the digital design process. Statistical Static Timing Analysis was introduced to reduce pessimism by modelling device delay variations. However it ignores circuit logic, which may cause some timing paths to never or only rarely be sensitized. We introduce a general timing analysis approach and tool to calculate the probability that individual timing paths are sensitized, enabling the calculation of bounding delay distributions over all input combinations. We show the connection to the well-known #SAT problem and present approaches to improve scalability, achieving average results 46 to 32% less pessimistic than Static Timing Analysis while running 14.6 to 44.0 times faster than Monte-Carlo timing simulation.

Realistic benchmarks are important for FPGA Architecture and CAD evaluation. This paper provides a demo illustrating how designs described in HDL can be converted to BLIF using the Titan flow, and used in academic CAD tools.

Background Hospital-acquired diagnoses (HAD) not only lengthen inpatients’ recovery times but also incur significant additional costs of care. The focus of previous research has been on ‘highly preventable’ indicator conditions and the cost of individual episodes, rather than on the entire spectrum of unintentional patient harm. As well, little attention has been paid to the frequency of HADs and resulting total costs.