Short path search using tiles and piecewise linear cost propagation

Number of patents in Portfolio can not be more than 2000

United States of America Patent

PATENT NO 7139992
APP PUB NO 20020107711A1
SERIAL NO

09998559

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
ORACLE AMERICA, INC.SANTA CLARA, CA8427

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

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

Cited Art Landscape

Patent Info (Count) # Cites Year
 
MITSUBISHI ELECTRIC INFORMATION TECHNOLOGY CENTER AMERICA, INC. (1)
5748844 Graph partitioning system 30 1994
 
APPLE INC. (1)
6477692 Method and apparatus for channel-routing of an electronic device 4 1999
 
Cadence Design Systems, Inc. (1)
* 5838583 Optimized placement and routing of datapaths 223 1996
 
THE ARIZONA BOARD OF REGENTS ON BEHALF OF THE UNIVERSITY OF ARIZONA (1)
6353918 Interconnection routing system 29 1999
 
FUJITSU LIMITED (1)
6415427 Method and apparatus for global routing, and storage medium having global routing program stored therein 59 2001
 
SYNOPSYS, INC. (2)
5841664 Method for optimizing track assignment in a grid-based channel router 31 1996
6324675 Efficient iterative, gridless, cost-based fine router for computer controlled integrated circuit design 165 1998
 
LOCKHEED MARTIN CORPORATION (1)
5511015 Double-accumulator implementation of the convolution function 22 1993
 
SUN MICROSYSTEMS, INC. (1)
* 2002/0104,061 Systems and methods for linear minimal convolution 50 2001
 
MATSUSHITA ELECTRIC INDUSTRIAL CO., LTD. (1)
6292928 Line path determining method and delay estimating method 9 1999
 
AVAGO TECHNOLOGIES GENERAL IP (SINGAPORE) PTE. LTD. (4)
6175950 Method and apparatus for hierarchical global routing descend 117 1998
6230306 Method and apparatus for minimization of process defects while routing 111 1998
6324674 Method and apparatus for parallel simultaneous global and detail routing 152 1998
6182272 Metal layer assignment 195 1998
 
ORACLE AMERICA, INC. (3)
* 6665852 Piecewise linear cost propagation for path searching 46 2001
6792587 2.5-D graph for multi-layer routing 15 2002
6763512 Detailed method for routing connections using tile expansion techniques and associated methods for designing and manufacturing VLSI circuits 15 2002
* Cited By Examiner

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (1)
* 7685553 System and method for global circuit routing incorporating estimation of critical area estimate metrics 1 2007
 
APPLE INC. (2)
8861506 Shortest path determination for large graphs 1 2012
9500487 Shortest path determination for large graphs 0 2014
 
GLOBALFOUNDRIES INC. (4)
* 7823108 Chip having timing analysis of paths performed within the chip during the design process 1 2007
* 2008/0066,036 Chip Having Timing Analysis of Paths Performed Within the Chip During the Design Process 4 2007
* 8365120 Resolving global coupling timing and slew violations for buffer-dominated designs 3 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)
* 7325216 Method and computer program for spreading trace segments in an integrated circuit package design 0 2005
* 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