Douglas Rea Boyle

US Patent:

6557145, Apr 29, 2003

Filed:

Mar 6, 2001

Appl. No.:

09/801010

Inventors:

Douglas B. Boyle - Palo Alto CA
James S. Koford - San Jose CA

Assignee:

Monterey Design Systems, Inc. - Sunnyvale CA

International Classification:

G06F 1750

US Classification:

716 2, 716 7, 716 8

Abstract:

A method for design optimization using logical and physical information is provided. In one embodiment, a method for design optimization using logical and physical information, includes receiving a behavioral description of an integrated circuit or a portion of an integrated circuit, optimizing placement of circuit elements in accordance with a first cost function, and optimizing logic of the circuit elements in accordance with a second cost function, in which the optimizing placement of the circuit elements and the optimizing logic of the circuit elements are performed concurrently. The method can further include optimizing routing in accordance with a third cost function, in which the optimizing routing, the optimizing placement of the circuit elements, and the optimizing logic of the circuit elements are performed concurrently.

US Patent:

60995807, Aug 8, 2000

Filed:

Feb 11, 1998

Appl. No.:

9/021973

Inventors:

Douglas B. Boyle - Palo Alto CA
James S. Koford - San Jose CA

Assignee:

Monterey Design Systems, Inc. - Sunnyvale CA

International Classification:

G06F 1750

US Classification:

716 7

Abstract:

A method for optimizing layout design using logical and physical information performs placement, logic optimization and routing and routing estimates concurrently. In one embodiment, circuit elements of the integrated circuit is partitioned into clusters. The clusters are then placed and routed by iterating over an inner-loop and an outer-loop according to cost functions in the placement model which takes into consideration interconnect wiring delays. Iterating over the inner-loop, logic optimization steps improves the cost functions of the layout design. Iterating over the outer-loop, the size of the clusters, hence the granularity of the placement, is refined until the level of individual cells is reached. The present method is especially suited for parallel processing by multiple central processing units accessing a shared memory containing the design data base.

US Patent:

58648542, Jan 26, 1999

Filed:

Jan 5, 1996

Appl. No.:

8/583334

Inventors:

Douglas B. Boyle - Palo Alto CA

Assignee:

LSI Logic Corporation - Milpitas CA

International Classification:

G06F 1730

US Classification:

707 10

Abstract:

An information system and method for reducing workload load on servers in an information system network. The system defines a group of interconnected clients which have associated cache memories. The system maintains a shared group cache look-up table for the group having entries which identify data items cached by the clients within the group and identify the clients at which the data items are cached. Each client in the group has access to the group cache look-up table, and any client or group can cache any data item. The system can include a hierarchy of groups, with each group having a group cache look-up table. The group cache look-up tables minimize requests for data items outside the groups and greatly minimize the service load on servers having popular data items.

US Patent:

56823223, Oct 28, 1997

Filed:

Apr 19, 1994

Appl. No.:

8/229949

Inventors:

Douglas B. Boyle - Palo Alto CA
James S. Koford - San Jose CA
Ranko Scepanovic - Cupertino CA
Edwin R. Jones - Sunnyvale CA
Michael D. Rostoker - Boulder Creek CA

Assignee:

LSI Logic Corporation - Milpitas CA

International Classification:

G06F 1750

US Classification:

364491

Abstract:

The fitness of a cell placement for an integrated circuit chip is optimized by relocating at least some of cells to new locations that provide lower interconnect congestion. For each cell, the centroid of the net of cells to which the cell is connected is computed. The cell is then moved toward the centroid by a distance that is equal to the distance from the current position of the cell to the centroid multiplied by a "chaos" factor. lambda. The value of. lambda. is selected such that the cell relocation operations will cause the placement to converge toward an optimal configuration without chaotic diversion, but with a sufficiently high chaotic element to prevent the optimization operation from becoming stuck at local fitness maxima. The new cell locations can be modified to include the effects of cells in other locations, such as by incorporating a function of cell density gradient or force direction into the computation. This spreads out clumps of cells so that the density of cells is more uniform throughout the placement.

US Patent:

59639750, Oct 5, 1999

Filed:

Sep 17, 1997

Appl. No.:

8/932042

Inventors:

Douglas B. Boyle - Palo Alto CA
James S. Koford - San Jose CA
Edwin R. Jones - Sunnyvale CA
Ranko Scepanovic - Cupertino CA
Michael D. Rostoker - Boulder Creek CA

Assignee:

LSI Logic Corporation - Milpitas CA

International Classification:

G06F 1300

US Classification:

711147

Abstract:

