Multiserver scheduling

Multiserver Scheduling-ppt Download

  • Date:30 Aug 2020
  • Views:6
  • Downloads:0
  • Size:878.00 KB

Share Presentation : Multiserver Scheduling

Download and Preview : Multiserver Scheduling

Report CopyRight/DMCA Form For : Multiserver Scheduling


Transcription:

SchedulingScheduling inServer FarmsMor Harchol BalterComputer Science Dept.
Carnegie Mellon Universityharchol cs cmu eduOutline tomorrowI Review of schedulingin single server.
II Supercomputi III Web server farmng FCFS model PSRouter RouterIV Towards Optimality SRPT Metric .
Single Server Model M G 1 Poisson Load E X 1w rate X job size service requirement Bounded Pareto.
Job sizes with huge variance are everywhere1 Pr Job size x x Downey 96 CPU Lifetimes of UNIX jobs Harchol Balter Supercomputing job sizes Schroeder Harchol Balter 00 .
Web file sizes Crovella Bestavros 98 Barford Crovella 98 Huge Shin 99 IP Flow durations Shaikh Rexford Variability D F R 2Var X .
E X 2 Top heavy 8 C X2 50 is typical top 1 jobsk x p make up half Scheduling Single Server M G 1 Poisson Load 1 Huge.
arrival VariancQuestion Order these scheduling policies formean response time E T 1 FCFS First Come First Served non preemptive 2 PS Processor Sharing preemptive .
3 SJF Shortest Job First a k a SPT non preemptive 4 SRPT Shortest Remaining Processing... preemptive 5 LAS Least Attained Service a k a FB preemptive Scheduling Single Server M G 1 Poisson Load 1 Huge.
arrival VariancLOW E T HIGH E T SRPT LAS PS SJF FCFSOPT for all Insensitive Surprisingly bad E X2 Requires D F R .
arrival to E X2 E X2 term shortssequences Shanthikumar89 caught Schrage 67 behindNo Starvation Even the biggest jobs prefer SRPT to PS Bansal Harchol Balter 01 Wierman Harchol Balter 03 .
THM E T x SRPT E T x PS for all x for Bounded Pareto 9 Effect of VariabilityBounded Pareto job sizes Closed vs OpenOpen System.
Closed System What s theThink effect ofscheduling Send Receive Closed vs Open.
Open System Results Closed System ResultsClosed open systems analyzed under same job sizedistribution with same average load Schroeder Wierman Harchol Balter NSDI 06 .
Summary Single Single server system LESSONS LEARNED Smart scheduling greatlyimproves mean response time Variability of job size.
distribution is key X job size highly variable Closed system sees muchreduced effect Multiserver ModelServer farms .
Scalable capacitySched policy assignment Incoming policy Sched policyPoisson Router.
Process Sched policy2 Policy Decisions Sometimes scheduling policy is fixed legacy system 10I Review of schedulingin single server.
II Supercomputi III Web server farmng FCFS model PSRouter RouterIV Towards Optimality SRPT Metric .
Supercomputing Model assignment policy FCFSProcess Router Jobs are not preemptible .
Jobs processed in FCFS order Assume hosts are identical Jobs i i d G highly variable size distribution Size may or may not be known Initially assume known 12 Q Compare Routing Policies for.
E T Supercomputing1 Round Robin FCFS2 Join Shortest Queue policy FCFSGo to host w fewest jobs Router3 Least Work Left .
equivalent to M G k FCFS Jobs i i d G highly variableGo to host with least total work 4 Central Queue Shortest Job M G k SJF .
Host grabs shortest job when free 5 Size Interval SplittingJobs are split up by size among hosts A Size Interval Splitting best soHigh Supercomputing.
E T 1 Round Robin FCFS2 Join Shortest Queue FCFSGo to host w fewest jobs Router3 Least Work Left equivalent to M G k FCFS Highly variable job sizes.
Go to host with least total work 4 Central Queue Shortest Job M G k SJF Host grabs shortest job when free 5 Size Interval Splitting Harchol Balter Crovella .
Low Jobs are split up by size among hosts Murta JPDC 99 Routing Policies High Remarks Central Queue E T 1 Round Robin Good utilization.
of servers 2 Join Shortest Queue Some isolationGo to host w fewest jobs for smalls3 Least Work Left equivalent to M G k FCFS.
Go to host with least total work Size Interval WAY Better 4 Central Queue Shortest Job Worse utilizationof servers M G k SJF Great isolation.
Host grabs shortest job when free for smalls 5 Size Interval SplittingLow Jobs are split up by size among hosts E T Harchol Balter Crovella .
Murta JPDC 99 Size Interval Splittingx f x job size xQuestion How to choose the size cutoffs .
To Balance Load or Not to BalanceLoad xf x dx xf x dx xf x dx xf x dx Size Interval SplittingFCFS x f x .
job size xAnswer Recent Research for case of Boundedjob size Pr X x x 1 1 1UNBALANCE BALANCE LOAD UNBALANCE.
favor smalls favor larges Harchol Balter Vesilo 06 Glynn Harchol Balter Ramanan 06 Beyond Size Interval SplittingFCFS x f x job size x.
Q Is Size Interval Splitting as good as it Size Interval Splitting with StealingAnswer Allow CycleS Send Shorts HereL Send Longs Here .
Size But if idle send Short Cycle Gain to Shorts is high Pain to Longs is very small Cycle Stealing analysis very hard Fayolle Iasnogorodski Konheim Meilijson Melkman Cohen Boxma van Uitert Jelenkovic Foley McDonald .
Harrison Borst Williams New easy approach Dimensionality Reduction 2D 1D Harchol Balter Osogami Scheller Wolf Squillante SPAA03 What if Don t Know JobSize FCFS.
1 Round Robinpolicy FCFS2 Join Shortest QueueGo to host w fewest jobs 3 Least Work Left .
equivalent to M G k FCFS Highly variable job sizesGo to host with least total work 4 Central Queue Shortest Job M G k SJF Host grabs shortest job when free .
Q What can we do tominimize E T when5 Size Interval Splittingdon t know job size Jobs are split up by size among hosts .
The TAGS algorithm Task Assignment by Guessing Size When job reaches size limit for host then itis killed and restarted from scratch at next host Harchol Balter JACM 02 .
Results ofLeast Work LeftHigh Lowervariability variability Summary Part I.
Single server system LESSONS LEARNED Smart scheduling greatlyimproves mean response time Variability of job sizedistribution is key .
X job size highly variable Closed system sees muchreduced effect LESSONS LEARNED Supercomputing Greedy routing policies .
FCFS like JSQ LWL are poor To combat variability needRouter size interval splitting FCFS By isolating smalls canachieve effects of smart.
single server policies Load UN balancing Don t need to know size 23 Tomorrow Review of scheduling in single server.
II Supercomputing III Web server farmManufacturing FCFS modelRouter RouterV Towards Optimality Scheduling.
Scheduling inin MultiserverMultiserverMor Harchol BalterComputer Science Dept.
Carnegie Mellon Universityharchol cs cmu eduI Review of schedulingin single serverII Supercomputi III Web server farm.
ng FCFS model PSRouter RouterIV Towards Optimality I Review of schedulingin single server.
II Supercomputi III Web server farmng FCFS model PSRouter RouterIV Towards Optimality Web Server Farm.
Cisco LocalRouting Directorpolicy IBM NetworkPoisson DispatcherProcess Router Microsoft.
PS SharePoint F5 Labs BIG IP HTTP requests are immediately dispatched to server Requests are fully preemptible Commodity servers utilized Do Processor Sharing .
Jobs i i d G highly variable size distribution 7 orders magnitude difference in job size Crovella Bestavros 98 Q Compare Routing Policies forHigh Web Server Farm.
2 Join Shortest QueueGo to host w fewest jobs High variance job size3 Least Work LeftGo to host with least total4 Size Interval Splitting.
Low Jobs are split up by size Central Queue policies aren tE T FCFS among hosts possible for PS farms Q Compare Routing Policies for1 Random PS2 Join Shortest Queue.
Go to host w fewest jobs Answer Same for E T but not great Also want to3 Least Work Left better 8 servers 9 C2 50.
E T balance load Go to host with least total RAND SIZEwork 1 E T M G 1 PS 1 .
4 Size Interval Splitting PS farm 1 E T pi Jobs are split up by size p 1 i i among hosts .
Prior Analysis of JSQAll prior JSQ analysis assumes FCFS servers2 server 2 server approximations Kingman 61 Flatto McKean 77 Nelson Philips Sigmetrics 89 Wessels Adan Zijm 91 Nelson Philips Perf Eval 93 .
Foschini Salz 78 Lin Raghavendra TPDS 96 Knessl Makkowsky Schuss Tier 87 Conolly 84 Rao Posner 87 Blanc 87 Grassmann 80 Muntz Lui Towsley 95 Cohen Boxma 83 31.
Nelson Philips E Waiting Time E JobSize Pr n total in all E length shortest queue n total Assume this is Assume thisM M k is .
n k k servers First Analysis of JSQ for Gupta Harchol Balter Sigman Whitt 06 Process JSQ.
Near insensitivity to C2 PS server farm with General service PS server farm w Exponential service FCFS server farm w Exponential serviceSingle queue equivalence .
For PS server farm w Exponential service Multiserver system Single queue w contingent arrival rate Summary so farLESSONS LEARNED Supercomput Greedy routing policies .
ing like JSQ LWL are poor To combat variability needsize interval splitting Router By isolating smalls canachieve effects of smart.
single server policies Load UN balancing Don t need to know size Web server farmPS LESSONS LEARNED .
JSQ routing is good PS Job size variabilityRouter not a problem PS Load Balancing Review of scheduling in single server.
II Supercomputing III Web server farmManufacturing FCFS modelRouter RouterIV Towards Optimality What is Optimal.
Routing Scheduling Sched policySched policyjobs RouterSched policy.
2 Policy DecisionsAssume no restrictions Jobs are fully preemptible Can have central queue if want it or not Know job size.
of course don t know future jobs 36 What is OptimalRouting Scheduling Central Queue SRPTRecall minimizes E T on every sample path .
Schrage 67 Question Central Queue SRPT looks prettyDoes it minimize E T 37 Central Queue SRPTAnswer This does not minimize E T on every arrival sequence .
Bad Arrival Sequence time 0 2 jobs size 29 1 job size 210 time 210 2 jobs size 28 1 job size 29 time 210 29 2 jobs size 27 1 job size 28 OPT Central Queue SRPT.
28 28 29 29 28 2929 210 29 28 210 29preempted 38 Central Queue SRPTAdversarial Worst Case Guarantees .
THM Leonardi Raz STOC 97 Central Queue SRPT is O log min biggest sizesmallest size serverscompetitive for E T and no online policy can improve upon.
this by more than constant factor log biggest smallest could be factor 7 in practice Closest stochastic result analyzes only central queuew priorities Harchol Balter Wierman Osogami Scheller Wolf QUESTA 05 .
What is OptimalRouting Schedulingwith Immediate Dispatch Sched policySched policy.
jobs RouterSched policy2 Policy DecisionsPractical Assumption jobs must be immediately dispatched Jobs are fully preemptible within queue .
Know job size What is OptimalRouting Schedulingwhen ImmediatelyImmediately SRPT Claim Dispatch .
Dispatch Jobs The optimal routing sched jobs Router SRPT pair given immed dispatchuses SRPT at the hosts Assuming an opt pair exists Let A optimal routing scheduling pair wrt E T .
Suppose by contradiction A does not use SRPT at the hosts Let policy pair B mimic A with respect to A s dispatching of jobs to I e policy B may be different from A but sends the same jobs to thesame hosts at the same times as A But after the dispatching B does SRPT scheduling at the hosts .
Thus B improves upon A with respect to E T Contradiction IMPACT Claim narrow search to policies with SRPT at 41 In search of goodImmediate Dispatch RoutingImmediately.
Dispatch JobsIncoming SRPTjobs RouterQ What should immediate dispatch routingpolicy be given SRPT sched at hosts .
In search of goodRao and M. Posner, “Algorithmic and approximate analysis of the shorter queue,” Model Naval Research Logistics, Vol. 34, 1987, pp. 381-398. R. Righter and J. Shanthikumar, “Scheduling multiclass single server queueing systems to stochastically maximize the number of successful departures," Probability in the Engineering and Informational ...

