Partitioning a model into a plurality of independent partitions to be processed within a distributed environment

• US 7,124,071 B2
• Filed: 04/18/2002
• Issued: 10/17/2006
• Est. Priority Date: 04/18/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mellors, William K, Rich, Marvin J, Joe, Soon I.
• Primary Examiner(s): Rodriguez, Paul L.
• Assistant Examiner(s): Ochoa, Juan Carlos
• Application Number:
  US10/125,217
• Publication Number:
  US 20030200073A1
• Time in Patent Office: 1,643 Days
• Field of Search: 326/93, 370/218, 370/392, 702/60, 703 13- 17, 703/20, 703/22, 703/23, 703/27, 709/248, 714/33, 714/38, 716 1- 18, 717/141, 717/149
• US Class Current: 703/16
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking

Abstract

A model is partitioned into a plurality of partitions to be processed by a selected number of processors. Since the partitions are substantially independent of one another, the policy employed in the mapping of the partitions to the processors is flexible. Further, in the case in which the model is a chip, at least a portion of the clock and maintenance logic of the chip is also partitioned and mapped to the selected number of processors.

Claims

1. A method of partitioning a model, said method comprising:

automatically partitioning a model of an arbitrary size into a plurality of partitions to be distributed across an arbitrary number of processors;

determining clock logic of the model common to multiple partitions of the plurality of partitions; and

associating the common clock logic with the multiple partitions, wherein a partition of the plurality of partitions not sharing the clock logic is excluded from having the common clock logic associated therewith, and wherein the automatically partitioning, the determining and the associating are automatically performed without user directive.

2. The method of claim 1, further comprising assigning the plurality of partitions to the arbitrary number of processors.

3. The method of claim 2, wherein the assigning is based on a policy, said policy being independent of the partitioning.

4. The method of claim 1, wherein the model is to be simulated within a distributed environment, said distributed environment comprising said arbitrary number of processors.

5. The method of claim 4, wherein said model is to be simulated using event simulation.

6. The method of claim 1, wherein said automatically partitioning comprises:

partitioning the model into multiple cones of logic; and

combining the multiple cones of logic into the plurality of partitions.

7. The method of claim 1, wherein said model comprises functionality of a chip.

8. The method of claim 7, wherein the automatically partitioning comprises:

partitioning the functionality of the chip into multiple logic units, each logic unit comprising a single latch of the chip; and

combining the multiple logic units into the plurality of partitions, wherein each partition of the plurality of partitions comprises one or more logic units of the multiple logic units.

9. The method of claim 8, wherein said combining into a partition of the plurality of partitions comprises:

determining whether a latch of one logic unit intersects with one or more latches of one or more other logic units; and

including in said partition said one logic unit and any of said one or more other logic units determined to intersect with said one logic unit.

10. The method of claim 9, wherein the latch of the one logic unit intersects with the latch of another logic unit, when the latch of the one logic unit shares combinatorial logic with the latch of the another logic unit.

11. The method of claim 8, wherein the combining comprises:

obtaining a list of intersecting latches, wherein said list includes a plurality of entries having a latch id and an intersecting latch id;

determining whether zero or more latch ids are repeated one or more times in the list, wherein zero or more sets of multiple entries are provided, and wherein a set, if provided, comprises multiple entries having the same latch id;

for each set of multiple entries that is provided;

removing from the list one or more multiple entries of the set, wherein one entry of the set remains in the list;

providing in the list one or more latch ids that correspond to one or more intersecting latch ids of the set removed; and

assigning the one or more latch ids provided in the list an intersecting latch id of the set;

repeating said determining, said removing, said providing and said assigning, at least in response to at least one set of multiple entries being provided;

reducing said list, in which there are no intersecting latch ids equal to latch ids; and

using the reduced list in assigning the multiple logic units to the plurality of partitions.

12. The method of claim 11, wherein the one entry of the set to remain in the list is the entry with the lowest intersecting latch id of the set.

13. The method of claim 11, wherein the assigning of the intersecting latch id comprises the assigning of the intersecting latch id that is remaining in the list for that set.

14. The method of claim 11, wherein said reducing comprises:

