cs345 Exam 1 Solutions

Part 1

a1) Grace Hopper was a US Naval officer (rear admiral) who was famous for finding the first bug (a moth) and for creating COBOL.

a2) Charles Babbage invented the Analytical and Difference Engines.  He is famous for being the "father of modern computing".

b3) The theoretical best run time is 350s (total time) - 250s (parallelizable time) = 100s

b4) The maximum speedup is 3.5 = 350s (sequential time) /100s (parallelizable time).

b5) The performance on one processor is 1/350s and the performance using an infinite number of processors is 1/100s

b6) The cycle time of a 2GHz processor is 1/2*10^9 s/cycle = 0.5 ns

b7) There are 2 billion cycles per second on a 2 GHz processor since GHz means billions of cycles per second.

b8) 10 instructions * 4 cycles/instruction / 2*10^9 cycles/second = 20 * 10 ^ -9 s = 20ns

c9) add $t4, $t1, $t2
    sle $t4, $t3, $t4 

c10) and $t4, $t1, $t2
     and $t4, $t3, $t4

c11) add $t4, $t1, $t2
     mul $t4, $t4, $t3
     sub $t3, $t4, $t1

c12) lw $t4, 16($s0)
     lw $t5, 32($s0)
     add $t6, $t4, $t5
     sw $t6, 0($s0)

d13) 9EA2

d14) 123 % 2 --> 1
     61 % 2 --> 1
     30 % 2 --> 0
     15 % 2 --> 1
     7 % 2 --> 1
     3 % 2 --> 1
     1

     1111011

d15) 111001 is 1 + 8 + 16 + 32 = 57


Part 2

1. The five basic parts of a computer are as follows:
    CPU - Central Processing Unit the brain of the computer that contains the logic to complete
    mathematical, logical, control, and branching operations.

    Main memory (RAM) - this is where data and programs are temporarily stored as a program is
    executing

    I/O - input and output devices that allow for a user to provide information to the computer and 
    receive responses from the computer.  This includes keyboards, mice, monitors, printers, etc.

    Secondary storage - this is permanent storage for data and programs such as a hard disk.

    Bus or interconnect - this is the communication layer or data path between each of the devices

2. .data
prompt: .asciiz "Enter the length and width: "

.text  #compute the area of a rectangle
main:

li $v0, 4  #print the prompt
la $a0, prompt
syscall

li $v0, 5  #get the length
syscall

move $t1, $v0

li $v0, 5  #get the width
syscall

move $t2, $v0

mul $t3, $t1, $t2  #a = l*w

move $a0, $t3  #print the result
li $v0, 1
syscall

3. .data
promptOption: .asciiz "Enter 1 for circle or 2 for rectangle: "
promptCir: .asciiz "Enter the length and width: "
promptRect: .asciiz "Enter the radius: "
invalid: .asciiz "Invalid input\n"

.text  #compute the area of a rectangle
main:

la $a0, promptOption #prompt user to enter an option
li $v0, 4
syscall

li $v0, 5 #get the option
syscall
move $t4, $v0 #store the option

beq $t4, 1, circle
beq $t4, 2, rect
beq $zero, $zero, elseif

circle:
#read the radius of the circle
#compute circle area here

beq $zero, $zero, endif

rect:
#read the length and width
#compute the rectangle area

beq $zero, $zero, endif

elseif:

la $a0, invalid  #print an invalid message
li $v0, 4
syscall

endif:

4. 0.5 add * 3 cycles/add + 0.25 mult * 4 cycles/mult + 0.25 move * 2 cycles/move = 1.5 + 1 + 0.5
    = 3 cycles/instruction

    3 * 10^9 cycles/s / 3 cycles/instruction = 10^9 instr/s avg

    10s * 10^9 instr/s = 10^10 instructions total

5. .double should be replaced with .asciiz because we are working with a string
    t1 should be replaced with $t1 in the instruction li t1, 0.  Registers must start with a dollar sign.
    subi should be replaced with addi.  We need to increment $t0 to pass through the array.
    beq should be replaced with bne.  We want the loop to continue as long as $t1 < $t2.
    sys should be replaced with syscall.  sys is not a keyword.

6. addi $s3, $t5, 73
001000 01101 10011 0000 0000 0100 1001
opcode rs    rt    immediate

0010 0001 1011 0011 0000 0000 0100 1001
0x21b30049

div $s7, $t0, $t3
000000 01000 01011 10111 00000 011010
opcode rs    rt    rd    shamt funct

0000 0001 0000 1011 1011 1000 0010 1010
0x010bb82a

7. Analytical benchmarking refers to true benchmarking of a system.  This includes true mathematical models of performance criteria for a processor.  For most modern processors, analytical data is too complicated to calculate, so empirical benchmarks are used.  Empirical benchmarks involve using simulations or real programs to calculate performance or runtime data on a processor.  Simulations may include programs that test specific instructions such as floating point operations or integer operations to get instruction ratings such as FLOPS (floating point operations per second) or MIPS (millions of instructions per second).  Such simulations don't always provide a true estimate of performance because operation counts may vary across different architectures.  Experimental benchmarks that use real or production quality programs to test run times often provide better comparison measures across different architectures.