QuickRoute: a fast routing algorithm for pipelined architectures

<p>{A}s interconnect delays begin to dominate logic delays in large circuits, pipelined interconnects will be needed to achieve the highest performance. {I}n {FPGA}s, this pipelining will be provided by the configurable interconnect architecture itself. {T}his changes the routing problem substantially since the shortest path problem, which is at the core of any router, becomes {NP}-hard when latency constraints are added. {T}hat is, if signals must be routed through a given number of registers between source and destination, an efficient shortest path algorithm like {D}jikstra's algorithm is no longer an option. {W}e propose here an approximate algorithm that uses simple heuristics to solve the pipelined shortest path problem efficiently. {W}e have incorporated {Q}uick{R}oute in the {P}ath{F}inder router to route pipelined interconnects. {W}e present the results achieved with {Q}uick{R}oute for several circuits with heavily pipelined interconnect which show an improvement over a previously described algorithm.</p>