Energy constrained resource allocation optimization for mobile grids

A mobile grid incorporates mobile devices into Grid systems. But mobile devices at present have severe limitations in terms of processing, memory capabilities and energy. Minimizing the energy usage in mobile devices poses significant challenges in mobile grids. This paper presents energy constrained resource allocation optimization for mobile grids. The goal of the paper is not only to reduce energy consumption, but also to improve the application utility in a mobile grid environment with a limited energy charge, ensuring battery lifetime and the deadlines of the grid applications. The application utility not only depends on its allocated resources including computation and communication resources, but also on the consumed energy, this leads to a coupled utility model, where the utilities are functions of allocated resources and consumed energy. Energy constrained resources allocation optimization is formulated as a utility optimization problem, which can be decomposed into two subproblems, the interaction between the two sub-problems is controlled through the use of a pricing variable. The paper proposes a price-based distributed energy constrained resources allocation optimization algorithm. In the simulation, the performance evaluation of our energy constrained resources allocation optimization algorithm is conducted.     

Integrating best effort and fixed priority scheduling

Adaptive and dynamic behaviour is seen as one of the key characteristics of next generation hard real-time systems. Whilst fixed priority pre-emptive scheduling is becoming a de facto standard in real-time system implementation, it remains inflexible in its purest form. One approach to countering this criticism is to allow optional components, not guaranteed offline, to be executed at run-time. Optional components may be guaranteed a minimum set of resources at run-time, with competing resource requests scheduled according to the best-effort approach. This allows increased dynamic behaviour and improves the utility of the system. In this paper, we discuss this integration of fixed priority and best-effort scheduling.     

Autonomous and adaptive resource allocation among multiple nodes and multiple applications in heterogeneous wireless networks

In the forthcoming future, various means of wireless communication, such as cellular, Wi-Fi, WiMAX, and DSRC, will be available to mobile users and applications. With the development of wireless communication and mobile devices, more and more users and applications will be accommodated in mobile environment. Since mobile users and applications compete for the limited wireless resources whose communication quality dynamically change, we need an adaptive mechanism for mobile users and applications to share the available network resources while satisfying each application?s QoS requirements. In this paper, we propose an adaptive resource allocation mechanism where each node autonomously determines wireless network resources to assign to each of networked applications running on it. For this purpose, we adopt an attractor composition model, which is based on an autonomous and adaptive behavior of biological systems. Through numerical analysis, we confirmed that our mechanism could adaptively and stably allocate wireless network resources to applications, while considering their QoS requirements and fairly sharing network resources with other nodes. It also is shown that our mechanism superiors to a mechanism where a node determines resource allocation by solving an optimization problem.     

Survey on Grid Resource Allocation Mechanisms

Grid is a distributed high performance computing paradigm that offers various types of resources (like computing, storage, communication) to resource-intensive user tasks. These tasks are scheduled to allocate available Grid resources efficiently to achieve high system throughput and to satisfy user requirements. The task scheduling problem has become more complex with the ever increasing size of Grid systems. Even though selecting an efficient resource allocation strategy for a particular task helps in obtaining a desired level of service, researchers still face difficulties in choosing a suitable technique from a plethora of existing methods in literature. In this paper, we explore and discuss existing resource allocation mechanisms for resource allocation problems employed in Grid systems. The work comprehensively surveys Gird resource allocation mechanisms for different architectures (centralized, distributed, static or dynamic). The paper also compares these resource allocation mechanisms based on their common features such as time complexity, searching mechanism, allocation strategy, optimality, operational environment and objective function they adopt for solving computing- and data-intensive applications. The comprehensive analysis of cutting-edge research in the Grid domain presented in this work provides readers with an understanding of essential concepts of resource allocation mechanisms in Grid systems and helps them identify important and outstanding issues for further investigation. It also helps readers to choose the most appropriate mechanism for a given system/application.     

Characterization of Bandwidth-Aware Meta-Schedulers for Co-Allocating Jobs Across Multiple Clusters

In this paper, we present a bandwidth-centric job communication model that captures the interaction and impact of simultaneously co-allocating jobs across multiple clusters. We compare our dynamic model with previous research that utilizes a fixed execution time penalty for co-allocated jobs. We explore the interaction of simultaneously co-allocated jobs and the contention they often create in the network infrastructure of a dedicated computational multi-cluster.We also present several bandwidth-aware co-allocating meta-schedulers. These schedulers take inter-cluster network utilization into account as a means by which to mitigate degraded job run-time performance. We make use of a bandwidth-centric parallel job communication model that captures the time-varying utilization of shared inter-cluster network resources. By doing so, we are able to evaluate the performance of multi-cluster scheduling algorithms that focus not only on node resource allocation, but also on shared inter-cluster network bandwidth.     

