[ACM Press the 2003 ACM/SIGDA eleventh international symposium - Monterey, California, USA (2003.02.23-2003.02.25)] Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays - FPGA '03 - PipeRoute

✍ Scribed by Sharma, Akshay; Ebeling, Carl; Hauck, Scott

• Book ID: 120933400
• Publisher: ACM Press
• Year: 2003
• Tongue: English
• Weight: 176 KB
• Edition: 2003
• Category: Article
• ISBN-13: 9781581136517
• DOI: 10.1145/611817.611829

✦ Synopsis

We present a pipelining-aware router for FPGAs. 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. We begin this work by proving 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 multiterminal 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 [2] architecture. Our results show that the architecture overhead incurred in routing retimed 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.