Routing for array-type FPGA's
Authors:
- M. Marek-SadowskaMMM. Marek-Sadowska
- 1 May 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 16 (5) , 506-518
Abstract
In this paper, the routing problem for two-dimensional (2-D) field programmable gate arrays of a Xilinx-like architecture is studied. We first propose an efficient one-step router that makes use of the main characteristics of the architecture. Then we propose an improved approach of coupling two greedy heuristics designed to avoid an undesired decaying effect, a dramatically degenerated router performance on the near completion stages. This phenomenon is commonly observed on results produced by the conventional deterministic routing strategies using a single optimization cost function. Consequently, our results are significantly improved on both the number of routing tracks and routing segments by just applying low-complexity algorithms. On the tested MCNC and industrial benchmarks, the total number of tracks used by the best known two-step global/detailed router is 28% more than that used by our proposed method.Keywords
This publication has 9 references indexed in Scilit:
- New performance-driven FPGA routing algorithms1995
- A performance and routablity driven router for FPGAs considering path delays1995
- A New Global Routing Algorithm For FPGAs1994
- On The Np-completeness Of Regular 2-d Fpga Routing Architectures And A Novel Solution1994
- Layout driven logic synthesis for FPGAs1994
- Architecture of field-programmable gate arraysProceedings of the IEEE, 1993
- A detailed router for field-programmable gate arraysIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992
- Greedoids1991
- Worst-Case Performance Bounds for Simple One-Dimensional Packing AlgorithmsSIAM Journal on Computing, 1974