Method apparatus for scheduling tasks in repeated iterations in a digital data processing system having multiple processors
AssigneeDigital Equipment Corporation
InventorsWilliam Barabash, William S. Yerazunis
Life of this patent
Estimating the term…
Abstract
A task dispatch system for use in connection with a plurality of digital data processors for processing tasks. The task dispatch system maintains a task identification queue including a plurality of task identification entries defining a series of tasks to be processed during an iteration. A task dispatcher dispatches tasks to the processors in the order defined by the task identification queue. At the end of an iteration, the task dispatcher reorganizes the entries in the task identification queue so as to dispatch one or more tasks, which were completed last during an iteration, at the beginning of a subsequent iteration.
Claims51
A digital data processing system comprising:
- A. a plurality of digital data processors for processing a plurality of tasks;
- B. a task identification queue for storing a plurality of task identification entries arranged in an order, where each one of the plurality of task identification entries correspondingly represents one of the plurality of tasks, respectively;
- and
- C. a task dispatcher comprising means for sequentially dispatching the plurality of tasks to said plurality of digital data processors by sequentially referring to the plurality of task identification entries in the order that the plurality of task identification entries are arranged in said task identification queue to retrieve the plurality of tasks, and means for reordering the plurality of task identification entries in said task identification queue after all of the tasks represented by the plurality of task identification entries have been sequentially dispatched and processed so that a last one of the plurality of tasks to be processed has its representative one of the plurality of task identification entries placed at the beginning of said task identification queue.
A task dispatch system for use in connection with a plurality of digital data processors for processing tasks, where each one of the tasks can be processed more than once, the task dispatch system comprising:
- a task dispatcher for dispatching the tasks to the plurality of digital data processors;
- a task identification queue coupled to the task dispatcher, the task identification queue including a plurality of task identification entries, initially arranged in an initial predefined order, the order of the task identification queue used by the task dispatcher to determine which task is to be dispatched, each one of the plurality of task identification entries correspondingly representative of one of the tasks to be processed;
- and
- a dispatch order determining portion coupled to the task identification queue, the dispatch order determining portion including means for reorganizing the initial predefined order of the task identification queue at the end of an iteration through said task identification queue into a reorganized order, wherein an iteration comprises dispatching and processing every one of the tasks represented by the plurality of task identification entries in order, so that the task dispatcher dispatches a preselected number of tasks which completed processing at the end of an iteration, at the beginning of a subsequent iteration, wherein the tasks are dispatched by the task dispatcher in the reorganized order.
A method of operating a digital data processing system comprising a plurality of digital data processors, each for processing tasks, and a task dispatcher, comprising the steps of:
- (a) dispatching one task of a series of tasks by the task dispatcher to an available one of the plurality of digital data processors for processing, wherein the task being dispatched is determined according to a pre-selected order;
- (b) determining if each one of the tasks in the series of tasks has been dispatched;
- (c) repeating steps (a) and (b) until each one of the tasks in the series of tasks has been dispatched;
- (d) detecting a pre-selected number of last completed tasks, wherein a completed task is a task that has been dispatched for processing and the processing has been completed;
- (e) reorganizing the pre-selected order of the series of tasks so that the pre-selected number of last completed tasks are placed at the beginning of the reorganized order;
- and
- (f) repeating steps (a) to (c), wherein the reorganized order is used as the preselected order in step (a).
A digital data processing system comprising:
- A. a plurality of digital data processors for processing a plurality of task information;
- B. a queue for storing the task information in an order;
- and
- C. a task dispatcher for sequentially dispatching the task information to said plurality of digital data processors in the order that the task information is arranged in said queue, comprising
- means for storing task information in the queue;
- means for receiving task information from said plurality of digital data processors;
- means for placing task information at the beginning of the queue;
- means for detecting a last one of the task information to be processed;
- and
- means for reordering the task information in said queue after all task information has been processed so that a last one of the task information to be processed is placed at the beginning of said queue.
Dependencies are inferred from the claim text.