Problem: http://www.cs.utexas.edu/~hds/cs352/assignments/nov12/nov12.pdf
Solution: http://docs.google.com/Doc?id=dgt9wvxh_84fzwg52

1. Textbook: 8.18

Max sustainable simultaneous disk transfers
= Max sustainable bandwidth / Disk Transfer Rate
= Max sustainable bandwidth / 50 MB per sec (from page 570)

Now we need to calculate max sustainable bandwidth.

For 4 words:

We calculate the bus bandwidth for 4 words.
Bandwidth
= Size of 4 words / Time to transfer 4 words
= 4 * 32 / Time to Transfer 4 words

Time to transfer 4 words
= actual transfer time + memory access time
= (Total cycles required to transfer 4 words / clock speed) + memory access time.

Memory access time = 200ns (characteristic 4)

Total cycles = 2 (characteristic 2: 1 per 64 bit data transfer) + 1 (characteristic 2: to send address) + 2 (characteristic 3: between each bus operation) = 5

Therefore,
Time to transfer 4 words
= 5 cycles / 200MHz + 200 ns = 225 ns.

Bandwidth
= Size of 4 words / Time to transfer 4 words
= 4 * 32 / Time to Transfer 4 words
= 4 * 32 bits / 225 ns
= 4 * 4000 / 225 MB per sec
= 71.11 MB per sec

Similarly,
For 16 words:

We calculate the bus bandwidth for 16 words.

Bandwidth
= Size of 16 words / Time to transfer 16 words
= 16 * 32 / Time to Transfer 16 words

Time to transfer 16 words
= Total cycles required to transfer 16 words / clock speed + memory access time.

Memory access time = 200ns + 20 * 3 = 260 ns(characteristic 4: 3 additional set of four words)

Total cycles = 8 (characteristic 2: 1 per 64 bit data transfer) + 1 (characteristic 2: to send address) + 2 (characteristic 3: between each bus operation) = 11
Therefore,
Time to transfer 16 words
= 11 cycles / 200MHz + 200 ns = 315 ns.

Bandwidth
= Size of 16 words / Time to transfer 16 words
= 16 * 32 / Time to Transfer 16 words
= 16 * 32 bits / 315 ns
= 16 * 4000 / 315 MB per sec
= 203.1746 MB/sec

For 4-word block transfers, the bus bandwidth is 71.11 MB/sec. For 16-
word block transfers, the bus bandwidth was 203.175 MB/sec. The disk drive has a
transfer rate of 50 MB/sec. Thus for 4-word blocks we could sustain 71/50 = 1
simultaneous disk transfers, and for 16-word blocks we could sustain 203/50 = 4
simultaneous disk transfers. The number of simultaneous disk transfers is inherently
an integer and we want the sustainable value. Thus, we take the floor of the
quotient of bus bandwidth divided by disk transfer rate.

2. Textbook: 8.43
Redo the example on page 601, but instead assume that the reads are 8KB
reads. You can assume that the reads are always
to an idle disk, if one is available.

(We need to do exactly as per the text, just instead of 64KB reads we have 8KB reads)

Maximum I/O rate of CPU
= Instructions per sec / Instructions per I/O
= 3*10^9 / (200,000 + 100,000)
= 10,000 I/O per sec

Each I/O transfers 8KB, so

Maximum I/O rate of bus
= Bus Bandwidth / Bytes per I/O
= 1000*10^6 / 8,000
= 125,000 I/Os per sec

The CPU is the bottleneck and therefore, the maximum sustainable I/O rate is 10,000 I/Os per sec

Now, we need to calculate the maximum number of disks possible while within the maximum sustainable I/O rate bound
Max disks
<= Max sustainable I/O rate / I/O rate of disk
= Max sustainable I/O rate * Time per I/O at disk

Time per I/O at disk
= (Seek + rotational) + Transfer
= (6 ms) + 8 KB / 75 MB per sec
= 6.1066 ms

Therefore,
Max disks
<= Max sustainable I/O rate * Time per I/O at disk
= 10,000 I/Os per sec * 6.1066 ms
= 61.066

Max disks = 61

To compute the number of SCSI buses, we need to check the average transfer rate per disk to see if we can saturate the bus, which is given by

Transfer rate
= Transfer Size / Transfer Time
= 8 KB / 6.1066 ms
= 1.31 MB/sec

The SCSI Controller has max sustainable rate of 320 MB/sec and therefore can very easily handle 7 disks each of transfer rate 1.31 MB/sec.

Therefore,

Number of SCSI Controllers required
>= Number of disks required / number of disks per controller
= 61 / 7
= 8.714


Number of SCSI Controllers required = 9


3.

