Optimal placement by branch-and-price | Zendy

Pradeep Ramachandaran | Zendy; Ameya R. Agnihotri | Zendy; Satoshi Ono | Zendy; Purushothaman Damodaran | Zendy; Krishnaswami Srihari | Zendy; Patrick H. Madden | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Optimal placement by branch-and-price

Author(s) -

Pradeep Ramachandaran,

Ameya R. Agnihotri,

Satoshi Ono,

Purushothaman Damodaran,

Krishnaswami Srihari,

Patrick H. Madden

Publication year - 2005

Publication title -

citeseer x (the pennsylvania state university)

Language(s) - English

Resource type - Conference proceedings

DOI - 10.1145/1120725.1120865

Subject(s) - computer science , integer programming , reliability (semiconductor) , mathematical optimization , placement , power consumption , branch and price , linear programming , simple (philosophy) , branch and cut , scale (ratio) , power (physics) , physical design , circuit design , mathematics , algorithm , embedded system , philosophy , physics , quantum mechanics , epistemology

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research