Name
Abstract | ||
|---|---|---|
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. 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. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1145/611817.611829 | FPGA |
Keywords | Field | DocType |
n-delay routers,multi-terminal pipelined signal,piperoute,multi-terminal routing algorithm,pipelining,routing,minimum spanning tree,pipelined signal,1-delay route,bfs,retiming,retimed circuits,terminal n-delay router,pipelined circuits,pipelining-aware router,terminal n-delay problem,terminal n-delay,1-delay router,conventional fpga routing problem,satisfiability | Equal-cost multi-path routing,Link-state routing protocol,Dynamic Source Routing,Static routing,Computer science,Parallel computing,Destination-Sequenced Distance Vector routing,DSRFLOW,Real-time computing,Routing table,Metrics | Conference |
ISBN | Citations | PageRank |
1-58113-651-X | 13 | 0.88 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Akshay Sharma | 1 | 85 | 7.28 |
| Carl Ebeling | 2 | 1405 | 185.32 |
| Scott Hauck | 3 | 2539 | 232.71 |