Predicting the performance of FPGA routing algorithms

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.