\documentclass[11pt]{article}
\usepackage[a4paper,margin=0.9in]{geometry}
\usepackage{array}
\usepackage{booktabs}
\usepackage{longtable}
\usepackage{multirow}
\usepackage{tabularx}
\usepackage{enumitem}
\usepackage{amsmath,amssymb}
\usepackage{fancyhdr}
\usepackage{titlesec}
\usepackage{makecell}
\usepackage{setspace}
\usepackage{xcolor}
\usepackage{graphicx}
\usepackage{lastpage}
\usepackage{calc}
\usepackage{tikz}
\usepackage{listings}
\usepackage{mdframed}
\usepackage{environ}
\usetikzlibrary{arrows.meta,positioning,calc}

\setlength{\parindent}{0pt}
\setlength{\parskip}{4pt}
\renewcommand{\arraystretch}{1.15}

\pagestyle{fancy}
\fancyhf{}
\lhead{CA I}
\rhead{2026}
\cfoot{HW7, Page \thepage\ of \pageref{LastPage}}

\newcommand{\ptbox}[1]{%
    \makebox[0pt][r]{\raisebox{0.2ex}{\fbox{\rule{0pt}{1.2ex}\hspace{0.5em}#1\hspace{0.5em}}}\hspace{0.8em}}%
}

\newcommand{\scoreline}[2]{\ptbox{#1}\textbf{#2}}
\newcommand{\blank}{\underline{\hspace{2.5cm}}}
\newcommand{\sblank}{\underline{\hspace{1.5cm}}}
\newcommand{\mblank}{\underline{\hspace{3.5cm}}}
\newcommand{\lblank}{\underline{\hspace{5cm}}}

\titleformat{\section}
  {\normalfont\bfseries\large}
  {\thesection.}
  {0.5em}
  {}

\lstset{
  language=C,
  basicstyle=\ttfamily\small,
  keywordstyle=\color{blue}\bfseries,
  commentstyle=\color{gray},
  showstringspaces=false,
  columns=fullflexible,
  keepspaces=true,
  frame=single
}

\mdfdefinestyle{solframe}{
  linewidth=0.6pt,
  innertopmargin=6pt,
  innerbottommargin=6pt,
  innerleftmargin=8pt,
  innerrightmargin=8pt,
  skipabove=6pt,
  skipbelow=6pt,
  roundcorner=2pt
}


\newcommand{\blankphysicaladdressdiagram}{
\begin{center}
\setlength{\tabcolsep}{0pt}
\renewcommand{\arraystretch}{1.0}
\begin{tabular}{*{12}{>{\centering\arraybackslash}m{0.85cm}}}
11 & 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0
\end{tabular}

\vspace{0.08cm}

\begin{tabular}{|*{12}{>{\centering\arraybackslash}m{0.85cm}|}}
\hline
\rule{0pt}{1.05cm} & & & & & & & & & & & \\
\hline
\end{tabular}
\end{center}
}

\newcommand{\twolvlpagetablefigure}{
\begin{center}
\begin{tikzpicture}[
    x=1cm,y=1cm,
    >=Stealth,
    arr/.style={->, line width=1.0pt, draw=blue!65},
    idx/.style={->, line width=1.2pt, draw=violet!85!black},
    thickbox/.style={draw=black, line width=1.0pt},
    lab/.style={font=\bfseries\large},
    idxlab/.style={font=\bfseries\Large, text=violet!85!black}
]

% PTBR
\draw[thickbox] (0.9,1.2) rectangle (2.4,1.8);
\node[lab, align=center] at (1.65,0.45) {Page Table\\Base Register};

% L1 table
\draw[thickbox] (3.8,0.3) rectangle (5.3,3.1);
\foreach \y in {1.0,1.7,2.4} {
    \draw[thickbox] (3.8,\y) -- (5.3,\y);
}
\node[lab] at (4.55,-0.15) {L1 Table};

% Upper L2
\draw[thickbox] (6.9,1.9) rectangle (8.4,4.7);
\foreach \y in {2.6,3.3,4.0} {
    \draw[thickbox] (6.9,\y) -- (8.4,\y);
}
\node[lab] at (7.65,1.35) {L2 Table};

% Lower L2
\draw[thickbox] (6.9,-1.9) rectangle (8.4,0.9);
\foreach \y in {-1.2,-0.5,0.2} {
    \draw[thickbox] (6.9,\y) -- (8.4,\y);
}
\node[lab] at (7.65,-2.45) {L2 Table};

% Upper middle data pages
\draw[thickbox] (10.0,2.1) rectangle (11.5,4.9);
\foreach \y in {2.8,3.5,4.2} {
    \draw[thickbox] (10.0,\y) -- (11.5,\y);
}
\node[lab] at (10.75,1.55) {Data Pages};

% Right data pages
\draw[thickbox] (12.8,1.0) rectangle (14.3,3.8);
\foreach \y in {1.7,2.4,3.1} {
    \draw[thickbox] (12.8,\y) -- (14.3,\y);
}
\node[lab] at (13.55,0.45) {Data Pages};

% Lower data pages
\draw[thickbox] (10.0,-1.8) rectangle (11.5,1.0);
\foreach \y in {-1.1,-0.4,0.3} {
    \draw[thickbox] (10.0,\y) -- (11.5,\y);
}
\node[lab] at (10.75,-2.35) {Data Pages};

% Blue arrows
\draw[arr] (2.4,1.5) -- (3.8,0.35);
\draw[arr] (5.3,1.65) -- (6.9,2.15);
\draw[arr] (5.3,0.75) -- (6.9,-1.75);

% Upper L2 -> upper data pages
\draw[arr] (8.45,4.25) -- (12.8,1.0);
\draw[arr] (8.45,3.15) -- (10.2,1.92);

% Lower L2 -> lower data pages
\draw[arr] (8.4,-0.55) -- (10.05,-1.65);

% Purple index arrows
\draw[idx] (3.55,0.75) -- (3.55,1.95);
\node[idxlab] at (3.15,1.35) {P1};

\draw[idx] (6.7,2.2) -- (6.7,3.5);
\node[idxlab] at (6.35,2.85) {P2};

\draw[idx] (9.8,-1.55) -- (9.8,-0.2);
\node[idxlab] at (9.45,-0.95) {offset};

\end{tikzpicture}

\vspace{0.35em}
Figure 1: Two-level Hierarchical Page Table
\end{center}
}

\begin{document}

\begin{center}
    {\Large \textbf{Computer Architecture I 2026}}\\
    {\Large \textbf{Homework 7}}
\end{center}

Chinese Name:\underline{\hspace{4cm}} \\
Pinyin Name:\underline{\hspace{4cm}} \\
Student ID:\underline{\hspace{4cm}} \\
E-Mail prefix:\underline{\hspace{4cm}} \\

\vspace{0.6em}

\scoreline{10}{1. Put T (True) or F (False) for each of following statement. [2 points each]}


\begin{enumerate}[label=(\alph*),leftmargin=2.2em]
    \item ( \hspace{1cm} ) If two processes share the same physical page, then they must use the same virtual address to access that page.
    

    \item ( \hspace{1cm} ) A TLB miss can occur even when the referenced page is present in physical memory and its page-table entry is valid.
    

    \item ( \hspace{1cm} ) If a machine has 32-bit virtual addresses and 30-bit physical addresses, then no process can use more than \(2^{30}\) bytes of virtual memory.
    

    \item ( \hspace{1cm} ) In a multi-level page table, the operating system may avoid allocating lower-level page tables for virtual address regions that are never used.
    

    \item ( \hspace{1cm} ) A page fault always implies that some page currently in memory must be written back to disk before the faulting access can complete.
    
\end{enumerate}
\newpage

\scoreline{20}{2. Set-Associative TLB Replacement and Address Translation [20 points]}

A processor has \textbf{20-bit virtual addresses}, \textbf{256-byte pages}, and an \textbf{8-entry TLB} organized as a \textbf{2-way set associative cache} with \textbf{4 sets}. The TLB uses \textbf{LRU replacement within each set}. In each set, the \textbf{LRU field is 1 bit}, where \textbf{0 means most recently used (MRU)} and \textbf{1 means least recently used (LRU)}.

At some time instant, the TLB for the current process is in the initial state shown in Table 2. Assume:
\begin{itemize}[leftmargin=1.8em,itemsep=1pt,topsep=2pt]
    \item all valid entries in the initial TLB correctly reflect the current page table state;
    \item all referenced pages are readable and writable;
    \item if a referenced VPN is found in the TLB, the access uses the existing translation;
    \item if a referenced VPN is not found in the TLB, assume for this problem that it does not already have a resident physical page; the system immediately creates a new translation for that VPN and allocates a new physical page from the free list;
    \item on a TLB miss, if the VPN is not already in the TLB, a new TLB entry is created;
    \item when a new translation must be created, the system first uses an \textbf{invalid entry in the target set} if one exists; otherwise, it replaces the \textbf{LRU entry in that set};
    \item on a write access, the corresponding TLB entry's Dirty bit becomes 1; on a read access, the Dirty bit is unchanged;
    \item newly allocated physical pages are taken in order from the free list.
\end{itemize}

Free physical pages: \textbf{0x031, 0x032, 0x033, 0x034}.

Fill in the final state of the TLB according to the access pattern in Table 1, and answer the following questions.

\begin{center}
\textbf{Table 1: Access Pattern for Memory}
\end{center}
\begin{center}
\begin{tabular}{|c|c|}
\hline
No. & Access Pattern \\
\hline
1 & Write 0x2333A \\
2 & Read 0x11AF0 \\
3 & Write 0x20244 \\
4 & Write 0x13001 \\
5 & Read 0x20FEE \\
6 & Write 0x34155 \\
\hline
\end{tabular}
\end{center}

\begin{center}
\textbf{Table 2: Initial TLB}
\end{center}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
Set & Way & Tag & PPN & Valid & Dirty & LRU \\
\hline
0 & 0 & 0x044 & 0x024 & 1 & 0 & 1 \\
0 & 1 & 0x02B & 0x026 & 1 & 1 & 0 \\
\hline
1 & 0 & 0x004 & 0x021 & 1 & 1 & 0 \\
1 & 1 & 0x000 & 0x000 & 0 & 0 & 1 \\
\hline
2 & 0 & 0x080 & 0x022 & 1 & 1 & 1 \\
2 & 1 & 0x046 & 0x025 & 1 & 0 & 0 \\
\hline
3 & 0 & 0x03F & 0x027 & 1 & 0 & 0 \\
3 & 1 & 0x000 & 0x000 & 0 & 0 & 1 \\
\hline
\end{tabular}
\end{center}


\scoreline{8}{(a)}
For each access in Table 1, determine the following:
\begin{itemize}[leftmargin=1.8em,itemsep=1pt,topsep=2pt]
    \item the \textbf{VPN};
    \item the \textbf{TLB set index};
    \item the \textbf{TLB tag};
    \item whether it is a \textbf{TLB hit} or \textbf{TLB miss}.
\end{itemize}

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
No. & Virtual Address & VPN & Set Index & Tag & Hit / Miss \\
\hline
1 & 0x2333A & & & & \\
2 & 0x11AF0 & & & & \\
3 & 0x20244 & & & & \\
4 & 0x13001 & & & & \\
5 & 0x20FEE & & & & \\
6 & 0x34155 & & & & \\
\hline
\end{tabular}
\end{center}


\scoreline{12}{(b)}
Fill in the \textbf{final state of the TLB} in Table 3 after all six accesses.

\begin{center}
\textbf{Table 3: Final TLB}
\end{center}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
Set & Way & Tag & PPN & Valid & Dirty & LRU \\
\hline
0 & 0 & & & & & \\
0 & 1 & & & & & \\
\hline
1 & 0 & & & & & \\
1 & 1 & & & & & \\
\hline
2 & 0 & & & & & \\
2 & 1 & & & & & \\
\hline
3 & 0 & & & & & \\
3 & 1 & & & & & \\
\hline
\end{tabular}
\end{center}


\newpage

\scoreline{20}{3. Page Table Walk [20 points]}

Suppose there is a virtual memory system with \textbf{64KB pages} which has a \textbf{2-level hierarchical page table}. The physical address of the base of the level 1 page table (\textbf{0x02000}) is stored in the \textbf{Page Table Base Register}. The system uses \textbf{20-bit virtual addresses} and \textbf{20-bit physical addresses}. Figure~1 summarizes the page table structure in this system.

\twolvlpagetablefigure

The size of both level 1 and level 2 page table entries is \textbf{4 bytes} and the memory is \textbf{byte-addressed}. Assume that all pages and all page tables are loaded in the main memory. The breakdown of a virtual address is:

\begin{center}
\setlength{\tabcolsep}{0pt}
\renewcommand{\arraystretch}{1.0}

\begin{tabular}{@{}c@{}c@{}c@{}}
\makebox[3.4cm][c]{19 \hfill 18} &
\makebox[3.4cm][c]{17 \hfill 16} &
\makebox[4.6cm][c]{15 \hfill 0}
\end{tabular}

\vspace{-0.08cm}

\begin{tabular}{|>{\centering\arraybackslash}m{3.4cm}|>{\centering\arraybackslash}m{3.4cm}|>{\centering\arraybackslash}m{4.6cm}|}
\hline
L1 Index (p1) & L2 Index (p2) & Page Offset \\
\hline
\end{tabular}
\end{center}

Each entry of the level 1 page table contains the \textbf{physical address} of the base of each level 2 page tables, and each entry of the level 2 page table entries contains the \textbf{PTE} of the data page. As described in Figure~1, L1 index and L2 index are used as indices to locate the corresponding \textbf{4-byte entry} in the level 1 and level 2 page tables.


\newcommand{\pteformatfigure}{
\begin{center}
\begin{tikzpicture}[x=1cm,y=1cm,baseline=(current bounding box.center)]
    % height
    \def\H{0.6}

    % widths of the three fields
    % [31:20] , [19:16] , [15:0]
    \def\Wzero{6.2}
    \def\Wppn{5.1}
    \def\Wstat{2.9}

    % x coordinates
    \coordinate (x0) at (0,0);
    \coordinate (x1) at (\Wzero,0);
    \coordinate (x2) at ({\Wzero+\Wppn},0);
    \coordinate (x3) at ({\Wzero+\Wppn+\Wstat},0);

    % outer box
    \draw (x0) rectangle ($(x3)+(0,\H)$);
    \draw (x1) -- ($(x1)+(0,\H)$);
    \draw (x2) -- ($(x2)+(0,\H)$);

    % top bit labels
    \node[anchor=south] at ($(x0)+(0,\H)$) {31};

    % separate 20 and 19
    \node[anchor=south east] at ($(x1)+(0,\H)$) {20};
    \node[anchor=south west] at ($(x1)+(0,\H)$) {19};

    % separate 16 and 15
    \node[anchor=south east] at ($(x2)+(0,\H)$) {16};
    \node[anchor=south west] at ($(x2)+(0,\H)$) {15};

    \node[anchor=south] at ($(x3)+(0,\H)$) {0};

    % texts inside boxes

    \node at ($(x0)!0.5!(x1)+(0,\H/2)$) {0};
\node[font=\small] at ($(x1)!0.5!(x2)+(0,\H/2)$) {Physical Page Number (PPN)};
\node[font=\small] at ($(x2)!0.5!(x3)+(0,\H/2)$) {Status Bits};
\end{tikzpicture}
\end{center}
}

A PTE in level 2 page tables can be broken into the following fields (do not worry about status bits for the entire problem):

\pteformatfigure


\scoreline{8}{(a) Part A [8 points]}

Assuming the initial TLB and memory states are in \textbf{Table 4} and \textbf{Table 6}, respectively, what will be the final TLB state after accessing the virtual address given below? Please fill out the table with the final TLB state in \textbf{Table 5}. You only need to write \textbf{VPN} and \textbf{PPN} fields of the TLB. The TLB has \textbf{4 slots} and is \textbf{fully associative}, and if there are empty lines they are taken first for new entries. Also, translate the virtual address (\textbf{VA}) to the physical address (\textbf{PA}).

\begin{minipage}[t]{0.43\textwidth}
\begin{center}
\textbf{Table 4: Initial TLB State}
\end{center}
\begin{center}
\begin{tabular}{|c|c|}
\hline
VPN & PPN \\
\hline
0x4 & 0x2 \\
-- & -- \\
-- & -- \\
-- & -- \\
\hline
\end{tabular}
\end{center}

\vspace{1em}

\begin{center}
\textbf{Table 5: Final TLB State}
\end{center}
\begin{center}
\begin{tabular}{|c|c|}
\hline
VPN & PPN \\
\hline
0x4 & 0x2 \\
 & \\
 & \\
 & \\
\hline
\end{tabular}
\end{center}

\vspace{1em}

\[
\text{VA: } 0x5689A \longrightarrow \text{PA: } \underline{\hspace{4.2cm}}
\]
\end{minipage}
\hfill
\begin{minipage}[t]{0.50\textwidth}
\begin{center}
\textbf{Table 6: Initial Memory State}
\end{center}
\begin{center}
\begin{tabular}{|c|c|}
\hline
Address (PA) & Content \\
\hline
0x0200C & 0x34000 \\
0x02008 & 0x2C000 \\
0x02004 & 0x2A000 \\
0x02000 & 0x28000 \\
\hline
0x2A00C & 0x450AA \\
0x2A008 & 0x53011 \\
0x2A004 & 0x4E022 \\
0x2A000 & 0x39004 \\
\hline
\end{tabular}
\end{center}
\end{minipage}

\vspace{1em}

Show the key intermediate steps:
\begin{itemize}[leftmargin=1.8em,itemsep=1pt,topsep=2pt]
    \item p1 = \sblank \qquad p2 = \sblank \qquad offset = \blank
    \item L1 entry address = \blank \qquad L1 entry content = \blank
    \item L2 entry address = \blank \qquad L2 entry content = \blank
    \item TLB hit or miss: \blank
\end{itemize}


\scoreline{12}{(b) Part B [12 points]}

To reduce the amount of physical memory required to store the page table, the designer decides to only put the level 1 page table in physical memory and use the \textbf{virtual memory} to store level 2 page tables. Now, each entry of the level 1 page table contains the \textbf{virtual address} of the base of a level 2 page table, and each entry of the level 2 page table contains the PTE of the data page. Other system specifications remain the same. (The size of both level 1 and level 2 page table entries is 4 bytes.)

Assuming the initial TLB and memory states are in \textbf{Table 7} and \textbf{Table 9}, respectively, what will be the final TLB state after accessing the virtual address given below? Please fill out the table with the final TLB state in \textbf{Table 8}. You only need to write \textbf{VPN} and \textbf{PPN} fields of the TLB. The TLB has \textbf{4 slots} and is \textbf{fully associative}, and if there are empty lines they are taken first for new entries. Also, translate the virtual address to the physical address.

\begin{minipage}[t]{0.43\textwidth}
\begin{center}
\textbf{Table 7: Initial TLB State}
\end{center}
\begin{center}
\begin{tabular}{|c|c|}
\hline
VPN & PPN \\
\hline
0x8 & 0x1 \\
-- & -- \\
-- & -- \\
-- & -- \\
\hline
\end{tabular}
\end{center}

\vspace{1em}

\begin{center}
\textbf{Table 8: Final TLB State}
\end{center}
\begin{center}
\begin{tabular}{|c|c|}
\hline
VPN & PPN \\
\hline
0x8 & 0x1 \\
 & \\
 & \\
 & \\
\hline
\end{tabular}
\end{center}

\vspace{1em}

\[
\text{VA: } 0x9D234 \longrightarrow \text{PA: } \underline{\hspace{4.2cm}}
\]
\end{minipage}
\hfill
\begin{minipage}[t]{0.50\textwidth}
\begin{center}
\textbf{Table 9: Initial Memory State}
\end{center}
\begin{center}
\begin{tabular}{|c|c|}
\hline
Address (PA) & Content \\
\hline
0x0200C & 0x00000 \\
0x02008 & 0x84010 \\
0x02004 & 0x90008 \\
0x02000 & 0x88020 \\
\hline
0x1401C & 0x00000 \\
0x14018 & 0x5C012 \\
0x14014 & 0x3D055 \\
0x14010 & 0x43001 \\
\hline
\end{tabular}
\end{center}
\end{minipage}

\vspace{1em}

Show the key intermediate steps:
\begin{itemize}[leftmargin=1.8em,itemsep=1pt,topsep=2pt]
    \item p1 = \sblank \qquad p2 = \sblank \qquad offset = \blank
    \item L1 entry address = \blank \qquad L1 entry content = \blank
    \item Virtual address of L2 table base = \blank
    \item Physical address of translated L2 table base = \blank
    \item Address of the L2 PTE of VA = \blank \qquad L2 entry content = \blank
\end{itemize}



\newpage

\scoreline{25}{4. End-to-End Address Translation and Cache Access [25 points]}

A small memory system has the following parameters:
\begin{itemize}[leftmargin=1.8em,itemsep=1pt,topsep=2pt]
    \item Memory is \textbf{byte-addressable}
    \item Virtual addresses are \textbf{14 bits}
    \item Physical addresses are \textbf{12 bits}
    \item Page size is \textbf{64 bytes}
    \item The TLB is \textbf{4-way set associative} with a total of \textbf{16 entries}
    \item Assume the system uses a single \textbf{unified instruction/data TLB} for this problem; only the address translations for the listed virtual addresses need to be considered.
    \item The L1 data cache is \textbf{physically addressed} and \textbf{direct-mapped}
    \item Cache block size is \textbf{4 bytes}
    \item The cache has \textbf{16 sets}
\end{itemize}

\textbf{Abbreviation notes:}
\begin{itemize}[leftmargin=1.8em,itemsep=1pt,topsep=2pt]
    \item \textbf{VA}: virtual address
    \item \textbf{PA}: physical address
    \item \textbf{VPN}: virtual page number
    \item \textbf{VPO}: virtual page offset
    \item \textbf{PPN}: physical page number
    \item \textbf{PPO}: physical page offset
    \item \textbf{TLB}: translation lookaside buffer
    \item \textbf{TLBI}: TLB index
    \item \textbf{TLBT}: TLB tag
    \item \textbf{PTE}: page table entry
    \item \textbf{CT}: cache tag
    \item \textbf{CI}: cache index
    \item \textbf{CO}: cache block offset
    \item \textbf{V}: valid bit
\end{itemize}

The current TLB state, page table contents, and L1 d-cache state are given below.

\begin{center}
\textbf{TLB State}
\end{center}
\begin{center}
\begin{tabular}{|c||c|c|c||c|c|c||c|c|c||c|c|c|}
\hline
Set Index & Tag & PPN & Valid & Tag & PPN & Valid & Tag & PPN & Valid & Tag & PPN & Valid \\
\hline
0 & 03 & -- & 0 & 09 & 0D & 1 & 00 & -- & 0 & 07 & 02 & 1 \\
\hline
1 & 03 & 2D & 1 & 02 & -- & 0 & 04 & -- & 0 & 0A & -- & 0 \\
\hline
2 & 02 & -- & 0 & 08 & -- & 0 & 06 & -- & 0 & 03 & -- & 0 \\
\hline
3 & 07 & -- & 0 & 03 & 0D & 1 & 0A & 34 & 1 & 02 & -- & 0 \\
\hline
\end{tabular}
\end{center}

\newpage

\begin{center}
\textbf{Page Table (only first 16 PTEs shown)}
\end{center}
\begin{center}
\begin{tabular}{|c|c|c||c|c|c|}
\hline
VPN & PPN & Valid & VPN & PPN & Valid \\
\hline
00 & 28 & 1 & 08 & 13 & 1 \\
01 & -- & 0 & 09 & 17 & 1 \\
02 & 33 & 1 & 0A & 09 & 1 \\
03 & 02 & 1 & 0B & -- & 0 \\
04 & -- & 0 & 0C & -- & 0 \\
05 & 16 & 1 & 0D & 2D & 1 \\
06 & -- & 0 & 0E & 11 & 1 \\
07 & -- & 0 & 0F & 0D & 1 \\
\hline
\end{tabular}
\end{center}

\begin{center}
\textbf{L1 d-cache State}
\end{center}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
Index & CT & V & Byte 0 & Byte 1 & Byte 2 & Byte 3 \\
\hline
0 & 19 & 1 & 99 & 11 & 23 & 11 \\
1 & 15 & 0 & -- & -- & -- & -- \\
2 & 1B & 1 & 00 & 02 & 04 & 08 \\
3 & 36 & 0 & -- & -- & -- & -- \\
4 & 32 & 1 & 43 & 6D & 8F & 09 \\
5 & 0D & 1 & 36 & 72 & F0 & 1D \\
6 & 31 & 0 & -- & -- & -- & -- \\
7 & 16 & 1 & 11 & C2 & DF & 03 \\
8 & 24 & 1 & 3A & 00 & 51 & 89 \\
9 & 2D & 0 & -- & -- & -- & -- \\
A & 2D & 1 & 93 & 15 & DA & 3B \\
B & 0B & 0 & -- & -- & -- & -- \\
C & 12 & 0 & -- & -- & -- & -- \\
D & 16 & 1 & 04 & 96 & 34 & 15 \\
E & 13 & 1 & 83 & 77 & 1B & D3 \\
F & 14 & 0 & -- & -- & -- & -- \\
\hline
\end{tabular}
\end{center}

For each of the following virtual addresses, explain how the system translates the virtual address to a physical address and accesses the cache. Indicate whether a TLB hit occurs, whether a page fault occurs, whether a cache hit occurs, and the returned cache byte.

If a \textbf{cache miss} occurs, write \textbf{--} in the ``Returned cache byte'' field.  
If a \textbf{page fault} occurs, write \textbf{--} in the ``PPN'' field and leave Part C and Part D blank.

\scoreline{9}{(a) Virtual Address 0x03D7}

\textbf{A. Virtual Address Format}

Fill in the virtual-address fields \textbf{VPN} and \textbf{VPO}.

\begin{center}
\begin{tabular}{|p{6cm}|p{7cm}|}
\hline
Parameter & Value \\
\hline
VPN & \\
VPO & \\
\hline
\end{tabular}
\end{center}

\textbf{B. Address Translation}

Fill in the translation-related fields: \textbf{TLBI}, \textbf{TLBT}, whether a \textbf{TLB hit} occurs, whether a \textbf{page fault} occurs, and the resulting \textbf{PPN}.

\begin{center}
\begin{tabular}{|p{6cm}|p{7cm}|}
\hline
Parameter & Value \\
\hline
TLBI & \\
TLBT & \\
TLB hit? (Y/N) & \\
Page fault? (Y/N) & \\
PPN & \\
\hline
\end{tabular}
\end{center}

\textbf{C. Physical Address Format}

Fill in the \textbf{12-bit physical address (PA)} in the diagram below using \textbf{PPN $\parallel$ PPO}. Do \textbf{not} fill cache tag/index/offset in this part.

\blankphysicaladdressdiagram

\textbf{D. Physical Memory Reference}

Using the physical address from Part C, fill in the cache-access fields: \textbf{byte offset}, \textbf{cache index}, \textbf{cache tag}, whether a \textbf{cache hit} occurs, and the \textbf{returned cache byte}.

\begin{center}
\begin{tabular}{|p{6cm}|p{7cm}|}
\hline
Parameter & Value \\
\hline
Byte offset & \\
Cache index & \\
Cache tag & \\
Cache hit? (Y/N) & \\
Returned cache byte & \\
\hline
\end{tabular}
\end{center}


\scoreline{9}{(b) Virtual Address 0x027C}

\textbf{A. Virtual Address Format}

Fill in the virtual-address fields \textbf{VPN} and \textbf{VPO}.

\begin{center}
\begin{tabular}{|p{6cm}|p{7cm}|}
\hline
Parameter & Value \\
\hline
VPN & \\
VPO & \\
\hline
\end{tabular}
\end{center}

\textbf{B. Address Translation}

Fill in the translation-related fields: \textbf{TLBI}, \textbf{TLBT}, whether a \textbf{TLB hit} occurs, whether a \textbf{page fault} occurs, and the resulting \textbf{PPN}.

\begin{center}
\begin{tabular}{|p{6cm}|p{7cm}|}
\hline
Parameter & Value \\
\hline
TLBI & \\
TLBT & \\
TLB hit? (Y/N) & \\
Page fault? (Y/N) & \\
PPN & \\
\hline
\end{tabular}
\end{center}

\textbf{C. Physical Address Format}

Fill in the \textbf{12-bit physical address (PA)} in the diagram below using \textbf{PPN $\parallel$ PPO}. Do \textbf{not} fill cache tag/index/offset in this part.

\blankphysicaladdressdiagram

\textbf{D. Physical Memory Reference}

Using the physical address from Part C, fill in the cache-access fields: \textbf{byte offset}, \textbf{cache index}, \textbf{cache tag}, whether a \textbf{cache hit} occurs, and the \textbf{returned cache byte}.

\begin{center}
\begin{tabular}{|p{6cm}|p{7cm}|}
\hline
Parameter & Value \\
\hline
Byte offset & \\
Cache index & \\
Cache tag & \\
Cache hit? (Y/N) & \\
Returned cache byte & \\
\hline
\end{tabular}
\end{center}


\scoreline{7}{(c) Virtual Address 0x0109}

\textbf{A. Virtual Address Format}

Fill in the virtual-address fields \textbf{VPN} and \textbf{VPO}.

\begin{center}
\begin{tabular}{|p{6cm}|p{7cm}|}
\hline
Parameter & Value \\
\hline
VPN & \\
VPO & \\
\hline
\end{tabular}
\end{center}

\textbf{B. Address Translation}

Fill in the translation-related fields: \textbf{TLBI}, \textbf{TLBT}, whether a \textbf{TLB hit} occurs, whether a \textbf{page fault} occurs, and the resulting \textbf{PPN}.

\begin{center}
\begin{tabular}{|p{6cm}|p{7cm}|}
\hline
Parameter & Value \\
\hline
TLBI & \\
TLBT & \\
TLB hit? (Y/N) & \\
Page fault? (Y/N) & \\
PPN & \\
\hline
\end{tabular}
\end{center}

\textbf{C. Physical Address Format}

Fill in the \textbf{12-bit physical address (PA)} in the diagram below using \textbf{PPN $\parallel$ PPO}. If a page fault occurs, leave this part blank.

\blankphysicaladdressdiagram

\textbf{D. Physical Memory Reference}

Using the physical address from Part C, fill in the cache-access fields: \textbf{byte offset}, \textbf{cache index}, \textbf{cache tag}, whether a \textbf{cache hit} occurs, and the \textbf{returned cache byte}. If a page fault occurs, leave this part blank.

\begin{center}
\begin{tabular}{|p{6cm}|p{7cm}|}
\hline
Parameter & Value \\
\hline
Byte offset & \\
Cache index & \\
Cache tag & \\
Cache hit? (Y/N) & \\
Returned cache byte & \\
\hline
\end{tabular}
\end{center}


\newpage

\scoreline{25}{5. Page Faults Under Demand Paging [25 points]}

A system uses \textbf{demand paging} with \textbf{byte-addressable memory}. Virtual addresses are \textbf{32 bits}. The page size is \textbf{1KB}. The size of an \texttt{int} is \textbf{4 bytes}. Two-dimensional arrays are stored in \textbf{row-major order}.

At the beginning of execution, all pages containing the arrays below are \textbf{not present in main memory}. Ignore code pages, stack pages, and page-table pages. Only consider the data pages of the arrays. The process is allocated exactly \textbf{2 physical page frames}, and the system uses \textbf{LRU page replacement}. Assume the TLB is large enough, so \textbf{TLB misses can be ignored}.

The arrays start at the following \textbf{page-aligned} virtual addresses:
\begin{itemize}[leftmargin=1.8em,itemsep=1pt,topsep=2pt]
    \item \texttt{A[32][32]} starts at \texttt{0x001800}
    \item \texttt{B[32][32]} starts at \texttt{0x005000}
\end{itemize}

Consider the following program:

\begin{lstlisting}
int A[32][32];
int B[32][32];
int sum = 0;

for (int j = 0; j < 32; j++) {
    for (int i = 0; i < 32; i++) {
        A[i][j] = A[i][j] + 1;
        sum += B[i][j];
    }
}
\end{lstlisting}

\scoreline{4}{(a)}
How many pages does \texttt{A} occupy? How many pages does \texttt{B} occupy?

\vspace{0.4em}
\[
\texttt{A occupies: } \underline{\hspace{2cm}}
\qquad
\texttt{B occupies: } \underline{\hspace{2cm}}
\]



\scoreline{9}{(b)}
How many \textbf{total page faults} occur during the entire execution of the program?

\[
\text{Total page faults: } \underline{\hspace{3cm}}
\]


\scoreline{8}{(c)}
Now suppose the loops are exchanged as follows, while all other conditions remain unchanged:

\begin{lstlisting}
for (int i = 0; i < 32; i++) {
    for (int j = 0; j < 32; j++) {
        A[i][j] = A[i][j] + 1;
        sum += B[i][j];
    }
}
\end{lstlisting}

How many \textbf{total page faults} occur now?

\[
\text{Total page faults after loop interchange: } \underline{\hspace{3cm}}
\]


\scoreline{4}{(d)}
Briefly explain why the results of (b) and (c) are very different.

\vspace{4em}
\underline{\hspace{15cm}}

\vspace{2em}
\underline{\hspace{15cm}}

\end{document}
