Survey of Memory Management Techniques for HPC and Cloud Computing <s> A. SCHEDULING <s> For task-scheduling problems in cloud computing, a multi-objective optimization method is proposed here. First, with an aim toward the biodiversity of resources and tasks in cloud computing, we propose a resource cost model that defines the demand of tasks on resources with more details. This model reflects the relationship between the user’s resource costs and the budget costs. A multi-objective optimization scheduling method has been proposed based on this resource cost model. This method considers the makespan and the user’s budget costs as constraints of the optimization problem, achieving multi-objective optimization of both performance and cost. An improved ant colony algorithm has been proposed to solve this problem. Two constraint functions were used to evaluate and provide feedback regarding the performance and budget cost. These two constraint functions made the algorithm adjust the quality of the solution in a timely manner based on feedback in order to achieve the optimal solution. Some simulation experiments were designed to evaluate this method’s performance using four metrics: 1) the makespan; 2) cost; 3) deadline violation rate; and 4) resource utilization. Experimental results show that based on these four metrics, a multi-objective optimization method is better than other similar methods, especially as it increased 56.6% in the best case scenario. <s> BIB001 </s> Survey of Memory Management Techniques for HPC and Cloud Computing <s> A. SCHEDULING <s> Virtual machine (VM) scheduling with load balancing in cloud computing aims to allocate VMs to suitable physical machines (PM) and balance the resource usage among all of the PMs. Correct scheduling of cloud hosts is necessary to develop efficient scheduling strategies to appropriately allocate VMs to physical resources. In this regard the use of dynamic forecast of resource usage in each PM can improve the VM scheduling problem. This paper combines ant colony optimization (ACO) and VM dynamic forecast scheduling (VM_DFS), called virtual machine dynamic prediction scheduling via ant colony optimization (VMDPS-ACO), to solve the VM scheduling problem. In this algorithm through analysis of historical memory consumption in each PM, future memory consumption forecast of VMs on that PM and the efficient allocation of VMs on the cloud infrastructure is performed. We experimented the proposed algorithm using Matlab. The performance of the proposed algorithm is compared with VM_DFS [1]. VM_DFS algorithm exploits first fit decreasing (FFD) scheme using corresponding types (i.e. queuing the list of VMs increasingly, decreasingly or randomly) to schedule VMs and assign them to suitable PMs. We experimented the proposed algorithm in both homogeneous and heterogeneous mode. The results indicate, VMDPS-ACO produces lower resource wastage than VM_DFS in both homogenous and heterogeneous modes and better load balancing among PMs. <s> BIB002 </s> Survey of Memory Management Techniques for HPC and Cloud Computing <s> A. SCHEDULING <s> Recent advent of manycore system increases needs for larger but faster memory hierarchy. Emerging next generation memories such as on-chip DRAM and nonvolatile memory (NVRAM) are promising candidates for replacement of DRAM-only main memory. Combined with the manycore trends, it gives an opportunity to rethink conventional resource management system with a memory hierarchy for a single cloud node. In an attempt to mitigate the energy and memory problems, we propose MN-MATE, an elastic resource management architecture for a single cloud node with manycores, on-chip DRAM, and large size of off-chip DRAM and NVRAM. In MN-MATE, the hypervisor places consolidated VMs and balances memory among them. Based on the monitored information about the allocated memory, a guest OS co-schedules tasks accessing different types of memory with complementary access intensity. Polymorphic management of DRAM hierarchy accelerates average memory access speed inside each guest OS. A guest OS reduces energy consumption with small performance loss based on the NVRAM-aware data placement policy and the hybrid page cache. A new lightweight kernel is developed to reduce the overhead from the guest OS for scientific applications. Experiment results show that our techniques in MN-MATE platform improve system performance and reduce energy consumption. <s> BIB003 </s> Survey of Memory Management Techniques for HPC and Cloud Computing <s> A. SCHEDULING <s> Green cloud is an emerging new technology in the computing world in which memory is a critical component. Phase-change memory (PCM) is one of the most promising alternative techniques to the dynamic random access memory (DRAM) that faces the scalability wall. Recent research has been focusing on the multi-level cell (MLC) of PCM. By precisely arranging multiple levels of resistance inside a PCM cell, more than one bit of data can be stored in one single PCM cell. However, the MLC PCM suffers from the degradation of performance compared to the single-level cell (SLC) PCM, due to the longer memory access time. In this paper, we present a genetic-based optimization algorithm for chip multiprocessor (CMP) equipped with PCM memory in green clouds. The proposed genetic-based algorithm not only schedules and assigns tasks to cores in the CMP system, but also provides a PCM MLC configuration that balances the PCM memory performance as well as the efficiency. The experimental results show that our genetic-based algorithm can significantly reduce the maximum memory usage by 76.8 percent comparing with the uniform SLC configuration, and improve the efficiency of memory usage by 127 percent comparing with the uniform 4 bits/cell MLC configuration. Moreover, the performance of the system is also improved by 24.5 percent comparing with the uniform 4 bits/cell MLC configuration in terms of total execution time. <s> BIB004 </s> Survey of Memory Management Techniques for HPC and Cloud Computing <s> A. SCHEDULING <s> A growing number of data- and compute-intensive experiments have been modeled as scientific workflows in the last decade. Meanwhile, clouds have emerged as a prominent environment to execute this type of workflows. In this scenario, the investigation of workflow scheduling strategies, aiming at reducing its execution times, became a top priority and a very popular research field. However, few work consider the problem of data file assignment when solving the task scheduling problem. Usually, a workflow is represented by a graph where nodes represent tasks and the scheduling problem consists in allocating tasks to machines to be executed at a predefined time aiming at reducing the makespan of the whole workflow. In this article, we show that the scheduling of scientific workflows can be improved when both task scheduling and the data file assignment problems are treated together. Thus, we propose a new workflow representation, where nodes of the workflow graph represent either tasks or data files, and define the Task Scheduling and Data Assignment Problem (TaSDAP), considering this new model. We formulated this problem as an integer programming problem. Moreover, a hybrid evolutionary algorithm for solving it, named HEA-TaSDAP, is also introduced. To evaluate our approach we conducted two types of experiments: theoretical and practical ones. At first, we compared HEA-TaSDAP with the solutions produced by the mathematical formulation and by other works from related literature. Then, we considered real executions in Amazon EC2 cloud using a real scientific workflow use case (SciPhy for phylogenetic analyses). In all experiments, HEA-TaSDAP outperformed the other classical approaches from the related literature, such as MinMin and HEFT. A new workflow model that considers tasks and data.The mathematical formulation of Task Scheduling and Data Assignment Problem.The design of a Hybrid Evolutionary Algorithm (HEA) for scheduling tasks and data.An extensive experimental evaluation, based on synthetic and real executions. <s> BIB005 </s> Survey of Memory Management Techniques for HPC and Cloud Computing <s> A. SCHEDULING <s> Today's Cloud applications are dominated by composite applications comprising multiple computing and data components with strong communication correlations among them. Although Cloud providers are deploying large number of computing and storage devices to address the ever increasing demand for computing and storage resources, network resource demands are emerging as one of the key areas of performance bottleneck. This paper addresses network-aware placement of virtual components (computing and data) of multi-tier applications in data centers and formally defines the placement as an optimization problem. The simultaneous placement of Virtual Machines and data blocks aims at reducing the network overhead of the data center network infrastructure. A greedy heuristic is proposed for the on-demand application components placement that localizes network traffic in the data center interconnect. Such optimization helps reducing communication overhead in upper layer network switches that will eventually reduce the overall traffic volume across the data center. This, in turn, will help reducing packet transmission delay, increasing network performance, and minimizing the energy consumption of network components. Experimental results demonstrate performance superiority of the proposed algorithm over other approaches where it outperforms the state-of-the-art network-aware application placement algorithm across all performance metrics by reducing the average network cost up to 67% and network usage at core switches up to 84%, as well as increasing the average number of application deployments up to 18%. <s> BIB006 </s> Survey of Memory Management Techniques for HPC and Cloud Computing <s> A. SCHEDULING <s> Recent advances in chip design and integration technologies have led to the development of Single-Chip Cloud computers which are a microcosm of cloud datacenters. Those computers are based on Network-on-Chip (NoC) architectures with deep memory hierarchies. Developing scheduling algorithms to reduce data access latency as well as energy consumption is a major challenge for such architectures. In this paper, we propose a set of algorithms to jointly address the problem of task scheduling and data allocation in a unified approach. Moreover, we present a feasible system model for NoC based multicores considering a three-level memory hierarchy that effectively captures the energy consumed by various elements of system including: processing cores, caches, and NoC subsystem. Simulation results show the superiority of proposed algorithms compared to two state-of-the-art algorithms found in the literature. The experimental results clearly indicate that algorithms performing data and task scheduling in a joint fashion are superior against techniques implementing task and data scheduling separately. <s> BIB007 </s> Survey of Memory Management Techniques for HPC and Cloud Computing <s> A. SCHEDULING <s> Cloud computing is growing in popularity among computing paradigms, but in practice the energy consumption of the cloud data centers is very high. In this paper, we build the resource model of the cloud data center and the dynamic power model of the physical machine, and then propose a three-dimensional virtual resource scheduling method for energy saving in cloud computing (TVRSM), in which the process of virtual resource scheduling are divided into three stages: virtual resource allocation, virtual resource scheduling and virtual resource optimization. For the different objective of each stage, we design three different algorithms, respectively. The simulation results prove that the TVRSM is able to efficiently allocate and manage the virtual resources in the cloud data center. And compared with other traditional algorithms, the TVRSM can effectively reduce the energy consumption of the cloud data center and significantly minimize the amount of violations of Service Level Agreement (SLA). We propose a three-dimensional virtual resource (VR) scheduling method.We present a bin packing problem based heuristics VR allocation algorithm.We demonstrate a multi-dimensional power-aware based VR scheduling algorithm.We put forward a VR optimization algorithm to reduce energy consumption.The simulation results demonstrate the effectiveness of the proposed method. <s> BIB008 </s> Survey of Memory Management Techniques for HPC and Cloud Computing <s> A. SCHEDULING <s> Abstract With the rapid development of cloud computing, how to reduce energy consumption as well as maintain high computation capacity has become a timely and important challenge. Existing Virtual Machines (VMs) scheduling schemes have mainly focused on enhancing the cluster resource utilization and reducing power consumption by improving the legacy “bin-packing” algorithm. However, different resource-intensive applications running on VMs in realistic scenarios have significant effects on the system performance and energy consumption. Furthermore, instantaneous peak loads may lead to a scheduling error, which can significantly impede the energy efficiency of scheduling algorithms. In this paper, we propose a new scheduling approach named P r e A n t P o l i c y that consists of a prediction model based on fractal mathematics and a scheduler on the basis of an improved ant colony algorithm. The prediction model determines whether to trigger the execution of the scheduler by virtue of load trend prediction, and the scheduler is responsible for resource scheduling while minimizing energy consumption under the premise of guaranteeing the Quality-of-Service (QoS). Through extensive analysis and simulation experiments using real workload traces from the compute clusters of Google, the performance results demonstrate that the proposed approach exhibits excellent energy efficiency and resource utilization. Moreover, this approach offers an effective dynamic capacity provisioning model for resource-intensive applications in a heterogeneous computing environment and can reduce the consumption of system resources and energy when scheduling is triggered by instantaneous peak loads. <s> BIB009 </s> Survey of Memory Management Techniques for HPC and Cloud Computing <s> A. SCHEDULING <s> Since cloud computing provides computing resources on a pay per use basis, a task scheduling algorithm directly affects the cost for users. In this paper, we propose a novel cloud task scheduling algorithm based on ant colony optimization that allocates tasks of cloud users to virtual machines in cloud computing environments in an efficient manner. To enhance the performance of the task scheduler in cloud computing environments with ant colony optimization, we adapt diversification and reinforcement strategies with slave ants. The proposed algorithm solves the global optimization problem with slave ants by avoiding long paths whose pheromones are wrongly accumulated by leading ants. <s> BIB010 </s> Survey of Memory Management Techniques for HPC and Cloud Computing <s> A. SCHEDULING <s> Abstract Distributed Stream Processing Systems (DSPS) are “Fast Data” platforms that allow streaming applications to be composed and executed with low latency on commodity clusters and Clouds. Such applications are composed as a Directed Acyclic Graph (DAG) of tasks, with data parallel execution using concurrent task threads on distributed resource slots. Scheduling such DAGs for DSPS has two parts—allocation of threads and resources for a DAG, and mapping threads to resources. Existing schedulers often address just one of these, make the assumption that performance linearly scales, or use ad hoc empirical tuning at runtime. Instead, we propose model-driven techniques for both mapping and allocation that rely on low-overhead a priori performance modeling of tasks. Our scheduling algorithms are able to offer predictable and low resource needs that is suitable for elastic pay-as-you-go Cloud resources, support a high input rate through high VM utilization, and can be combined with other mapping approaches as well. These are validated for micro and application benchmarks, and compared with contemporary schedulers, for the Apache Storm DSPS. <s> BIB011 </s> Survey of Memory Management Techniques for HPC and Cloud Computing <s> A. SCHEDULING <s> Cloud computing offers simplified system maintenance and scalable resource management with Virtual Machines (VMs). Users access resources of data centers by allocating VMs to hosts. Therefore, to improve the quality of cloud computing environment, not only the conventional multi Quality of Service (QoS) be satisfied, but also specific importance has to be made on certain metrics such as the system accessibility and resource scheduling in a cooperative and dynamic manner. This paper proposes a method called, Moving Average-based Fuzzy Resource Scheduling (MV-FRS) for virtualized cloud environment to optimize the scheduling of resources through virtual machines. Initially, the MV-FRS method starts by predicting the resource (i.e. bandwidth, memory and processing cycle) requirements. Then a measure of relationships between availability of resources and the requirements of resources are made. Finally, a fuzzy control theory is designed to accomplish system accessibility between user cloud requirements and cloud users resources availability. The simulations results demonstrate that the MV-FRS method is able to reduce the total waiting time of cloud user resource requirements and also ensure the feasibility and effectiveness of the overall system accessibility in terms of average success rate and resource usage when running in a cloud computing environment. Moving Average-based Fuzzy Resource Scheduling (MV-FRS) for virtualized cloud environment to optimize the scheduling of resources through virtual machines.A fuzzy control theory is designed for system accessibility between user cloud requirements and cloud users resources.MV-FRS method is to reduce the total waiting time of cloud user resource requirements and effectiveness of the system accessibility. <s> BIB012 </s> Survey of Memory Management Techniques for HPC and Cloud Computing <s> A. SCHEDULING <s> Abstract In this paper we argue that scientific applications traditionally considered as representing typical HPC workloads can be successfully and efficiently ported to a cloud infrastructure. We propose a porting methodology that enables parallelization of communication – and memory-intensive applications while achieving a good communication to computation ratio and a satisfactory performance in a cloud infrastructure. This methodology comprises several aspects: (1) task agglomeration heuristic enabling increasing granularity of tasks while ensuring they will fit in memory; (2) task scheduling heuristic increasing data locality; and (3) two-level storage architecture enabling in-memory storage of intermediate data. We implement this methodology in a scientific workflow system and use it to parallelize a multi-frontal solver for finite-element meshes, deploy it in a cloud, and execute it as a workflow. The results obtained from the experiments confirm that the proposed porting methodology leads to a significant reduction of communication costs and achievement of a satisfactory performance. We believe that these results constitute a valuable step toward a wider adoption of cloud infrastructures for computational science applications. <s> BIB013
Generally, scheduling is a decision-making process that allows to distribute available resources among a number of tasks by determining the order of execution. Scheduling is a NP-complete problem, even for the simple scenarios. Moreover scheduling in Cloud architectures is a bit more complicated due to the heterogeneity of VMs and negative impact of the transfers of the huge data between VMs. Recent studies on scheduling in the Cloud were analysed from the MM techniques point of view. In BIB005 data distribution and task distribution are defined as dependent problems, and they are analysed together for efficient scheduling. Data communication requirements between VMs and storage nodes in addition to the computing and memory resource demands are taken into account in the scheduling approach proposed in BIB006 . Layers of the data communication requirements is presented in Figure 15 . Scheduling interdependent tasks and intermediate data within a system with four level cache/memory hierarchies introduced in BIB007 aims to optimise performance and energy consumption. The scheduling approach introduced in [63] uses profiles which are created on the machine learning models based on the workflow profiling information along with resources that were used during execution, such as CPU, memory, a number of compute nodes, input file size. Virtual resources scheduling techniques described in BIB008 use an energy consumption model to perform VMs migration from the overloaded hosts to other hosts with lower resource utilisation or to idled hosts. The responsibility of the scheduler in the VMs migration is also evident in the approach presented in BIB009 . Prediction model instructions are used to decide whether migration is needed, and the destination is determined using an improved ant colony algorithm. A multi-objective optimisation scheduling method (PBACO) proposed in BIB001 is also based on the ant colony algorithm. A resource cost model includes two parts of the CPU and the memory, such as the base cost and the cost associated with the transmission. The proposed approach achieves the multi-objective optimisation for the optimal span, deadline, resource utilisation and user costs. This work focuses on two types of resources, CPU and disk I/O bandwidth, but the approach allows to scale the number of resources. The ant colony optimisation method, along with VM dynamic forecast scheduling, was also used in BIB002 . Ant colony optimisation with slave ants for scheduling tasks in cloud computing environments described in BIB010 aims at maximising the utilisation of cloud servers. The proposed approach uses stored information about CPU utilisation and memory usage provided by the resource manager. Diversification and reinforcement strategies with slave ants allow avoiding long paths whose pheromones are wrongly accumulated by leading ants. Here, to evaluate the pheromone level, solutions generated by the first fit decreasing (FFD) algorithm are presented as the function of the memory loss of the particular solution. A general scheme of the ant colony optimisation in cloud scheduling is shown in Figure 16 . Scheduling for Distributed Stream Processing Systems (DSPS) in BIB011 was considered as two interdependent parts, namely threads and resources allocation and mapping threads to resources. The allocation part is in charge of identifying the number of threads per task and the number of resource slots allocated. The mapping part aims at assigning these task to the specific resource slots and to meet the requirements. A dynamic resource scheduling model based on the Max Min Fuzzy Inference is designed in BIB012 for executing different types of cloud user requests. Reference BIB013 shows that task scheduling heuristic with the memory consumption balancing has a positive effect on the number of machines required to complete a multi-frontal solver at a given time. They propose the task agglomeration heuristics where the amount of memory required to perform a given subtree of the element partition tree is estimated. If this falls below a defined threshold, then the subtree is agglomerated into a single task. The aim of a task scheduling policy based on the memory accesses distribution in the time proposed in BIB003 is to prevent performance degradation. This approach uses per-task memory access monitoring for memory access classification in order to schedule a latency-sensitive task before bandwidth-sensitive tasks. A genetic-based optimisation algorithm presented in BIB004 uses a genetic-based algorithm for the task-core scheduling along with Phase-change memory (PCM) configuration. Aiming at green cloud computing, this approach provides a PCM configuration that balanced the PCM memory performance as well as the efficiency. Scheduling has been traditionally considered as an NP-complete optimisation problem with the execution time as a single objective of interest. The complexity of the current heterogeneous cloud systems, brought additional objectives, such as energy consumption, operational costs, throughput, makespan, fault tolerance, reliability, security, predictability, elasticity. The challenge is that these objectives are often in conflict with each other, requiring new complex algorithms to obtain an optimal solution with regards to all conflicting objectives. Heuristic and metaheuristic algorithms for task scheduling in Cloud reduce the solution search space, consequently, significantly improve efficiency. However, these algorithms are time-consuming and, in some cases, return local optimum solution due to imbalance between local and global search. For instance, the common used ACO algorithms still have the slow convergence speed and are easy to fall into local optimum value. Besides, the quality of scheduling produced by these algorithms still tightly depends on the problem size and the number of objectives to be optimised. Therefore, it is necessary to further and deeply study and improve heuristic and metaheuristic algorithms along with algorithms inspired by nature with better optimisation performance. The majority of the scheduling algorithms focused on the scheduling problem of jobs/tasks, but ignore the deployment of input data. However, the management of memory resources and data movement are becoming more critical, as the applications are becoming data-intensive. The scheduling algorithms with data placement strategy will improve the data locality.