Related Presentations

Surplus Fair Scheduling A Proportional Share Scheduling

Challenge: Make Web Servers Scalable Server Scalability Issues Large number of concurrent/idle connections Last-mile problem: Slow end-connections High latency WAN traffic HTTP/1.1 Persistent Connections Heavy Request Loads Need for high throughput Pure Thread-based vs. Event-based servers Focus: Scalability of Event-based servers on Linux ...

21 Views0 Downloads

Scheduling a Scheduling Competition

Scheduling a Scheduling Competition ICAPS07 workshop 22 September 2007 Providence, RI, USA

12 Views0 Downloads

Welcome to Twinsburg High School 9th Grade Scheduling

THS Graduation Requirements. English –4 credits. Science-3 credits. Math –4 credits. Social Studies –4 credits. Academic Elective-1 credit. Freshman Success-0.5 credits

47 Views0 Downloads

Project Scheduling Networks Duration Estimation and

Determine the ES, LS, EF, LF, and slack of each activity A(3) B(6) C(9) ABC=18 days Laddered ABC=12 days A1(1) A2(1) A3(1) B1(2) B2(2) B3(2) C1(3) C2(3) C3(3) 0 A 5 0 5 5 B 15 5 10 15 15 C 18 15 3 18 0 Hammock 18 0 18 18 Useful with a complex project or one that has a shared budget * Task a b c Mean Variance Z 7 8 15 9.00 1.78 Y 13 16 19 16.00 ...

