A hybrid Branch-and-Bound and evolutionary approach for allocating strings of applications to heterogeneous distributed computing systems

Providing efficient workload management is an important issue for a large-scale heterogeneous distributed computing environment where a set of periodic applications is executed. The considered shipboard distributed system is expected to operate in an environment where the input workload is likely to change unpredictably, possibly invalidating a resource allocation that was based on the initial workload estimate. The tasks consist of multiple strings, each made up of an ordered sequence of applications. There is a quality of service (QoS) minimum throughput constraint that must be satisfied for each application in a string, and a maximum utilization constraint that must be satisfied on each of the hardware resources in the system. The challenge, therefore, is to efficiently and robustly manage both computation and communication resources in this unpredictable environment to achieve high performance while satisfying the imposed constraints. This work addresses the problem of finding a robust initial allocation of resources to strings of applications that is able to absorb some level of unknown input workload increase without rescheduling. The proposed hybrid two-stage method of finding a near-optimal allocation of resources incorporates two specially designed mapping techniques: (1) the Permutation Space Genitor-Based heuristic, and (2) the follow-up Branch-and-Bound heuristic based on an Integer Linear Programming (ILP) problem formulation. The performance of the proposed resource allocation method is evaluated under different simulation scenarios and compared to an iteratively computed upper bound.     

Failure-aware resource provisioning for hybrid Cloud infrastructure

Hybrid Cloud computing is receiving increasing attention in recent days. In order to realize the full potential of the hybrid Cloud platform, an architectural framework for efficiently coupling public and private Clouds is necessary. As resource failures due to the increasing functionality and complexity of hybrid Cloud computing are inevitable, a failure-aware resource provisioning algorithm that is capable of attending to the end-users quality of service (QoS) requirements is paramount. In this paper, we propose a scalable hybrid Cloud infrastructure as well as resource provisioning policies to assure QoS targets of the users. The proposed policies take into account the workload model and the failure correlations to redirect users’ requests to the appropriate Cloud providers. Using real failure traces and a workload model, we evaluate the proposed resource provisioning policies to demonstrate their performance, cost as well as performance–cost efficiency. Simulation results reveal that in a realistic working condition while adopting user estimates for the requests in the provisioning policies, we are able to improve the users’ QoS about 32% in terms of deadline violation rate and 57% in terms of slowdown with a limited cost on a public Cloud.     

Maximizing stochastic robustness of static resource allocations in a periodic sensor driven cluster

This research investigates the problem of robust static resource allocation for distributed computing systems operating under imposed Quality of Service (QoS) constraints. Often, such systems are expected to function in an environment where uncertainty in system parameters is common. In such an environment, the amount of processing required to complete a task may fluctuate substantially. Determining a resource allocation that accounts for this uncertainty—in a way that can provide a probability that a given level of QoS is achieved—is an important area of research. We have designed novel techniques for maximizing the probability that a given level of QoS is achieved. These techniques feature a unique application of both path relinking and local search within a Genetic Algorithm. In addition, we define a new methodology for finding resource allocations that are guaranteed to have a non-zero probability of addressing the timing constraints of the system. We demonstrate the use of this methodology within two unique steady-state genetic algorithms designed to maximize the robustness of resource allocations. The performance results for our techniques are presented for a simulated environment that models a heterogeneous cluster-based radar data processing center.     

基于DVFS感知与虚拟机动态合并的云数据中心能效策略

为了解决云数据中心资源分配时能耗与性能间的均衡问题,提出了一种基于DVFS感知与虚拟机动态合并的能效优化策略。首先,策略通过新的DVFS管理算法（DVFS-perf）在不降低系统性能的同时降低了数据中心功耗,然后,通过频率感知的虚拟机VM部署合并算法（Frequency-aware Placement）在实现DVFS最优配置的同时最小化总体能耗,同时确保了虚拟机映射时的QoS保障。最后,通过真实云负载数据流构建仿真实验进行了性能分析。结果表明,在动态负载条件下,策略可以在不降低QoS和不增加SLA违例的情况下,降低虚拟机迁移次数和数据中心的总体能耗,更好地实现能耗与性能的均衡。     

Using Constraint Satisfaction Problem approach to solve human resource allocation problems in cooperative health services

