Buscar

Solucionário The Art of Computer Systems Performance Analysis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 3, do total de 67 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 6, do total de 67 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes
Você viu 9, do total de 67 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

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�

Outros materiais