IS CS-2023S-04

题目来源：Problem 4 日期：2024-08-03 题目主题：CS-计算机体系结构

解题思路

在计算机体系结构中，不同的处理器架构可能会有不同的数据存储方式和缓存管理策略。以下问题涵盖了字节序、数据冒险、控制冒险、缓存记忆和指令周期等方面。这些问题需要理解处理器的内部工作原理以及其对程序执行的影响。

Solution

Question 1: Byte Order (Endianness)

Explanation:

The difference in output between processor A and processor B is due to the endianness of the processors.

Big-endian: Processor A stores the most significant byte (MSB) at the lowest memory address. Therefore, the bytes of the integer 0x12345678 are stored as 0x12 0x34 0x56 0x78.
Little-endian: Processor B stores the least significant byte (LSB) at the lowest memory address. Therefore, the bytes of the integer 0x12345678 are stored as 0x78 0x56 0x34 0x12.

In the given program, the union my_uni allows accessing the same memory location as both an integer and an array of characters. When printing the elements of the character array, the order of the bytes differs based on the processor’s endianness.

Output (a) corresponds to big-endian architecture.
Output (b) corresponds to little-endian architecture.

Question 2: Data Hazard and Control Hazard

Data Hazard:

Data hazards occur when instructions that exhibit data dependencies are executed in a pipeline. There are three types of data hazards: Read After Write (RAW), Write After Read (WAR), and Write After Write (WAW). In a pipeline without forwarding, these hazards can cause stalls.

Example:

ADD R1, R2, R3  // Instruction 1
SUB R4, R1, R5  // Instruction 2 (depends on the result of Instruction 1)

Instruction 2 needs the result of Instruction 1. Without forwarding, the pipeline must stall until the result of Instruction 1 is available.

Control Hazard:

Control hazards (or branch hazards) occur when the pipeline makes decisions based on the results of branch instructions.

Example:

BEQ R1, R2, LABEL  // Branch if R1 == R2
NOP                // This instruction may need to be flushed if the branch is taken
LABEL:

If the branch is taken, the instruction after the branch (NOP in this case) needs to be flushed and the pipeline must fetch the correct instruction from the branch target.

Question 3: Cache Memory

Given:

Cache size: 32 KiB ( $32 \times 2^{10}$ bytes)
Cache line size: 64 bytes
4-way set-associative cache
Address width: 32 bits

Calculation:

Number of cache lines:
$Number of cache lines = \frac{Cache size}{Cache line size} = \frac{32 \times 2 ^{10} bytes}{64 bytes} = 512 cache lines$
Number of sets:
$Number of sets = \frac{Number of cache lines}{Associativity} = \frac{512}{4} = 128 sets$
Index bit width:
$Index bit width = lo g_{2} (Number of sets) = lo g_{2} (128) = 7 bits$
Block offset bit width:
$Block offset bit width = lo g_{2} (Cache line size) = lo g_{2} (64) = 6 bits$
Tag bit width:
$Tag bit width = Address width - Index bit width - Block offset bit width = 32 - 7 - 6 = 19 bits$
Total RAM capacity for storing tags:
$Total tag storage = Number of sets \times Associativity \times Tag bit width = 128 \times 4 \times 19 = 9728 bits$

Question 4: Processor with Cache

Given:

CPI without cache miss: $C$
Cache miss penalty: $P$
Ratio of load/store instructions: $R_{l s}$
Cache miss rate of instruction cache: $R_{i}$
Cache miss rate of data cache: $R_{d}$
IPC (instructions per cycle): $I$

Expression for IPC:

The total CPI considering cache misses can be calculated as:

CPI = C + R_{i} \times P + R_{l s} \times R_{d} \times P

Since IPC is the inverse of CPI:

I = \frac{1}{CPI} = \frac{1}{C + R _{i} \times P + R _{l s} \times R _{d} \times P}

知识点

字节序数据冒险控制冒险缓存记忆指令周期

重点词汇

Big-endian: 大端序
Little-endian: 小端序
Data hazard: 数据冒险
Control hazard: 控制冒险
Pipeline: 流水线
Set-associative cache: 组相联缓存
Cache miss penalty: 缓存未命中惩罚
Instructions per cycle (IPC): 每周期指令数

参考资料

Computer Organization and Design by David A. Patterson and John L. Hennessy, Chap. 5
Computer Architecture: A Quantitative Approach by John L. Hennessy and David A. Patterson, Chap. 2

Zephyr's Notes on ISCS & CBMS, UTokyo

Explorer