29-01-2013, 03:17 PM
FPGA-Based Multilayer Maze Routing Accelerator
FPGA-Based Multilayer Maze Routing.ppt (Size: 572.5 KB / Downloads: 19)
The Routing Problem
Given
a set desired connections (a netlist)
A set of layers available to make connections
Create a set of connections that:
Completely connects the terminals of each net
Meets timing constraints on delay for critical nets
Minimizes the area consumed by routing
Minimizes the crossings between each layer
Resolves crosstalk and noise issues
Work Accomplished
Modified Lee’s algorithm such that the propagation time for expansion is dramatically reduced to O (d) and the time required for clean up to 1 clock cycle.
Successfully designed the single layer Maze Router, Complete with FIFO Rams, Control unit, Decoders, Encoders and the 4X4 and 8X8 programming array.
Perused through the nuances of Multi Layer Maze Router and currently working for its successful completion.
PE Details
Efficient implementation -
32 LUTs in a Xilinx Spartan/ Virtex FPGA for each PE
Large Xilinx FPGAs can support grids of 32 X 32 PEs
Execution time comparison: hw vs. sw:
Expansion: O (d) for L layers vs. O(d2)
Trace back: O (d) vs. O (d)
Cleanup: 1 vs. O(N2)
Single-net routing speedup of 93X over software for a 16 X 16 4 layer array (2.5GHz Pentium 4)
Drawbacks
Limited clock speed due to long timing paths in design
No support for multiple net routing
Conclusions
Extended accelerator for Maze Routing
Support for Rip-Up and Reroute
Support for multiple net routing
Faster clock speed
Control algorithm based on simulated evolution
Future Work
Larger arrays in a PCI-based accelerator
Performance measurements including interface overhead
Hardware support to accelerate control algorithm