Published Articles >> Table of Contents >> Abstract

10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'02)   p. 205
Hardware-Assisted Fast Routing
Andre DeHon, California Institute of Technology
Randy Huang, University of California at Berkeley
John Wawrzynek, University of California at Berkeley

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FPGA.2002.1106675
Send link to a friend

Abstract
To fully realize the benefits of partial and rapid reconfiguration of field-pr ogrammable devices, we often need to dynamically schedule computing tasks and generate instance-specific configurations — new graphs which must be routed during program execution. Consequently, route time can be a significant overhead cost reducing the achievable net benefits of dynamic configuration generation. By adding hardware to accelerate routing, we show that it is possible to compute routes in one thousandth the time of a traditional, software router and achieve routes that are within 5% of the state-of-the-art offline routing algorithms for a sample set of application netlists and within 25% for a set of difficult synthetic benchmarks. We further outline how strategic use of parallelism can allow the total route time to scale substantially less than linearly in graph size. We detail the source of the benefits in our approach and survey a range of options for hardware assistance that vary from a speedup of over 10× with modest hardware overhead to speedups in excess of 1000×.
Back to Top Additional Information
Citation:  Andre DeHon, Randy Huang, John Wawrzynek, "Hardware-Assisted Fast Routing," fccm, p. 205,  10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'02),  2002