UWEE Tech Report Series

PipeRoute - A Pipelining-Aware Router for FPGAs


UWEETR-2002-0018

Author(s):
Akshay Sharma, Carl Ebeling, Scott Hauck

Keywords:

Abstract

In this paper 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 multi-terminal routing algorithm (PipeRoute) that effectively leverages the 1-Delay and N-Delay routers is proposed. We evaluate PipeRoute’s performance by routing a set of retimed benchmarks on the RaPiD [3] 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.

Download the PDF version

Download the Gzipped Postscript version