Optimal placement by branch-and-price

被引：5

作者：

Ramachandaran, Pradeep ^{[1
]}

Agnihotri, Ameya R. ^{[1
]}

Ono, Satoshi ^{[1
]}

Damodaran, Purushothaman ^{[1
]}

Srihari, Krishnaswami ^{[1
]}

Madden, Patrick H. ^{[1
]}

机构：

[1] SUNY Binghamton, SSIE, Binghamton, NY USA

来源：

ASP-DAC 2005: PROCEEDINGS OF THE ASIA AND SOUTH PACIFIC DESIGN AUTOMATION CONFERENCE, VOLS 1 AND 2 | 2005年

关键词：

D O I：

10.1145/1120725.1120865

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Circuit placement has a large impact on all aspects of performance; speed, power consumption, reliability, and cost are all affected by the physical locations. of interconnected transistors., The placement problem is NP-Complete for even simple metrics. In this paper, we apply techniques developed by the Operations Research (OR) community to the placement problem. Using an Integer Programming (IP) formulation and by applying a "branch-and-price" approach, we are able to optimally solve placement problems that are an order of magnitude larger than those addressed by traditional methods. Our results show that suboptimality is rampant on the small scale, and that there is merit in increasing the size of optimization windows used in detail placement.

引用

页码：337 / 342

页数：6

共 21 条

[1]

Adya S.N., 2003, Proc. ACM/IEEE International Symposium on Physical Design, P95

[2] Fractional cut: Improved recursive bisection placement [J].