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

Family

Loading Family data... loading....

Patent Owner(s)

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

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Kao, Russell Portola Valley, CA 9 268
Xing, Zhaoyun San Jose, CA 11 197

Cited Art Landscape

Patent Info (Count) # Cites Year
 
APPLE INC. (1)
6,477,692 Method and apparatus for channel-routing of an electronic device 4 1999
 
AVAGO TECHNOLOGIES GENERAL IP (SINGAPORE) PTE. LTD. (4)
6,175,950 Method and apparatus for hierarchical global routing descend 116 1998
6,230,306 Method and apparatus for minimization of process defects while routing 109 1998
6,324,674 Method and apparatus for parallel simultaneous global and detail routing 149 1998
6,182,272 Metal layer assignment 166 1998
 
CADENCE DESIGN SYSTEMS, INC. (1)
* 5,838,583 Optimized placement and routing of datapaths 215 1996
 
THE ARIZONA BOARD OF REGENTS ON BEHALF OF THE UNIVERSITY OF ARIZONA (1)
6,353,918 Interconnection routing system 28 1999
 
FUJITSU LIMITED (1)
6,415,427 Method and apparatus for global routing, and storage medium having global routing program stored therein 57 2001
 
SYNOPSYS, INC. (2)
5,841,664 Method for optimizing track assignment in a grid-based channel router 31 1996
6,324,675 Efficient iterative, gridless, cost-based fine router for computer controlled integrated circuit design 159 1998
 
LOCKHEED MARTIN CORPORATION (1)
5,511,015 Double-accumulator implementation of the convolution function 22 1993
 
SUN MICROSYSTEMS, INC. (4)
* 6,665,852 Piecewise linear cost propagation for path searching 45 2001
* 2002/0104,061 Systems and methods for linear minimal convolution 49 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 11 2002
 
BINARY SERVICES LIMITED LIABILITY COMPANY (1)
5,748,844 Graph partitioning system 28 1994
 
MATSUSHITA ELECTRIC INDUSTRIAL CO., LTD. (1)
6,292,928 Line path determining method and delay estimating method 9 1999
* Cited By Examiner

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (4)
* 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
* 2012/0144,358 Resolving Global Coupling Timing and Slew Violations for Buffer-Dominated Designs 0 2010
 
AVAGO TECHNOLOGIES GENERAL IP (SINGAPORE) PTE. LTD. (1)
* 7,325,216 Method and computer program for spreading trace segments in an integrated circuit package design 0 2005
 
APPLE INC. (1)
8,861,506 Shortest path determination for large graphs 0 2012
* Cited By Examiner

Maintenance Fees

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