Parallel Algorithms and Methods for FPGA Placement

This thesis evaluates new parallel approaches for simulated annealing-based placement, and also leverages recent processor features such as hardware transactional memory (TM) and thread-level speculation (TLS) that aim to make parallel programming easier. Our contributions include a quantitative comparison of the speedup and quality-of-results obtained with various parallel algorithmic and programming approaches. We find that while TM and TLS simplify parallel programming, neither can achieve a compelling combination of speedup and placement quality. Our best algorithms require more programming effort than TM or TLS, but outperform prior approaches: without loss of placement quality, we can reach 5.9x speedup with a deterministic algorithm and 34x speedup with a non-deterministic one. We also evaluate the impact of hardware platforms on placement time. We find that while the greatest speedups occur on systems with many (57) simple cores, the fastest execution is achieved by systems with fewer (16) more complex cores.%%%%M.A.S.