2004 talk

Some Systems, Applicationsand Models I Have Known: 

Some Systems, Applications and Models I Have Known Ken Sevcik University of Toronto

Overview: 

Overview In the past 35 years, … Systems Have Changed Applications Have Grown Models Have Matured and Adapted … and some interesting problems have been encountered

First Research Application: Probability of a Voters’ Paradox: 

First Research Application: Probability of a Voters’ Paradox C candidates for election V voters with strict preference orderings Can one candidate beat each other pairwise? Example: V = 3 andamp; C = 3 V1 : X andgt; Y andgt; Z V2 : Y andgt; Z andgt; X V3 : Z andgt; X andgt; Y Then, in pair-wise elections, X beats Y ; and Y beats Z ; yet Z beats X ! Paradox occurs in 12 of the (3!)3 = 216 possible configurations. In general, there are (C!)V voting configurations.

My first “personal” computer: IBM System 360 Model 30 with BOS: 

My first 'personal' computer: IBM System 360 Model 30 with BOS

Exact Probabilities of Voters’ Paradox: 

Exact Probabilities of Voters’ Paradox V = 3 andamp; C = 3  12 cycles in 216 configs. V = 7 andamp; C = 7  26,295,386,028,643,902,475,468,800 cycles in 82,606,411,253,903,523,840,000,000 configs. (Computed in approximately 40 hours of CPU time.) C = 3 5 7 ~ 40 V = 3 .0555… .1600… .238798185941 ~ .61 V = 5 .06944… .19999525 .295755170299 ~ .71 V = 7 .075017 .215334 .318321370333 ~ .74 V ~ 40 ~ .09 ~ .24 ~ .36 ~ .80

Job Sequencing on a Single Processor: 

Job Sequencing on a Single Processor Minimize Investment (quantum length) Payoff (Pr [Completion]) = Service Time Knowledge exact average distribution No SPT SEPT SEPT Preemption Allowed? Yes SRPT SERPT SR 'Smallest Rank' (SR) Scheduling: (using service time distribution knowledge)

Job Sequencing with Two Processors & Two Customers: 

Job Sequencing with Two Processors andamp; Two Customers Extending 'Shortest First' to Multiple Resources SBT-RSBT -- Based on average service time per visit of each customer at each resource SBT:  A gets priority at k RSBT:  A gets priority at 1

In the Beginning …: 

In the Beginning … Single Server Queue Many variations arrival process, service process multiple servers, finite buffer size scheduling discipline FCFS, RR, FBn, PS, SRPT, … RR, FBn, and PS increased relevance of models N , Z S

Queuing Network Models: 

Queuing Network Models N customers 'Central Server' Model Variants: Open, Closed, Mixed scheduling disciplines 'Separable' (or 'product form') models and efficient computational algorithms

The “Great Debate”:Operational Analysis vs. Stochastic Modeling: 

The 'Great Debate': Operational Analysis vs. Stochastic Modeling SM Ergodic stationary Markov process in equilibrium Coxian distributions of service times independence in service times and routing OA finite time interval measurable quantities testable assumptions OA made analytic modelling accessible to capacity planners in large computing environments

Uses and Analysis of Queuing Network Models: 

Uses and Analysis of Queuing Network Models Applications System Sizing; Capacity Planning; Tuning Analysis Techniques Global Balance Solution Massive sets of Simultaneous Linear Equations Bounds Analysis Asymptotic Bounds (ABA), Balanced System Bounds (BSB) Solutions of 'Separable' Models Exact (Convolution, eMVA) Approximate (aMVA) Generalizations beyond 'Separable' Models aMVA with extended equations

Bounding Analysis Case Study: Insurance Company with 20 sites: 

Bounding Analysis Case Study: Insurance Company with 20 sites Upgrade alternatives: Upgrade Dcpu Dio Dtot Improvement Current 4.6 4.0 10.6 ----- # 1 5.1 1.9 7.0 1.5 to 2.0 # 2 3.1 1.9 5.0 2.0 to 3.5 ABA Inputs: N, Z, Dtot, Dmax Throughput Bound: Response Time Bound:

Bounding Analysis Case Study: Insurance Company with 20 sites: 

Bounding Analysis Case Study: Insurance Company with 20 sites Upgrade alternatives: Upgrade Dcpu Dio Dtot Improvement Current 4.6 4.0 10.6 # 1 5.1 1.9 7.0 1.5 to 2.0 # 2 3.1 1.9 5.0 2.0 to 3.5 X N .1 .2 .3 .4 2 6 8 10 4 Cur #1 #2

Bounding Analysis Case Study: Insurance Company with 20 sites: 

