System and method for altering the work definitions in an iterative parallel opportunistic work stealing scheduler

A method, implemented in a computer system that includes a plurality of hardware processors, for scheduling a group of work units across a plurality of computerized worker processes, the method comprising:

• an act of instantiating a first worker process at a first hardware processor and instantiating a second worker process at a second hardware processor as part of a worker process pool, the first and second worker processes having no assigned work units upon instantiation;
• an act of adding a plurality of work units to a first definition of work units that are to be completed by the worker process pool, wherein the first definition of work units is structured such that the first definition may be altered by one or more worker processes;
• an act of assigning the first worker process to the first definition of work units, thereby causing the first worker process to initiate processing of work units that are in the first definition, wherein the first worker process is configured to process each work unit in the first definition until all work units in the first definition have been completed, and such that the first worker process initiates processing of the plurality of work units of the first definition, and wherein the first definition of work units is defined as a range of work units, such that the first worker proceeds sequentially through the range of work units from the beginning of the work units towards the end of the range of work units, and for at least two sequential work units in the first definition, the first worker process uses a result from a prior work unit of the at least two sequential work units to assist in processing of a next work unit of the at least two sequential work units;
• subsequent to initiating processing of the first definition of work units by the first worker process, an act of the second worker process determining that a second definition that is associated with the second worker process has no associated work units and that the second worker process therefore has no work units to process;
• based on the second worker process determining that the second worker process has no work units to process, an act of the second worker process stealing one or more work units from the first definition, including the second worker process modifying the first definition to remove one or more first work units from the first definition, resulting in an updated first definition, and causing the one or more first work units that were removed from the first definition to be added to the second definition for processing by the second worker process, wherein when the second worker process steals from the first definition the second worker process alters the first definition by truncating the range of work units by changing the end of the range of work units;
• subsequent to the second worker process stealing the one or more first work units from the first definition, an act of the first worker process using the updated first definition to determine that the first worker process has completed all work units that are associated with the first definition;
• and
• based on the first worker process determining that the first worker process has completed all work units that are associated with the first definition, an act of the first worker process stealing one or more work units from the second definition, including the first worker process modifying the second definition to remove one or more second work units from the second definition, resulting in an updated second definition, and causing the one or more second work units that were removed from the second definition to be added to the first definition for processing by the first worker process.

A computer system, comprising:

• a plurality of hardware processors;
• and
• one or more computer-readable media having stored thereon computer-executable instructions that, when executed by the one or more hardware processors, cause the computer system to schedule a group of work units across a plurality of computerized worker processes, including at least the following:
• instantiating a first worker process at a first hardware processor and instantiating a second worker process at a second hardware processor as part of a worker process pool, the first and second worker processes having no assigned work units upon instantiation;
• adding a plurality of work units to a first definition of work units that are to be completed by the worker process pool, wherein the first definition of work units is structured such that the first definition may be altered by one or more worker processes;
• assigning the first worker process to the first definition of work units, thereby causing the first worker process to initiate processing of work units that are in the first definition, wherein the first worker process is configured to process each work unit in the first definition until all work units in the first definition have been completed, and such that the first worker process initiates processing of the plurality of work units of the first definition, and wherein the first definition of work units is defined as a range of work units, such that the first worker proceeds sequentially through the range of work units from the beginning of the work units towards the end of the range of work units, and for at least two sequential work units in the first definition, the first worker process uses a result from a prior work unit of the at least two sequential work units to assist in processing of a next work unit of the at least two sequential work units;
• subsequent to initiating processing of the first definition of work units by the first worker process, the second worker process determining that a second definition that is associated with the second worker process has no associated work units and that the second worker process therefore has no work units to process;
• based on the second worker process determining that the second worker process has no work units to process, the second worker process stealing one or more work units from the first definition, including the second worker process modifying the first definition to remove one or more first work units from the first definition, resulting in an updated first definition, and causing the one or more first work units that were removed from the first definition to be added to the second definition for processing by the second worker process, wherein when the second worker process steals from the first definition the second worker process alters the first definition by truncating the range of work units by changing the end of the range of work units;
• subsequent to the second worker process stealing the one or more first work units from the first definition, the first worker process using the updated first definition to determine that the first worker process has completed all work units that are associated with the first definition;
• and
• based on the first worker process determining that the first worker process has completed all work units that are associated with the first definition, the first worker process stealing one or more work units from the second definition, including the first worker process modifying the second definition to remove one or more second work units from the second definition, resulting in an updated second definition, and causing the one or more second work units that were removed from the second definition to be added to the first definition for processing by the first worker process.