System and Method for Parallel Processing

• US 20110016153A1
• Filed: 07/14/2010
• Published: 01/20/2011
• Est. Priority Date: 07/17/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: El-Shishiny, Hisham, Atta, Islam
• Granted Patent: US 8,370,394 B2
• Time in Patent Office: Days
• US Class Current: 707/797
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes

Abstract

A method for parallel processing of data organized in the form of a tree including: converting the tree into a linear array structure including a data array for storing the data of said tree and three reference arrays; determining partial workloads from the linear array structure obtained at step a; and performing parallel processing of said partial workloads. Each entry in the data array corresponding to a given node in the tree and includes three pointers. The pointers each point to a respective one of the reference arrays: a first pointer identifies the parent node of the given node, a second pointer identifies the first child node of the given node, and a third pointer identifies the sibling node of the given node.

Claims

1. A method for parallel processing of data organized in the form of a tree, the method comprising:

converting the tree into a linear array structure including a data array for storing the data of said tree and three reference arrays, wherein each entry in said data array corresponds to a given node in said tree and includes three pointers, with each of said three pointers pointing to a respective one of said three reference arrays, wherein a first one of said pointers identifies a parent node of said given node, a second one of said pointers identifies a first child node of said given node, and a third one of said pointers identifies a sibling node of said given node;

determining partial workloads from the linear array structure; and

performing parallel processing of said partial workloads.

2. The method of claim 1, wherein the data from said tree are stored in said data array using a Polish representation.

3. The method of any preceding claims, wherein said converting of the tree into a linear array structure comprises:

parsing said tree to obtain one or more parsed nodes;

initially setting a current index to zero; and

for each parsed node and for a current index in said data array;

copying the data associated with the parsed node into said data array at said current index;

setting a first reference array at the current index to point to the data array entry corresponding to the parent node of the parsed node in said tree;

if the parsed node has at least one child in the input tree, setting a second reference array at the current index to point to data array value at index (current index+1);

if the parsed node is a sibling to another node in the input tree and if said another node has an index k in the data array, setting a third reference array at index k to point to the data array value at index i; and

incrementing the current index by one.

4. The method of claim 1, wherein:

said determining partial workloads includes dividing the linear data array into equally sized data chunks; and

said performing parallel processing of the partial workload includes processing the data chunks in parallel.

5. The method of claim 1, wherein said determining partial workloads comprises determining lists of sub-trees from the linear array structure, each sub-tree representing a partial workload.

6. The method of claim 5, wherein said determining lists of sub-trees comprises:

defining a root structure representing a candidate sub-tree, said root structure being composed of four pointers pointing respectively to a data node into said data array and to three entries into said three reference arrays;

computing the size of said candidate sub-tree using a third reference array;

determining if the size of said sub-tree matches a predefined condition;

if the size of said sub-tree matches said predefined condition, adding the candidate sub-tree into said list of sub-trees;

setting root to point to its sibling using the third reference array; and

for each new value of root, performing the computing, determining and adding steps.

7. The method of claim 6, further comprising setting root to point to its first child using a second reference array if it is determined that said sub-tree does not match said predefined condition.

8. The method of claim 6, said computing of the size of the candidate sub-tree further comprising setting root to point to its parent sibling using a first reference array if it is determined that root does not have any siblings.

9. The method of claim 6, wherein said determining if the size of the sub-tree matches the predefined condition comprises comparing the size of said candidate sub-tree added to a number of nodes in said list of sub-trees with available space for partial workload.

10. The method of claim 6, wherein determining partial workload further includes queuing said list of sub-trees for processing.

11. A computer program product comprising a computer readable medium having encoded thereon computer program code that when executed of a data processing device performs the method of:

converting the tree into a linear array structure including a data array for storing the data of said tree and three reference arrays, wherein each entry in said data array corresponds to a given node in said tree and includes three pointers, with each of said three pointers pointing to a respective one of said three reference arrays, wherein a first one of said pointers identifies a parent node of said given node, a second one of said pointers identifies a first child node of said given node, and a third one of said pointers identifies a sibling node of said given node;

determining partial workloads from the linear array structure; and

performing parallel processing of said partial workloads.

12. The computer program product of claim 11, wherein the program code for performing said converting of the tree into a linear array structure comprises program code for:

parsing said tree to obtain one or more parsed nodes;

initially setting a current index to zero; and

for each parsed node and for a current index in said data array;

copying the data associated with the parsed node into said data array at said current index;

