检索结果-内蒙古大学图书馆

Requirement-Aware Scheduling of bag-of-tasks applications on Grids with Dynamic Resilience

IEEE TRANSACTIONS ON COMPUTERS 2013年第10期62卷 2108-2114页

作者： Hu, Menglan Veeravalli, Bharadwaj Natl Univ Singapore Commun & Networks Lab Dept Elect & Comp Engn Singapore 117576 Singapore

Grids have been extensively deployed to handle various scientific and engineering applications that can be structured as bag-of-tasks (BoT). The scheduling of BoT applications on Grids is an important issue for achieving high performance. Grid scheduling involves a number of challenging issues, mainly due to the dynamic nature of the Grid. To deal with this dynamic nature, in this paper, we propose an online scheduling algorithm called prudent algorithm with replication (PAR) for scheduling Grid applications. PAR is shown to prudently make scheduling decisions in such a way that it can tolerate inaccurate performance predictions. Another point to note is that PAR adopts task duplication as an attempt to reduce serious schedule increases. Moreover, since the applications to be performed may widely vary in terms of their required hardware and software, we also capture the loads' various processing requirements in our algorithms, a unique feature that is applicable for running proprietary applications only on certain eligible processing nodes. Thus, in our problem formulation each application can only be processed by certain processors as both the applications and processing nodes are heterogeneous. We then present a task selection policy, referred to as requirement-aware load selection (RALS) policy to handle the contention of multiple applications that have various processing requirements but share the same computing resources. Based on RALS and PAR, we develop two scheduling algorithms: requirement-aware prudent algorithm with replication (RAPAR), and requirement-aware knowledge-free algorithm with replication (RAKAR). RAPAR and RAKAR address the scheduling of multiple BoT applications with heterogeneous processing requirements on Grids. RAPAR works in scenarios where inaccurate performance prediction information is provided whereas RAKAR works without any prediction information. Performance evaluation results are presented to demonstrate the effectiveness and compe

关键词： Task scheduling grid computing bag-of-tasks applications parallel computing

来源：评论

学校读者我要写书评

暂无评论

GA-based cloud resource estimation for agent-based execution of bag-of-tasks applications

引用

INFORMATION SYSTEMS FRONTIERS 2012年第4期14卷 925-951页

作者： Gutierrez-Garcia, J. Octavio Sim, Kwang Mong Gwangju Inst Sci & Technol Dept Informat & Commun Kwangju 500712 South Korea

Executing bag-of-tasks applications in multiple Cloud environments while satisfying both consumers' budgets and deadlines poses the following challenges: How many resources and how many hours should be allocated? What types of resources are required? How to coordinate the distributed execution of bag-of-tasks applications in resources composed from multiple Cloud providers?. This work proposes a genetic algorithm for estimating suboptimal sets of resources and an agent-based approach for executing bag-of-tasks applications simultaneously constrained by budgets and deadlines. Agents (endowed with distributed algorithms) compose resources and coordinate the execution of bag-of-tasks applications. Empirical results demonstrate that the genetic algorithm can autonomously estimate sets of resources to execute budget-constrained and deadline-constrained bag-of-tasks applications composed of more economical (but slower) resources in the presence of loose deadlines, and more powerful (but more expensive) resources in the presence of large budgets. Furthermore, agents can efficiently and successfully execute randomly generated bag-of-tasks applications in multi-Cloud environments.

关键词： Cloud resource estimation bag-of-tasks applications Cloud resource management Multiagent systems Genetic algorithms Cloud computing

来源：评论

学校读者我要写书评

暂无评论

Improving scalability of bag-of-tasks applications running on master-slave platforms

引用

PARALLEL COMPUTING 2009年第2期35卷 57-71页

作者： da Silva, Fabricio A. B. Senger, Hermes Univ Lisbon Dept Informat Fac Ciencias P-1200 Lisbon Portugal Univ Presbiteriana Mackenzie Fac Comp & Informat Sao Paulo Brazil Univ Catolica Santos Santos Brazil

