IJMLC 2018 Vol.8(6): 542-548 ISSN: 2010-3700
DOI: 10.18178/ijmlc.2018.8.6.743

Efficient Simulated Annealing-Based Placement Algorithm for Island Style FPGAs

Runxiao Shi, Lan Ma, and Takahiro Watanabe

Abstract—This paper proposes a group-based very fast simulated annealing (GB-VFSA) algorithm to achieve higher-quality placement in a shorter CPU time. We first introduce a temperature-dependent perturbation model based on Cauchy distribution to generate new solutions. Then, we put high-connected blocks into one group and use a group as a unit for placement. In order to avoid premature convergence of the algorithm, multiple potential solutions are used to search the solution space at the same time. The idea “pheromone” which comes from ant colony optimization is used to realize the communication between multiple potential solutions. Experimental results using MCNC beachmarks show that GB-VFSA achieved 23% reduction in CPU time and 3.6% improvement in maximal time delay over traditional simulating annealing algorithm.

Index Terms—Placement, simulating annealing, island style FPGAs, block group, potential solution group.

The authors are with the Graduate School of Information, Production and Systems, Waseda University, Kitakyushu-shi, CO 808-0135 Japan (e-mail: srxssinseu@toki.waseda.jp, mimolan@toki.waseda.jp, watt@waseda.jp).

[PDF]

Cite: Runxiao Shi, Lan Ma, and Takahiro Watanabe, "Efficient Simulated Annealing-Based Placement Algorithm for Island Style FPGAs," International Journal of Machine Learning and Computing vol. 8, no. 6, pp. 542-548, 2018.

General Information

  • ISSN: 2010-3700 (Online)
  • Abbreviated Title: Int. J. Mach. Learn. Comput.
  • Frequency: Bimonthly
  • DOI: 10.18178/IJMLC
  • Editor-in-Chief: Dr. Lin Huang
  • Executive Editor:  Ms. Cherry L. Chen
  • Abstracing/Indexing: Scopus (since 2017), EI (INSPEC, IET), Google Scholar, Crossref, ProQuest, Electronic Journals Library.
  • E-mail: ijmlc@ejournal.net