Title :
Improved cut sequences for partitioning based placement
Author :
Yildiz, Mehmet Can ; Madden, Patrick H.
Author_Institution :
Dept. of Comput. Sci., State Univ. of New York, Binghamton, NY, USA
Abstract :
Recursive partitioning based placement has a long history, but there has been little consensus on how cut sequences should be chosen. In this paper, we present a dynamic programming approach to cut sequence generation. If certain assumptions hold, these sequences are optimal. After study of these optimal sequences, we observe that an extremely simple method can be used to construct sequences that are near optimal. Using this method, our bisection based placement tool Feng Shui outperforms the previously presented Capo tool by 11% on a large benchmark. By integrating our cut sequence method into Capo, we are able to improve performance by 5%, bringing the results of Feng Shui and Capo closer together.
Keywords :
cellular arrays; circuit layout CAD; dynamic programming; integrated circuit layout; logic CAD; logic partitioning; Capo; Feng Shui; benchmark; bisection based placement tool; cut sequence generation; cut sequences; dynamic programming approach; optimal sequences; partitioning based placement; recursive partitioning; Circuit simulation; Computer science; Dynamic programming; History; Linear programming; Modems; Partitioning algorithms; Permission; Simulated annealing; Wire;
Conference_Titel :
Design Automation Conference, 2001. Proceedings
Print_ISBN :
1-58113-297-2
DOI :
10.1109/DAC.2001.156241