Lsi Logic Corporation

Pedja Raspopovic

Ranko L Scepanovic

Alexander E Andreev

Ivan Pavisic

Alexander Andreev

Elyar Eldarovich Gasanov

Anatoli Aleksandrovich Bolotov

Mikhail I Grinchuk

Aiguo Lu

Partha Datta Ray

Partha P Data Ray

Aiquo Lu

An optimization apparatus and method optimizes a functional block within a netlist of an integrated circuit design. A corresponding delay value is assigned to each of a plurality of pins of the block. Each pin corresponds to a respective signal path through the block. The delay values together form a delay value combination, which is selected from a continuous set of possible combinations in which each combination in the set satisfies a predetermined criteria. A circuit configuration for the block is then generated with a plurality of logic cells that are interconnected in the netlist such that the respective signal paths have delays through the block that are based on the corresponding delay values.

Method and apparatus for adaptive timing optimization of an integrated circuit design

A pre-placement delay model for a logical function block of an integrated circuit design includes a fan-in count variable, a fan-out count variable and a delay variable. The fan-in count variable has a value indicative of a number of inputs to the logical function block. The fan-out count variable has a value indicative of the number of inputs of other logical function blocks that are driven by an output of the logical function block. The delay variable has a value that is a function of the binary logarithm of the fan-in count variable and the binary logarithm of the fan-out count variable.

Virtual tree-based netlist model and method of delay estimation for an integrated circuit design

A computer program that improves a netlist of logic nodes and physical placement for an IC. The program (a) identifies critical nodes based on delay information calculated from the physical placement. Then the program (b) selects a set of critical nodes and optimally collapses their critical fan-ins and part of the non-critical fan-ins based on their Boolean relationship, which, includes at least one critical node. After that, the program (c) remaps the collapsed sub-netlist by covering its subject graph with an optimal pattern graph, and dynamically estimates and updates the fanout loads. The program returns to step (b) if the remapped sub-netlist is unacceptable, and returns to step (a) after updating the delay information and coordinates of newly mapped gates if the remapped sub-netlist is acceptable. The program exits at step (a) when no more critical nodes are identified at step (a).

Netlist resynthesis program based on physical delay calculation

A program for improving a netlist of logic nodes and physical placement for an IC. The program (A) identifies critical nodes based on time calculated from a physical placement. The program (B) selects a set of critical nodes and sub-netlists associated with the critical nodes and co-factors critical fan-ins in the sub-netlists. The program remaps the sub-netlists by optimization and dynamically estimates and updates fanout loads. The program returns to step B if the remapped sub-netlist is unacceptable, returns to step A if the remapped sub-netlist is acceptable, and exits at step A when no more critical nodes are identified at step A.

Netlist resynthesis program using structure co-factoring

Channels are routed in an integrated circuit layout by reserving grid positions for buffers. Cell pins are identified at different y-coordinates to be connected by the channel. A determination is made as to the necessity of a jog between vertical segments, and if so, a y-coordinate is assigned to each such jog. An x-coordinate is assigned to each channel segment extending across the y-coordinates. Y-coordinates are assigned to buffers to be connected to the channel.

Channel router with buffer insertion

True paths are identified in a timing graph of a circuit in which the timing graph contains known false paths containing nodes of at least two sets selected from FROM, THROUGH and TO nodes. The false paths are processed to include sets of FROM and TO nodes and then transformed into equivalent sets of two logical false paths. True path intervals are constructed as logical subgraphs that do not describe any equivalent false path. In preferred embodiments, the process is carried out by a computer under control of a computer readable program.

IC timing analysis with known false paths

A linear assignment problem for an ordered system containing a plurality of boxes each containing an object having an associated penalty function is solved. A hierarchy contains a bottom level containing at least as many generalized boxes as there are boxes in the assignment problem, and top and intermediate levels. The objects of the assignment problem are placed in the generalized box of the top level. A first local task is executed to transition the contents of a generalized box of a higher level to at least two generalized boxes of the next lower level. A second local task is executed on the generalized boxes of the lower level to minimize a global penalty function. The first and second tasks are executed through successive iterations until all of the objects are placed in the generalized boxes in the bottom level in a layout having minimal penalty function.

Process for solving assignment problems in integrated circuit designs with unimodal object penalty functions and linearly ordered set of boxes

