Heuristics for scheduling parameter sweep applications in grid environments
Published 7 November 2002Open access
Henri Casanova, Arnaud Legrand, Dmitrii Zagorodnov, Fran Berman
Citations569
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
This study proposes an adaptive scheduling algorithm for parameter sweep applications on the grid, modify standard heuristics for task/host assignment in perfectly predictable environments, and proposes an extension of Sufferage called XSufferage.
Abstract
The computational Grid provides a promising platform for the\nefficient execution of parameter sweep applications over very large parameter\nspaces. Scheduling such applications is challenging because target resources\nare heterogeneous, because their load and availability varies dynamically, and\nbecause tasks may share common data files. In this paper, we propose a\nscheduling algorithm for parameter sweep applications on the Grid. We consider\nstandard heuristics for task/host assignment (Max-min, Min-min, Sufferage), and\nwe propose an extension of Sufferage called XSufferage. Using simulation, we\ndemonstrate 3 results: 1) that XSufferage can take advantage of file sharing\nto achieve better performance than the other heuristics under a wide variety of\nload conditions, 2) that it is possible to characterize the environments under\nwhich different heuristics perform best, and 3) that it is possible to\ncharacterize the performance of different heuristics under the (realistic)\nassumption of varying accuracy of performance estimations.Pre-2018 CSE ID: CS1999-0632
Keywords
Computer Science
The Grid 2: Blueprint for a New Computing Infrastructure
7,622 Citations1998Ian Foster, Carl Kesselman
This chapter discusses grids in context, distributed supercomputing applications, and testbed Bridges from Research to Infrastructure.
IIE TransactionsScheduling: Theory, Algorithms, and Systems
6,281 Citations1996Michael Pinedo
Scheduling will serve as an essential reference for professionals working on scheduling problems in manufacturing and computing environments and Graduate students in operations management, operations research, industrial engineering and computer science will find the book to be an accessible and invaluable resource.
The International Journal of Supercomputer Applications and High Performance ComputingGlobus: a Metacomputing Infrastructure Toolkit
3,161 Citations1997Ian Foster, Carl Kesselman
The Globus system is intended to achieve a vertically integrated treatment of application, middleware, and net work, an integrated set of higher level services that enable applications to adapt to heteroge neous and dynamically changing metacomputing environ ments.
Journal of the ACMHeuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
800 Citations1977Óscar H. Ibarra, Chul E. Kim
A simplified scheduling problem involving identical processors and restricted task sets is shown to be P-complete, however, the LPT algorithm applied to this problem yields schedules which are near optimal for large n.
Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems
592 Citations2003Muthucumaru Maheswaran, Shoukat Ali +3 more
Three new heuristics, one for batch and two for on-line, are introduced as part of this research, revealing that the choice of mapping heuristic depends on parameters such as: the structure of the heterogeneity among tasks and machines, the optimization requirements, and the arrival rate of the tasks.
AIAA JournalSteady and unsteady solutions of the incompressible Navier-Stokes equations
439 Citations1991Stuart E. Rogers, Dochan Kwak +1 more
Cluster ComputingDynamically forecasting network performance using the Network Weather Service
397 Citations1998Rich Wolski
The Network Weather Service is a generalizable and extensible facility designed to provide dynamic resource performance forecasts in metacomputing environments and its design and predictive performance are outlined.
NetSolve
392 Citations1996Henri Casanova, Jack Dongarra
This paper presents a new system, called NetSolve, that allows users to access computational resources, such as hardware and software, distributed across the network, and offers the ability to look for computational resources on a network, choose the best one available, solve a problem, and return the answer to the user.
The International Journal of Supercomputer Applications and High Performance ComputingNetsolve: a Network-Enabled Server for Solving Computational Science Problems
316 Citations1997Henri Casanova, Jack Dongarra
This paper presents a new system, called NetSolve, that allows users to access computational resources, such as hardware and software, distributed across the network, and offers the ability to look for compu tational resources on a network, choose the best one available, solve a problem, and return the answer to the user.
Future Generation Computer SystemsA worldwide flock of Condors: Load sharing among workstation clusters
290 Citations1996Dick Epema, Miron Livny +3 more
The design and implementation of a distributed, layered Condor flocking mechanism that represents in each pool idle machines from other pools in the flock and allows job transfers across pool boundaries is described.
A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems
236 Citations2003Tracy D. Braun, H.J. Siegal +9 more
A collection of eleven heuristics from the literature has been selected, implemented, and analyzed under one set of common assumptions and provides one even basis for comparison and insights into circumstances where one technique will outperform another.
IEEE Transactions on Parallel and Distributed SystemsHow useful is old information?
228 Citations2000Michael Mitzenmacher
The problem of load balancing in dynamic distributed systems in cases where new incoming tasks can make use of old information is considered, and it is found that only small amounts of queue length information can be extremely useful in these settings.
GASS
220 Citations1999Joseph Bester, Ian Foster +3 more
A data movement and access service called Global Access to Secondary Storage (GASS) is proposed, which defines a global name space via Uniform Resource Locators and allows applications to access remote files via standard I/O interfaces.
ComputerWide area computing: resource sharing on a large scale
133 Citations1999Andrew Grimshaw, Adam J. Ferrari +2 more
Legion is a network-level operating system designed from scratch to target wide-area computing demands and would allow multiple organizations with diverse platforms to share and combine their resources.
Load-sharing in heterogeneous systems via weighted factoring
124 Citations1996Susan Flynn Hummel, Jeanette P. Schmidt +2 more
It is shown that weighted factoring significantly outperforms variants of a work-stea!ing load-balancing algorithm and on certain applications dramatically outperforms factoring as well.
The Internet Backplane Protocol: Storage in the Network
117 Citations1999James S. Plank, Micah Beck +4 more
The development of IBP is discussed, the implementation of a prototype system for managing network storage, and a preliminary deployment as part of the Internet-2 Distributed Storage Initiative are discussed.
Predicting the CPU availability of time-shared Unix systems on the computational grid
107 Citations2003Rich Wolski, Neil Spring +1 more
Overview of a performance evaluation system for global computing scheduling algorithms
106 Citations2003Atsuko Takefusa, Satoshi Matsuoka +3 more
The Bricks performance evaluation system allows the analysis and comparison of various scheduling schemes in a typical high-performance global computing setting, and observed that Bricks behaved in the same manner as the real environment, and NWS also behaved similarly, making quite comparative forecasts under both environments.
A resource query interface for network-aware applications
94 Citations2002Bruce Lowekamp, Nancy Houston Miller +4 more
A unified resource scheduling framework for heterogeneous computing environments
84 Citations2003Ammar Alhusaini, Viktor K. Prasanna +1 more
A unified framework for resource scheduling in metacomputing systems where tasks with various requirements are submitted from participant sites is developed and it accommodates emerging notions of quality of service (QoS) and advance resource reservations.
Monte Carlo Simulation of Neuro- Transmitter Release Using MCell, a General Simulator of Cellular Physiological Processes
79 Citations1998Joel R. Stiles, Thomas M. Bartol +2 more
Simulation of neurotransmitter exocytosis is discussed, focusing on the theoretical and computational factors underlying simulation accuracy: how inadvertent use of seemingly appropriate input parameters can lead to orders-of- magnitude errors; and how some of MCell's features can reduce the computation time required for simulations by orders of magnitude.
Stochastic scheduling
73 Citations1999Jennifer M. Schopf, Francine Berman
It is demonstrated that a stochastic scheduling policy based on time-balancing for data parallel applications whose execution behavior can be represented as a normal distribution can achieve good and predictable performance for the application as evaluated by several performance measures.
Using Effective Network Views to Promote Distributed Application Performance.
49 Citations1999Gary Shao, Francine Berman +1 more
It is shown that distributed parallel application performance in clusters of workstations benefits from knowledge about network topology in cases where LAN resources can become potential performance bottlenecks.
OpenGrey (Institut de l'Information Scientifique et Technique)Using simulation to evaluate scheduling heuristics for a class of applications in grid environments
15 Citations1999Francine Berman, Henri Casanova +5 more
A template for scheduling Parameter Sweep applications and a general scheduling algorithm that can adapt to Grid environments and use a variety of strategies and heuristics to assign tasks and data to resources are introduced.
Scheduling large parametric modelling experiments on a distributed meta-computer
9 Citations1997David Abramson, J. Giddy
A new version of Nimrod, called Nimrod/G, is currently building, which will integrate Nimrod job generation techniques with Globus, an international project which is building the underlying infrastructure for large meta-computing applications.
Why the mean is inadequate for accurate scheduling decisions
7 Citations2003T. Kidd, D. Hensgen
The authors show that if this assumption is violated, if jobs do not execute for exactly their expected run-times, then this algorithm will underestimate the time at which the last job is exacted to finish, sometimes substantially.