PipeRoute: A pipelining-aware router for reconfigurable architectures
We present a pipelining-aware router for field-programmable gate arrays (FPGAs). The problem of routing pipelined signals is different from the conventional FPGA routing problem. The two-terminal N-D pipelined routing problem is to find the lowest cost route between a source and sink that goes through at least N (N >= 1) distinct pipelining resources. In the case of a multiterminal pipelined signal, the problem is to find a minimum spanning tree (MST) that contains sufficient pipelining resources such that pipelining constraints at each sink are satisfied. In this paper, we first present an optimal algorithm for finding a lowest cost 1(D) route. The optimal 1(D) algorithm is then used as a building block for a greedy two-terminal N-D router. Next, we discuss the development of a multiterminal routing algorithm (PipeRoute) that effectively leverages both the 1(D) and N-D routers. Finally, we present a preprocessing heuristic that enables the application of PipeRoute to pipelined FPGA architectures. PipeRoute's performance is evaluated by routing a set of benchmark netlists on the reconfigurable pipelined datapath (RaPiD) architecture. Our results show that the architecture overhead incurred in routing netlists on RaPiD is less than 20%. Further, the results indicate a possible trend between the architecture overhead and the percentage of pipelined signals in a netlist.
routing reconfigurable architectures field-programmable gate arrays (fpga) design automation