Improved Parallel Legalization Schemes for Standard Cell Placement with Obstacles

Technologies

Thanasis Loukopoulos¹  Athanasios Kakarountas¹  Antonios N. Dadaliaris²  Panagiotis Oikonomou²  Georgios I. Stamoulis³  Kostas Kolomvatsos⁴ 

[1] Computer Science and Biomedical Informatics, University of Thessaly, 35100 Lamia, Greece;Computer Science, University of Thessaly, 35131 Lamia, Greece;Electrical and Computer Engineering, University of Thessaly, 382 21 Volos, Greece;Informatics and Telecommunications, University of Athens, 106 79 Athens, Greece;

关键词: standard cell placement;    cell legalization;    obstacles;    Abacus;    Tetris;    parallelization.;   

DOI  :  10.3390/technologies7010003

来源: DOAJ

【 摘 要 】

In standard cell placement, a circuit is given consisting of cells with a standard height, (different widths) and the problem is to place the cells in the standard rows of a chip area so that no overlaps occur and some target function is optimized. The process is usually split into at least two phases. In a first pass, a global placement algorithm distributes the cells across the circuit area, while in the second step, a legalization algorithm aligns the cells to the standard rows of the power grid and alleviates any overlaps. While a few legalization schemes have been proposed in the past for the basic problem formulation, few obstacle-aware extensions exist. Furthermore, they usually provide extreme trade-offs between time performance and optimization efficiency. In this paper, we focus on the legalization step, in the presence of pre-allocated modules acting as obstacles. We extend two known algorithmic approaches, namely Tetris and Abacus, so that they become obstacle-aware. Furthermore, we propose a parallelization scheme to tackle the computational complexity. The experiments illustrate that the proposed parallelization method achieves a good scalability, while it also efficiently prunes the search space resulting in a superlinear speedup. Furthermore, this time performance comes at only a small cost (sometimes even improvement) concerning the typical optimization metrics.

【 授权许可】

Unknown