101年 - 101 國立中山大學_碩士班招生考試_資工系(甲、乙組)：計算機結構#105905

1. You are going to enbance a machine, and there are two possible improvements:
either make multiply instructions run four times faster than before, or make memory access instructions run two times faster than before. You repeatedly run a program that takes 200 seconds to execute. Of this time, 50% is used for multiplication, 20% for memory access instructions, and 30% for other tasks. Determine the speedup for the corresponding cases. Copy Table I to your answer sheet and fill your answers.
Enhancement cases:
C1: Improve only multiplication
C2: Improve only memory access
C3: Improve both multiplication and memory access
Table 1.

2. The dynamic power of a processor is related to the capacitive load (C), operation frequency (F) and voltage (V) with this equation Power=CFV². Suppose we developed a new, simpler processor that has 80% of the capacitive load of the more complex older processor. Further, we can reduce the voltage of the new processor by 20% and let the new processor run at 20% faster frequency. What's the dynamic power of the new processor with respect to the dynamic power of the old processor ?

3. The following C procedure swap is compiled into the corresponding MIPS
assembly code. Assume that the parameters v and k, and variable temp are in registers $a0, sal and $to, respectively. Other registers that can be used are St1 and St2. C procedure:

Please determine proper values for the operands (OPA, OPB, OPC, OPD). Copy the
following table (Table 3) to your answer sheet and fill in the operand values.

4. Figure 4.1 is a basic multiplication hardware and Figure 4.2 is an improved
version of the basic one.
Figure 4.1: Basic multiplication hardware
Figure 4.2: Improved multiplication hardware

The following statements are possible observations for the improvement:
S1: The multiplicand register, ALU, Multiplier register and the Product register are all 32 bits wide；
S2: The Product register always shifts right two bits in each iteration；
S3: The original Multiplier register disappears and is now placed in the right half of the Product register initially；
S4: The left side of the Product register is initially set to zero.
S5: The Multiplicand register is initially set to zero.
Please copy the following table (Table 4) to your answer sheet and determine if these statements are true or false.

5.The following figure is a simple implementation of a MIPS subset (R-type, 1w, sw, beg). Copy Table 5 to your answer sheet and fill in the corresponding control signal values (0, 1 or X) for instructions 1w (load word) and beg (branch on equal).

6. There are three small caches, each consisting of four one-word blocks. The first cache is direct mapped, the second cache is two-way set associative, and the third cache is fully associative. Find the numbers of misses for each organization given the following sequence of block addresses: 8. 0. 8. 6, 0. Copy Table 6 to your answer sheet and fill in the answers. Assume that the least recently used replacement policy is used for the fully associative cache and the set-associative cache.

7. Suppose we want to sum 100,000 numbers on a single-bus multiprocessor
computer. Let's assume we have 10 processors. The first step would be to split the set of
numbers into subsets of the same size. All processors start the program by running the
following loop that sums their subset of numbers, where Pn is its processor index (0~9):
sum/Pn] = 0；
for (I = 10000 * Pn；I ＜10000*(Pn+1)；I=I+1)
      sum(Pn] = sum[Pn] + Al]； / sum the assigned areas
The next step is to add these many partial sums, so we divide to conquer. Half of
processors add pairs of partial sums, then a quarter add pairs of the new partial sums,
and so on until we have the single, final sum. We want each processor to have its own
version of loop counter variable I, so we must indicate that it is a "private" variable.
In this problem, the two processors must synchronize before the "consumer" processor
tries to read the result from the memory location written by the "producer" processor,
otherwise, the consumer may read the old value of the data. Here is the code (halfis also
a private variable):

Question: according to the algorithm, find out what operations are executed by the
designated processor during the designated repeat-loop iteration. (Ex: NOP or sum[0] =
sum[0] + sum [4]). Copy Table 7 to your answer sheet and fill in the answers.

8.1 Derive the Boolean equation for the carry-out bit C₂ using only (where i=0,1) and C₀.

8.2 In a carry-lookahead adder, there are two additional signals defined, , (generate), (propagate). Derive the Boolean equation for the carry-out bit Co using only G, Pi(where i=0, 1) and C₀.