Russell Allen Kao

6446245, Sep 3, 2002

Jan 5, 2000

09/477652

Zhaoyun Xing - San Jose CA
Russell Kao - Portola Valley CA

Sun Microsystems, Inc. - Santa Clara CA

G06F 1750

716 10, 716 12, 716 8, 716 9, 716 11, 716 13, 716 14

A method and apparatus for performing power routing in ASIC design. Power routing is performed after cell placement, allowing more knowledgeable placement of power structures in the physical layout. By performing cell placement prior to power routing, standard cells are allowed to be placed in more optimal configurations. In one embodiment, power rings and power straps are placed over the top of the standard cells based on power analysis of the standard cell layout. Those regions of the layout where design violations are triggered are corrected by an incremental placement correction of affected cells. In another embodiment, cells are placed in the physical layout in a bottom-up hierarchical manner. When a given cell becomes large enough to require power routing, a power feed cell of sufficient dimension to support the necessary power strap is inserted into the layout during the placement process. In the subsequent power routing phase, power straps are placed over the power feed cells.

6519756, Feb 11, 2003

Oct 5, 1999

09/412285

Russell Kao - Portola Valley CA
Zhaoyun Xing - San Jose CA

Sun Microsystems, Inc. - Santa Clara CA

G06F 1750

716 18, 716 4, 365 51

A method and apparatus for building an integrated circuit. A description of the logical operation of a module in a hardware description language is provided, which includes annotations in the form of design directives. An interpreting process is configured to read the annotations and identify which logical and physical design tools are needed to process each module in the description, as well as the order in which to invoke the logical physical design tools. Dependencies in the execution of the design tools on the various modules of the description are analyzed to determine where the processing of modules may be performed in parallel to optimize execution.

6665852, Dec 16, 2003

Nov 30, 2001

09/998558

Zhaoyun Xing - San Jose CA
Russell Kao - Portola Valley CA

Sun Microsystems, Inc. - Santa Clara CA

G06F 1750

716 12, 716 5, 716 6, 716 7, 716 13, 716 14

The problem of searching for a low cost path from a source location to a target location through a traversable region partitioned into a plurality of tiles is solved using source and target cost functions. Each tile in the traversable region is defined by boundary segments. The source cost function provides a cost for traversing from the source location to the boundary segment in question. The target cost function provides a cost for traversing from the boundary segment in question to the target location. The target cost function is estimated, and the source cost function is calculated. A path cost function is determined by adding the source and target cost functions. If the target location is a tile, then the target cost may be estimated using a convex hull of the target tile and the boundary segment in question. To facilitate the cost function calculations, multiple forms of cost function propagation between segments are disclosed.

6792587, Sep 14, 2004

Jan 28, 2002

10/058550

Zhaoyun Xing - San Jose CA
Russell Kao - Portola Valley CA

Sun Microsystems, Inc. - Palo Alto CA

G06F 1750

716 12, 716 13, 716 14, 716 15

A routing graph (e. g. , a 2. 5-D graph) and a method for generating same is provided for more efficient multiple-layer path searching and routing. Subgraphs are generated for each layer, and then are combined (e. g. , through via connections) into a single, multi-layer graph. The resulting 2. 5-dimensional graph may be used in VLSI routing, for example, which commonly includes multiple routing layers in a given design space. Each subgraph corresponds to a layer of circuitry and includes segments based on segments from other layers and intersection points of all such segments. Methods of generating subgraph layers are disclosed.

7139992, Nov 21, 2006

Nov 30, 2001

09/998559

Zhaoyun Xing - San Jose CA, US
Russell Kao - Portola Valley CA, US

Sun Microsystems, Inc. - Santa Clara CA

G06F 17/50

716 12, 716 4, 716 9, 716 13, 716 14

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.

20020104061, Aug 1, 2002

Nov 30, 2001

09/998405

Zhaoyun Xing - San Jose CA, US
Russell Kao - Portola Valley CA, US

Sun Microsystems, Inc.

G06F017/50

716/004000

Linear minimum convolution (LMC) calculations are used, for example, to enhance calculations using cost functions as part of path searching methods. Thus, an LMC of a weight value with a continuous piecewise linear function may be calculated. An exemplary cost function includes a plurality of line segments connected at knot points. As part of the calculation of the LMC, a forward leg sweep is performed in one direction over the cost function, followed by a backward leg sweep in the opposite direction. The forward leg sweep is performed using a clipping function. The clipping function includes a knot point connecting a first leg having a slope equal to the weight value and a second leg having a slope equal to the negative of the weight value.

20030018462, Jan 23, 2003

Mar 28, 2002

10/109139

Liang T. Chen - Saratoga CA, US
Earl T. Cohen - Fremont CA, US
Russell Kao - Portola Valley CA, US
Thomas M. McWilliams - Menlo Park CA, US

G06F017/50

703/019000

A method and apparatus for simulating a source system having a plurality of source clocks to trigger a plurality of logic elements is provided. The plurality of source clocks are modeled with a global clock. At least one of the plurality of source clocks is modeled with a clock mask and a clock state. At least one of the plurality of logic elements is evaluated when the global clock generates a global clock pulse and updated based on the clock mask and the clock state.

47220503, Jan 26, 1988

Mar 27, 1986

6/845213

Ruby B. Lee - Cupertino CA
Allen J. Baum - Palo Alto CA
Russell Kao - Palo Alto CA

Hewlett-Packard Company - Palo Alto CA

G06F 1300
G06F 930

364200

A computer having a cache memory and a main memory is provided with a transformation unit between the main memory and the cache memory so that at least a portion of an information unit retrieved from the main memory may be transformed during retrieval of the information (fetch) from a main memory and prior to storage in the cache memory (cache). In a specific embodiment, an instruction may be predecoded prior to storage in the cache memory. In another embodiment involving a branch instruction, the address of the target of the branch is calculated prior to storing in the instruction cache. The invention has advantages where a particular instruction is repetitively executed since a needed decode operation which has been partially performed previously need not be repeated with each execution of an instruction. Consequently, the latency time of each machine cycle may be reduced, and the overall efficiency of the computing system can be improved. If the architecture defines delayed branch instructions, such branch instructions may be executed in effectively zero machine cycles.