locating in the list one or more intersecting latch ids that have the same value as a latch id of the list;

changing the one or more intersecting latch ids to the intersecting latch id corresponding to the latch id of the same value; and

repeating the locating and changing zero or more times, until there are no intersecting latch ids equal to the latch ids.

15. The method of claim 7, further comprising:

partitioning clock logic of the chip into multiple clock partitions; and

assigning the multiple clock partitions to one or more processors of the arbitrary number of processors.

16. The method of claim 15, wherein a clock partition of the multiple clock partitions corresponds to a partition of the plurality of partitions, and wherein the assigning comprises assigning the clock partition and the partition to a same processor.

17. The method of claim 1, wherein a partition of the plurality of partitions is disjoint from the other partitions of the plurality of partitions.

18. The method of claim 1, further comprising partitioning other logic associated with said model into at least one of a plurality of logic partitions and a common set of logic to be assigned to at least a plurality of processors of said arbitrary number of processors.

19. The method of claim 18, wherein the common set of logic is assigned to each processor of the arbitrary number of processors.

20. The method of claim 18, wherein a logic partition of the plurality of logic partitions is associated with a partition of the plurality of partitions, and wherein the logic partition and the partition are assigned to a same processor of the arbitrary number of processors.

21. A method of partitioning a chip, said method comprising:

partitioning functionality of a chip of an arbitrary size into multiple cones of logic;

combining the multiple cones of logic into a plurality of partitions, wherein the plurality of partitions are provided without user directive;

mapping the plurality of partitions to an arbitrary number of processors;

partitioning, without user directive, clock logic of the chip into a plurality of clock partitions and a common set of clock logic, said common set of clock logic being common to multiple partitions of the plurality of partitions;

assigning the plurality of clock partitions to the arbitrary number of processors; and

associating, without user directive, the common set of clock logic with the multiple partitions, wherein a partition of the plurality of partitions not sharing the common set of clock logic is excluded from having the common set of clock logic associated therewith.

22. The method of claim 21, wherein the partitioning into a plurality of clock partitions comprises, for a clock partition, identifying clock logic uniquely associated with a latch of the chip, and wherein the assigning for the clock partition comprises writing the identified clock logic to the processor of the latch.

23. The method of claim 21, wherein the partitioning into a common set of clock logic comprises:

determining whether clock logic of one or more latches of the chip intersects with clock logic of one or more other latches of the chip; and

combining the intersecting logic to provide the common set of clock logic.

24. The method of claim 23, further comprising assigning the common set of clock logic to one or more processors of the arbitrary number of processors, wherein said assigning comprises writing the common set of clock logic to the one or more processors having partitions sharing the common set of clock logic.

25. The method of claim 21, further comprising partitioning other logic of the chip into at least one of a plurality of logic partitions and a common set of logic to be assigned to at least a plurality of processors of the arbitrary number of processors.

26. The method of claim 21, wherein each cone of logic comprises a latch of the chip, and wherein the combining comprises:

obtaining a list of intersecting latches, wherein said list includes a plurality of entries having a latch id and an intersecting latch id;

determining whether zero or more latch ids are repeated one or more times in the list, wherein zero or more sets of multiple entries are provided, and wherein a set, if provided, comprises multiple entries having the same latch id;

for each set of multiple entries that is provided;

removing from the list one or more multiple entries of the set, wherein one entry of the set remains in the list;

providing in the list one or more latch ids that correspond to one or more intersecting latch ids of the set removed; and

assigning the one or more latch ids provided in the list an intersecting latch id of the set;

repeating said determining, said removing, said providing, and said assigning, at least in response to at least one set of multiple entries being provided;

reducing said list, in which there are no intersecting latch ids equal to latch ids; and

using the reduced list in assigning the multiple cones of logic to the plurality of partitions.

27. The method of claim 26, wherein said reducing comprises:

locating in the list one or more intersecting latch ids that have the same value as a latch id of the list;

changing the one or more intersecting latch ids to the intersecting latch id corresponding to the latch id of the same value; and

repeating the locating and changing zero or more times, until there are no intersecting latch ids equal to the latch ids.

