Deadline-sensitive workflow orchestration without explicit resource control
Journal of Parallel and Distributed ComputingPublished 9 December 2010
Lavanya Ramakrishnan, Jeffrey S. Chase, Dennis Gannon, Daniel Nurmi, Rich Wolski
Citations29
SJR quartileQ1
SJR score0.98
SNIP1.35
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Experimental results show that WORDS enables effective orchestration possible at reasonable costs on batch queue grid and cloud systems with or without explicit resource control.
Abstract
eScholarship provides open access, scholarly publishing services to the University of California and delivers a dynamic research platform to scholars worldwide.
Keywords
Computer ScienceDecision Sciences
Journal of Parallel and Distributed ComputingA Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems
1,715 Citations2001Tracy D. Braun, Howard Jay Siegel +9 more
It is shown that for the cases studied here, the relatively simple Min?min heuristic performs well in comparison to the other techniques, and one even basis for comparison and insights into circumstances where one technique will out-perform another.
Concurrency and Computation Practice and ExperienceScientific workflow management and the Kepler system
1,696 Citations2005Bertram Ludäscher, İlkay Altıntaş +7 more
Characteristics of and requirements for scientific workflows as identified in a number of application projects are described, and some key features of Kepler and its underlying Ptolemy II system, planned extensions, and areas of future research are described.
IEEE International Conference on High Performance Computing, Data, and AnalyticsThe cost of doing science on the cloud: the Montage example
584 Citations2008Ewa Deelman, Gurmeet Singh +3 more
Scientific ProgrammingScheduling Scientific Workflow Applications with Deadline and Budget Constraints Using Genetic Algorithms
388 Citations2006Jia Yu, Rajkumar Buyya
A genetic algorithm approach is presented to address scheduling optimization problems in workflow applications, based on two QoS constraints, deadline and budget, which are presented in this paper.
Lecture notes in computer scienceSNAP: A Protocol for Negotiating Service Level Agreements and Coordinating Resource Management in Distributed Systems
375 Citations2002Karl Czajkowski, Ian Foster +3 more
A resource management model is defined that distinguishes three kinds of resource-independent service level agreements (SLAs), formalizingag reements to deliver capability, perform activities, and bind activities to capabilities, respectively.
Task scheduling strategies for workflow-based applications in grids
365 Citations2005James M. Blythe, Shweta Jain +5 more
This work identifies two families of resource allocation algorithms: task-based algorithms, that greedily allocate tasks to resources, and workflow-based algorithms, that search for an efficient allocation for the entire workflow.
A quality of service architecture that combines resource reservation and application adaptation
325 Citations2002Ian Foster, A. Roy +1 more
A QoS architecture, GARA, is described that has been extended to support features of reservations and adaptation, and three examples of application-level adaptive strategies are used to show how this framework can permit applications to adapt both their resource requests and behavior in response to online sensor information.
Scheduling with advanced reservations
279 Citations2002Warren Smith, Ian Foster +1 more
This work proposes and evaluates several algorithms for supporting advanced reservation of resources in supercomputing scheduling systems and finds that the wait times of applications submitted to the queue increases when reservations are supported and the increase depends on how reservations aresupported.
Scheduling Workflows with Budget Constraints
248 Citations2007Rizos Sakellariou, Henan Zhao +2 more
This paper considers a basic model for workflow applications modelled as Directed Acyclic Graphs (DAGs) and investigates heuristics that allow to schedule the nodes of the DAG (or tasks of a workflow) onto resources in a way that satisfies a budget constraint and is still optimized for overall time.
Scheduling strategies for mapping application workflows onto the grid
184 Citations2005Anirban Mandal, Ken Kennedy +5 more
The results of the experiments show that the strategy of performance model based, in-advance heuristic workflow scheduling results in 1.5 to 2.2 times better makespan than other existing scheduling strategies.
Sharing networked resources with brokered leases
159 Citations2006David Irwin, Jeffrey S. Chase +4 more
This paper presents the design and implementation of Shirako, a system for on-demand leasing of shared networked resources, and shows how Shirako enables applications to lease groups of resources across multiple autonomous sites, adapt to the dynamics of resource competition and changing load, and guide configuration and deployment.
IEEE Intelligent SystemsArtificial intelligence and grids: workflow planning and beyond
144 Citations2004Yolanda Gil, Ewa Deelman +3 more
Pegasus, an AI planning system which is integrated into the grid environment that takes a user's highly specified desired results, generates valid workflows that take into account available resources, and submits the workflows for execution on the grid.
Toward a framework for preparing and executing adaptive grid programs
113 Citations2002Ken Kennedy, M. Mazina +11 more
The goal of this framework is to provide good resource allocation for Grid applications and to support adaptive reallocation if performance degrades because of changes in the availability of Grid resources.
Lecture notes in computer scienceThe Performance Impact of Advance Reservation Meta-scheduling
110 Citations2000Quinn Snell, Mark Clement +2 more
This research quantifies the impact of advance reservations on and outlines the algorithms that must be used to schedule metajobs and indicates that advance reservations can improve the response time for meetajobs, while not significantly impacting overall system performance.
Computing in Science & EngineeringService-oriented environments for dynamically interacting with mesoscale weather
100 Citations2005
Research that is enabling a major shift toward dynamically adaptive responses to rapidly changing environmental conditions is described.
Proceedings of the IEEEAgreement-Based Resource Management
94 Citations2005Karl Czajkowski, Ian Foster +1 more
A unifying resource management framework is presented in which to address the need to coordinate resource usage, the diversity of resource types and the variety of different management modes that may be used.
QBETS
77 Citations2007Daniel Nurmi, John Brevik +1 more
Most space-sharing parallel computers presently operated by high-performance computing centers use batch-queuing systems to manage processor allocation, which is a drag on productivity as it makes planning difficult and intellectual continuity hard to maintain.
Lecture notes in computer scienceQBETS: Queue Bounds Estimation from Time Series
59 Citations2008Daniel Nurmi, John Brevik +1 more
Grid scheduling and protocols---Evaluation of a workflow scheduler using integrated performance modelling and batch queue wait time prediction
57 Citations2006Daniel Nurmi, Anirban Mandal +4 more
This work augments an existing workflow scheduler through the introduction of methods which make accurate predictions of both the performance of the application on specific hardware, and the amount of time individual workflow tasks would spend waiting in batch queues.
Efficient resource description and high quality selection for virtual grids
54 Citations2005Yang-Suk Kee, Dionysios Logothetis +3 more
The results show that resource selection and binding for virtual grids of 10,000's of resources can scale up to grids with millions of resources, identifying good matches in less than one second, enabling applications to have high confidence in the results.
International Conference on e-ScienceApplication-Level Resource Provisioning on the Grid
41 Citations2006Gurmeet Singh, Carl Kesselman +1 more
It is shown that the GA paired with a list scheduling algorithm can obtain significantly better solutions than the Min-Min heuristic alone, and a cost model that combines the cost of resource allocation and the expected application runtime is evaluated.
Parallel scheduling of complex dags under uncertainty
31 Citations2005Grzegorz Malewicz
The goal is to find a regimen Ε, that dictates how workers get assigned to tasks (possibly in parallel and redundantly) throughout execution, so as to minimize expected completion time.
VARQ
26 Citations2008Daniel Nurmi, Rich Wolski +1 more
VARQ is described, a new method for job scheduling that provides users with probabilistic "virtual" advanced reservations using only existing best effort batch schedulers, and it is found that VARQ can implement a reservation capability probabilistically and that the effects of this Probabilistic approach are unlikely to negatively affect resource utilization.
Scalable Grid Application Scheduling via Decoupled Resource Selection and Scheduling
25 Citations2006Yang Zhang, Anirban Mandal +5 more
Leveraging the Virtual Grid abstraction, it is demonstrated that the decoupled approach is indeed both scalable and effective in large-scale and highly heterogeneous resource environments.
High Performance Distributed Computing
12 Citations2004
Cluster ComputingPredictable quality of service atop degradable distributed systems
10 Citations2009Lavanya Ramakrishnan, Daniel A. Reed
A resource performability model is presented to estimate lost performance and corresponding cost considerations with varying availability levels and is used in a multi-phase planning approach for scheduling a set of deadline-sensitive meteorological workflows atop grid and cloud resources to trade-off performance, reliability and cost.
A fast recursive algorithm to compute the probability of M-out-of-N events
9 Citations2002G. E. Radke, Javon Evanoff
A simple recursive algorithm to compute the exact probability of occurrence of M or more events out of a possible N events, especially in cases where N exceeds limitations of cut set manipulation techniques, and when the M-out-of-N event is statistically independent of other events in the system under consideration.
Extensible resource management for networked virtual computing
8 Citations2007Jeffrey S. Chase, Laura Grit
This thesis addresses the hypothesis that a new, foundational layer for virtual computing is sufficiently powerful to support a diversity of resource management needs in a general and uniform manner and shows that resource management at a lower layer can expose dynamic resource control to hosted middleware, at a modest cost in fidelity to the goals of the policy.