先自己算，再核对，最后看完整推导

Suppose a cache is 10 times faster than main memory and has a hit rate of 90%. How much speedup is achieved by using the cache?

Determine how many times faster a cache memory must be compared to the main memory in order to achieve an overall speedup of 5. Assume that the cache hit rate is 0.85.

(a) Assume a machine has an ideal CPI of 2.0 when all instruction and data accesses hit in the cache. Loads and stores account for 40% of all instructions. Every instruction fetch and every data access has a cache miss rate of 2%. The miss penalty is 25 clock cycles. How much slower is the machine compared with the ideal all-hit machine?

(b) What would happen if there were no cache at all, assuming every memory access incurs the same 25-cycle penalty?

(c) If the ideal CPI is reduced to 1.0, but we want to maintain the same performance ratio as in part (a), what miss penalty is required, assuming the miss rate remains unchanged?

Consider the following program fragment:

sum = 0; i = 0; while (sum < 15 && i < 8) { sum += a[i]; i++; }

The contents of the array a are: a[0] = 3, a[1] = 4, a[2] = 2, a[3] = 6, a[4] = 5, a[5] = 1, a[6] = 7, a[7] = 2. Determine:

• the final value of sum;
• the number of memory accesses;
• the total access time without using a cache;
• the total access time with a cache; and
• the performance improvement factor due to using the cache.

A 500 MHz processor has a main memory access time of 60 ns. Assume that the processor has an ideal Cycles per Instruction (CPI) of 2 when using a perfect cache (i.e., all instruction and data accesses hit in the L1 cache). Suppose that 25% of the program instructions are load or store instructions. If the instruction cache miss rate is 2% and the data cache miss rate is 5%, compute the effective CPI of the processor.

Suppose a cache memory is 5 times faster than the main memory. The cache hit time is 10 ns, while a cache miss requires 100 ns. A program takes 1 hour to execute, and 20% of the execution time is spent on memory and cache accesses. The cache system achieves an average miss rate of 0.1. Determine how much execution time would be saved or lost if the same program were executed without cache memory.

