Inter-layer per-mobile optimization of cloud mobile computing: A message-passing approach

Cloud mobile computing enables the offloading of computation-intensive applications from a mobile device to a cloud processor via a wireless interface. In light of the strong interplay between offloading decisions at the application-layer and physical-layer parameters, which determine the energy and latency associated with the mobile-cloud communication, this paper investigates the inter-layer optimization of fine-grained task offloading across both layers. In prior art, this problem was formulated, under a serial implementation of processing and communication, as a mixed integer program, entailing a complexity that is exponential in the number of tasks. In this work, instead, algorithmic solutions are proposed that leverage the structure of the call graphs of typical applications by means of message passing on the call graph, under both serial and parallel implementations of processing and communication. For call trees, the proposed solutions have a linear complexity in the number of tasks, and efficient extensions are presented for more general call graphs that include 'map'-type and 'reduce'-type tasks. Moreover, the proposed schemes are optimal for the serial implementation and provide principled heuristics for the parallel implementation. Extensive numerical results yield insights into the impact of inter-layer optimization and on the comparison of the two implementations.