Parametric Analysis for Adaptive Computation Offloading

Motivation:

Computation offloading has shown to be effective to improve performance and conserve energy consumption. This requires optimal partitioning of the program to run across mobile and cloud. This paper focuses on effective partitioning of computation using parametric analysis to reduce execution cost.

Main points:

• The program is split into tasks and then they are scheduled to execute either in mobile or cloud. At a particular point of time, only one task executes in the system. After execution, task communicates to following task using message passing.
• Tasks are just consecutive statements which will start with a header and end with a task branch.These tasks are represented as graphs called task control flow graph (TCFG) representing the branches in execution.
• A new method called data validity states is used to represent the network communication cost ignoring redundant data communication cost. To represent the data flow across the program during run time, a approach called memory abstraction is used. It uses finite set of typed abstract memory for locations accessed in run time.
• Task assignment is performed based on semantic, data validity state and data access constraints. The tasks are associated with costs based on computation, communication, task scheduling and data registration. These constraints are optimized for by representing them as optimization problem to partition the tasks.
• Then the graph is split across mobile nodes and cloud by solving using graph min cut problem. Program analysis and running min cut algorithm is run offline as they are costly operations.
• Programs are run for range of parameters to find the execution cost and communication cost for program analysis.

Positives :

• This method does not require programmer involvement to partition the program. This dynamic approach gives better partitioning for different mobile configurations.
• Tasks are not just methods as in other approaches like MAUI and CloneCloud which gives better flexibility in partitioning.
• The paper has given careful considerations to remove network cost due to redundant data flow and also allows user annotations for better accuracy and flexibility.

Trade offs:

• Task execution in one system blocks other tasks. Sometimes it may not be suitable in circumstances like waiting on user input.
• Execution cost may vary for different loop execution based on parameters. Those are some limitations when using profiling for program analysis.