(Extra question shown in the lecturer's Tutorial 7 solutions.) Assume each instruction requires on average 1.2 instruction fetches, and the processor has an ideal CPI of 1.5. The instruction-cache miss rate is 2% with a miss penalty of 50 cycles. On average there are 0.3 data accesses per instruction, the data-cache miss rate is 5% and the data miss penalty is 80 cycles. Find the memory stall cycles per instruction and the actual CPI.

A processor has an ideal CPI of 1.5 when all instruction fetches and data accesses hit in the cache. The actual CPI is measured to be 2.7. Assume that:

• 40% of the instructions are load/store instructions.
• The instruction-cache miss penalty is 30 clock cycles.
• The data-cache miss penalty is 60 clock cycles.
• The data-cache miss rate is 3.3 times the instruction-cache miss rate.

Find the instruction-cache miss rate, the data-cache miss rate, and the total memory stall cycles per instruction.

A processor has an ideal CPI of 1.8. The instruction mix consists of 60% arithmetic/logic instructions, 25% load/store instructions and 15% branch instructions. Assume:

• Every instruction requires one instruction fetch.
• Only load/store instructions access data memory.
• The combined miss rate (for both instruction fetches and data accesses) is 3%.
• The miss penalty is 40 clock cycles.

Determine the average number of memory references per instruction, the memory stall cycles per instruction, the actual CPI, and the percentage of execution time spent on memory stalls.

A cache has hit time = 2 cycles, miss rate = 4% and miss penalty = 80 cycles. Determine the miss time and the Average Memory Access Time (AMAT).

A computer has 4 GB of byte-addressable main memory and uses a 32-bit address bus. For each of the following cache organisations, determine:

1. The number of cache blocks/lines
2. The number of sets
3. The number of address bits used for the block offset, index, and tag
4. The total number of bits required to store all tag fields
5. The number of XOR gates required for tag comparison
6. Assume that 1 word = 4 bytes.

(i) A direct-mapped cache with a total data size of 512 KB, using 8-word blocks.
(ii) A 2-way set-associative cache with a total data size of 256 KB, using 2-word blocks.

Consider a program in which 20% of the instructions are load or store instructions. The processor has: main memory access time = 50 ns; processor clock rate = 500 MHz; base CPI with a perfect cache = 2.0; instruction-cache miss rate = 3%; data-cache miss rate = 10%. Assume that every instruction requires one instruction fetch, and only load/store instructions require a data-cache access. Also assume that the miss penalty is equal to the main memory access time. Find the effective CPI of the machine.

Assume a computer with a 32-bit byte-addressable address space.

1. For a 1 MB, 8-way set-associative cache with 128-byte blocks, determine the number of bits used for the tag, index, and block offset.
2. Consider a direct-mapped cache with 32 cache blocks and a 21-bit tag. Determine the block size and the total cache capacity.
3. A cache has a total data capacity of 256 bytes, a 28-bit tag, and 16-byte blocks. Determine the number of index bits and the degree of associativity.

Assume a computer with a 32-bit byte-addressable address space. A cache has capacity = 256 KB, block size = 64 bytes, 4-way set associativity. Determine:

1. The number of cache blocks.
2. The number of sets.
3. The number of offset bits.
4. The number of index bits.
5. The number of tag bits.
6. The total number of bits required to store all tags.
7. The number of comparators required for tag comparison.

A processor uses a cache memory with cache hit time = 2 ns, cache miss penalty = 80 ns and cache hit rate = 95%.

(a) Determine 1. the cache miss rate, 2. the cache miss time, 3. the AMAT. Use both of the following formulas and verify that they give the same answer: AMAT = HR × HT + MR × MT and AMAT = HT + MR × MP.

(b) A cache designer improves the cache and increases the hit rate from 95% to 98%. Assuming the hit time and miss penalty remain unchanged, determine the new AMAT.

(c) Another design reduces the miss penalty from 80 ns to 40 ns while keeping the original hit rate of 95%. Determine the new AMAT.

(d) Compare the results obtained in Parts (a), (b), and (c). Which improvement gives the larger reduction in AMAT?

(e) A second cache design has hit time = 1 ns, miss penalty = 120 ns, hit rate = 94%. Determine its AMAT. Which cache design would you choose based on AMAT? Explain your answer.

Consider a cache with tag size = 6 bits and number of cache lines = 16. Determine the number of comparators required for a direct-mapped cache, the total number of parallel bit-comparisons required for a direct-mapped cache, the number of comparators required for a fully-associative cache, and the total number of parallel bit-comparisons required for a fully-associative cache.

A computer system has main memory size 256 bytes, cache size 8 cache lines, block size 4 bytes per block, Least Recently Used (LRU) replacement (where applicable), and the cache is initially empty. The following sequence of memory references is generated: 20, 37, 54, 20, 70, 38. Repeat the following for each cache organization: (a) fully-associative; (b) direct-mapped; (c) 2-way set-associative.

(i) Determine the number of bits required for the memory address, tag, index (or set index) and offset, where applicable.

(ii) For each memory reference: determine the corresponding memory block; determine the cache set (or cache line) to which the block maps; state whether the access is a hit or a miss; if it is a miss, classify it as either a compulsory (cold) miss or a conflict miss; show the contents of the cache after the access, including the LRU information for each line (where applicable).

(iv) Using the same sequence, determine the total number of cache hits, cache misses, compulsory (cold) misses, conflict misses, and the cache hit rate.

(v) Compare the results obtained for the three cache organizations and comment on the effect of cache associativity on cache performance.

Suppose a computer has a 12-bit byte-addressable address space and a direct-mapped cache with 16 cache blocks. Each cache block can store 16 bytes of data. A program generates the following sequence of memory accesses, given in hexadecimal: 3FE, 4FE, 4FD, 4F2, 111, 111, 2F1, 4FE, 2F7, 448, 2F9, 2A2.

1. How many bits are used for the cache tag field?
2. Assuming the cache is initially empty, determine the final contents of the cache after the program runs. Draw a diagram of the cache showing all fields, but fill in only the tag fields.
3. Suppose a cache hit takes 5 ns, a cache miss takes 100 ns, and a memory access without a cache takes 95 ns. How much time is saved by using this cache for the given program, compared with an equivalent machine without a cache?
4. Give one example of spatial locality and one example of temporal locality exhibited by this program.

Assume that a CPU has a base CPI of 2.0 with a perfect cache and a clock cycle time of 2 ns. The program has an average of 1.3 memory references per instruction. Two cache organizations are considered:

1. Direct-mapped 64-KB cache: miss rate = 1.4%, clock cycle time = 2 ns.
2. 2-way set-associative 64-KB cache: miss rate = 1.0%, clock cycle time increases by 10% due to the selection multiplexer.

Assume cache hit time = 1 clock cycle and cache miss penalty = 70 ns for both organizations. Calculate (a) the AMAT for each cache organization; (b) the CPU time for each cache organization in terms of instruction count, IC; (c) which cache organization gives better overall CPU performance? Explain briefly.

A processor has two levels of data cache: L1 — block size 8 bytes, hit time 1 cycle, local miss rate 5%; L2 — block size 32 bytes, hit time 19 cycles, local miss rate 2%. Assume that it takes 50 clock cycles to request and complete a 32-byte transfer between main memory and the L2 cache.

(a) Find the AMAT for the L2 cache. (b) Find the AMAT for the L1 cache. (c) Assume the ideal CPI is 2.0 and 25% of the instructions are loads or stores. Find 1. the average memory stall cycles per instruction; 2. the overall CPI.

Consider a cache that initially contains memory block 100–103 with cache contents A, B, C, D. The CPU performs: 1. Store X to address 101; 2. Store Y to address 102; 3. Store Z to address 101.

1. Using a write-through cache, show the contents of the cache and main memory after each store operation.
2. Using a write-back cache, show the contents of the cache and main memory after each store operation.
3. For the write-back cache, indicate the value of the dirty bit after each operation.
4. Assume the cache block is later evicted. Show the final contents of main memory.
5. State two advantages of write-back caches over write-through caches.
6. State one advantage of write-through caches over write-back caches.

A computer uses a 32-bit address space and a 64 KB cache with 64-byte blocks. Answer for each organization: 1. direct-mapped; 2. 4-way set-associative; 3. fully associative.

(a) Determine the number of cache blocks, cache sets, tag bits, index bits and offset bits. (b) How many tag comparators are required for each organization during a cache lookup? (c) If each cache block requires 1 valid bit and tag storage only (ignore data storage), calculate the total number of bits required to store all tags and valid bits for each organization. (d) Which organization is expected to have 1. the lowest conflict miss rate, 2. the lowest hardware complexity, 3. the largest tag storage overhead? Explain briefly.

A program accesses the byte addresses 8, 12, 16, 20, 24, 28, 32, 36. Assume the cache is initially empty.

(a) Suppose the cache contains only one cache block and uses a block size of 8 bytes. For each access, indicate hit or miss, and determine the overall miss rate. (b) Repeat (a) with a block size of 16 bytes. (c) Repeat (a) with a block size of 32 bytes. (d) Compare the miss rates in (a)–(c). Explain how increasing block size exploits spatial locality. (e) Although larger blocks may reduce compulsory misses, explain why excessively large blocks can increase the overall miss rate in a fixed-size cache. (f) A designer is considering increasing the block size from 64 B to 256 B while keeping the cache size fixed. State one advantage and two disadvantages of the larger block size.

A computer system uses 32-bit virtual addresses, 30-bit physical addresses and a page size of 4 KB. Page table entries: VPN 0x12345 → PPN 0x1A234 (valid 1); VPN 0x12346 → PPN 0x0B567 (valid 1); VPN 0xABCDE → PPN 0x1F890 (valid 1); VPN 0x22222 → — (valid 0).

(a) Determine the number of bits used for 1. the page offset, 2. the VPN, 3. the PPN. (b) Translate the virtual addresses 0x12345678, 0x12346ABC and 0xABCDEFFF into physical addresses. Show all working. (c) What happens when the CPU attempts to access virtual address 0x22222000? Explain the role of the valid bit. (d) Explain why the page offset remains unchanged during address translation. (e) State two advantages of virtual memory. (f) A page fault requires 5 ms to service, whereas a TLB miss requires only 50 ns. Calculate how many times more expensive a page fault is than a TLB miss.

A computer system uses a cache. The following cache misses are observed: 1. the program accesses memory block A for the first time and incurs a miss; 2. memory blocks B and C repeatedly replace each other in the cache because they map to the same cache location; 3. a program repeatedly accesses a working set of 2 MB, but the cache size is only 64 KB. For each scenario, (a) state whether the miss is compulsory, conflict or capacity; (b) suggest one method to reduce the miss rate.

(i) Consider a task that can be divided into m equal-duration subtasks, each requiring one clock cycle. The task is executed using an m-stage pipeline, where each stage performs one subtask. Derive an expression for the total number of clock cycles required for the pipeline to complete n tasks. Hence, show that T_pipeline = m + n − 1 clock cycles.

(ii) Figure 1 shows a sequential machine and its pipelined counterpart. Each widget must pass through three processing steps A, B and C, each requiring one clock cycle. The sequential machine completes the three steps one after another; the pipelined machine has three stages (A, B, C), each requiring one clock cycle. Determine the minimum number of widgets that must be processed for the pipelined machine to achieve a speedup of at least 2.5 over the sequential machine. Justify your answer.

A processor can be implemented either as a single-stage (non-pipelined) processor with a clock cycle time of 5 ns, or as a 5-stage pipelined processor with a clock cycle time of 1 ns. Both execute the same instruction set, and the program is long enough that pipeline filling and draining effects may be ignored.

(a) Assuming no pipeline stalls, determine the speedup of the 5-stage pipelined processor relative to the single-stage processor. (b) Suppose the pipelined processor incurs a one-cycle stall for 40% of all instructions: i. determine its average CPI; ii. determine its speedup relative to the single-stage processor. (c) Now consider an alternative 4-stage pipelined processor with a clock cycle time of 1.1 ns and no stalls: i. determine the execution time per instruction for both pipelined processors; ii. determine which implementation delivers better performance and explain why.

Component delays: instruction fetch 200 ps, register read 100 ps, ALU operation 200 ps, data memory access 200 ps, register write 100 ps. The processor can be single-cycle or a 5-stage pipeline (one stage per component), with no stalls or hazards; the pipelined clock is set by the slowest stage, and the LW instruction (the longest path) sets the single-cycle clock.

(a) Suppose the ALU delay is reduced by 25%: i. the new ALU delay; ii. the LW execution time in the single-cycle processor; iii. the pipelined clock cycle time; iv. the speedup achieved by pipelining, compared with the original speedup. (b) Repeat with the ALU delay increased by 25%.

A processor performs a simplified image-processing task. Each image block passes through four stages: load image block from memory 10 ns; apply filter operation 20 ns; compute feature value 15 ns; store result to memory 5 ns. A pipelined implementation is used, and each stage can process only one image block at a time.

(a) Determine the pipeline cycle time. (b) How long does it take to complete the first image block? (c) Determine the total time required to complete 8 image blocks. (d) If the blocks were processed sequentially, determine the total time for 8 blocks. (e) Determine the speedup achieved by pipelining. (f) Explain why the speedup is less than the number of stages.

A simple pipelined system consists of three stages: X read input 10 s; Y process input 25 s; Z write output 15 s. Assume that a task must pass through X, Y and Z in sequence; once a stage finishes a task it can immediately begin the next; different stages can work on different tasks simultaneously; there are no resource conflicts or dependencies; the pipeline cycle time is determined by the slowest stage; pipeline register overhead is negligible; a batch job contains 1000 independent tasks.

(The tutorial slide does not list the quantities to compute; the solution works out the standard set.)

A simple pipelined system consists of four stages: A read input 22 s; B decode input 38 s; C process input 34 s; D write output 30 s. A batch job contains 1000 independent tasks. The system operates as an ideal pipeline, and the cycle time is determined by the slowest stage. An engineer is allowed to reduce the total execution time across all stages by 24 seconds; the reduction may be distributed across one or more stages. Determine:

i. the original pipeline cycle time and the total time for all 1000 tasks; ii. how the 20-second reduction should be distributed among the stages to maximize throughput; iii. the new cycle time and total time after optimization; iv. the percentage improvement in throughput.

Consider a 5-stage DLX pipeline IF → ID → EX → MEM → WB with stage delays IF 220 ps, ID 180 ps, EX 250 ps, MEM 200 ps, WB 150 ps.

(a) Determine the pipeline clock period. (b) Determine the latency of a single instruction in the pipelined processor. (c) Determine the throughput after the pipeline is filled. (d) A student claims: "Since the pipelined instruction latency is larger than the single-cycle instruction latency, pipelining makes the processor slower." Do you agree? Explain using latency and throughput. (e) Determine the theoretical maximum speedup if all stages could be perfectly balanced.

Registers: R1 = 100, R2 = 20, R3 = 5, R4 = 200. Memory: [120] = 50, [208] = 80. Instructions: LW R5, 20(R1), ADD R6, R2, R3, ADDI R7, R2, #10, BEQZ R3, LOOP, J EXIT.

(a) For each instruction, identify 1. the format (R-type, I-type or J-type) and 2. the addressing mode. (b) Determine the final value produced by each instruction (each executes independently). (c) For LW R5, 20(R1), identify the meaning of the opcode, RS1, RD and the immediate field. (d) Explain why ADD R8, R2, 20(R1) is illegal in DLX and rewrite it using valid DLX instructions.

Consider the DLX instruction ADD R7, R3, R4 with R3 = 25, R4 = 17 and PC = 200. For each pipeline stage (IF, ID, EX, MEM, WB): 1. describe the operation performed; 2. determine the key outputs generated; 3. state whether data memory is accessed. Use a table with columns Stage, Operation Performed, Key Output.

Refer to the 5-stage DLX datapath and consider ADDI R5, R2, #-12 with R2 = 40. Determine: 1. the 16-bit two's complement representation of −12; 2. the 32-bit sign-extended value; 3. the value of A after the ID stage; 4. the value of Imm after sign extension; 5. the value of ALUOut after the EX stage; 6. the final value written into R5 during WB. Show all working and intermediate results.

Register and memory contents: R2 = 500, R3 = 88, Mem[520] = 123. Consider LW R1,20(R2) and SW 20(R2),R3. For each instruction determine: 1. the effective address; 2. ALUOut; 3. whether memory is read or written; 4. the value of LMD (if any); 5. the final value stored in memory or register.

Refer to the 5-stage DLX datapath and consider LW R8,40(R4). The pipeline uses the inter-stage buffers F/D, D/A, A/M and M/W. Assume R4 = 1000 and Memory[1040] = 250. For each pipeline buffer, identify the information that must be stored after the corresponding stage, and complete the table (Buffer, Information Stored).

Consider the instruction sequence LW R1,0(R2); ADD R3,R4,R5; ADDI R6,R7,#10; SW 20(R8),R9; BEQZ R10,LOOP. The 5 DLX stages are IF → ID → EX → MEM → WB; assume ideal pipelining with no hazards or stalls. Draw the pipeline timing diagram showing the stage occupied by each instruction during every clock cycle (rows: cycle 1, 2, …; columns: I1–I5).

Consider a processor with five pipeline stages IF → ID → EX → MEM → WB with delays IF 250 ns, ID 350 ns, EX 150 ns, MEM 300 ns, WB 200 ns. The unpipelined design executes one instruction at a time; the pipelined design uses the same five stages; hazards, stalls and branch penalties are ignored; pipeline register overhead is negligible unless stated otherwise. Determine: a) the average instruction execution time of the unpipelined processor; b) the average instruction execution time of the pipelined processor; c) the speedup achieved by pipelining; d) the theoretical maximum speedup of this 5-stage pipeline if overhead is ignored and all stages are perfectly balanced. Show all calculations.