a. Maximum operations per second that the disk can sustain
= 1/average delay
= 1/ ( 0.0075 sec per operation)
= 133.33 operation per sec

b. Number of disk units required
>= arrival rate of operations / maximum operations per second
= 3 * 550 operations per sec / 133.33
= 12.375

Therefore, 13 units will be required

c. With a cache of hit rate 40% the number of disk units required
= Number of disk units required for misses which are 60% of total accesses
>= miss_rate * Number of disk units required without cache
= 0.6 * Number of disk units required without cache
= 0.6 * 12.375
= 7.425

Therefore, 8 units will be required

d. We have,
Number of disk units required with cache >= miss_rate * (Number of disk units required without cache)
=> 3 >= miss_rate * (Number of disk units required without cache)
=> 3 >= (1-hit_rate) * (Answer of 3.b)
=> hit_rate >= (1- (3/12.375))
= 0.75757

Therefore, required hit rate is 76%

Assignment#2
Problems:
http://www.cs.utexas.edu/users/hds/cs352/assignments/sep10/asg2.pdf
Solution:
http://docs.google.com/Doc?id=dgt9wvxh_50n26sb8

1)
a. slt $t0, $t1, $t2

slt $8, $9, $10
0, 9, 10, 8, 0, 0x2a
000000 01001 01010 01000 00000 101010
0000 0001 0010 1010 0100 0000 0010 1010

0x012a402a <--------------------------

b. bne $t0, $zero, 0x0010

bne $8, $0, 0x0010

5, 8, 0, 0x0004 divide const address by 4 (right shift 2)
000101 01000 00000 0000 0000 0000 0100
0001 0101 0000 0000 0000 0000 0000 0100
0x15000004 <--------------------------

c. li $t5, 32
orni $13, $zero,, 0x0020
001101 00000 01101 0000 0000 0010 0000
0011 0100 0000 1101 0000 0000 0010 0000
0x340d0020 <--------------------------

d. j 0x0020000
2, 0x0020000 or if divide const by 4 we get
2, 0x0008000
000010 00 0000 0000 01000 0000 0000 0000
0x08008000 <---------------

e. add $v0, $s0, $t0

add $2, $16, $8
000000 10000 01000 00010 00000 100000
0000 0010 0000 1000 0001 0000 0010 0000
0x02081020 <-----------------------


2)
a) 0x8fa40000
1000 1111 1010 0100 0000 0000 0000 0000
100011 11101 00100 (0000)hex
(23)hex (29)dec (4)dec (0000)hex
lw $a0, 0($sp)

b) 0x23bdfff8

addi $sp, $sp, -8


c) 0xafa40000

sw $a0, 0($sp)

d) 0x28880001

slti $t0, $a0, 1

e) 0x11000004
beq $t0, $zero, 4


4)
a. Define pseudo-op - A directive to the assembler to generate the instructions required to achieve the specified operation. These instructions are accepted by the MIPS assembler, however they are not real instructions within the MIPS instruction set. Instead, the assembler translates them into sequences of real instructions.

b. i. la $t0, xx assume address(xx) = 0x81234567
lui $t0, 0x8123
ori $t0, $t0, 0x4567

ii. li $t0, 5

ori $t0, $zero, 5

iii. bgt $t0, $t1, L1 this is the same as blt $t1, $t0, L1

slt $at, $t1, $t0
bne $at, $zero, L1

iv. ble $t0, $t2, L2

if we had bge $s1, $s2, L5 we would write
slt $at, $s1, $s2
beq $at, $zero, L5 # branch if not less than

so, ble $t0, $t2, L2 is the same as bge $t2, $t0, L5 and this is
slt $at, $t2, $t0
beq $at, $zero, L5

v beqz $t0, L3
beq $t0, $zero, L3

Assignment#1
http://www.cs.utexas.edu/users/hds/cs352/assignments/sep05/asg1.pdf
Fall 2007 Schwetman
CS352 – Assignment #1
Sept. 5, 2007
Weight: 25 points
Due date: Monday, Sept. 10, 2007 (beginning of class)
1. Write a C program that accomplishes the following:
· Fills every element of an array of dimension N = 200,000 with random numbers
from the uniform01 probability distribution (see below), and then
· Processes the array, to compute the average, variance, minimum and maximum
of the values in the array. Print out the results “so far” after 50,000 values, after
100,000 values, after 150,000 values and after 200,000 values.
Statistics
Let n = the number of samples
Let sum = the sum of the value of the samples
Let sumsq = the sum of the squares of the values of the samples
Then average of the sample values = sum/n
The variance of the sample values = (sumsq – n*avg*avg)/(n – 1)
Uniform01()
The C function random() returns int values which are randomly (and uniformly)
distributed over the interval (0.0, 2147483648.0). If each of these values is
divided by the maximum possible value (2147483648.0), then these new values
appear to be from the uniform01 probability distribution. So, you need to write a
function named uniform01() which uses the random() function to generate the
sequence of required values.
Turn in a listing of the C program and a copy of the output

