System for learning and applying integrated task and data parallel strategies in dynamic applications

• US 6,675,189 B2
• Filed: 05/28/1998
• Issued: 01/06/2004
• Est. Priority Date: 05/28/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (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/086,032
• Publication Number:
  US 20020091748A1
• Time in Patent Office: 2,049 Days
• Field of Search: 709/100, 709/102-107, 709/201, 709/231, 707/8, 707/10, 707/100
• US Class Current: 718/100
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

A system for learning and applying a task and data parallel strategy to an application that includes at least one task for processing an input data stream to produce an output data stream includes the following components. A controller measuring an execution of the application to generate an action space representing a task and data parallel strategy. A run-time system applying the action space to implement the task and data parallel strategy.

Claims

1. A system for learning and applying a task and data parallel strategy to an application including at least one task for processing a continuous input data stream to produce an output data stream, comprising:

a controller measuring an execution of the application to update an evaluation of an action space representing a task and data parallel strategy for processing the continuous input data stream, the action space including an action vector, the action vector including a data parallel parameter for each task of the application; and

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

2. The system of claim 1 wherein the controller measures application and system states during the execution of the application;

a modeling task which forms a model of the application and system states;

an exploration task which explores the model for particular application and system states; and

a control policy for generating the action space.

3. The system of claim 1 wherein the application includes interacting tasks and data parallel tasks.

4. The system of claim 2 wherein the controller includes means for modeling the application and system states and means for exploring the model for particular application and system states, and a control policy for generating the action space.

5. The system of claim 4 wherein the modeling task uses a forward model expressed as (q, a)→

g where q denotes particular states, a denotes the action vector, and g denotes a goal vector.

6. The system of claim 1 wherein the run-time system includes;

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

a plurality of worker tasks 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 from the at least one task using the task and data parallel strategy.

7. A method for learning and applying a task and data parallel strategy to an application including at least one task for processing a continuous input data stream to produce an output data stream, comprising the steps of:

measuring, by a controller an execution of the application to update an evaluation of an action space representing a task and data parallel strategy for processing the continuous input data stream, the action space including an action vector, the action vector including a data parallel parameter for each task of the application; and

applying, by a run-time system the action space as newly evaluated to implement the task and data parallel strategy.

8. The method of claim 7 wherein the step of measuring measures application and system states during the execution of the application.

9. The method of claim 7 wherein the application includes interacting tasks and data parallel tasks.

10. The method of claim 8 wherein the step of measuring includes the steps of:

modeling the application and system states;

exploring the model for particular application and system states; and

generating the action space using a control policy.

11. The method of claim 10 wherein the step of modeling uses a forward model expressed as (q, a)→

g where q denotes particular states, a denotes the action vector, and g denotes a goal vector.

12. The method of claim 7 wherein the step of applying includes the steps of:

partitioning the input data stream into a plurality of data chunks;

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

combining, by a joiner task, the processed data chunks to produce the output data stream from the at least one task using the task and data parallel strategy.

13. A system for learning and applying a task and data parallel strategy to an application including at least one task for processing a continuous input data stream to produce an output data stream, comprising:

means for measuring an execution of the application to update an evaluation of an action space representing a task and data parallel strategy for processing the continuous input data stream, the action space including an action vector, the action vector including a data parallel parameter for each task of the application; and

means for applying the action space as newly evaluated to implement the task and data parallel strategy.