Midterm Examination

                               Total 100 points

1. [20 points] MIPS

  (1)There are 3 basic formats in MIPS. Fill in the following blanks.

     (3pts.)

       R-format:

 Opcode　　　Rs　　　　Rt　　　　Rd　　　　Shamt　　　Funct

 ____bits　____bits　____bits　____bits　　____bits　____bits

       I-format:

 Opcode　　　Rs　　　　Rt　　Address/Immediate

 ____bits　____bits　____bits　____bits

       J-format:

 Opcode　　Address

  ____bits　____bits

  (2)Please describe five addressing modes of MIPS and then show one instruction ofeach. (6 pts.)

  (3)The following is a MIPS function. It expects one non-negative integer

     argument and returns one integer result.

     function:

               addi $t0, $0, 1

               addi $t1, $0, 1

     loop:

               blt $a0, 2, exit

               add $t2, $t0, $t1

               add $t0, $t1, $0

               add $t1, $t2, $0

               add $a0, $a0, -1

               j   loop

     exit:

               add $v0, $t1, $0

               jr $ra

     a.    Translate the function intoC. Do not use "goto". (4 pts.)

     b.    What will this functionreturn if it is called with an argument

           ($a0) of 4?

           What foes this function compute?(4 pts.)

  (4)For the pseudoinstruction "ble $t4, $t3, Loop" (branch less thanequal.)

     Please produce a minimal sequence of MIPS instructions (beq, bne or slt)

     to accomplish the same thing. You may need to use $t5 if necessary.

     (3 pts.)

2. [8 points] IEEE754 (in the singleprecision)

  (1)Write the IEEE 754 representation in the single precision for 14/3.

     (4 pts.)

  (2)What decimal number is represented by this word in IEEE 754? (4 pts.)

      11000001111100000000000000000000

3. [14 points] ALU

  (1)We will use the following 1-bit ALU that supports "add","complement

     subtract", "and", "or" and "slt" toconstruct a 16-bit ALU. Overflow

     detection has to be applied too. Describe how to use this 1-bit ALU

     and how to modify MSB and LSB. (8 pts.)

     (圖:1-bit ALU)

  (2)Carry Look Ahead Adder

     The figure shows a 2-level CLA adder. (ALUi is a 4-bit CLA adder.)

     (a) please determine the value of CarryOut15 (C4) of adding a and b:

     a: 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1     

b: 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1

     Please show your answer by determining (pt, gi) and (Pi, Gi) step by

     step. (8 pts.)

4. [28 points] Datapath

  Youare given four sheets of datapath figures of the single-cycle

 implementation. Please highlight the active parts in the datapath for

  (1)"addi $t1, $t2, 2" on Figure 1 (4 pts.)

  (2)"lw $t1, 2($t2)" on Figure 2 (4 pts.)

  (3)"beq $t1, $t2, Loop" on Figure 3 (4 pts.)

  (4)"slt $t1, $t2, $t3" on Figure 4 (4 pts.)

  (發四張 Single-Cycle Datapath 的圖)

5. [8 points] Control

  How will you plan to design the main control of "the single cycle

  implementation" of MIPS? Given the following table of a simplifiedMIPS,

  please show your design.

  Control   Signal name   R-format lw   sw   beq

              Op5              0      1   1    0

              Op4              0      0   0    0

  Inputs     Op3              0      0   1    0

              Op2              0      0   0    1

              Op1              0      1   1    0

              Op0              0      1   1    0

              RegDst           1      0   X    X

              ALUSrc           0      1   1    0

              MemtoReg         0     1    X    X

              RegWrite         1     1    0    0

  Outputs    MemRead          0     1    0    0

              MemWrite         0     0    1    0

              Branch           0      0   0    1

             ALUOp1           1      0   0    0

              ALUOp0           0      0   0    1

6. [12 points] Multiplier/Divisor

  (1) Please describe which multiplier in the following two datapath

      (left vs. right) is better and why. Then use the better multiplier

      to calculate 6x7 (4 bits for each number and 8 bits for the result)

      step by step. (6 pts.)

      (左圖: First Version)  (右圖: Refined Version)

  (2) Please use the Booth algorithm to calculate -5*7. (4 pts.)

  (3) Please show the process of calculating 5(0101)/2(0020) step bystep       with the following restoringdivision. (4 pts.)

      (圖:Datapath of Refined Version of Division)

