A novel macro placement approach based on simulated evolution algorithm

Jai Ming Lin, You Lun Deng, Ya Chu Yang, Jia Jian Chen, Yao Chieh Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper proposes a novel approach to handle the macro placement problem, which integrates the simulated evolution algorithm and corner stitching data structure. Unlike the simulated annealing based algorithm which has to pack each macro to a contour in its representation, a macro can be placed at any empty region according to the corner stitching. Hence, even when a chip contains several preplaced macros which do not abut to boundaries, it can be easily handled by our approach. Moreover, we further apply an efficient and effective simulated evolution algorithm to refine a placement. To avoid standard cells being placed at a small region or being pushed away from related macros in the cell placement stage, our macro placement method also preserves placement areas for standard cells by expanding macros according to the design hierarchy. The experimental results show that our approach obtains better results than CP-tree and a commercial tool in term of wirelength and routability. More importantly, our methodology can complete a large test case in 6 minutes that CP-tree fails to get a result in one day, and their runtime is 659 times longer than ours even when large test cases are ignored.

Original languageEnglish
Title of host publication2019 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2019 - Digest of Technical Papers
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728123509
DOIs
Publication statusPublished - 2019 Nov
Event38th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2019 - Westin Westminster, United States
Duration: 2019 Nov 42019 Nov 7

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
Volume2019-November
ISSN (Print)1092-3152

Conference

Conference38th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2019
CountryUnited States
CityWestin Westminster
Period19-11-0419-11-07

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'A novel macro placement approach based on simulated evolution algorithm'. Together they form a unique fingerprint.

Cite this