Parallel execution of operations for a partitioned binary radix tree on a parallel computer

• US 7,779,016 B2
• Filed: 09/14/2006
• Issued: 08/17/2010
• Est. Priority Date: 09/14/2006
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lynam, Benjamin E., Archer, Charles J., Ricard, Gary R.
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): MUELLER, KURT A
• Application Number:
  US11/531,846
• Publication Number:
  US 20080126739A1
• Time in Patent Office: 1,433 Days
• Field of Search: None
• US Class Current: 707/755
• 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 previously established partitioned binary radix tree (‘

PBRT’

) on a parallel computer, the previously established PBRT comprising;

a plurality of logical pages that contain a plurality of entries in the previously established PBRT, each logical page included in a tier of the previously established 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 previously established 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 previously established PBRT;

processing in parallel, on the parallel computer, each logical page in each tier of the previously established 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 previously established 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 previously established 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 previously established 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 previously established 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 previously established 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 previously established 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 the computer memory computer program instructions configured to;

receive, in the parallel computer, an operational entry for the previously established PBRT, the previously established PBRT comprising a plurality of logical pages that contain a plurality of entries in the previously established PBRT, each logical page included in a tier of the previously established 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 previously established PBRT is composed of a subentry from each logical page on an entry path for the entry;

process in parallel, on the parallel computer, each logical page in each tier of the previously established 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

select 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 configured to:

configure each logical page of the previously established 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 configured to:

configure each logical page of the previously established PBRT on a different memory partition; and

map 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 previously established 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 previously established 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 previously established 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 previously established partitioned binary radix tree on a parallel computer, the computer program product:

disposed upon a recordable medium for machine-readable information and comprising computer program instructions configured to;

receive, in the parallel computer, an operational entry for the previously established PBRT, the previously established PBRT comprising a plurality of logical pages that contain a plurality of entries in the previously established PBRT, each logical page included in a tier of the previously established 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 previously established PBRT is composed of a subentry from each logical page on an entry path for the entry;

process in parallel, on the parallel computer, each logical page in each tier of the previously established 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

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

14. 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 configured to:

configure each logical page of the previously established PBRT on a different compute node in the operational group.

15. 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 configured to:

configure each logical page of the previously established PBRT on a different memory partition; and

map each processor to a different memory partition.

16. 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.

17. 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.

18. The computer program product of claim 13 wherein:

processing in parallel, on the parallel computer, each logical page in each tier of the previously established 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 previously established 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 previously established 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.