Distributed-memory parallel routing for field-programmable gate arrays
Authors:
- M.D.F. SchlagMSM.D.F. Schlag
- C. EbelingCEC. Ebeling
- L. McMurchieLML. McMurchie
- 1 August 2000
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 19 (8) , 850-862
Abstract
The problems of placement and routing are without doubt the most time-consuming part of the process of automatically synthesizing and configuring circuits for field-programmable gate arrays (FPGAs). FPGAs offer the ability to quickly reconfigure circuits to support rapid prototyping, emulation, or configurable computing, but the time to perform placement and routing, which can take many hours, has become a serious bottleneck. This problem is addressed here by showing that the negotiation-based routing paradigm, which has been applied successfully in several FPGA routers, can be parallelized to achieve increased performance without any significant decrease in the quality of the results. In this paper, we report several new findings related to the negotiation-based routing paradigm. We examine in-depth the convergence of the negotiation-based routing algorithm. We illustrate that the negotiation-based algorithm can be parallelized. Finally, we demonstrate that a negotiation-based parallel FPGA router performs well in terms of delay and speedup with practical FPGA circuits.Keywords
This publication has 8 references indexed in Scilit:
- Acceleration of an FPGA router2002
- Parallel global routing algorithms for standard cells2002
- Effect of the prefabricated routing track distribution on FPGA area-efficiencyIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1998
- A fast routability-driven router for FPGAs1998
- Placement and routing tools for the Triptych FPGAIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1995
- PathFinder: A Negotiation-Based Performance-Driven Router for FPGAs1995
- A detailed router for field-programmable gate arraysIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992
- Parallel global routing for standard cellsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1990