Reducing the Space Complexity of Pipelined Routing Using Modified Range Encoding

Interconnect delays are becoming an increasingly significant part of the critical path delay for circuits implemented in FPGAs. Pipelined interconnects have been proposed to address this problem, where long distance routes are pipelined using registers available in the configurable interconnect architecture. Unfortunately, pipelined interconnects are much harder to route than simple interconnects. QuickRoute is a fast, heuristic router based on PathFinder for pipelined interconnects. While its performance scales well with circuit size, it requires O(N²) space and in practice can only be used for circuits with up to about 10,000 nodes. This paper describes an efficient solution to this space problem based on arithmetic coding, a technique widely used in data compression. We show that this reduces the space complexity to O(NlogN) while only slightly affecting performance. This result will allow pipelined routing to be used even for very large FPGA architectures. Experiments show that memory usage is reduced by 90% even for our relatively small coarse-grained benchmark circuits