\documentclass[11pt]{article}

\def\choice#1{\left\{ \begin{array}{ll} #1 \end{array} \right.}
\def\AND{\mbox{ and }}
\def\OR{\mbox{ or }}
\def\NOT{\mbox{ not }}
\def\IF{\mbox{\it if }}
\def\WHERE{\mbox{\it where }}



\title{6.823 Problem Set 4}
\author{Chris Laas}
\date{April 10, 2000}

\pagestyle{myheadings}
\markright{Chris Laas \hfil 6.823 \hfil 4/10/2000}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii}}

\begin{document}
\maketitle

\section*{Problem 4-1}
\begin{enumerate}

\item%(a)

If a page is not in the TLB, it will raise a miss exception, on either
a load or a store.

If the valid bit is not set, then the TLB will raise a page-not-valid
fault, on either a load or a store.

If the resident bit is not set, then the TLB will raise a
page-not-resident fault, on either a load or a store.

If the CPU supervisor bit is not set and the TLB entry's supervisor
bit is set, then the TLB will raise a priviledge-level protection
violation, on either a load or a store.

If the writable bit is not set, then the TLB will raise a
write-protection violation on a store.

A single memory reference might raise a TLB miss exception; then,
after the entry is loaded, the restarted reference could raise any
other exception.

Or, a reference might raise a page-not-resident fault; then after the
page is loaded into memory, a protection violation could be raised.


\item%(b)

\begin{eqnarray*}
GoodTLBHit & \gets & TLBEntryValid \AND (MemVPN = TLBTag) \\
           &       & \AND V \AND R \\
           &       & \AND (CPUSupervisorBit \OR \NOT S) \AND (MemRead \OR W)
\end{eqnarray*}


\item%(c)

The TLB Entry Valid bit clearly doesn't need to be written back, since
it is only relevent to the structure of the TLB and not to the page
table.

The V, R, W, and S bits need to be written back if they have been
changed since they were loaded, because they all give memory
protection information that needs to be preserved.

The U and M bits must be written back if changed, because the swapping
subsystem needs to keep this information around to decide how swap
pages out and whether to write pages back.



\item%(d)

This would mean that, on a TLB flush, all entries in the TLB would
have to be made valid by loading page table entries.  This would have
the advantage of decreasing the TLB memory requirements and of
decreasing the TLB hardware complexity; however, the disadvantage
would be a significant degradation of context switching performance.


\item%(e)

The kernel software needs to be changed to deal with refills and
invalidates as described.  In addition, the TLB miss and
page-not-valid exception handlers must be combined (because there will
only be one exception) and the kernel must distinguish between the two
cases by examining the TLB.


\item%(f)

Now, the page-not-valid TLB fault disappears; whenever an invalid
address is accessed, a TLB miss is generated, and the kernel reads the
page table from memory, discovers that the address is invalid, and
generates a page-not-valid fault.  The kernel must also change not to
cache nonvalid page table entries (so that an invalid page table entry
is never loaded into the TLB).


\item%(g)

While Alyssa's scheme will perform better if a program accesses a lot
of invalid pages, most programs try not to use invalid-page-faults as
a normal operating construct.  Thus, on normal programs, the scheme in
F will perform better, since more valid PTEs will be stored in the
TLB, and the kernel will not modify the TLB on invalid page references.


\item%(h)

If the R bit is removed from the TLB, then the kernel must ensure that
the pages for all PTEs in the TLB are resident.  Since an access to a
non-resident page will initiate a disk access, and disk access time is
much greater than memory access time, there will be very little
performance impact from removing the R bit.


\item%(i)

The kernel will have to temporarily remove the protected pages from
the page table whenever it enters user space.  This is not too hard;
however, when program flow enters kernel space from user space, the
page table entries must be re-inserted into the memory map, which will
be an inefficient copy operation.  (With clever partitioning of the
address space, it could be reduced to a single pointer copy.)

Alternatively, the valid or resident bits of the protected pages could
be set to zero in user space; however, this could lead to significant
other problems with the kernel code, depending on how it treated
invalid PTEs.


\item%(j)

At the first store, a protection fault will be raised: the kernel
first loads the PTE from the page table, and if the W bit there is
set, it will set the U and M bits in the page table, and will set the
W bit in the TLB.  Any successive stores will proceed as normal.  When
the swap daemon walks the page table and unsets the U bits, the TLB
entries should be reloaded and the W bits set to zero.  When the
entries are replaced, they should be written back to memory, although
the value of the W bit should not be written back.


