Driven by the rapid growth of the demand for efficient and economical computational power, cloud computing has led the world into a new era. It delivers computing resources as services, whereby shared resources are provided to cloud users over the network in order to offer dynamic flexible resource provisioning for reliable and guaranteed services by using pay-as-you-use pricing model. Since multiple cloud users can request cloud resources simultaneously, cloud resource management mechanisms must operate in an efficient manner to satisfy demand of cloud users. Therefore, investigating cloud resource management mechanisms to achieve cloud resource efficiency is one of key elements that benefits both cloud providers and users. In this thesis, we present cloud resource management mechanisms for two different cloud infrastructures, i.e. virtual machine-based (VM-based) and application-based infrastructure. The VM-based infrastructure is an infrastructure that provides multi-tenancy for cloud users at VM-level, i.e. each cloud user directly controls their VMs in the cloud environment. The application-based infrastructure provides multi-tenancy at application level, in the other word, each cloud user directly control their applications in the cloud environment. For the VM-based infrastructure, we introduce two heuristics metrics to capture multi-dimensional characteristics of logical machines. By using a multivariate probabilistic model, we develop an algorithm to improve resource utilisation for the VM-based infrastructure. We then designed and implemented an application-based infrastructure called Elastic Application Container system (EAC system) to support multi-tenant cloud use. Based on the characteristics of the application-based and the VM-based infrastructure, we developed auto-scaling algorithms that can automatically scale cloud resources in the EAC system. In general, the cloud resource management mechanisms proposed in this thesis aims to investigate resource management mechanisms for cloud resource utilisation in the VM-based infrastructure and to provide suitable cloud resource provisioning mechanisms for the application-based infrastructure.

In recent years, sensor technology has advanced in terms of hardware sophistication and miniaturisation. This has led to the incorporation of unobtrusive, low-power sensors into networks centred on human participants, called Body Sensor Networks. Amongst the most important applications of these networks is their use in healthcare and healthy living. The technology has the possibility of decreasing burden on the healthcare systems by providing care at home, enabling early detection of symptoms, monitoring recovery remotely, and avoiding serious chronic illnesses by promoting healthy living through objective feedback. In this thesis, machine learning and data mining techniques are developed to estimate medically relevant parameters from a participant‘s activity and behaviour parameters, derived from simple, body-worn sensors. The first abstraction from raw sensor data is the recognition and analysis of activity. Machine learning analysis is applied to a study of activity profiling to detect impaired limb and torso mobility. One of the advances in this thesis to activity recognition research is in the application of machine learning to the analysis of 'transitional activities': transient activity that occurs as people change their activity. A framework is proposed for the detection and analysis of transitional activities. To demonstrate the utility of transition analysis, we apply the algorithms to a study of participants undergoing and recovering from surgery. We demonstrate that it is possible to see meaningful changes in the transitional activity as the participants recover. Assuming long-term monitoring, we expect a large historical database of activity to quickly accumulate. We develop algorithms to mine temporal associations to activity patterns. This gives an outline of the user‘s routine. Methods for visual and quantitative analysis of routine using this summary data structure are proposed and validated. The activity and routine mining methodologies developed for specialised sensors are adapted to a smartphone application, enabling large-scale use. Validation of the algorithms is performed using datasets collected in laboratory settings, and free living scenarios. Finally, future research directions and potential improvements to the techniques developed in this thesis are outlined.

