Skip to Main content Skip to Navigation
Conference papers

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

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.
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01872451
Contributor : Laércio Lima Pilla <>
Submitted on : Wednesday, September 12, 2018 - 10:28:36 AM
Last modification on : Tuesday, October 6, 2020 - 4:20:09 PM
Long-term archiving on: : Thursday, December 13, 2018 - 12:23:02 PM

File

kd-tree_partitioning.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

301

Files downloads

517