Cadence Design Systems, Inc.

International Business Machines Corporation

Wave Computing, Inc.

Asmus Hetzel

Steven L Teig

Etienne Jacques

Anish Malhotra

Jonathan Frankle

Akira Fujimura

Heath Feather

Jon Frankle

David S Harrison

Alexandre Matveev

Roger King

Dieter F Wendel

Juergen Koehl

Erich Klink

Parsotam Trikam Patel

Samit Chaudhuri

Ivan Q Peyrot

Deepak Cherukuri

Disclosed techniques utilize a satisfiability solver for allocation and/or configuration of resources in a reconfigurable fabric of processing elements. A dataflow graph is an input provided to a toolchain that includes a satisfiability solver. The satisfiability solver operates on subsets of interconnected nodes within a dataflow graph to derive a solution. The solution is trimmed by removing artifacts and unnecessary parts. The solutions of subsets are then used as an input to additional subsets of nodes within the dataflow graph in an iterative process to derive a complete solution. The satisfiability solver technique uses adaptive windowing in both the time dimension and the spatial dimensions of the dataflow graph. Processing elements and routing elements within the reconfigurable fabric are configured based on the complete solution. Data computation is performed based on the dataflow graph using the processing elements and the routing resources.

Reconfigurable processor fabric implementation using satisfiability analysis

Some embodiments of the invention provide a Local Preferred Direction (LPD) wiring model for use with one or more EDA tools (such as placing, routing, etc). An LPD wiring model allows at least one wiring layer to have a set of regions that each have a different preferred direction than the particular wiring layer. In addition, each region has a local preferred direction that differs from the local preferred direction of at least one other region in the set. Furthermore, at least two regions have two different polygonal shapes and no region in the set encompasses another region in the set. Some embodiments also provide a Graphical User Interface (GUI) that facilitates a visual presentation of an LPD design layout and provides tools to create and manipulate LPD regions in a design layout.

Local preferred direction architecture

Some embodiments of the invention provide a method for pre-tabulating sub-networks. This method (1) generates a sub-network that performs a function, (2) generates a parameter based on this function, and (3) stores the sub-network in a storage structure based on the generated parameter. In some embodiments, the generated sub-network has several circuit elements. Also, in some embodiments, the generated sub-network performs a set of two or more functions. Some embodiments store each generated sub-network in an encoded manner. Some embodiments provide a method for producing a circuit description of a design. This method (1) selects a candidate sub-network from the design, (2) identifies an output function performed by the sub-network, (3) based on the identified output function, identifies a replacement sub-network from a storage structure that stores replacement sub-networks, and (4) replaces the selected candidate sub-network with the identified replacement sub-network in certain conditions. In some embodiments, this method is performed to map a design to a particular technology library. Some embodiments provide a data storage structure that stores a plurality of sub-networks based on parameters derived from the output functions of the sub-networks.

Method and apparatus for pre-tabulating sub-networks

A method is provided that performs a path search that identifies several path extensions. The method performs a viability check on a particular path extension by identifying first and second circuit geometries. The first circuit geometry is associated with a particular segment of a route that would result from the particular path expansion in a design layout. The second circuit geometry is associated with a circuit element to which the particular segment connects. The viability check also determines whether connecting the segment with the first geometry and the circuit element with the second geometry is allowable based on predetermined rules. The method stores the particular path expansion in a storage medium as a viable path expansion when the viability check determines that connecting the segment with the first geometry and the circuit element with the second geometry is allowable.

Method and apparatus for routing

Some embodiments of the invention provide a method for defining wiring directions in a design layout having several wiring layers. The method decomposes a first wiring layer into several non-overlapping regions. It assigns at least two different local preferred wiring directions to at least two of the regions. In some embodiments, the method decomposing the first wiring layer by using the vertices of items in the layout to decompose the layout. In some of these embodiments, the items include macro blocks. The method of some embodiments also identifies several power via arrays on the first wiring layer, and identifies a local preferred wiring direction based on the arrangement of the power via arrays on the first wiring layer.

Method and apparatus for generating layout regions with local preferred directions

A method for watermarking a circuit design layout based on frequency or number of geometric structures. The method includes dividing a circuit design layout into a plurality of segments or tiles. Certain segments are selected, and within these selected segments, a router alters the number of geometric structures, such as vias and jogs, of the circuit design layout in the selected segments to form the watermark without relying on a netlist. The number of geometric structures is changed slightly so that a random sampling of segments would not identify the watermark since the variations would not be detectable or would be within acceptable variances, but the watermark would be readily identified if the selected segments are known. The watermark or portions thereof can be used to encode one or more data bits.

Watermarking a chip design based on frequency of geometric structures

Some embodiments of the invention provide a router that can define a route that has different widths along different directions on the same layer. To facilitate the creation of such a route, some embodiments adaptively define the shape of interconnect-line ends (i.e., the shape of route-segment ends) on a particular layer based on the routing directions available on the particular layer. By so defining these shapes, these embodiments improve the alignment of route segments that have differing widths. In other words, dynamically defining the interconnect-line ends improves the shape of a route at bends along which the route transition from one width to another. Also, to facilitate the creation of a route with different widths and/or spacing in different directions on a particular layer, some embodiments define, for each available routing direction on the particular layer, an 'unroutable' bloated region about a previously defined geometry (e.g., a previously defined obstacle, wire, or via pad) on the particular layer. An item's bloated region for a particular routing direction specifies the portion of the particular layer that is not available for route segments along the particular routing direction. As further described below, the item's bloated region for a particular direction is derived based on the minimum spacing required between the item and any route segment in the particular direction for the particular net.

Some embodiments of the invention provide a method for defining wiring directions in a design layout having several wiring layers. The method decomposes a first wiring layer into several non-overlapping regions. It assigns at least two different local preferred wiring directions to at least two of the regions. In some embodiment, the method decomposing the first wiring layer by using the vertices of items in the layout to decompose the layout. In some of these embodiments, the item include macro blocks. The method of some embodiments also identifies several power via arrays on the first wiring layer, and identifies a local preferred wiring direction based on the arrangement of the power via arrays on the first wiring layer.

Disclosed is a method, system, and computer program product for performing interblock stitching for electronic designs. According to some approaches, interblock stitching is accomplished by implementing a stitching region between the block and external routing structures. The stitching region is implemented using local preferred direction approaches.

Block interstitching using local preferred direction architectures, tools, and apparatus

Method and apparatus replacing sub-networks within an IC design

Some embodiments of the invention provide a routing method. The routing method receives a set of nets to route in a region of an integrated circuit ('IC') layout. The routing method defines routes for the nets in a manner that ensures that each segment of each route is not less than a minimum length that is required for the segment. In some embodiments, the routing method identifies a route for a net by performing one or more path search operations. Each path search operation identifies one set of path expansions that can be used to define a segment of a route for the net. A path search operation in some embodiments performs a viability check for each path expansion that it identifies, in order to ensure that any segment that might eventually result from an identified set of path expansions satisfies its minimum required length.

Method and apparatus for performing a path search

Local preferred direction architecture, tools, and apparatus

Some embodiments of the invention provide a method for routing. The method defines at least one wiring layer that has at least two regions with different local preferred wiring directions. The method then uses the differing local preferred wiring directions to define a global route on the wiring layer. The two regions are a first region with a first local preferred wiring direction, and a second region with a second local preferred wiring direction. The global route traverses the first region along the first local preferred wiring direction and traverses the second region along the second local preferred wiring direction.

Local preferred direction routing

A method for pre-tabulating sub-networks that (1) generates a sub-network that performs a function, (2) generates a parameter based on this function, and (3) stores the sub-network based on the parameter. In some embodiments, the generated sub-network has several circuit elements, performs two or more functions, or is stored in an encoded manner. A method for producing a circuit description of a design that (1) selects a candidate sub-network from the design, (2) identifies an output function performed by the sub-network, (3) based on the identified output function, identifies a replacement sub-network from a storage structure, and (4) replaces the candidate sub-network with the replacement sub-network in certain conditions. In some embodiments, this method is performed to map a design to a particular technology library. Some embodiments provide a data storage structure that stores sub-networks based on parameters derived from the output functions of the sub-networks.

Growing community of inventors

Berlin, Germany

Asmus Hetzel