In this thesis we present a symbolic execution-based technique for cross-checking programs accelerated using SIMD or OpenCL against an unaccelerated version, as well as a technique for detecting data races in OpenCL programs. Our techniques are implemented in KLEE-CL, a symbolic execution engine based on KLEE that supports symbolic reasoning on the equivalence between expressions involving both integer and floating-point operations. While the current generation of constraint solvers provide good support for integer arithmetic, there is little support available for floating-point arithmetic, due to the complexity inherent in such computations. The key insight behind our approach is that floating-point values are only reliably equal if they are essentially built by the same operations. This allows us to use an algorithm based on symbolic expression matching augmented with canonicalisation rules to determine path equivalence. Under symbolic execution, we have to verify equivalence along every feasible control-flow path. We reduce the branching factor of this process by aggressively merging conditionals, if-converting branches into select operations via an aggressive phi-node folding transformation. To support the Intel Streaming SIMD Extension (SSE) instruction set, we lower SSE instructions to equivalent generic vector operations, which in turn are interpreted in terms of primitive integer and floating-point operations. To support OpenCL programs, we symbolically model the OpenCL environment using an OpenCL runtime library targeted to symbolic execution. We detect data races by keeping track of all memory accesses using a memory log, and reporting a race whenever we detect that two accesses conflict. By representing the memory log symbolically, we are also able to detect races associated with symbolically indexed accesses of memory objects. We used KLEE-CL to find a number of issues in a variety of open source projects that use SSE and OpenCL, including mismatches between implementations, memory errors, race conditions and compiler bugs.

Portfolio selection is a decision problem that can be formulated as a mathematical optimisation program. Ever since portfolio selection has been first modelled as a mathematical optimisation problem, a number of frameworks have emerged. These different frameworks aim to address the shortfalls and limitations of previous models. However, most of these models rely on the weak assumption, that the input parameters are known exactly. In the existence of uncertainty surrounding the input parameters, the outcome of a deterministic optimisation problem might be overoptimistic with unexpected consequences in certain scenarios. Robust optimisation deals with the uncertainty surrounding the input parameters. This framework approaches the uncertainty as deterministic and the solution provides certain guarantees, given that the realized scenario is within the considered uncertainty set. The consideration of all possible scenarios leads to more sensible decisions. Robust optimisation frameworks are quite popular in engineering, whereas an overoptimistic solution might yield a catastrophic outcome. This thesis aims to investigate the portfolio construction using robust optimisation frameworks. More specifically, we formulate existing deterministic optimisation models as robust optimisation models and show that they remain tractable under several types of uncertainty. In particular, we examine the distributionally robust Omega Ratio maximization (through solving the Omega Ratio as a convex optimisation problem) and we show that it remains tractable under mixture distribution, ellipsoidal and box uncertainty. In order to illustrate this, we first show that the Omega Ratio maximization is a convex optimisation problem. In addition, we show that the robust counterpart of the Equally-weighted Risk Contribution problem can also be formulated as a convex optimisation problem. We finally provide numerical evidence that suggest the existence of a positive premium for the portfolios constructed using robust formulations versus the deterministic models. The numerical evidence is based on real-life data that span the pre-and post- credit crisis periods.

Domain-specific languages (DSLs) are everywhere, with applications in areas such as parser generation, music synthesis, parallel programming and even the design of domain-specific languages. However, while the pay-off in using a DSL may be substantial, the cost of introducing a language may be made prohibitively high by the need to construct a supporting toolchain. A common tactic is to embed a DSL into a general-purpose host programming language. Existing infrastructure such as a language’s compiler or type system may be re-used, provided that the embedding accurately captures the properties of the DSL. While the rich type systems and orthogonal abstraction features of modern functional languages have proved particularly capable in this regard, they are not without their shortcomings. Building type-safe functions defined over an embedded DSL can introduce application-specific type constraints that end up being imposed on the DSL data types themselves. At best, these constraints are unwieldy and at worst they can limit the range of DSL expressions that can be built. In this thesis we tackle the problem of accurately embedding a DSL’s type system into that of the purely functional language Haskell. We present a framework for expressing application-specific constraints at the point of a DSL expression’s use rather than when the DSL’s embedding is defined. We show how our framework can be applied more generally to capture arbitrary properties of a DSL expression and, in certain cases, how we may subsequently prove additional safety properties such as the totality of a function which operates over DSL expressions. We evaluate our techniques by illustrating their use in constructing a DSL for heterogeneous parallel programming. However, our methods have potentially wider applications such as context-dependent computation, which are also discussed.