融合遗传算法和蚁群算法动态网格任务调度算法研究

网格计算是当今计算机科学领域最新兴起的一项有很高学术价值和应用价值的研究课题。未来互联网的发展方向是将网络中众多闲置的计算资源、存储资源以及科学仪器等可用资源充分合理的加以利用。如何高效地使用网格资源,即网格调度问题也随之成为研究的重点,虽然在传统的分布式并行计算中有很多成熟的任务调度算法,但由于网格的新特性,使得必须研究新的算法来解决一些新出现的问题,如调度问题的NP安全性,调度算法的高效性,资源的异构性以及资源分配决策的并行性和分布性等。     

The Prospero Resource Manager: A scalable framework for processor allocation in distributed systems

Existing techniques for allocating processors in parallel and distributed systems are not suitable for use in large distributed systems. In such systems, dedicated multiprocessors should exist as an integral component of the distributed system, and idle processors should be available to applications that need them. The Prospero Resource Manager (PRM) is a scalable resource allocation system that supports the allocation of processing resources in large networks and on multiprocessor systems. PRM employs three types of managers-the job manager, the system manager and the node manager-to manage resources in a distributed system. Multiple independent instances of each type of manager exist, reducing bottlenecks. When making scheduling decisions each manager utilizes information most closely associated with the entities for which it is responsible.     

Note on a unified approach to the single-machine scheduling problem with a deterioration effect and convex resource allocation

In many resource allocation problems in physical or economic systems, a linear resource consumption function is commonly considered, and job processing times are assumed to be fixed parameters. However, the former assumption fails to reflect the law of diminishing returns, and the latter may be controlled by changing the allocation of resources to jobs. Motivated by these observations, we provide a unified model for solving single-machine scheduling problems in which each job's processing time is a function of its starting time and convex resource allocation. The objective is to find the optimal sequence of jobs subject to a limited resource consumption. We first show how this unified model can be useful in solving scheduling problems under due date assignment considerations. We analyze the problem with four different due date assignment methods, and our objective function includes costs for earliness, tardiness and due date assignments. We also consider scheduling problems without involving due date assignment decisions. The objective function is to minimize the makespan, total completion time, total absolute variation in completion times, and total absolute variation in waiting times. We show that several existing well-known problems can be reduced to a special case of our unified model and solved in O(nlogn) time.     

Tabu search based resource allocation in radiological examination process execution

Efficient resource scheduling and allocation in radiological examination process (REP) execution is a key requirement to improve patient throughput and radiological resource utilization and to manage unexpected events that occur when resource scheduling and allocation decisions change due to clinical needs. In this paper, a Tabu search based approach is presented to solve the resource scheduling and allocation problems in REP execution. The primary objective of the approach is to minimize a weighted sum of average examination flow time, average idle time of the resources, and delays. Unexpected events, i.e., emergent or absent examinations, are also considered. For certain parameter combinations, the optimal solution of radiological resource scheduling and allocation is found, while considering the limitations such as routing and resource constraints. Simulations in the application case are performed. Results show that the proposed approach makes efficient use of radiological resource capacity and improves the patient throughput in REP execution.     

5G超密集异构网络带内无线回传资源分配方案

为实现5G超密集异构网络中无线回传链路和接入链路之间的最优资源分配,研究多用户场景下双层异构网络的联合用户调度和功率分配问题,在队列稳定和无线回传资源有限的情况下,综合考虑用户调度、功率分配和干扰控制等因素,对带内无线回传的最优资源分配问题进行数学建模并求解,基于李雅普诺夫优化理论提出联合用户调度和功率分配的优化算法。将优化问题解耦为网络内各个用户的调度以及宏基站和小基站的功率分配过程,采用MOSEK求解器和二分类方法获得用户调度向量,利用拉格朗日乘子法求解功率分配问题,并通过队列的时刻更新过程实现最优资源分配。仿真结果表明,在多用户场景下,该方案能够有效提升网络总吞吐量以及网络效用,并且毫米波频段的通信性能优于传统蜂窝网络频段。     

Energy efficient and robust allocation of interdependent tasks on mobile ad hoc computational grid

