Uwe Schwiegelshohn - Böcker

Thisvolumecontainsthepaperspresentedatthe8thWorkshoponJobSched- ingStrategiesforParallelProcessing,whichwasheldinconjunctionwith HPDC11andGGF5inEdinburgh,UK,onJuly24,2002. Thepapershave beenthroughacompletereviewprocess,withthefullversionbeingreadand evaluatedby?vetosevenmembersoftheprogramcommittee. Wewouldliketo takethisopportunitytothanktheprogramcommittee,AndreaArpaci-Dusseau, WalfredoCirne,AllenDowney,WolfgangGentzsch,AllanGottlieb,MoeJette, RichardLagerstrom,JensMache,CathyMcCann,ReaganMoore,BillNitzberg, MarkSquillante,andJohnTowns,foranexcellentjob. Thanksarealsodueto theauthorsfortheirsubmissions,presentations,and?nalrevisionsforthisv- ume. Finally,wewouldliketothanktheMITLaboratoryforComputerScience andtheSchoolofComputerScienceandEngineeringattheHebrewUniversity fortheuseoftheirfacilitiesinthepreparationoftheseproceedings. Thisyearsawanemphasisontwomainthemes. The?rstwastheclassical MPPschedulingarea. Themainfocusinthisareawasonback?lling,including severaladvancedvariationsonthebasicscheme. Itisalsonoteworthythatseveral papersdiscussedtheuseofadaptivenessinjobscheduling.Thesecondmajor themewasschedulinginthecontextofgridcomputing,whichisemergingasan areaofmuchactivityandrapidprogress. Thesearecomplementedbyaninvited paperprovidinganoverviewoftheschedulingandresourcemanagementareaof theGlobalGridForum(GGF)e?ort. Thiswastheeighthannualworkshopinthisseries,whichre?ectsthec- tinuedinterestinthisarea. Theproceedingsofpreviousworkshopsareavailable fromSpringer-VerlagasLNCSvolumes949,1162,1291,1459,1659,1911,and 2221(andsince1998theyhavealsobeenavailableonline). Wehopeyou?ndthesepapersinterestinganduseful. September2002 DrorFeitelson LarryRudolph UweSchwiegelshohn Table of Contents ASelf-TuningJobSchedulerFamilywithDynamicPolicySwitching ...1 AchimStreit PreemptionBasedBack?ll...24 QuinnO. Snell,MarkJ. Clement,andDavidB. Jackson JobSchedulingfortheBlueGene/LSystem...38 ElieKrevat,Jos'eG. Castan"Thisvolumecontainsthepaperspresentedatthe8thWorkshoponJobSched- ingStrategiesforParallelProcessing,whichwasheldinconjunctionwith HPDC11andGGF5inEdinburgh,UK,onJuly24,2002. Thepapershave beenthroughacompletereviewprocess,withthefullversionbeingreadand evaluatedby?vetosevenmembersoftheprogramcommittee.Wewouldliketo takethisopportunitytothanktheprogramcommittee,AndreaArpaci-Dusseau, WalfredoCirne,AllenDowney,WolfgangGentzsch,AllanGottlieb,MoeJette, RichardLagerstrom,JensMache,CathyMcCann,ReaganMoore,BillNitzberg, MarkSquillante,andJohnTowns,foranexcellentjob. Thanksarealsodueto theauthorsfortheirsubmissions,presentations,and?nalrevisionsforthisv- ume. Finally,wewouldliketothanktheMITLaboratoryforComputerScience andtheSchoolofComputerScienceandEngineeringattheHebrewUniversity fortheuseoftheirfacilitiesinthepreparationoftheseproceedings. Thisyearsawanemphasisontwomainthemes. The?rstwastheclassical MPPschedulingarea. Themainfocusinthisareawasonback?lling,including severaladvancedvariationsonthebasicscheme. Itisalsonoteworthythatseveral papersdiscussedtheuseofadaptivenessinjobscheduling. Thesecondmajor themewasschedulinginthecontextofgridcomputing,whichisemergingasan areaofmuchactivityandrapidprogress. Thesearecomplementedbyaninvited paperprovidinganoverviewoftheschedulingandresourcemanagementareaof theGlobalGridForum(GGF)e?ort. Thiswastheeighthannualworkshopinthisseries,whichre?ectsthec- tinuedinterestinthisarea.Theproceedingsofpreviousworkshopsareavailable fromSpringer-VerlagasLNCSvolumes949,1162,1291,1459,1659,1911,and 2221(andsince1998theyhavealsobeenavailableonline). Wehopeyou?ndthesepapersinterestinganduseful. September2002 DrorFeitelson LarryRudolph UweSchwiegelshohn Table of Contents ASelf-TuningJobSchedulerFamilywithDynamicPolicySwitching ...1 AchimStreit PreemptionBasedBack?ll...24 QuinnO. Snell,MarkJ. Clement,andDavidB. Jackson JobSchedulingfortheBlueGene/LSystem...38 ElieKrevat,Jos'eG. Castan"os,andJos'eE. Moreira SelectiveReservationStrategiesforBack?llJobScheduling...55 SrividyaSrinivasan,RajkumarKettimuthu,VijaySubramani, andPonnuswamySadayappan Multiple-QueueBack?llingSchedulingwithPrioritiesandReservations forParallelSystems...72 BarryG. LawsonandEvgeniaSmirni SchedulingJobsonParallelSystemsUsingaRelaxedBack?llStrategy...88 WilliamA. Ward,Jr. ,CarrieL. Mahood,andJohnE. West TheImpactofMoreAccurateRequestedRuntimes onProductionJobSchedulingPerformance...103 Su-HuiChiang,AndreaArpaci-Dusseau,andMaryK. Vernon EconomicSchedulinginGridComputing...128 CarstenErnemann,VolkerHamscher,andRaminYahyapour SNAP:AProtocolforNegotiatingServiceLevelAgreements andCoordinatingResourceManagementinDistributedSystems...153 KarlCzajkowski,IanFoster,CarlKesselman,VolkerSander, andStevenTuecke LocalversusGlobalSchedulerswithProcessorCo-allocation inMulticlusterSystems...184 AncaI. D. BucurandDickH. J. Epema PracticalHeterogeneousPlaceholderScheduling inOverlayMetacomputers:EarlyExperiences...205 ChristopherPinchak,PaulLu,andMarkGoldenberg CurrentActivitiesintheSchedulingandResourceManagementArea oftheGlobalGridForum...229 BillNitzbergandJenniferM. Schopf Author Index...237 ASelf-TuningJobSchedulerFamily withDynamic PolicySwitching Achim Streit 2 PC - Paderborn Center for Parallel Computing, Paderborn University 33102 Paderborn, Germany streit@upb. de http://www. upb. de/pc2 Abstract. The performance of job scheduling policies strongly depends on the properties of the incoming jobs. If the job characteristics often change, the scheduling policy should follow these changes. For this p- pose the dynP job scheduler family has been developed. The idea is to dynamically switch the scheduling policy during runtime.In a basic v- sion the policy switching is controlled by two parameters. The basic concept of theself-tuning dynP scheduler is to compute virtual schedules for each policy in every scheduling step. That policy is chosen which generates the 'best' schedule. The performance of the self-tuning dynP scheduler no longer depends on a adequate setting of the input parameters.

