US Patent No: 7,024,650

Number of patents in Portfolio can not be more than 2000

Method and apparatus for considering diagonal wiring in placement

Stats

ALSO PUBLISHED AS: 20020133798
ATTORNEY / AGENT: (SPONSORED)
 

Importance

Loading Importance Indicators... loading....

Abstract

The invention is directed towards method and apparatus that consider diagonal wiring in placement. Some embodiments of the invention are placers that use diagonal lines in calculating the costs of potential placement configurations. For instance, some embodiments estimate the wirelength cost of a placement configuration by (1) identifying, for each net in a net list, a bounding box that encloses all the circuit elements of the net, (2) computing an attribute of each bounding box by using a line that can be completely or partially diagonal, and (3) computing the wirelength cost estimate based on the computed attributes. To estimate the wirelength cost of different placement configurations, other embodiments construct connection graphs that model the net interconnect topologies. These connection graphs can have edges that are completely or partially diagonal. Other embodiments use diagonal lines to measure congestion costs of potential placement configurations. For instance, some placers use diagonal lines as cut lines that divide the IC layout into regions. These placers then generate congestion-cost estimates by measuring the number of nets cut by the diagonal cut lines.

Loading the Abstract Image... loading....

First Claim

Related Publications

Loading Related Publications... loading....

Patent Owner(s)

Patent OwnerAddressTotal Patents
CADENCE DESIGN SYSTEMS, INC.SAN JOSE, CA1294

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Ganley, Joseph L Vienna, VA 23 281
Teig, Steven Menlo Park, CA 355 3401

Cited Art

Patent Info (Count) # Cites Year
 
LSI LOGIC CORPORATION (37)
5,566,078 Integrated circuit cell placement using optimization-driven clustering 69 1993
5,914,887 Congestion based cost factor computing apparatus for integrated circuit physical design automation system 114 1994
6,155,725 Cell placement representation and transposition for integrated circuit physical design automation system 114 1994
5,587,923 Method for estimating routability and congestion in a cell placement for integrated circuit chip 93 1994
5,578,840 Microelectronic integrated circuit structure and method using three directional interconnect routing based on hexagonal geometry 136 1994
5,532,934 Floorplanning technique using multi-partitioning based on a partition cost factor for non-square shaped partitions 95 1995
5,742,086 Hexagonal DRAM array 98 1995
5,777,360 Hexagonal field programmable gate array architecture 238 1995
5,811,863 Transistors having dynamically adjustable characteristics 133 1995
5,822,214 CAD for hexagonal architecture 194 1995
5,973,376 Architecture having diamond shaped or parallelogram shaped cells 113 1995
6,407,434 Hexagonal architecture 123 1995
5,699,265 Physical design automation system and process for designing integrated circuit chips using multiway partitioning with constraints 43 1995
5,637,920 High contact density ball grid array package for flip-chips 246 1995
5,636,125 Computer implemented method for producing optimized cell placement for integrated circiut chip 141 1995
5,650,653 Microelectronic integrated circuit including triangular CMOS "nand" gate device 117 1995
6,038,385 Physical design automation system and process for designing integrated circuit chip using "chessboard" and "jiggle" optimization 19 1996
6,085,032 Advanced modular cell placement system with sinusoidal optimization 28 1996
6,216,252 Method and system for creating, validating, and scaling structural description of electronic device 180 1996
5,980,093 Integrated circuit layout routing using multiprocessing 156 1996
5,784,289 Method for estimating routability and congestion in a cell placement fo integrated circuit chip 99 1996
5,898,597 Integrated circuit floor plan optimization system 100 1997
6,058,254 Method and apparatus for vertical congestion removal 85 1997
6,068,662 Method and apparatus for congestion removal 91 1997
6,070,108 Method and apparatus for congestion driven placement 49 1997
6,123,736 Method and apparatus for horizontal congestion removal 86 1997
6,134,702 Physical design automation system and process for designing integrated circuit chips using multiway partitioning with constraints 61 1997
6,154,874 Memory-saving method and apparatus for partitioning high fanout nets 60 1998
6,175,950 Method and apparatus for hierarchical global routing descend 108 1998
6,230,306 Method and apparatus for minimization of process defects while routing 106 1998
6,247,167 Method and apparatus for parallel Steiner tree routing 99 1998
6,253,363 Net routing using basis element decomposition 107 1998
6,289,495 Method and apparatus for local optimization of the global routing 114 1998
6,324,674 Method and apparatus for parallel simultaneous global and detail routing 139 1998
6,088,519 Method and system for improving a placement of cells using energetic placement with alternating contraction and expansion operations 72 1998
6,412,102 Wire routing optimization 102 1998
6,473,891 Wire routing to control skew 79 2000
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (7)
4,593,363 Simultaneous placement and wiring for VLSI chips 152 1983
4,615,011 Iterative method for establishing connections and resulting product 225 1983
6,295,634 Wiring design apparatus, wiring determination apparatus and methods thereof 95 1999
6,415,422 Method and system for performing capacitance estimations on an integrated circuit design routed by a global routing tool 51 1999
6,401,234 Method and system for re-routing interconnects within an integrated circuit design having blockages and bays 88 1999
6,490,713 Method and apparatus for automatically generating multi-terminal nets, and program storage medium storing program for executing automatic multi-terminal net generation method 102 2001
6,480,991 Timing-driven global placement based on geometry-aware timing budgets 91 2001
 
