Comprehensive Examination Computer Architecture and Operating Systems September 16, 1995

\underline{Note:}

• Start each answer on a fresh sheet of paper. Please keep your answers brief and to the point. Clearly state any assumption that you make.

• You must write your Social Security Number on each answer book. Do not write your name.

1. (10 points) You are considering three choices of memory organizations for a computer system: Direct Mapped, 2-way set associative and 4-way set associative. The following information is given:

Direct Mapped 2-way set associative 4-way set associative
Clock Cycle Time  10ns  10.7ns  10.9ns
miss rate  4.6%  3.8%  3.5%
miss penalty (in cycles)  10  10  10

CPI_{execution} = 1.2 Average memory references per instruction = 1.4 Cache hit time is 1 clock cycle for any cache organization.

(a) Which organization results in the smallest average memory access time? (5 points)

(b) Which organization results in the best CPU performance? (5 points)

2. (10 points) Consider a simple RISC architecture (such as DLX) where only LOAD and STORE instructions access memory. The following pipeline is designed for such a system:

IF Instruction fetch starts
IS Instruction fetch completes
RF Instruction decode and register fetch; branch target computed.

testing of branch condition begins this cycle;

EX Execution - effective address or ALU result available;

testing of branch condition completed.

DF Memory access starts
DS Memory access completes.
WB Write back.

Register writes are done in the first half of a clock cycle and the reads in the second half.

(a) We would like to eliminate data hazards with forwarding. Name which units need to be connected to which other units with forwarding logic and specify which instructions each forwarding logic should keep track of. Do not waste time by giving example assembly language sequences or drawing pipeline flow diagrams. (3 points)

(b) Assume that 20% of the instructions are conditional branches and that 70% of these are taken. For best CPU performance, should we adopt the predict taken strategy or the predict not taken strategy? (4 points)

(c) Assume that the only interrupt that can occur is a data TLB miss and 5% of the instructions cause this interrupt. The interrupt is recognized in the DF stage and takes 10 cycles to service. If the interrupt is precise and the CPI without interrupts is 1.5, what is the CPI with interrupts? (3 points)

3. (10 points) Consider the design of an I/O system with a total storage capacity of 10GB. The average size of each disk access is 4KB. The following information is given on the components available to build the I/O system: \underline{Component} \underline{Cost}

Performance

I/O Bus  $1000 Peak bandwidth = 80 MB/s;

can support 10 disk controllers

Disk controller and String $3000 Peak string bandwidth = 10 MB/s;

1 ms overhead per I/O event due to controller; String can support a maximum of 10 disks

3.5 inch disk  $2000 Capacity = 1 GB; Avg. seek time = 5 ms;

Avg. rotational delay = 8 ms; transfer rate = 2 MB/s

Design the I/O system with maximum possible peak performance. What is the performance to cost ratio (in megabytes per second per $1000) of your design? For convenience, assume that 1 GB = 1000 MB and 1 MB = 1000 KB. (10 points)

4. (5 points) Two monitors are said to be nested if a procedure in one monitor can call a procedure in another monitor and vice versa. Is there a problem if we allow monitors to be nested? If there is a problem, suggest two approaches (other than forbidding the use of nested monitors) to avoid the problem.

5. (5 points) In the ADA programming language, processes are called tasks. Let Task A and Task B be two tasks and let P be a procedure defined in Task A. ADA provides two constructs Accept and Call which behave as follows:

\underline{Task A}  \underline{Task B}
⋮ ⋮
Accept P (…) Call Task A.P (…)
⋮  ⋮

Task A cannot execute the Accept procedure until Task B executes the Call procedure. After executing the Call procedure, Task B must wait until Task A executes the Accept procedure. After that, both the tasks proceed independently. This is called the ADA tasking mechanism. Show how the ADA tasking can be implemented using semaphores.

6. (10 points) Consider a paging system using the working set model. At any time, the system keeps track of a constant number of previous references called the Window. The working set is the set of distinct pages in the window. Define the following:

Δ  = Window size
ω  = The reference string
P (Δ)  = Total number of page faults
W (i, Δ) = Working set size after referencing i^{th} page in ω.
W (Δ) = Average working set size = \frac{1}{|ω|} ∑_{i=1}^{|ω|} W (i, Δ)
F (Δ)  = Average page fault rate = \frac{P (Δ)}{|ω|}

Show that for large ω

(a) 0 ≤ F (Δ) ≤ 1. (2 points)

(b) W (i, Δ) ⊆ W (i, Δ + 1). (2 points)

(c) F (Δ) ≈ W (Δ + 1) − W (Δ). (6 points)

7. (4 points) What factors influence the selection of disk sector size? That is, why are large disk sectors good? Why are they bad? Why are small disk sectors good? Why are they bad?

8. (6 points) A distributed mutual exclusion algorithm is said to obey the No starvation property if any processor that is trying to enter the critical section will eventually succeed. Suppose that we are given an algorithm that will ensure mutual exclusion and no starvation for two processors. We can extend it to n processors as follows: Place the processors at the leaves of a n node complete binary tree called the tournament tree. To enter the critical section, a processor has to move up to the root of the tree. At every node of the tree, the two processor algorithm is used to select from the two processors that may compete to gain access to it. A processor exits the critical section by returning from the root to the leaf corresponding to it. Once a processor gains access to a node, another processor can not gain access to it until the first processor leaves the node. Prove that the n processor distributed mutual exclusion algorithm also obeys no starvation property. Does the no starvation property imply no deadlock? Why?