Title:
A SENSITIVITY BASED PATTERN SEARCH ALGORITHM FOR COMPONENT LAYOUT
Document Type and Number:
WIPO Patent Application WO2004029841
Kind Code:
A3
Abstract:
A solution to determining the move set ordering in pattern searching is disclosed that involves driving a pattern search algorithm by a metric other than the step size of the patterns. An instance of this metric is the amount of change in an objective function. Preprocessing algorithms are disclosed which quantify the effect each move has on the objective function. Those moves having a greater effect on the objective function are applied before moves having a lesser effect. We call this effect on the object function the sensitivity of the object function to a particular move and present several methods to quantify it. The sensitivity may be expressed as a function or the moves can be ranked and clustered with the pattern search being driven by the ranked moves or the function.
Inventors:
ALADAHALLI CHANDANKUMAR
CAGAN JONATHAN
SHIMADA KENJI
CAGAN JONATHAN
SHIMADA KENJI
Application Number:
PCT/US2003/030523
Publication Date:
June 24, 2004
Filing Date:
September 26, 2003
Export Citation:
Assignee:
UNIV CARNEGIE MELLON (US)
International Classes:
G06F17/00; G06F17/50; G06N5/02; (IPC1-7): G06F17/50
Foreign References:
| US6185724B1 | 2001-02-06 |
Other References:
"2001 GRADUATE STUDENT TECHNICAL CONFERENCE MASTERS PRESENTATIONS", CARNEGIE MELLON UNIVERSITY MECHANICAL ENGINEERING WEB SITE, 21 August 2002 (2002-08-21), XP002278320, Retrieved from the Internet [retrieved on 20040526]
CAGAN J ET AL: "A survey of computational approaches to three-dimensional layout problems", COMPUTER AIDED DESIGN, ELSEVIER PUBLISHERS BV., BARKING, GB, vol. 34, no. 8, July 2002 (2002-07-01), pages 597 - 611, XP004344145, ISSN: 0010-4485
UPTON M ET AL: "Integrated placement for mixed macro cell and standard cell designs", PROCEEDINGS OF THE ACM / IEEE DESIGN AUTOMATION CONFERENCE. ORLANDO, JUNE 24 - 28, 1990, PROCEEDINGS OF THE ACM/IEEE DESIGN AUTOMATION CONFERENCE (DAC), NEW YORK, IEEE, US, vol. CONF. 27, 24 June 1990 (1990-06-24), pages 32 - 35, XP010079379, ISBN: 0-89791-363-9
CAGAN J ET AL: "A simulated annealing-based algorithm using hierarchical models for general three-dimensional component layout", COMPUTER AIDED DESIGN, ELSEVIER PUBLISHERS BV., BARKING, GB, vol. 30, no. 10, September 1998 (1998-09-01), pages 781 - 790, XP004183745, ISSN: 0010-4485
ALADAHALLI CHANDANKUMAR ET AL: "A sensitivity-based pattern search algorithm for 3D component layout", PROC. ASME DES. ENG. TECH. CONF.; PROCEEDINGS OF THE ASME DESIGN ENGINEERING TECHNICAL CONFERENCE 2002, vol. 2, 2002, pages 839 - 848, XP009029827
KATKOORI S ET AL: "RT-level interconnect optimization in DSM regime", PROCEEDINGS IEEE COMPUTER SOCIETY WORKSHOP ON VLSI 2000, 27 April 2000 (2000-04-27), ORLANDO, FL, pages 143 - 148, XP010379680
TORCZON V, TROSSET M W: "From Evolutionary Operation to Parallel Direct Search: Pattern Search Algorithms for Numerical Optimization", PROCEEDINGS OF THE 29TH SYMPOSIUM ON THE INTERFACE, COMPUTING SCIENCE AND STATISTICS, vol. 29, no. 1, 14 May 1997 (1997-05-14), HOUSTON, TX, pages 396 - 401, XP002278321
CAGAN J ET AL: "A survey of computational approaches to three-dimensional layout problems", COMPUTER AIDED DESIGN, ELSEVIER PUBLISHERS BV., BARKING, GB, vol. 34, no. 8, July 2002 (2002-07-01), pages 597 - 611, XP004344145, ISSN: 0010-4485
UPTON M ET AL: "Integrated placement for mixed macro cell and standard cell designs", PROCEEDINGS OF THE ACM / IEEE DESIGN AUTOMATION CONFERENCE. ORLANDO, JUNE 24 - 28, 1990, PROCEEDINGS OF THE ACM/IEEE DESIGN AUTOMATION CONFERENCE (DAC), NEW YORK, IEEE, US, vol. CONF. 27, 24 June 1990 (1990-06-24), pages 32 - 35, XP010079379, ISBN: 0-89791-363-9
CAGAN J ET AL: "A simulated annealing-based algorithm using hierarchical models for general three-dimensional component layout", COMPUTER AIDED DESIGN, ELSEVIER PUBLISHERS BV., BARKING, GB, vol. 30, no. 10, September 1998 (1998-09-01), pages 781 - 790, XP004183745, ISSN: 0010-4485
ALADAHALLI CHANDANKUMAR ET AL: "A sensitivity-based pattern search algorithm for 3D component layout", PROC. ASME DES. ENG. TECH. CONF.; PROCEEDINGS OF THE ASME DESIGN ENGINEERING TECHNICAL CONFERENCE 2002, vol. 2, 2002, pages 839 - 848, XP009029827
KATKOORI S ET AL: "RT-level interconnect optimization in DSM regime", PROCEEDINGS IEEE COMPUTER SOCIETY WORKSHOP ON VLSI 2000, 27 April 2000 (2000-04-27), ORLANDO, FL, pages 143 - 148, XP010379680
TORCZON V, TROSSET M W: "From Evolutionary Operation to Parallel Direct Search: Pattern Search Algorithms for Numerical Optimization", PROCEEDINGS OF THE 29TH SYMPOSIUM ON THE INTERFACE, COMPUTING SCIENCE AND STATISTICS, vol. 29, no. 1, 14 May 1997 (1997-05-14), HOUSTON, TX, pages 396 - 401, XP002278321
Download PDF:
Previous Patent: A METHOD FOR MODULARIZATION OF SHIP HULL
Next Patent: VIRTUAL CARD SERVICE SYSTEM AND METHOD
Next Patent: VIRTUAL CARD SERVICE SYSTEM AND METHOD