CADENCE DESIGN SYSTEMS, INC. (6)
5,663,891 Optimization of multiple performance criteria of integrated circuits by expanding a constraint graph with subgraphs derived from multiple PWL convex cost functions 104 1996
5,838,583 Optimized placement and routing of datapaths 195 1996
6,543,043 Inter-region constraint-based router for use in electronic design automation 102 2000
6,651,233 Method and apparatus for measuring congestion in a partitioned region 30 2000
6,516,455 Partitioning placement method using diagonal cutlines 84 2001
2002/0166,105 "LP method and apparatus for identifying routes" 43 2002
 
KABUSHIKI KAISHA TOSHIBA (6)
5,224,057 Arrangement method for logic cells in semiconductor IC device 172 1992
5,634,093 Method and CAD system for designing wiring patterns using predetermined rules 92 1995
5,633,479 Multilayer wiring structure for attaining high-speed signal propagation 115 1995
6,262,487 Semiconductor integrated circuit device, semiconductor integrated circuit wiring method, and cell arranging method 241 1999
6,546,540 Method of automatic layout design for LSI, mask set and semiconductor integrated circuit manufactured by automatic layout design method, and recording medium storing automatic layout design program 104 2000
6,436,804 Semiconductor integrated circuit device, semiconductor integrated circuit wiring method, and cell arranging method 106 2001
 
SYNOPSYS, INC. (6)
5,798,936 Congestion-driven placement method and computer-implemented integrated-circuit design tool 89 1996
6,442,743 Placement method for integrated circuit design using topo-clustering 69 1998
6,324,675 Efficient iterative, gridless, cost-based fine router for computer controlled integrated circuit design 143 1998
6,349,403 Interative, gridless, cost-based layer assignment coarse router for computer controlled IC design 116 1998
6,557,145 Method for design optimization using logical and physical information 143 2001
6,567,967 Method for designing large standard-cell base integrated circuits 102 2001
 
FUJITSU LIMITED (3)
5,889,677 Circuit designing apparatus of an interactive type 130 1995
6,327,694 Cell placement apparatus and method, and computer readable record medium having cell placement program recorded thereon 94 1998
6,240,541 Interactive circuit designing apparatus which displays a result of component placement and wire routing from a layout design unit 59 1999
 
INTEL CORPORATION (3)
6,366,279 Triangle mesh compression 21 1998
6,442,745 Method and apparatus for layout-constrained global routing 67 1999
6,519,751 Method and apparatus for accurate crosspoint allocation in VLSI area routing 76 2000
 
FREESCALE SEMICONDUCTOR, INC. (2)
6,505,331 Method for routing of nets in an electronic device 58 1996
6,209,123 Methods of placing transistors in a circuit layout and semiconductor device with automatically placed transistors 293 1996
 
MENTOR GRAPHICS CORPORATION (2)
5,757,656 Method for routing breakouts 117 1995
6,327,693 Interconnect delay driven placement and routing of an integrated circuit design 104 1999
 
MITSUBISHI DENKI KABUSHIKI KAISHA (2)
5,859,449 Semiconductor integrated circuit 78 1997
6,463,575 Cell-layout method in integrated circuit devices 75 2000
 
NEC CORPORATION (2)
4,855,929 Routing method for use in wiring design 108 1987
5,757,089 Method of automatic wiring 110 1995
 
NEC TOPPAN CIRCLE SOLUTIONS, INC. (2)
6,035,108 Figure layout compaction method and compaction device 96 1997
6,301,686 Graphic layout compaction system capable of compacting a layout at once 132 1999
 
