CS代写 COMP9334 2 - PowCoder代写

Capacity Planning of Computer Systems and Networks
Week 1A: Introduction to Capacity Planning

About your lecturer

• Research in Computer Networks and Embedded Systems • Example research projects
• Deriveefficientalgorithmsforembeddeddevices
• Enablingbiologicalcomputerstotalktoeachother
• Tools I use in my research • Measurements
• Mathematicalanalysis • Simulation
• Programandtest
https://research.unsw.edu.au/people/associate-professor-chun-tung-chou
T1, 2022 COMP9334 2

Course organisation
• Course web site: www.cse.unsw.edu.au/~cs9334 • Email:
• Read the course outline
• Lectures: Tue 12-2, Thur 12-2, live online
• 2×50-minute.10minutebreak.
• Youcanaskquestionsviachat
• Iwillaskquestions.Youcananswerthemviachat.
• Participantsaremuteduponentry.Iwillunmuteyouifneeded
• Ifyouwanttotalktomeduringthebreak,thentellmeinchat.We will talk in a breakout room.
• Consultation (one-on-one) on Zoom.
• Tue2-2:30pm(Note:timemaychange.Pleasecheck“Timetable”
in the course website to confirm.)
• DifferentZoommeetingidfromthelectures.
T1, 2022 COMP9334 3

Course objective:
• Aim: The design of computer systems and networks to meet performance specifications
• Example problem: You want to design a computer system that can deal with 400,000 HTTP hits per minute. How can you make sure that your system will meet this demand?
• You will learn how to solve capacity planning problems using mathematical modelling.
T1, 2022 COMP9334 4

How to learn?
• Lectures
• Keyconcepts,illustrationbysmallexamples • Don’tjustdependthelecturenotes,youmust
• Readthereferencematerialstoo • Revisionproblems
• Tryifyoucansolvetheproblem
• Tryalsotheexercisesinthebook
• Usediscussionboard
• Don’tthinkyourquestionissilly,othermayhavethesameproblem
• WewillusetheEdplatform.Iwillsendyouaninvitationafterthe first lecture. Please accept the invitation.
• Thekeyisunderstanding,notmemorisation
• Mathematicsissomethingthatyoucangetusedto
T1, 2022 COMP9334 5

• Books and reference materials
• Wewillusematerialsfromanumberofbooks
• Availableinlibraryashardcopyorelectronically
• Two key books:
• Menasce et al. Performance by Design. PH. 2004 (Hard copy)
• Harchol-Balter. Performance Modelling and Design of Computer Systems. CUP, 2013. (Electronic)
• On-line resources
• Journalandconferencearticles • IEEEandACM
• Two general books
• Solvingmathematicalproblems
• Polya, “How to solve it?” (Highly recommended)
• Howtodowellinmathsandscience
• , “A mind for numbers”.
T1, 2022 COMP9334 6

Assessment
• Three assessment components • Assignment(20%)
• Project(30%)
• Finalexam(openbook)(50%)
• Assignment: Extended tutorial questions
• Project: Simulation (coding + statistics)
• Overall mark:
• C=Assignment+Project->RescaleCtobeoutof100 • E=Exammark->RescaleEtobeoutof100
• Overallmark=(C+E)/2
• Passifoverallmark>=50
T1, 2022 COMP9334 7

Assumed knowledge
• Mathematics • Probability
• Probability density function, independence, conditional probability • Statistics
• Vectorsandmatrices,linearequations • Differentiationandintegration
• A good review of probability is in Chapter 3 of Harcol- Balter, “Performance Modeling and Design of Computer Systems”
T1, 2022 COMP9334 8

A quick test on probability
• Probability is fun and very useful, but is sometimes tricky
• Prof. (Big Bang Theory) made a wrong argument in the following clip. Can you use the language of probability to explain his error?
• https://www.youtube.com/watch?v=bjUwSHGsG9o
• Sheldon’s reply on why he thought the person’s name should be . “Mohammed is the most common first name in the world. Li the most common surname. As I didn’t know the answer, I though that gave me a mathematical edge.”
T1, 2022 COMP9334 9

