Enhancing routing architecture and routing algorithm for improving FPGAs' performance

With the advent of deep submicron technologies, the extreme high design and mask costs incurred for ASICs have made FPGAs an increasingly popular hardware implementation option. However, it has been shown that the programmable routing structure underlined contributes over 60% of the signal delay and as high as 90% of the total chip area. As a result, current FPGAs still cannot meet performance requirements of many high-end applications. To attack this issue, we propose new solutions along the two major tracks: (I) architectural revisions (hardware) and (II) new EDA technique/flow (software).;(I) Architectural revisions: Probably due to historical reasons, programmable switches on conventional FPGA architectures are divided into two kinds of substructures: Connection boxes (C-boxes) and Switch boxes (S-boxes), where C-boxes are used to connect logic/pad pins with their crossing wire segments, and S-boxes are used to connect wire segments of surrounding routing channels. In this work, we will challenge if this divided C- and S-boxes structure is really necessary and will explore a new experimental architecture which adopts only one kind of switching components - Connection-Switch boxes (CS-boxes). Extensive experiments are conducted on MCNC benchmark circuits to justify its architectural performance impacts. The results show that this CS-box based FPGA outperforms the conventional FPGA in terms of channel width, circuit delay, and segment usage. Besides an over 20% drastic dropping in the total number of manufactured switches needed, circuit delay performance is improved by 10% under the usage of the same pin assignments and router.;(II) New EDA technique/flow: By applying circuit rewirings, logic perturbations can be carried out by shifting logic resources from perhaps costly Look-Up-Table (LUT) external to cost-free LUT internal areas, or from critical to non-critical paths. This work presents a simple, while effective and low-overhead postlayout logic perturbation scheme for improving LUT-based FPGA routings without altering placements. A rewiring-based logic perturbation technique is used to improve upon a timing-driven FPGA P&R tool - TVPR. Compared with the already high-quality pure TVPR results, our approach reduces critical path delay by up to 31.74% (avg. 11%) without disturbing the placement or sacrificing chip areas, where only 4% of the nets are perturbed in our scheme. The complexity of our algorithm is linear in the total number of nets of the circuit. The experimental results show that the CPU time used by the rewiring engine is only 5% of the total time consumed by the placement and routing of TVPR.;Based on these studies, we believe the prospect for FPGA performance improvement is still quite profound in both architectural and EDA aspects. On the EDA technique, we have also performed logic perturbations to improve both the technology mapping and routing to investigate the effectiveness of the logic perturbation if applied in a larger context. The results show that a best technology mapping is not always leading to a best final routing, which seems to suggest that an ideal FPGA EDA flow should consider more on trade-offs between different stages. To the best of our knowledge, this is the first work exploring the power of logic perturbations applied for multiple physical stages for LUT-based FPGAs. The encouraging hardware improvement shown in our proposed CS-box based FPGAs seems to suggest a new design direction for FPGA routing architectures.