We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Improved Parallel Legalization Schemes for Standard Cell Placement with Obstacles †.
- Authors
Oikonomou, Panagiotis; Dadaliaris, Antonios N.; Kolomvatsos, Kostas; Loukopoulos, Thanasis; Kakarountas, Athanasios; Stamoulis, Georgios I.
- Abstract
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.
- Subjects
PRUNING; LEGALIZATION; ELECTRIC power distribution grids; COMPUTATIONAL complexity; CELLS
- Publication
Technologies (2227-7080), 2019, Vol 7, Issue 1, p3
- ISSN
2227-7080
- Publication type
Article
- DOI
10.3390/technologies7010003