In developing countries, the increasing utilization of health services, due to a great life expectancy, is followed by a reduction in incomes from the public health system and from private insurance companies, to the payment of medical procedures. Beyond this scenery, it is mandatory an effective hospital cost control though the utilization of planning tools.This work is intended to contribute to the reduction of hospital costs, proposing a new tool for planning human resources utilization in hospital plants. Specifically, it is proposed a new tool for human resources allocation in health units. The solution to the allocation problem uses the CSP technique (Constraint Satisfaction Problem) associated with the backtracking search algorithm. With the objective of enhancing the backtracking search algorithm performance a new heuristics is proposed. Through some simulations the performance of the proposed heuristics is compared to the other heuristics previously published in literature: remaining minimum values, forward checking and grade heuristics.Another important contribution of this work is the mathematical modeling of the constraints, that could be unary, multiple, numeric and implicit constraints. In the results it is presented a case study of a human resource allocation in a cooperative health service.Based on the results, it is proposed that for a real allocation problems solution, the best approach is to combine the remaining minimum values heuristics with the grade heuristics, to select the best unit allocation to be filled, and then use the proposed heuristic to select the best physician to the chosen unit allocation. This association shows a satisfactory result for the human resource allocation problem of the case study, with an algorithm convergence time of 46.7 min with no backtracks. The same problem when manually resolved took about more than 50 h.     

一种异构实时系统中任务流均衡负载的算术模型

异构环境下如何提高系统自治并发处理的能力,是分布式系统研究领域的重要课题。而异构实时系统中系统自治并发处理的能力则体现在事件驱动任务流控制的资源最优分配。本文针对已有的资源分配策略的缺陷给出了一个通用的任务流均衡负载的算术模型,除了对任务流进行量化,使其可以动态分配以外,还可以在任务流发生变化时在满足系统最大利益的前提下最优化代价函数。另外,由于这个算术模型具有通用性,因此适用于各种资源分配的启发式搜索算法。     

Application Layer Scheduling in Cloud: Fundamentals,Review and Research Directions

The cloud computing paradigm facilitates a finite pool of on-demand virtualized resources on a pay-per-use basis. For large-scale heterogeneous distributed systems like a cloud, scheduling is an essential component of resource management at the application layer as well as at the virtualization layer in order to deliver the optimal Quality of Services (QoS). The cloud scheduling, in general, is an NP-hard problem due to large solution space, thus, it is difficult to find an optimal solution within a reasonable time. In application layer scheduling, the tasks are mapped to logical resources (i.e., virtual machines), aiming to optimize one or more QoS parameters, and conforming to several constraints. Various algorithms have been proposed in the literature for application layer scheduling, where each of them is based on some fundamental design techniques like simple heuristics, meta-heuristics, and most recently hybrid heuristics. Although ample literature survey exists for cloud scheduling algorithms, none of them present their study exclusively for the application layer. In this survey paper, we present a study on task scheduling algorithms used only at the application layer of the cloud. We classify our study according to various fundamental techniques used in designing such scheduling algorithms. One of the main features of our study is that it covers numerous application type e.g., a set of independent tasks, simple workflow, scientific workflow, and MapReduce jobs. We also provide a comparative analysis of existing algorithms on various parameters like makespan, cost, resource utilization, etc. In the end, research directions for future work have been provided.     

Dynamically mapping tasks with priorities and multiple deadlines in a heterogeneous environment

In a distributed heterogeneous computing system, the resources have different capabilities and tasks have different requirements. To maximize the performance of the system, it is essential to assign the resources to tasks (match) and order the execution of tasks on each resource (schedule) to exploit the heterogeneity of the resources and tasks. Dynamic mapping (defined as matching and scheduling) is performed when the arrival of tasks is not known a priori. In the heterogeneous environment considered in this study, tasks arrive randomly, tasks are independent (i.e., no inter-task communication), and tasks have priorities and multiple soft deadlines. The value of a task is calculated based on the priority of the task and the completion time of the task with respect to its deadlines. The goal of a dynamic mapping heuristic in this research is to maximize the value accrued of completed tasks in a given interval of time. This research proposes, evaluates, and compares eight dynamic mapping heuristics. Two static mapping schemes (all arrival information of tasks are known) are designed also for comparison. The performance of the best heuristics is 84% of a calculated upper bound for the scenarios considered.     

Characterization of the iterative application of makespan heuristics on non-makespan machines in a heterogeneous parallel and distributed environment

Heterogeneous computing (HC) is the coordinated use of different types of machines, and networks to process a diverse workload in a manner that will maximize the combined performance and/or cost effectiveness of the system. Heuristics for allocating resources in an HC system are based on some optimization criterion. A common optimization criterion is to minimize the completion time of the machine that finishes last (makespan). In this study, we consider an iterative approach that repeatedly runs a mapping heuristic to minimize the makespan of the considered machines and tasks. For each successive iteration, the makespan machine of the previous iteration and the tasks assigned to it are removed from the set of considered machines and tasks. This study focuses on understanding the different mathematical characteristics of resource allocation heuristics that cause them to behave differently when combined with this iterative approach. This paper has three main contributions. The first contribution is the study of an iterative technique used in conjunction with resource allocation heuristics. The second contribution is the definition and mathematical characterization of “iteration invariant” heuristics. The third contribution is to determine the characteristics of a heuristic that will cause the mapping to change across iterations.     

Heuristics for scheduling file-sharing tasks on heterogeneous systems with distributed repositories

We consider the problem of scheduling an application on a computing system consisting of heterogeneous processors and data repositories. The application consists of a large number of file-sharing otherwise independent tasks. The files initially reside on the repositories. The processors and the repositories are connected through a heterogeneous interconnection network. Our aim is to assign the tasks to the processors, to schedule the file transfers from the repositories, and to schedule the executions of tasks on each processor in such a way that the turnaround time is minimized. We propose a heuristic composed of three phases: initial task assignment, task assignment refinement, and execution ordering. We experimentally compare the proposed heuristics with three well-known heuristics on a large number of problem instances. The proposed heuristic runs considerably faster than the existing heuristics and obtains 10–14% better turnaround times than the best of the three existing heuristics.     

Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system

We present a multi-heuristic evolutionary task allocation algorithm to dynamically map tasks to processors in a heterogeneous distributed system. It utilizes a genetic algorithm, combined with eight common heuristics, in an effort to minimize the total execution time. It operates on batches of unmapped tasks and can preemptively remap tasks to processors. The algorithm has been implemented on a Java distributed system and evaluated with a set of six problems from the areas of bioinformatics, biomedical engineering, computer science and cryptography. Experiments using up to 150 heterogeneous processors show that the algorithm achieves better efficiency than other state-of-the-art heuristic algorithms.     

Multihybrid job scheduling for fault-tolerant distributed computing in policy-constrained resource networks

Unpredictable fluctuations in resource availability often lead to rescheduling decisions that sacrifice a success rate of job completion in batch job scheduling. To overcome this limitation, we consider the problem of assigning a set of sequential batch jobs with demands to a set of resources with constraints such as heterogeneous rescheduling policies and capabilities. The ultimate goal is to find an optimal allocation such that performance benefits in terms of makespan and utilization are maximized according to the principle of Pareto optimality, while maintaining the job failure rate close to an acceptably low bound. To this end, we formulate a multihybrid policy decision problem (MPDP) on the primary-backup fault tolerance model and theoretically show its NP-completeness. The main contribution is to prove that our multihybrid job scheduling (MJS) scheme confidently guarantees the fault-tolerant performance by adaptively combining jobs and resources with different rescheduling policies in MPDP. Furthermore, we demonstrate that the proposed MJS scheme outperforms the five rescheduling heuristics in solution quality, searching adaptability and time efficiency by conducting a set of extensive simulations under various scheduling conditions.     

Robust resource allocation in a cluster based imaging system

Recently there has been an increased demand for imaging systems in support of high-speed digital printing. The required increase in performance in support of such systems can be accomplished through an effective parallel execution of image processing applications in a distributed cluster computing environment. The output of the system must be presented to a raster based display at regular intervals, effectively establishing a hard deadline for the production of each image. Failure to complete a rasterization task before its deadline will result in an interruption of service that is unacceptable. The goal of this research was to derive a metric for measuring robustness in this environment and to design a resource allocation heuristic capable of completing each rasterization task before its assigned deadline, thus, preventing any service interruptions. We present a mathematical model of such a cluster based raster imaging system, derive a robustness metric for evaluating heuristics in this environment, and demonstrate using the metric to make resource allocation decisions. The heuristics are evaluated within a simulation of the studied raster imaging system. We clearly demonstrate the effectiveness of the heuristics by comparing their results with the results of a resource allocation heuristic commonly used in this type of system.     

一个快速的时延有界低代价多播路由算法

基于ＱｏＳ的多播路由算法需要在满足每个个体ＱｏＳ需求的同时,又能高效管理网络资源,提出了一种满足端端时延限制的低代价多播路由算法。算法使用一个修改的Ｓｔｅｉｎｅｒ树近似算法先构建时延有界的低代价多播树,再通过最小时延路径与其它尚不在多播树的且结点相连。     

Predictive performance modeling for distributed batch processing using black box monitoring and machine learning

In many domains, the previous decade was characterized by increasing data volumes and growing complexity of data analyses, creating new demands for batch processing on distributed systems. Effective operation of these systems is challenging when facing uncertainties about the performance of jobs and tasks under varying resource configurations, e. g., for scheduling and resource allocation. We survey predictive performance modeling (PPM) approaches to estimate performance metrics such as execution duration, required memory or wait times of future jobs and tasks based on past performance observations. We focus on non-intrusive methods, i. e., methods that can be applied to any workload without modification, since the workload is usually a black box from the perspective of the systems managing the computational infrastructure. We classify and compare sources of performance variation, predicted performance metrics, limitations and challenges, required training data, use cases, and the underlying prediction techniques. We conclude by identifying several open problems and pressing research needs in the field.     

