Cited By
View all- Kuh EOhtsuki T(1990)Recent advances in VLSI layoutProceedings of the IEEE10.1109/5.5221278:2(237-263)Online publication date: Jan-1990
An investigation into statistical properties of partitioning and floorplanning problems
Authors: 
S. Sastry, J.-I. PiAuthors Info & Claims
Pages 382 - 387
Abstract
In this paper we examine some statistical properties exhibited by combinatorial optimization problems. Although the paper focuses on two particular problems that arise in chip design, namely circuit partitioning and floorplanning, the results seem valid for a much larger set of such problems. For the partitioning problem, we examine the solutions generated by the well known Kernighan-Lin procedure [5,10] and solutions generated by random search. We find that in both cases, the Type 3 (Weibull) extreme-value distribution provides an excellent model for the distribution of local minima generated. The location parameter of the Weibull provides an estimate of the minimum cost. For the floorplanning problem, we construct a number of test problems, whose optimal value is known. As with the partitioning problem, we find that the Weibull distribution provides an excellent model for estimating the minimum cost.
References
[1]
A. D. Bethke. Genetic Algorithm8 as Function Optim/zers. PhD thesis, University of Michigan, 1980.
[2]
S. H. Brooks. Discussion of Methods for Lock, ring Surface Maxima. Operations Research, 6:244-251, 1958.
[3]
L. P. Devroye. On the Gonvergence of Statistical Search. IEEE Transactions on Systems, Man and Cybernetics, SMC-6(1):46-56, 1976.
[4]
S. D. Dubey. Some Percentile Estimators for WeibullParameters. Technometrics, 9(1):119-129, February 1967.
[5]
C. M. Fiduccia and R. M. Mattheyses. A Linear Time Heuristic for improving Network Partitions. In Proceedings of 19~h Design Au~or,~a~ion Conference, pages 175-181. IEEE, June 1982.
[6]
J. Galambos. The Asymptotic Theory o/ Extreme Order S~atistics. Wiley series in probability and mathematical statistics. John Wiley and Sons, 1978.
[7]
B. V. Gnedenko. Sur la distribution limite du terme maximum d'une serie aleatoire. Annals of Mathematics, 44:423-453, 1943.
[8]
B. L. Golden. A Statistical Approach to the TSP. Networks, 7:209-225, 1977.
[9]
H. L. Haxter and A. H. Moore. Maximum Likelihood Estimation of the Parameters of Gamma and Weibull Populations from Complete and Censored Samples. Technometrics, 7(4):639-643, November 1965.
[10]
B. W. Kernighan and S. Lin. An Efficient Heuristic Procedure for Partitioning Graphs. Bell Systems Technical Journal, 49(2):291-307, February 1970.
[11]
S. Kirkpatrick, D. Oela~t, C, and M. P. Vecchi. Optimization by Simulated Annealing. Science, 220(4598):671-680, May 1983.
[12]
B. Krishnamurthy. An improved Min-Gut Algorithm for Partitioning VLSI Networks. IEEE Transactions on Computers, C-33(5}:438-446, 1984.
[13]
K. McRoberts. A Search Model for Evaluating Combinatorial Explosive Problems. Operations Research, 19:1331, 1971.
[14]
R. H. J. M. Otten. Efficient Floorplan Optimization. In Proceedings of In~l. Conf. on Computers and Design, pages 499-501. IEEE, October 1983.
[15]
N. R. Patel and R. L. Smith. The Asymptotic Extreme Value Distribution of the Sample Minimum of a Concave Function under Linear Constraints. Operations Research, 31(4):789--79.t, August 1983.
[16]
S. Sastry and A. G. Parker. On the Relation between Wire Length Distributions and Placement of Logic on Master Slice ICs. In Proceedings of ~he $ist Design Automation Conference, Albuquerque, NM., June 1984. IEEE, ACM.
[17]
S. Sastry and A. C. Parker. Stochastic Models for Wirability Analysis of Gate Arrays. IEEE Transactions on CAD, GAD-5(1):52-65:, 3anuaxy 1985.
[18]
D. F. Wong and (3. L. L~u. A New Algorithm for Floorplan Design. in Proeeedir~gs of P, Srd Desigal Automation Conference, pages 101-107, 1986.
[19]
S. H. Zanakis. Computational Experience with some Non-Linear Optimization Algorithms in deriving Maximum-Likelihood Estimates for the Three-Parameter Weibull Distribution. TIMS Studies in Management Sciences, 7:63-77, 1977.
Index Terms
- An investigation into statistical properties of partitioning and floorplanning problems
Recommendations
How does partitioning matter for 3D floorplanning?
GLSVLSI '06: Proceedings of the 16th ACM Great Lakes symposium on VLSIThe recent hierarchical design framework[8] for 3D floorplan-ning suggests a better performance than previous flat design framework. Under this framework, the layer assignment of the blocks is accomplished by some partitioning algorithms which are ...
On partitioning vs. placement rent properties
SLIP '01: Proceedings of the 2001 international workshop on System-level interconnect predictionRent's rule can be derived by direct partitioning of the circuit netlist, by indirect partitioning of the placed layout, or by averaging the number of terminals for various equally large regions of the placed circuit. It is shown that all three methods ...
Unification of partitioning, placement and floorplanning
ICCAD '04: Proceedings of the 2004 IEEE/ACM International conference on Computer-aided designLarge macro blocks, pre-designed datapaths, embedded memories and analog blocks are increasingly used in ASIC designs. However, robust algorithms for large-scale placement of such designs have only recently been considered in the literature, and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 1989 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
- IEEE-CS\TCDA: TC Design Automation
- SIGDA: ACM Special Interest Group on Design Automation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 June 1989
Check for updates
Qualifiers
- Article
Conference
DAC89
Sponsor:
- IEEE-CS\TCDA
- SIGDA
Acceptance Rates
DAC '89 Paper Acceptance Rate 156 of 465 submissions, 34%;
Overall Acceptance Rate 1,770 of 5,499 submissions, 32%
Upcoming Conference
DAC '25
- Sponsor:
- sigda
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 240Total Downloads
- Downloads (Last 12 months)30
- Downloads (Last 6 weeks)6
Reflects downloads up to 16 Feb 2025
Other Metrics
Citations
Cited By
View all- Kuh EOhtsuki T(1990)Recent advances in VLSI layoutProceedings of the IEEE10.1109/5.5221278:2(237-263)Online publication date: Jan-1990
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in