This volume contains the papers presented at the 9th workshopon Job Sched- ing Strategies for Parallel Processing, which was held in conjunction with HPDC12 and GGF8 in Seattle, Washington, on June 24, 2003. The papers went through a complete review process, with the full version being read and eva- ated by ?ve to seven members of the program committee. We would like to take this opportunity to thank the program committee, Su-Hui Chiang, Walfredo Cirne, Allen Downey, Wolfgang Gentzsch, Allan Gottlieb, Moe Jette, Richard Lagerstrom, Virginia Lo, Cathy McCann, Reagan Moore, Bill Nitzberg, Mark Squillante, and John Towns, for an excellent job. Thanks are also due to the authors for their submissions, presentations, and ?nal revisions for this volume. Finally, we would like to thank the MIT Laboratory for Computer Science and the School of Computer Science and Engineering at the Hebrew University for the use of their facilities in the preparation of these proceedings. This year we had papers on three main topics. The ?rst was continued work on conventional parallel systems, including infrastructure and scheduling al- rithms.Notable extensions include the considerationof I/O and QoSissues. The secondmajortheme wasscheduling inthe contextofgridcomputing, whichc- tinues to be an area of much activity and rapid progress.The third area was the methodological aspects of evaluating the performance of parallel job scheduling.

This book constitutes the thoroughly refereed postproceedings of the 10th International Workshop on Job Scheduling Strategies for Parallel Processing, JSSPP 2004, held in New York, NY in June 2004. The 15 revised full research papers presented together with a report on scheduling on the Top 50 machines went through two rounds of reviewing and improvement. Various current issues in job scheduling and load balancing are addressed in the context of computing clusters, parallel and distributed systems, multi-processor systems, and supercomputers.

