Baixe o app para aproveitar ainda mais
Prévia do material em texto
� Solution Manual for The Art of Computer Systems Performance Analysis Techniques for Experimental Design� Measurement� Simulation� and Modeling By Raj Jain Professor of CIS ���� Neil Avenue Mall� ��� Dreese Lab Columbus� OH ����� ���� Internet Jain�Cis�Ohio State�Edu Tentative Publication Date August ���� Copyright ���� Raj Jain Please do not copy without Author�s written permission� Copy No� For � ��� � Compare the ratio with system A as the base System Workload � Workload � Average A � � � B ���� � ���� Considering the ratio of performance with system A as base� we con� clude that system B is better� � Compare the ratio with system B as the base System Workload � Workload � Average A � ���� ���� B � � � Considering the ratio of performance with system B as base� we con� clude that system A is better� � ��� incomplete ��� Can be done � ��� a� Measurements� Run your favourite programs and pick the one that runs them faster� b� Use measurements and simulations of various network con guirations� c� Measurement� d� a� Analytical modelling b� Analytical modelling and simulations� c� Extensive simulations and modelling� ��� a� � Response time for commonly used programs� � Failure rate rate of crashing�� � Storage capacity� � User�friendliness� b� � Query response time� � Failure rate� � Storage capacity� � Usability� c� � Capacity� � Response time� � Failure rate� d� � Response time� � ��� The following information is from SPEC Standard Performance Evaluation Corporation� home page� CPU benchmarks CINT��� current release Rel� ���� Integer benchmarks contains Name Application espresso Logic Design li Interpreter eqntott Logic Design compress Data Compression sc Spreadsheet gcc Compiler CFP��� current release Rel� ���� Floating point benchmark suite contains Name Application spice�g� Circuit Design doduc Simulation mdljdp� Quantum Chemistry wave� Electromagnetism tomcatv Geometric Translation ora Optics alvinn Robotics ear Medical Simulation mdljsp� Quantum Chemistry swm��� Simulation su�cor Quantum Physics hydro�d Astrophysics nasa� NASA Kernels fpppp Quantum Chemistry More information about these benchmarks can be found in http���performance�netlib�org�performa web page� ��� A C program to implement sieve workload� �� � seive�c � Program to implement sieve workload � �� � �include �stdio�h� �define MaxNum �� � �� List all primes upto MaxNum �� �define NumIterations � �� Repeats procedure NumIterations times �� �define TRUE � �define FALSE void main�void� int IsPrime�MaxNum���� int i�k�Iteration� �� Loop indexes �� int NumPrimes� �� Number of primes found �� printf��Using Eratosthenes Sieve to find primes up to �d�n�� MaxNum�� printf��Repeating it �d times��n��NumIterations�� for �Iteration � �� Iteration �� NumIterations� Iteration��� �� Initialize all numbers to be prime �� for �i � �� i �� MaxNum� i��� IsPrime�i� � TRUE� i � �� while �i�i �� MaxNum� if �IsPrime�i�� �� Mark all multiples of i to be nonprime �� k � i � i� while �k �� MaxNum� IsPrime�k� � FALSE� k � k � i� � �� of while k �� � �� of if IsPrime �� i � i � �� � � �� of WHILE i�i �� NumPrimes � � for �i � �� i �� MaxNum� i��� �� Count the number of primes �� if �IsPrime�i�� NumPrimes � NumPrimes � �� printf���d primes�n��NumPrimes�� � �� of for Iterations �� �� The following can be added during debugging to list primes� �� �� for �i � � i � MaxNum� i��� if �IsPrime�i�� printf���d�n��i�� �� � The result of running the program Using Eratosthenes Sieve to find primes up to �� � Repeating it � times� � � primes � � primes � � primes � � primes � � primes � � primes � � primes � � primes � � primes � � primes � ��� a� Cannot compare systems o�ering di�erent services� b� � Metric response time� � Workload Favourite programs Word processor� spreadsheet� c� Metric response time� functionality Workload A synthetic program which tests the versions using various operating system commands� operating system services� d� � Metric Response time� reliability� time between failures � Workload A synthetic program generating representative �oppy drive I�O requests e� � Metric size of code� structure of code� execution time � Workload A representative set of programs in C and Pascal� � ��� a� � t CPU � � n n X i�� t CPU � �� � � ����� �n I�O � � n n X i�� n I�O � �� ��� � � ����� s � x s � � n� � n X i�� x si � �x s � � � � n� � �� n X i�� x � si � � n�x � s � � ���� �� ����� � � � ���� � Similarly� s � x r � �� ���� ���� �� ��� � � � ������ � b� Normalize the variables to zero mean and unit standard deviation� The normalized values x � s and x � r are given by x � s � x s � �x s s x s � x s � ����� ���� x � r � x r � �x r s x r � x r � ��� ������ The normalized values are shown in the fourth and fth columns of Table b� The other steps are similar to example ���� �� Observation Variables Normalized Variables Principal Factors No� x s x r x � s x � r y � y � � �� ���� ����� ����� ����� ������ � �� ��� ����� ������ ����� ����� � � �� ����� ������ ������ ����� � � �� ������ ������ ������ ����� � � �� ������ ������ ������ ����� � � �� ������ ������ ������ ������ � � �� ������ ������ ������ ������ P x �� ����� ����� ����� ����� ����� P x � ��� ��������� ����� ����� ����� ����� Mean ���� ����� ����� ����� ����� ����� Standard Deviation ���� ������ ����� ����� ����� ����� The correlation between CPU time t CPU � and number of I�O�s n I�O � is ������ The principal factors y � and y � are � y � y � � � � � p � � p � � p � � � p � � � � � t CPU ����� ���� n I�O ����� � ��� � � The rst factor explains ������ ������������ or ��� of total variation� ��� There is no unique solution to this exercise� Depending upon the choice of outliers� scaling technique� or distance metric� di�erent results are possible� all of which could be considered correct� One solution using no outliers� range normalization to ����� and Euclidean distance starts with the the normalized values shown in the following Program CPU time I�O�s TKB ���� ���� MAC ���� ���� COBOL ���� ���� BASIC ���� ���� Pascal ���� ���� EDT ���� ���� SOS ���� ���� BASIC� Pascal� EDT� COBOL� SOS� MAC� and TKB join the dendro� gram at distances of ����� ����� ����� ����� ����� and ����� respectively� �� Other possibilities are to discard TKB and MAC as outliers� normalize using the mean and standard deviation� and transform I�O�s to a logarithmic scale� All these and similar alternatives should be considered correct provided a justi cation is given for the choice� �� ��� a� Hardware monitor as software monitor cannot measure time� b� Software monitor becuase with hardware it is di�cult to monitor soft� ware events� c� Software monitor� Program reference is a software event d� Hardware monitor� Virtual memory reference is a hardware event� e� Hardware monitor� Softwareinterferes with time measurements� f� Software monitor� Database query is high�level software� event� ��� Let us choose a network card our computer subsytem� Then the quantities that can be monitored using the di�erent monitors are as follows a� Software monitor� Total number of packets received� total number of packets sent� Number of error packets� Total bytes sent� b� Hardware monitor� Record of all tra�c to the card using promiscuous mode�� c� Firmware monitor� The card be programmed to monitor tra�c only from a particular node� For the software monitor� using the quantities one could measure the average packet size� error rate in packets� For the hardware monitor� the record of tra�c can be used to measure time between packet arrivals� For the rmware monitor� the number of packets received from a particular node can be measured� �� �� a� Those with the largest number of terminal reads�writes per CPU sec� ond� a� Find the average number of disk reads�writes per second of program X� and the maximum rate that the disk can support� The ratio gives you the number of copies of program X that can run simultaneously on the disk drive� a� Find the mode of typical data recorded by the log and compare that with data of the benchmark� If they are close� then the benchmark is representative� a� I�O bound programs � those with high �disk I�O�s per CPU second� should be chosen for I�O optimization� �� ��� incomplete ��� incomplete �� � �� a� Bar chart� as intermediate values have no meaning� b� Line chart� as intermediate values have meaning� c� Bar chart� no meaning for intermediate value� d� Line chart� intermediate values have meaning� � �� a� a� Axes lables are not self�explanatory� b� Scales and divisions are not shown c� Curves are not labelled� b� a� Y�axis is not labelled� b� No Y�axis scales and division are not shown� c� Y�axis minimum and maximum are not appropriate� c� a� Scales and divisions are not shown� b� Too many curves� c� Curves are not individually labelled� d� a� Order of bars is wrong� b� Y�axis scales divisions not shown � �� incomplete � �� FOM � �� � �� FOM � �� �� ���� Raw Execution Time is a LB Lower is better� parameter� � Compare the ratio with system A as the base Benchmark System A System B System I ���� ���� ���� J ���� ���� ���� K ���� ���� ���� Average ���� ���� ���� Considering the ratio of performance with system A as base� we con� clude that system A is better� � Compare the ratio with system A as the base Benchmark System A System B System I ���� ���� ���� J ���� ���� ���� K ���� ���� ���� Average ���� ���� ���� Considering the ratio of performance with system B as base� we con� clude that system B is better� � Compare the ratio with system A as the base Benchmark System A System B System I ���� ���� ���� J ���� ���� ���� K ���� ���� ���� Average ���� ���� ���� Considering the ratio of performance with system C as base� we con� clude that system C is better� �� System A System B Test Total Pass � Pass � a ax ���� x � b by ���� y Total a � b ax � by � ax�by� a�b Test Total Pass � Pass � c cu ���� u � d dv ���� v Total c� d cu� dv ��� � cu�dv� c�d ���� Consider two systems A and B with two experiments� System A is better than B based on the individual experiments� if the fol� lowing conditions are satis ed ���� x � ���� u and ���� y � ���� v These conditions simplify to x � u and y � v System A is better than B based on total both the experiments�� if ��� ax� by� a � b � ��� cu� dv� c� d which simpli es to ax � by� a� b � cu� dv� c� d If any of the above conditions are satis ed then the percentages can be used for system A�s advantage� �� ���� a� The servers are chosen independently with equal probablility� therefore the probability that server A is chosen P A� � � � � b� P AorB� � P A� � P B� � P AandB�� Only one server at a time is selected� so P AandB� � �� Thus P AorB� � � � � c� �� Only one server at a time is selected� d� P � A� � �� P A� � � � � e� Successive selections are independent� so we can multiple their proba� bilities� Thus P AA� � � � � � � � � � � f� All nine events are independent� each with probablility � � � therefore the probability that they occur in sequence is � � � � ���� The distribution is geometric� The mean of a geometric distribution with pmf � � p� x�� p is � � � p � The variance � � � ��p p � � The standard deviation � � p ��p p � The Coe�cient of variation COV � � � � p �� p� ���� The mean of a Poisson distribution with pmf � x e ��x x is � � �� The variance � � � �� The COV � � � � p �� ���� From ����� we know that the mean and variance of a Poisson distribution with pmf � � p� x�� p are equal to �� x and y are independent random variables� a� Mean x � y� � Mean x� �Mean y� � ��� b� V ar x � y� � V ar x� � V ar y� � ��� c� Mean x � y� �Mean x� �Mean y� � �� d� V ar x� y� � V ar x� � V ar y� � ��� e� Mean �x� �y� � �Mean x� � �Mean y� � ��� f� V ar �x � �y� � �V ar x� � ��V ar y� � ���� COV � p V ar�Mean � � p �� �� ���� pdf � f x� � dF x� dx � e �x�a a � m�� X i� x�a� i i� � � e �x�a � m�� X i� x�a� i a � i� � � x m�� e �x�a m� ���a m Mean � � � Z � xf x�dx � Z � x m e �x�a m� ���a m dx � � m� ���a m Z � x m e �x�a dx Integrating by parts � � m� ���a m h �ax m e �x�a i � � am m� ���a m Z � x m�� e �x�a dx � am m� ���a m Z � x m�� e �x�a dx � a m m� m� ���a m Z � e �x�a dx � m Z � e �x�a dx � am h �e �x�a i � � am��� ���� � am Variance � � � � Z � x� �� � f x�dx � � m� ���a m Z � x� am� � x m�� e �x�a dx � � m� ���a m Z � x m�� � �amx m � a � m � x m�� �e �x�a dx �� � a � m� ��m� �a � m � � a � m � m� ���a m Z � x m�� e �x�a dx � a � m Mode is the maximum possible probability� f x� is maxium when df x� dx � � df x� dx � � m� ���a m m� ��x m�� e�x�a� x m�� e �x�a � � � x m�� e �x�a m� ���a m m� ��� x�a� � � Therefore mode occurs at x � a m� �� C�O�V � � � � p a � m am � � p m ���� pdf � f x� � dF x� dx � ax � a��� Mean � � � Z � � xf x�dx � Z � � ax �a dx � a � x �a�� �a� �� � � � � a a� � Variance � � � � Z � � x� �� � f x�dx � Z � � x� a a� � � � ax � a��� dx Integrating by parts �� � a � x� a a� � � � x �a �a � � � � � Z � � x� a a� � �x �a dx � � a� �� � � � � x� a a� � � x �a�� �a � � � � � � � �a � � Z � � x �a�� dx � �a� �� � � � a� �� � � � �a � � � x �a�� �a � � � � � � �� a� �� � � � a� �� a� �� � �a� �� a � � a� �� � a� �� � a a� �� � a� �� C�O�V � � � � s a a� �� � a� �� a� � a � � q a a� �� � �a a� ��� � � ���� The pdf for normal distribution is given by� f x� � � � p �� e ��x��� � �� � Here � � � and � � �� Hence� f x� � � p �� e ��x��� � � For pdf values for x � �� � � � � � are tabluated below� �� x f x� � �������� � �������� � �������� � �������� � �������� � �������� � �������� � �������� Total �������� a� P X � �� � � � P X � �� � � � P � i�� f i� � � �� xxx answer in the book is wrong� b� P X � �� � P � i�� f i� � ����� xxx answer in the book is wrong� c� f �� � f �� � f �� � f �� � �������� � ���� � xxx answer in the book is wrong� d� P x � � � z � �� � Here � ���� From appendix table A��� z ��� � ������ Hence x � � � ������ � � ����� seconds ��� a� The distribution is not skewed� nor is the data categorical� so we use the Mean� b� The total number of packets makes sense� also the distribution is not skewed� so we use the Mean� c� The distribution is skewed� so we use the Median� d� The keywords constitute categorical information� hence we use the Mode� ���� a� CPU type is a category� so we would use Mode to summarize it� b� Memory size is typically skewed � most personal compters have ap� proximately the same amount of memory� but a few users have lots of memory � so the Median is the best choice� c� Disk type is a category� so we would use the Mode� �� d� Number of peripherals is skewed� so the Median is a good choice� e� Using the same logic as for memory size and number of peripherals� we choose the Median� ���� Since the ratio of maximum to minimum is very high� use the median� The geometric mean can also be used if a logarithmic transformation can be justi ed based on physical considerations� ����� Arithmetic mean since the data is very clustered together not skewed� and y max �y min ratio is small� ����� Use SIQR since the data is skewed� ����� Range � � to �� Variance � �� ���percentile � �� � ��� ������ � �th element � �� ���percentile � �� � ��� ����� � ��th element � �� Semi� Interquartile Range SIQR� � Q � �Q � � Q � � �th element � �� Q � � ��th element � �� SIQR � ��� a� ��� Coe�cient of Variation � ���� Use the coe�cient of variation or standard deviation� since the data is not skewed� ����� The normal quantile�quantile plot for this data is shown in Figure ���� of the book� From the plot� the errors do appear to be normally distributed� �� ���� The normal distribution has the linearity property� Hence� the means get added� when sum of two normal distribution are taken� The variance is given by � � s � � � n � � � � � n � a� From central limit theorem N �� �� p n� is the distribution of the sam� ple means� Here � � �� Hence the distribution is N �� �� p n� b� mean � �� � � q ��n� ��n � q ��n� Hence the distribution is N � q ��n� xxx answer in the book is wrong� c� mean � ��� � ��� � � q ��n� ��n � q ��n� Hence the distribution is N ��� q ��n�� d� mean � ��� � � �� � �� � � q ���n� ���n � �� p �n� Hence the distribution is N �� �� p �n�� e� The sum of square of normal variates has the chi�square � n� distri� bution� f� The sum of the variance has � �n� distribution� g� The ratio of two chi�square distribution has an F distribution� Here both numerator and denominator have the same chi�squre distribution� Hence� F n� n� is the distribution for the ratio of variances� h� If x is normal variate and y � � �� then x� q y�� where � is the degrees of freedom� has a t distribution� Here x��� is normal variate� s x has � n� distribution� The degrees of freedom is n� hence x���� s x � p n� has t n� distribution� ���� The numbers in the sorted order is f �� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��g� There are n � �� numbers� a� The ���p�percentile is x p � x ��� n���p�� � Therefore x ��� ����� ��� � x � � �� and x ��� ����� ��� � x � � � � �� b� Mean � ���� P �� i�� x i � ������ � ����� c� s � � � n�� P n i�� x i � �x� � � �������� There s � p ������� � ������� A ��� con dence interval for the mean � ������ ������ �������� p �� � ������ ������ d� Number of programs with less than or equal �� I�O�s � ��� Fraction � ����� � �� �� A ��� con dence interval for the fraction � p� z ����� s p �� p� n � ������ z s ����� �� ������ �� � ������ ������ ������ � ����� ����� xxx answer in book is wrong� gives ��� C�I�s� e� One�sided con dence interval for mean is given by �x� �x � z ��� s� p n� or �x� z ��� s� p n� �x�� ������ ������ �������� p ��� ������ or ������ ������ ������ �������� p ��� ������ ������ or ������ ��� �� ���� The standard deviation for the codes are s RISC�I � �������� s Z� � � �������� s V AX������ � �������� s PDP����� � �������� s C�� � �������� The ��� con dence interval is given by �x � t � ����� � s� p ��� since n � �� is less than ��� The con dence intervals are CI RISC�I � �������� ��������� CI Z� � � �������� ��������� CI V AX������ � �������� ��������� CI PDP����� � ������� ��������� CI C�� � ������� ��������� xxx answer in the book is wrong� Let us choose RISC�I and Z���� as the two systems� a� The con dence intervals for both the processors include �� so if the processors are not di�erent� b� incomplete� question not clear � �� ���� incomplete refer math book to use Langrange multiplier technique� ���� A linear model to predict disk I�O�s as a function of CPU time can be developed as follows For this data n � �� !xy � ����� !x � ��� !x � � ���� !y � ���� !y � � ��� ���� �x � ����� �y � ������ Therefore� b � � !xy � n�x�y !x � � n �x� � � ����� �� ����� ����� ���� �� ����� � � ������ b � �y � b � �x � ������ ������� ���� � ������ The desired model is Number of disk I�O�s � ������ � ������ CPU time� SSE � !y � �b !y�b � !xy � ��� �������������������������� � ������ SST � SSY� SS� � !y � � n �y� � � ��� ���� �� ������ � � ������� SSR � SST� SSE � �������� ������ � ������� R � � SSR SST � ������� ������� � ������ Thus� the regression explains ��� of CPU time�s variation� The mean squared error is MSE � SSE Degrees of Freedom for Errors � ������ � � ����� The standard deviation of errors is s e � p MSE � p ����� � ����� s b � � s e � � n � �x � !x � � n�x � � ��� � ����� � � � � ����� � ���� �� ����� ���� � ��� � ������ s b � � s e �!x � � n�x � � ��� � ����� ����� �� ����� ����� ��� � ������ �� The ��� con dence interval for b is ������� ������ ������� � ������� ������� �������� ������� Since this includes zero b is not signi cant� The ��� con dence interval for b is ������� ������ ������� � ������� ������ � ������� ������� a� Only b � is signi cant� b� ��� xxx answer in book is wrong it said �� c� y expected � ������ � ������ � �� � �� ����� d� s �y �p � ����� � � � � � � ��� ����� � ���� � ����� � � ��� � ������� The ��� con dence interval for a single prediction � ��������� ������ �������� � ��������� ������� � ������� ������� xxx answer in book is wrong ������� ������� � e� s �y �p � ����� � � � � ��� ����� � ���� � ����� � � ��� � ������� The ��� con dence interval for predicted mean � ��������� ������ �������� � ��������� ������� � ������� ������� xxx answer in book is wrong ������� ������� � �� ���� For the data n � �� !xy � ��� ���� !x � ����� !x � � ���� ���� !y � ��� !y � � ���� �x � ������� �y � ����� Therefore� b � � !xy � n�x�y !x � � n �x� � � ��� ���� �� ������� ���� ���� ���� �� ������� � � ������ b � �y � b � �x � ����� ������� ������ � ������ The desired model is CPU time in milliseconds � ������ � ������� memory size in kilobytes� SSE � ������� SST � ��������� SSR � ��������� R � � ������ MSE � ������� s e � ������� s b � � ������� s b � � ������� The ��� con dence intervals of b and b � are �������� ������� and ������� �������� the intercept is zero but the slope is signi cant� ���� Elasped time � ����� number of days� � ������ the ��� con dence intervals for the regression coe�cients are ����� ����� for the intercept and ����� ����� for the slope� both are signi cant� Note Calculations are similar to the solution for exercise ����� ���� Elapsed time � ������������ number of keys�� R � � ������ the con dence intervals of the coe�cients are ������������ and ������������� respectively� Note Calculations are similar to the solution for exercise ����� ���� Number of disk I�O�s � ������ � ����� � number of keys�� R � � ������ the ��� con dence intervals for the coe�cients are �������� ������� and ����� ������� b is not signi cant� Note Calculations are similar to the solution for exercise ����� ���� Time � ���������� � ������ record size�� R � � ������ Both parameters are signi cant� However� the scatter plot of the data shows a nonlinear relationship� The residuals versus predicted estimates show that the errors have a parabolic trend� This indicates that the errors are not independent of the predictor variables and so either other predictor variables or some nonlinear terms of current predictors need to be included in the model� �� ���� yyy question not clear� no x � � but solution talks about x � � � a� R � ���� R � � ������� So ������ of variance is explained by the regression� b� Yes c� x � d� x � e� x � � x � � and x � f� Multicollinearity possible g� Compute correlation among predictors and reduce the number of pre� dictors� Table ���� Time to Encrypt a k�bit Record after log tranformation� ���� log � k� Uniprocessor Multiprocessor ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� ����� Let us use the following model y � b � b � x � � b � x � where y is log time�� x � is the key size and x � is a binary variable� x � � �� multiprocessor and x � � ��uniprocessor� In this case X � � � � � � � � � � � � � � � � � ����� � � ����� � � ����� � � ����� � � ����� � � ����� � � ����� � � ����� � � � � � � � � � � � � � � � �� X T X � � � � � ������ � ������ ������ ������ � ������ � � � C � X T X� �� � � � � ����� ������ ����� ������ ����� � ����� � ��� � � X T y � � � � ������ ������ ������ � � The regression parameters are b � X T X� �� X T y � ������� ������������� T The regression equation is log time� � ������ � ����� log key size�� �����x � R � � ������� The con dence intervals of the coe�cients are ������ ������� ����� ������ and ������ ������� �� ���� Each of the factors have � levels� a� A full factorial experiment is necessary if there is signi cant interaction among factors� Hence� number of experiments is �� �� � � ��� b� If there is no interaction among factors� then simple design can be used� The number of experiments is � � �� �� � �� �� � �� �� � � � c� A fractional factorial experiment can be used if the interaction is small among factor� Hence� number of experiments is � ��� � � xxx answer in book is wrong� The answers for b� and c� are interchanged� �� ���� The sign table for this data is given below I A B C AB AC BC ABC y � �� �� �� � � � �� ��� � � �� �� �� �� � � ��� � �� � �� �� � �� � �� � � � �� � �� �� �� �� � � �� �� � � �� �� � �� � � �� � �� � �� �� �� � �� � � �� �� � �� �� � � � � � � � � �� ��� �� ���� ���� ��� �� ��� �� Total ������ ����� ������� ������� ������ ����� ������ ����� Total�� SST � � � q � A � q � B � q � C � q � AB � q � AC � q � BC � q � ABC � � � ����� � � ������ � � ������ � � ����� � � ����� � � ������ � � ����� � � � ������ � �������� � �������� � ������ � ������ � �������� � ������� � ��������� a� q � ������ q A � ����� q B � ������� q C � ������� q AB � ������ q AC � ����� q BC � ������ and q ABC � ���� b� The portion of variation explained by the seven e�ects are ���������������� ������������������������� ���� �������� ���������������� ������� ���������������� ������� ������������������ �������� and ����������������� ������� respectively� c� Sorting according to their coe�cient values� the factors with decreasing order of importance are BC� C� B� ABC� A� AB� AC �� � �� Let A indicate workload and B indicate Processor�s used� I A B AB y Mean �y � �� �� � ������ ������ ������ ������ � � �� �� ������������������ ������ � �� � �� ������������������ ������ � � � � ������������������ ������ ������� ������ ������ ������� Total ����� ������ ����� ������ Total�� The e�ects are ������ ����� ������ and ������ The e�ect of workloads ������ is not signi cant� Interactions explain ������ of the variation� �� ���� The following sign table with I � ACD as the generator polynomial is used to analyze the � ��� design� I A B C AB D BC BD y � �� �� �� � � � �� �� � � �� �� �� �� � � ��� � �� � �� �� � �� � �� � � � �� � �� �� �� ��� � �� �� � � �� �� � �� � � �� � �� � �� �� �� � �� � � �� �� � �� �� � � � � � � � � �� ��� ��� �� ���� �� ���� �� ��� Total ������ ������ ����� ������� ����� ������� ����� ������ Total�� a� q � q ACD � ������ q A � q CD � ����� q B � q ABCD � ������� q C � q AD � ������� q AB � q BCD � ������ q AC � q D � ����� q BC � q ABD � ������ and q ABC � q BD � ���� b� ������ ������� ������� ������ ������ ������� ����� c� BC� C� B� BD� A� AB� D� Higher order interactions are assumed smaller� d� The generator is I � ACD� Theconfoundings are I � ACD� A � CD� B � ABCD� C � AD� D � AC� AB � BCD� BC � ABD and ABC � BD e� I � ABCD may be better since its resolution will be IV� f� R III � since the generator is I � ACD� ���� Yes� I � ABC is a � ��� III design� yes� I � AB is a � ��� II design� yes� I � ABCD is a � ��� IV design� �� � �� Rewrite the given equation as j � r X i�� a X k�� a ikj y ik We know that j � �y �j � � � �y �j � �y �� Expanding the terms for �y �j and �y �� we get the following equation� j � � r r X i�� y ij � � ar r X i�� a X k�� y ik Collecting the terms we get j � � r � � ar � r X i�� y ij � � ar r X i���i��j a X k�� y ik Comparing the coe�cients of y ij we get a ikj � � r � � ra � k � j �� ra � Otherwise xxx answer in book is wrong� it gives ��ar instead of ���ar� The variance of e ij can be written as � � e � j � � � e r X i�� a X k�� a ikj � � e � j � � r � � r � � ra � � � ar � r� � � ra � � � � � e � � ra � a� �� � � � ra � a� �� � � � e � � a� �� ra � a� �� � �� � � � e � a� ��� � e ar �� Table ���� Computation of E�ects for the Scheme versus Spectrum Study Row Row Ro Workload Scheme�� Spect��� Spect���� Sum Mean E�e Garbage Collection ����� ����� ����� ������ ����� ���� Pattern Match ����� ����� ����� ����� ����� ����� Bignum Addition ������� ������� ������� ������ ������ ����� Bignum Multiplication ����� ����� ����� ����� ����� ����� Fast Fourier Transform ����� ����� ����� ����� ����� ������ ���� Column Sum ������ ������� �������� ������� Column Mean ������ ������ ������ ������ Column e�ect ������ ����� ������ ���� The computation of e�ects for Scheme versus Spectrum study is given in table ���� SSY � X ij y � ij � ��� ������� SS� � ab� � � �� �� ������� � � �� ������� SSA � b X j � j � �� � ������� � � ������ � � ������� � � � ������� SSB � a X i � � i � �� � ������� � � �������� � � �������� � � �������� � � ������� � � � �� ������� SST � SSY� SS� � ��� �������� �� ������� � ��� ������� SSE � SST� SSA� SSB � ��� �������� �������� �� ������� � �������� The di�erences of the e�ects of di�erent processors are������������ � ������� ������ � ����� � ������ and ����� � ����� � ������� MSE � SSE a� �� b� �� MSE � �������� �� �� �� �� � ������� s e � p MSE � p ������� � ������ �� Table ���� Computation of E�ects the Intel iAPX ��� Study System Workload Row Row Row No� ��� Sieve Puzzle Acker Sum Mean E�ect � ����� ����� ����� ����� ������ ����� ������� � ����� ����� ����� ����� ������ ����� ������� � ����� ����� ����� ����� ������ ����� ������� � ����� ����� ����� ����� ������ ����� ������� � ����� ����� ����� ����� ������ ����� ������� � ����� ����� ����� ����� ������ ����� ������ � ����� ����� ����� ����� ����� ����� ������� � ����� ����� ����� ����� ������ ����� ������� � ����� ����� ����� ����� ������ ����� ������ �� ����� ����� ����� ����� ������ ����� ������ �� ����� ����� ����� ����� ������ ����� ������ �� ����� ����� ����� ����� ������ ������ ������ Column Sum ����� ������ ������ ������ ������� Column Mean ����� ����� ����� ����� ����� Column E�ect ������ ������ ����� ����� The standard deviation for the di�erences � s e � p � � ������������ � ������ The con dence intervals for the di�erences are ������ ���� � ������ � ������ �������� � �������� ������ ������� ���� � ������ � ������� �������� � �������� ������� ������� ���� � ������ � ������� �������� � ������� ������� The processor are not sign cantly di�erent� The plots of residul errors does not show any trend and the plot of normal quantile�quantile plot does appear linear� But since the y max �y min is large a multiplicative model should be used� ���� The table after the log transformation is shown in table ����� The ANOVA for Scheme versus Spectrum study is given in table ����� which agrees with the table ����� given in the book� �� Table ���� ANOVA Table for the Intel iAPX ��� Study Compo� Sum of �Variation DF Mean F � F � nent Squares Square Comp� Table y ������� y �� ������� y � y �� ������� ������ �� Workload ������� ����� � ���� ������ ��� System ������ ����� �� ��� ���� ��� Errors ���� ���� �� ���� s e � p MSE � p ���� � ���� ���� After logarithmic transformation� the table for computing e�ects is shown in table ����� The ANOVA table for RISC Code size study is given in table ����� The con dence intervals for e�ect di�erences are shown in table ����� a� ����� variation is explained by the processors b� ������ variation is due to workloads� c� Yes� several processor pairs are signi cantly di�erent� at ��� con � dence level� ���� After log transformation� the table for computing e�ects including ����� column� is given in table ����� The ANOVA table including ����� column is given in table ����� The con dence intervals of e�ect di�erences for RISC code study in� cluding column ����� is given in table ������ a� ����� variation is explained by the processors� b� ������ variation is due to workloads� c� Yes� several processor pairs are signi cantly di�erent at ��� con dence level� �� Table ���� Computation of E�ects for the RISC Code Size Study Processors Row Row Row Workload RISC�I Z���� VAX������� PDP������ C��� Sum Mean E�ect E�String Search ���� ���� ���� ���� ���� ����� ���� ����� � F�Bit Test ���� ���� ���� ���� ���� ����� ���� ����� H�Linked List ���� ���� ���� ���� ���� ����� ���� ����� K�Bit Matrix ���� ���� ���� ���� ���� ����� ���� ����� I�Quick Sort ���� ���� ���� ���� ���� ����� ���� ���� Ackermann ���� ���� ���� ���� ���� ���� ����� ���� ����� Recursive Qsort ���� ���� ���� ���� ���� ����� ���� ���� Puzzle Subscript� ���� ���� ���� ���� ���� ����� ���� ���� Puzzle Pointer� ���� ���� ���� ���� ���� ����� ���� ���� SED Batch Editor� ���� ���� ���� ���� ���� ����� ���� ���� Towers Hanoi ��� ���� ���� ���� ���� ���� ����� ���� ����� Column Sum ����� ����� ����� ����� ����� ������ Column Mean ���� ���� ���� ���� ���� ���� Column E�ect ���� ���� ����� ����� ����� Table ���� ANOVA Table for RISC Code Size Study Compo� Sum of �Variation DF Mean F � F � nent Squares Square Comp� Table y ������ y �� ������ y � y �� ����� ������ �� Workload ���� ����� � ���� ���� ���� System ����� ������ �� ���� ������ ���� Errors ���� ����� �� ���� s e � p MSE � p ���� � ���� �� Table ���� Con dence Intervals of E�ect Di�erences in the RISC Code Size Study RISC�I Z���� VAX������� PDP������ C��� RISC�I �����������y ����� ����� �����������y ����� ����� Z���� ����� ����� ����� ����� ����� ����� VAX������� �����������y ������ �����y PDP������ ������ �����y y � Not signi cant Table ���� Computation of E�ects for the RISC Code Size Study Processors Row Row Workload RISC�I ����� Z���� ������ ����� C��� Sum Mean E E�String Search ���� ���� ���� ���� ���� ���� ����� ���� �� F�Bit Test ���� ���� ���� ���� ���� ���� ����� ���� � H�Linked List ���� ���� ���� ���� �������� ����� ���� � K�Bit Matrix ���� ���� ���� ���� ���� ���� ����� ���� � I�Quick Sort ���� ���� ���� ���� ���� ���� ����� ���� Ackermann ���� ���� ���� ���� ���� ���� ���� ����� ���� � Recursive Qsort ���� ���� ���� ���� ���� ���� ����� ���� Puzzle Subscript� ���� ���� ���� ���� ���� ���� ����� ���� Puzzle Pointer� ���� ���� ���� ���� ���� ���� ����� ���� SED Batch Editor� ���� ���� ���� ���� ���� ���� ����� ���� Towers Hanoi ��� ���� ���� ���� ���� ���� ���� ����� ���� � Column Sum ����� ����� ����� ����� ����� ����� ������ Column Mean ���� ���� ���� ���� ���� ���� ���� Column E�ect ���� ����� ���� ����� ����� ����� �� Table ���� ANOVA Table for RISC Code Size Study Compo� Sum of �Variation DF Mean F � F � nent Squares Square Comp� Table y ������ y �� ������ y � y �� ����� ������ �� Workload ���� ����� � ���� ���� ���� System ����� ������ �� ���� ������ ���� Errors ���� ����� �� ���� s e � p MSE � p ���� � ���� Table ����� Con dence Intervals of E�ect Di�erences in the RISC Code Size Study ���� Z���� ������ ����� C��� RISC�I ���������� �����������y ����� ����� �����������y ����� ����� ����� ������ ������ ������ �����y ������ ������ ������ �����y Z���� ����� ����� ����� ����� ����� ����� ������ �����������y ������ �����y ����� ������ �����y y � Not signi cant �� Table ����� Computation of E�ects for exercise ���� A Row Row Row B A� A� A� Sum Mean E�ect B� ������ ������ ������ ������� ������ ������� B� ������ ������ ������� �������� ������� ������ B� ������ ������ ������ ������� ������ ������� B� ������ ������ ������� ������� ������� ������ B� ������ ������� ������� �������� ������� ������ Column Sum ������� ������� ������� �������� Column Mean ������ ������ ������� ������ Column e�ect ������� ������� ������ Table ����� Interactions B A� A� A� B� ������ ������ ������� B� ������� ����� ����� B� ������ ������ ������� B� ������ ������� ������ B� ������� ������� ������ ���� The table for computing e�ects is given in table ������ The interactions are given in table ������ The Analysis of Variance table is given table ������ The ��� con dence intervals for e�ects are given in table ������ The ��� con dence intervals for the interactions are given in table ������ The ��� con dence intervals for the e�ect di�erences are given in table ������ a� Yes� All processors are signi cantly di�erent from each other� b� ����� c� All e�ects and interactions are signi cant� �� Table ����� ANOVA Table exercise ���� Compo� Sum of �Variation DF Mean F � F � nent Squares Square Comp� Table y ���������� y �� ���������� y � y �� ���������� ������ �� A ���������� ����� � ��������� �������� ��� B ��������� ����� � ��������� ������� ��� Interactions ��������� ����� � �������� ������ ��� Errors ������ ���� �� ���� s e � p MSE � p ���� � ����� Table ����� Con dence Intervals for E�ects Para� Mean Std� Con dence meter E�ect Dev� Interval � ������ ���� ������� ������� A A� ������� ���� �������� �������� A� ������� ���� �������� �������� A� ������ ���� ������� ������� B B� ������� ���� �������� �������� B� ������ ���� ������� ������� B� ������� ���� �������� �������� B� ������ ���� ������� ������� B� ������ ���� ������� ������� �� Table ����� Interactions B A� A� A� B� ������� ������� ������� ������� �������� �������� B� ���������������� ������������ ������������ B� �������������� �������������� ���������������� B� �������������� ���������������� �������������� B� ���������������� ���������������� �������������� Table ����� Interactions A� A� A� A� �������� �������� ��������� ��������� A� ��������� ��������� �� ���� The experiment number � maximizes T I ������ so T I is high for A � ��� B � ��� and E � ��� The experiment number � maximizes T B ������ so� T B is high for A � ��� B � �� and D � ��� ���� The throughputs are ranked according to decreasing value of T I and it is seen that� T I is high for A � ��� B � ��� and E � ��� Similarily when the throughputs are ranked according to decreasing value of T B it is seen that� T B is high for A � ��� B � �� and D � ��� �� ���� a� y t� � t � ��� Countinuous state� deterministic� dynamic� linear� and unstable b� y t� � t � Continuous state� deterministic� dynamic� nonlinear� and unstable c� y t � �� � y t� � "� " is not an integer� Discrete time� continuous state� deterministic� dynamic� linear� and unstable d� n t� �� � �n t� � � Discrete time� deterministic� dynamic� linear� and unstable e� y t� � sin wt� Continuous time� continuous state� dynamic� nonlinear� and stable f� �y t � �� � �y t� � " Discrete time� continuous state� probabilistic � dynamic� linear� and unstable ���� a� Since the number of factors this is best modeled by a Trace�driven simulation� b� The known distribution can be used to generate the events� Hence this is best modeled by Discrete�event simulation� c� The value of � is independent of time� Hence Monte Carlo simulation is best suited to nd the value of �� ���� The unit time approach is a time�advancing mechanism to adjust the sim� ulation clock� In this approach the time is incremeneted in small intervals and checks are done at each increment to see if there are any events which have to be scheduled� This approach is generally not used� since unnecessary increments and checks are done during idle time� �� ���� a� This is expected when the system is underloaded� Make sure that the system is in underloaded region b� This is quite common when the system is overloaded� Make sure that the system is in overloaded region c� This is expected� d� This is uncommon and would require validation� e� This is rare and would require serious validation e�ort� ���� The transient interval using the truncation method is �� since � is neither the maximum nor the minimum of the remaining observations� However� this is incorrect� since the actual transient interval seems to be �� �� ���� This is multiplicative LCG� Hence the maximum Maximum period is � l�� � � ��� � �� a must be �i� �� that is � or ��� The seed must be odd� ���� The values of �� n mod �� for n � �� � � � � �� are ��� ��� ��� ��� ��� �� �� ��� ��� ��� ��� ��� ��� �� ��� �� ��� �� ��� �� ��� ��� ��� �� �� ��� ��� ��� ��� �� The smallest n that results in � is ��� Yes� �� is a primitive root of ��� ���� �� �� �� � ���� ���� ���� x � � ������������� ���� q � m div a � �� div �� � � r � m mod a � �� mod �� � � No� the seqence generated with and without Schrage method are di�erent� Since� q � � and r � � do not satisfy the condition r less than q� ���� q � m div a � �� div �� � � r � m mod a � �� mod �� � � Since� q � � and r � � do not satisfy the condition r � q� this cannot be implemented using Schrage�s method� ��� a� Primitive b� Primitive c� Not primitive� Since � � x � � x � � �� x � � � �� x � � d� Primitive ���� a� ��� b� �� Since x � � �� x � � x� �� � x � � � �� Table ����� Tausworthe method Step� Copy seed Y � ������ ������ ������ ������ ������ Step� ��bit Right shift Y � ������ ������ ������ ������ ������ Step� Xor Y � � Y � � Y � ������ ������ ������ ������ ������ Step� ��bit Left shift Y � ������ ������ ������ ������ ������ Step� Xor� Y � � Y � � Y � ������ ������ ������ ������ ������ c� ���d� ��� Since x � � � x � � � �� x � �� �� � x � �� � ���� The characteristic polynomial is x � � x � �� In this case r � �� q � �� and q � r � �� We need a ��bit right shift and ��bit left shift� The initial seed is X � ������� The sequence of calculations are show in table ������ Hence the rst ve ��bit numbers are �������� � � �������� � � �������� � � �������� � � �������� � � ����� In both cases� the additive parameter c should be replaced by c mod m� ����� The rst �� numbers and their binary representations are listed in ta� ble ������ From the table it can be seen that the period of the lth bit is � l � �� Table ����� Random Numbers Generated by the LCG x n � ��x n�� � �� mod � �� n x n Decimal Binary � �� �� � ��� � � �� � ���� � ��� � � ������ �� � � � �� � � � � ������ �� �� �� �� ��� � � �� � � � � �� ��� � ��� � � �� � �� � ��� �� �� ���� ��� � � � � � � � � ��� � � ���� � � �� � �� �� ���� �� � ���� � �� ������ � � ���� ���� � �� ��� �� ��� �� � � �� ��� �� � � ���� �� ����� �� ��� �� ��� ��� � ���� �� ����� �� � �� � � �� ����� � ��� � � � �� ������ � �� � � � �� � ������ � � �� � � � ������ �� � � � � � � �� ���� The nal seed value is ���������� The nal random number is ��������� Table ����� Chi�Square Test on ������ Numbers Cell Observed Expected Observed�Expected� � Expected � ��� ������ ����� � ���� ������ ����� � ��� ������ ����� � ��� ������ ����� � ���� ������ ����� � ���� ������ ����� � ��� ������ ����� � ��� ������ ����� � ���� ������ ����� �� ���� ������ ����� Total ����� ������� ����� The computed statistic is ������ The ����quantile of a chi�square variate with nine degrees of freedom is ������ The sequence doest not passes the test at ���� ���� Fifteen random numbers generated using the given LCG are �� ��� ��� ��� �� ��� �� �� ��� �� �� �� ��� �� �� The normalized numbers obtained by dividing by �� are �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� �������� Table ����� shows a sorted list of these numbers and di�erences� Usin the maximum values obtained from the table� K�S statistics can be computed as follows K � � p n max j � j n � x j � � p ��� ������� � ������ K � � p n max j � x j � j � � n � � p ��� ������� � ������ K � � �������K � � ������� Both values are less thanK � ������� �������� The sequence passes the test� �� Table ����� Computation for the K�S Test j x j j n � x j x j � j�� n � ������� ������� ������� � ������� ������� ������� � ������� ������� ������� � ������� ������� ������� � ������� ������� ������� � ������� ������� ������� � ������� ������� ������� � ������� ������� ������� � ������� ������� ������� �� ������� ������� ������� �� ������� ������� ������� �� ������� ������� ������� �� ������� ������� ������� �� ������� ������� ������� �� ������� ������� ������� Max ������� ������� Table ����� Autocovariances for the Random Sequence for exercise ���� Lag Autocovariance St� Dev� ��� Con dence Interval k R k of R k Lower Limit Upper Limit � ��������� �������� ��������� ��������� p � �������� �������� ��������� �������� � ��������� �������� ��������� �������� � ��������� �������� ��������� �������� � �������� �������� �������� �������� p � ��������� �������� ��������� �������� � �������� �������� ��������� �������� � �������� �������� ��������� �������� � ��������� �������� ��������� ��������� p �� �������� �������� ��������� �������� �� ���� The autocovariance and con dence intervals for the serial autocovariances at lags � to �� are given in table ������ Three autocovariance at lag �� �� �� are signi cant� ���� The pairs generated by the rst generator lie on the following two lines with a positive slope x n � � � x n�� � �� � k� k � �� � The distance between the lines is ��� p �� The pairs generated by the second generator lie on the following two lines with a negative slope x n � ��x n�� � ��k� k � �� � The distance between the lines is ��� p �� Both generators have the same ��distributivity� �� � �� a� Inverse transformation Generate u � U �� ��� If u � ���� then x � p �u� otherwise x � �� q � �� u�� b� Rejection Generate x � U �� �� and y � U �� ��� If y � min x� �� x�� then output x� otherwise repeat with another pair� c� Composition The pdf f x� can be expressed as a weighted sum of a left triangular density and a right triangular density� d� Convolution Generate u � � U �� �� and u � � U �� ��� Return u � � u � � �� ���� a� Geometric� Geometric distribution is used to model number of at� tempts between successive failures� b� Negative binomial� It can be used model the numberof failures before the mth success� c� Logistic� � xxx� d� Normal� The mean of large set of uniform distribution is a normal distribution� e� Lognormal� The product of large set of uniform is a lognormal distri� bution� f� Pareto� This is used t power curves� g� Poisson� Sum of two Poisson�s is a Poisson distribution� h� Chi square� Variances of normal population has chi�square distribution� i� F � Ratio of variances of normal population has F distribution� j� Exponential� Exponential is used to model memoryless events� k� Erlang�m� Sum m memoryless servers can be represented by Erlang�m distribution�� l� Binomial� This models the successes in n independent and identical Bernoulli trails� m� Beta� This is used to model ratio of random�variates� ���� a� Sum of normal distribution is normal� � � ��� � ��� � q ��� � �� Hence it is a N �� �� distribution� ��� quantile is ����� from appendix table A�� b� Sum of variances is chi�square distribution� There are � normal variates� hence it is a � �� distribution� ��� quantile is ����� from appendix A��� �� c� Ratio of two chi�square variates is a F distribution� Since both numer� ator and denominator have two variates the degrees of freedom is � for both� Hence it is a F �� �� distribution� ��� quantile is ���� from appendix A��� d� Ratio of normal to square root of chi�square distribution is a t distinc� tion� Number of degrees of freedom is �� Hence it is a t �� distribution� ��� is ����� from appendix A��� �� � �� Erlang�k arrivals� general bulk service� ve servers� ��� waiting positions� ���� population size� and last come rst served preemptive resume service� � �� Because it provides �� waiting positions for a population of only �� Also� since there are �� servers and only �� waiting positions� two servers have no waiting positions� � �� Both will provide the same performance� Increasing bu�ers beyond the population size has no e�ect� � �� E�n� � �E�r� � � �� �� � � � � �� Job �ow balance was assumed� Service time distribution has no e�ect� � �� If k � � then E k becomes a exponential distribution� Hence E k �M�� can be called a Poisson process if k � �� �� ���� a� The probability p n for birth�deathprocesses is given by p n � � � � � n�� � � � � � n p � n � �� �� � � � � Here � n � � n�� and � n � �� Therefore p n � n n� p �where � � � b� The sum of the probabilities should be �� Therefore� p � � � � P � n� � n n p � e �� c� E�n� � � X n�� np n � p � X n�� n n n� E�n� � e �� e � � d� � � � � � �� e �� � e� E�r� � E�n� � � � � � � ��e �� � ���� a� The probability p n for birth�death processes is given by p n � � � � � n�� � � � � � n p � n � �� �� � � � � Here � n � � and � n � n�� Therefore p n � n n� p �where � � � b� p � e �� derivation is similar to previous exercise solution� c� E�n� � �� d� Var�n� � E�n � �� E�n�� � � P � n�� n � � n n p � � � e �� � ��e � � � Var�n� � e� E�r� � E�n� � � � � ���� a� � ����� � ��� b� E�s� � ��� � E�r� �� � � � �� ���� � ��� � ��� second c� � � � � ����� �� ����� � ��� queries per minute d� E�n� � � ��� � ��� ����� � � e� P n � ��� � �� � ���� � � � ����� f� r � � E�r� ln���� � ��� seconds g� w � � E�r� ln��� � � ���� seconds ���� a� � � m� � � �� �� � �� � ��� b� p � ���� c� � � �� ��� � � �� ��� ���� � ���� d� E�n� � � � ��� � ���� ����� �� ���� � ���� e� E�n q � � ���� ����� �� ���� � ���� f� E�r� � � � � � � ��� � �� ��� � � ������ second g� Var�r� � ������� second � use forumla �� of Box ����� h� w � � ������ second use formula �� of Box ����� ���� a� � � ���� � ��� � ��� ������� � ��� b� p � � ���� c� � � ���� d� E�n� � �� �� �� � � request per drive e� E�n q � � �� � �� �� � ��� request per drive f� E�r� � ��� �� �� � ��� second g� Var�r� � E�r�� � � ���� ��� � ���� second � h� w � � ���� second use formula �� of Box ����� ���� Yes� With the new system� the ���percentile of the waiting time will be zero� ���� Yes� since with � � ������� � ������� average waiting time is ���� minutes and the ���percentile of waiting time is zero� �� ��� a� p � ���� use formula � of Box ����� p � � ����� p � � ����� p � � ����� p � � ������ use formula � of Box ����� b� E�n� � ��� requests use formula � of Box ����� c� E�n q � � ������ requests use formula � of Box ����� d� Var�n� � � � � p � � � � � p � � � � � p � � � � � p � � ���� � � ��� e� � � � � �� p B � � �� �� ������� � �� requests per second f� Loss rate� �p B � ��� ������ � ��� requests per second g� U � �� p B � � ��� �� ������� � ���� h� E�r� � E�n��� � � ������ � ������ second ���� The probability p n for birth�death processes is given by p n � � � � � n�� � � � � � n p � n � �� �� � � � � p n � � � � � � � � � � � � p m � n � K n � � � n � m p n � K n � n m m m m � n � K where � � m� Average throughput � � � P K�� n� K � n��p n � � K � E�n�� U � � � m� � K � E�n�� E�r� � E�n� � � � E�n� � K�E�n�� ���� p n � � � � � � � � � � � � � K n � m � n p � � n � m � K n � n �� n m m m p m � n � B where� � � m� � Average throughput � � � P B n� K � n��p n � � K � E�n�� K � B�p B � where p B is the probability of B jobs in the system� U � � � m� � K � E�n�� K �B�p B � E�r� � E�n� � � � E�n� � K�E�n�� K�B�p B � �� ���� a� Job �ow balance� Number of job arrivals is not equal to number of departures since some jobs are lost� b� Fair service c� Single resource possession d� Routing homogeneity e� No blocking f� Single resource possession g� One�step behavior �� ���� X����������� S������� U � XS����������� ���� n��� X��� n � XR � R���� second� ���� X��������� V disk ���X disk � XV disk ��� S disk ������� U disk � X disk S disk �� � ���� � ���� � ��� ���� X printer ����������� V printer ��� X � X printer �V printer � ���� � �� jobs�minute ���� a� V CPU � ������ � ��� V A � �������� � ��� V B � ��������� � �� b� D CPU ����� � �� � �� D A ����� � �� � ���� D B � ������� � ��� c� U k � XD k � X����������� U CPU ��� U B ���� d� U k � XD k � X����������� R � N�X � Z � ����� � � �� seconds ���� xxx The data used here looks like that from problem ����� a� CPU since it has the most demand� b� R min � D � �D � �D � � ��������� � ��� c� X � �� U � � �� ��� � ��� d� D max ��� U k � XD k � X � � job�second e� R � maxfD�ND max � Zg � D max � R�Z N � ���� We need at least a ��� faster CPU� disk A would be just OK� f� D����� D max ��� Z��� � X � minf N ��� � �g� R � maxf���� N � �g ���� a� D � �����D � � ����D � � ��� � disk A b� D � ����� D � �����D � � ��� � disk A c� D � ���D � � ����D � ���� � CPU d� D � ���D � � ����D � �� � disk B �� ���� X � ��� D � � �� D � � �� � ���� � ���� D � � � � ���� � ���� Q i � U i � � � U i � � XD i � � � XD i �� Q � � ��� � �� � � ��� � �� � �� Q � � ��� � ���� � � ����� � ������ Q � � ��� � ���� � � ����� � ����� Q a vg � P i Q i � � � ����� � ����� � ����� R i � S i � ��U i � � S i � ��XD i �� R � � ����� �� ���� � ���� R � � ����� �� ����� � ������� R � � ������ ������� � ������� R a vg � P R i V i � ������� ������� �� � ������� � � ������ seconds� ���� xxx depends on data of ���� which is wrong�� Response Time System Queue Lengths N CPU Disk A Disk B System Throughput CPU Disk A Disk B � ����� ����� ����� ����� ����� ����� ����� ����� � ����� ����� ����� ����� ����� ����� ����� ����� � ����� ����� ����� ����� ����� ����� ����� ����� � ����� ����� ����� ����� ����� ����� ����� ����� � ����� ����� ����� ����� ����� ����� ����� ����� ���� xxx depends on data of ���� which is wrong�� Itera� Response Time System Queue Lengths tion No� CPU Disk A Disk B System Throughput CPU Disk A Disk B � ����� ����� ����� ������ ����� ����� ����� ����� � ����� ����� ����� ������ ����� ������ ����� ����� � ����� ����� ����� ������ ����� ������ ����� ����� � ����� ����� ����� ������ ����� ������ ����� ����� � ����� ����� ����� ������ ����� ������ ����� ����� ���� Each packet is serviced by the � computers� Hence the throughput is when there is one packet is X � � ���S� The packet spents a time of S in each hop so the response time is R � � �S� Similiarily X � � ���S� R � � �S X � � ���S� R� � �S X � � ���S� R � � �S X � � ���S� R � � �S In general R � n � ��S� X � n n���S � n � � ���� If there are h hops in the network� then the each packet has to get serviced by h hops and has to wait a time of nS hops before getting serviced� Hence� �� the response time is R � n � h�S� Arguing similarily the throughput is X � n n�h�S � Power X�R � n n�h� � S � is maximum when n�h� � �� n�h�n � �� n � h ���� xxx depends on data of ���� which is wrong�� The balanced job bounds are N � � ��� � N � ������ ��� N��� ��� N����� � X N� � min �� N � � ��� � N � �� ��� ����� � max � N � �� ��� � N � �� ��� ��� � � � � R N� � ���� N������� N � ����� N � ����� � � Response Time Throughput Lower Upper Lower Upper N BJB MVA BJB BJB MVA BJB � ����� ����� ����� ����� ����� ����� � ����� ����� ����� ����� ����� ����� � ����� ����� ����� ����� ����� ����� � ����� ����� ����� ����� ����� ����� � ����� ����� ����� ����� ����� ����� � ����� ����� ����� ����� ����� ����� � ����� ����� ����� ����� ����� ����� � ����� ����� ����� ����� ����� ����� � ����� ����� ����� ����� ����� ����� �� ����� ����� ����� ����� ����� ����� ���� a� X � N D �� N�� M � � NM D M�N��� � R � Q�X � N�X � D M�N��� M b� Substituting D avg � D max � D�M and Z � � in Equations ����� and ������ we get the same expressions as in Exercise ���� for balanced job bounds� �� Table ����� Computing the Normalizing Constant for Exercise ���� n y CPU � �� y A � � y B � � � � � � � �� �� �� � ��� ��� ��� � ���� ���� ���� ���� D CPU � ����� �� � �� D A � ����� �� � ���� D B � ������ � � ���� For scaling factor choose � ����� � ��� This results in y CPU � ��� y A � �� y B ��� The probability of exactly j jobs at the ith device is P n i � j� � P n i � j�� P n i � j � �� � y j i G N� G N � j�� y i G N � j � ��� P Q CPU � �jN � �� � � ���� ����� ��� ���� � ����� P Q CPU � �jN � �� � �� ���� ���� ��� ��� � ����� P Q CPU � �jN � �� � ��� ���� ��� ��� �� � ����� P Q CPU � �jN � �� � ���� ���� �� ��� �� � ����� xxx the book answer is di�erent� P Q CPU � njN � �� for n � �� �� �� � are ������ ������ ������ and ������ respectively��� The throughputs for N � �� �� � are X �� � G N � �� G N� � ��� �������� � ����� X �� � �� G �� G �� � ��� ������ � ����� X �� � �� G �� G �� � ��� ���� � ����� xxx in book are di�erent� �� ���� xxx data in ���� is wrong�� P Q CPU � njN � �� for n � �� �� �� � are ������ ������ ������ and ������ respectively� �� ���� xxx answer depends on data of Exercise ����� X � ������ ������ and ����� for N � �� �� �� respectively� R � ������ ������ ����� for N � �� �� �� respectively� ���� xxx answer depends on data of Exercise ����� The service rates of the FEC are ������ ������ and ������ respectively� for one through three jobs at the service center�
Compartilhar