Asynchronous Linked Data Structure Traversal

• US 20080263091A1
• Filed: 06/27/2008
• Published: 10/23/2008
• Est. Priority Date: 08/16/2005
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: International Business Machines Corporation
• Inventors: Nutter, Mark Richard, Day, Michael Norman, Aguilar, Maximino
• Granted Patent: US 7,984,075 B2
• Time in Patent Office: Days
• US Class Current: 707/103Y
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Asynchronously traversing a disjoint linked data structure is presented. A synergistic processing unit (SPU) includes a handler that works in conjunction with a memory flow controller (MFC) to traverse a disjoint linked data structure. The handler compares a search value with a node value, and provides the MFC with an effective address of the next node to traverse based upon the comparison. In turn, the MFC retrieves the corresponding node data from system memory and stores the node data in the SPU'"'"'s local storage area. The MFC stalls processing and sends an asynchronous event interrupt to the SPU which, as a result, instructs the handler to retrieve and compare the latest node data in the local storage area with the search value. The traversal continues until the handler matches the search value with a node value or until the handler determines a failed search.

Claims

1. A computer program product comprising:

a computer memory, the computer memory storing computer readable code, the computer readable code configured to;

identify a number of nodes to search in the linked data structure;

reserve a plurality of direct memory access list elements corresponding to the identified number of nodes in which to search, wherein each direct memory access list element includes a transfer size field and an effective address field;

store a parent node effective address in a first effective address field included in a first direct memory access list element;

set a first notification flag located in a first transfer size field included in the first direct memory access list element;

invoke a memory flow controller to retrieve parent node data located at the parent node effective address;

in response to the invoking, retrieve the parent node data by the memory flow controller;

store, by the memory flow controller, the parent node data in a first storage location;

receive an asynchronous event interrupt from the memory flow controller;

stall execution at the memory flow controller in response to detecting that the first notification flag is set;

retrieve the parent node data corresponding to the parent node effective address from the first storage location in response to receiving the asynchronous event interrupt, the parent node data included in the linked data structure;

determine whether a node value included in the parent node data matches a search value;

in response to determining that the node value included in the parent node data does not match the search value, store a child node effective address that corresponds to a second memory location in a second effective address field included in a second direct memory access list element included in the plurality of direct memory access list elements, the child node effective address included in the parent node data;

set a second notification flag that corresponds to the child node effective address, the second notification flag located in a second transfer size field included in the second direct memory access list element;

re-invoke the memory flow controller to retrieve child node data located at the child node effective address;

in response to the re-invoking, retrieve the child node data by the memory flow controller;

store, by the memory flow controller, the child node data in a second storage location; and

stall execution at the memory flow controller in response to detecting that the second notification flag is set.

2. The computer program product of claim 1 wherein the first memory location and the second memory location are disjoint and separately allocated in memory space.

3. The computer program product of claim 1 wherein the computer readable code is further configured to:

determine whether the node value is greater than or less than the search value;

wherein the child node effective address corresponds to a child node value that is less than the node value if it was determined that the search value is less than the node value; and

wherein the child node effective address corresponds to a child node value that is greater than the node value if it was determined that the search value is greater than the node value.

4. An information handling system comprising:

one or more processors;

a memory accessible by the processors;

one or more nonvolatile storage devices accessible by the processors; and

a traversing tool for traversing a linked data structure, the traversing tool being configured to;

identify a number of nodes to search in the linked data structure;

reserve a plurality of direct memory access list elements in the memory corresponding to the identified number of nodes in which to search, wherein each direct memory access list element includes a transfer size field and an effective address field;

store a parent node effective address in a first effective address field included in a first direct memory access list element;

set a first notification flag located in a first transfer size field included in the first direct memory access list element;

invoke a memory flow controller to retrieve parent node data located at the parent node effective address;

in response to the invoking, retrieve the parent node data by the memory flow controller;

store, by the memory flow controller, the parent node data in a first storage location;

receive an asynchronous event interrupt from the memory flow controller;

stall execution at the memory flow controller in response to detecting that the first notification flag is set;

retrieve the parent node data from one of the nonvolatile storage devices corresponding to the parent node effective address from the first storage location in response to receiving the asynchronous event interrupt, the parent node data included in the linked data structure;

determine whether a node value included in the parent node data matches a search value;

in response to determining that the node value included in the parent node data does not match the search value, store a child node effective address in the memory that corresponds to a second memory location in a second effective address field included in a second direct memory access list element included in the plurality of direct memory access list elements, the child node effective address included in the parent node data;

set a second notification flag that corresponds to the child node effective address, the second notification flag located in a second transfer size field included in the second direct memory access list element;

re-invoke the memory flow controller to retrieve child node data located at the child node effective address;

in response to the re-invoking, retrieve the child node data by the memory flow controller;

store, by the memory flow controller, the child node data in a second storage location; and

stall execution at the memory flow controller in response to detecting that the second notification flag is set.

5. The information handling system of claim 4 wherein the first memory location and the second memory location are disjoint and separately allocated in memory space.

6. The information handling system of claim 4 wherein the traversing tool is further configured to:

determine whether the node value is greater than or less than the search value;

wherein the child node effective address corresponds to a child node value that is less than the node value if it was determined that the search value is less than the node value; and

wherein the child node effective address corresponds to a child node value that is greater than the node value if it was determined that the search value is greater than the node value.