In the emerging microservice-based architecture of cloud HPC systems, a challenging problem of critical importance for system service capability is how we can schedule microservices to minimize the end-to-end response time for user requests while keeping cost within the specified budget. We address this problem for multi-instance microservices requested by a single application to which no existing result is known to our knowledge. We propose an effective two-stage solution of first allocating budget (resources) to microservices within the budget constraint and then deploying microservice instances on servers to minimize system operational overhead. For budget allocation, we formulate it as the Discrete Time Cost Tradeoff (DTCT) problem which is NP-hard, present a linear program (LP) based algorithm, and provide a rigorous proof of its worst-case performance guarantee of 4 from the optimal solution. For microservice deployment, we show that it is harder than the NP-hard problem of 1-D binpacking through establishing its mathematical model, and propose a heuristic algorithm of Least First Mapping that greedily places microservice instances on fewest possible servers to minimize system operation cost. The experiment results of extensive simulations on DAG-based applications of different sizes demonstrate the superior performance of our algorithm in comparison with the existing approaches. • Formulate the problem of budget allocation to multi-instance microservices as the Discrete Time Cost Tradeoff (DTCT) problem, a well-known NP-hard problem. • Transform this problem to a linear program (LP) and present an approximation algorithm to minimize microservice completion time by determining the desired number of instances for each microservice within the given budget constraint. • Provide a rigorous proof of worst-case performance guarantee of 4 of our algorithm. • Present a heuristic algorithm of Least First Mapping for the problem of microservice deployment to place the microservice instances on fewest possible servers at minimum system operation cost. • Experimentally validate our algorithm and demonstrate its superiority to the existing approaches in terms of maximum completion time of microservices under budget constraint and the number of launched servers.

Workflow tasks are time-sensitive and their task completion utility, i.e., value of task completion, is inversely proportional to their completion time. Existing solutions to the NP-hard problem of utility-maximization task scheduling were achieved under the assumptions of linear Time Utility Function (TUF), i.e., utility is inversely proportional to completion time following a linear function, and prior knowledge of task execution time, which is unrealistic for many applications and dynamic systems. This paper proposes a novel model of combining greedy optimization with machine learning for scheduling time-sensitive tasks with convex TUF and unknown task execution time on heterogeneous cloud servers offline nonpreemptively to maximize the total utility of input tasks. For a set of time-sensitive tasks with data dependencies, we first employ multi-layer perceptron neural networks to predict task execution time by utilizing historical data. Then, by solving a linear program after relaxing the disjunctive constraint introduced by the nonpreemption requirement to calculate maximum utility increment, we propose a novel greedy algorithm of marginal incremental utility maximization that jointly determines the task-to-processor allocation plan and tasks' execution sequence on each processor. We then show that our algorithm has an expected approximation ratio of$\frac{(e-1)(\tau -2)}{e\tau }$for convex TUF and$\frac{e-1}{3e}\approx 0.21$for linear TUF, where$\tau$is the ratio of total completion utility over total delay cost under optimal scheduling. Our result presents the first polynomial-time approximation solution for this problem that achieves a performance guarantee of bounded ratio for convex TUF and constant ratio for linear TUF respectively. Extensive experiment results through both simulation and real cloud implementation demonstrate significant performance improvement of our algorithm over the known results.

In a large cloud data center HPC system, a critical problem is how to allocate the submitted tasks to heterogenous servers for achieving the goal of maximize systems net gain defined as the value of completed tasks minus system operation cost. We consider this problem in the online setting that tasks arrive in batches and propose a novel deep reinforcement learning (DRL) enhanced greedy algorithm of two-stage scheduling interacting task sequencing and task allocation. For task sequencing we deploy a DRL module to make prediction for the best allocation sequence for each arriving batch of tasks based on knowledge (allocation strategies) learnt from prior batches. For task allocation, we propose a greedy strategy that allocates tasks to servers one by one online following the allocation sequence to maximally increase the total gain. We show that our greedy strategy has a performance guarantee of competitive ratio 1/(1+k) to the optimal offline solution, which improves the existing result for the same problem, where k is upper bounded by the maximum cost-to-gain ratio of each task. While our DRL module enhances the greedy by providing the likely-optimal allocation sequence for each batch of arriving tasks, our greedy strategy bounds DRLs prediction error within a proven performance guarantee for any allocation sequence, enabling a better solution quality than that obtainable from both DRL and greedy optimization alone. Extensive experiment evaluation results in both simulation and real application environments demonstrate the effectiveness and efficiency of our proposed algorithm. Compared with the state-of-the-art baselines, our algorithm increases the system gain by about 10% to 30%. Our algorithm provides an interesting example of joining machine-learning and greedy optimization techniques to improve ML-based solutions with a worst-case performance guarantee for solving hard optimization problems.