Hermes: Latency Optimal Task Assignment for Resource-constrained Mobile Computing
Top Cited Papers
- 8 March 2017
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. 16 (11), 3056-3069
- https://doi.org/10.1109/tmc.2017.2679712
Abstract
With mobile devices increasingly able to connect to cloud servers from anywhere, resource-constrained devices can potentially perform offloading of computational tasks to either save local resource usage or improve performance. It is of interest to find optimal assignments of tasks to local and remote devices that can take into account the application-specific profile, availability of computational resources, and link connectivity, and find a balance between energy consumption costs of mobile devices and latency for delay-sensitive applications. We formulate an NP-hard problem to minimize the application latency while meeting prescribed resource utilization constraints. Different from most of existing works that either rely on the integer programming solver, or on heuristics that offer no theoretical performance guarantees, we propose Hermes, a novel fully polynomial time approximation scheme (FPTAS). We identify for a subset of problem instances, where the application task graphs can be described as serial trees, Hermes provides a solution with latency no more than (1 + ε) times of the minimum while incurring complexity that is polynomial in problem size and 1/ε. We further propose an online algorithm to learn the unknown dynamic environment and guarantee that the performance gap compared to the optimal strategy is bounded by a logarithmic function with time. Evaluation is done by using real data set collected from several benchmarks, and is shown that Hermes improves the latency by 16 percent compared to a previously published heuristic and increases CPU computing time by only 0.4 percent of overall latency.Keywords
Funding Information
- General Motors Corporation
- Armenian National Science and Education Fund (CNS-1217260)
This publication has 30 references indexed in Scilit:
- Optimizing mobile computational offloading with delay constraintsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2014
- Deterministic Sequencing of Exploration and Exploitation for Multi-Armed Bandit ProblemsIEEE Journal of Selected Topics in Signal Processing, 2013
- A close examination of performance and power characteristics of 4G LTE networksPublished by Association for Computing Machinery (ACM) ,2012
- MAUIPublished by Association for Computing Machinery (ACM) ,2010
- Tight bound for matchingJournal of Combinatorial Optimization, 2010
- Predicting task execution time on handheld devices using the keystroke-level modelPublished by Association for Computing Machinery (ACM) ,2005
- Parametric analysis for adaptive computation offloadingACM SIGPLAN Notices, 2004
- A Polynomial Algorithm for the k-cut Problem for Fixed kMathematics of Operations Research, 1994
- An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on GraphsJournal of the ACM, 1976
- Reducibility among Combinatorial ProblemsPublished by Springer Science and Business Media LLC ,1972