Floorplan sizing by linear programming approximation

In this paper, we present an approximation algorithm by linear programming (LP) for floorplan sizing problem. Given any topological constraints between blocks, we can formulate it as an LP problem with a cost function for the minimum bounding box area. Unlike slicing structures, this approach can ha...

Full description

Saved in:
Bibliographic Details
Main Authors: Chen, Pinhong, Kuh, Ernest S.
Format: Conference Proceeding
Language:English
Subjects:
Applied computing > Physical sciences and engineering > Engineering
Approximation algorithms
Constraint optimization
Cost function
Functional programming
Hardware > Electronic design automation > Physical design (EDA)
Hardware > Emerging technologies
Hardware > Robustness
Hardware > Very large scale integration design
Linear approximation
Linear programming
Mathematics of computing > Mathematical analysis > Functional analysis > Approximation
Mathematics of computing > Mathematical analysis > Mathematical optimization > Continuous optimization > Linear programming
Permission
Theory of computation > Design and analysis of algorithms > Approximation algorithms analysis
Theory of computation > Design and analysis of algorithms > Mathematical optimization > Continuous optimization > Linear programming
Timing
Topology
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 471
container_issue
container_start_page 468
container_title
container_volume
creator Chen, Pinhong
Kuh, Ernest S.
description In this paper, we present an approximation algorithm by linear programming (LP) for floorplan sizing problem. Given any topological constraints between blocks, we can formulate it as an LP problem with a cost function for the minimum bounding box area. Unlike slicing structures, this approach can handle any topological constraints as well as soft/hard/preplaced blocks, and timing constraints. Empirically, our method needs few iterations to find the optimum solution and shows one order of improvement over previous methods both in run time and capability to handle a larger problem size even on a very limited computing resource PC.
doi_str_mv 10.1145/337292.337547
format conference_proceeding
fullrecord <record><control><sourceid>proquest_ieee_</sourceid><recordid>TN_cdi_proquest_miscellaneous_27520187</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>855356</ieee_id><sourcerecordid>27520187</sourcerecordid><originalsourceid>FETCH-LOGICAL-a302t-a956fab7784d2dac1db4c4eaca5f3ac088ec9d10dd8ba59562fac94398e909a13</originalsourceid><addsrcrecordid>eNqNkM1LAzEQxQMqWGqPXjztyZNbM_lokqMUW4WCFwVvYTabLdH9ctOC9a83ZQWPOpfHDD9m5j1CLoHOAYS85Vwxw-ZJpFAnZGaUBqkBOGgFp2RCFdc5UPp6TmYxvtFUSjJN9YSIVd11Q19jm8XwFdptVhyyOrQeh6wfuu2ATXOcYp-6z9DgLnTtBTmrsI5-9qNT8rK6f14-5Jun9ePybpMjp2yXo5GLCgultChZiQ7KQjjh0aGsODqqtXemBFqWukCZYFahM4Ib7Q01CHxKrse96fbH3sedbUJ0vk7f-m4fLQdQaiH-BlmyS1MYCbwaweC9t_2QDA0Hq6XkcvG7BV1ji657jxaoPSZsx4TtmHACb_4F2mIIvuLfimZ47A</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype><pqid>27520187</pqid></control><display><type>conference_proceeding</type><title>Floorplan sizing by linear programming approximation</title><source>IEEE Xplore All Conference Series</source><creator>Chen, Pinhong ; Kuh, Ernest S.</creator><creatorcontrib>Chen, Pinhong ; Kuh, Ernest S.</creatorcontrib><description>In this paper, we present an approximation algorithm by linear programming (LP) for floorplan sizing problem. Given any topological constraints between blocks, we can formulate it as an LP problem with a cost function for the minimum bounding box area. Unlike slicing structures, this approach can handle any topological constraints as well as soft/hard/preplaced blocks, and timing constraints. Empirically, our method needs few iterations to find the optimum solution and shows one order of improvement over previous methods both in run time and capability to handle a larger problem size even on a very limited computing resource PC.</description><identifier>ISSN: 0738-100X</identifier><identifier>ISBN: 9781581131871</identifier><identifier>ISBN: 1581131879</identifier><identifier>DOI: 10.1145/337292.337547</identifier><language>eng</language><publisher>New York, NY, USA: ACM</publisher><subject>Applied computing -- Physical sciences and engineering -- Engineering ; Approximation algorithms ; Constraint optimization ; Cost function ; Functional programming ; Hardware -- Electronic design automation -- Physical design (EDA) ; Hardware -- Emerging technologies ; Hardware -- Robustness ; Hardware -- Very large scale integration design ; Linear approximation ; Linear programming ; Mathematics of computing -- Mathematical analysis -- Functional analysis -- Approximation ; Mathematics of computing -- Mathematical analysis -- Mathematical optimization -- Continuous optimization -- Linear programming ; Permission ; Theory of computation -- Design and analysis of algorithms -- Approximation algorithms analysis ; Theory of computation -- Design and analysis of algorithms -- Mathematical optimization -- Continuous optimization -- Linear programming ; Timing ; Topology</subject><ispartof>37th Design Automation Conference, 2000, 2000, p.468-471</ispartof><rights>2000 ACM</rights><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>309,310,314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Chen, Pinhong</creatorcontrib><creatorcontrib>Kuh, Ernest S.</creatorcontrib><title>Floorplan sizing by linear programming approximation</title><title>37th Design Automation Conference, 2000</title><addtitle>DAC</addtitle><description>In this paper, we present an approximation algorithm by linear programming (LP) for floorplan sizing problem. Given any topological constraints between blocks, we can formulate it as an LP problem with a cost function for the minimum bounding box area. Unlike slicing structures, this approach can handle any topological constraints as well as soft/hard/preplaced blocks, and timing constraints. Empirically, our method needs few iterations to find the optimum solution and shows one order of improvement over previous methods both in run time and capability to handle a larger problem size even on a very limited computing resource PC.</description><subject>Applied computing -- Physical sciences and engineering -- Engineering</subject><subject>Approximation algorithms</subject><subject>Constraint optimization</subject><subject>Cost function</subject><subject>Functional programming</subject><subject>Hardware -- Electronic design automation -- Physical design (EDA)</subject><subject>Hardware -- Emerging technologies</subject><subject>Hardware -- Robustness</subject><subject>Hardware -- Very large scale integration design</subject><subject>Linear approximation</subject><subject>Linear programming</subject><subject>Mathematics of computing -- Mathematical analysis -- Functional analysis -- Approximation</subject><subject>Mathematics of computing -- Mathematical analysis -- Mathematical optimization -- Continuous optimization -- Linear programming</subject><subject>Permission</subject><subject>Theory of computation -- Design and analysis of algorithms -- Approximation algorithms analysis</subject><subject>Theory of computation -- Design and analysis of algorithms -- Mathematical optimization -- Continuous optimization -- Linear programming</subject><subject>Timing</subject><subject>Topology</subject><issn>0738-100X</issn><isbn>9781581131871</isbn><isbn>1581131879</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2000</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNqNkM1LAzEQxQMqWGqPXjztyZNbM_lokqMUW4WCFwVvYTabLdH9ctOC9a83ZQWPOpfHDD9m5j1CLoHOAYS85Vwxw-ZJpFAnZGaUBqkBOGgFp2RCFdc5UPp6TmYxvtFUSjJN9YSIVd11Q19jm8XwFdptVhyyOrQeh6wfuu2ATXOcYp-6z9DgLnTtBTmrsI5-9qNT8rK6f14-5Jun9ePybpMjp2yXo5GLCgultChZiQ7KQjjh0aGsODqqtXemBFqWukCZYFahM4Ib7Q01CHxKrse96fbH3sedbUJ0vk7f-m4fLQdQaiH-BlmyS1MYCbwaweC9t_2QDA0Hq6XkcvG7BV1ji657jxaoPSZsx4TtmHACb_4F2mIIvuLfimZ47A</recordid><startdate>20000101</startdate><enddate>20000101</enddate><creator>Chen, Pinhong</creator><creator>Kuh, Ernest S.</creator><general>ACM</general><general>IEEE</general><scope>6IE</scope><scope>6IH</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIO</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20000101</creationdate><title>Floorplan sizing by linear programming approximation</title><author>Chen, Pinhong ; Kuh, Ernest S.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-a302t-a956fab7784d2dac1db4c4eaca5f3ac088ec9d10dd8ba59562fac94398e909a13</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2000</creationdate><topic>Applied computing -- Physical sciences and engineering -- Engineering</topic><topic>Approximation algorithms</topic><topic>Constraint optimization</topic><topic>Cost function</topic><topic>Functional programming</topic><topic>Hardware -- Electronic design automation -- Physical design (EDA)</topic><topic>Hardware -- Emerging technologies</topic><topic>Hardware -- Robustness</topic><topic>Hardware -- Very large scale integration design</topic><topic>Linear approximation</topic><topic>Linear programming</topic><topic>Mathematics of computing -- Mathematical analysis -- Functional analysis -- Approximation</topic><topic>Mathematics of computing -- Mathematical analysis -- Mathematical optimization -- Continuous optimization -- Linear programming</topic><topic>Permission</topic><topic>Theory of computation -- Design and analysis of algorithms -- Approximation algorithms analysis</topic><topic>Theory of computation -- Design and analysis of algorithms -- Mathematical optimization -- Continuous optimization -- Linear programming</topic><topic>Timing</topic><topic>Topology</topic><toplevel>online_resources</toplevel><creatorcontrib>Chen, Pinhong</creatorcontrib><creatorcontrib>Kuh, Ernest S.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan (POP) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE/IET Electronic Library</collection><collection>IEEE Proceedings Order Plans (POP) 1998-present</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Chen, Pinhong</au><au>Kuh, Ernest S.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Floorplan sizing by linear programming approximation</atitle><btitle>37th Design Automation Conference, 2000</btitle><stitle>DAC</stitle><date>2000-01-01</date><risdate>2000</risdate><spage>468</spage><epage>471</epage><pages>468-471</pages><issn>0738-100X</issn><isbn>9781581131871</isbn><isbn>1581131879</isbn><abstract>In this paper, we present an approximation algorithm by linear programming (LP) for floorplan sizing problem. Given any topological constraints between blocks, we can formulate it as an LP problem with a cost function for the minimum bounding box area. Unlike slicing structures, this approach can handle any topological constraints as well as soft/hard/preplaced blocks, and timing constraints. Empirically, our method needs few iterations to find the optimum solution and shows one order of improvement over previous methods both in run time and capability to handle a larger problem size even on a very limited computing resource PC.</abstract><cop>New York, NY, USA</cop><pub>ACM</pub><doi>10.1145/337292.337547</doi><tpages>4</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0738-100X
ispartof 37th Design Automation Conference, 2000, 2000, p.468-471
issn 0738-100X
language eng
recordid cdi_proquest_miscellaneous_27520187
source IEEE Xplore All Conference Series
subjects Applied computing -- Physical sciences and engineering -- Engineering
Approximation algorithms
Constraint optimization
Cost function
Functional programming
Hardware -- Electronic design automation -- Physical design (EDA)
Hardware -- Emerging technologies
Hardware -- Robustness
Hardware -- Very large scale integration design
Linear approximation
Linear programming
Mathematics of computing -- Mathematical analysis -- Functional analysis -- Approximation
Mathematics of computing -- Mathematical analysis -- Mathematical optimization -- Continuous optimization -- Linear programming
Permission
Theory of computation -- Design and analysis of algorithms -- Approximation algorithms analysis
Theory of computation -- Design and analysis of algorithms -- Mathematical optimization -- Continuous optimization -- Linear programming
Timing
Topology
title Floorplan sizing by linear programming approximation
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-26T04%3A07%3A14IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_ieee_&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Floorplan%20sizing%20by%20linear%20programming%20approximation&rft.btitle=37th%20Design%20Automation%20Conference,%202000&rft.au=Chen,%20Pinhong&rft.date=2000-01-01&rft.spage=468&rft.epage=471&rft.pages=468-471&rft.issn=0738-100X&rft.isbn=9781581131871&rft.isbn_list=1581131879&rft_id=info:doi/10.1145/337292.337547&rft_dat=%3Cproquest_ieee_%3E27520187%3C/proquest_ieee_%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-a302t-a956fab7784d2dac1db4c4eaca5f3ac088ec9d10dd8ba59562fac94398e909a13%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=27520187&rft_id=info:pmid/&rft_ieee_id=855356&rfr_iscdi=true