Parametric Analysis for Adaptive Computation Offloading

Save energy and Improve performance: Another computation offloading approach by Wang & Li @Purdue University 2004 

This paper focuses on solving program partitioning problem for programs whose execution instances are sensitive to input parameters and data files. Such programs optimal code partitioning depends on input parameters and can only be determined at run time. To deal with this issue paper presents a parametric program analysis to identify optimal partitioning corresponding to different ranges of run-time parameters. Though paper mainly focuses on minimizing the execution time rather than energy but it also argues that both are proportional to each other. 

What’s new about this approach ? 

• This method considers run time parameters for finding optimal program partitioning and hence can adapt according to different execution instances of the code.
•  Program is partition into smaller chunk of code called as task for offloading and defined at much finer grain than functions/methods. Task control flow graph (TCFG) of each program is then computed for representing the program flow execution . 
• Paper also introduces a new concept called “data validity states” for reducing the communication cost by identifying the redundant data transfer between client and server. 
• Paper presents a memory abstraction layout to maintain the data dependency under all possible program execution contexts. This is required as often times control and data flow information cannot be determined at compile time. 

Key Idea: Integrating input parameters in optimization problem. 

Divide the program into tasks. Relate cost factors with count and execution time for instructions executed in each task. Express instruction count and dynamically allocated size as a function of input parameters. Formalize an optimization problem and solve it. 

How does it work ? 

An optimization problem is formed for assigning tasks for offloading by considering four cost factors: computational cost, data communication cost, task scheduling cost and data registration cost. Their cost coefficients are then expressed in terms of run time parameters which further depend on the instruction execution count & time in a particular task.  Finally this problem is converted into a min-cut network flow problem. Now solving min-cut problem takes O(n³) and introduces an unacceptable run-time overhead. Thus paper statically solves the parametric min-cut network flow problem for all possible ranges of input parameters. 

How this approach is different than MAUI ?  

 

MAUI focuses on solving energy consumption of a device subject to latency constraints rather than execution time. Only “methods” can be offloaded. But here much fine grain of functions called tasks are defined for offloading process. MAUI does not consider run time parameters for program profiling but rather consider past behavior of a method as a predictor of future invocations.

Assumptions and Consequences ? 

Paper considers per-computed data transfer time which can vary dramatically for a mobile device and hence can yield non-optimal or only sub-optimal solutions. 

Considering different range of input parameters for pre-computing the optimal program partitioning can lead to different solutions. Paper does not explicitly address the problem of finding the range of input parameters.

No two tasks can run simultaneously on both client and server. A host has to send a message before server can perform computational and afterwards becomes passive in this process and vice-verse. Thus we lose the opportunity of increasing the performance in cases where two tasks are independent.