Bounding Analysis Case Study: Insurance Company with 20 sites Upgrade alternatives: Upgrade Dcpu Dio Dtot Improvement Current 4.6 4.0 10.6 # 1 5.1 1.9 7.0 1.5 to 2.0 # 2 3.1 1.9 5.0 2.0 to 3.5 R N # 2 Cur # 1 2 4 6 8 10 5 10 15 20

Exact Mean Value Analysis Algorithm: 

Exact Mean Value Analysis Algorithm for n = 1, … , N Understandable and Easy to Implement Initialize (for zero customers): Iterate up to N customers: Set Arrival Instant Queue Lengths: Set Residence Time:

Approximate Mean Value Analysis: 

Approximate Mean Value Analysis loop until Qk ( N ) are stable Substantial time savings; Little loss of accuracy Initialize to Equal Queue Lengths: Iterate until convergence: Revise Arrival Instant Queue Lengths: Revise Residence Times:

“Details” of Real Systems: 

'Details' of Real Systems Going beyond 'Separable' models Priority Scheduling Alter Residence Time equation FCFS with high variance service times Reflect coefficient of variation in service times Memory Constraints Alter MPL limit N , or Dpaging I/O Subsystems (simultaneous resource possession) Reflect contention by inflating Ddisk Enhanced Utility of QNM’s for Real Systems

System Sizing Case Study:NASA Numerical Aerodynamic Simulator: 

System Sizing Case Study: NASA Numerical Aerodynamic Simulator GOAL: to attain a sustainable Gigaflop QNM’s proved more useful than a simulation model Cray 1 Cray 2 Cray 3 Data Mgmt Graphics Work Stations

QNM’s for Capacity Planning & Tuning: 

QNM’s for Capacity Planning andamp; Tuning Existing system with measurable workload 'What if …' … the workload volume increases? … the workload mix changes? … the processor is upgraded? … memory is added? … the I/O configuration is enhanced? … class priorities are adjusted? … file placements are changed? … changing usage of memory? Answer by changing model parameters CAPACITY PLANNING TUNING

Capacity Planning Case Study: FAA Air Traffic Control System: 

Capacity Planning Case Study: FAA Air Traffic Control System ~ 40 distributed air traffic control centers Each with the SAME: software hardware family 35 transaction types But DIFFERENT: transaction volumes and mixes Single QNM (one class per transaction type) supports capacity planning for all sites

QNM’s for System and Architecture Analysis: 

QNM’s for System and Architecture Analysis Architectures caching structures Communication networks Local Area Networks Rings, buses Store and Forward flow control end to end response time Interconnection networks omega, shuffle-exchange, …

SE&EU Interconnection Network: 

SEandamp;EU Interconnection Network Source 000 001 010 011 100 101 110 111 Destination 000 001 010 011 100 101 110 111 Shuffle Exchange Exchange Unshuffle

SE&EU operation: 

SEandamp;EU operation Up to 40% increase in throughput SE: Left 3 EU: Right 5 SE: Left 2 Combination Lock Algorithm:

Network for NASA’s Space Station (circa 1984): 

Network for NASA’s Space Station (circa 1984) Distributed LAN for many components Ground Station Results: Some properties of the FDDI Protocol

Architectural Analysis Case Study: NUMAchine: 

Architectural Analysis Case Study: NUMAchine 4 x 4 x 4 Hierarchical Ring Architecture Setting Routing Priorities: Contiguous vs. Interleaved Shortest First ? Message Handling:

Job Scheduling for Parallel Processing: 

Job Scheduling for Parallel Processing time 3 2 1 P processors Job j = ( tj , pj ) Variants: Static Moldable Malleable Dynamic

Parallelism: Early or Late ?: 

Parallelism: Early or Late ? Problem Schedule N jobs of two tasks each on two processors to minimize average residence time Each pair of jobs can be executed as … PARALLEL: SEQUENTIAL: overhead of parallel execution

Parallelism: Early or Late ?: 

Parallelism: Early or Late ? Results of two similar studies: [RN et al.] Start parallel; Finish sequential P P P P P P S S S S S S

Parallelism: Early or Late ?: 

Parallelism: Early or Late ? Results of two similar studies: [RN et al.] Start parallel; Finish sequential [KCS] Start sequential; Finish parallel S P P P P P P P P P P P P S S S S S S S S S S S

Parallelism: Early or Late ?: 

Parallelism: Early or Late ? Results of two similar studies: [RN et al.] Start parallel; Finish sequential [KCS] Start sequential; Finish parallel S P P P P P P P P P P P P S S S S S S S S S S S

Parallelism: Early or Late ?: 

Parallelism: Early or Late ? Resolution increasing increasing

Distributed Processing Models: 

Distributed Processing Models Processor selection strategies local vs. global execution Load Sharing sender-initiated vs. receiver-initiated

