APPARATUS AND METHOD IN A MULTIPLE OPERAND STREAM COMPUTING SYSTEM FOR IDENTIFYING THE SPECIFICATION OF MULTITASKS SITUATIONS AND CONTROLLING THE EXECUTION THEREOF

• US 3,614,745 A
• Filed: 09/15/1969
• Issued: 10/19/1971
• Est. Priority Date: 09/15/1969
• Status: Expired due to Term

• Current Assignee: Albert Podvin, Michael J. Flynn
• Original Assignee: Albert Podvin, Michael J. Flynn
• Inventors: Podvin, Albert, Flynn, Michael J.
• Primary Examiner(s): Shaw, Gareth D.
• Application Number:
  US04/858,022
• Time in Patent Office: 764 Days
• Field of Search: 340/172.5 235/157
• US Class Current: 718/104
• CPC Class Codes: G06F 15/161 Computing infrastructure, e.g. computer clusters, blade chassis or hardware partitioning casings, cabinets, racks or drawers for data centers H05K5/00
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
• CPC Class Codes: G06F 9/38 Concurrent instruction execution, e.g. pipeline or look ahead
• CPC Class Codes: G06F 9/3854 Instruction completion, e.g. retiring, committing or graduating
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

A system is described, useful in a multiple operand stream, or parallel, data processing system, for detecting the specification of independent tasks which can be operated upon in parallel. The specification of the independent parallel operable tasks is given by a fork instruction specifying the number of tasks and the physical or logical function to be performed for the task. A fork point can therefore be visualized as a logical node point where a given class of physical or logical tasks is undertaken. There is control apparatus associated with each node point. The control apparatus is a resource distributor-manager and also a controller into which each system resource reports when it has become free from whatever other task it was performing. The control apparatus dynamically allocates resources to the tasks in the fork on an as-available basis. The fork ends at a join point where data from the parallel tasks is coordinated. In one embodiment, the processor which initiated the fork may reach the join point, and apparatus is provided which gives this processor the options to wait for all tasks to be completed and coordinate data itself; to become one of the fork processors and help out by taking on an undistributed task, if one or more tasks remain undistributed; or to abort, for example under priority interrupt, and go to another job leaving the data to be coordinated by another processor in the system. The control apparatus includes subsystems, each comprising first and second queueing means, the first queueing means for queueing fork instructions as they are issued, and second queueing means for allowing the control of a plurality of fork instructions at a given time.

Claims

1. In a multiple-operand stream computing system wherein data processing tasks are designated as capable of being operated upon in parallel, the combination of:

a plurality of data processing elements, each for operating on a stream of instructions;

resource posting means responsive to said plurality of data processing elements for listing the status of each of said plurality of data processing elements;

means for detecting the occurrence, in a given one of said streams of instructions, of a group of data processing tasks which can be operated upon in parallel;

means associated with each data processing element and reSponsive to the detection of said occurrence, for issuing from the data processing element operating upon said given one of said streams of instructions, a request for data processing elements to operate upon individual ones of said tasks, said request having associated therewith an indication of the number of tasks awaiting distribution to individual ones of said plurality of data processing elements;

means responsive to said resource posting means for detecting free data processing elements;

means responsive to the detection of a free data processing element, for testing said indication of the number of tasks awaiting distribution;

means responsive to the detection of a least one awaiting task in said last-named test, for distributing one of said at least one awaiting tasks to said free data processing element;

a second and a third indication, associated with said request, for indicating the number of distributed but incompleted tasks in said group, and whether or not said issuing data processing element is retaining its status as the issuing data processing element, respectively;

means for decrementing said second indication each time a task is completed;

means responsive to said decrementing means for testing said second indication after each decrementation to determine whether the last task of said group is completed;

means responsive to the detection of the completion of said last task for testing said third indication to detect whether said data processing element issuing said request is retaining its status as the issuing data processing element;

means responsive to the detection of the condition that said issuing data processing element is retaining its status as the issuing date processing element for gating to said issuing data processing element an indication to coordinate data and continue processing instructions in said given one of said streams of instructions; and

means responsive to the detection in said last-named test that said issuing data processing element is not retaining its status as the issuing data processing element for gating to the processing element which completed the last task in said group, an indication to coordinate data and continue processing instructions in said given one of said streams of instructions.

2. In a multiple-operand stream computing system wherein data-processing tasks are designated as being capable of performance in parallel, the method of:

processing a given stream of instructions by an issuing data processor;

decoding, in said given stream of instructions, an indication that a plurality of data processing tasks of a particular type are capable of being operated upon in parallel;

decoding the type of task contained in said plurality;

issuing to a facility dedicated to said decoded type of task, a request for additional processors;

dynamically distributing tasks to data processors as each processor becomes available to process a task;

testing an indication to determine whether or not said issuing data processor is maintaining its status as said issuing data processor;

issuing, in response to the detection that said issuing processor is maintaining its status as the issuing processor, a signal to said issuing processor to coordinate data from said plurality of tasks and to continue processing instructions in said given instruction stream, after the final task in said group has been completed; and

issuing, in response to the determination that said issuing processor has not retained its status as the issuing processor, an indication to the processor which completed that final task in said plurality of tasks to coordinate data and continue processing instructions in said given stream of instructions.

3. A multiple instruction stream computing system wherein computational tasks are designated as being of a specific physical or logical function type, and further designated as being operable upon in parallel, the combination of:

a pluralitY of data processing elements, each for processing a respective stream of instructions, each said element individually dedicated to said specific physical and logical functions;

resource posting means responsive to said plurality of data processing elements for listing the status of each of said plurality of data processing elements;

means for detecting the occurrence in a given one of said streams of instructions, of a group of data processing tasks which can be operated upon in parallel. means for detecting the occurrence in said given one of said streams of instructions, the designation of the physical or logical function type of said tasks which can be operated upon in parallel;

means responsive to the detection of said occurrence for issuing from the data processing element operating upon said given one of said streams of instructions a request for data processing elements to operate upon individual ones of said tasks, said request having associated therewith an indication of the number of tasks awaiting distribution to requesting data processing elements;

means for scanning said resource posting elements for detecting free data processing elements dedicated to the same physical or logical function type as said tasks;

means responsive to the detection of a free data processing element for testing said indication of the number of tasks awaiting distribution;

means responsive to the detection of at least one awaiting task in said last-named test, for distributing one of said awaiting tasks to said free data processing element;

a second and third indication, associated with said request, for indicating the number of distributed but incompleted tasks in said group, and whether or not said issuing data processing element is retaining its status as the issuing data processing element, respectively;

means for decrementing said second indication each time a task is completed;

means responsive to said decrementing means for testing said second indication after decrementation to determine whether the last task of said group is completed;

means responsive to the detection of the completion of said last task for testing said third indication to detect whether the data processing element issuing said request is retaining its status as issuing data processing element;

means responsive to the detection of the condition that said issuing data processor is retaining its status as the issuing data processing element, for gating to said issuing data processing element an indication to coordinate data and continue processing instructions in said given one of said streams of instructions, and;

means responsive to the detection in said last-named test that said issuing data processing element is not retaining its status as the issuing data processing element, for gating to the processing element which completed the last task in said group, an indication to coordinate data and continue processing instructions in said given one of said streams of instructions.