Predicting the performance of FPGA routing algorithms

Author

Gao, Li ; Billups, Brent ; Purdy, Carla

Author_Institution

Electr. & Comput. Eng. & Comput. Sci. Dept., Cincinnati Univ., OH, USA

Volume

3

fYear

2002

fDate

4-7 Aug. 2002

Abstract

Recent work on the NP-complete satisfiability problem (SAT) has revealed that commonly used heuristics for SAT may exhibit wildly unpredictable behavior for even small perturbations in input data. This type of behavior is unacceptable for the many heuristic algorithms which form the basis for modem VLSI CAD systems. We study the behavior of three well-known FPGA routing algorithms. Our results show that algorithm performance can vary widely under reasonable input perturbations. Our study also gives insight into how to improve CAD system performance by providing optimization options to users and to CAD tool designers.

Keywords

VLSI; circuit optimisation; computational complexity; field programmable gate arrays; logic CAD; network routing; CAD systems; CAD tool designers; FPGA; NP-complete satisfiability problem; VLSI; heuristic algorithms; input perturbations; optimization options; routing algorithms; Algorithm design and analysis; Circuits; Design automation; Field programmable gate arrays; Heuristic algorithms; Logic testing; Partitioning algorithms; Routing; Statistics; Visualization;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 2002. MWSCAS-2002. The 2002 45th Midwest Symposium on

Print_ISBN

0-7803-7523-8

Type

conf

DOI

10.1109/MWSCAS.2002.1187016

Filename

1187016