2. Give a sequence of MIPS assembly language instructions that produces the same
results as the following sequence of C statements:
i = 0;
sum = 0;
while(i < 10) {
sum = sum + x[i];
i = i + 1;
}
Assume that the address of i is in $s1, the address of sum is in $s2 and the address
of x (really x[0]) is in $s3.

3. Give a sequence of C statements that produces the same results as the following
sequence of MIPS assemble language statements (assume $s1 = address of i, $s2 =
address of j, and $s3 = address of x[0])
lw $t0, 0($s1)
lw $t1, 0($s2)
slt $t3, $t0, $t1
beq $t3, $zero, exit
sll $t3, $t0, 2
add $t4, $t3, $s3
sw $zero, 0($t4)
exit:
Fall 2007 Schwetman


1.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

double uniform01()
{
return (double)random()/RAND_MAX;
}
void run()
{
//seed the random() function with current time
srand(time(NULL));
//array of dimemsion 200000
double n[200000];
//total sum of random number
double sum = 0.0;
//sum of squares of numbers
double sumsq=0.0;
int i;
double min=1.0, max=0.0, avg;

//Fill in the arrray
for(i = 0; i < 200000; i++)
{
//uniform01 probability distribution
//random number generated from random() divided by 2147483648

n[i] = uniform01();

//adds each uniform01 to get total sum
sum += n[i];
sumsq+=n[i]*n[i];
if(n[i]<min)
{
min = n[i];
}
if(n[i]>max)
{
max = n[i];
}
//generate the result "so far"
if ((i+1) % 50000 == 0)
{
//Current Count
printf("So far at: %d n" , i+1);
//Min
printf("Min: %f n",min);
//Max
printf("Max: %f n",max);
//average of the sample
avg = sum/ (i+1);
printf("Average: %f n", avg);
//variance
printf("Variance: %f n", (sumsq - (i+1)*avg*avg)/i);
//Sum
printf("Sum: %f n",sum);
//Sumsq
printf("Sumsq: %f n",sumsq);

printf("n");
}
}

}
int main()
{
run();
return 0;
}

So far at: 50000
Min: 0.000021
Max: 0.999986
Average: 0.499254
Variance: 0.083463
Sum: 24962.697366
Sumsq: 16635.783491

So far at: 100000
Min: 0.000009
Max: 0.999986
Average: 0.500316
Variance: 0.083336
Sum: 50031.608752
Sumsq: 33365.092141

So far at: 150000
Min: 0.000001
Max: 0.999998
Average: 0.499792
Variance: 0.083408
Sum: 74968.810490
Sumsq: 49979.966471

So far at: 200000
Min: 0.000001
Max: 0.999998
Average: 0.499853
Variance: 0.083273
Sum: 99970.691038
Sumsq: 66625.112423




2.
Give a sequence of MIPS assembly language instructions that produces the
same results as the following sequence of C statements:

i = 0;

sum = 0;

while(i < 10) {

sum = sum + x[i];

i = i + 1;

}

Assume that the address of i is in $s1, the address of sum is in $s2 and
the address of x (really x[0]) is in $s3.


li $t1, 0 # use $t1 as i
li $t2, 0 # use $t2 as sum
li $s4, 10
loop:
slt $t0, $t1, $s4
beq $t0, $zero, done # if(i >= 10) goto done
sll $t3, $t1, 2 # 4*i
add $t4, $s3, $t3 # $t4 = addr(x[i])
lw $t5, 09$t4) #t5 = x[i]
add $t2, $t2, $t5 # sum = sum + x[i]
addi $t1, $t1, 1 # i = i + 1
b loop
done:
sw $t1, 0($s1) # store i
sw $t2, 0($s2) # store sum


3. if(i<j)x[i]=0;

Assume $s1 = address of i, $s2 = address of j, and $s3 = address of x[0]

lw $t0, 0($s1) # $t0 = i
lw $t1, 0($s2) # $t1 = j
slt $t3, $t0, $t1 # $t3 = i< j ? 1:0
beq $t3, $zero, exit # $t3 == 0 -> exit
sll $t3, $t0, 2 # else $t3 = $t0 * 4
add $t4, $t3, $s3 # $t4 = $t3 + &x[0] = i*4 + &x[0] = &x[i]
sw $zero, 0($t4) # save $t4 = $zero, i.e. x[i] = 0
exit: