Resource and Instance Hour Minimization for Deadline Constrained DAG Applications Using Computer Clouds - Wu, Hao; Hua, Xiayu; Li, Zheng; Ren, Shangping (IEEE Transactions on Parallel and Distributed Systems, 2016)
In this paper, we address the resource and virtual machine instance hour minimization problem for directed-acyclic-graph based deadline constrained applications deployed on computer clouds. The allocated resources and instance hours on computer clouds must: (1) guarantee the satisfaction of a deadline constrained application's end-to-end deadline; (2) ensure that the number of virtual machine (VM) instances allocated to the application is minimized; (3) under the allocated number of VM instances, determine application execution schedule that minimizes the application's makespan; and (4) under the decided application execution schedule, determine a VM operation schedule, i.e., when a VM should be turned on or off, that minimizes total VM instance hours needed to execute the application. We first give lower and upper bounds for the number of VM instances needed to guarantee the satisfaction of a deadline constrained application's end-to-end deadline. Based on the bounds, we develop a heuristic algorithm called minimal slack time and minimal distance (MSMD) algorithm that finds the minimum number of VM instances needed to guarantee the application's deadline and schedules tasks on the allocated VM instances so that the application's makespan is minimized. Once the application execution schedule and the number of VM instances needed are determined, the proposed VM instance hour minimization (IHM) algorithm is applied to further reduce the instance hours needed by VMs to complete the application's execution. Our experimental results show that the MSMD algorithm can guarantee applications' end-to-end deadlines with less resources than the HEFT [32], MOHEFT [16], DBUS [9], QoS-base [40] and Auto-Scaling [25] heuristic scheduling algorithms in the literature. Furthermore, under allocated resources, the MSMD algorithm can, on average, reduce an application's makespan by 3.4 percent of its deadline. In addition, with the IHM algorithm we can effectively reduce the application's execution instance hours compared with when IHM is not applied.
Conference Name: IEEE Transactions on Parallel and Distributed Systems
Keywords: Cloud; Cloud computing; Computers; Heuristic algorithms; Minimization; Processor scheduling; Schedules; Virtual machining; cost minimization; dept.csc; instance hour minimization; makespan minimization; peer-reviewed; real-time; MSMD; resource minimization; scheduling

Best-Harmonically-Fit Periodic Task Assignment Algorithm on Multiple Periodic Resources - Guo, Chunhui; Hua, Xiayu; Wu, Hao; Lautner, Douglas; Ren, Shangping (IEEE Transactions on Parallel and Distributed Systems, 2016)
The periodic task set assignment problem in the context of multiple processors has been studied for decades. Different heuristic approaches have been proposed, such as the Best-Fit (BF), the First-Fit (FF), and the Worst-Fit (WF) task assignment algorithms. However, when processors are not dedicated but only periodically available to the task set, whether existing approaches still provide good performance or if there is a better task assignment approach in the new context are research problems which, to our best knowledge, have not been studied by the real-time research community. In this paper, we present the Best-Harmonically-Fit (BHF) task assignment algorithm to assign periodic tasks on multiple periodic resources. By periodic resource we mean that for every fixed time interval, i.e., the period, the resource always provides the same amount of processing capacity to a given task set. Our formal analysis indicates that if a harmonic task set is also harmonic with a resource's period, the resource capacity can be fully utilized by the task set. Based on this analysis, we present the Best-Harmonically-Fit task assignment algorithm. The experimental results show that, on average, the BHF algorithm results in 53.26 , 42.54 , and 27.79 percent higher resource utilization rate than the Best-Fit Decreasing (BFD), the First-Fit Decreasing (FFD), and the Worst-Fit Decreasing (WFD) task assignment algorithms, respectively; but comparing to the optimal resource utilization rate found by exhaustive search, it is about 11.63 percent lower.
Conference Name: IEEE Transactions on Parallel and Distributed Systems
Keywords: Context; Harmonic analysis; Program processors; Real-time systems; Resource management; Scheduling algorithms; best-harmonically-fit; dept.csc; peer-reviewed; periodic resource; task assignment

A Reference Model for Virtual Machine Launching Overhead - Wu, Hao; Ren, Shangping; Garzoglio, Gabriele; Timm, Steven; Bernabeu, Gerard; Chadwick, Keith; Noh, Seo-Young (IEEE Transactions on Cloud Computing, 2016)
Cloud bursting is one of the key research topics in the cloud computing communities. A well designed cloud bursting module enables private clouds to automatically launch virtual machines (VMs) to public clouds when more resources are needed. One of the main challenges in developing a cloud bursting module is to decide when and where to launch a VM so that all resources are most effectively and efficiently utilized and the system performance is optimized. However, based on system operational data obtained from FermiCloud, a private cloud developed by the Fermi National Accelerator Laboratory for scientific workflows, the VM launching overhead is not a constant. It varies with physical resource utilization, such as CPU and I/O device utilizations, at the time when a VM is launched. Hence, to make judicious decisions as to when and where a VM should be launched, a VM launching overhead reference model is needed. In this paper, we first develop a VM launching overhead reference model based on operational data we have obtained on FermiCloud. Second, we apply the developed reference model on FermiCloud and compare calculated VM launching overhead values based on the model with measured overhead values on FermiCloud. Our empirical results on FermiCloud indicate that the developed reference model is accurate. We believe, with the guidance of the developed reference model, efficient resource allocation algorithms can be developed for cloud bursting process to minimize the operational cost and resource waste.
Conference Name: IEEE Transactions on Cloud Computing
Keywords: Bandwidth; Cloud computing; Computational modeling; Computers; FermiCloud; Resource management; Servers; VM launching overhead; Virtualization; cloud; dept.csc; launch; model; overhead; peer-reviewed; predict; reference model; virtual machine; vm launching; vm startup time