Skip to main content
eScholarship
Open Access Publications from the University of California

Parallel FPGA routing based on the operator formulation

  • Author(s): Moctar, YOM
  • Brisk, P
  • et al.

Published Web Location

http://www1.cs.ucr.edu/faculty/philip/papers/conferences/dac14/dac14-routing.pdf
No data is associated with this publication.
Abstract

We have implemented an FPGA routing algorithm on a shared memory multi-processor using the Galois API, which offers speculative parallelism in software. The router is a parallel implementation of PathFinder, which is the basis for most commercial FPGA routers. We parallelize the maze expansion step for each net, while routing nets sequentially to limit the amount of rollback that would likely occur due to misspeculation. Our implementation relies on non-blocking priority queues, which use software transactional memory (SMT), to identify the best route for each net. Our experimental results demonstrate scalability for large benchmarks and that the amount of available parallelism depends primarily on the circuit size, not the interdependence of signals. We achieve an average speedup of approximately 3x compared to the most recently published work on parallel multi-threaded FPGA routing, and up to 6x in comparison to the single-threaded router implemented in the publicly available Versatile Place and Route (VPR) framework. Copyright 2014 ACM.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item