Thisvolumecontainsthepaperspresentedatthe11thworkshoponJobSched- ing Strategies for Parallel Processing. The workshop was held in Boston, MA, on June 19, 2005, in conjunction with the 19th ACM International Conference on Supercomputing (ICS05). The papers went through a complete review process, with the full version being readand evaluatedby anaverageof ?ve reviewers.We wouldlike to thank the Program Committee members for their willingness to participate in this e?ortandtheirexcellent,detailedreviews:Su-HuiChiang,WalfredoCirne,Allen Downey, Wolfgang Gentzsch, Allan Gottlieb, Moe Jette, Richard Lagerstrom, Virginia Lo, Jose Moreira, Bill Nitzberg, and Mark Squillante. We would also like to thank Sally Lee of MIT for her assistance in the organization of the workshop and the preparation of the pre-conference proceedings. The papers in this volume cover a wide range of parallel architectures, from distributed grids, through clusters, to massively-parallel supercomputers. The diversity extends to application domains as well, from short, sequential tasks, through interdependent tasks and distributed animation rendering, to classical large-scale parallel workloads.In addition, the methods and metrics used for scheduling and evaluation include not only the usual performance and workload considerations, but also considerations such as security, fairness, and timezones. This wide range of topics attests to the continuing viability of job scheduling research. The continued interest in this area is re?ected by the longevity of this wo- shop, which has now reached its 11th consecutive year. The proceedings of p- vious workshops are available from Springer as LNCS volumes 949, 1162, 1291, 1459,1659,1911,2221,2537,2862,and3277(and since1998theyhavealsobeen available online).

This book constitutes the thoroughly refereed post-proceedings of the 12th International Workshop on Job Scheduling Strategies for Parallel Processing, JSSPP 2006, held in Saint-Malo, France in June 2006 in conjunction with the Joint International Conference on Measurement and Modeling of Computer Systems SIGMETRICS/Performance 2006. The 12 revised full research papers cover all current issues of job scheduling strategies for parallel processing.

th Thisvolumecontainsthepaperspresentedatthe13 workshoponJobSched- ing Strategies for Parallel Processing. The workshop was held in Seattle, WA, USA, on June 17, 2007, in conjunction with ICS 2007. All submitted papers went through a complete review process, with the full versionbeingreadandevaluatedbyanaverageof?vereviewers.Wewouldliketo thanktheProgramCommittee membersandadditionalrefereesfortheirwilli- ness to participate in this e?ort and their excellent, detailed reviews: Nazareno Andrade, Su-Hui Chiang, Walfredo Cirne, Alvaro Coelho, Lauro Costa, Dror Feitelson, Allan Gottlieb, Andrew Grimshaw, Moe Jette, Richard Lagerstrom, Virginia Lo, Reagan Moore, Bill Nitzberg, Mark Squillante, John Towns, Jon Weissman, and Ramin Yahyapour. The accepted workshop papers in recent years show a departure from the supercomputer-centric viewpoint of parallel job scheduling. On the one hand, the ?eld of supercomputer scheduling is showing some signs of maturity, exh- ited in many widely accepted practices for job scheduling.On the other hand, many nontraditionalhigh-performancecomputing andparallelenvironments are emerging as viable solutions to many users and uses that cannot or need not - cess a traditional supercomputer, such as Grids, Web services, and commodity parallelcomputers.With the growingubiquity ofthese technologies,the requi- ment to schedule parallel jobs well on these various architectures also grows.

This book constitutes the revised papers of the 14th International Workshop on Job Scheduling Strategies for Parallel Processing, JSSPP 2009, which was held in Rome, Italy, in May 2009. The 15 revised papers presented were carefully reviewed and selected from 25 submissions. The papers cover all current issues of job scheduling strategies for parallel processing; this year the conference had an increasing trend towards heterogeneous and multi-core architectures.

th Thisvolumecontainsthepaperspresentedatthe15 workshoponJobSched- ing Strategies for Parallel Processing that was held in Atlanta (GA), USA, on April 23, 2010 in conjunction with the IEEE International Parallel Processing Symposium 2010. This year 18 papers were submitted to the workshop. All submitted papers went through a complete review process, with the full version being read and evaluated by an average of four reviewers. We would like to especially thank the program committee members and additional referees for their willingness to participate in this e?ort and their excellent, detailed reviews: Henri Casanova, Peter A. Chronz, Walfredo Cirne, Julita Corbalan, Arash Deshmeh,DickEpema,DrorG.Feitelson,AllanGottlieb,RajkumarKettimuthu, Virginia Lo, Kuan Lu, Vicent Matossian, Jose E. Moreira, Bill Nitzberg, Elizeu Santos-Neto,Angela C.Sodan,MarkS. Squillante,DanTsafrir,Philipp Wieder, and Ramin Yahyapour. The papers in this volume show a proli?c growth in the areas of applicability forparallelscheduling.Togetherwiththemorecommonschedulingaspects(such asclusterandGridscheduling,workloadanalysis,metrics,qualityofservice,and task scheduling), these papers increasingly discuss more recent problems and applications, such as virtualized environments, many-core processors, DNA - quencing, and Hadoop.This volume also includes a paper that summarizes Dan Tsafrir'sworkonunderstandingthe roleofuser estimates injob schedulingev- uations. His insights, which were presented in this workshop'skeynote, are quite instructive and lead to the conclusion that accurate user estimates are indeed better fore?cientscheduling.Althoughthis conclusionmaysoundintuitive,itis actuallycontradictoryto previousstudies thatfound inaccurateestimates to - prove scheduler performance. Following his analysis, Dan also suggests practical ways to deal with estimate inaccuracy for realistic job scheduler evaluations.