Parallel Execution of Operations for a Partitioned Binary Radix Tree on a Parallel Computer

• US 20080126739A1
• Filed: 09/14/2006
• Published: 05/29/2008
• Est. Priority Date: 09/14/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Archer, Charles J., Ricard, Gary R., Lynam, Benjamin E.
• Granted Patent: US 7,779,016 B2
• Time in Patent Office: Days
• US Class Current: 711/173
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

Methods, apparatus, and products are disclosed for parallel execution of operations for a partitioned binary radix tree that include: receiving, in a parallel computer, an operational entry for the PBRT, the PBRT comprising a plurality of logical pages that contain a plurality of entries, each logical page included in a tier and containing one or more subentries corresponding to the tier of the logical page containing the subentry, each entry is composed of a subentry from each logical page on an entry path; processing in parallel, on the parallel computer, each logical page in each tier, including: identifying a portion of the operational entry that corresponds to the tier of the logical page, and performing an operation on the logical page in dependence upon the identified portion of the operational entry for the tier; and selecting operation results from the logical pages on the entry path for the operational entry.

Claims

1. A method of parallel execution of operations for a partitioned binary radix tree (‘

PBRT’

) on a parallel computer,

the PBRT comprising a plurality of logical pages that contain a plurality of entries in the PBRT, each logical page included in a tier of the PBRT and containing one or more subentries represented by a plurality of radix nodes organized as a sub tree on the logical page, each subentry is a portion of an entry that corresponds to the tier of the logical page containing the subentry, each entry in the PBRT is composed of a subentry from each logical page on an entry path for the entry, the method comprising;

receiving, in the parallel computer, an operational entry for the PBRT;

processing in parallel, on the parallel computer, each logical page in each tier of the PBRT, including;

identifying a portion of the operational entry that corresponds to the tier of the logical page, and

performing an operation on the logical page in dependence upon the identified portion of the operational entry for the tier; and

selecting operation results from the logical pages on the entry path for the operational entry.

2. The method of claim 1 wherein the parallel computer further comprises a plurality of compute nodes, the compute nodes organized into at least one operational group of compute nodes for collective parallel operations on the parallel computer, the method further comprising:

configuring each logical page of the PBRT on a different compute node in the operational group.

3. The method of claim 1 wherein the parallel computer further comprises a plurality of computer processors and shared computer memory accessible to the plurality of computer processors, the shared computer memory partitioned into a plurality of memory partitions, the method further comprising:

configuring each logical page of the PBRT on a different memory partition; and

mapping each processor to a different memory partition.

4. The method of claim 1 wherein:

performing an operation on the logical page in dependence upon the identified portion of the operational entry for the tier further comprises searching the logical page for a subentry that matches the identified portion of the operational entry for the tier by traversing the radix nodes of the logical page; and

selecting operation results from the logical pages on the entry path for the operational entry further comprises selecting, from the logical pages having a subentry that matches the identified portion of the operational entry, search results from the logical pages on the entry path for the operational entry.

5. The method of claim 1 wherein:

performing an operation on the logical page in dependence upon the identified portion of the operational entry for the tier further comprises inserting into the logical page a subentry that matches the identified portion of the operational entry for the tier by modifying logical connections among radix nodes of the logical page; and

selecting operation results from the logical pages on the entry path for the operational entry further comprises discarding the insertions into the logical pages not on the entry path for the operational entry.

6. The method of claim 1 wherein:

processing in parallel, on the parallel computer, each logical page in each tier of the PBRT further comprises determining whether a subentry that matches the identified portion of the operational entry for the tier is comprised in more than one entry of the PBRT;

performing an operation on the logical page in dependence upon the identified portion of the operational entry for the tier further comprises deleting from the logical page a subentry that matches the identified portion of the operational entry for the tier by modifying logical connections among radix nodes of the logical page if the subentry that matches the identified portion of the operational entry for the tier is not comprised in more than one entry of the PBRT; and

selecting operation results from the logical pages on the entry path for the operational entry further comprises discarding the deletions from the logical pages not on the entry path for the operational entry.

7. A parallel computer for parallel execution of operations for a partitioned binary radix tree, the parallel computer comprising a computer processor, a computer memory operatively coupled to the computer processor, the computer memory having disposed within it computer program instructions capable of:

receiving, in the parallel computer, an operational entry for the PBRT, the PBRT comprising a plurality of logical pages that contain a plurality of entries in the PBRT, each logical page included in a tier of the PBRT and containing one or more subentries represented by a plurality of radix nodes organized as a sub tree on the logical page, each subentry is a portion of an entry that corresponds to the tier of the logical page containing the subentry, each entry in the PBRT is composed of a subentry from each logical page on an entry path for the entry;

processing in parallel, on the parallel computer, each logical page in each tier of the PBRT, including;

identifying a portion of the operational entry that corresponds to the tier of the logical page, and

performing an operation on the logical page in dependence upon the identified portion of the operational entry for the tier; and

selecting operation results from the logical pages on the entry path for the operational entry.

8. The parallel computer of claim 7 wherein the parallel computer further comprises a plurality of compute nodes, the compute nodes organized into at least one operational group of compute nodes for collective parallel operations on the parallel computer, the parallel computer further comprising computer program instructions capable of:

