115 年 國立中正大學資訊工程學系碩士班《計算機系統》

Process the following 10 memory accesses in order, where each access is either a read (R) or write (W) to the given byte address:

(1) R $0x12345678$
(2) R $0x1234567C$
(3) W $0x12345670$
(4) R $0x12346678$
(5) R $0x12347678$
(6) W $0x12348678$
(7) R $0x12345674$
(8) R $0x12349678$
(9) R $0x1234667C$
(10) W $0x1234867C$

For each cache organization (direct-mapped, 4-way set-associative, and fully-associative), determine whether each of the 10 accesses is a cache hit or cache miss, and report the total number of hits and misses for that organization.

In Problem 1, if the main memory size is increased significantly (e.g., from $4\ \mathrm{GB}$ to $16\ \mathrm{GB}$), is it mandatory to increase the total cache size (currently $4\ \mathrm{KB}$) for the system to function correctly?

(A) Increase
(B) Decrease
(C) No Change Required

Our favorite program runs on Computer A in 10 seconds. Computer A uses a 5-stage pipeline, has an average CPI of $1.0$, and operates at a clock rate of $2\ \mathrm{GHz}$. A computer designer is considering a new machine, Computer B, with the goal of reducing the execution time of this program to 6 seconds.

Computer B uses a deeper 10-stage pipeline. The increased pipeline depth allows for a higher clock rate; however, it also introduces additional pipeline overhead, such as larger branch misprediction penalties. As a result, the average CPI of Computer B increases to $1.2$. The clock rate of Computer B is not yet determined.

Assume that the instruction count of the program is identical on Computer A and Computer B. Determine the clock rate that Computer B must achieve in order to meet the 6-second execution time target.

Modern ARM processors often use a big.LITTLE architecture to reduce energy consumption by executing only performance-critical code on high-power cores while running the remaining code on energy-efficient cores. Consider an ARM-based SoC with one big core and one LITTLE core, where only one core is active at any time. The LITTLE core consumes $2\ \mathrm{W}$ when active, while the big core consumes $8\ \mathrm{W}$ when active. When a core is inactive, its power consumption can be ignored.

A given program takes 10 seconds to complete when executed entirely on the LITTLE core. Profiling shows that $30\%$ of the execution time is performance-critical code that can benefit from the big core. The big core executes this portion $4\times$ faster than the LITTLE core. There is no overhead for switching between cores.

The program is executed using the following strategy:

a. The performance-critical portion runs on the big core.
b. The remaining portion runs on the LITTLE core.

What is the average power consumption (in watts) of the program when executed using the ARM big.LITTLE strategy described above?

CPU Scheduling & I/O Performance: CPU scheduling strategies significantly affect I/O system throughput.

a. Explain why it is crucial to let I/O-bound processes acquire the CPU as early as possible to maximize I/O throughput.

b. Using the Multilevel Feedback Queue algorithm as an example, explain how it dynamically identifies I/O-bound processes and adjusts their priorities to achieve this goal.

Copy-on-Write (COW) Mechanism: When using the Copy-on-Write mechanism to optimize the fork() system call:

a. Explain how the Page Table Entries (PTEs) for both the Parent and the Child should be configured immediately after fork() completes.

b. When the Child process attempts to write to a shared page, a Page Fault is triggered. How does the Kernel distinguish whether this Page Fault is caused by the Copy-on-Write mechanism or by an invalid memory access?

Simple Reader-Writer Spinlock: Consider the following Simple Reader-Writer Spinlock implemented using atomic operations. Assume that atomic_sub(addr, val) atomically subtracts val from *addr and returns the old value (before subtraction). atomic_add performs atomic addition.

(a) Prove that mutual exclusion holds between a Writer and a Reader.

(b) Prove that multiple Readers can enter the Critical Section simultaneously (Concurrency).

#define MAXVAL 0x40000000

void init_spinlock(int* lock) {
*lock = MAXVAL;
}

void writer_lock(int* lock) {
while (1) {
int oldVal = atomic_sub(lock, MAXVAL);
if (oldVal == MAXVAL) return; // Successfully acquired lock
else atomic_add(lock, MAXVAL); // Failed, rollback
}
}

void reader_lock(int* lock) {
while (1) {
int oldVal = atomic_sub(lock, 1);
if (oldVal > 0) return; // Successfully acquired lock
else atomic_add(lock, 1); // Failed, rollback
}
}

void reader_unlock(int* lock) {
atomic_add(lock, 1);
}

void writer_unlock(int* lock) {
atomic_add(lock, MAXVAL);
}