bag-of-tasks applications are parallel applications composed of independent tasks. Examples of bag-of-tasks (BoT) applications include Monte Carlo simulations, massive searches (such as key breaking), image manipulation applications and data mining algorithms. This paper analyzes the scalability of bag-of-tasks applications running on master-slave platforms and proposes a scalability-related measure dubbed input file affinity. In this work, we also illustrate how the input file affinity, which is a characteristic of an application, can be used to improve the scalability of bag-of-tasks applications running on master-slave platforms. The input file affinity was considered in a new scheduling algorithm dubbed Dynamic Clustering, which is oblivious to task execution times. We compare the scalability of the Dynamic Clustering algorithm to several other algorithms, oblivious and non-oblivious to task execution times, proposed in the literature. We show in this paper that, in several situations, the oblivious algorithm Dynamic Clustering has scalability performance comparable to non-oblivious algorithms, which is remarkable considering that our oblivious algorithm uses much less information to schedule tasks. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Master-slave platforms Scalability analysis bag-of-tasks applications

来源：评论

学校读者我要写书评

暂无评论

Cost minimization for deadline-constrained bag-of-tasks applications in federated hybrid clouds

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2017年 71卷 113-128页

作者： Abdi, Somayeh PourKarimi, Latif Ahmadi, Mahmood Zargari, Farzad Islamic Azad Univ Dept Comp Engn Sci & Res Branch Tehran Iran Razi Univ Dept Math Kermanshah Iran Razi Univ Comp Engn & Informat Technol Dept Kermanshah Iran Iran Telecom Res Ctr Informat Technol Fac Tehran Iran

A mathematical programming model is proposed for a resource allocation problem in federated clouds, where bag-of-tasks (BoT) applications are assigned to instance types with different costs and performance levels. The proposed model is a binary linear programming problem containing deadline and resource constraints in the cloud federations and by the objective of minimizing the total cost of applications. These constraints and objective are explicitly expressed using mathematical functions, and the model is solved with the CPLEX solver. This paper also discusses a post-optimality analysis that deals with stability in assignment problems. Numerical results show that the optimal cost and optimal solutions in the cloud federations are lower and more stable, respectively, than those presented by single-provider clouds. In contrast to optimality in single-provider clouds, that in the cloud federations is less sensitive to input data. (C) 2017 Published by Elsevier B.V.

关键词： Federated hybrid clouds Scheduling bag-of-tasks applications Binary linear programming Cost minimization Deadline constrained

来源：评论

学校读者我要写书评

暂无评论

Practical scheduling of bag-of-tasks applications on grids with dynamic resilience

引用

IEEE TRANSACTIONS ON COMPUTERS 2007年第6期56卷 815-825页

作者： Lee, Young Choon Zomaya, Albert Y. Univ Sydney Sch Informat Technol Sydney NSW 2006 Australia

Over the past decade, the grid has emerged as an attractive platform to tackle various large-scale problems, especially in science and engineering. One primary issue associated with the efficient and effective utilization of heterogeneous resources in a grid is scheduling. Grid scheduling involves a number of challenging issues, mainly due to the dynamic nature of the grid. There are only a handful of scheduling schemes for grid environments that realistically deal with this dynamic nature that have been proposed in the literature. In this paper, two novel scheduling algorithms, called the Shared-Input-data-based Listing (SIL) algorithm and the Multiple Queues with Duplication (MQD) algorithm for bag-of-tasks (BoT) applications in grid environments are proposed. The SIL algorithm targets scheduling data-intensive BoT (DBoT) applications, whereas the MOD algorithm deals with scheduling computationally intensive BoT (CBoT) applications. Their common and primary forte is that they make scheduling decisions without fully accurate performance prediction information. Another point to note is that both scheduling algorithms adopt task duplication as an attempt to reduce serious schedule increases. Our evaluation study employs a number of experiments with various simulation settings. The results show the practicability and competitiveness of our algorithms when compared to existing methods.

关键词： scheduling grids grid computing parallel computing bag-of-tasks applications

来源：评论

学校读者我要写书评

暂无评论

Stochastic Scheduling for bag-of-tasks applications with Uncertain Task Durations in Cloud Computing Environments

Stochastic Scheduling for Bag-of-Tasks Applications with Unc...

