Enhancing Multi-Threaded Legalization Through k-d Tree Circuit Partitioning - Archive ouverte HAL Access content directly
Conference Papers Year :

Enhancing Multi-Threaded Legalization Through k-d Tree Circuit Partitioning

(1) , (1) , (2) , (1) , (1) , (1)
1
2

Abstract

In the physical synthesis of integrated circuits the legalization step may move all circuit cells to fix overlaps and misalignments. While doing so, it should cause the smallest perturbation possible to the solution found by previous optimization steps to preserve placement quality. Legalization techniques must handle circuits with millions of cells within acceptable runtimes, besides facing other issues such as mixed-cell-height and fence regions. In this work we propose a k-d tree data structure to partition the circuit, thus removing data dependency. Then, legalization is sped up through both input size reduction and parallel execution. As a use case we employed a modified version of the classic legalization algorithm Abacus. Our solution achieved a maximum speedup of 35 times over a sequential version of Abacus for the circuits of the ICCAD2015 CAD contest. It also provided up to 10% reduction on the average cell displacement.
Fichier principal
Vignette du fichier
kd-tree_partitioning.pdf (1.9 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01872451 , version 1 (12-09-2018)

Identifiers

Cite

Sheiny Fabre, José Luís Güntzel, Laércio Lima Pilla, Renan Netto, Tiago Fontana, et al.. Enhancing Multi-Threaded Legalization Through k-d Tree Circuit Partitioning. SBCCI 2018 - 31st Symposium on Integrated Circuits and Systems Design, Aug 2018, Bento Gonçalves, Brazil. pp.1-9, ⟨10.1109/SBCCI.2018.8533264⟩. ⟨hal-01872451⟩
144 View
312 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More