Lecture outline
• Capacity planning • Why?
• Quality of service metrics
• Quantitative performance analysis!”Capacity Planning • What techniques you will learn
• More quality of service metrics
• Single server queues
T1, 2022 COMP9334 10

Why capacity planning?
T1, 2022 COMP9334 11

Why capacity planning?
• The aim of capacity planning is to improve performance of computer systems by adding “capacity”.
• What is performance? • What is capacity?
T1, 2022 COMP9334 12

Design of an e-Commerce systems
• Functionalrequirements
• Productsearch,databasemanagementfunctionsetc
• Search correctness, algorithmic efficiency
• Computerandnetworksecurity
• Systemperformance
• E.g.Canthecomputersystemreturndatabasesearchwithin20msif there are 500 search queries per second?
• If not, should we buy more servers? How many?
performance
• Canyouthinkofothersystemperformancerequirements? T1, 2022 COMP9334 13

Web search engine
• Sayyouareplanningacomputersystemwhichwillhosta search engine that rivals Google
• Currentexpectedworkload • 1000searchespersecond
• Performancespecification • Returnresultswithin10ms
performance
• Whathardwareandnetworkshouldyouuse? • Howmanyservers?Howmuchdiskspace?Etc.
• Whatifworkloadisexpectedtoincreaseby50%inone year, can the system still maintain its performance?
• Question:Canyouthinkofothercapacityparameters?
T1, 2022 COMP9334 14

Capacity planning problems
• Focused on capacity planning of computer systems and networks
• Elements of a capacity planning problems • Given:
• Workload specifications
• Performance specifications
• Capacity e.g. hardware or network requirements, personnel
requirements etc.
• Capacity planning problems are everywhere in life. Can you come out with some capacity planning problems in real life? For each problem, you must identify the workload, performance and capacity parameters.
T1, 2022 COMP9334 15

Capacity planning motivations
• Importanceofperformance
• Canbelifeanddeath
• Availability of critical infrastructure e.g. emergency services
• Customersatisfaction • Availability
• Response time
• Theitalicisedtermsareexamplesofcomputersystem related performance metrics
• AlsoknownasQualityofservice(QoS)metrics
T1, 2022 COMP9334 16

Response time
• Response time
• What is it? (Next slide)
• Possible performance specifications
• Meanresponsetimeislessthan1swhennomorethan5000
requests arrive per second
• 95%oftherequestsarecompletedwithin1swhennomore than 5000 requests arrive / s
• Note: Workload characteristics are also part of the performance specification
COMP9334 17

Response time of a system
Request arrives at time t1
Request completes and leaves at time t2
Response time = t2 – t1.
Measured in seconds. Can be expressed as mean, standard deviation, probability distribution etc.
T1, 2022 COMP9334 18

Availability
• Fractionoftimethesystemisupanduseablebyusers
• Ex:ItiscommonforInternetServiceProviders(ISP)tosign Service Level Agreement (SLA) with their commercial customers. One ISP guarantees that its network outage is less than 6 hours per 30 days. The network availability is 1 – 6/(30*24) = 99.17%
T1, 2022 COMP9334 19

Capacity Planning”Performance analysis
• Capacity planning question:
• AwebserverneedstocompleteanHTTPrequestwithin20ms when there are 500 HTTP requests per second, what CPU speed do you need?
• Let us turn the capacity planning question into a performance analysis question
• Performance analysis question:
• IfthewebserverhasaCPUwithxMIPS,whatistheresponse
time when there are 500 HTTP requests per second?
• If you can solve the performance analysis question for any value of x, you can also solve the capacity planning question
T1, 2022 COMP9334 21

• As a capacity planner, your task is to choose the CPU speed (in MIPS) of a web server so that the mean response time to a specific workload is no more than 25ms.
• You talk to a performance analyst about your problem. The analyst knows an algorithm that predicts the mean response time for any CPU speed.
• You take the algorithm and plug in a number of different CPU speeds. The results are recorded below.
• Can you solve your capacity planning problem?
CPU Speed (MIPS)
4000 T1, 2022 C
Predicted mean response time (ms)