7. [20 points] Performance:

  (1) Amdahl'Law

  1.  Given a computational task inwhich at most 20% can be parallelized,

      what is the maximal speedup you can obtain according to Amdahl's law?

      (3 pts.)

  2.  Suppose you want to achieve aspeedup of 80 with a multiprocessor that

      has 100 processors. If you have a sequential program, X, what fraction

      of X can still be sequentially executed in order to achieve this goal?

      (3 pts.)

  (2) A processor has a clock rate of 500MHz, and the followingmeasurements

      have been made by using a test program:

      Instruction class      CPI     Frequency

              A                2         35%

              B                3         25%

              C                4         20%

              D                5          5%

              E                6         15%

   1.  What is the MIPS of the processor? (3 pts.)

  2.  What is the CPI of theprocessor? (3 pts.)

  The compiler of the processor is then improved. The instruction

  improvements from this enhanced compiler have been estimated as follows:

  Instruction class     Percentageof instructions executed vs. old compiler

         A                      90%

         B                      80%

         C                      85%

         D                     100%

         E                      80%

  3.  What is the new CPI of theprocessor after the test program

      is processed by the enhanced compiler? (4 pts.)

  4.  How many times faster can beachieved by using the enhanced compiler?

      (4 pts.)

MidtermExamination

Total 100 points

1.    [10 points] MIPS

(1)  Thereare 3 basic formats in MIPS. Fill in the following blanks. (3pts.)
R-format:

I-format:

J-format:

(2)  Forthe pesudoinstruction “ble $t5, $t3, Loop” (branch less than equal.)
Please produce a minimal sequence of MIPS instructions (beq, bne or slt) toaccomplish the same thing. You may need to use $t4 if necessary. (4 pts.)

(3)  Followingthe MIPS procedure calling convention, which of the following should be storedby the caller explicitly before a procedure call so that the callee can usethem as it wishes?(3 pts.)

a.      Savedregisters: $s0-$s7

b.     Temporaryregister: $t0-$t9

c.      Returnaddress: $ra

d.     Returnvalue: $v0-$v1

2.    [12 points] True or False: (Awrong answer costs one more pt. off)

(1)  Thereare more addressing modes in CISC than in RISC

(2)  Vaxis RISC.

(3)  Thegeometric mean in used to calculate the average SPECratio.

(4)  Upto 2³² words are addressable in MIPS.

(5)  Theproblem of MIPS is that it is program dependent and can even be affected by thecompiler.

(6)  Ifwe write a 32-bit (4-byte) data word, 0x12345678, to the address 0x1000 in abig-endian system, it should be
  0x1000      0x0001        0x1002     0x1003

3.    [10 points] IEEE754 (inthe single precision)

(1)  Writethe IEEE 754 representation in the single precision for 13/6. (5 pts.)

(2)  Whatdecimal number is represented by this word in IEEE 754? (5 pts.)
01000001010100000000000000000000

4.    [14 points] ALU

(1)  Pleaseuse the following 1-bit ALU that supports “add”, “complement subtract”, “and”, “or”and “slt” ALU to form a 3-bit ALU. (6 pts.)

(2)  CarryLook Ahead Adder
The right figure shows a 2-level CLA add. (ALU is a 4-bit CLA adder.)

(a)   Pleasedetermine the value of CarryOut15 (C4) of adding a and b:
a: 0101 0110 0011 1111
b: 1111 1101 1110 1011

(b)  Pleaseshow your answer by determining (pi, gi) and (Pi, Gi) step by step. (6pts.)

(3)  CarrySave Adder
In what situation will the carry save adder be used and perform well? (2 pts.)

5.    [16 points] Datapath
You are given four sheets ofdatapath figures of the single-cycle implementation. Please highlight the active partsin the datapath for 123

(1)  “addi$t1, $t2, 5” on Figure 1 (4 pts.)

(2)  “lw$t1, 3($t2)” on Figure 2 (4 pts.)

(3)  “beq$t1, $t2, Loop” on Figure 3 (4 pts.)

(4)  “slt$t1, $t2, $t3” on Figure 4 (4pts.)

6.    [8 points] Control
Howwill you plan to design the main control of “the single cycle” implementation”of MIPS? Given the following table of a simplified MIPS, please show yourdesign.

7.    [15 points] Multiplier/Divisor

(1)  Pleasecalculate 5x7 step by the following multiplier (4 bits for each number and 8bits for the result). Please do not switch multiplicand and multiplier. (5pts.)
 

(2)  Pleaseuse the Booth algorithm to calculate -5x5 (4 bits for each number and 8 bitsfor the result). Please show the steps and follow a similar structure of thefigure above. Again, please do not switch the multiplier and multiplicand. (5pts.)