Behavioural modelling has been widely used to aid in the design of concurrent systems. Behaviour models have shown to be useful to uncover design errors in early stages of the development process. However, building correct behaviour models is costly and requires significant experience. Controller synthesis offers a way to build models that are correct by construction. Existing software engineering techniques for synthesising controllers have various limitations. Such limitations can be seen as restrictions in the expressiveness of the controller goals and environment model, or in the relation between the controllable and monitored actions. The main aim of this thesis is the development of novel techniques overcoming known limitations of previous approaches and methodological guidelines for synthesising useful controllers. This thesis establishes the framework for controller synthesis techniques that support event-based models, expressive goal specifications, distinguish controllable from monitored actions and guarantee achievement of the desired goals. Together with these techniques, methodological guidelines are proposed to help in building more accurate descriptions of the environment and more effective controllers. In addition, this thesis presents a tool that implements the proposed techniques. Evaluation of the techniques has been conducted using the tool to model known case studies from the literature, showing that by allowing more expressive controller goals and environment models, and explicitly distinguishing controllable and monitored actions such case studies can be more accurately modelled and solutions guaranteeing satisfaction of the goals can be achieved.

No description available.

We consider revenue maximization problem in banner advertisements under two fundamental concepts: Envy-freeness and truthfulness. Envy-freeness captures fairness requirement among buyers while truthfulness gives buyers the incentive to announce truthful private bids. A extension of envy-freeness named competitive equilibrium, which requires both envy-freeness and market clearance conditions, is also investigated. For truthfulness also called incentive compatible, we adapt Bayesian settings, where each buyer's private value is drawn independently from publicly known distributions. Therefore, the truthfulness we adopt is Bayesian incentive compatible mechanisms. Most of our results are positive. We study various settings of revenue maximizing problem e.g. competitive equilibrium and envy-free solution in relaxed demand, sharp demand and consecutive demand case; Bayesian incentive compatible mechanism in relaxed demand, sharp demand, budget constraints and consecutive demand cases. Our approach allows us to argue that these simple mechanisms give optimal or approximate-optimal revenue guarantee in a very robust manner.

In this thesis we study online algorithms for dynamic bin packing. An online algorithm is presented with input throughout time and must make irrevocable decisions without knowledge of future input. The classical bin packing problem is a combinatorial optimization problem in which a set of items must be packed into a minimum number of uniform-sized bins without exceeding their capacities. The problem has been studied since the early 1970s and many variants continue to attract researchers’ attention today. The dynamic version of the bin packing problem was introduced by Coffman, Garey and Johnson in 1983. The problem is a generalization of the bin packing problem in which items may arrive and depart dynamically. In this setting, an online algorithm for bin packing is presented with one item at a time, without knowledge of its departure time, nor arrival and departure times of future items, and must decide in which bin the item should be packed. Migration of items between bins is not allowed, however rearrangement of items within a bin is permitted. The objective of problem is to minimize the maximum number of bins used over all time. In multi-dimensional generalizations of the problem, multi-dimensional items must be packed without overlap in multi-dimensional bins of uniform size in each dimension. In this work, we study the setting where items are oriented and cannot be rotated. We first consider online one-dimensional dynamic bin packing and present a lower bound of 8/3 ∼ 2.666 on the achievable competitive ratio of any deterministic online algorithm, improving the best known 2.5-lower bound. Since the introduction of the problem by Coffman, Garey and Johnson, the progress on the problem has focused on improving the original lower bound of 2.388 to 2.428, and to the best known 2.5-lower bound. Our improvement from 2.5 to 8/3 ∼ 2.666 makes a big step forward in closing the gap between the lower bound and the upper bound, which currently stands at 2.788. Secondly we study the online two- and three-dimensional dynamic bin packing problem by designing and analyzing algorithms for special types of input. Bar-Noy et al. initiated the study of the one-dimensional unit fraction bin packing problem, a restricted version where all sizes of items are of the form 1/k, for some integer k > 0. Another related problem is for power fraction items, where sizes are of the form 1/2k, for some integer k ≥ 0. We initiate the study of online multi-dimensional dynamic bin packing of unit fraction items and power fraction items, where items have lengths unit fraction and power fraction in each dimension, respectively. While algorithms for general input are suitable for unit fraction and power fraction items, their worst-case performance guarantees are the same for special types of input. For unit fraction and power fraction items, we design and analyze online algorithms that achieve better worst-case performance guarantees compared to their classical counterparts. Our algorithms give careful consideration to unit and power fraction items, which allows us to reduce the competitive ratios for these types of inputs. Lastly we focus on obtaining lower bounds on the performance of the family of Any- Fit algorithms (Any-Fit, Best-Fit, First-Fit, Worst-Fit) for online multi-dimensional dynamic bin packing. Any-Fit algorithms are classical online algorithms initially studied for the one-dimensional version of the bin packing problem. The common rule that the algorithms use is to never pack a new item to a new bin if the item can be packed in any of the existing bins. While the family of Any-Fit algorithms is always O(1)-competitive for one-dimensional dynamic bin packing, we show that this is no longer the case for multi-dimensional dynamic bin packing when using Best-Fit and Worst-Fit, even if the input consists of power fraction items or unit fraction items. For these restricted inputs, we prove that Best-Fit and Worst-Fit have unbounded competitive ratios, while for First-Fit we provide lower bounds that are higher than the lower bounds for any online algorithm. Furthermore, for general input we show that all classical Any-Fit algorithms are not competitive for online multi-dimensional dynamic bin packing.

In this thesis the author seeks to establish the most appropriate mechanism for conducting sentiment analysis with respect to political debates; firstly so as to predict their outcome and secondly to support a mechanism to provide for the visualisation of such debates in the context of further analysis. To this end two alternative approaches are considered, a classification-based approach and a lexicon-based approach. In the context of the second approach both generic and domain specific sentiment lexicons are considered. Two techniques to generating domain-specific sentiment lexicons are also proposed: (i) direct generation and (ii) adaptation. The first was founded on the idea of generating a dedicated lexicon directly from labelled source data. The second approach was founded on the idea of using an existing general purpose lexicon and adapting this so that it becomes a specialised lexicon with respect to some domain. The operation of both the generic and domain specific sentiment lexicons are compared with the classification-based approach. The comparison between the potential sentiment mining approaches was conducted by predicting the attitude of individual debaters (speakers) in political debates (using a corpus of labelled political speeches extracted from political debate transcripts taken from the proceedings of the UK House of Commons). The reported comparison indicates that the attitude of speakers can be effectively predicted using sentiment mining. The author then goes on to propose a framework, the Debate Graph Extraction (DGE) framework, for extracting debate graphs from transcripts of political debates. The idea is to represent the structure of a debate as a graph with speakers as nodes and “exchanges” as links. Links between nodes were established according to the exchanges between the speeches. Nodes were labelled according to the “attitude” (sentiment) of the speakers, “positive” or “negative”, using one of the three proposed sentiment mining approaches. The attitude of the speakers was then used to label the graph links as being either “supporting” or “opposing”. If both speakers had the same attitude (both “positive” or both “negative”) the link was labelled as being “supporting”; otherwise the link was labelled as being “opposing”. The resulting graphs capture the abstract representation of a debate where two opposing factions exchange arguments on related content. Finally, the author moves to discuss mechanisms whereby debate graphs can be structurally analysed using network mathematics and community detection techniques. To this end the debate graphs were conceptualised as networks in order to conduct appropriate network analysis. The significance was that the network mathematics and community detection processes can draw conclusions about the general properties of debates in parliamentary practice through the exploration of the embedded patterns of connectivity and reactivity between the exchanging nodes (speakers).