Logic verification in large systems

• US 7,171,347 B2
• Filed: 07/02/1999
• Issued: 01/30/2007
• Est. Priority Date: 07/02/1999
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Joshi, Mandar S., Otto, Steve W., Casas, Jeremy S., Seligman, Erik M., Khaira, Manpreet S., Yang, Honghua H.
• Primary Examiner(s): Rodriguez; Paul
• Assistant Examiner(s): CRAIG, DWIN M
• Application Number:
  US09/347,690
• Publication Number:
  US 20030163297A1
• Time in Patent Office: 2,769 Days
• Field of Search: 703/15, 703/14, 703/28, 716/18, 716/2, 716/1, 716/3, 716/4, 716/7, 716/8, 716/12, 716/16, 713/400, 710/104, 710/305, 709/250
• US Class Current: 703/15
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking

Abstract

A method of preparing a circuit model for simulation comprises decomposing the circuit model having a number of latches into a plurality of extended latch boundary components and partitioning the plurality of extended latch boundary components. Decomposing and partitioning the circuit model may include decomposing hierarchical cells of the circuit model, and using a constructive bin-packing heuristic to partition the plurality of extended latch boundary components. The partitioned circuit model is compiled, and simulated on a uni-processor, a multi-processor, or a distributed processing computer system.

Claims

1. A computer-implemented method of preparing a circuit model for simulation comprising:

decomposing the circuit model having a number of latches into a plurality of extended latch boundary components; and

partitioning the plurality of extended latch boundary components using a bin-packing heuristic, wherein using the bin-packing heuristic comprises

constructing a plurality of seeds from the plurality of extended latch boundary components

merging the plurality of extended latch boundary components with the plurality of seeds;

loading the decomposed circuit model into memory.

2. A computer-implemented method of preparing a circuit model for simulation comprising:

decomposing the circuit model having a number of latches into a plurality of extended latch boundary components;

partitioning the plurality of extended latch boundary components using a bin-packing heuristic, wherein decomposing the circuit model having a number of latches into a plurality of extend latch boundary components comprises

identifying an extended latch boundary component that meets a size constraint for at least one of a plurality of hierarchical cells;

loading the decomposed circuit model into memory.

3. The method of claim 2, wherein partitioning the plurality of extended latch boundary components comprises:

grouping the plurality of extended latch boundary components into a plurality of partitions by approximately equalizing the number of latches in each of the plurality of partitions.

4. A computer-implemented method of preparing a circuit model for simulation comprising:

decomposing the circuit model having a number of latches into a plurality of extended latch boundary components;

partitioning the plurality of extended latch boundary components using a bin-packing heuristic, wherein partitioning the plurality of extended latch boundary components comprises

grouping the plurality of extended latch boundary components to form a plurality of partitions, each of the plurality of partitions having a size;

loading the decomposed circuit model into memory.

5. The method of claim 4, wherein partitioning the plurality of extended latch boundary components comprises:

partitioning the plurality of extended latch boundary components by approximately equalizing the number of latches in each of the plurality of partitions, approximately equalizing the latches that are activated in each of the plurality of partitions, and approximately equalizing the size of each of the plurality of partitions.

6. A computer-implemented method of preparing a circuit model for simulation comprising:

decomposing the circuit model having a number of latches into a plurality of extended latch boundary components;

partitioning the plurality of extended latch boundary components using a bin-packing heuristic, wherein partitioning the plurality of extended latch boundary components comprises

partitioning the plurality of extended latch boundary components based on activity load balancing;

loading the decomposed circuit model into memory.

7. A computer-implemented method of preparing a circuit model for simulation, the circuit model having a model size, comprising:

merging a plurality of extended latch boundary components into a plurality of partitions having a partition size using a bin-packing heuristic;

maintaining a load balance within the plurality of partitions;

reducing circuit overlap within the plurality of partitions;

adjusting the load balance to obtain a partition size of less than about 120% of the model size;

loading the plurality of partitions into memory.

8. The method of claim 7, further comprising:

adjusting the load balance to obtain a partition size of less than about 110% of the model size.

9. A computer-implemented method of preparing a circuit model for a simulation having a total simulation time, the method comprising:

grouping a plurality of extended latch boundary components into a plurality of partitions using a bin-packing heuristic;

reducing the communication time within the plurality of partitions by adjusting the grouping;

reducing the communication time within the plurality of partitions to less than about ten percent of the total simulation time by adjusting the grouping;

loading the plurality of partitions into memory.

10. A computer-implemented method of sharing a repeated circuit structure among partitions created using a bin-packing heuristic in a circuit model, the method comprising:

expanding the repeated circuit structure once to form an expanded circuit structure;

grafting the expanded circuit structure to the circuit model as needed, wherein grafting the expanded circuit structure to the circuit model as needed comprises

copying a table representing the expanded circuit structure into the circuit model;

loading the expanded circuit structure into memory.

11. A computer-implemented method of sharing a repeated circuit structure among partitions created using a bin-packing heuristic in a circuit model, the method composing:

expanding the repeated circuit structure once to form an expanded circuit structure;

grafting the expanded circuit structure to the circuit model as needed, wherein grafting the expanded circuit structure to the circuit model as needed comprises

altering a table representing the circuit model to add the expanded circuit structure;

loading the expanded circuit structure into memory.

12. A computer system comprising:

a processor unit;

a dicing unit operably coupled to the processor unit, capable of executing on the processor unit, and capable of decomposing a circuit model into a plurality of extended latch boundary components, and capable of partitioning the plurality of extended latch boundary components; and

a simulation unit operably coupled to the dicing unit and the processor unit, and capable of executing on the processor unit.

13. The computer system of claim 12, wherein the processor unit is a plurality of distributed processor units.

14. The computer system of claim 13, wherein the dicing unit is capable of load balancing.

15. The computer system of claim 14, wherein the dicing unit is capable of activity load balancing.