configuring each logical page of the PBRT on a different compute node in the operational group.

9. The parallel computer of claim 7 wherein the parallel computer further comprises a plurality of computer processors and shared computer memory accessible to the plurality of computer processors, the shared computer memory partitioned into a plurality of memory partitions, the parallel computer further comprising computer program instructions capable of:

configuring each logical page of the PBRT on a different memory partition; and

mapping each processor to a different memory partition.

10. The parallel computer of claim 7 wherein:

performing an operation on the logical page in dependence upon the identified portion of the operational entry for the tier further comprises searching the logical page for a subentry that matches the identified portion of the operational entry for the tier by traversing the radix nodes of the logical page; and

selecting operation results from the logical pages on the entry path for the operational entry further comprises selecting, from the logical pages having a subentry that matches the identified portion of the operational entry, search results from the logical pages on the entry path for the operational entry.

11. The parallel computer of claim 7 wherein:

performing an operation on the logical page in dependence upon the identified portion of the operational entry for the tier further comprises inserting into the logical page a subentry that matches the identified portion of the operational entry for the tier by modifying logical connections among radix nodes of the logical page; and

selecting operation results from the logical pages on the entry path for the operational entry further comprises discarding the insertions into the logical pages not on the entry path for the operational entry.

12. The parallel computer of claim 7 wherein:

processing in parallel, on the parallel computer, each logical page in each tier of the PBRT further comprises determining whether a subentry that matches the identified portion of the operational entry for the tier is comprised in more than one entry of the PBRT;

performing an operation on the logical page in dependence upon the identified portion of the operational entry for the tier further comprises deleting from the logical page a subentry that matches the identified portion of the operational entry for the tier by modifying logical connections among radix nodes of the logical page if the subentry that matches the identified portion of the operational entry for the tier is not comprised in more than one entry of the PBRT; and

selecting operation results from the logical pages on the entry path for the operational entry further comprises discarding the deletions from the logical pages not on the entry path for the operational entry.

13. A computer program product for parallel execution of operations for a partitioned binary radix tree on a parallel computer, the computer program product disposed upon a signal bearing medium, the computer program product comprising computer program instructions capable of:

receiving, in the parallel computer, an operational entry for the PBRT, the PBRT comprising a plurality of logical pages that contain a plurality of entries in the PBRT, each logical page included in a tier of the PBRT and containing one or more subentries represented by a plurality of radix nodes organized as a sub tree on the logical page, each subentry is a portion of an entry that corresponds to the tier of the logical page containing the subentry, each entry in the PBRT is composed of a subentry from each logical page on an entry path for the entry;

processing in parallel, on the parallel computer, each logical page in each tier of the PBRT, including;

identifying a portion of the operational entry that corresponds to the tier of the logical page, and

performing an operation on the logical page in dependence upon the identified portion of the operational entry for the tier; and

selecting operation results from the logical pages on the entry path for the operational entry.

14. The computer program product of claim 13 wherein the signal bearing medium comprises a recordable medium.

15. The computer program product of claim 13 wherein the signal bearing medium comprises a transmission medium.

16. The computer program product of claim 13 wherein the parallel computer further comprises a plurality of compute nodes, the compute nodes organized into at least one operational group of compute nodes for collective parallel operations on the parallel computer, the parallel computer further comprising computer program instructions capable of:

configuring each logical page of the PBRT on a different compute node in the operational group.

17. The computer program product of claim 13 wherein the parallel computer further comprises a plurality of computer processors and shared computer memory accessible to the plurality of computer processors, the shared computer memory partitioned into a plurality of memory partitions, the parallel computer further comprising computer program instructions capable of:

configuring each logical page of the PBRT on a different memory partition; and

mapping each processor to a different memory partition.

18. The computer program product of claim 13 wherein:

performing an operation on the logical page in dependence upon the identified portion of the operational entry for the tier further comprises searching the logical page for a subentry that matches the identified portion of the operational entry for the tier by traversing the radix nodes of the logical page; and

selecting operation results from the logical pages on the entry path for the operational entry further comprises selecting, from the logical pages having a subentry that matches the identified portion of the operational entry, search results from the logical pages on the entry path for the operational entry.

19. The computer program product of claim 13 wherein:

performing an operation on the logical page in dependence upon the identified portion of the operational entry for the tier further comprises inserting into the logical page a subentry that matches the identified portion of the operational entry for the tier by modifying logical connections among radix nodes of the logical page; and

selecting operation results from the logical pages on the entry path for the operational entry further comprises discarding the insertions into the logical pages not on the entry path for the operational entry.

20. The computer program product of claim 13 wherein:

processing in parallel, on the parallel computer, each logical page in each tier of the PBRT further comprises determining whether a subentry that matches the identified portion of the operational entry for the tier is comprised in more than one entry of the PBRT;

performing an operation on the logical page in dependence upon the identified portion of the operational entry for the tier further comprises deleting from the logical page a subentry that matches the identified portion of the operational entry for the tier by modifying logical connections among radix nodes of the logical page if the subentry that matches the identified portion of the operational entry for the tier is not comprised in more than one entry of the PBRT; and

selecting operation results from the logical pages on the entry path for the operational entry further comprises discarding the deletions from the logical pages not on the entry path for the operational entry.