Scalable and deterministic timing-driven parallel placement for FPGAs
University of British Columbia, Vancouver, BC, Canada
Proceedings of the 19th ACM/SIGDA international symposium on Field programmable gate arrays, FPGA ’11
@inproceedings{wang2011scalable,
title={Scalable and deterministic timing-driven parallel placement for FPGAs},
author={Wang, C.C. and Lemieux, G.G.F.},
booktitle={Proceedings of the 19th ACM/SIGDA international symposium on Field programmable gate arrays},
pages={153–162},
year={2011},
organization={ACM}
}
This paper describes a parallel implementation of the timing-driven VPR 5.0 simulated annealing engine. By restricting the move distance to a confined neighborhood, it is possible to consider a large number of non-conflicting moves in parallel and achieve a deterministic result. The full timing-driven algorithm is parallelized, including the detailed timing analysis updates done periodically while placement progresses. The limited move slightly degrades the placement quality, but this is necessary to expose greater degrees of parallelism. The overall bounding box metric degrades about 11% and critical path delay metric degrades about 8% compared to VPR’s original algorithm, but we show the amount of degradation is independent of the number of threads. Overall, the parallel implementation scales to a speedup of 123x using 25 threads compared to VPR. With additional tuning effort, we believe the algorithm can be scaled to a larger number of threads, perhaps even run on a GPU, with little additional quality degradation.
September 15, 2011 by hgpu
