Parametric analysis for adaptive computation offloading

ABSTRACT

Many programs can be invoked under different execution options, input parameters and data files. Such different execution contexts may lead to strikingly different execution instances. The optimal code generation may be sensitive to the execution instances. In this paper, we show how to use parametric program analysis to deal with this issue for the optimization problem of computation offloading.Computation offloading has been shown to be an effective way to improve performance and energy saving on mobile devices. Optimal program partitioning for computation offloading depends on the tradeoff between the computation workload and the communication cost. The computation workload and communication requirement may change with different execution instances. Optimal decisions on program partitioning must be made at run time when sufficient information about workload and communication requirement becomes available.Our cost analysis obtains program computation workload and communication cost expressed as functions of run-time parameters, and our parametric partitioning algorithm finds the optimal program partitioning corresponding to different ranges of run-time parameters. At run time, the transformed program self-schedules its tasks on either the mobile device or the server, based on the optimal program partitioning that corresponds to the current values of run-time parameters. Experimental results on an HP IPAQ handheld device show that different run-time parameters can lead to quite different program partitioning decisions.

REFERENCES

• 1: L. O. Andersen. Program analysis and specialization for the C programming language. PhD thesis, DIKU, University of Copenhagen, 1994.
• 2: J. Bang-Jensen and G. Gutin. Graphs: theory, algorithms, and applications. Springer-Verlag, London, 2001.
• 3: Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Wen-mei W. Hwu, Profile-guided automatic inline expansion for C programs, Software—Practice & Experience, v.22 n.5, p.349-369, May 1992 [doi>10.1002/spe.4380220502]
• 4: J. Engblom and A. Ermedahl. Modeling complex flows for worst-case execution time analysis. In Proc. of RTSS'00, 21st IEEE Real-Time Systems Symposium, 1998.
• 5: Thomas Fahringer, Efficient Symbolic Analysis for Parallelizing Compilers and Performance Estimators, The Journal of Supercomputing, v.12 n.3, p.227-252, May 1, 1998 [doi>10.1023/A:1008013906463]
• 6: P. Feautrier. Parametric integer programming. Operationnelle/Operations Research, 22:243--268, 1988.
• 7: Rajiv Gupta , David A. Berson , Jesse Z. Fang, Path Profile Guided Partial Redundancy Elimination Using Speculation, Proceedings of the 1998 International Conference on Computer Languages, p.230, May 14-16, 1998
• 8: P. Jansson and J. Jeuring. Polylib - a library of polytypic functions. In Informal Proceedings Workshop on Generic Programming (WGP'98), 1998.
• 9: U. Kermer, J. Hicks, and J. M. Rehg. A compilation framework for power and energy management on mobile computers . In 14th International Workshop on Parallel Computing (LCPC'01), August 2001.
• 10: Zhiyuan Li , Cheng Wang , Rong Xu, Computation offloading to save energy on handheld devices: a partition scheme, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502257]
• 11: Alexey Rudenko , Peter Reiher , Gerald J. Popek , Geoffrey H. Kuenning, Saving portable computer battery power through remote process execution, ACM SIGMOBILE Mobile Computing and Communications Review, v.2 n.1, p.19-26, January 1998 [doi>10.1145/584007.584008]
• 12: Haluk Topcuoglu , Salim Hariri , Min-You Wu, Task Scheduling Algorithms for Heterogeneous Processors, Proceedings of the Eighth Heterogeneous Computing Workshop, p.3, April 12-12, 1999
• 13: Peng Tu , David Padua, Gated SSA-based demand-driven symbolic analysis for parallelizing compilers, Proceedings of the 9th international conference on Supercomputing, p.414-423, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224648]
• 14: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation; Optimization

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance

Keywords:
adaptive optimization, computation offloading, distributed system, handheld devices, program analysis, program partitioning, program profiling, program transformation