The capacity of a cache memory is substantially reduced over that required for a multi-chip distributed shared memory (DSM) implementation to enable the cache memory, a main memory, a processor and requisite logic and control circuitry to fit on a single integrated circuit chip. The increased cache miss rate created by the reduced cache memory capacity is compensated for by the reduced cache miss resolution period resulting from integrating the main memory and processor on the single chip. The reduced cache miss resolution period enables the processor clock rate to be substantially increased, so that a processor having a simple functionality such as a reduced instruction set computer (RISC) processor can be utilized and still provide the required processing speed. The RISC processor is substantially smaller than a more complicated processor that would be required to provide the same processing speed in a multi-chip DSM implementation, thereby enabling the RISC processor to fit on the chip with the other elements. A single-chip communications node that can be used in telecommunications networks other than DSM includes a memory controller for providing local and remote memory coherency, and a bidirectional interconnect unit that converts memory access instructions into memory access messages and vice-versa.

US Patent:

58703136, Feb 9, 1999

Filed:

Dec 9, 1997

Appl. No.:

8/987865

Inventors:

Douglas B. Boyle - Palo Alto CA
James S. Koford - San Jose CA
Ranko Scepanovic - Cupertino CA
Edwin R. Jones - Sunnyvale CA
Michael D. Rostoker - Boulder Creek CA

Assignee:

LSI Logic Corporation - Milpitas CA

International Classification:

G06F 1750

US Classification:

364491

Abstract:

One or more non-overlapping moving windows are positioned over a placement of cells for an integrated circuit chip to delineate respective subsets of cells. A fitness improvement operation such as simulated evolution is performed on the subsets simultaneously using parallel processors. The windows are either moved to specifically identified high interconnect congestion areas of the placement, or are moved across the placement in a raster type pattern such that each area of the placement is processed at least once. Exchange of misplaced cells between subsets can be accomplished by dimensioning the windows and designing the window movement pattern such that the subsets overlap. Alternatively, such exchange can be accomplished by using two sets of windows of different sizes. As yet another alternative, the improvement operation can allow misplaced cells to move to a border area outside a window. Each misplaced cell is placed on a list, and then moved to the centroid of a net of cells to which it is connected, which can be outside the subset that originally included the misplaced cell.

US Patent:

56194196, Apr 8, 1997

Filed:

Sep 13, 1994

Appl. No.:

8/306182

Inventors:

Patrik D'Haeseleer - Atherton CA
Douglas B. Boyle - Palo Alto CA

Assignee:

LSI Logic Corporation - Milpitas CA

International Classification:

G06F 1500

US Classification:

364490

Abstract:

A method of cell placement for an integrated circuit chip includes performing a chaotic improvement operation on an initial cell placement. At least some of the cells are relocated to new locations that provide lower interconnect wirelength and congestion. For each cell, the centroid of the net of cells to which the cell is connected is computed. The cell is then moved toward the centroid by a distance that is equal to the distance from the current position of the cell to the centroid multiplied by a "chaos" factor. lambda. The value of. lambda. is selected such that the cell relocation operations will cause the placement to converge toward an optimal configuration without chaotic diversion, but with a sufficiently high chaotic element to prevent the optimization operation from becoming stuck at local fitness maxima. The chaotic placement operation can generate illegal placements in which two or more cells can occupy one location, some locations can contain no cells and/or two or more cells can partially overlap. Cell overlap is reduced and the spatial distribution of the placement improved by computing a density map representing cell densities in incremental blocks of the placement respectively, computing, from the density map, a warp map representing first repulsive forces exerted at centers of said blocks by cell densities in surrounding blocks respectively, interpolating, from the warp map, second repulsive forces acting on selected cells in the placement and spatially distributing the selected cells in accordance with the second repulsive forces.

US Patent:

55176585, May 14, 1996

Filed:

May 4, 1994

Appl. No.:

8/238597

Inventors:

David Gluss - Woodside CA
Georgia Lazana - Mountain View CA
Douglas Boyle - Palo Alto CA

Assignee:

LSI Logic Corporation - Milpitas CA

International Classification:

G06F 1560

US Classification:

395800

Abstract:

A method for testing the timing parameters of a system design is presented, especially suited for use in testing for timing violations between the pins of a semiconductor device. A description of the timing constraints of the various modules of a design is written in a common non-technical vernacular, and functions as an input file. A Timing Shell Generator converts the input file description into a simulator-environment-compatible output code-language file description. The output code-language file is operative to implement the timing constraints of the original input file during simulation such that any violations of the prescribed timing constraints are indicated to the tester who can then take appropriate action.