23 Views0 Downloads

Compiler Scheduling for a Wide Issue Multithreaded FPGA

Netezza. Data warehouse appliance; FPGAs accelerate DBMS. Algorithmics. Acceleration of financial algorithms. Lime (Liquid Metal) Java synthesized to heterogeneous (CPUs, FPGAs) HAL (Hardware Acceleration Lab) IBM Toronto; FPGA-based acceleration. New: IBM Canada Research & Development Centre. One (of 5) thrust on “agile computing”

31 Views0 Downloads

Scheduling Strategies for Public Computing

Virtual Organizations Types of Grids Grid Components Applications Grid Issues Conclusions Outlines -continued Public Computing and the BOINC Architecture Motivation for New Scheduling Strategies Scheduling Algorithms Testing Environment and Experiments MD4 Password Hash Search Avalanche Photodiode Gain and Impulse Response Gene Sequence ...

19 Views0 Downloads

Decentralized Scheduling for Grid Environments using IP

Key Issues for Security. Need independent assessment. ... FNAL and Open Science Grid Feeds Condor Usage into Gratia Accounting System3 vulnerabilities1.7 KLOC of Perl and Bash. ... Decentralized Scheduling for Grid Environments using IP Network Techniques Last modified by: ASUS

17 Views0 Downloads