引用

IEEE International Conference on Recent Advances in Systems Science and Engineering (RASSE)

作者： Yin, Lu Sun, Jin Zhang, Yi Wu, Zebin Nanjing Univ Sci & Technol Sch Comp Sci & Engn Nanjing 210094 Peoples R China

ISBN: (纸本)9781665434416

Scheduling bag-of-tasks (BoT) applications, which consist of many independent tasks, has been a challenging problem in cloud computing environments. Most existing BoT scheduling algorithms fail to consider the uncertainty of the task duration in actual situations, and regard task durations as fixed values that are pre-determined. Taking uncertain task durations into account, this paper establishes a stochastic optimization model for the BoT scheduling problem with the optimization objective of minimizing the user's cost for using cloud computing resources. The optimization model formulates each task's duration time as a normally distributed random variable, and imposes a stochastic deadline constraint on each BoT application's makespan, under which the application must be completed before a user-specified deadline in a probabilistic sense. We further design a stochastic BoT scheduling (SBS) metaheuristic to solve this stochastic scheduling problem. For each candidate scheduling solution, the proposed SBS employs a task assignment strategy to designate BoT tasks onto virtual machine instances under uncertain task durations as well as probabilistic deadline constraints. In this manner, the quality of each solution can be evaluated. An iterative procedure is performed to explore the best solution with the highest quality. Experimental results justify that the uncertainty-aware SBS algorithm can not only guarantee the satisfaction of probabilistic deadline constraints but also substantially reduce the user's cost.

关键词： stochastic scheduling bag-of-tasks applications cloud computing probabilistic constraint

来源：评论

学校读者我要写书评

暂无评论

Scheduling bag-of-tasks applications to Optimize Computation Time and Cost 1

引用

10th International Conference on Parallel Processing and Applied Mathematics (PPAM)

作者： Grekioti, Anastasia Shakhlevich, Natalia V. Univ Leeds Sch Comp Leeds LS2 9JT W Yorkshire England

ISBN: (数字)9783642551956

ISBN: (纸本)9783642551956

bag-of-tasks applications consist of independent tasks that can be performed in parallel. Although such problems are well known in classical scheduling theory, the distinctive feature of Grid and cloud applications is the importance of the cost factor: in addition to the traditional scheduling criterion of minimizing computation time, in Grids and clouds it also important to minimize the cost of using resources. We study the structural properties of the time/cost model and explore how the existing scheduling techniques can be extended to handle the additional cost criterion. Due to the dynamic nature of distributed systems, one of the major requirements to scheduling algorithms is related to their speed. The heuristics we propose are fast and, as we show in our experiments, they compare favourably with the existing scheduling algorithms for distributed systems.

关键词： Scheduling bag-of-tasks applications Heuristics

来源：评论

学校读者我要写书评

暂无评论

Running bag-of-tasks applications on computational grids:: The MyGrid approach

Running Bag-of-Tasks applications on computational grids:: T...

引用

International Conference on Parallel Processing

作者： Cirne, W Paranhos, D Costa, L Santos-Neto, E Brasileiro, F Sauvé, J Silva, FAB Barros, CO Silveira, C Univ. Fed. de Campina Grande Brazil

ISBN: (纸本)0769520170

We here discuss how to run bag-of-tasks applications on computational grids. bag-of-tasks applications (those parallel applications whose tasks are independent) are both relevant and amendable for execution on grids. However, few users currently execute their bag-of-tasks applications on grids. We investigate the reason for this state of affairs and introduce MyGrid, a system designed to overcome the identified difficulties. MyGrid provides a simple, complete and secure way for a user to run bag-of-tasks applications on all resources she has access to. Besides putting together a complete solution useful for real users, MyGrid embeds two important research contributions to grid computing. First, we introduce some simple working environment abstractions that hide machine configuration heterogeneity from the user. Second, we introduce Work Queue with Replication (WQR), a scheduling heuristics that attains good performance without relying on information about the grid or the application, although consuming a few more cycles. Note that not depending on information makes WQR much easier to deploy in practice.