28. The method of claim 21, wherein the mapping is based on a policy that is independent from the partitioning.

29. A system of partitioning a model, said system comprising:

means for automatically partitioning a model of an arbitrary size into a plurality of partitions to be distributed across an arbitrary number of processors;

means for determining clock logic of the model common to multiple partitions of the plurality of partitions; and

means for associating the common clock logic with the multiple partitions, wherein a partition of the plurality of partitions not sharing the clock logic is excluded from having the common clock logic associated therewith, and wherein the automatically partitioning, the determining and the associating are automatically performed without user directive.

30. The system of claim 29, further comprising means for assigning the plurality of partitions to the arbitrary number of processors.

31. The system of claim 30, wherein the assigning is based on a policy, said policy being independent of the partitioning.

32. The system of claim 29, wherein the model is to be simulated within a distributed environment, said distributed environment comprising said arbitrary number of processors.

33. The system of claim 32, wherein said model is to be simulated using event simulation.

34. The system of claim 29, wherein said means for automatically partitioning comprises:

means for partitioning the model into multiple cones of logic; and

means for combining the multiple cones of logic into the plurality of partitions.

35. The system of claim 29, wherein said model comprises functionality of a chip.

36. The system of claim 35, wherein the means for automatically partitioning comprises:

means for partitioning the functionality of the chip into multiple logic units, each logic unit comprising a single latch of the chip; and

means for combining the multiple logic units into the plurality of partitions, wherein each partition of the plurality of partitions comprises one or more logic units of the multiple logic units.

37. The system of claim 36, wherein said means for combining into a partition of the plurality of partitions comprises:

means for determining whether a latch of one logic unit intersects with one or more latches of one or more other logic units; and

means for including in said partition said one logic unit and any of said one or more other logic units determined to intersect with said one logic unit.

38. The system of claim 37, wherein the latch of the one logic unit intersects with the latch of another logic unit, when the latch of the one logic unit shares combinatorial logic with the latch of the another logic unit.

39. The system of claim 36, wherein the means for combining comprises:

means for obtaining a list of intersecting latches, wherein said list includes a plurality of entries having a latch id and an intersecting latch id;

means for determining whether zero or more latch ids are repeated one or more times in the list, wherein zero or more sets of multiple entries are provided, and wherein a set, if provided, comprises multiple entries having the same latch id;

means for performing for each set of multiple entries that is provided;

removing from the list one or more multiple entries of the set, wherein one entry of the set remains in the list;

providing in the list one or more latch ids that correspond to one or more intersecting latch ids of the set removed; and

assigning the one or more latch ids provided in the list an intersecting latch id of the set;

means for repeating the determining and the performing, at least in response to at least one set of multiple entries being provided;

means for reducing said list, in which there are no intersecting latch ids equal to latch ids; and

means for using the reduced list in assigning the multiple logic units to the plurality of partitions.

40. The system of claim 39, wherein the one entry of the set to remain in the list is the entry with the lowest intersecting latch id of the set.

41. The system of claim 39, wherein the assigning of the intersecting latch id comprises the assigning of the intersecting latch id that is remaining in the list for that set.

42. The system of claim 39, wherein said means for reducing comprises:

means for locating in the list one or more intersecting latch ids that have the same value as a latch id of the list;

means for changing the one or more intersecting latch ids to the intersecting latch id corresponding to the latch id of the same value; and

means for repeating the locating and changing zero or more times, until there are no intersecting latch ids equal to the latch ids.

43. The system of claim 35, further comprising:

means for partitioning clock logic of the chip into multiple clock partitions; and

means for assigning the multiple clock partitions to one or more processors of the arbitrary number of processors.

44. The system of claim 43, wherein a clock partition of the multiple clock partitions corresponds to a partition of the plurality of partitions, and wherein the means for assigning comprises means for assigning the clock partition and the partition to a same processor.

45. The system of claim 29, wherein a partition of the plurality of partitions is disjoint from the other partitions of the plurality of partitions.

46. The system of claim 29, further comprising means for partitioning other logic associated with said model into at least one of a plurality of logic partitions and a common set of logic to be assigned to at least a plurality of processors of said arbitrary number of processors.

47. The system of claim 46, wherein the common set of logic is assigned to each processor of the arbitrary number of processors.

48. The system of claim 46, wherein a logic partition of the plurality of logic partitions is associated with a partition of the plurality of partitions, and wherein the logic partition and the partition are assigned to a same processor of the arbitrary number of processors.

49. A system of partitioning a chip, said system comprising:

means for partitioning functionality of a chip of an arbitrary size into multiple cones of logic;

means for combining the multiple cones of logic into a plurality of partitions, wherein the plurality of partitions are provided without user directive;

means for mapping the plurality of partitions to an arbitrary number of processors;

means for partitioning, without user directive, clock logic of the chip into a plurality of clock partitions and a common set of clock logic, said common set of clock logic being common to multiple partitions of the plurality of partitions;

means for assigning the plurality of clock partitions to the arbitrary number of processors; and

means for associating, without user directive, the common set of clock logic with the multiple partitions, wherein a partition of the plurality of partitions not sharing the common set of clock logic is excluded from having the common set of clock logic associated therewith.

50. The system of claim 49, wherein the means for partitioning into a plurality of clock partitions comprises, for a clock partition, means for identifying clock logic uniquely associated with a latch of the chip, and wherein the means for assigning for the clock partition comprises means for writing the identified clock logic to the processor of the latch.

51. The system of claim 49, wherein the means for partitioning into a common set of clock logic comprises:

means for determining whether clock logic of one or more latches of the chip intersects with clock logic of one or more other latches of the chip; and

means for combining the intersecting logic to provide the common set of clock logic.

52. The system of claim 51, further comprising means for assigning the common set of clock logic to one or more processors of the arbitrary number of processors, wherein said means for assigning comprises means for writing the common set of clock logic to the one or more processors having partitions sharing the common set of clock logic.

53. The system of claim 49, further comprising means for partitioning other logic of the chip into at least one of a plurality of logic partitions and a common set of logic to be assigned to at least a plurality of processors of the arbitrary number of processors.

54. The system of claim 49, wherein each cone of logic comprises a latch of the chip, and wherein the means for combining comprises:

means for obtaining a list of intersecting latches, wherein said list includes a plurality of entries having a latch id and an intersecting latch id;

means for determining whether zero or more latch ids are repeated one or more times in the list, wherein zero or more sets of multiple entries are provided, and wherein a set, if provided, comprises multiple entries having the same latch id;

means for performing for each set of multiple entries that is provided;

removing from the list one or more multiple entries of the set, wherein one entry of the set remains in the list;

providing in the list one or more latch ids that correspond to one or more intersecting latch ids of the set removed; and

assigning the one or more latch ids provided in the list an intersecting latch id of the set;

means for repeating the determining and the performing, at least in response to at least one set of multiple entries being provided;

means for reducing said list, in which there are no intersecting latch ids equal to latch ids; and

means for using the reduced list in assigning the multiple cones of logic to the plurality of partitions.

55. The system of claim 54, wherein said means for reducing comprises:

means for locating in the list one or more intersecting latch ids that have the same value as a latch id of the list;

means for changing the one or more intersecting latch ids to the intersecting latch id corresponding to the latch id of the same value; and

means for repeating the locating and changing zero or more times, until there are no intersecting latch ids equal to the latch ids.

56. The system of claim 49, wherein the mapping is based on a policy that is independent from the partitioning.

57. A system of partitioning a model, said system comprising:

at least one processor to automatically partition a model of an arbitrary size into a plurality of partitions to be distributed across an arbitrary number of processors, to determine clock logic of the model common to multiple partitions of the plurality of partition, and to associate the common clock logic with the multiple partitions, wherein a partition of the plurality of partitions not sharing the clock logic is excluded from having the common clock logic associated therewith, and wherein the automatically partitioning, the determining and the associating are automatically performed without user directive.

58. A system of partitioning a chip, said system comprising:

