Partitioning for a massively parallel simulation system

A computer system to partition a logic design for a cycle-based system, comprising:

• a processor;
• a memory;
• and
• software instructions stored in the memory for enabling the computer system under control of the processor to:
• build an intermediate form data flow graph (IFgraph) from an intermediate form data flow tree (IFtree) associated with the logic design;
• partition the IFgraph for each of at least three levels of hardware granularity of the cycle-based system to obtain a partitioned IFgraph, wherein the partitioning of the IFgraph comprises:
• coarsening the IFgraph to obtain a coarsened IFgraph for a first level of the at least three levels of hardware granularity;
• balancing a set of nodes of the coarsened IFgraph for the first level into a first subset and a second subset to obtain a balanced IFgraph for the first level;
• uncoarsening the balanced IFgraph for the first level to obtain an uncoarsened balanced IFgraph for the first level;
• coarsening the uncoarsened balanced IFgraph for the first level to obtain a coarsened IFgraph for a second level of the at least three levels of hardware granularity;
• balancing a set of nodes of the coarsened IFgraph for the second level into a third subset and a fourth subset to obtain a balanced IFgraph for the second level;
• uncoarsening the balanced IFgraph for the second level to obtain an uncoarsened balanced IFgraph for the second level;
• coarsening the uncoarsened balanced IFgraph for the second level to obtain a coarsened IFgraph for a third level of the at least three levels of hardware granularity;
• balancing a set of nodes of the coarsened IFgraph for the third level into a fifth subset and a sixth subset to obtain a balanced IFgraph for the third level;
• and
• uncoarsening the balanced IFgraph for the third level to obtain the partitioned IFgraph,
• wherein the first subset and the second subset are each within a predefined constraint of the cycle-based system, and
• wherein the predefined constraint comprises at least one selected from the group consisting of memory capacity, register capacity, bit-register capacity, static random access memory (SRAM) capacity, and number of processor instructions;
• and
• rewrite the IFtree based on the partitioned IFgraph.

A compiler to compile a logic design of a cycle-based system, comprising:

• a partitioner configured to:
• accept as input an intermediate form data flow graph (IFgraph) from an intermediate form data flow tree (IFtree) associated with the logic design;
• partition the IFgraph for each of at least three levels of hardware granularity of the cycle-based system to obtain a partitioned IFgraph, wherein the partitioning of the IFgraph comprises:
• coarsening the IFgraph to obtain a coarsened IFgraph for a first level of the at least three levels of hardware granularity;
• balancing a set of nodes of the coarsened IFgraph for the first level into a first subset and a second subset to obtain a balanced IFgraph for the first level;
• uncoarsening the balanced IFgraph for the first level to obtain an uncoarsened balanced IFgraph for the first level;
• coarsening the uncoarsened balanced IFgraph for the first level to obtain a coarsened IFgraph for a second level of the at least three levels of hardware granularity;
• balancing a set of nodes of the coarsened IFgraph for the second level into a third subset and a fourth subset to obtain a balanced IFgraph for the second level;
• uncoarsening the balanced IFgraph for the second level to obtain an uncoarsened balanced IFgraph for the second level;
• coarsening the uncoarsened balanced IFgraph for the second level to obtain a coarsened IFgraph for a third level of the at least three levels of hardware granularity;
• balancing a set of nodes of the coarsened IFgraph for the third level into a fifth subset and a sixth subset to obtain a balanced IFgraph for the third level;
• and
• uncoarsening the balanced IFgraph for the third level to obtain the partitioned IFgraph,
• wherein the first subset and the second subset are each within a predefined constraint of the cycle-based system, and
• wherein the predefined constraint comprises at least one selected from the group consisting of memory capacity, register capacity, bit-register capacity, static random access memory (SRAM) capacity, and number of processor instructions;
• and
• rewrite the IFtree based on the partitioned IFgraph;
• and
• a scheduler configured to schedule a node associated with the IFgraph on a processor array.

A plurality of nodes to compile a logic design of a cycle-based system, comprising:

• a partitioner configured to:
• accept as input an intermediate form data flow graph (IFgraph) from an intermediate form data flow tree (IFtree) associated with the logic design;
• partition the IFgraph for each of at least three levels of hardware granularity of the cycle-based system to obtain a partitioned IFgraph, wherein the partitioning of the IFgraph comprises:
• coarsening the IFgraph to obtain a coarsened IFgraph for a first level of the at least three levels of hardware granularity;
• balancing a set of nodes of the coarsened IFgraph for the first level into a first subset and a second subset to obtain a balanced IFgraph for the first level;
• uncoarsening the balanced IFgraph for the first level to obtain an uncoarsened balanced IFgraph for the first level;
• coarsening the uncoarsened balanced IFgraph for the first level to obtain a coarsened IFgraph for a second level of the at least three levels of hardware granularity;
• balancing a set of nodes of the coarsened IFgraph for the second level into a third subset and a fourth subset to obtain a balanced IFgraph for the second level;
• uncoarsening the balanced IFgraph for the second level to obtain an uncoarsened balanced IFgraph for the second level;
• coarsening the uncoarsened balanced IFgraph for the second level to obtain a coarsened IFgraph for a third level of the at least three levels of hardware granularity;
• balancing a set of nodes of the coarsened IFgraph for the third level into a fifth subset and a sixth subset to obtain a balanced IFgraph for the third level;
• and
• uncoarsening the balanced IFgraph for the third level to obtain the partitioned IFgraph,
• wherein the first subset and the second subset are each within a predefined constraint of the cycle-based system, and
• wherein the predefined constraint comprises at least one selected from the group consisting of memory capacity, register capacity, bit-register capacity, static random access memory (SRAM) capacity, and number of processor instructions;
• and
• rewrite the IFtree based on the partitioned IFgraph;
• and
• a scheduler configured to schedule the set of nodes of the IFgraph on a processor array,
• wherein the partitioner is located on at least one of the plurality of nodes, and
• wherein the scheduler is executing on at least one of the plurality of nodes.