Exercise 4.1

Exercise 4.1

Different instructions utilize different hardware blocks in the basic single-cycle implementation. The next three problems in this exercise refer to the following instruction:

Instruction Interpretation

a. AND Rd,Rs,Rt	Reg[Rd] = Reg[Rs] AND Reg[Rt]
b. SW Rt,Offs(Rs)	Mem[Reg[Rs] + Offs] = Reg[Rt]

Figure 4.2

Taken from: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-823-computer-system-architecture-fall-2005/lecture-notes/l05_singlecycle.pdf

ExtSel is extend sign, which is not represented in our figure.

BSrc is the southern mux in the figure and is used to determine if an immediate operand or a register is passed to the ALU.

OpSel is ALU command

WBSel is middle mux, selecting whether the ALU output or a memory output is used as data.

4.1.1 What are the values of control signals generated by the control in Figure 4.2 for this instruction?

For these answers, i will be referencing the Control table above provided by MIT Open Courseware.

a) AND is an ALU Operation, so:

BSrc will look to register

OpSel will tell ALU to AND

MemW is false, we do not touch memory

RegW is true, we are writing back to register Rd

WBSrc is will set to use output from ALU as data

RegDst is Rd

PCSrc is PC + 4 since no jumps occur

b) SW is directly represented in our chart

BSrc will look to immediate operand Offs

OpSel will tell ALU to ADD the Offset to the Rs register

MemW is true, we are writing a register to memory

RegW is false, we are not writing back to a register

WBSrc is ignored

RegDst is ignored

PCSrc is PC + 4 since no jumps occur

4.1.2 Which  resources  (blocks)  perform  a  useful  function  for  this instruction?

a) pc, instruct mem, alu, mux, registers

    We are not using memory or jumping

b) pc, instruct mem, alu, mux, mem, reg

4.1.3 Which resources (blocks) produce outputs, but their outputs are not used for this instruction? Which resources produce no outputs for this instruction?

a) branch, data memory

b) branch

Different execution units and blocks of digital logic have different latencies (time needed to do their work). In Figure 4.2 there are seven kinds of major blocks. Latencies of blocks along the critical (longest-latency) path for an instruction determine the minimum latency of that instruction. For the remaining three problems in this exercise, assume the following resource latencies:

Since no mention is made as to analog or digital mux, I am assuming digital and that 20ps will always be spent.

I-Mem	Add	Mux	ALU	Regs	D-Mem	Control
a. 200ps	70ps	20ps	90ps	90ps	250ps	40ps
b. 750ps	200ps	50ps	250ps	300ps	500ps	300ps

4.1.4 What is the critical path for an MIPS AND instruction?

Figure above outlines latencies, and calculates Critical path to ALU completion.

The PC +4 and Control have lower latencies than other parts functioning in parallel. Control is slower the the registers, and data mem is not used.

a)instruction mem, reg, mux, alu, mux

400 + 20(writeback to reg mux) = 420ps

b) 1350+20=1370ps

4.1.5 What is the critical path for an MIPS load (LD) instruction?

Load will read from mem and write to register so we must use data memory and the mux to register data.

a)400+250+20 = 670ps

b)1350+500+50 = 1900ps

4.1.6 What is the critical path for an MIPS BEQ instruction?

beq will go up to the branch, and mux the new address from the ALU output to be the new Program Counter.

a)400+20 = 420ps

b)1350+50 = 1400ps

This Exercise focus’ on Critical Paths of Operations and the resources they use.

As such, we cover 4 distinct Control variations as described in the MIT Open Courseware Figures: ALU, SW, LW, BEQ.

To show all these in execution, I am running a simulation in ProcSim: http://jamesgart.com/procsim/

The resource configuration is slightly different from the one in the figure used above, however the operations performed are identical.

The Assembly I am executing is in the lower right of the images and the current register values is in the middle right.

Exercise 3.15

a. 1/3

b. 1/10

3.15.1 Write down the bit pattern in the mantissa assuming a

floating point format that uses binary numbers in the mantissa (essentially what

you have been doing in this chapter). Assume there are 24 bits, and you do not need

to normalize. Is this representation exact?

a) ⅓ can’t be represented since it repeats 3333 infinitely, and we are in base 2 therefore we must round up a little

010101010101010101010110

b) 1/10 also can’t be represented in base 2 and must be approximated.

000110011001100110011001

