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.

A. Sharma, C. Ebeling, S. Hauck, "PipeRoute: A Pipelining-Aware Router for FPGAs", University of Washington, Dept. of EE Technical Report UWEETR-2002-0018, 2002.

FPGA 2003 Talk

Pipelined Interconnect Exploration

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.

FPGA 2004 Talk