Three performance analysis strategies
• Build the system and perform measurement • Simulation
• Mathematical modelling
• This course will look at
• QuantitativemethodstodeterminetheQoSmetricsofcomputer
systems using
• Queueing networks
• Markov chains
• Usingsimulationtostudyperformance
• Optimisationmethodssuchaslinearandintegerprogramming
T1, 2022 COMP9334 23

Ex. 1: Server farm power allocation
• Aserverfarmconsistsofmultipleservers
• Theserverscanrunat
• Higher clock speed with higher power
• Lower clock speed with lower power
• Ex:Given
• Higher power = 250W, lower power = 150W
• Power budget = 3000W
• You can have
• 12 servers at highest clock speed
• 20 servers at lowest clock speed
• Other combinations
• Which combination is best? • Queueingtheory
T1, 2022 COMP9334 24

Ex 2: Internet data centre availability
• Distributed data centres • Availability problem:
• Eachdatacentremaygodown
• Mean time between going down is 90 days
• Meanrepairtimeis6hours
• CanImaintain99.9999%availabilityfor3outof4centres
• Technique: Markov Chain
T1, 2022 COMP9334 25

Ex 3: Network expansion
• You would like to add communication links to a network. The design questions are: Where to add? How much capacity?
• Technique: Integer programming
T1, 2022 COMP9334 26

Why probability?
• The mathematical methods that we are going to study are based on probability theory. Why probability?
• Let us say 500 HTTP requests arrive at the web server in one second
• A deterministic world will mean
• AnHTTPrequestarrivesevery2ms
• But the arrival pattern is not deterministic, it’s random time
T1, 2022 COMP9334

QoS metrics
• We have seen 2 QoS metrics • Responsetime
• Availability
• More QoS metrics • Throughput
• Reliability(Willdiscusslaterinthecourse) • Scalability(Notdiscussed)
T1, 2022 COMP9334 29

Throughput (1)
• Therateatwhichrequestsarecompleted
• Ex:Fornetworkrouters,throughputcanbemeasuredin
• Packetspersecond(pps)
• Ex: 10 Mpps for 40-byte packets • Note: Should specify packet size
• Otherthroughputmeasures
• Website:HTTPrequests/s,bytes/s • CPU:MIPS,FLOPS
T1, 2022 COMP9334 30

Throughput (2)
• Throughput is a function of the load
• Adisktakes0.01stoperformanI/Ooperation
• MaximumnumberofI/Ooperationpers=100
• If50I/Ooperationsarrivepersecond,thethroughput=50I/O operations/s
• If110I/Ooperationsarrivepersecond,thethroughput=100I/O operations
• Canyoufindaformularelatingthroughout,offeredloadandmax capacity?
• Throughput=min(offeredload,maxcapacity)
T1, 2022 COMP9334 31

Throughput (2*)
• If you find it difficult to do the previous page, you can try this real-life analogy.
• Throughput is a function of the load
• Abaristacanmakeacupofcoffeeevery30seconds
• Maximumnumberofcupsofcoffeethebaristacanmakeinan hour = 120
• If50customersarriveinanhourandeachcustomerordersa coffee, the barista’s throughput = 50 coffees / hour
• If150customersarriveinanhourandeachcustomerordersa coffee, the barista’s throughput = 120 coffees / hour
T1, 2022 COMP9334

Throughput (cont.)
Throughput (3)
Thrasing = congestion collapse
Thrashing = congestion collapse
T1, 2022 COMP9334 33

Throughput (4)
• Performance evaluation can be used to determine the maximum throughput of computer systems
• Example:bottleneckanalysis • Topic for next week
COMP9334 34

