Accelerating FPGA routing using architecture-adaptive A* techniques

The A* algorithm is a well-known path-finding technique that is used to speed up FPGA routing. Previously published A*-based techniques are either targeted to a class of architecturally similar devices, or require prohibitive amounts of memory to preserve architecture adaptability. This work presents architecture-adaptive A* techniques that require significantly less memory than previously published work. Our techniques are able to produce routing runtimes that are within 7% (on an island-style architecture) and 9% better (on a hierarchical architecture) than targeted heuristic techniques. Memory improvements range between 30× (island-style) and 140× (hierarchical architecture).