setting a first reference array at the current index to point to the data array entry corresponding to the parent node of the parsed node in said tree;

if the parsed node has at least one child in the input tree, setting a second reference array at the current index to point to data array value at index (current index+1);

if the parsed node is a sibling to another node in the input tree and if said another node has an index k in the data array, setting a third reference array at index k to point to the data array value at index i; and

incrementing the current index by one.

13. The computer program product of claim 11, wherein:

said program code that performs the determining partial workloads includes program code for dividing the linear data array into equally sized data chunks; and

said program code that performs the parallel processing of the partial workload includes program code for processing the data chunks in parallel.

14. The computer program product of claim 11, wherein said program code that perform the determining partial workloads comprises program code that also perform determining lists of sub-trees from the linear array structure, each sub-tree representing a partial workload, wherein said determining lists of sub-trees comprises:

defining a root structure representing a candidate sub-tree, said root structure being composed of four pointers pointing respectively to a data node into said data array and to three entries into said three reference arrays;

computing the size of said candidate sub-tree using a third reference array;

determining if the size of said sub-tree matches a predefined condition;

if the size of said sub-tree matches said predefined condition, adding the candidate sub-tree into said list of sub-trees;

setting root to point to its sibling using the third reference array; and

for each new value of root, performing the computing, determining and adding steps.

15. The computer program product of claim 14, wherein:

the program code for further comprise program code for performing the following functions;

setting root to point to its first child using a second reference array if it is determined that said sub-tree does not match said predefined condition; and

setting root to point to its parent sibling using a first reference array if it is determined that root does not have any siblings;

said determining if the size of the sub-tree matches the predefined condition comprises comparing the size of said candidate sub-tree added to a number of nodes in said list of sub-trees with available space for partial workload; and

said determining partial workload further includes queuing said list of sub-trees for processing.

16. A data processing system comprising:

a processor;

a storage coupled to the processor; and

program code that executes on the processor to perform the following functions;

converting the tree into a linear array structure including a data array for storing the data of said tree and three reference arrays, wherein each entry in said data array corresponds to a given node in said tree and includes three pointers, with each of said three pointers pointing to a respective one of said three reference arrays, wherein a first one of said pointers identifies a parent node of said given node, a second one of said pointers identifies a first child node of said given node, and a third one of said pointers identifies a sibling node of said given node;

determining partial workloads from the linear array structure; and

performing parallel processing of said partial workloads.

17. The data processing system of claim 16, wherein the program code for performing said converting of the tree into a linear array structure comprises program code for:

parsing said tree to obtain one or more parsed nodes;

initially setting a current index to zero; and

for each parsed node and for a current index in said data array;

copying the data associated with the parsed node into said data array at said current index;

setting a first reference array at the current index to point to the data array entry corresponding to the parent node of the parsed node in said tree;

if the parsed node has at least one child in the input tree, setting a second reference array at the current index to point to data array value at index (current index+1);

if the parsed node is a sibling to another node in the input tree and if said another node has an index k in the data array, setting a third reference array at index k to point to the data array value at index i; and

incrementing the current index by one.

18. The data processing of claim 16, wherein:

said program code that performs the determining partial workloads includes program code for dividing the linear data array into equally sized data chunks; and

said program code that performs the parallel processing of the partial workload includes program code for processing the data chunks in parallel.

19. The data processing system of claim 16, wherein said program code that perform the determining partial workloads comprises program code that also perform determining lists of sub-trees from the linear array structure, each sub-tree representing a partial workload, wherein said determining lists of sub-trees comprises:

defining a root structure representing a candidate sub-tree, said root structure being composed of four pointers pointing respectively to a data node into said data array and to three entries into said three reference arrays;

computing the size of said candidate sub-tree using a third reference array;

determining if the size of said sub-tree matches a predefined condition;

if the size of said sub-tree matches said predefined condition, adding the candidate sub-tree into said list of sub-trees;

setting root to point to its sibling using the third reference array; and

for each new value of root, performing the computing, determining and adding steps.

20. The data processing system of claim 19, wherein:

the program code for further comprise program code for performing the following functions;

setting root to point to its first child using a second reference array if it is determined that said sub-tree does not match said predefined condition; and

setting root to point to its parent sibling using a first reference array if it is determined that root does not have any siblings;

said determining if the size of the sub-tree matches the predefined condition comprises comparing the size of said candidate sub-tree added to a number of nodes in said list of sub-trees with available space for partial workload; and

said determining partial workload further includes queuing said list of sub-trees for processing.