Asynchronous linked data structure traversal
First Claim
1. A computer program product comprising:
- a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;
computer readable program code configured to identify a number of nodes to search in a linked data structure;
computer readable program code configured to 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;
computer readable program code configured to store a parent node effective address in a first effective address field included in a first direct memory access list element;
computer readable program code configured to set a first notification flag located in a first transfer size field included in the first direct memory access list element;
computer readable program code configured to invoke a memory flow controller to retrieve parent node data located at the parent node effective address;
computer readable program code configured to retrieve the parent node data by the memory flow controller in response to the invoking;
computer readable program code configured to store, by the memory flow controller, the parent node data in a first storage location;
computer readable program code configured to receive an asynchronous event interrupt from the memory flow controller;
computer readable program code configured to stall execution at the memory flow controller in response to detecting that the first notification flag is set;
computer readable program code configured to 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;
computer readable program code configured to determine whether a node value included in the parent node data matches a search value;
computer readable program code configured to 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 in response to determining that the node value included in the parent node data does not match the search value, the child node effective address included in the parent node data;
computer readable program code configured to 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;
computer readable program code configured to re-invoke the memory flow controller to retrieve child node data located at the child node effective address;
computer readable program code configured to retrieve the child node data by the memory flow controller in response to the re-invoking;
computer readable program code configured to store, by the memory flow controller, the child node data in a second storage location; and
computer readable program code configured to stall execution at the memory flow controller in response to detecting that the second notification flag is set.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
6 Claims
-
1. A computer program product comprising:
a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising; computer readable program code configured to identify a number of nodes to search in a linked data structure; computer readable program code configured to 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; computer readable program code configured to store a parent node effective address in a first effective address field included in a first direct memory access list element; computer readable program code configured to set a first notification flag located in a first transfer size field included in the first direct memory access list element; computer readable program code configured to invoke a memory flow controller to retrieve parent node data located at the parent node effective address; computer readable program code configured to retrieve the parent node data by the memory flow controller in response to the invoking; computer readable program code configured to store, by the memory flow controller, the parent node data in a first storage location; computer readable program code configured to receive an asynchronous event interrupt from the memory flow controller; computer readable program code configured to stall execution at the memory flow controller in response to detecting that the first notification flag is set; computer readable program code configured to 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; computer readable program code configured to determine whether a node value included in the parent node data matches a search value; computer readable program code configured to 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 in response to determining that the node value included in the parent node data does not match the search value, the child node effective address included in the parent node data; computer readable program code configured to 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; computer readable program code configured to re-invoke the memory flow controller to retrieve child node data located at the child node effective address; computer readable program code configured to retrieve the child node data by the memory flow controller in response to the re-invoking; computer readable program code configured to store, by the memory flow controller, the child node data in a second storage location; and computer readable program code configured to stall execution at the memory flow controller in response to detecting that the second notification flag is set. - View Dependent Claims (2, 3)
-
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. - View Dependent Claims (5, 6)
-
Specification