Work on Spreadsheet.

https://docs.google.com/spreadsheet/ccc?key=0Anpg-UsmVkpFdFY2cm1OeVRZZUQtS0g1Nk1kNjltUGc&usp=sharing

3.15.2 Write down the bit pattern in the mantissa assuming a

floating point format that uses Binary Coded Decimal (base 10) numbers in the

mantissa instead of base 2. Assume there are 24 bits, and you do not need to nor-

maize. Is this representation exact?

a)This also can’t be represented exactly

0011 = 3

.3      3       3      3     3      3

001100110011001100110011

b)This is our first number that CAN be represented exactly.

1/10 = .1

0001 = 1

.1     0       0      0      0       0

000100000000000000000000

3.15.3 Write down the bit pattern assuming that we are using

base 15 numbers in the mantissa instead of base 2. (Base 16 numbers use the sym-

bos 0–9 and A–F. Base 15 numbers would use 0–9 and A–E.) Assume there are 24

bits, and you do not need to normalize. Is this representation exact?

a)The first case in which ⅓ can in fact be represented exactly.

1/3 = 5/15

5 = 0101

5     0     0     0     0     0

010100000000000000000000

b)Can’t Be Represented Exactly

(1/10) = (x/15)

x = 1.5

Round(1.5) = 2

2 = 0010

0010 0010 0010 0010 0010 0010

3.15.4 Write down the bit pattern assuming that we are using

base 30 numbers in the mantissa instead of base 2. (Base 16 numbers use the sym-

bos 0–9 and A–F. Base 30 numbers would use 0–9 and A–T.) Assume there are 20

bits, and you do not need to normalize. Is this representation exact? Do you see any

advantage to using this approach?

a)⅓ = 10/30

10 = 01010

01010 00000 00000 00000

b) 1/10 = 3/30

3 = 00011

00011 00000 00000 00000

Using a larger base allows a greater flexibility when non normalized at the cost of precision.  Base 30 as represented above has 4 decimal digits, as opposed to base 10 above, which has 6.

http://en.wikipedia.org/wiki/Floating_point

This is mentioned here in a comparison with storing the value of the speed of light.  “floating-point numbers cannot represent point coordinates with atomic accuracy at galactic distances, only close to the origin” the smaller the number, the greater the precision we need.  The larger the number, the greater a exponent value we need.

I also created a Mips program to do parts of these calculations.

.data Ask_base: .asciiz "\Please Enter a Base\n" Ask_top: .asciiz "\Please Fraction Top\n" Ask_bottem: .asciiz "\Please Fraction Bottem\n" sig:  .asciiz "\Significand\n" space:  .asciiz "\n" not_possible: .asciiz "\This Fraction Cannot be accurately represented\n" .text main: la $a0, Ask_base li $v0, 4 syscall #print Ask_base li $v0, 5 syscall move $t0, $v0 #t0 is our base la $a0, Ask_top li $v0, 4 syscall #print Ask_top li $v0, 5 syscall move $t1, $v0 #t1 is top of fraction la $a0, Ask_bottem li $v0, 4 syscall #print Ask_bottem li $v0, 5 syscall move $t2, $v0 #t1 is bottem of fraction #goal is to test first if its possible to represent #if something can't be represented, it requires a fair amount of estimation #this is outside the scope of this program mulu $s0, $t0, $t1 divu $s0, $t2 mfhi $s1 mflo $s2 beqz $s1, calc  #if there is a remainer, we print and exit, else we continue la $a0, not_possible li $v0, 4 syscall #print not_possible j done calc: #not that there is much calc la $a0, sig li $v0, 4 syscall #significand li $v0, 1 #print_int move $a0, $s2 syscall la $a0, space li $v0, 4 syscall #print space #************** Convert to Bit notation  *************************# move $t2, $s0      # Move to temp        li $s1, 24         # Set up a loop counter - assuming 24 bit Loop:        ror $t2, $t2, 1    # Roll the bits left by one bit - wraps highest bit to lowest bit (where we need it!)        and $t0, $t2, 1    # Mask off lowest bit        add $t0, $t0, 48   # Combine it with ASCII code for '0', becomes 0 or 1               move $a0, $t0      # Output the ASCII character        li $v0, 11        syscall               subi $s1, $s1, 1   # Decrement loop counter        bne $s1, $zero, Loop  # Keep looping if loop counter is not zero #I started to do this but I stopped here, it doesn't take into account the appropriate bit size. and the calculations themselves are slightly off #example, a base 16 needs 4 bits, int 5 isn’t 1110 in binary #I kept this in here as reference to the attempt done: #example #input base 15 #input top 1 #input bottem 3 ##output## #Significand #5 #111000000000000000000000

