Page 1ECE 254 / CPS 225Fault Tolerant and Testable Computing Systems Modeling and EvaluationCopyright 2004 Daniel J. SorinDuke UniversityECE 254 / CPS 225 2(C) 2004 Daniel J. SorinOutline• Experimental Methodology and Modeling• Modeling• Random Variables• Probabilistic Models• Queuing Network Models• Markov Chain and Petri Net Models• Evaluation Using SimulationECE 254 / CPS 225 3(C) 2004 Daniel J. SorinExperimental Methodology• Follow the scientific rule (“strong inference”)– Devise hypothesis– Conduct experiment that will prove or disprove hypothesis• Keys to good evaluations– Using appropriate experimental tools– Using appropriate metrics– Designing experiments which will produce unambiguous results– NOT running experiments and THEN retro-fitting your hypothesis to match the results you obtained• Goals– Conclusive and persuasive results» Find situations for which your system is “better/worse” than existing systems» Determine which system to use for which scenarioECE 254 / CPS 225 4(C) 2004 Daniel J. SorinModeling• Model: a representation of a system and its behavior– Simulation is a form of modeling (e.g., SimpleScalar)• Why use models?– Can study systems quickly– Can study designs that haven’t been built yet• Caveat: GIGO (garbage in, garbage out)– If your model isn’t good, its outputs won’t be useful/correct• Analytical model = mathematical model– Numerous types of analytical modeling techniques existPage 2ECE 254 / CPS 225 5(C) 2004 Daniel J. SorinModeling Techniques• Simulation• Analytical– Combinatorial– Probabilistic– Queuing network– Markov chain– Petri Net– Etc.• Each type of model has pros and cons– More complexity Æ can model more detail, but tougher to solveECE 254 / CPS 225 6(C) 2004 Daniel J. SorinInputs and Outputs• Inputs– System model (# of components, how they’re connected, etc.)– Component characteristics» Size, speed, failure rate, etc.– Mean Time To Repair (MTTR) is often an input» But not if system self-repair is something we’re studying• Outputs– Performance (latency & throughput)– Reliability R(t)– Availability A(t)– Mean Time To Failure (MTTF)– Mean Time Between Failures (MTBF)ECE 254 / CPS 225 7(C) 2004 Daniel J. SorinA Paper with a Simple Model • “Modeling the Effect of Technology Trends on the Soft Error Rate of Combinational Logic”– by Shivakumar, Kistler, Keckler, Burger, and Alvisi– U. of Texas and IBM/AustinECE 254 / CPS 225 8(C) 2004 Daniel J. SorinOutline• Experimental Methodology and Modeling• Random Variables• Probabilistic Models• Queuing Network Models• Markov Chain and Petri Net Models• Evaluation Using SimulationPage 3ECE 254 / CPS 225 9(C) 2004 Daniel J. SorinRandom Variables• Informally, a random variable X is a variable that takes on a value as a result of an experiment– Time between failures– Time to repair a failure– Time between requests made to a server• Many types of random variables– Deterministic– Exponential (aka Markovian)– Gaussian (aka Normal)– Weibull– Hyper-exponential– Coxian– Etc.ECE 254 / CPS 225 10(C) 2004 Daniel J. SorinCharacterizing Random Variables• Can characterize random variable X in several ways– Mean (aka “expected value”), often denoted as µ or E[X]– Variance, often denoted as σ2» σ2 = E [(X – µ)2] = E[X2] – µ2» Note that E[X2] ≠ (E[X])2– Standard deviation, often denoted as σ» σ = sqrt(σ2 )– Coefficient of variation (CV)» CV = σ/µ– Probability density function (pdf)– Cumulative distribution function (CDF)• The pdf or CDF completely describes a RV– Looking at pdf or CDF, can determine mean, variance, etc.ECE 254 / CPS 225 11(C) 2004 Daniel J. SorinCDF: Cumulative Distribution Function• X is a random variable• CDF: Fx(y) = P[X <= y]– Monotonically increasing function• For an exponential RV:Fx(y) = 1 – e- λy1.0Fx(y)yECE 254 / CPS 225 12(C) 2004 Daniel J. Sorinpdf: Probability Density Function• X is a random variable• pdf: fx(y) corresponds to probability of X=y– Rough intuitive definition, not mathematically precise• P[a <= X < b] = ∫bafx(y)dy• fx(y) >= 0 for all y• lim(yÆinfinity)fx(y) = 0• For exponential RV:fx(y) = λe-λyfx(y)yPage 4ECE 254 / CPS 225 13(C) 2004 Daniel J. SorinExpected Value (mean)• E[X] = mean = ∫ fx(y)dy• For exponential RV (do the math at home):– E[X] = 1/λ• Important notes– In an experiment, E[X] is the expected value, but not the one that will always occur! There is a distribution of values around theexpected value.– Exception to above rule: deterministic distributions always have the same value for every experimentECE 254 / CPS 225 14(C) 2004 Daniel J. SorinPoisson Processes• Let X(t) = a random variable that is the number of events that occur between time 0 and time t• X(t) is a Poisson process if events occur at a constant rate, λ. – I.e., X(t) does not depend on t.• Many system behaviors can be modeled as Poisson processes (even if they aren’t exactly Poisson in reality)• X(t) = Poisson process ÅÆ the time between events is an Exponential random variable ECE 254 / CPS 225 15(C) 2004 Daniel J. SorinExponential Distributions• Denoted by: X(t) ~ Exponential(λ)• Can show that P[X <= t+x | X > t] = 1-e-λx– Not dependent on t Æ “memory-less” or “Markovian” property– Markov chains (later!) depend on this property• “Bus stop” analogy for memory-less property– How long you will wait for a bus is independent of how long you’ve already been waiting for a bus ECE 254 / CPS 225 16(C) 2004 Daniel J. SorinOutline• Experimental Methodology and Modeling• Random Variables• Probabilistic Models• Markov Chain and Petri Net Models• Evaluation Using SimulationPage 5ECE 254 / CPS 225 17(C) 2004 Daniel J. SorinProbabilistic Models• Model system behaviors and failure rates (inputs) with probabilities (probability distributions)• Simple example:C1dataC2C2C3• Assume C2 components are redundant paths• Assume you’re given failure rates for each component• What is the probability of getting correct output?P=0.5P=0.5ECE 254 / CPS 225 18(C) 2004 Daniel J. SorinHazard Rate• Hazard rate z(t) = failure rate at time t• Simplest model is non-time-varying: z(t) = λ– Models failures as a Poisson process– Leads to reliability function that has Exponential distribution• More sophisticated model: