Title :
Distributed-memory parallel routing for field-programmable gate arrays
Author :
Chan, Pak K. ; Schlag, Martine D F ; Ebeling, Carl ; Mcmurchie, Larry
Author_Institution :
Dept. of Comput. Eng., California Univ., Santa Cruz, CA, USA
fDate :
8/1/2000 12:00:00 AM
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 :
circuit layout CAD; field programmable gate arrays; logic CAD; network routing; parallel algorithms; automatic synthesizing; configurable computing; delay; distributed-memory parallel routing; emulation; field-programmable gate arrays; negotiation-based routing paradigm; rapid prototyping; speedup; Circuit synthesis; Concurrent computing; Convergence; Costs; Delay; Emulation; Field programmable gate arrays; Prototypes; Routing; Switches;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on