Paper Info
Title
Parallel FPGA routing based on the operator formulation
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 inter-dependence 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.
Year
DOI
Venue
2014
10.1145/2593069.2593177
Design Automation Conference
Keywords
Field
DocType
field programmable gate arrays,logic design,microprocessor chips,multiprocessing systems,Galois API,PathFinder,operator formulation,parallel FPGA routing,routing algorithm,shared memory multiprocessor,software transactional memory,versatile place and route framework,Field Programmable Gate Array (FPGA),Irregular Algorithm,Maze Expansion,Routing,Routing Resource Graph (RRG),Software Transactional Memory (STM)
Link-state routing protocol,Computer science,Real-time computing,Electronic engineering,route,Routing table,Speedup,Shared memory,Enhanced Interior Gateway Routing Protocol,Parallel computing,Place and route,Router,Embedded system
Conference
ISSN
Citations 
PageRank 
0738-100X
13
0.63
References 
Authors
18
2
Name
Order
Citations
PageRank
Yehdhih Ould Mohammed Moctar1181.82
Philip Brisk28010.05