Input-centric profiling and prediction for computational offloading of mobile applications

Relentless growth in mobile computing technologies continues to bring the vision of ubiquitous computing closer than ever before. As mobile hardware becomes more powerful and connected, user expectations of smartphones and tablets continue to push the boundaries of device capabilities. However, the inherent limitations of portability continue to impose constraints that are not present on traditional server platforms. The confluence of high-speed network connections and cloud compute services allows mobile applications to leverage cloud servers, in order to augment device capabilities and overcome the limitations of mobility. Computational offloading frameworks are a widely-researched tool for optimising the performance and resource use of mobile applications by exploiting the benefits of cloud computing. Offloading frameworks transparently facilitate the delegation of processing to remote servers, allowing mobile applications to utilise the power of cloud computing resources without imposing additional burden on developers. The improved performance and reduced energy use offered by computational offloading helps to mitigate the inherent limitations of mobile devices. Modern computational offloading frameworks facilitate dynamic offloading decisions that adapt to changing application and device conditions. Adaptive offloading is utilised to ensure that processing is always performed in the most efficient manner. To achieve this, offloading frameworks monitor the behaviour of the application and the state of the mobile device, and perform a cost-benefit analysis designed to produce optimal offloading decisions. The quality of these offloading decisions is dependant on the accuracy of the information used to produce them. Existing computational offloading frameworks fail to take into account the full influence of an application's input data on its behaviour. Changes in arbitrary input characteristics can result in dramatic changes in application behaviour. However, the overwhelming majority of existing offloading frameworks consider only the size of input data when making offloading decisions. Many frameworks model changes in application behaviour only indirectly through monitoring performance changes over time. This approach assumes a temporal pattern in input characteristics that is not guaranteed to exist, and cannot cleanly differentiate between changes in application behaviour and performance differences caused by changes in device state. Hardware power saving features implemented in modern mobile devices allow a given device to shift between a number of different system states. Each of these states results in different performance characteristics for mobile applications running on the device. The interactions between hardware components, the mobile operating system, and user-facing applications, result in performance variations that introduce noise into measurements of application performance. This interference is known as OS noise. Both changes in device state, and the presence of OS noise in performance measurements, must be taken into account by computational offloading frameworks in order to provide accurate information for making offloading decisions. The overall aim of this thesis is to develop a system for profiling and predicting the performance of mobile applications, that takes into account the influence of arbitrary input characteristics, whilst mitigating the effects of OS noise. This profiling and prediction system should be efficient enough to perform the frequent processing required in order to adapt to changes in device state, and produce accurate predictions of application performance that can be used by a computational offloading framework to make quality offloading decisions. This thesis focusses on five research objectives in order to address the identified gap in the existing literature. The first three objectives are concerned with expanding the existing understanding of OS noise on traditional desktop and server platforms to encompass mobile device platforms, and examine the interaction between mobile device state changes and OS noise. The fourth objective is concerned with developing a new approach for mitigating the effects of OS noise on performance benchmark data, whilst accounting for the influence of changing device states. The fifth objective applies the outcomes of the preceding objectives to address the overall research aim, and is concerned with developing and input-centric profiling and prediction system for use by a computational offloading framework. Chapter 1 provides background detail on how computational offloading frameworks function, and presents a thorough literature review of current offloading frameworks. The gap in the existing literature is discussed, and the research question and objectives are described in detail. A brief overview of the Design Science Research Methodology (DSRM) used in this thesis is described, and the choice of methodology is discussed. Overviews of the data chapters of the thesis are provided, along with publication details and a statement of contributions for each chapter. Chapter 2 describes in detail the DSRM utilised by the research in this thesis. This chapter focusses on extending the existing evaluation methodology of the DSRM to address the unique technical challenges associated with evaluating research outputs that target mobile device platforms. Requirements are drawn from existing literature on both evaluation methodology and mobile data collection, then a model is proposed for automating the evaluation of Design Science artifacts targeting mobile device platforms. The proposed model automates feedback loops of the DSRM to facilitate rapid iteration, providing richer information to researchers. Chapter 3 addresses research objectives 1, 2, and 3, and addresses part of research objective 4. The first part of this chapter describes a study into the levels of OS noise present on Apple iPad Air devices, which addresses research objective 1. Examination of the collected data confirms that the characteristics of OS noise on mobile devices are consistent with those observed on traditional desktop and server platforms in the existing literature, thus addressing research objective 2. Further data analysis demonstrates that a relationship exists between OS noise levels and changes in device state, thus addressing research objective 3. The second half of the chapter proposes an adaptive noise mitigation technique for mitigating the effects of OS noise on micro-benchmarking datasets. This addresses the key requirements of research objective 4. Chapter 4 builds on the work presented in Chapter 3. Research objective 4 requires that the adaptive noise mitigation technique be fully automated. However, the outlier removal phase of the noise mitigation technique described in Chapter 3 is only semi-automated. This chapter proposes a fully automated outlier removal technique. The proposed technique exploits the inherent clustering structure present in outliers introduced by OS noise to perform outlier removal. Hierarchical Agglomerative Clustering (HAC) is used to capture the nested clustering structure of the data, and a heuristic algorithm automatically extracts clusterings that isolate outliers from meaningful data. Chapter 5 extends the work presented in Chapter 4 by proposing a novel parallel algorithm for performing hierarchical clustering of single-dimensional data. The classical algorithm for HAC features computational costs that make it too expensive for use on resource-constrained mobile devices. The proposed algorithm utilises GPGPU technologies to enable massive parallelism on commodity consumer hardware, including modern mobile devices. By exploiting the unique properties of single-dimensional data, the proposed algorithm maximises the amount of processing that can be performed in parallel. This efficiency makes the proposed algorithm, and thus the automated outlier removal technique proposed in Chapter 4, suitable for use on resource-constrained mobile devices. This addresses the remaining requirements of research objective 4. Chapter 6 builds the foundation for addressing research objective 5. This chapter reviews existing software timing models from the literature on Worst-Case Execution Time (WCET), and adapts elements of two popular models for use on resource-constrained mobile devices. The proposed timing model simplifies these models to substantially reduce information requirements and computational complexity. Validation of the proposed timing model for individual code execution paths demonstrates that it is an extremely accurate approximation of the information represented by the models that it simplifies. The efficiency of the proposed timing model allows it to be invoked repeatedly to adapt to changes in device state. Chapter 7 completes the work that was started in Chapter 6 to address research objective 5. This chapter proposes a language- and platform-agnostic tooling pipeline that can be used to implement the proposed input-centric profiling and prediction system for any programming language and mobile device platform. The implementation of a prototype of the proposed model targeting the C++ programming language and the Apple iOS platform is then described. The second half of the chapter validates the predictive power of the input-centric profiling and prediction system for code with multiple execution paths. Validation results demonstrate that the produced predictions are extremely accurate across all of the code modules tested. The accuracy and efficiency of the proposed input-centric performance model make it well-suited for use in a computational offloading framework. Chapter 8 summarises the outcomes of the preceding chapters, and discusses the contributions of this thesis to the greater body of knowledge. Theoretical, empirical, and real-world contributions are discussed. The limitations of the thesis are then discussed and used to motivate directions for future research. The outcomes achieved by addressing the five research objectives represent a number of contributions to the greater body of knowledge. The OS noise study undertaken in Chapter 3 to address research objective 1 is the first detailed exploration OS noise on mobile device platforms of which I am aware. The examination of the collected data that was undertaken to address research objective 2 demonstrates that the characteristics of OS noise on mobile devices are consistent with those characteristics observed on traditional desktop and server platforms in the existing literature. The data analysis performed to address research objective 3 demonstrates that a relationship exists between changes in OS noise levels and changes in device state. The work done in Chapters 3, 4, and 5 to address research objective 4 resulted in contributions that extend beyond mobile computing, to the field of data mining. The adaptive OS noise mitigation technique proposed in 3 is the first approach for mitigating the effects of OS noise on micro-benchmarking data to maximise accuracy by taking into account the actual noise profile of the device the benchmark is running on. The automated outlier removal technique proposed in Chapter 4 demonstrates that the structure of outliers introduced by OS noise can be exploited to provide an efficient, automated technique for removing such outliers from micro-benchmarking data. The novel GPU-accelerated clustering algorithm proposed in Chapter 5 demonstrates the enormous performance improvements that can be achieved through the maximisation of merge parallelism, by exploiting the unique properties of single-dimensional datasets. The input-centric profiling and prediction system presented in Chapters 6 and 7 to address research objective 5 represents the key contribution to the field of computational offloading. The application timing model developed in Chapter 6 simplifies popular software timing models from the existing literature to substantially reduce information requirements and computational complexity. This simplification demonstrates the feasibility of adapting timing models for use on resource-constrained mobile devices, even when the unmodified timing models are unsuitable for use in a mobile context. The language- and platform-agnostic tooling pipeline proposed in Chapter 7 allows the proposed input-centric profiling and prediction system to be implemented for any programming language, and for any target mobile device platform. Evaluation of the input-centric profiling and prediction system in Chapters 6 and 7 demonstrates that the produced predictions are extremely accurate. The proposed system accounts for the influence of arbitrary input characteristics on application behaviour, whilst mitigating the effects of OS noise. The efficiency and accuracy of the proposed system make it well-suited for use in a computational offloading framework. The use of deep application-specific knowledge provides high-quality information for making optimal offloading decisions, thus maximising the performance and energy efficiency of mobile applications