US Patent No: 7,139,992

Number of patents in Portfolio can not be more than 2000

Short path search using tiles and piecewise linear cost propagation

ALSO PUBLISHED AS: 20020107711

Stats

ATTORNEY / AGENT: (SPONSORED)

Importance

Loading Importance Indicators... loading....

Abstract

See full text

A method for finding shortest paths is disclosed which uses a piecewise linear cost model to guide the search of through a compact tile graph and to ensure that a shortest path may always be found in a computationally effective manner. Cost function propagation from tile segment to tile segment is used to search for a target location from a source location through a region, and the shortest path is found through tracing backwards using the cost functions calculated during the searching. Linear minimal convolution is used to facilitate the cost function propagation.

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

First Claim

See full text

all claims..

Related Publications

Loading Related Publications... loading....

Patent Owner(s)

Patent OwnerAddressTotal Patents
SUN MICROSYSTEMS, INC.SANTA CLARA, CA9305

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Kao, Russell Portola Valley, CA 12 267
Xing, Zhaoyun San Jose, CA 19 274

Cited Art Landscape

Patent Info (Count) # Cites Year
 
LSI LOGIC CORPORATION (4)
6,175,950 Method and apparatus for hierarchical global routing descend 112 1998
6,230,306 Method and apparatus for minimization of process defects while routing 108 1998
6,324,674 Method and apparatus for parallel simultaneous global and detail routing 147 1998
6,182,272 Metal layer assignment 149 1998
 
SUN MICROSYSTEMS, INC. (4)
2002/0104,061 Systems and methods for linear minimal convolution 49 2001
6,665,852 Piecewise linear cost propagation for path searching 45 2001
6,792,587 2.5-D graph for multi-layer routing 14 2002
6,763,512 Detailed method for routing connections using tile expansion techniques and associated methods for designing and manufacturing VLSI circuits 3 2002
 
SYNOPSYS, INC. (2)
5,841,664 Method for optimizing track assignment in a grid-based channel router 24 1996
6,324,675 Efficient iterative, gridless, cost-based fine router for computer controlled integrated circuit design 152 1998
 
BINARY SERVICES LIMITED LIABILITY COMPANY (1)
5,748,844 Graph partitioning system 24 1994
 
CADENCE DESIGN SYSTEMS, INC. (1)
5,838,583 Optimized placement and routing of datapaths 211 1996
 
FREESCALE SEMICONDUCTOR, INC. (1)
6,477,692 Method and apparatus for channel-routing of an electronic device 4 1999
 
FUJITSU LIMITED (1)
6,415,427 Method and apparatus for global routing, and storage medium having global routing program stored therein 57 2001
 
LOCKHEED MARTIN CORPORATION (1)
5,511,015 Double-accumulator implementation of the convolution function 22 1993
 
MATSUSHITA ELECTRIC INDUSTRIAL CO., LTD. (1)
6,292,928 Line path determining method and delay estimating method 9 1999
 
UNIVERSITY OF ARIZONA (1)
6,353,918 Interconnection routing system 28 1999

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (3)
7,685,553 System and method for global circuit routing incorporating estimation of critical area estimate metrics 0 2007
7,823,108 Chip having timing analysis of paths performed within the chip during the design process 0 2007
8,365,120 Resolving global coupling timing and slew violations for buffer-dominated designs 0 2010
 
LSI LOGIC CORPORATION (1)
7,325,216 Method and computer program for spreading trace segments in an integrated circuit package design 0 2005

Maintenance Fees

Fee Large entity fee small entity fee micro entity fee due date
7.5 Year Payment $3600.00 $1800.00 $900.00 May 21, 2014
11.5 Year Payment $7400.00 $3700.00 $1850.00 May 21, 2018
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