https://drive.google.com/file/d/0B3pg-UsmVkpFVEZCb05PRlBib1U/edit?usp=sharing

Exercise 3.2

Exercise 3.2

Hexadecimal (base 16) is also a commonly used numbering system for representing values in computers. In fact, it has become much more popular than octal. The following table shows pairs of hexadecimal numbers.

	A	B
a	1446	672F
b	2460	4935

Binary Conversion

	A	B
a	0001 0100 0100 0110	0110 0111 0010 1111
b	0010 0100 0110 0000	0100 1001 0011 0101

3.2.1 What is the sum of A and B if they represent unsigned 16-bit hexadecimal numbers? The result should be written in hexadecimal. Show your work.

a)

1446 +

672F

7B75

0001 0100 0100 0110 +

0110 0111 0010 1111

0111 1011 0111 0101

b)

2460 +

4935

6D95

0010 0100 0110 0000 +

0100 1001 0011 0101

0110 1101 1001 0101

3.2.2 What is the sum of A and B if they represent signed 16-bit hexadecimal numbers stored in sign-magnitude format? The result should be written in hexadecimal. Show your work.

In sign magnitude format, the most significant bit is a sign bit.  In order to have a sign bit set in hex, the leading ‘character’ must be 8-F.  In none of the given numbers, or answers, is this the case.  The binary math also supports this. This makes the answers to this problem, the exact same as the one above.

3.2.3 Convert A into a decimal number, assuming it is unsigned. Repeat assuming it stored in sign-magnitude format. Show your work.

See spreadsheet.  As with exercise 3.1, I have made a sheet with weights and sums to represent the long hand math to calculate decimal from binary.

https://docs.google.com/spreadsheet/ccc?key=0Anpg-UsmVkpFdFczMDZYUnNmZWp1ZDhBbVNmdmUwenc&usp=sharing

a. 5190

b. 9312

	A	B
a	C352	36AE
b	5ED4	07A4

Bit Conversion

	A	B
a	1100 0011 0101 0010	0011 0110 1010 1110
b	0101 1110 1101 0100	0000 0111 1010 0100

3.2.4 What is A – B if they represent unsigned 16-bit hexadecimal numbers? The result should be written in hexadecimal.

a.

C352 -

36AE

8CA4

1100 0011 0101 0010 -

0011 0110 1010 1110

1000 1100 1010 0100

   8       C      A      4

b.

5ED4 -

07A4

5730

0101 1110 1101 0100 -

0000 0111 1010 0100

0101 0111 0011 0000

  5       7       3       0

3.2.5 What is A – B if they represent signed 16-bit hexadecimal  numbers stored in sign-magnitude format? The result should be written in hexadecimal.

a.

C352 = 1100 0011 0101 0010

The sign bit is set, so this is a negative number

-A-B = -(A+B)

0100 0011 0101 0010 = 4352

4352 +

36AE

7A00

0100 0011 0101 0010 +

0011 0110 1010 1110

0111 1010 0000 0000

   7      A       0       0

Now we add the sign bit back in

1111 1010 0000 0000

  F       A       0       0

b.

0101 1110 1101 0100 - 0000 0111 1010 0100

neither one have a sign bit set, so the math is same as unsigned math above.

3.2.6 Convert A into a binary number. What makes base 16 (hexadecimal) an attractive numbering system for representing values in computers?

I have been working with binary as i went as an additional proof to the math.

http://en.wikipedia.org/wiki/Hexadecimal

Hex is a very useful numerical system.  It is the primary representation of memory addresses in computers as modern computers operate at a base of 16, my computer, for example, is 64 bit, so 16*4.  This makes representation accurate and easy.  In addition it allows large numbers to be displayed in less digits, for example, Hex Dword(32 bits) is written as FFFFFFFF, just 8 digits, but in decimal is represented as 4294967295, 10 digits.

The largest downside of this representation comes with its verbal representation.  The symbols for decimal 10-15 (A-F) can easily be misinterpreted.  For example, 40 and 4D, have very similar pronunciations.