The problem of routing pipelined
signals is different from the conventional FPGA routing problem. For example,
the two terminal N-Delay 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 multi-terminal pipelined signal, the problem
is to find a Minimum Spanning Tree that contains sufficient pipelining resources
such that the delay constraint at each sink is satisfied.
In this work, we prove that the two terminal N-Delay problem is NP-Complete. We
then propose an optimal algorithm for finding a lowest cost 1-Delay route. Next,
the optimal 1-Delay router is used as the building block for a greedy two terminal
N-Delay router. Finally, a multi-terminal routing algorithm (PipeRoute) that
effectively leverages the 1-Delay and N-Delay routers is proposed. PipeRoute’s
performance is evaluated by routing a set of retimed benchmarks on the RaPiD
architecture. Our results show that the architecture overhead incurred in routing
netlists on RaPiD is less than a factor of two. Further, the results indicate a
possible trend between the architecture overhead and the percentage of pipelined
signals in a netlist.
A. Sharma, C.Ebeling, S. Hauck,
"PipeRoute: A Pipelining-Aware
Router for FPGAs", 11th ACM/SIGDA Symposium on
Field-Programmable Gate Arrays, pp 68-77, 2003.
In this work, we parameterize and explore the interconnect structure of pipelined FPGAs. Specifically, we explore the effects of interconnect register population, length of registered routing track segments, registered IO terminals of logic units, and the flexibility of the interconnect structure on the performance of a pipelined FPGA. Our experiments with the RaPiD architecture identify tradeoffs that must be made while designing the interconnect structure of a pipelined FPGA. The post-exploration architecture that we found shows a 19% improvement over RaPiD, while the area overhead incurred in placing and routing benchmarks netlists on the post-exploration architecture is 18%.
A. Sharma, K. Compton, C. Ebeling, S. Hauck,
"Exploration of Pipelined FPGA Inteconnect
Structures", 12th ACM/SIGDA Symposium on Field-Programmable
Gate Arrays, pp. 13 - 22, 2004.