PipeRoute: a pipelining-aware router for reconfigurable architectures

<p>{W}e present a pipelining-aware router for fieldprogrammable gate arrays ({FPGA}s). {T}he problem of routing pipelined signals is different from the conventional {FPGA} routing problem. {T}he two-terminal {N}/sub {D}/ pipelined routing problem is to find the lowest cost route between a source and sink that goes through at least {N} ({N}/spl ges/1) distinct pipelining resources. {I}n 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. {I}n this paper, we first present an optimal algorithm for finding a lowest cost 1/sub {D}/ route. {T}he optimal 1/sub {D}/ algorithm is then used as a building block for a greedy two-terminal {N}/sub {D}/ router. {N}ext, we discuss the development of a multiterminal routing algorithm ({P}ipe{R}oute) that effectively leverages both the 1/sub {D}/ and {N}/sub {D}/ routers. {F}inally, we present a preprocessing heuristic that enables the application of {P}ipe{R}oute to pipelined {FPGA} architectures. {P}ipe{R}oute's performance is evaluated by routing a set of benchmark netlists on the reconfigurable pipelined datapath ({R}a{P}i{D}) architecture. {O}ur results show that the architecture overhead incurred in routing netlists on {R}a{P}i{D} is less than 20%. {F}urther, the results indicate a possible trend between the architecture overhead and the percentage of pipelined signals in a netlist.</p>