Concurrently processing parts of cells of a data structure with multiple processes

Patent metadata

Field	Value
Publication number	US-9501327-B2
Application number	US-201414277019-A
Country	US
Kind code	B2
Filing date	May 13, 2014
Priority date	May 13, 2014
Publication date	Nov 22, 2016
Grant date	Nov 22, 2016

Abstract

Provided are a computer program product, system, and method for concurrently processing parts of cells of a data structure with multiple processes. Information is provided to indicate a partitioning of the cells of the data structure into a plurality of parts, and having a cursor pointing to a cell in the part. Processes concurrently process different parts of the data structure by performing: determining from the cursor for the part one of the cells in the part to process; processing the cells from the cursor to determine whether to process the unit of work corresponding to the cell; and setting the cursor to identify one of the cells from which processing is to continue in a subsequent iteration in response to processing the units of work for a plurality of the processed cells.

First claim

What is claimed is:

1. A computer program product for processing a data structure having a plurality of cells, wherein each cell represents a unit of work to process, wherein the computer program product comprises a computer readable storage medium having program instructions embodied therewith, the program instructions that when executed by a processor perform operations, the operations comprising:
providing information to indicate a partitioning of the cells of the data structure into a plurality of parts, and having a cursor pointing to a cell in a part of the plurality of parts; and
concurrently processing, by processes, different parts of the data structure by performing:
determining, from the cursor for the part, one of the cells in the part to process;
processing the cells from the cursor to determine whether to process the unit of work corresponding to the cell; and
setting the cursor to identify one of the cells from which processing is to continue in a subsequent iteration in response to processing the units of work for a plurality of the processed cells.

2. The computer program product of claim 1 , wherein the processing of the unit of work corresponding to the cell comprises adding indication of the unit of work corresponding to the cell to a work list, wherein the work list is processed to perform the unit of work indicated in the work list.

3. The computer program product of claim 1 , wherein different processes process different cells of one of the parts, and wherein a subsequent process processing subsequent cells in one of the parts following a processing of previous cells uses the cursor to determine the subsequent cells to process.

4. The computer program product of claim 1 , wherein the operations further comprise:
for each of the parts, setting a processing flag to indicate that the part is not being processed;
setting, by one of the processes processing one of the parts, the processing flag to indicate that the part is being processed; and
setting, by one of the processes completing processing of the cells in one of the parts being processed, the processing flag to indicate that the part is not being processed.

5. The computer program product of claim 4 , wherein the operations further comprise:
determining, by one of the processes, the processing flag for one of the parts indicating that the part is not being processed, wherein the process sets the processing flag to indicate that the part is being processed in response to determining that the processing flag for the part indicates that the part is not being processed.

6. The computer program product of claim 1 , wherein the data structure comprises a bitmap, wherein each cell of the bitmap has one of a first value indicating to perform the unit of work represented by the cell and a second value indicating that there is no work to be performed for the cell, wherein the determining whether to perform the unit of work represented by the cell comprises determining whether the cell has the first value, wherein the operations further comprise:
setting the cell to the second value in response to processing the unit of work represented by the cell when the cell has the first value; and
processing a next cell in the part to determine whether the next cell has the first or second value in response to setting the cell to the second value or determining that a previously processed cell has the second value.

7. The computer program product of claim 1 , wherein the operations further comprise:
setting, by the process, the cursor to indicate that the part has been processed in response to processing a last cell in the part.

8. The computer program product of claim 1 , wherein the cells in each part are in a sequential ordering, wherein each of the parts comprise consecutively ordered cells according to the sequential ordering, and wherein the parts are processed in an order so as to process the cells in the data structure according to the sequential ordering.

9. A system for processing a data structure having a plurality of cells, wherein each cell represents a unit of work to process, comprising:
a processor; and
a computer readable storage medium having program instructions that when executed by the processor perform operations, the operations comprising:
providing information to indicate a partitioning of the cells of the data structure into a plurality of parts, and having a cursor pointing to a cell in a part of the plurality of parts; and
concurrently processing, by processes, different parts of the data structure by performing:
determining, from the cursor for the part, one of the cells in the part to process;
processing the cells from the cursor to determine whether to process the unit of work corresponding to the cell; and
setting the cursor to identify one of the cells from which processing is to continue in a subsequent iteration in response to processing the units of work for a plurality of the processed cells.

10. The system of claim 9 , wherein the processing of the unit of work corresponding to the cell comprises adding indication of the unit of work corresponding to the cell to a work list, wherein the work list is processed to perform the unit of work indicated in the work list.

11. The system of claim 9 , wherein different processes process different cells of one of the parts, and wherein a subsequent process processing subsequent cells in one of the parts following a processing of previous cells uses the cursor to determine the subsequent cells to process.

12. The system of claim 9 , wherein the operations further comprise:
for each of the parts, setting a processing flag to indicate that the part is not being processed;
setting, by one of the processes processing one of the parts, the processing flag to indicate that the part is being processed; and
setting, by one of the processes completing processing of the cells in one of the parts being processed, the processing flag to indicate that the part is not being processed.

13. The system of claim 12 , wherein the operations further comprise:
determining, by one of the processes, the processing flag for one of the parts indicating that the part is not being processed, wherein the process sets the processing flag to indicate that the part is being processed in response to determining that the processing flag for the part indicates that the part is not being processed.

14. The system of claim 9 , wherein the cells in each part are in a sequential ordering, wherein each of the parts comprise consecutively ordered cells according to the sequential ordering, and wherein the parts are processed in an order so as to process the cells in the data structure according to the sequential ordering.

15. A method for processing a data structure having a plurality of cells, wherein each cell represents a unit of work to process, comprising:
providing information to indicate a partitioning of the cells of the data structure into a plurality of parts, and having a cursor pointing to a cell in a part of the plurality of parts; and
concurrently processing, by processes, different parts of the data structure by performing:
determining, from the cursor for the part, one of the cells in the part to process;
processing the cells from the cursor to determine whether to process the unit of work corresponding to the cell; and
setting the cursor to identify one of the cells from which processing is to continue in a subsequent iteration in response to processing the units of work for a plurality of the processed cells.

16. The method of claim 15 , wherein the proc

Assignees

• IBM

Inventors

• Brown Theresa M
• Clayton Nicolas M
• Gupta Lokesh M
• Harris Jr Theodore T
• Hatfield Brian D
• Sanchez Matthew
• Schreiber David B

Classifications

• G06F16/90

  Details of database functions independent of the retrieved data types · CPC title

• G06F9/5066 Primary

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title

• G06F9/4843

  by program, e.g. task dispatcher, supervisor, operating system · CPC title

• G06F17/30943

  Physics · mapped topic