(3)  Pleaseshow the process of calculating 5(0101)/3(0011) steps by step by using thefollowing restoring division. (5 pts.)

8.    [15 points] Performance:

(1)  Whichchange is more effective on a certain machine: speeding up 10 times thefloating point square root operation only, which takes up 20% of executiontime, or speeding up 2 times all other floating point operations, which take up50% of total execution time? Assume that the cost of accomplishment either changeis the same, and the two changes are mutually exclusive. (5 pts.)

(2)  Assumewe have two computer named “Orange” and “Tomato”. “Orange” computer runs a 1.2GHz clock while “Tomato” computer runs a 1.4 GHz clock. They use the same ISA,which has three classed of instructions, A, B, and C with CPI equal to 1, 2 and3, respectively. Assume computer #1 is designed for (or sold/bundled with) “Orange”computers and compiler#2 is designed for “Tomato” computers. If we use the Cprogramming language to implement a computer program, which is then compiled tomachine instructions by the two compilers. We obtain the following data:

Pleasecalculate (a) MIPS and (b) execution time to determine which machine is faster.(10 pts.)

Computer Organization Midterm Examination  total:100 points

1.     (10%) True or false(一題兩分，答錯扣三分，False要寫理由)

(1) Microprogramming is usually used in the control design of CISC machines.

(2)For a little-endian machine, if we write a 32-bit(4-byte) data word,   0x87655678, to the address 0x1000, the byte at 0x1000 is 01111000.

(3)The stack in MIPS32 grows from lower address to higher address.

(4)In the history of computers' development, the size of memory and number of   registers in a computer grow according to the Moore's law.

(5)In MIPS32, by using J-format, the program can jump to anywhere(any 32-bit   address)in the memory

2.     (12%)MIPS

(1)Please describe five addressing modes of MIPS and then show one   instruction of each(6%)

(2)For the pseudoinstruction "ble $t4, $t3, Loop"(branch less than equal), please use "beq/bne/slt"to accomplish it. Try as few instructions as possible. Please use $t5 if necessary(6%).

3.     (12%)IEEE754 (in the single precision)

(1)Write the IEEE 754 representation in the single precision for 8/3(4%)

(2)What decimal number is represented by this word in IEEE 754?(4%)   11000001010100000000000000000000

(3)What are the largest Denormalized number and the smallest normalized number?(4%)

4.     (28%)Datapath

(1)You are given 4 sheets of datapath figures of single-cycle implementations.   Please highlight the active part in the datapath for

(a)addi $t1, $t2, 2   on figure1

(b)lw $t1,2($t2)      on figure2      老師發四張datapath的圖，描圖

(c)beq $t1, $t2, Loop on figure3      each 4 pts.

(d)slt $t1,$t2,$t3    on figure4

(2)What are the CPI values of a/b/c/d?(4%)

(3)Roughly describe the control design methodology of MainControl and   ALUControl in the datapath figure(8%)

5.     (16%)ALU

(1)We will use the following 1-bit ALU that supports "add","or",and "slt"to   construct a 16-bit ALU that supports these operations.Overflow detection has to be applied too. Describe how to use this 1-bit ALU and how to modify MSB and LSB (8%)
   圖片

(2)Carry look ahead adder. The figure shows a 2-level CLA adder.(ALUi is a 4-bit CLA adder.)
 
   Please determine the value of CarryOut15(C4) of adding a and b:

   a: 0001 1010 0011 0011

   b: 1110 1101 1110 1011
Please show your answer by determining(pi,gi)and(Pi,Gi)step by step(8%)

6.     (12%)Multiplier/Divisor

(1)Please describe which multiplier in the following two datapath(左vs右)is   better and why.Then use the better multiplier to calculate 4x5(4 bits for each number and 8 bits for the result)step by step(6%)
 (就是First multiplication 和refined version那兩個圖拿來比較)

(2)Please show the processor of calculating 5/2 step by step with the following

7.      (10%)Performance

Two different compilers, A and B, are being tested for an 1GHz machine with three different classes of instructions:
(I) branch/Jump

(II) arithmetic and

(III) memory-access instructions

, which require one, two and three cycles per instructions, respectively. Both compilers are used to produce code for a large piece of software. The compiler A's code uses 60 million branch/jump instructions, 20million arithmetic instructions and 0 million memory-access instructions. The compiler B's code uses 100 million branch/jump instructions, 10 million arithmetic instructions and 10 million memory-access instructions.

Which sequence will be faster according to MIPS? Which sequence will be faster according to execution time?(You have to calculate MIPS and execution time.)