International Business Machines Corporation

Globalfoundries Inc.

Michael David Moffitt

Zhuo Li

Paul Gerard Villarrubia

Matyas A Sustik

Charles Jay Alpert

Chin Ngai Sze

David Anthony Papa

Zoltan T Hidvegi

Chuck Alpert

A recursive solution to a bin-packing algorithm provides efficient allocation of computing or communications resources to resource consumers in a computer or network system. The algorithm determines resource requirement vectors for the consumers that specify amounts of multiple resource types required for each consumer, thereby forming a multi-dimensional bin-packing problem. The algorithm assigns the resource consumers to corresponding groups of computing or communication resources by recursively exploring partial solutions that assign the consumers to the groups by extending the partial solutions via recursion until the requirements in the resource requirement vectors are met. The bin-packing algorithm tests resource requirements vectors for remaining unassigned ones of the resource consumers for both assignment and non-assignment to a current individual group of computing or communications resources in a current partial solution until the current partial solution becomes a complete solution that satisfies the requirement vectors for the plurality of resource consumers.

Multi-dimensional computing and communication resource allocation using bin-packing with per-branch combination tries

Multi-way partitioning is dramatically improved based on 'weakest-link' optimality. The set of numbers to be partitioned is subjected to pairwise decomposition with a first partition having a candidate subset (P={S}), and a lower cost bound cis set equal to a maximum cost of this subset. A recursive call is then invoked to resolve the subproblem of the second partition (P={S, S, . . . , S}). If each second candidate subset in the second partition has a cost which is less than or equal to the lower cost bound, then the first partition is returned with the second partition as an optimal solution regardless of whether the second partition is an optimal decomposition. Additional efficiency may be achieved by excluding any subset having a cost which is greater than or equal to the best cost so far. Dominated and symmetric solutions can also be excluded.

Multi-way number partitioning using weakest link optimality

A recursive solution to a bin-packing algorithm provides efficient placement of objects in a physical layout. The algorithm determines requirement vectors for the objects that specify requirement for placement of the object in multiple dimensions, thereby forming a multi-dimensional bin-packing problem. The algorithm assigns the objects to physical partitions or 'bins' by recursively exploring partial solutions that place the objects in the partitions by extending the partial solutions via recursion until the objects are placed. The bin-packing algorithm tests requirements vectors for remaining unassigned ones of the objects for both assignment and non-assignment to a current partition in a current partial solution until the current partial solution becomes a complete solution that satisfies the requirement vectors for the plurality of objects.

Multi-dimensional physical arrangement techniques using bin-packing with per-branch combination tries

Methods, systems, and computer program products may provide planning for hardware-accelerated functional verification in data processing systems. A method may include receiving, by a computer system, a description of architecture of a hardware accelerator for accelerating functional verification of a circuit design, the architecture including a plurality of logical processors. The method may additionally include receiving, by the computer system, a description of the circuit design having a plurality of gates, and representing, by the computer system, each gate, each stage of the functional verification, and each logical processor as a separate object based on the received description of the architecture and the circuit design. The method may further include representing, by the computer system, relationships between gates as pairwise edges, and defining, by the computer system, a goal state that requires each gate to be scheduled for execution by a logical processor during a stage of the functional verification.

Planning for hardware-accelerated functional verification

A circuit design is partitioned for hardware-accelerated functional verification using a directed hypergraph with edge weights that are a function of slack. Slack may be computed as the difference between the early and late ranks for the source of an edge. The weight may further be computed as the difference between the edge's slack and a maximum slack value. In a preferred implementation each vertex also has multiple weights associated with resource requirements of different node types, and the partitioning is constrained to prevent vertex movement that would result in vertex weights for a given partition exceeding a partition resource capacity based on the accelerator architecture. Edge and vertex weights can be recomputed for the next level of partitioning. The partitioning process can be repeatedly iteratively until a termination criterion is met, the termination criterion being based in part on the number of directed cuts in each of the partitions.

Partitioning for hardware-accelerated functional verification

A circuit design is compiled for hardware-accelerated functional verification by removing internal gates of a uniform operator tree (e.g., an assertion tree) while retaining node information, and partitioning the circuit to optimize connectivity without being constrained by the uniform operator tree. After partitioning, sub-trees are constructed for the partitions, and aggregated to form a master tree. The sub-trees can have leaf nodes at varying depths based on ranks of the leaf nodes, and the master tree can similarly provide inputs from the sub-trees at varying depths based on simulation depths for the sub-trees. The resynthesized master tree is structurally distinct from the original uniform operator tree but, since the inputs are commutative (e.g., OR gates), the functional equivalence of the model is preserved.

Partitioning and scheduling uniform operator logic trees for hardware accelerators

A method, system, and computer usable program product for buffer-aware routing in integrated circuit design are provided in the illustrative embodiments. The design has cells, and the circuit includes buffers and wires. A route is received from a set of routes. The route couples a first point in the circuit to a second point in the circuit and including at least one buffer between the first point and the second point. A determination is made whether the route violates a set of hard constraints for a part of the circuit, where the set of hard constraints includes a reach length constraint. In response to the route not violating any hard constraint in the set of hard constraints, the route is selected as a buffer-aware routing solution between the first and the second points in the circuit.

Buffer-aware routing in integrated circuit design

A method, system, and computer usable program product for automated planning in physical synthesis are provided in the illustrative embodiments. A state of an integrated circuit design is identified where the state is a representation of a particular configuration of circuit components having a particular electrical characteristic. A first operation applicable to the first state is selected and applied to reach a second state of the design. A consequence of reaching the second state is analyzed. If the consequence indicates an improvement in the design, a solution is presented to achieve the improvement. The solution includes manipulations of design components using a set of operations to reach the second state from the first state.

Automated planning in physical synthesis

A portion of a gate-level netlist representing an integrated circuit design is selected for optimization. A timing window representing the selected portion is made comprising one or more copies of the selected portion. A checkpoint is created for the timing window and stored in a transaction history. One or more changes are then made to the timing window and stored in the transaction history. The changed elements are marked as dirty and stored in the transaction history. After the one or more changes have been made, the timing window is queried for current timing conditions and compared with the checkpoint. If the one or more changes are an improvement, the one or more changes are committed by replicating the one or more changes to the portion of the gate-level netlist. If the one or more changes are not an improvement, the timing window may be restored to the checkpoint.

Method for bounded transactional timing analysis

The present disclosure is directed to a method for estimating an interconnect delay for a source-to-sink path of a net within a Very Large Scale Integration (VLSI) circuit, the source-to-sink path connecting a source and a sink in the net. The method may comprise estimating a total wire capacitance; calculating a delay contribution based on delay of the source-to-sink path and delay of a plurality of off-path sinks; and estimating the interconnect delay for the source-to-sink path based on the delay contribution.

Method and system for point-to-point fast delay estimation for VLSI circuits

A method, data processing system and computer program product for optimizing the placement of logic gates of a subcircuit in a physical synthesis flow. A Path Smoothing utility identifies one or more movable gates based on at least one selection criteria. A set of legalized candidate locations corresponding to one or more identified movable gates is generated. A disjunctive timing graph based on the generated set of legalized candidate locations is then generated. An optimal location of one or more movable gate(s) is determined using a recursive branch-and-bound search and stored in the computing device.

Growing community of inventors

Austin, TX, United States of America

Michael David Moffitt