关键词： grid computing processor scheduling parallel processing bag-of-tasks applications computational grid MyGrid approach scheduling heuristic machine configuration work queue replication WQR Grid computing computational grids Machine Configuration scheduling of multiprocessor PARALLEL PROCESSING (COMPUTERS)

来源：评论

学校读者我要写书评

暂无评论

A Novel Firefly Algorithm for Scheduling bag-of-tasks applications Under Budget Constraints on Hybrid Clouds

引用

IEEE ACCESS 2019年 7卷 151888-151901页

作者： Zhang, Yi Zhou, Junlong Sun, Lulu Mao, Jingjing Sun, Jin Nanjing Univ Sci & Technol Sch Comp Sci & Engn Nanjing 210094 Jiangsu Peoples R China

This paper aims at scheduling bag-of-tasks (BoT) applications under budget constraints on hybrid clouds for minimizing the makespan. To solve this NP-hard problem, we propose a novel firefly algorithm (NFA) in which the evaluation of a firefly consists of two steps: (1) mapping a firefly to a scheduling solution (a task sequence);(2) calculating the solutions objective (its corresponding makespan). In the first step, different from the well-known ranked-order value (ROV) rule, we propose a distance-based mapping operator that relies on the distance between a firefly and the brightest one to determine the mapping relationship between a firefly and a solution. We use a probability model in which solutions corresponding to fireflies closer to the brightest one would have higher probabilities to inherit tasks from the current best solution. In this manner, these solutions can inherit more good genes hidden inside the current best solution to evolve into more high-quality solutions. In the second step, we employ an effective heuristic to evaluate solution objectives. We further develop a composite heuristic to generate the initial best solution, providing the proposed NFA with a good start. We also establish a new movement scheme such that fireflies distant from the brightest one can explore a wide range in the search space, whereas fireflies nearby the brightest one can search in a small neighborhood. Experimental results show that, by employing the above-mentioned strategies, NFA outperforms the standard firefly algorithm and the existing best algorithm, in terms of scheduling effectiveness and computational efficiency. Specifically, the distance-based mapping operator is verified to be both more effective and more efficient than the ROV rule. The composite heuristic is capable of generating a good initial solution, leading to the high quality of the final schedule. The movement scheme can further reduce the makespan of BoT applications.

关键词： Cloud computing Task analysis Scheduling Processor scheduling Optimization Schedules Sun bag-of-tasks applications hybrid clouds makespan firefly algorithms

来源：评论

学校读者我要写书评

暂无评论

A stochastic algorithm for scheduling bag-of-tasks applications on hybrid clouds under task duration variations

引用

JOURNAL OF SYSTEMS AND SOFTWARE 2022年 184卷

作者： Yin, Lu Zhou, Junlong Sun, Jin Nanjing Univ Sci & Technol Sch Comp Sci & Engn 200 Xiaolingwei St Nanjing 210094 Peoples R China

Hybrid cloud computing, which typically involves a hybrid architecture of public and private clouds, is an ideal platform for executing bag-of-tasks (BoT) applications. Most existing BoT scheduling algorithms ignore the uncertainty of task execution times in practical scenarios and schedule tasks by assuming that the task durations can be determined accurately in advance, often leading to the violation of the deadline constraint. In view of this fact, this paper devotes to maximizing the profit of the private cloud provider while guaranteeing the quality-of-service provided by the cloud platform, through designing an effective stochastic BoT scheduling algorithm based on the distribution of task duration variations. With the varying task execution times modeled as random variables, we formulate a stochastic scheduling framework that incorporates a probabilistic constraint upon the makespans of BoT applications. The resultant stochastic optimization model is capable of characterizing the complete distribution information of makespan variations and satisfying the deadline constraint in a probabilistic sense. We further design an immune algorithm-based metaheuristic to solve this stochastic optimization problem. Simulations results justify that our proposed algorithm outperforms several competing algorithms in maximizing the cloud provider's profit while satisfying the user-specified deadline constraint under the impact of uncertain task durations. (C) 2021 Elsevier Inc. All rights reserved.

关键词： bag-of-tasks applications Hybrid clouds Stochastic task scheduling Probabilistic constraint Profit maximization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：