NEC TOPPAN CIRCUIT SOLUTIONS, INC. (2)
6,385,758 System and method for compacting a graphic layout 120 1999
6,412,097 COMPACTING METHOD OF CIRCUIT LAYOUT BY MOVING COMPONENTS USING MARGINS AND BUNDLE WIDTHS IN COMPLIANCE WITH THE DESIGN RULE, A DEVICE USING THE METHOD AND A COMPUTER PRODUCT ENABLING PROCESSOR TO PERFORM THE METHOD 114 2000
 
ACTEL CORPORATION (1)
5,640,327 Apparatus and method for partitioning resources for interconnections 107 1996
 
AT&T IPM CORP. (1)
5,519,836 Method of on-line permanent virtual circuit routing 48 1994
 
AVAGO TECHNOLOGIES GENERAL IP PTE. LTD. (1)
6,405,358 Method for estimating and displaying wiring congestion 88 1999
 
BSC ACQUISTION, INC. (1)
6,260,179 Cell arrangement evaluating method, storage medium storing cell arrangement evaluating program, cell arranging apparatus and method, and storage medium storing cell arranging program 152 1998
 
CASCADE DESIGN AUTOMATION CORPORATION (1)
5,097,422 Method and apparatus for designing integrated circuits 170 1989
 
FUJITSU VLSI LIMITED (1)
5,618,744 Manufacturing method and apparatus of a semiconductor integrated circuit device 104 1993
 
MATSUSHITA ELECTRIC INDUSTRIAL CO., LTD. (1)
6,330,707 Automatic routing method 109 1998
 
MICRON TECHNOLOGY, INC. (1)
6,448,591 Metallization line layout 90 1999
 
NEC ELECTRONICS CORPORATION (1)
6,378,121 Automatic global routing device for efficiently determining optimum wiring route on integrated circuit and global routing method therefor 81 1998
 
NORTEL NETWORKS LIMITED (1)
4,777,606 Method for deriving an interconnection route between elements in an interconnection medium 141 1986
 
RELAY DESIGN AUTOMATION INCORPORATED (1)
6,249,902 Design hierarchy-based placement 157 1998
 
RENESAS ELECTRONICS CORPORATION (1)
5,375,069 Wiring routes in a plurality of wiring layers 133 1994
 
SIEMENS AKTIENGESELLSCHAFT (1)
5,267,176 Method for placing modules on a carrier 92 1991
 
SIMPLEX SOLUTIONS, INC. (1)
6,618,849 Method and apparatus for identifying routes for nets 24 2002
 
SUN MICROSYSTEMS, INC. (1)
2004/0044,979 Constraint-based global router for routing high performance designs 83 2002
 
XILINX, INC. (1)
6,601,227 Method for making large-scale ASIC using pre-engineered long distance routing structure 240 2001
 
OTHER [CHECK PATENT PROFILE FOR ASSIGNMENT INFORMATION] (2)
6,128,767 Polygon representation in an integrated circuit layout 109 1997
2009/0132,648 CONTENT DELIVERY AND GLOBAL TRAFFIC MANAGEMENT NETWORK SYSTEM 2009

Patent Citation Ranking

Forward Cites

Patent Info (Count) # Cites Year
 
CADENCE DESIGN SYSTEMS, INC. (9)
7,506,295 Non manhattan floor plan architecture for integrated circuits 1 2002
7,707,537 Method and apparatus for generating layout regions with local preferred directions 2 2004
7,441,220 Local preferred direction architecture, tools, and apparatus 6 2004
7,493,581 Analytical placement method and apparatus 3 2006
8,201,128 Method and apparatus for approximating diagonal lines in placement 0 2006
7,594,196 Block interstitching using local preferred direction architectures, tools, and apparatus 0 2006
8,250,514 Localized routing direction 0 2006
8,166,442 Local preferred direction architecture 0 2008
8,010,929 Method and apparatus for generating layout regions with local preferred directions 0 2010

Maintenance Fees

Fee Large entity fee small entity fee micro entity fee due date
7.5 Year Payment $3600.00 $1800.00 $900.00 Oct 4, 2013
11.5 Year Payment $7400.00 $3700.00 $1850.00 Oct 4, 2017
Fee Large entity fee small entity fee micro entity fee
Surcharge - 7.5 year - Late payment within 6 months $160.00 $80.00 $40.00
Surcharge - 11.5 year - Late payment within 6 months $160.00 $80.00 $40.00
Surcharge after expiration - Late payment is unavoidable $700.00 $350.00 $175.00
Surcharge after expiration - Late payment is unintentional $1,640.00 $820.00 $410.00