Ex$5$: Cache Performance Analysis

A CPU produces the following sequence of read addresses in hexadecimal:

$1$A$,2$C$,3$E$,1$A$,0$B$,3$F$,2$C$,4$D$,3$E$,1$A$,0$B$,5$A$,6$B$,2$C$,4$D$.$

Suppose the cache has $16$ words, and the word size is $32$ bits. The cache is initially empty, and

the CPU uses a $10-$bit byte$-$level address. Use the Least Recently Used $($LRU$)$ replacement

policy.

Tasks:

Determine hits and misses for the following cache organizations:

Direct$-$Mapped Cache

Fully Associative Cache

$4-$Way Set Associative Cache

Address Conversion Table:

Convert each hexadecimal address into its $10-$bit binary equivalent. Indicate the tag,

index, and offset bits for each cache type.

Cache Table:

Fill in the table to track the sequence of hits $($H$)$ or misses $($M$)$ for each cache

organization.

Sketch the Cache Structure:

Draw how the blocks are placed in the cache for each mapping scheme.

Indicate block replacements when they occur.

Calculate and Compare Hit Ratios:

Compute the hit ratio for each mapping scheme.

Word$-$Level Design Modification:

Suppose the cache is redesigned to store $4$ words per block instead of $1$ word per

block.

How would the address division $($tag$,$ index, offset$)$ change?

Discuss the potential impact on the hit ratio and the memory hierarchy.

Performance Impact of Miss Penalty:

Explain how increasing the miss penalty affects system performance.

Discuss strategies to reduce miss penalties.

Ex$7$:

$1.$ Memory Chip Design

How many $64$K $16$ chips are needed to provide a RAM of $2$M $32?$

$$ Tasks:

o Determine the number of chips required.

o Design the RAM chip layout.

o Specify all the inputs and outputs required for the design.

$2.$ GPU Acceleration and Amdahl$$s Law

A computation runs $20$ times faster on the GPU compared to the CPU. Assume that $70\%$ of the program can be accelerated using the GPU.

$$ Tasks:

o Calculate the overall speedup using Amdahl$$s Law.

o If the program requires an overall speedup of $8,$ determine the percentage of the program that must be accelerated using the GPU.

$3.$ Virtual Memory and Page Tables

In a multitasking system with virtual memory:

$$ Page size: $16$ kB

$$ Page table entry size: $128$ bits

$$ The number of pages per program:

o Program X: $3500$ pages

o Program Y: $4800$ pages

o Program Z: $5200$ pages

Tasks:

$$ Calculate the total memory occupied by the page tables for all three programs in bytes.

$-$ If each program requires a directory for $8$ regions, where each directory entry is $64$ bytes, calculate the total memory occupied by the directory pages.

$4.$ Speed$-$Up with Multiple Processors

Two computations are performed:

$-$ A scalar sum of $100$ variables.

$-$ A matrix sum of two$-$dimensional arrays of dimensions $4040.$

Tasks:

$-$ Calculate the speedup using $50$ processors versus $100$ processors, assuming perfect parallelism.

$-$ Discuss the effect of diminishing returns as the number of processors increases.

$5.$ Cache Design and Address Decomposition

a$)$ Show the address decomposition for a $256$kB direct$-$mapped cache with a $64-$byte block size using a $32-$bit address.

$-$Identify the tag, index, and offset bits.

b$)$ For a direct$-$mapped cache with the following address division:

$-$ TAG: Bits $31-12$

$-$ INDEX: Bits $11-6$

$-$ BYTE OFFSET: Bits $5-0$

Tasks:

$-$ Determine the cache line size in bytes.

$-$ Calculate the number of cache entries.