Automated Design of FPGAs Facilitated by Cycle-Free Routing

As device technology advances into the sub-10nm era, the design costs of Field Programmable Gate Arrays (FPGAs) built out of fully-custom, hand-layout blocks have increased dramatically. At the same time, Embedded FPGAs (eFPGAs) are picking up steam in heterogeneous system-on-chip designs, in which case supporting customizable FPGA architectures and reducing design costs are more crucial than squeezing the last bit of performance out of the transistors. To reduce the cost and complexity of FPGA designs, prior works have proposed to build FPGAs using Electronic Design Automation (EDA) tools and standard-cell libraries. Though functionally viable, this approach faces two challenges: 1) An accurate timing model is crucial for FPGA implementation tools to produce correct and optimal results. However, post-layout Static Timing Analysis (STA) with EDA tools is error-prone on FPGAs, because the typical FPGA routing graphs contain many cycles at design time. 2) Conventional FPGA design relies heavily on iterative/empirical improvements to achieve optimal floorplanning and time-budgeting. Without such insights, blocks may be shaped and constrained sub-optimally. This work addresses the first challenge by proposing an algorithm to derive cycle-free sub-graphs. A cycle-free subgraph is achieved by logically ranking the routing tracks and selectively removing some switch block connections. Each subgraph enables accurate, per-switch, post-layout STA, and the union of multiple sub-graphs covers all the timing arcs of the FPGA. Furthermore, our proposed approach addresses the second challenge by enabling the creation of intrinsically cycle-free FPGAs that facilitate a flat multi-block or full-chip design flow. By blending the blocks, the EDA tools can exploit more optimization opportunities and automatically adapt to heterogeneous blocks. Our experiments show that the routability of cycle-free routing graphs is comparable to conventional FPGA routing graphs, and the Quality of Results (QoR) of the FPGA layout is superior to the result of previous approaches.