Online Migration Solver Based on Instructions Statistics

Yuanren Song, Zhijun LiLecture Notes in Computer Science 2014 · DOI · OpenAlex

Abstract

Mobile devices are perennially constrained by limited battery life and computing power. This paper presents a method for optimizing mobile application performance by intelligently offloading specific functions to the cloud. By modeling the problem using instruction counts and a "Function Invoking Tree" (FIT), the authors develop a dynamic programming approach that significantly reduces execution time. The proposed linear-time solver automates the decision-making process, achieving application speed-ups of up to 23x.

Introduction

While "cloud offloading"—sending heavy tasks to a powerful server—is a known solution, deciding exactly which functions to migrate remains a significant challenge. Existing systems often require manual code annotation or involve heavy virtual machine state migrations that are inefficient. This research addresses the need for an automated system that models costs accurately using instruction counts and handles complex call structures where a function's benefit from offloading depends on its specific context within the program execution flow.

Methodology

The authors build their solution on top of COMET, an open-source framework that uses Distributed Shared Memory (DSM) to migrate threads between a mobile device and a server.

The Function Invoking Tree (FIT) and DP Solver

The core of the model is the FIT, where each node represents a function call. This allows the system to treat the same function differently depending on its position in the execution flow. The optimization objective is to maximize "saved time," accounting for instruction length, relative CPU speeds, and synchronization overhead. Because the FIT lacks circular dependencies, the authors utilize a Dynamic Programming (DP) algorithm. This solver runs in $O(|V|)$ time, making it efficient enough for real-time, online decision-making.

Comparison of CPU speeds between the mobile device and the server across various instruction lengths.

Key Insights and Experimental Results

The system was evaluated using custom benchmarks: Matrix Multiplication, Seeking Primes (Sieve of Eratosthenes), and an IO Test. The hardware setup involved a mobile device with a speed of approximately 15 MB/s and a server reaching 110 MB/s.

The "First Migration" Penalty

A critical observation during testing was the "First Migration" penalty. Experimental data showed that the initial migration is always the most expensive because the entire memory state must be synchronized. Subsequent migrations of the same thread are significantly faster as only modified memory blocks are transmitted.

Running time comparison for matrix multiplication, highlighting the high initial cost of the first offload experiment.

Performance Benchmarks

  • Matrix Multiplication: Achieved an average speed-up of 7.11x.
  • Seeking Primes: Achieved the highest speed-up of 23.23x, as the task is highly computational with low memory synchronization requirements.
  • IO Test: Achieved an average speed-up of 8.24x when using optimal buffer sizes (approximately 10,000 bytes).

Discussion and Conclusion

The research identifies a $10^6$ byte threshold: for functions with fewer instructions, network Round Trip Time (RTT) typically outweighs offloading benefits. While the system is highly effective, it remains sensitive to network stability and currently does not support offloading for most native C/C++ functions. Future work may involve integrating more granular energy profiling to complement the instruction-based model, further refining the efficiency of the FIT solver for massive, modern applications.

Summary updated

BibTeX
@inproceedings{song2014online,
  author = {Yuanren Song and Zhijun Li},
  title = {{Online Migration Solver Based on Instructions Statistics}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2014},
  doi = {10.1007/978-3-662-44980-6\_4},
}
Figure