\end{enumerate}
\newpage






\section*{Problem 4-2}
\begin{enumerate}

\item%(a)

A program might write two different values to the different virtual
addresses, and the values could both be cached separately; however,
the second write should have overwritten the first.  Thus, the wrong
result could be obtained if a read to the first address was serviced
by the cache.

This example code clarifies the problem:

\begin{verbatim}
  SW R1, A
  SW R2, B
  LW R1, A
  LW R2, B
\end{verbatim}

If A and B are different virtual addresses which map to the same
physical address, then at the end both R1 and R2 should have the value
initially in R2.  However, if a virtual-index virtual-tag cache stores
the values for A and B separately, the final value for R1 will
incorrectly be equal to the initial value of R1.


\item%(b)

Using a write-through cache will not fix the problem, because (in the
example above) the cache system does not know to reread A from memory
instead of loading it from the cache.


\item%(c)

In the most general case, changing the cache to be direct-mapped won't
fix the problem.  However, in the fairly common case in which the
number of cache offset bits (log size of the cache) is less than the
page offset bits (log pagesize), the problem is avoided: addresses can
only be synonyms if they are the same page offset in different pages.
If the cache size is smaller than the page size, then different
virtual addresses with the same page offset will be mapped to the same
cache slot, and thus two synonyms cannot be in the cache at the same time.


\item%(d)

No, using a virtual-index, physical-tag cache avoids the synonym
problem: any two synonyms A and B will have the same page offset, and
will have different VPNs but will have the same PPN.  Thus, they will
both be stored in the same slot of the cache.


\item%(e)

If the address space identifier of the current process is added to the
tag information of every cache line, then {\em effectively} all
processes will really be in different address spaces, eliminating the
homonym problem.  It will have no effect on the synonym problem,
however.


\item%(f)

Yes:  in a virtual-index, physical-tag cache, the PPN, and hence tag,
of that same virtual address is different in the two processes; thus,
the cache will not return a false hit when the address is accessed
from a different process, and the problem is avoided.


\item%(g)

Yes:  a physically-indexed, physically-tagged cannot have synonym or
homonym problems, because each slot of the cache maps to at most one
memory location, and each memory location maps to at most one cache
slot.  The primary drawback is that the cache lookup must be performed
after address translation, whereas in a virtual-index virtual-tag
cache, the lookup can be performed in parallel with translation.  In
computers with complex memory systems, the additional latency of the
address translation can be crippling.


\end{enumerate}
\newpage









\section*{Problem 4-3}

I answered this before the correction came out.

\begin{enumerate}

\item%(a)

In addition to the RAW and WAW hazards present in in-order issue,
out-of-order issues also has WAR (write-after-read) hazards, which can
come about due to code segments like the following:

\begin{verbatim}
  MULTF F1, F2, F3
  DIVF F4, F1, F5
  ADDF F5, F6, F7
\end{verbatim}

In this case, if the ADDF were issued and completed before the DIVF
was issued (in this case due to the RAW hazard with the MULTF), then
the DIVF would read an incorrect value of F5.


\item%(b)

The RO vector will be used to avoid WAR hazards:  if the bit for the
destination register of the instruction in the decode stage is set,
that instruction will be stalled instead of issued (because there is a
WAR hazard with an already-stalled instruction).


\item%(c)

$STALL = Busy[Mult] \OR WP[Rs1] \OR WP[Rs2] \OR WP[Rd] \OR RP[Rd]$


\item%(d)

No; this would allow WAW hazards.  (Anyway, this would be explicitly
disallowed by the $WP[Rd]$ term above, so the question is rather
meaningless.)  For example, a sequence of the form

\begin{verbatim}
  DIVF F1, F2, F3
  ADDF F1, F4, F5
\end{verbatim}

could produce an incorrect result in R1 if the latency for DIVF was
greater than that for ADDF.

Note that such hazards would be rather rare, because in the above
example the result of the DIVF is thrown away without being used.  In
any code sequence in which the result of the first writer is used
before the second writer (i.e. in normal code), the RP vector would
stall the second writer appropriately.  So, in practice, we might not
notice the brokenness unless we wrote code segments specifically to
foul it up.


\item%(e)

This scheme is certainly simpler to implement and more efficient in
terms of tag lookups than a ROB/register renaming scheme.  The
downside is that, instead of dealing with WAR and WAW hazards by
renaming registers and issuing the instructions, this scheme simply
stalls the instructions, possibly wasting precious cycles that could
have been used on computation.