A mobile ad hoc computational grid is a distributed computing infrastructure that allows mobile nodes to share computing resources in a mobile ad hoc environment. Compared to traditional distributed systems such as grids and clouds, resource allocation in mobile ad hoc computational grids is not straightforward because of node mobility, limited battery power and an infrastructure‐less network environment. The existing schemes are either based on a decentralized architecture that results in poor allocation decisions or assume independent tasks. This paper presents a scheme that allocates interdependent tasks and aims to reduce task completion time and the amount of energy consumed in transmission of data. This scheme comprises two key algorithms: resource selection and resource allocation. The resource selection algorithm is designed to select nodes that remain connected for a longer period, whereas the resource assignment or allocation algorithm is developed to allocate interdependent tasks to the nodes that are accessible at the minimum transmission power. The scheme is based on a hybrid architecture that results in effective allocation decisions, reduces the communication cost associated with the exchange of control information, and distributes the processing burden among the nodes. The paper also investigates the relationship between the data transfer time and transmission energy consumption and presents a power‐based routing protocol to reduce data transfer costs and transmission energy consumption. Copyright © 2014 John Wiley & Sons, Ltd.     

Market-oriented Grids and Utility Computing: The State-of-the-art and Future Directions

Traditional resource management techniques (resource allocation, admission control and scheduling) have been found to be inadequate for many shared Grid and distributed systems, that consist of autonomous and dynamic distributed resources contributed by multiple organisations. They provide no incentive for users to request resources judiciously and appropriately, and do not accurately capture the true value, importance and deadline (the utility) of a user’s job. Furthermore, they provide no compensation for resource providers to contribute their computing resources to shared Grids, as traditional approaches have a user-centric focus on maximising throughput and minimising waiting time rather than maximising a providers own benefit. Consequently, researchers and practitioners have been examining the appropriateness of ‘market-inspired’ resource management techniques to address these limitations. Such techniques aim to smooth out access patterns and reduce the chance of transient overload, by providing a framework for users to be truthful about their resource requirements and job deadlines, and offering incentives for service providers to prioritise urgent, high utility jobs over low utility jobs. We examine the recent innovations in these systems (from 2000–2007), looking at the state-of-the-art in price setting and negotiation, Grid economy management and utility-driven scheduling and resource allocation, and identify the advantages and limitations of these systems. We then look to the future of these systems, examining the emerging ‘Catallaxy’ market paradigm. Finally we consider the future directions that need to be pursued to address the limitations of the current generation of market oriented Grids and Utility Computing systems.     

A novel approach for traffic accidents sanitary resource allocation based on multi-objective genetic algorithms

The development of communication technologies integrated in vehicles allows creating new protocols and applications to improve assistance in traffic accidents. Combining this technology with intelligent systems will permit to automate most of the decisions needed to generate the appropriate sanitary resource sets, thereby reducing the time from the occurrence of the accident to the stabilization and hospitalization of the injured passengers. However, generating the optimal allocation of sanitary resources is not an easy task, since there are several objectives that are mutually exclusive, such as assistance improvement, cost reduction, and balanced resource usage. In this paper, we propose a novel approach for the sanitary resources allocation in traffic accidents. Our approach is based on the use of multi-objective genetic algorithms, and it is able to generate a list of optimal solutions accounting for the most representative factors. The inputs to our model are: (i) the accident notification, which is obtained through vehicular communication systems, and (ii) the severity estimation for the accident, achieved through data mining. We evaluate our approach under a set of vehicular scenarios, and the results show that a memetic version of the NSGA-II algorithm was the most effective method at locating the optimal resource set, while maintaining enough variability in the solutions to allow applying different resource allocation policies.     

基于效用的超宽带系统带宽分配

把超宽带系统的带宽优化调度表示为一个效用最大化的问题。对于系统的带宽分配,效用函数是服务质量的有效度量,它反映了用户对所分配的资源的满意程度。针对超宽带无线网络带宽分配中链路和用户的集中式算法的复杂性,用分布式方案解决这种问题,以自适应变化的无线网络环境。对系统带宽进行基于效用的分配,满足超宽带系统高速率传输的需要。     

Adaptive energy efficient scheduling in Peer-to-Peer desktop grids

We address non-preemptive scheduling problems on heterogeneous P2P grids, where resources are changing over time, and scheduling decisions are free from information of application characteristics. We consider a scheduling with task replications to overcome possible bad resource allocation in presence of uncertainty, and ensure good performance. We analyze the energy consumption of job allocation strategies exploring the replication thresholds, and dynamic component deactivation. The main idea of our approach is to set replication thresholds, and dynamically adapt them to cope with different objective preferences, workloads, and Grid properties. We compare three groups of strategies: knowledge-free, speed-aware, and power-aware. In order to provide good performance and minimize energy consumption, first, we perform a joint analysis of two metrics considering their degradation in performance. Then, we provide two-objective optimization analysis that is not restricted to find a unique solution, but the Pareto optimal set. Based on these results, we use a Set Coverage metric for assessing the performance of our strategies and compare twenty algorithms in terms of Pareto dominance. A case study is given, and corresponding results indicate that two replicas for knowledge-free algorithms, and one replica for speed-aware algorithms provide the best energy and performance trade-offs in the scheduling. They perform well in different scenarios with a variety of workloads and grid configurations.     

A hybrid design-time/run-time scheduling flow to minimise the reconfiguration overhead of FPGAs

Current multimedia applications are characterized by highly dynamic and non-deterministic behaviour as well as high-performance requirements. Potentially, partially reconfigurable fine-grain configurable architectures like FPGAs can be reconfigured at run-time to match the dynamic behaviour. However, the lack of programming support for dynamic task placement as well as the large configuration overhead has prevented their use for highly dynamic applications. To cope with these two problems, we have adopted an FPGA model with specific support for task allocation. On top of this model, we have applied an existing hybrid design-time/run-time scheduling flow initially developed for multiprocessor systems. Finally, we have extended this flow with specific modules that greatly reduce the reconfiguration overhead making it affordable for current multimedia applications.     

Credit-based scheme for security-aware and fairness-aware resource allocation in cloud computing

Cloud computing systems include different types of participants with varied requirements for resources and multiple tasks; these varying requirements must be considered in the design of fairness-aware resource allocation schemes for better resources sharing. However, some participants may be malicious with a goal to damage the resource allocation fairness and increase their own utility. Hence, the resource scheduling policy must guarantee allocation fairness among the participants; further, it must ensure that fairness is not affected by the malicious usage of resources, that could cause resource exhaustion and lead to denial of service. In order to address this challenge, we propose a credit-based mechanism for resource allocation that will avoid the malicious usage of resources and, simultaneously, guarantee allocation fairness. In our scheme, a credit factor is introduced for each participant in order to evaluate the history of resource utilization and determine future resource allocation. Our model encourages a participant to release the occupied resources in timely manner after the completion of a task and imposes a punishment for malicious occupation of resources. We prove the fairness of our model and provide linear and variable gradient approaches to determine the credit factor for different scenarios. We simulate our model and perform experiments on a real cloud computing platform. The results prove the rationality, effectiveness and correctness of our approaches.     

Lagrangian relaxation and constraint generation for allocation and advanced scheduling

Diverse applications in manufacturing, logistics, health care, telecommunications, and computing require that renewable resources be dynamically scheduled to handle distinct classes of job service requests arriving randomly over slotted time. These dynamic stochastic resource scheduling problems are analytically and computationally intractable even when the number of job classes is relatively small. In this paper, we formally introduce two types of problems called allocation and advanced scheduling, and formulate their Markov decision process (MDP) models. We establish that these MDPs are “weakly coupled” and exploit this structural property to develop an approximate dynamic programming method that uses Lagrangian relaxation and constraint generation to efficiently make good scheduling decisions. In fact, our method is presented for a general class of large-scale weakly coupled MDPs that we precisely define. Extensive computational experiments on hundreds of randomly generated test problems reveal that Lagrangian decisions outperform myopic decisions with a statistically significant margin. The relative benefit of Lagrangian decisions is much higher for advanced scheduling than for allocation scheduling.     

CA-DAG: Modeling Communication-Aware Applications for Scheduling in Cloud Computing

This paper addresses performance issues of resource allocation in cloud computing. We review requirements of different cloud applications and identify the need of considering communication processes explicitly and equally to the computing tasks. Following this observation, we propose a new communication-aware model of cloud computing applications, called CA-DAG. This model is based on Directed Acyclic Graphs that in addition to computing vertices include separate vertices to represent communications. Such a representation allows making separate resource allocation decisions: assigning processors to handle computing jobs, and network resources for information transmissions. The proposed CA-DAG model creates space for optimization of a number of existing solutions to resource allocation and for developing novel scheduling schemes of improved efficiency.