The invention is directed to optimization of an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins. The surface is divided into a set of areas, and a boundary pin is defined at each point on a boundary of one of the areas where the boundary of the one of the areas intersects a net. Routing optimization is then performed in at least one of the areas, the routing optimization optimizing the routing among the net pins and the boundary pins within the at least one of the areas. The invention is also directed to optimization of an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins. The surface is divided into a first set of pre-defined areas, and routing optimization is performed independently in each of the pre-defined areas in the first set. The surface is divided into a second set of pre-defined areas, and routing optimization is performed independently in each of the pre-defined areas in the second set. It is a feature of this aspect of the invention that each of plural pre-defined areas in the first set overlaps at least two pre-defined areas in the second set, and each of plural pre-defined areas in the second set overlaps at least two pre-defined areas in the first set.

Wire routing optimization

A method for routing nets in an integrated circuit design, said method comprising the steps of dividing the integrated circuit design with lines in a first direction and lines in a second direction, forming a routing graph having vertices and edges, wherein vertices correspond to locations where lines in the first direction cross lines in the second direction, routing nets as a function of said routing graph with parallel processors operating substantially simultaneously, determining the relative wire congestion among different areas in the integrated circuit design, and rerouting nets passing though areas with a relatively high wire congestion.

Method and apparatus for parallel simultaneous global and detail routing

A method for routing nets in an integrated circuit design, said method comprising the steps of forming a routing graph for an integrated circuit design, said routing graph have edges in a first direction and edges in a second direction, globally routing said integrated circuit design in accordance with said routing graph, dividing the routing graph into strips, for each strip in the routing graph, generating a general task for optimizing the routing in the strip, solving general tasks in parallel by assigning different processors different strips to process.

Method and apparatus for local optimization of the global routing

A method for implementing net routing for an integrated circuit design with parallel processors, said method comprising the steps of creating a character array, filling said character array with a first character, dividing a plurality of nets into groups, supplying a plurality of locks and assigning each said group its own individual lock, assigning for each net in said plurality of nets a position in the character array; and placing a second character in the position of a particular net in said character array when the net is operated on by a processor and replacing said second character with the first character after said operation is completed.

Method and apparatus for parallel routing locking mechanism

Nets are routed on an integrated circuit device by dividing a portion of the integrated circuit device into a first group of tiles. A first routing graph is then formed as a function of the first group of tiles and nets are routed as a function of the first routing graph. A new group of tiles is formed by dividing the tiles of the first group of tiles, a new routing graph is formed as a function of the new group of tiles, and nets are rerouted as a function of the new routing graph. The steps of the preceding sentence are then repeated and each time a new group of tiles is formed, the tiles are divided in a same first dimension, resulting in tiles have progressively smaller lengths in that first dimension, while the size of the tiles in a second dimension does not change.

Method and apparatus for coarse global routing

A method for routing a net on an integrated circuit device, said method comprising the steps of creating a list of basis elements of the net, said basis elements being defined by a predetermined size limitation, determining a complexity value for each basis element as a function of the distance between pins in the basis element, forming a hypertree for the net as a function of complexity values of basis elements so determined, and routing the net as a function of the hypertree.

Net routing using basis element decomposition

The present invention provides for a method and apparatus to partition high fanout nets into smaller subnets. Said method includes the steps of identifying elementary pairs of pins in the net, each such elementary pair defining a line; eliminating lines such that a planar graph is formed; eliminating further lines such that a spanning tree is formed, said spanning tree connecting each pin in the net; identifying basic elements, each basic element forming a portion of said spanning tree; and constructing a connected cover for said net, said connected cover comprising a plurality of said basic elements.

Method and apparatus for parallel Steiner tree routing

A method for optimizing the routing of nets in an integrated circuit device, said method comprising the steps of dividing an integrated circuit design with lines in a first direction and lines in a second direction, wherein said first direction is substantially orthogonal to said second direction, forming a routing graph with vertices corresponding to locations where lines in said first direction and lines in said second direction cross and edges connect vertices, for each edge in a plurality of edges in said routing graph, computing an individual edge occupancy value, for an edge in said plurality of edges, computing a penalty value as a function of the individual edge occupancy value of a different edge, and routing a net as a function of said penalty value.

Growing community of inventors

Cupertino, CA, United States of America

Pedja Raspopovic