Automated Design of FPGAs Facilitated by Cycle-Free Routing

Ang Li, Ting Jung Chang, David Wentzlaff

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationProceedings - 30th International Conference on Field-Programmable Logic and Applications, FPL 2020
EditorsNele Mentens, Nele Mentens, Leonel Sousa, Pedro Trancoso, Miquel Pericas, Ioannis Sourdis
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781728199023
StatePublished - Aug 2020
Event30th International Conference on Field-Programmable Logic and Applications, FPL 2020 - Virtual, Gothenburg, Sweden
Duration: Aug 31 2020Sep 4 2020

Publication series

NameProceedings - 30th International Conference on Field-Programmable Logic and Applications, FPL 2020


Conference30th International Conference on Field-Programmable Logic and Applications, FPL 2020
CityVirtual, Gothenburg

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Hardware and Architecture
  • Software
  • Logic


  • EDA Flow
  • FPGA
  • FPGA Routing Architecture


Dive into the research topics of 'Automated Design of FPGAs Facilitated by Cycle-Free Routing'. Together they form a unique fingerprint.

Cite this