Slack Allocation and Routing to Improve FPGA Timing While Repairing Short-Path Violations
Authors:
- 21 March 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 27 (4) , 686-697
Abstract
This paper presents the first published algorithm to simultaneously optimize both short- and long-path timing in a field-programmable gate array (FPGA): the routing cost valleys (RCV) algorithm. RCV consists of the following two components: a new slack-allocation algorithm that determines both a minimum and a maximum delay budget for each circuit connection and a new router that strives to meet and, if possible, surpass these connection-delay constraints. RCV improves both long- and short-path timing slacks significantly versus an earlier computer-aided design system, showing the importance of an integrated approach that simultaneously optimizes considering both types of timing constraints. It is able to meet long- and short-path timing constraints on all 157 peripheral component interconnect cores tested, while an earlier algorithm failed to achieve timing on 75% of the cores. Even in cases where there are no short-path timing constraints, RCV outperforms a state-of-the-art FPGA router and improves the maximum clock speed of circuits by an average of 3.2% (and up to 24.7%).Keywords
This publication has 12 references indexed in Scilit:
- Solving hard instances of FPGA routing with a congestion-optimal restrained-norm path search space2007
- Simultaneous short-path and long-path timing optimization for FPGAs2005
- Optimal Integer Delay-Budget Assignment on Directed Acyclic GraphsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2004
- Timing-driven routing for FPGAs based on lagrangian relaxationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2003
- Iterative and adaptive slack allocation for performance-driven layout and FPGA routing2003
- Minimum padding to satisfy short path constraints2002
- Timing constraints for correct performance2002
- Architecture and CAD for Deep-Submicron FPGAS1999
- Placement and routing tools for the Triptych FPGAIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1995
- A performance and routablity driven router for FPGAs considering path delays1995