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 metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Laércio Lima Pilla Connect in order to contact the contributor
Submitted on : Wednesday, September 12, 2018 - 10:28:36 AM
Last modification on : Thursday, October 21, 2021 - 3:45:28 AM
Long-term archiving on: : Thursday, December 13, 2018 - 12:23:02 PM


Files produced by the author(s)




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⟩



Record views


Files downloads