Stochastic, spatial routing for hypergraphs, trees, and meshes
- Creators
- Huang, Randy
- Wawrzynek, John
- DeHon, André
- Other:
- Trimberger, Steve
Abstract
FPGA place and route is time consuming, often serving as the major obstacle inhibiting a fast edit-compile-test loop in prototyping and development and the major obstacle preventing late-bound hardware and design mapping for reconfigurable systems. Previous work showed that hardware-assisted routing can accelerate fanout-free routing on Fat-Trees by three orders of magnitude with modest modifications to the network itself. In this paper, we show how these techniques can be applied to any FPGA and how they can be implemented on top of LUT networks in cases where modification of the FPGA itself is not justified. We further show how to accommodate fanout and how to achieve comparable route quality to software-based methods. For a tree network, we estimate an FPGA implementation of our routing logic could route the Toronto Place and Route Benchmarks at least two orders of magnitude faster than a software Pathfinder while achieving within 3% of the aggregate quality. Preliminary results on small mesh benchmarks achieve within one track of vpr-fast.
Additional Information
© 2003 ACM. This research was funded in part by the DARPA Moletronics program under grant ONR N00014-01-0651 and by the NSF CAREER program under grant CCR-0133102.Additional details
- Eprint ID
- 71781
- DOI
- 10.1145/611817.611830
- Resolver ID
- CaltechAUTHORS:20161107-154348196
- N00014-01-0651
- Office of Naval Research (ONR)
- CCR-0133102
- NSF
- Created
-
2016-11-08Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field