VistA Scheduling Enhancements VSE Super User Training Day 2

Super User Training – Day Two. Managing Requests and Appointments Part One. ... a patient and non-responsive patients remain in effect so we may ensure the best clinical care and not miss any medical issues. The process for contacting patients to schedule appointments are as follows: ... VistA Scheduling Enhancements (VSE) Super User Training ...

20 Views0 Downloads

Scheduling and Resource Management for Next Generation

Infowares (yahoo.Com, AOL.Com) Email, eChat, ePhone, eBook,eBank, eSociety, eAnything Computing portal Resource Management Each application is demanding Several applications/users can be present at the same time System Model Two Phases in Resource Management Allocation Issues Admission Control Arrival Queue Principle Scheduling Issues (CPU ...

24 Views0 Downloads

Scheduling for FB network

November 2019. Kazuyuki Sakoda, Sony. Slide . Discussionon low latency capability for 802.11be. Date: 2020-01-14

23 Views0 Downloads

Large Scale and Dynamic Evolutionary Scheduling

Hunt, R., Johnston, M. and Zhang, M., 2014, July. Evolving machine-specific dispatching rules for a two-machine job shop using genetic programming. In 2014 IEEE Congress on Evolutionary Computation (CEC) (pp. 618-625). IEEE.

36 Views0 Downloads

CCA Scheduling and Enrollment

Confidential and Proprietary, Ministry of Education, Negara Brunei Darussalam. SSSS-YYTNNNNCCA (Max. 15 characters only) SSSS = School Code. Dash. YY = Last two digit of academic year. E.g year 2019 = 19, year 2020 =20. T = Current Term. E.g Term 2 = 2 , Term 3 = 3. NNNN = Group/Class section based on created Timetable. I.eGroup 1 = G1, Lower 6 ...

9 Views0 Downloads