Improving FPGA Placement with Dynamically Adaptive Stochastic Tunneling

    Authors

    M. J. Lin;J. Wawrzynek

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    IEEE Trans. Comput-Aided Des. Integr. Circuits Syst.

    Keywords

    Field-programmable gate array (FPGA); placement; simulated annealing; stochastic tunneling; POTENTIAL-ENERGY LANDSCAPES; MINIMIZATION; ARCHITECTURE; OPTIMIZATION; Computer Science, Hardware & Architecture; Computer Science, ; Interdisciplinary Applications; Engineering, Electrical & Electronic

    Abstract

    This paper develops a dynamically adaptive stochastic tunneling (DAST) algorithm to avoid the "freezing" problem commonly found when using simulated annealing for circuit placement on field-programmable gate arrays (FPGAs). The main objective is to reduce the placement runtime and improve the quality of final placement. We achieve this by allowing the DAST placer to tunnel energetically inaccessible regions of the potential solution space, adjusting the stochastic tunneling schedule adaptively by performing detrended fluctuation analysis, and selecting move types dynamically by a multi-modal scheme based on Gibbs sampling. A prototype annealing-based placer, called DAST, was developed as part of this paper. It targets the same computer-aided design flow as the standard versatile placement and routing (VPR) but replaces its original annealer with the DAST algorithm. Our experimental results using the benchmark suite and FPGA architecture file which comes with the Toronto VPR5 software package have shown a 18.3% reduction in runtime and a 7.2% improvement in critical-path delay over that of conventional VPR.

    Journal Title

    Ieee Transactions on Computer-Aided Design of Integrated Circuits and Systems

    Volume

    29

    Issue/Number

    12

    Publication Date

    1-1-2010

    Document Type

    Article

    Language

    English

    First Page

    1858

    Last Page

    1869

    WOS Identifier

    WOS:000284417400002

    ISSN

    0278-0070

    Share

    COinS