\end{enumerate}
\newpage









\section*{Problem 4-4}
\begin{enumerate}

\def\u#1{\underline{#1}}

\item%(a)

I assume that the memory and floating-point units are fully internally
pipelined, so that, for example, another load can be initiated in the
second cycle of the first load.

In that case, the instructions are issued and \u{retired} in the following
order:

1 2 \u{1} \u{2} 3 4 5 (\u{3},\u{4}) \u{5} 6 . . \u{6} 7 . . \u{7} 8

The total number of cycles between the issue of the
first load instruction and the issue of the final store is
17 cycles.


\item%(b)

\begin{verbatim}
1:  LF F0, A
2:  LF F1, B
3:  LF F2, C
4:  LF F3, D
5:  MULTF F0, F0, F1
6:  MULTF F2, F2, F3
7:  ADDF F0, F0, F2
8:  SF F0, E
\end{verbatim}

The issue/retire order is:

1 2 (3,\u{1}) (4,\u{2}) (5,\u{3}) \u{4} . (6,\u{5}) . . 7 . . \u{7} 8

The total number of cycles is 14 cycles.


\item%(c)

\begin{verbatim}
1:  LF F0, A
2:  LF F1, B
3:  MULTF F0, F0, F1
4:  SF F0, E
5:  LF F1, C
6:  LF F0, D
7:  MULTF F0, F0, F1
8:  LF F1, E
9:  ADDF F0, F0, F1
10: SF F0, E
\end{verbatim}

In the simple single-issue in-order machine, this has the order:

1 2 \u{1} \u{2} 3 . . \u{3} 4 5 (6,\u{4}) \u{5} \u{6} 7 8 . (\u{7},\u{8}) 9 . . \u{9} 10

This uses 21 cycles.


\item%(d)

After the effects of register renaming, the code looks like this:

\begin{verbatim}
1:  LF F0, A
2:  LF F1, B
3:  MULTF F2, F0, F1
4:  SF F2, E
5:  LF F3, C
6:  LF F4, D
7:  MULTF F5, F4, F3
8:  LF F6, E
9:  ADDF F7, F5, F6
10: SF F7, E
\end{verbatim}

The instructions are issued and \u{retired} in the following
order:

1 2 \u{1} \u{2} 3 5 6 (\u{3},\u{5}) (4,\u{6}) 7 \u{4} 8 \u{7} \u{8} 9 . . \u{9}

This gives a total of 18 cycles between the issue of instruction 1 and
the issue of instruction 10.  This is closer to the unoptimized code
runtime of part A; probably a lot of the slowdown comes from the
register spilling.


\end{enumerate}
\newpage











\section*{Problem 4-5}
\begin{enumerate}

\item%(a)

At the end of the program segment, R2 contains a count of the number
of elements in the array equal to zero.


\item%(b)

(See table.)  The number of mispredicts is 7 (out of a total of 16
conditional branches).


\item%(c)

(See table.)  The number of mispredicts is 8.


\item%(d)

(See table.)  The number of mispredicts is 7.


\item%(e)

For example B, there are three mispredicts at the beginning, one every
four conditional branches periodically, and one more at the end.

For example C, there are four mispredicts at the beginning, one every
four conditional branches periodically, and one more at the end.

For example D, there are five mispredicts at the beginning, no
periodic mispredicts, and one at the end.

In general, global history bits cause the predictor to take a little
longer to settle into a steady state, but can help to reduce the
mispredicts by providing context in a tight loop.  Hence, for large N,
more history bits will work best; in the example in part D, there are
no periodic mispredicts in the steady state.


\item%(f)

Well, the presence or absence of history bits and the randomness of
the input don't affect the predictor's steady-state performance on
branch B2; however, adding history bits will cause the BP bits for B2
to take longer to reach the steady state.

If the input is random, then the result of the previous B1 has no
relation with the result of the current B1; thus, adding history bits
will never improve the predictions of the result of B1.  (In fact,
nothing at all can improve the prediction, because the branch result
is entirely random.)

Thus, in conclusion, adding history bits will always decrease
performance (by a few more mispredicts of B2 at the beginning) if the
result of branch B1 is random.  In general, we can say that history
bits help when the pattern of branches is very regular, but hurt when
it is completely random.


\end{enumerate}
\newpage



\end{document}



