System for integrating task and data parallelism in dynamic applications

• US 6,480,876 B2
• Filed: 05/28/1998
• Issued: 11/12/2002
• Est. Priority Date: 05/28/1998
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Compaq Information Technologies Group LP (HP Inc.)
• Inventors: Ramachandran, Umakishore, Nikhil, Rishiyur S., Knobe, Kathleen, Rehg, James Mathew
• Primary Examiner(s): Courtenay, III, St. John
• Assistant Examiner(s): Nguyen, Van H.
• Application Number:
  US09/085,795
• Publication Number:
  US 20020091747A1
• Time in Patent Office: 1,629 Days
• Field of Search: 709/100-108, 709/310-400, 709/231, 709/215, 713/400
• US Class Current: 718/100
• 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 for integrating task and data parallelism in a dynamic application that includes at least one task for processing an input data stream to produce an output data stream replaces the at least one task with the following components. A splitter task for partitioning the input data stream into a plurality of data chunks. A plurality of worker tasks for processing subsets of the data chunks, each worker task being an instance of the at least one task, and a joiner task combining the processed data chunks to produce the output data stream.

Claims

1. A system for integrating task and data parallelism for a dynamic application including at least one task for real-time processing of a continuous input data stream to produce an output data stream, comprising:

a splitter task partitioning the input data stream into a plurality of individually marked data chunks;

a work queue storing the data chunks;

a variable number of worker tasks processing subsets of the data chunks from the work queue, each worker task being an instance of the at least one task;

a controller queue storing a control item for each data chunk, the control item including task and data strategy provided by the splitter task; and

a joiner task combining the processed data chunks dependent on the control items on the controller queue to produce the output data stream.

2. The system of claim 1 wherein the plurality of data chunks are continuous and time-varying data of the input and output data streams.

3. The system of claim 2 wherein each data chunk includes at least part of one data item, and means for temporally ordering the data items in the input and output data streams using time-stamp values.

4. The system of claim 3 wherein each data stream corresponds to a spatially ordered memory port.

5. The system of claim 4 including means for accessing the data items using space coordinates of the ports and time coordinates of the data items.

6. The system of claim 1 wherein the input data stream is a sequence of time-ordered video frames.

7. The system of claim 6 wherein each data chunk is a portion of one of the video frames of the sequence.

8. The system of claim 2 including means for dynamically varying the number of worker tasks over time.

9. The system of claim 1 including means for associating the task and data parallel strategy with each chunk.

10. The system of claim 9 wherein each task and data parallel strategy includes methods for processing the associated chunk.

11. The system of claim 10 wherein the methods include the worker tasks.

12. The system of claim 1 including means for learning and applying a task and data parallel strategy to the application.

13. The system of claim 12 including a controller measuring an execution of the application to generate an action space representing a task and data parallel strategy;

and

a run-time system applying the action space to implement the task and data parallel strategy.

14. A method for integrating task and data parallelism for a dynamic application including at least one task for real-time processing of continuous input data stream to produce an output data stream, comprising the steps of:

splitting the input data stream into a plurality of individually marked data chunks by a splitter;

storing the data chunks in a work queue;

processing subsets of the data chunks by a variable number of worker tasks, each worker task being an instance of the at least one task;

storing a control item for each data chunk in a controller queue, the control item including task and a data strategy provided by the splitter task; and

combining the processed data chunks by a joiner task dependent on the control items on the controller queue to produce the output data stream.