Small example: Individual Versus Social Optimum: 

Small example: Individual Versus Social Optimum Arriving customers must pick one of two processors, one fast and one slow: F S Individual Optimum: Pick server with lower response time (  response times are equalized) Social Optimum: Control pF to minimize avg. response time pF pS

Resolution of Social and Individual Goals: 

Resolution of Social and Individual Goals Individual Optimum: Social Optimum minimizes: Toll on F: Rebate on S: RESULT: Everybody Wins !!!

Anomaly of High Dimensional Spaces: 

Anomaly of High Dimensional Spaces 1. Pointy-ness Property 2. Radius of Inner Sphere 3. Volume Ratio R2 = .414 R10 = 2.16 !!! 2k Spheres (radius = 1) in Cube (vol. 4k andamp; 2 k sides) and an Inner sphere

Diagonal of a k-dimensional Cube: 

Diagonal of a k-dimensional Cube (Example: k = 25 ) Blues = Red = Corners =

Diagonals of Cube: 

Diagonals of Cube K = 2 K = 1 K = 3 K = 4

Diagonals of Cube: 

Diagonals of Cube K = 9 K = 121 (There are 2121 blue spheres)

Multidimensional Databases: 

Multidimensional Databases Relational View: Multidimensional View: (Records of k Attributes) (Points in k-dimensional space) Indexing Support for: -- point search -- range search -- similarity search -- clustering

Bounding Spheres and Rectangles: 

Bounding Spheres and Rectangles circumscribed inscribed ratio of Dim k sphere cube sphere volumes -------- ---------------- ---------- --------------- ------------- 2 1.57 1.00 .785 2 4 4.93 1.00 .308 16 8 64.94 1.00 .0159 4096 16 15422.64 1.00 .000004 4294967296

Edge Density in High-Dimensions: 

Edge Density in High-Dimensions Proportion of points near some side: Fraction near some edge: k eps = .002 .020 .200 ---- ------ ------ ----- 1 .004 .040 .400 2 .007 .078 .640 4 .015 .150 .870 8 .031 .278 .983 16 .062 .479 .999 1

Lessons and Conclusions: 

Lessons and Conclusions Exact answers are overrated accurate approximate answers often suffice (e.g., Voters’ Paradox and aMVA ) Analytic models have an important role quick, inexpensive answers in many situations (e.g., Insurance Co., NAS System, and FAA System ) Assumptions matter subtle differences can have big effects (e.g., in Early or Late Parallelism, NUMAchine analysis and PRI vs. FCFS or PS)

What is the “best” way to attain largeimprovements in computer performance?: 

What is the 'best' way to attain large improvements in computer performance? -- Analysis? -- Simulation? -- Experimentation?

What is the “best” way to attain largeimprovements in computer performance?: 

What is the 'best' way to attain large improvements in computer performance? -- Analysis? -- Simulation? -- Experimentation? None of the above … Just wait 30 years!!!

ACM Sigmetrics & IFIP W.G. 7.3 ,: 

ACM Sigmetrics andamp; IFIP W.G. 7.3 , Thanks for the memories …

Problems with Voting Systems: 

Problems with Voting Systems Problems have occurred recently in .. France (lowest eliminated) R andgt; M andgt; L 40% L andgt; M andgt; L 40% M andgt; (R, L) 20% Middle eliminated in first round though rank score (2.2) Beats rank score of others (1.9) USA (primaries, and electoral college) E.g., McCain loses to Bush in primaries although he Might be both candidates in a final election

Exact Mean Value Analysis Algorithm: 

Exact Mean Value Analysis Algorithm for n = 1, … , N end for -- Understandable -- Easy to implement -- Arrival Instant Theorem

Approximate Mean Value Analysis: 

Approximate Mean Value Analysis loop exit when X(N) and R(N) converge -- Substantial time savings -- Little loss of accuracy end loop

The Case for Popt = 1 :: 

The Case for Popt = 1 : (Assume p andgt; 1  Ej (p) andlt; 1 ) Argument: Demand is insatiable (unbounded backlog) Economies of scale (100’s of users) 'Good' systems will be heavily used Parallelism overhead decreases throughput and increases queuing times

System Sizing Case Study:NASA Numerical Aerodynamic Simulator: 

System Sizing Case Study: NASA Numerical Aerodynamic Simulator

Quiz #1: Sequence Two Jobs on a Processor: 

Quiz #1: Sequence Two Jobs on a Processor Service Times: Rank Calculations: t1 = 4 t2 = 1 w. prob. .5 10 w. prob. .5 Job Attained Investment Payoff Rank 1 0 4 1.0 4.0 2 0 1 .5 2.0 2 0 5.5 1.0 5.5 2 1 9 1.0 9.0

Two Spheres: 

Two Spheres