Quantitative performance analysis (3)
• Sample performance analysis question:
• IfthewebserverhasaCPUwithxMIPS,whatistheresponse
time when there are 500 HTTP requests per second? • Performanceanalysisquestion:
• A computer system with a certain capacity
• The workload
• The performance (response time, throughput etc) of the system
• Ourmethodis:
• Build analytical models of computer systems
• Animportantpartoftheanalyticalmodelis“queue” • You can surely relate “queues” to “waiting time”
T1, 2022 COMP9334 36

Single server FIFO queue
• QueueingTheoryterminologies • Server:Processingunit
• FIFO:First-infirst-out
• Workconservingserver
• The server cannot be idle when there are jobs waiting to be processed in the queue
• Ex:Shopwithonlyonecheckoutcounter • Theserverisaresource
• Queuesresultfromresourcecontention • Mainconcern:responsetime
T1, 2022 COMP9334 37

Arrival time
Processing time required
Assumption: server is idle when job #1 arrives
Job #1 is admitted into the server immediately since the server is idle.
Job #1 is completed and leaves the system at time 4.
T1, 2022 COMP9334 38

Arrival time
Processing time required
Job #2 arrives when the server is idle. It gets admitted immediately.
Job #2 will be completed at time 10.
T1, 2022 COMP9334 39

Arrival time
Processing time required
Job #3 arrives when Job #2 is being served i.e. the server is busy. Job #3 has to wait in the queue.
Server starts processing Job #3 immediately after finishing Job #2.
T1, 2022 COMP9334 40

Arrival time
Processing time required
246 10 1417
Job #4 arrives when the server is processing Job#2 and Job#3 is in the queue. Job #4 joins the queue. It gets served at time 14, immediately after Job#3 is completed.
T1, 2022 COMP9334 41

Arrival time
Processing time required
246 10 1417
• Definition: Response time = Departure time – arrival time Ex: Response time for Job#4 = 17 – 9 = 8 (= 5 + 3)
• Response time = Waiting time + Processing time
T1, 2022 COMP9334 42

Arrival time
Processing time required
246 10 1417
• Definition: Utilisation = Percentage of time over which the server is busy
•What is the utilisation of the server over the first 12s? • 8/12 = 66.7%
T1, 2022 COMP9334 43

Single server FIFO queues
• Can be used to model
• Shopwithonlyonecheckoutcounter
• AsingleprocessorprocessingjobsinFIFOorder • AdiskprocessingjobinFIFOorder
• Anabstractionoftherealsystem
• Needtocaptureenoughdetailstomeetouranalysisrequirements
T1, 2022 COMP9334 44

What if both inter-arrival time and processing time are determinisitic?
Arrival time
Processing time required
What is the waiting time for each job? What is the response time for each job?
T1, 2022 COMP9334 45

Determining response time
• Generallyweneedtoknow
• Thearrivalpattern
• Ex: The arrival rate
• Ex: The inter-arrival time probability distribution
• Theservicetimeprobabilitydistribution • The time required to process the job
• Sinceweareinterestedinresponsetime,ourmodels capture the time related aspects of the real systems e.g. queueing, processing units
• Wewilllearndifferentmethodstodetermineresponse time in this course
T1, 2022 COMP9334 46

Service time
• Time require to process a request at a resource
• Ex:Theservicetimetosenda1000bytepacketovera10kbpslink
is 0.8s. In this case,
• Service time = packet size / transmission rate
• Ex:TheservicetimetofetchaXbytelargefilefromadiskis • Seek time + X / transfer rate
• Foraclassofresources,wehave
• Service time = Overhead + Job size / Processing rate
T1, 2022 COMP9334 47

• What capacity planning is
• Very important: A capacity planning problem can be solved
by solving a series of performance analysis problems
• Performance metrics
• Responsetime,waitingtime,throughput
• Modelling of single server queues
T1, 2022 COMP9334 48

References
• Reading:
• Menasceetal,Chapters1&2
• Harcol-Balter.Chapters1&2.
• Exercises:
• Revisionproblems:
• See course web site
• Youareexpectedtotrytheseexercises.Solutionswillbeavailable
on the web.
T1, 2022 COMP9334 49

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts