System and method for automatically segmenting and populating a distributed computing problem

• US 20050015571A1
• Filed: 05/29/2003
• Published: 01/20/2005
• Est. Priority Date: 05/29/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lehman, Tobin Jon, Kaufman, James H.
• Granted Patent: US 7,467,180 B2
• Time in Patent Office: Days
• US Class Current: 712/10
• CPC Class Codes: G06F 30/23 using finite element methods [FEM] or finite difference methods [FDM]

Abstract

The initial partitioning of a distributed computing problem can be critical, and is often a source of tedium for the user. A method is provided that automatically segments the problem into fixed sized collections of original program cells (OPCs) based on the complexity of the problem specified, and the combination of computing agents of various caliber available for the overall job. The OPCs that are on the edge of a collection can communicate with OPCs on the edges of neighboring collections, and are indexed separately from OPCs that are within the ‘core’ or inner non-edge portion of a collection. Consequently, core OPCs can iterate independently of whether any communication occurs between collections and groups of collections (VPPs). All OPCs on an edge have common dependencies on remote information (i.e., their neighbors are all on the same edge of a neighboring collection).

Claims

1. A method of automatically segmenting and populating a distributed problem, comprising:

determining a bounding space that is at least equal in size to a problem space volume;

partitioning the bounding space into a plurality of sub-spaces capable of holding collections of original problem cells; and

mapping the problem into the partitioned bounding space to populate the collections with data from the problem, for processing the problem.

2. The method of claim 1, further comprising determining boundaries between the subspaces.

3. The method of claim 2, further comprising determining coupling interdependencies between the subspaces.

4. The method of claim 3, further comprising determining complexities associated with the boundaries.

5. The method of claim 1, wherein the bounding space comprises a physical space.

6. The method of claim 5, wherein the bounding space comprises a single dimension physical space.

7. The method of claim 5, wherein the bounding space comprises a multi-dimensional physical space.

8. The method of claim 1, wherein the bounding space comprises an abstract space.

9. The method of claim 8, wherein the bounding space comprises any of a single dimension abstract space or a multi-dimensional abstract space.

10. The method of claim 1, wherein the problem is arbitrarily sized.

11. The method of claim 10, wherein processing the problem comprises assigning the problem to a plurality of interconnected nodes;

and

wherein the problem exceeds a memory capacity of each node.

12. The method of claim 1, further comprising calculating densities of the collections.

13. The method of claim 12, wherein if a particular collection density exceeds an upper threshold, dynamically subdividing the particular collection into a finer granularity.

14. The method of claim 12, wherein if the densities of two or more contiguous collections fall below a lower threshold, dynamically joining the two or more contiguous collections.

15. The method of claim 14, wherein if a particular collection density exceeds an upper threshold, dynamically subdividing the particular collection into a finer granularity.

16. The method of claim 15, wherein dynamically joining the two or more contiguous collections comprises selectively joining the two or more contiguous collections, provided the density of the joined two or more contiguous collections does not exceed the upper threshold.

17. The method of claim 1, wherein the original problem cells are grouped into fixed size original problem cell collections.

18. The method of claim 1, wherein the original problem cells are assigned to variable problem partitions.

19. The method of claim 1, further comprising identifying edges of the original problem cell collections that can communicate with neighboring original problem cell collections.

20. The method of claim 1, further comprising identifying edges of the original problem cell collections that must communicate with neighboring original problem cell collections.

21. A system for automatically segmenting and populating a distributed problem, comprising:

means for determining a bounding space that is at least equal in size to a problem space volume;

means for partitioning the bounding space into a plurality of sub-spaces capable of holding collections of original problem cells; and

means for mapping the problem into the partitioned bounding space to populate the collections with data from the problem, for processing the problem.

22. The system of claim 21, further comprising a means for determining boundaries between the subspaces.

23. The system of claim 22, wherein the means for determining the boundaries between the subspaces further determines coupling interdependencies between the subspaces.

24. The system of claim 23, wherein the means for determining the boundaries between the subspaces further determines complexities associated with the boundaries.

25. The system of claim 21, wherein the bounding space comprises a physical space.

26. The system of claim 21, wherein the bounding space comprises an abstract space.

27. The system of claim 21, further comprising means for calculating densities of the collections.

28. The system of claim 27, wherein if a particular collection density exceeds an upper threshold, the means for calculating the densities of the collections dynamically subdivides the particular collection into a finer granularity.

29. The system of claim 27, wherein if the densities of two or more contiguous collections fall below a lower threshold, the means for calculating the densities of the collections dynamically joins the two or more contiguous collections.

30. The system of claim 21, wherein the original problem cells are assigned to variable problem partitions.

31. A computer program product having instruction codes for automatically segmenting and populating a distributed problem, comprising:

a first set of instruction codes for determining a bounding space that is at least equal in size to a problem space volume;

a second set of instruction codes for partitioning the bounding space into a plurality of sub-spaces capable of holding collections of original problem cells; and

a third set of instruction codes for mapping the problem into the partitioned bounding space to populate the collections with data from the problem, for processing the problem.

32. The computer program product of claim 31, further comprising a fourth set of instruction codes for determining boundaries between the subspaces.

33. The computer program product of claim 32, wherein the fourth set of instruction codes further determines coupling interdependencies between the subspaces.

34. The computer program product of claim 33, wherein the fourth set of instruction codes further determines complexities associated with the boundaries.

35. The computer program product of claim 31, wherein the bounding space comprises a physical space.

36. The computer program product of claim 31, wherein the bounding space comprises an abstract space.

37. The computer program product of claim 31, further comprising a fifth set of instruction codes for calculating densities of the collections.

38. The computer program product of claim 37, wherein if a particular collection density exceeds an upper threshold, the fifth set of instruction codes dynamically subdivides the particular collection into a finer granularity.

39. The computer program product of claim 37, wherein if the densities of two or more contiguous collections fall below a lower threshold, the fifth set of instruction codes dynamically joins the two or more contiguous collections.

40. The computer program product of claim 31, wherein the original problem cells are assigned to variable problem partitions.

41. The computer program product of claim 31, wherein the distributed problem comprises a connected problem.