An improved heuristic for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is an important and practical problem in the OR literature. In short, the problem is to identify routes to service (e.g., pickup or deliver) demand located along the edges of a network such that the total cost of the routes is minimized. In general, a single route cannot satisfy the entire demand due to capacity constraints on the vehicles. CARP belongs to the set of NP-hard problems; consequently numerous heuristic and metaheuristic solution approaches have been developed to solve it. In this paper an “ellipse rule” based heuristic is proposed for the CARP. This approach is based on the path-scanning heuristic, one of the mostly used greedy-add heuristics for this problem. The innovation consists basically of selecting edges only inside ellipses when the vehicle is near the end of each route. This new approach was implemented and tested on three standard datasets and the solutions are compared against: (i) the original path-scanning heuristic; (ii) two other path-scanning heuristics and (iii) the three best known metaheuristics. The results indicate that the “ellipse rule” approach lead to improvements over the three path-scanning heuristics, reducing the average distance to the lower bound in the test problems by about 44%.     

Scheduling algorithms for heterogeneous batch processors with incompatible job-families

We consider the problem of scheduling heterogeneous batch processors (i.e., batch processors with different capacity) with incompatible job-families and non-identical job sizes to maximize the utilization of the batch processors. We analyzed the computational complexity of this problem and showed that it is NP-hard and proposed eight variants of a fast greedy heuristic. A series of computational experiments were carried out to compare the performance of the heuristics and showed that the heuristics are capable of consistently obtaining near (estimated) optimal solutions with very low-computational burden for large-scale problems. We also carried out a study to find the effect of family processing time changes on the performance of the heuristics. This sensitivity analysis indicated that the processing time set of job-families influences the performance of the heuristic algorithms.     

Deadline and energy constrained dynamic resource allocation in a heterogeneous computing environment

Energy-efficient resource allocation within clusters and data centers is important because of the growing cost of energy. We study the problem of energy-constrained dynamic allocation of tasks to a heterogeneous cluster computing environment. Our goal is to complete as many tasks by their individual deadlines and within the system energy constraint as possible given that task execution times are uncertain and the system is oversubscribed at times. We use Dynamic Voltage and Frequency Scaling (DVFS) to balance the energy consumption and execution time of each task. We design and evaluate (via simulation) a set of heuristics and filtering mechanisms for making allocations in our system. We show that the appropriate choice of filtering mechanisms improves performance more than the choice of heuristic (among the heuristics we tested).     

Security‐aware scheduling model for computational grid

Grid applications with stringent security requirements introduce challenging concerns because the schedule devised by nonsecurity‐aware scheduling algorithms may suffer in scheduling security constraints tasks. To make security‐aware scheduling, estimation and quantification of security overhead is necessary. The proposed model quantifies security, in the form of security levels, on the basis of the negotiated cipher suite between task and the grid‐node and incorporates it into existing heuristics MinMin and MaxMin to make it security‐aware MinMin(SA) and MaxMin(SA). It also proposes SPMaxMin (Security Prioritized MinMin) and its comparison with three heuristics MinMin(SA), MaxMin(SA), and SPMinMin on heterogeneous grid/task environment. Extensive computer simulation results reveal that the performance of the various heuristics varies with the variation in computational and security heterogeneity. Its analysis over nine heterogeneous grid/task workload situations indicates that an algorithm that performs better for one workload degrades in another. It is conspicuous that for a particular workload one algorithm gives better makespan while another gives better response time. Finally, a security‐aware scheduling model is proposed, which adapts itself to the dynamic nature of the grid and picks the best suited algorithm among the four analyzed heuristics on the basis of job characteristics, grid characteristics, and desired performance metric. Copyright © 2011 John Wiley & Sons, Ltd.     

Stochastic robustness metric and its use for static resource allocations

This research investigates the problem of robust static resource allocation for distributed computing systems operating under imposed Quality of Service (QoS) constraints. Often, such systems are expected to function in a physical environment replete with uncertainty, which causes the amount of processing required to fluctuate substantially over time. Determining a resource allocation that accounts for this uncertainty in a way that can provide a probabilistic guarantee that a given level of QoS is achieved is an important research problem. The stochastic robustness metric proposed in this research is based on a mathematical model where the relationship between uncertainty in system parameters and its impact on system performance are described stochastically.The utility of the established metric is then exploited in the design of optimization techniques based on greedy and iterative approaches that address the problem of resource allocation in a large class of distributed systems operating on periodically updated data sets. The performance results are presented for a simulated environment that replicates a heterogeneous cluster-based radar data processing center. A mathematical performance lower bound is presented for comparison analysis of the heuristic results. The lower bound is derived based on a relaxation of the Integer Linear Programming formulation for a given resource allocation problem.