Consider LW R1, 20(R2) with R2 = 100 and Memory[120] = 55. For each pipeline register (F/D, D/A, A/M, M/W), determine the contents stored at the end of the cycle.

Assume: unpipelined CPI = 4.6, clock cycle = 0.8 ns; pipelined CPI = 1.2, clock cycle = 1.0 ns. Determine 1. the average instruction execution time (unpipelined); 2. the average instruction execution time (pipelined); 3. the pipeline speedup.

For an R4000-style pipeline, the branch target address is known after 3 pipeline stages and the branch condition is evaluated 1 cycle later; assume no stalls due to register dependencies in the branch comparison. Branch penalties (unconditional / conditional not taken / conditional taken): flush pipeline 2 / 3 / 3; predict taken 2 / 3 / 2; predict not taken 2 / 0 / 3. SPEC branch frequencies: unconditional 4%, conditional not taken 6%, conditional taken 10%. Find the effective addition to CPI due to branches for each branch handling scheme.

The PowerPC 601 has a 6-stage pipeline: Fetch → Dispatch → Decode → Execute → Cache Access → Write. A branch or jump is detected in Fetch; the target address for a jump or conditional branch is available at the end of Decode; the conditional branch outcome is decided in Execute. Benchmark profile: conditional branches 20% of all instructions; jumps or calls 5%; 60% of conditional branches are taken.

