This thesis describes a parallel implementation of the timing-driven VPR 5.0 simulated-annealing placement engine. By partitioning the grid into regions and allowing distant data to grow stale, it is possible to consider a large number of non-conflicting moves in parallel and achieve a deterministic result. The full timing-driven placement algorithm is parallelized, including swap evaluation, bounding-box calculation and the detailed timing-analysis updates. The partitioned region approach slightly degrades the placement quality, but this is necessary to expose greater parallelism. We also suggest a method to recover the lost quality. In simulated annealing, runtime can be shortened at the expense of quality. Using this method, the serial placer can achieve a maximum speedup of 100X while quality metrics degrades as much as 100%. In contrast, the parallel placer can scale beyond 500X with all quality metrics degrading by less than 30%. Specifically, at the point where the parallel placer begins to dominate over the serial placer, the post-routing minimum channel width, wirelength and critical-path delay degrades 13%, 10% and 7% respectively on average compared to VPR’s original algorithm,while achieving a 140X to 200X speedup 25 threads. Finally, it is shown that the amount of degradation in the parallel placer is independent of the number of threads used. ; Applied Science, Faculty of ; Electrical and Computer Engineering, Department of ; Graduate


    Access

    Download


    Export, share and cite



    Title :

    Scalable and deterministic timing-driven parallel placement for FPGAs


    Contributors:

    Publication date :

    2011-01-01


    Type of media :

    Theses


    Type of material :

    Electronic Resource


    Language :

    English


    Classification :

    DDC:    629






    RadTolerant FPGAs

    Emerald Group Publishing | 1999


    Deterministic Ethernet for Scalable, Modular Launcher Avionics (AIAA 2016-5623)

    Fidi, Christian / Dufour, Jean-Francois | British Library Conference Proceedings | 2016