Process for dispatching tasks among multiple information processors

• US 5,109,512 A
• Filed: 05/31/1990
• Issued: 04/28/1992
• Est. Priority Date: 05/31/1990
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bahr, James E., Corrigan, Michael J., Knipfer, Diane L., McMahon, Lynn A., Metzger, Charlotte B.
• Primary Examiner(s): Heckler, Thomas M.
• Application Number:
  US07/531,178
• Time in Patent Office: 698 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 718/103
• CPC Class Codes: G06F 9/5033 considering data affinity

Abstract

In connection with an information processing network in which multiple processing devices have individual cache memories and also share a main storage memory, a process is disclosed for allocating multiple data operations or tasks for subsequent execution by the processing devices. A plurality of task dispatching elements (TDE) forming a task dispatching queue are scanned in an order of descending priority, for either a specific affinity to a selected one of the processing devices, or a general affinity to all of the processing devices. TDEs with specific affinity are assigned immediately if the selected processor is available, while TDEs of general affinity are reserved. TDEs with a specific affinity are bypassed if the selected processor is not available, or reserved if a predetermined bypass threshold has been reached. Following the primary scan a secondary scan, in an order of ascending priority, assigns any reserved tasks to the processing devices still available, without regard to processor affinity. Previously bypassed tasks can be assigned as well, in the event that any processor remains available. A further feature of the network is a means to reset the processor affinity of a selected task from the specific affinity to the general affinity. Resetting is accomplished through an assembly level instruction contained in the task, and either can be unconditional, with reset occurring whenever the task is executed on one of the processing devices, or can occur only upon the failure to meet a predetermined condition while the task is executing.

Claims

1. In an information processing network including a main memory having memory locations for storing bit-encoded data, a plurality of processing devices for manipulating bit-encoded data, and a main storage interface connected to the processing devices and to the main memory;

each of the processing devices having a cache memory including a plurality of cache locations for storing bit-encoded data, each processing device further including means for storing and retrieving bit-encoded data to and from the main storage memory via the main storage interface and means for storing and retrieving bit-encoded data to and from its associated cache memory;

said bit-encoded data including data operations, each of the data operations having priority indicia and having affinity indicia to indicate either a general affinity for at least two of the processing devices or a specific affinity for a selected one of the processing devices;

a process for associating each of the data operations with one of the processing devices for subsequent execution of the operation by the associated processing device, including the steps of;

(a) performing a primary scan of the data operations, including scanning the affinity indicia of each data operation for the presence of a specific affinity;

(b) for each of the data operations having a specific affinity for a selected one of the processing devices, either (i) assigning the data operation to the selected processing device if the processing device is available for such assignment, or (ii) bypassing the data operation in the event that a higher priority data operation has been assigned to the selected processing device;

(c) in the event that the data operation has a general affinity for the processing devices, proceeding to the data operation having the next highest priority;

(d) performing steps b and c until either all of the data operations have been assigned, or until each one of the processing devices has an associated one of the data operations assigned to it; and

(e) dispatching each assigned operation to its associated processing device.

2. The process of claim 1 wherein:

said general affinity is an affinity for all of the processing devices.

3. The process of claim 1 wherein said primary scan is performed in order of descending priority of said data operations, beginning with the one of said data operations having the highest priority.

4. The process of claim 1 including the further step of:

setting a bypass threshold prior to said primary scan and, after bypassing a number of the data operations equal to the bypass threshold, assigning each of the subsequently scanned data operations to any one of the processing devices to which a data operation has not yet been assigned, disregarding the specific affinity, if any, of said subsequently scanned operations, until one of the data operations has been assigned to each one of the processing devices.

5. The process of claim 4 wherein said subsequently scanned data operations having specific affinity for a processing device that was already assigned to another data operation is assigned a general affinity.

6. The process of claim 1 including the further steps of:

upon determining no specific affinity for a data operation being scanned, reserving the data operation for subsequent assignment to one of the processing devices;

counting the number of said data operations reserved for subsequent assignment and, responsive to determining that the number of reserved data operations equals the number of said processing devices to which no data operation has been assigned pursuant to step b, performing a secondary scan upon the previously scanned data operations; and

for each of the data operations reserved for subsequent assignment, assigning each said reserved data operations to one of the remaining available processing devices.

7. The process of claim 6 including the further step of:

following said assigning of each reserved data operation, and upon determining that at least one of the processing devices remains available for assignment of a data operation and that at least one of the previously scanned data operations was bypassed, further performing the secondary scan on each said bypassed data operation and assigning it to an available processing device, disregarding the specific affinity, until either (i) all of the processing devices have been assigned one of the data operations;

or (ii) all of the data operations have been assigned.

8. The process of claim 6 wherein:

said secondary scan is performed in an order of ascending priority of the data operations.

9. The process of claim 8 wherein:

said step of dispatching the data operations further includes modifying the affinity indicia of each dispatched data operation to exhibit the specific affinity for the processing device to which it is dispatched.

10. The process of claim 8 wherein:

the specific affinity, of each one of the data operations having a specific affinity, is based upon the one of said processing devices that most recently executed the data operation.

11. An information processing network including a main memory having memory locations for storing bit-encoded data, a plurality of processing devices, and a main storage interface connected to the processing devices and to the main memory;

each of the processing devices having a cache memory including a plurality of cache locations for storing bit-encoded data, each processing device further including means for storing and retrieving bit-encoded data to and from the main storage memory via the main storage interface, and means for storing and retrieving bit-encoded data to and from its associated cache memory;

said bit-encoded data including data operations comprising working data and program instructions, said processing devices using instruction streams of the program instructions to manipulate the working data, each said instruction stream comprising a plurality of the program instructions;

wherein the improvement comprises;

processor affinity indicia associated with each of the data operations and identifying the associated data operation as having either a general affinity for at least two of the processing devices, or a specific affinity for a selected one of the processing devices;

data operation allocation means for scanning a plurality of the data operations, and for associating each of the data operations with one of the processing devices for subsequent execution of the instruction stream by the associated processing device, the associating of each data operation being based at least in part upon the affinity indicia of the data operation;

a means for modifying the processor affinity indicia of each data operation, upon the associating of the data operation with one of the processing devices, to exhibit the specific affinity for the associated processing device; and

at least one processor affinity reset means, each affinity reset means being associated with a selected one of the instruction streams, for resetting the processor affinity indicia of the associated selected data operation to exhibit said general affinity as the associated processing device executes the selected instruction stream of the data operation.

12. The information processing network of claim 11 wherein:

each of the data operations includes a processor affinity field, and the processor affinity indicia of each data operation include a binary word in the affinity field.

13. The processing network of claim 12 wherein:

said reset means includes a reset instruction of the program instructions, the reset instruction being inserted into each of the selected instruction streams, said reset instruction, when its associated selected instruction stream is executed by the associated processing device, resetting the binary word in the associated processor affinity field to a value corresponding to said general affinity.

14. The processing network of claim 13 wherein:

said program instructions include a receive instruction and a send instruction in first and second ones of the instruction streams, respectively, for synchronizing the first and second data operations;

wherein the receive instruction when executed seeks a message that a predetermined condition is satisfied, and the send instruction when executed provides a message that the condition is satisfied; and

wherein the instruction stream of the first data operation, when executed, continues to execute if said message is detected when the receive instruction is executed, and the data operation is switched out of the associated processing device if the message is not detected when the receive instruction is executed; and

wherein the processor affinity field reset means includes a conditional reset means, associated with the instruction stream of the first data operation, for maintaining the specific affinity of the first data operation whenever the message is so detected, and for resetting the processor affinity field of the first data operation when the message is not so detected.

15. The information processing network of claim 14 wherein:

said conditional reset means comprises a binary flag within a field of the receive instruction, operable to cause said resetting only upon the failure to detect said message when the receive instruction is executed.

16. An information processing network including a main storage memory having memory locations for storing bit-encoded data, a plurality of processing devices, and a main storage interface connected to the processing devices and to the main memory;

each of the processing devices having a cache memory including a plurality of cache locations for storing bit-encoded data, each processing device further including means for storing and retrieving bit-encoded data to and from the main storage memory via the main storage interface, and means for storing and retrieving bit-encoded data to and from its associated cache memory;

said bit-encoded data including working data and program instructions, said processing devices using streams of the program instructions to manipulate working data, each of the streams comprising a plurality of the program instructions;

the programming instructions further including receive instructions and send instructions incorporated into first and second ones of the instruction streams, respectively, for synchronizing the first and second data operations, said receive instruction when executed seeking a message that a predetermined condition is satisfied, and said send instruction when executed providing the message that the condition is satisfied, wherein the first data operation continues to execute if the message is detected when the receive instruction is executed, and the first data operation is switched out of the associated processing device if the message is not detected when the receive instruction is executed;

wherein the improvement comprises;

processor affinity indicia associated with each of the data operations, to identify its associated data operation as having either a general affinity for at least two of the processing devices, or a specific affinity for only a selected one of the processing devices;

data operation allocation means for scanning a plurality of the data operations, and for associating each of the data operations with one of the processing devices for subsequent execution of the instruction stream of the data operation by the associated processing device, based at least in part upon the affinity indicia of the data operation;

a means for modifying the processor affinity indicia of each data operation to exhibit the specific affinity for the associated processing device with which the data operation is associated; and

a conditional reset means, associated with said receive instruction, for resetting the processor affinity indicia of the first data operation to exhibit said general affinity if said message is not detected when the receive instruction is executed, and for leaving the affinity indicia unchanged in the event that said message is detected when the receive instruction is executed.

17. The information processing network of claim 16 wherein:

each of the data operations includes a processor affinity field for binary data, and wherein the affinity indicia of each instruction stream include a binary word in the affinity field; and

wherein said conditional reset means includes a binary reset flag in a conditional reset field of the receive instruction, operable to reset the binary word in the processor affinity field of the first data operation only if the message is not detected when the receive instruction is executed.