a) Find the expected CPI if the CPU stalls until the branch outcome is known. b) Suppose two-slot delayed branching is added for unconditional branches. If 60% of the delay slots are filled with useful instructions, what is the new CPI? Assume conditional branches use the "Predict Not Taken" strategy.

Assume delayed branching is implemented: the instruction immediately after the branch is always executed before the branch takes effect. Reorder the following code to make better use of the branch delay slot. Assume R3 is initialized to 8 before the loop starts; the code may need to be slightly modified to preserve correctness.

Loop: LW R2, 100(R3) / SW 200(R3), R2 / SUBI R3, R3, #4 / BNEZ R3, Loop / NOP ; branch delay slot

A pipelined processor uses a single-port memory shared by instruction fetches and data accesses. 40% of instructions are loads/stores. Assume ideal CPI = 1 and each load/store causes 1 structural stall cycle. a) Compute the average stall cycles per instruction. b) Determine the effective CPI. c) Determine the speedup relative to a non-pipelined processor with CPI = 5.

For each instruction pair, identify the hazard type (RAW, WAR, WAW, or None): 1. ADD R1,R2,R3 / SUB R4,R1,R5; 2. ADD R1,R2,R3 / LW R2,0(R5); 3. LW R1,0(R2) / ADD R1,R3,R4; 4. ADD R1,R2,R3 / OR R4,R5,R6. For each dependency, state whether it can occur in a basic DLX pipeline.

Consider LW R1,0(R2); ADD R3,R1,R4; SUB R5,R3,R6; AND R7,R5,R8 on a DLX pipeline with forwarding. a) Identify all RAW hazards. b) Determine which hazards can be eliminated by forwarding. c) Determine the number of stall cycles required. d) Draw the pipeline timing diagram.

Consider LW R1,0(R2); ADD R3,R1,R4; BEQZ R3,Target; OR R5,R6,R7. Assume forwarding is available, the branch is resolved in the EX stage, and there is no branch prediction. a) Draw the pipeline timing diagram. b) Identify all data hazards. c) Identify all control hazards. d) Determine the total number of stall cycles.

A benchmark contains 15% branch instructions, of which 60% are taken and 40% not taken. The processor uses the Predict Not Taken scheme, with a branch penalty of 3 cycles when the prediction is incorrect and ideal CPI = 1. a) Compute the average branch penalty. b) Determine the additional CPI caused by branches. c) Determine the effective CPI. d) Compare the result with a processor that always stalls 3 cycles for every branch.