at least one processor to partition functionality of a chip of an arbitrary size into multiple cones of logic, to combine the multiple cones of logic into a plurality of partitions, wherein the plurality of partitions are provided without user directive, to map the plurality of partitions to an arbitrary number of processors, to partition, without user directive, clock logic of the chip into a plurality of clock partitions and a common set of clock logic, said common set of clock logic being common to multiple partitions of the plurality of partitions, to assign the plurality of clock partitions to the arbitrary number of processors, and to associate without user directive, the common set of clock logic with the multiple partitions, wherein a partition of the plurality of partitions not sharing the common set of clock logic is excluded from having the common set of clock logic associated therewith.

59. At least one program storage device readable by a machine tangibly embodying at least one program of instructions executable by the machine to perform a method of partitioning a model, said method comprising:

automatically partitioning a model of an arbitrary size into a plurality of partitions to be distributed across an arbitrary number of processors;

determining clock logic of the model common to multiple partitions of the plurality of partitions; and

associating the common clock logic with the multiple partitions, wherein a partition of the plurality of partitions not sharing the clock logic is excluded from having the common clock logic associated therewith, and wherein the automatically partitioning, the determining and the associating are automatically performed without user directive.

60. The at least one program storage device of claim 59, wherein said method further comprises assigning the plurality of partitions to the arbitrary number of processors.

61. The at least one program storage device of claim 60, wherein the assigning is based on a policy, said policy being independent of the partitioning.

62. The at least one program storage device of claim 59, wherein the model is to be simulated within a distributed environment, said distributed environment comprising said arbitrary number of processors.

63. The at least one program storage device of claim 62, wherein said model is to be simulated using event simulation.

64. The at least one program storage device of claim 59, wherein said automatically partitioning comprises:

partitioning the model into multiple cones of logic; and

combining the multiple cones of logic into the plurality of partitions.

65. The at least one program storage device of claim 59, wherein said model comprises functionality of a chip.

66. The at least one program storage device of claim 65, wherein the automatically partitioning comprises:

partitioning the functionality of the chip into multiple logic units, each logic unit comprising a single latch of the chip; and

combining the multiple logic units into the plurality of partitions, wherein each partition of the plurality of partitions comprises one or more logic units of the multiple logic units.

67. The at least one program storage device of claim 66, wherein said combining into a partition of the plurality of partitions comprises:

determining whether a latch of one logic unit intersects with one or more latches of one or more other logic units; and

including in said partition said one logic unit and any of said one or more other logic units determined to intersect with said one logic unit.

68. The at least one program storage device of claim 67, wherein the latch of the one logic unit intersects with the latch of another logic unit, when the latch of the one logic unit shares combinatorial logic with the latch of the another logic unit.

69. The at least one program storage device of claim 66, wherein the combining comprises:

obtaining a list of intersecting latches, wherein said list includes a plurality of entries having a latch id and an intersecting latch id;

determining whether zero or more latch ids are repeated one or more times in the list, wherein zero or more sets of multiple entries are provided, and wherein a set, if provided, comprises multiple entries having the same latch id;

for each set of multiple entries that is provided;

removing from the list one or more multiple entries of the set, wherein one entry of the set remains in the list;

providing in the list one or more latch ids that correspond to one or more intersecting latch ids of the set removed; and

assigning the one or more latch ids provided in the list an intersecting latch id of the set;

repeating said determining, said removing, said providing and said assigning, at least in response to at least one set of multiple entries being provided;

reducing said list, in which there are no intersecting latch ids equal to latch ids; and

using the reduced list in assigning the multiple logic units to the plurality of partitions.

70. The at least one program storage device of claim 69, wherein the one entry of the set to remain in the list is the entry with the lowest intersecting latch id of the set.

71. The at least one program storage device of claim 69, wherein the assigning of the intersecting latch id comprises the assigning of the intersecting latch id that is remaining in the list for that set.

72. The at least one program storage device of claim 69, wherein said reducing comprises:

locating in the list one or more intersecting latch ids that have the same value as a latch id of the list;

changing the one or more intersecting latch ids to the intersecting latch id corresponding to the latch id of the same value; and

repeating the locating and changing zero or more times, until there are no intersecting latch ids equal to the latch ids.

73. The at least one program storage device of claim 65, wherein said method further comprises:

partitioning clock logic of the chip into multiple clock partitions; and

assigning the multiple clock partitions to one or more processors of the arbitrary number of processors.

74. The at least one program storage device of claim 73, wherein a clock partition of the multiple clock partitions corresponds to a partition of the plurality of partitions, and wherein the assigning comprises assigning the clock partition and the partition to a same processor.

75. The at least one program storage device of claim 59, wherein a partition of the plurality of partitions is disjoint from the other partitions of the plurality of partitions.

76. The at least one program storage device of claim 59, wherein said method further comprises partitioning other logic associated with said model into at least one of a plurality of logic partitions and a common set of logic to be assigned to at least a plurality of processors of said arbitrary number of processors.

77. The at least one program storage device of claim 76, wherein the common set of logic is assigned to each processor of the arbitrary number of processors.

78. The at least one program storage device of claim 76, wherein a logic partition of the plurality of logic partitions is associated with a partition of the plurality of partitions, and wherein the logic partition and the partition are assigned to a same processor of the arbitrary number of processors.

79. At least one program storage device readable by a machine tangibly embodying at least one program of instructions executable by the machine to perform a method of partitioning a chip, said method comprising:

partitioning functionality of a chip of an arbitrary size into multiple cones of logic;

combining the multiple cones of logic into a plurality of partitions, wherein the plurality of partitions are provided without user directive;

mapping the plurality of partitions to an arbitrary number of processors;

partitioning, without user directive, clock logic, of the chip into a plurality of clock partitions and a common set of clock logic, said common set of clock logic being common to multiple partitions of the plurality of partitions;

assigning the plurality of clock partitions to the arbitrary number of processors; and

associating, without user directive, the common set of clock logic with the multiple partitions, wherein a partition of the plurality of partitions not sharing the common set of clock logic is excluded from having the common set of clock logic associated therewith.

80. The at least one program storage device of claim 79, wherein the partitioning into a plurality of clock partitions comprises, for a clock partition, identifying clock logic uniquely associated with a latch of the chip, and wherein the assigning for the clock partition comprises writing the identified clock logic to the processor of the latch.

81. The at least one program storage device of claim 79, wherein the partitioning into a common set of clock logic comprises:

determining whether clock logic of one or more latches of the chip intersects with clock logic of one or more other latches of the chip; and

combining the intersecting logic to provide the common set of clock logic.

82. The at least one program storage device of claim 81, wherein the method further comprises assigning the common set of clock logic to one or more processors of the arbitrary number of processors, wherein said assigning comprises writing the common set of clock logic to the one or more processors having partitions sharing the common set of clock logic.

83. The at least one program storage device of claim 79, wherein said method further comprises partitioning other logic of the chip into at least one of a plurality of logic partitions and a common set of logic to be assigned to at least a plurality of processors of the arbitrary number of processors.

84. The at least one program storage device of claim 79, wherein each cone of logic comprises a latch of the chip, and wherein the combining comprises:

obtaining a list of intersecting latches, wherein said list includes a plurality of entries having a latch id and an intersecting latch id;

determining whether zero or more latch ids are repeated one or more times in the list, wherein zero or more sets of multiple entries are provided, and wherein a set, if provided, comprises multiple entries having the same latch id;

for each set of multiple entries that is provided;

removing from the list one or more multiple entries of the set, wherein one entry of the set remains in the list;

providing in the list one or more latch ids that correspond to one or more intersecting latch ids of the set removed; and

assigning the one or more latch ids provided in the list an intersecting latch id of the set;

repeating said determining, said removing, said providing, and said assigning, at least in response to at least one set of multiple entries being provided;

reducing said list, in which there are no intersecting latch ids equal to latch ids; and

using the reduced list in assigning the multiple cones of logic to the plurality of partitions.

85. The at least one program storage device of claim 84, wherein said reducing comprises:

locating in the list one or more intersecting latch ids that have the same value as a latch id of the list;

changing the one or more intersecting latch ids to the intersecting latch id corresponding to the latch id of the same value; and

repeating the locating and changing zero or more times, until there are no intersecting latch ids equal to the latch ids.

86. The at least one program storage device of claim 79, wherein the mapping is based on a policy that is independent from the partitioning.