807 lines
No EOL
39 KiB
TeX
807 lines
No EOL
39 KiB
TeX
|
|
\chapter{Speicher in Computern} \index{Speicher}
|
|
|
|
\section{Speicherhierarchie}
|
|
\autoref{tbl:speicherhierarchie} zeigt die Speicherhierarchie in modernen Universalrechnern
|
|
|
|
\begin{table}[ht]
|
|
\centering
|
|
\begin{tabular}{p{29mm}|p{36mm}|p{19mm}|p{34mm}|p{23mm}}
|
|
\textbf{Speicher} & \textbf{von-Neumann-Rechner} & \textbf{Persistenz} & \textbf{Größe} & \textbf{Zugriffszeit} \\ \midrule
|
|
\acs{CPU}-Register & Zentraleinheit (Rechen- und Steuerwerk) & flüchtig & $<1kB$ Byte & $\approx$ 200ps \\ \midrule
|
|
Cache \newline (\enquote{CPU-Cache}) & nicht vorhanden & flüchtig & \circa{4}MB \newline L1 $\approx$ 64KB \newline L2 $\approx$ 512KB & $\approx$ 10ns \\ \midrule
|
|
Hauptspeicher/ Primärspeicher & Speicherwerk & flüchtig & \circa{8}GB & $\approx$ 100ns \newline L1 schneller \\ \midrule
|
|
Sekundärspeicher & Peripheriegeräte an Ein- und Ausgabewerk & nicht flüchtig & HDD: 3T \newline SSD: 512GB \newline opt.~\acs{LW}: bis~100GB \newline \acs{BLW}: wenige TB & HDD~$\approx10ms$ \newline SSD~$\approx 10\mu s$\newline opt.~\acs{LW}~$\approx 1s$ \newline \acs{BLW}~$\approx 1min$
|
|
\end{tabular}
|
|
\caption{Speicherhierarchie und -Daten}
|
|
\label{tbl:speicherhierarchie}
|
|
\end{table}
|
|
|
|
\section{Sekundärspeicher}
|
|
Motivation für Sekundärspeicher: nicht-flüchtig, \dash der Speicherinhalt bleibt auch bei Stromausfall erhalten.
|
|
|
|
\textbf{Anwendungen:}
|
|
|
|
\begin{itemize}
|
|
\item Programmcode (Betriebsystem, Anwendungsprogramme)
|
|
\item Nutzdaten
|
|
\item virtuelle Erweiterung des Speicherwerks (Swap-Datei/-Partition)
|
|
\item Hibernation (\enquote{Ruhezustand})
|
|
\end{itemize}
|
|
|
|
\section{CPU-Cache}
|
|
|
|
Temporärer, flüchtiger, schneller Zwischenspeicher, um auf Informationen aus dem Hauptspeicher schneller zugreifen zu können.
|
|
|
|
\newpage % Für's Layout
|
|
|
|
Eigenschaften des Cache:
|
|
\begin{itemize}[noitemsep]
|
|
\item flüchtig
|
|
\item kleiner als das zu cachende Medium (Hauptspeicher)
|
|
\item schneller als das zu cachende Medium (Hauptspeicher)
|
|
\item transparent, \dash es wird nicht auf den Cache, sondern auf das zu cachende Medium logisch zugegriffen (die \acs{CPU} adressiert den Hauptspeicher und nicht den Cache)
|
|
\item konsistent, \dash alle Instanzen derselben \acf{HSA} haben denselben Wert
|
|
\item kohärent, \dash beim Zugriff auf eine \acs{HSA} wird immer der aktuelle Wert geliefert
|
|
\end{itemize}
|
|
|
|
\bigskip
|
|
\begin{Hinweis}[frametitle={Anmerkung: Kohärenz und Konsistenz}]
|
|
Kohärenz ist Pflicht und Konsistenz ist Wunsch, da aus Konsistenz Kohärenz folgt. Zeitweise kann aber auf Konsistenz verzichtet werden.
|
|
\end{Hinweis}
|
|
|
|
\subsection{Lokalität des Zugriffmusters} \index{Lokalität}
|
|
Verantwortlich dafür, dass der Cache Geschwindigkeitsvorteile bringen kann.
|
|
\begin{description}
|
|
\item[räumliche Lokalität] Wenn auf eine Adresse zugegriffen wird, wird auch auf naheliegende Adressen zugegriffen.
|
|
\item[zeitliche Lokalität] Die Zugriffe (auf nahe beieinanderliegende Adressen) erfolgen in relativ geringem zeitlichen Aufwand
|
|
\end{description}
|
|
\medskip
|
|
\begin{Hinweis}
|
|
Hinweis: Insbesondere die räumliche Lokalität ist beim Zugriff auf Programmcode und Nutzdaten sehr unterschiedlich (Programmcode: sequentiell, Nutzdaten zufällig innterhalb von Speicherblöcken).
|
|
|
|
$\Rightarrow$ Moderne \acsp{CPU} weisen getrennte Caches für Programmcode und Nutzdaten auf!
|
|
\end{Hinweis}
|
|
|
|
|
|
\subsection{Begriffe}
|
|
\begin{description}
|
|
\item[Hit]\index{Hit-Rate} Zugriff auf \acl{HS}-Daten, welcher aus dem Cache bedient werden kann
|
|
\item[Miss]\index{Miss-Rate} Zugriff auf \acl{HS}-Daten, welcher \textit{nicht} aus dem Cache bedient werden kann und deshalb der Cache die Daten erst aus dem \acl{HS} holen muss.
|
|
\item[Hit-Rate] Anteil der \enquote{erfolgreichen} Zugriffe an allen Zugriffen. \newline
|
|
Hit-Rate=$\frac{\text{\#Hits}}{\text{\#Zugriffe}}$
|
|
\item[Miss-Rate] Anteil der \enquote{nicht erfolgreichen} Zugriffe an allen Zugriffen. \newline
|
|
Miss-Rate=$\frac{\text{\#Misses}}{\text{\#Zugriffe}}$
|
|
\item[Zugriffe] Anzahl der Misses plus der Hits
|
|
\end{description}
|
|
|
|
\columnratio{0.5}
|
|
\begin{paracol}{2}
|
|
\begin{tabular}{@{}ll}
|
|
\textbf{Anwendung}: & $0\leq$ Hit-Rate $\leq 1$ \\
|
|
& $0\leq$ Miss-Rate $\leq 1$ \\
|
|
& Hit-Rate + Miss-Rate $= 1$
|
|
\end{tabular}
|
|
\switchcolumn
|
|
\begin{tabular}{ll}
|
|
\textbf{Ziel}: & Hit-Rate $\rightarrow 1$ (nicht realistisch) \\
|
|
& Miss-Rate $\rightarrow 0$ \\
|
|
& Hit-Rate $\rightarrow$ systembedingtes Maximum \\
|
|
& \qquad (realistisch)
|
|
\end{tabular}
|
|
\end{paracol}
|
|
|
|
Das systembedingte Maximum hängt ab von:
|
|
\begin{itemize}[noitemsep]
|
|
\item Lokalität des Zugriffsmusters
|
|
\item Größe (und Größenverhältnis) von Cache und \acl{HS}
|
|
\end{itemize}
|
|
|
|
Hinweis: $\text{Hit-Rate}_\text{erreicht} \geq \frac{\text{Größe (Cache)}}{\text{Größe HS}}$ (Wahrscheinlichkeit, das ein beliebiger Zugriff eine bereits im Cache gespeicherte Adresse betrifft)
|
|
|
|
$\Rightarrow$ sobald das Zugriffsmuster Lokalität aufweist, ergibt sich eine bessere Hit-Rate
|
|
|
|
|
|
\subsection{Betriebszustände des Cache}
|
|
\begin{description}
|
|
\item[kalter Cache]\index{Cache!kalter Cache} bei Betriebsbeginn ist der Cache leer
|
|
\item[sich erwärmender Cache]\index{Cache!erwärmender Cache} Während des Betriebs wird der Cache mit immer mehr Daten geladen und die Hit-Rate steigt.
|
|
\item[heißer Cache]\index{Cache!heißer Cache} Der Cache ist nach einer gewissen Betriebszeit (nahezu) voll. Die Hit-Rate erreicht das systembedingte Maximum.
|
|
\end{description}
|
|
|
|
\subsection{Cachearchitekturen}\index{Cache!Architektur}
|
|
\begin{figure}[!htb]
|
|
\medskip
|
|
\minipage{0.5\textwidth}
|
|
\begin{tikzpicture}
|
|
% CPU
|
|
\draw (-3, -0.5) rectangle ++(6,1);
|
|
\node at (0, 0) (SW) {Speicherwerk};
|
|
|
|
\draw (-2.5, 1.5) rectangle ++(5,1);
|
|
\node at (0, 2) (Ca) {CPU-Cache};
|
|
|
|
\draw (-2, 3.5) rectangle ++(4,1);
|
|
\node at (0, 4) (CPU) {Zentraleinheit (CPU)};
|
|
|
|
\draw ($(CPU)+(0,-0.5)$) -- ($(Ca)+(0,0.5)$) ($(Ca)+(0,-0.5)$) -- ($(SW)+(0,0.5)$);
|
|
\end{tikzpicture}
|
|
\caption{Look-Through-Cache}
|
|
\label{fig:cpu_cache_look_through}
|
|
\endminipage\hfill
|
|
\minipage{0.5\textwidth}
|
|
\begin{tikzpicture}
|
|
% CPU
|
|
\draw (-2.5, -0.5) rectangle ++(5,1);
|
|
\node at (0, 0) (SW) {Speicherwerk};
|
|
|
|
\draw (1.5, 1.5) rectangle ++(3,1);
|
|
\node at (3, 2) (Ca) {CPU-Cache};
|
|
|
|
\draw (-2, 3.5) rectangle ++(4,1);
|
|
\node at (0, 4) (CPU) {Zentraleinheit (CPU)};
|
|
|
|
\draw ($(CPU)+(0,-0.5)$) -- ($(SW)+(0,0.5)$);
|
|
\draw (0, 2) -- ($(Ca)+(-1.5,0)$);
|
|
\end{tikzpicture}
|
|
\caption{Look-Aside-Cache}
|
|
\label{fig:cpu_cache_look_aside}
|
|
\endminipage
|
|
\end{figure}
|
|
|
|
\columnratio{0.5}
|
|
\begin{paracol}{2}
|
|
\textsf{\textbf{Look-Through-Cache}}\index{Cache!Look-Through}
|
|
|
|
Wie in \autoref{fig:cpu_cache_look_through} zu sehen, ist die CPU nur mit dem Cache und der \acl{HS} ebenfalls nur mit dem Cache verbunden.
|
|
|
|
Die \acs{CPU} greift über den Cache auf den \acl{HS} zu:
|
|
|
|
\begin{itemize}[leftmargin=5mm]
|
|
\item[$\ominus$] $t_\text{Miss}=t_\text{Cache}+t_\text{HS}$ \newline
|
|
Zugriffszeit bei Miss größer als ohne Cache
|
|
\item[$\oplus$] optimale Konsistenz
|
|
\end{itemize}
|
|
|
|
\switchcolumn
|
|
\textsf{\textbf{Look-Aside-Cache}}\index{Cache!Look-Aside}
|
|
|
|
In \autoref{fig:cpu_cache_look_aside} sind \acs{CPU}, Cache und \acs{HS} über einen Bus miteinander verbunden. Die Anfrage durch die CPU geht auf dem Bus an beide und ggf. antworten beide, \dash die schnellere Antwort gewinnt.
|
|
|
|
\begin{itemize}[leftmargin=5mm]
|
|
\item[$\oplus$] $t_\text{Miss} > t_\text{HS}$ \newline
|
|
Zugriffszeit bei einem Miss genauso wie ohne Cache $\Rightarrow$ immer \enquote{beste} Zugriffszeit
|
|
\item[$\ominus$] Bus braucht Zugriffsprotokoll mit Overhead $\Rightarrow$ langsamer als 1:1 Verbindung
|
|
\item[$\ominus$] Konsistenz durch zweite Antwort potentiell gefährdet
|
|
\end{itemize}
|
|
\end{paracol}
|
|
|
|
\subsection{Schreibstrategie}
|
|
\columnratio{0.5}
|
|
\begin{paracol}{2}
|
|
\textsf{\textbf{Write-Back}}
|
|
|
|
Schreibzugriff durch die \acs{CPU} findet im Cache statt und der Cache aktualisiert die Daten bei nächster Gelegenheit im \acl{HS}.
|
|
\bigskip
|
|
\medskip
|
|
\begin{itemize}[leftmargin=5mm]
|
|
\item[$\ominus$] zeitwertige Inkonsistenz der Daten
|
|
\item[$\oplus$] Schreiben in Cache-Geschwindigkeit möglich
|
|
\end{itemize}
|
|
|
|
\switchcolumn
|
|
\textsf{\textbf{Write-Through}}
|
|
|
|
Schreibzugriff durch die \acs{CPU} findet im \acl{HS} statt. Parallel dazu müssen die Daten im Cache invalidiert (schlecht) oder ebenfalls geschrieben werden (gut).
|
|
\begin{itemize}[leftmargin=5mm]
|
|
\item[$\oplus$] optimale Konsistenz der Daten
|
|
\item[$\ominus$] Schreiben nur in \acs{HS}-Geschwindigkeit möglich
|
|
\end{itemize}
|
|
\end{paracol}
|
|
|
|
\hspace*{-5mm}
|
|
\begin{tabular}{p{32mm}|p{62mm}|p{62mm}}
|
|
\textbf{Schreibstrategie} \newline \newline \textbf{Cachearchitektur}
|
|
& \textbf{Write-Bac}k
|
|
& \textbf{Write-Through} \\
|
|
\midrule
|
|
|
|
\textbf{Look-Through}
|
|
& $\oplus$ gute klassische Kombination, da die physische Gegebenheit vorhanden ist, um direktes Schreiben in Cache und Rückschreiben vom Cache in \acs{HS} zu ermöglichen
|
|
& $\ominus$ Kombination nicht möglich, da kein direkter Zugriff der \acs{CPU} auf \acs{HS} physisch gegeben ist.
|
|
\\ \midrule
|
|
|
|
\textbf{Look-Aside}
|
|
& $\ominus$ schlechte Kombination, da bei jedem Schreibzugriff der Bus zweimal belastet wird
|
|
& $\oplus$ gute klassische Kombination, da Schreibzugriffe parallel im \acs{HS} und Cache physisch gut machbar sind
|
|
\end{tabular}
|
|
|
|
\subsection{Cache-Aufbau}
|
|
|
|
\begin{figure}[ht]
|
|
\centering
|
|
\includegraphics[width=\textwidth]{./Bilder/Cache_Aufbau.png}
|
|
\caption{Aufbau des Caches}
|
|
\label{fig:cache_aufbau}
|
|
\end{figure}
|
|
|
|
\begin{description}
|
|
\item[\acf{HSS}] Gleich große Speicheranteile des Hauptspeichers. Eine \acs{HSS} sollte $2^m$ \acfp{HSA} beinhalten, um eine einfache Umrechnung von \acs{HSS}-Nummern und \acs{HSA} zu ermöglichen.
|
|
\item[\acf{CL}] Kopie einer \acl{HSS} im Cache
|
|
\item[Tag] Die um $m$ niederwertigsten Bit gekürzte \acs{HSA}, welche der \acs{HSS}-Nummer entspricht.
|
|
\item[Status] Zustandsinfo zur Cache-Line, \zB Valid-Flag und weitere Zustandsinfos abhängig von Verdrängungsstrategie
|
|
\item[Valid-Flag] Die Daten werden im Cache geändert und müssen noch in den \acs{HS} zurückgeschrieben werden (nur bei Write-Back-Schreibstrategie)
|
|
\end{description}
|
|
|
|
\subsection{Vollassoziativer Cache} \index{Cache!Vollassoziativ}
|
|
Jede \acl{HSS} kann in jeder \acl{CL} eingelagert werden (nicht gleichzeitig!)
|
|
|
|
\begin{itemize}
|
|
\item[$\Rightarrow$] bei jedem Zugriff auf eine \acf{HSA} muss überprüft werden, ob die gekürzte \acs{HSA} einem der Tags von validen \aclp{CL} entspricht!
|
|
\item[$\Rightarrow$] Vergleichen der gekürzten \acs{HSA} mit allen Tags (von validen \acs{CL})
|
|
\end{itemize}
|
|
|
|
Wie kann verglichen werden? Welche Möglichkeiten des Vergleichs gibt es?
|
|
|
|
\begin{itemize}
|
|
\item Sequentiell $\Rightarrow$ Nachteil: erhöhte Zugriffszeit
|
|
\item Parallel $\Rightarrow$ gleichzeitiges Vergleichen der angelegten (gekürzten) \acs{HSA} mit allen Tags über jeweils einen eigenen Komparator in jeder \acs{CL}. \newline
|
|
Nachteil: \acl{HW}-Aufwand für Komparator in jeder \acs{CL}.
|
|
\end{itemize}
|
|
|
|
|
|
\textsf{\textbf{Einschub: Schaltungssynthese Komparator}} \newline
|
|
Hier: Schaltnetz, welches zwei Zahlen auf Gleichheit, Größer und Kleiner vergleicht.
|
|
|
|
\begin{figure}[!ht]
|
|
\centering
|
|
\includegraphics[width=6cm]{./Bilder/Cache_Komparator_1.png}
|
|
\caption{$n$-Bit-Komparator}
|
|
\label{fig:cache_komparator_1}
|
|
\end{figure}
|
|
|
|
Möchte man eine Wertetabelle für einen $n$-Bit-Komparator erstellen, sieht man, dass zu viele Zeilen in der Wertetabelle ($2^{2n}$\ldots) sind $\Rightarrow$ besser mit kaskadierbaren 1-Bit-Komparatoren
|
|
|
|
\textsf{\textbf{Komparator für Gleichheit}} \newline
|
|
\textit{Hinweis}: Im Cache reicht der Vergleich auf Gleichheit. \autoref{fig:cache_komparator_3} zeigt 1-Bit-Komparatoren für einen Gleichheits-Komparator.
|
|
\begin{figure}[!ht]
|
|
\centering
|
|
\includegraphics[width=9cm]{./Bilder/Aufwand_Komparator.png}
|
|
\caption{Aufbau des Gleichheits-Komparators im Cache}
|
|
\label{fig:cache_komparator_3}
|
|
\end{figure}
|
|
|
|
\subsubsection{Komparator}
|
|
|
|
\begin{figure}[!h]
|
|
\centering
|
|
\includegraphics[width=\textwidth]{./Bilder/Cache_Komparator.png}
|
|
\caption{Aufbau des $n$-Bit-Komparator aus kaskadierbaren 1-Bit-Komparatoren}
|
|
\label{fig:cache_komparator_2}
|
|
\end{figure}
|
|
|
|
Aus \autoref{fig:cache_komparator_2} ergibt sich folgende Tabelle:
|
|
\begin{center}
|
|
\ttfamily
|
|
\begin{tabular}{ccccc|ccc}
|
|
$b_n$ & $a_n$ & $(a>b)_{in}$ & $(a=b)_{in}$ & $(a<b)_{in}$ & $(a>b)_{out}$ & $(a=b)_{out}$ & $(a<b)_{out}$ \\ \midrule
|
|
0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\
|
|
0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\
|
|
0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\
|
|
0 & 1 & x & x & x & 1 & 0 & 0 \\
|
|
1 & 0 & x & x & x & 0 & 0 & 1 \\
|
|
1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\
|
|
1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\
|
|
1 & 1 & 1 & 0 & 0 & 1 & 0 & 0
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
Somit ergibt sich als Schaltnetz für einen 4-Bit-Komparator die \autoref{fig:n_komparator}
|
|
|
|
\begin{figure}[!ht]
|
|
\centering
|
|
\includegraphics[width=8cm]{./Bilder/n-bit-Komparator.png}
|
|
\caption{kaskadierbarer 4-Bit-Komparator}
|
|
\label{fig:n_komparator}
|
|
\end{figure}
|
|
|
|
\acs{HW}-Aufwand für einen kaskadierbaren 1-Bit-Komparator
|
|
\begin{itemize}[noitemsep]
|
|
\item HW: 30 Transistoren (8 \texttt{ODER} + 14 \texttt{UND} + 8 \texttt{NOT})
|
|
\item Zeit: 2 \acs{GLZ}
|
|
\end{itemize}
|
|
|
|
Im Cache reicht der Vergleich auf Gleichheit aller Ziffern parallel:
|
|
|
|
\begin{itemize}[noitemsep]
|
|
\item 2 $n$-Bit-Zahlen: $n$ Äquivalenzgatter und 1 \code{UND} mit $n$ Eingängen. (vergleiche \autoref{fig:cache_komparator_3})
|
|
|
|
$\Rightarrow$ $7n$ Transistoren \acs{HW}-Aufwand
|
|
|
|
$\Rightarrow$ 3 \acs{GLZ} Zeitaufwand
|
|
\end{itemize}
|
|
|
|
\subsection{Direct-Mapped Cache}\index{Cache!Direct-Mapped}
|
|
|
|
\begin{wrapfigure}[8]{r}[15mm]{78mm}
|
|
\centering
|
|
\vspace*{-15mm}
|
|
\begin{tikzpicture}
|
|
\draw (0.5, 0) rectangle ++(2,1);
|
|
\node at (1.5, 0.5) (Tag) {Tag};
|
|
\draw [decorate,decoration={brace,amplitude=6pt,raise=4pt},yshift=0pt]
|
|
(0.5,1) -- (4,1) node [black,midway,yshift=0.7cm,font=\footnotesize] {
|
|
Nummer der \acs{HSS}};
|
|
|
|
\draw (2.5, 0) rectangle ++(1.5,1);
|
|
\node at (3.25, 0.5) (mBit) {$m$-Bit};
|
|
\draw[->,very thick] (3.25,0) -- ++(0,-1.5);
|
|
\node[font=\footnotesize,align=center] at (3.25, -2) (mBesc) {Nummer der\\ \acs{CL} im \acs{DMC}};
|
|
|
|
\draw (4, 0) rectangle ++(1.5,1);
|
|
\node at (4.75, 0.5) (kBit) {$k$-Bit};
|
|
\draw[->,very thick] (4.75,0) -- ++(0,-0.6);
|
|
\node[font=\footnotesize,align=center] at (4.75, -1.1) (kBesch) {Position innerhalb\\einer \acs{HSS}};
|
|
\end{tikzpicture}
|
|
\caption{Direct-Mapped-Cache-Line}
|
|
\label{fig:direct_mapped_cache_line}
|
|
\end{wrapfigure}
|
|
|
|
Beim \acf{DMC} gibt es für jede \acs{HSS} nur/genau eine \acs{CL}, in welche diese \acs{HSS} eingelagert werden kann. \newline
|
|
$\Rightarrow$ es ist nur ein Komparator nötig
|
|
|
|
Es ist eine Hash-Funktion notwendig, welche die gekürzte \acs{HSA} auf die \acs{CL}-Nummer abbildet. Die einfachste Hash-Funktion ist \enquote{Modulo} (Rest einer Ganzzahldivision).
|
|
|
|
Modulo ist besonders einfach, falls der Divisor eine Zweierpotenz (\zB $2^m$) an Bits ist, denn dann stellen die niederwertigsten $m$ Bit den gesuchten Rest dar! Nachteil ist, dass dadurch nur Zweierpotenzen an \acsp{CL} möglich sind.
|
|
|
|
Viele Paare von \acs{HSS} können nicht gleichzeitig im Cache gehalten werden (bei gleichem Ergebnis der Hash-Funktion). Eine mögliche Problemlösung: Ausweichfunktion (wird aus Zeitgründen beim Cache nicht verwendet).
|
|
|
|
\textbf{Abhilfe}: \acf{nWAC}
|
|
|
|
\subsection{$n$-Wege-Assoziativ-Cache} \index{Cache!$n$-Wege-Assoziativ-Cache}
|
|
Für jede \acs{HSS} gibt es genau $n$ \aclp{CL}, in welche die \acs{HSS} eingelagert werden kann.
|
|
Die Realisierung findet über $n$ \acs{DMC} statt, welche alle jeweils gleich aufgebaut sind.
|
|
|
|
|
|
\subsection{Kollision}
|
|
Falls beim Einlagern einer \acl{HSS} in den Cache bereits alle für diese \acs{HSS} in Frage kommenden \aclp{CL} belegt sind, handelt es sich um eine Kollision.
|
|
|
|
Eine Kollision kann frühestens auftreten:
|
|
\begin{itemize}[noitemsep]
|
|
\item beim \acs{VAC}: bei vollem (heißen) Cache
|
|
\item beim \acs{DMC}: beim zweiten Zugriff
|
|
\item beim $n$-Wege-\acs{AC}: beim $(n+1)$-ten Zugriff
|
|
\end{itemize}
|
|
|
|
Wie groß ist die Kollisionswahrscheinlichkeit?
|
|
|
|
\begin{tabular}{c@{}llccl}
|
|
\textbullet~ & \acs{DMC}: & $p_\text{Kollision beim 2. Zugriff}$ & $=$ & $\frac{1}{\text{Anzahl \acs{CL}}}$ & $=\frac{1}{2^m}$ \\[1.5ex]
|
|
\textbullet~ & $n$-Wege-\acs{AC}: & $p_\text{Kollision beim n+1 Zugriff}$ & $=$ & $(\frac{1}{2^m})^n$ & $=(\frac{1}{2^{mn}})$
|
|
\end{tabular}
|
|
|
|
\bigskip
|
|
Beispiel: Vergleich \acs{DMC} mit 2-Wege-\acs{AC}
|
|
|
|
\begin{tabular}{c@{}l@{}ll}
|
|
\textbullet~ & \acs{DMC}: & Anzahl \acs{CL} $= 16 \Rightarrow m=4: p_\text{Kollision 2. Zugriff}$ & $=\frac{1}{2^4}=0,0625=6,25\%$ \\[1.5ex]
|
|
\textbullet~ & 2-Wege-\acs{AC}:~ & Anzahl \acs{CL} je 8~ $\Rightarrow m=3: p_\text{Kollision 3. Zugriff}$ & $=\frac{1}{2^{3\cdot 2}}=\frac{1}{2^6}=1,5625$
|
|
\end{tabular}
|
|
|
|
\subsection{Verdrängung} \index{Cache!Verdrängung}
|
|
Wenn eine \acs{HSS} in den Cache eingelagert werden soll, muss eine andere aus dem Cache entfernt werden. Eine Kollision ist Voraussetzung für Verdrängung. Mit einer Verdrängungsstrategie wird darüber entschieden, welche der möglichen \acs{HSS} verdrängt wird. In \autoref{sec:verdraengungsstrategie} wird auf die Verdrängungsstrategie eingegangen.
|
|
|
|
\begin{Hinweis}
|
|
Eine Verdrängungsstrategie ist nur notwendig beim \acs{VAC} und beim $n$-Wege-\acs{AC}. Beim \acs{DMC} braucht man \textit{keine} Verdrängungsstrategie!
|
|
\end{Hinweis}
|
|
|
|
\subsection{Adressrechnen mit Cache}
|
|
|
|
\columnratio{0.6}
|
|
\begin{paracol}{2}
|
|
\begin{tabular}{c@{}ll}
|
|
\textbullet~ & 2-Wege-\acs{AC}: & $n=2$ \\[1ex]
|
|
\textbullet~ & 2 \acs{DMC} mit jeweils 8 \acs{CL}: & $m=3$ \\[1ex]
|
|
\textbullet~ & jede \acs{CL} beinhaltet 16 Worte: & $k=4$ \\[1ex]
|
|
\textbullet~ & \acs{HS} beinhaltet $4096$ \acs{HSA}: & $2^{12}$ Speicherwerte
|
|
\end{tabular}
|
|
\switchcolumn
|
|
Der Tag ist $12-4-3=5$ Bit groß, siehe \autoref{fig:5_Bit_Tag}.
|
|
\end{paracol}
|
|
|
|
\bigskip
|
|
\begin{Hinweis}
|
|
Die Größe eines Speicherwertes bzw. Wortes in Bit wird nicht definiert und ist auch unerheblich für die folgenden Überlegungen
|
|
\end{Hinweis}
|
|
|
|
\begin{figure}[!ht]
|
|
\centering
|
|
\begin{tikzpicture}
|
|
\draw (-0.5, 0) rectangle ++(3.5,1.5);
|
|
\node[align=center] at (1.25, 0.75) (Tag) {$12-m-k$ \\$=5$ Bit Tag};
|
|
\draw [decorate,decoration={brace,amplitude=6pt,raise=4pt},yshift=0pt]
|
|
(-0.5,1.5) -- (9,1.5) node [black,midway,yshift=0.7cm] {\acs{HSA} - 12 Bit};
|
|
|
|
\draw (3, 0) rectangle ++(3,1.5);
|
|
\node[align=center] at (4.5, 0.75) (mBit) {$m$ (3) Bit\\\acs{CL}-Nummer};
|
|
|
|
\draw (6, 0) rectangle ++(3,1.5);
|
|
\node[align=center] at (7.5, 0.75) (kBit) {$k$ (4) Bit\\ Pos. in \acs{CL}};
|
|
\end{tikzpicture}
|
|
\caption{Cache-Line mit $5$-Bit Tag}
|
|
\label{fig:5_Bit_Tag}
|
|
\end{figure}
|
|
|
|
\autoref{fig:adressrechnen} zeigt Cache A (links) und Cache B (rechts), mit denen im folgenden gerechnet wird. Die angefragten \aclp{HSA} müssen auf 12-Bit erweitert werden, denn hier ist eine \acl{HSA} 12-Bit groß, wie in \autoref{fig:5_Bit_Tag} zu sehen ist.
|
|
|
|
\begin{figure}[!h]
|
|
\centering
|
|
\hspace*{-2cm}
|
|
\includegraphics[width=\textwidth+4cm]{./Bilder/Adressrechnen.png}
|
|
\caption{2-Wege-\acs{AC} - Beispiel für Adressrechnen}
|
|
\label{fig:adressrechnen}
|
|
\end{figure}
|
|
|
|
\columnratio{0.5}
|
|
\begin{paracol}{2}
|
|
\textbf{angefragte \acs{HSA}}: $42_{10}=101010_2$
|
|
\begin{center}
|
|
$\underbrace{0~0~0~0~0}_\text{Tag}\underbrace{~0~~~1~~~0~}_{\text{\acs{CL}-Nr (2)}}\underbrace{~1~~~~0~~~~1~~~~0~}_{\text{Pos. in \acs{CL} (10)}}$
|
|
\end{center}
|
|
|
|
Cache A \acs{CL}-Nr. 2 ist nicht valide
|
|
|
|
Cache B \acs{CL}-Nr. 2 ist nicht valide
|
|
|
|
$\Rightarrow$ ein Miss
|
|
|
|
$\Rightarrow$ Einlagern der \acs{HSS} (von \acs{HSA} 32 bis 47) \newline
|
|
\phantom{$\Rightarrow$} in \acs{CL}-Nr. 2
|
|
|
|
\switchcolumn
|
|
\textbf{angefragte \acs{HSA}}: $0815_{10}=1100101111_2$
|
|
\begin{center}
|
|
$\underbrace{0~0~1~1~0}_\text{Tag}\underbrace{~0~~1~~0~}_\text{\acs{CL}-Nr. (2)}\underbrace{~1~~~1~~~1~~~1~}_\text{Pos. in \acs{CL} (15)}$
|
|
\end{center}
|
|
|
|
Cache-A \acs{CL}-Nr. 2 ist valide, aber falscher Tag.
|
|
|
|
Cache-B \acs{CL}-Nr. 2 ist nicht valide.
|
|
|
|
$\Rightarrow$ insgesamt ein Miss
|
|
|
|
$\Rightarrow$ Einlagern der \acs{HSS} (von \acs{HSA} 800 bis 815) \newline
|
|
\phantom{$\Rightarrow$} in \acs{CL}-Nr. 2 in Cache B \newline
|
|
\phantom{$\Rightarrow$} (Cache A nicht möglich)
|
|
\end{paracol}
|
|
\bigskip
|
|
|
|
\columnratio{0.5}
|
|
\begin{paracol}{2}
|
|
\textbf{angefragte \acs{HSA}}: $0271_{10}$
|
|
|
|
\begin{center}
|
|
$\underbrace{~0~0~0~1~0~}_\text{Tag}\underbrace{~0~~~0~~~0~}_\text{\acs{CL}-Nr. 0}\underbrace{~1~1~1~1~}_\text{Pos. in \acs{CL} (15)}$
|
|
\end{center}
|
|
|
|
Cache A \acs{CL}-Nr. 0 ist nicht valide
|
|
|
|
Cache B \acs{CL}-Nr. 0 ist nicht valide
|
|
|
|
$\Rightarrow$ Miss
|
|
|
|
$\Rightarrow$ Einlagen der \acs{HSS} von (\acs{HSA} 256 bis 271) \newline
|
|
\phantom{$\Rightarrow$} in \acs{CL}-Nr. 0
|
|
\switchcolumn
|
|
\textbf{angefragte \acs{HSA}}: $37_{10}$
|
|
|
|
\begin{center}
|
|
$\underbrace{~0~0~0~0~0~}_\text{Tag}\underbrace{~0~~~1~~~0~}_\text{\acs{CL}-Nr. 2}\underbrace{~0~1~0~1~}_\text{Pos. in \acs{CL} (5)}$
|
|
\end{center}
|
|
|
|
\acs{CL}-Nr. 2 in Cache A ist valide, der Tag stimmt überein, also
|
|
|
|
$\Rightarrow$ Hit in Cache A \acs{CL}-Nr. 2
|
|
\end{paracol}
|
|
|
|
\textbf{angefragte \acs{HSA}}: $0675_{10}$
|
|
|
|
$\underbrace{~0~0~1~0~1~}_\text{Tag}\underbrace{~0~~~1~~~0~}_\text{\acs{CL}-Nr. 2}\underbrace{~0~0~1~1~}_\text{Pos. in \acs{CL} (3)}$
|
|
|
|
Tag in \acs{CL}-Nr. 2 von Cache A und Cache B \newline
|
|
sind verschieden vom angefragten Tag.
|
|
|
|
$\Rightarrow$ Miss $\Rightarrow$ sogar Kollision \newline
|
|
$\Rightarrow$ Verdrängung notwendig
|
|
|
|
|
|
|
|
\subsection{Verdrängungsstrategie} \label{sec:verdraengungsstrategie} \index{Cache!Verdrängungsstrategie}
|
|
|
|
\subsubsection{Random}
|
|
Die zu verdrängende Seite wird zufällig aus den möglichen \acs{HSS} ausgewählt.
|
|
|
|
\textit{Bewertung}:\newline
|
|
Erwartete Hit-Rate $=\frac{\text{Größe (Cache)}}{\text{Größe (\acs{HS})}}$ (bei zufällig verteilten Zugriffen, also ziemlich schlecht)
|
|
|
|
$\Rightarrow$ nur für Benchmark-Zwecke
|
|
|
|
notwendiger Aufwand: Zufallszahlengenerator
|
|
\begin{itemize}[noitemsep]
|
|
\item[$\Rightarrow$] echter Zufall ist sehr teuer \& aufwändig.
|
|
\item[$\Rightarrow$] für Benchmarks reichen (meist) Pseudozufallszahlen aus
|
|
\end{itemize}
|
|
|
|
\subsubsection{Optimale Strategie}
|
|
Es wird die \acl{HSS} verdrängt, welche in der Zukunft gar nicht mehr oder am längsten nicht mehr gebraucht wird.
|
|
|
|
\textit{Bewertung}: \newline
|
|
Erwartete Hit-Rate = \enquote{systembedingtes Maximum}
|
|
|
|
\textit{Aufwand}: \newline
|
|
\enquote{Blick in die Zukunft} bzw. \enquote{Kristallkugel} $\Rightarrow$ nicht möglich!
|
|
|
|
\textit{Realisierung für Benchmarking}: \newline
|
|
Zweimaliger Durchlauf für genau dieselben Parameter. Der erste Durchlauf für Logfile und zweiter Durchlauf mit optimaler Strategie anhand des Logfiles.
|
|
|
|
\subsubsection{First-In-First-Out (FIFO)}
|
|
Bei der \acf{FIFO}-Strategie wird die \acs{HSS}, welche sich am längsten im Cache befindet, verdrängt (klassische Warteschlangenbedienstrategie).
|
|
|
|
\textit{Aufwand}:\newline
|
|
Timestamp in jeder \acl{CL}. Bei Verdrängung: Suche nach dem Minimum der Timestamps (sehr aufwändig!).
|
|
|
|
\textit{Besser}:\newline
|
|
Verwaltung der \acsp{CL} als einfach verwaltete Liste, \dash Zeiger auf den Nachfolger in jeder \acs{CL}. Globalen Zeiger auf den ersten und letzten Eintrag für Verdrängung und Einlagerung.
|
|
|
|
\textit{Schlecht unterstützte, aber häufige Zugriffsmuster}: \newline
|
|
Ständig genutzte Datenstücke werden genauso schnell verdrängt wie Daten, die nur ein einziges Mal gebraucht werden. Anders gesagt: Daten, die lange nicht benötigt wurden, werden auch nicht schneller verdrängt, als Daten, die genauso lange im Cache sind, aber erst kürzlich gebraucht wurden.
|
|
|
|
\subsubsection{Least-Recently-Used (LRU)}
|
|
Bei der \acf{LRU} Strategie wird die \acl{HSS}, auf welche am längsten nicht zugegriffen wurde, verdrängt.
|
|
|
|
\textit{Aufwand}: \newline
|
|
Timestamp mit Update bei jedem Zugriff $\Rightarrow$ Die Suche bei Verdrängung ist zu aufwändig!
|
|
|
|
\textit{Besser}:\newline
|
|
Verwaltung als \textit{doppelt} verkettete Liste, \dash Zeiger auf Vorgänger \textit{und} Nachfolger in jeder \acs{CL}. Globalen Zeiger auf ersten und letzten Eintrag.
|
|
|
|
\textit{Schlecht unterstützte Zugriffsmuster}: \newline
|
|
Häufigkeit der Zugriffe wird nicht berücksichtigt, \dash vielfach genutzte \aclp{HSS} werden genauso verdrängt wie \acs{HSS} mit nur einem Zugriff)
|
|
|
|
\subsubsection{Least-Frequently-Used (LFU)}
|
|
Bei der \acf{LFU} Strategie wird die \acl{HSS} verdrängt, welche bisher am seltensten (\enquote{am wenigsten häufig}) verwendet wurde.
|
|
|
|
\columnratio{0.35}
|
|
\begin{paracol}{2}
|
|
\textit{Aufwand (für Statusinfo):}
|
|
\begin{itemize}[noitemsep]
|
|
\item Benutzungszähler
|
|
\item Einlagerungszeit
|
|
\end{itemize}
|
|
\switchcolumn
|
|
\medskip
|
|
Häufigkeit=$\frac{\text{Zugriffe}}{\text{Zeit}}$
|
|
|
|
$\Rightarrow$ Bei Verdrängung aufwändige Berechnung und Suche
|
|
\end{paracol}
|
|
|
|
\textit{Problem (Zugriffsmuster)}: \newline
|
|
Neu eingelagerte Seiten werden schnell wieder verdrängt, wenn sich der Zugriffszähler am Anfang nicht schnell genug erhöht und andere etablierte Seiten eine höhere Häufigkeit aufgrund vieler \enquote{alter} Zugriffe aufweisen.
|
|
|
|
\textit{Lösungsansatz}: \newline
|
|
Zugriffe müssen \enquote{altern}, \dash alte Zugriffe werden weniger stark gewichtet als neue Zugriffe.
|
|
|
|
\textit{Mögliche Implementierung}: \newline
|
|
Mehrere Zugriffszähler in jeder \acs{CL} für die letzten $i$ Zeitscheiben.
|
|
Dividieren ist damit überflüssig (alle Zeitscheiben sind gleich lang): Addition der mit $2^j$ gewichteten Zähler als \enquote{Häufigkeit} ($j=i-1$ für jüngste Zeitscheiben, $j=0$ für älteste Zeitscheibe).
|
|
|
|
\textit{Weiterhin}: \newline
|
|
Bei der Verdrängung gibt es ein Problem bei der Suche nach der niedrigsten \enquote{Häufigkeit}. \newline
|
|
$\Rightarrow$ evtl. Lösung über eine bei Beginn jeden Zeitslots neu aufzubauende verkettete Liste. \newline
|
|
\phantom{$\Rightarrow$ }Hier gibt es viel Platz für Optimierungen der \acs{CPU}-Hersteller.
|
|
|
|
\subsection{Cache bei Mehrprozessor-/Mehrkernsystemen} \index{Mehrkernprozessor}
|
|
In \autoref{fig:cpu_mehrprozessor} besitzt jeder Kern einen eigenen Cache. Möglich wäre auch ein gemeinsamer Cache. Verglichen werden diese beiden Möglichkeiten in \autoref{tbl:mehrprozessor_cache}.
|
|
|
|
\begin{figure}[!ht]
|
|
\centering
|
|
\includegraphics[width=\textwidth-3cm]{./Bilder/CPU_Mehrprozessor.png}
|
|
\caption{Mehrprozessor-/Mehrkernsystem}
|
|
\label{fig:cpu_mehrprozessor}
|
|
\end{figure}
|
|
|
|
\begin{table}[ht]
|
|
\hspace*{-5mm}
|
|
\begin{tabular}{@{}cp{7.6cm}|cp{7.6cm}}
|
|
& \textbf{gemeinsamer Cache} & & \textbf{getrennter Cache} \\ \midrule
|
|
|
|
$\oplus$ & dieselben Daten für beide Kerne benötigt/bedeutet nur einmaliges Einlagern im Cache (Platzvorteil).
|
|
& $\ominus$ & Dieselben Daten müssen ggf. mehrfach in den Caches gehalten werden.
|
|
\\ [4ex]
|
|
|
|
$\ominus$ & komplexer Bus mit Zugriffsprotokoll\newline(Zeitverlust zumindest bei Zugriffskollision)
|
|
& $\oplus$ & einfache 1:1-Verbindungen (kein komplexes Zugriffsprotokoll)
|
|
\\ [2ex]
|
|
|
|
& & $\ominus$ & keine Konsistenz trotz Write-Through Strategie gewährleistet\\
|
|
\end{tabular}
|
|
\caption{Vergleich von getrennten/gemeinsamen Caches bei Mehrkernsystemen}
|
|
\label{tbl:mehrprozessor_cache}
|
|
\end{table}
|
|
|
|
Abhilfe für Inkonsistenzen bei mehreren Caches und Mehrprozessorsystemen:
|
|
|
|
\begin{itemize}[noitemsep]
|
|
\item gemeinsamer Cache (ungünstige Performance aufgrund eines Bus)
|
|
\item Snoop-Logik, \dash jeder Cache schnüffelt bei den anderen Caches bzw. beim \acs{HS}, welche Daten geschrieben wurden und invalidiert diese ggf. im eigenen Cache.
|
|
\end{itemize}
|
|
|
|
Tatsächlich haben moderne \acsp{CPU} beim L1-Cache getrennte Caches für jeden Kern und beim L3-Cache einen gemeinsamen Cache. Ob eine Snoop-Logik verwendet wird, ist davon abhängig, ob es für das Level notwendig ist oder nicht.
|
|
|
|
\section{Hauptspeicher-Organisation}
|
|
Ein \acl{HS}-Wort wird über eine \acl{HSA} (binäre, ganze, nicht negative Zahl) angesprochen.
|
|
Jedes \acl{HS}-Wort hat eine feste Wortbreite (im besten Fall gleich der \acs{CPU}-Wortbreite, also 64-Bit).
|
|
|
|
Im folgenden gehen wir von 1-Bit-Worten aus:
|
|
\begin{center}
|
|
$0\leq \text{\acs{HSA}} \leq (\text{\acs{HS}-Größe in Worten}) - 1$
|
|
\end{center}
|
|
|
|
Ein 1-Bit-Kondensatorspeicher wird in \autoref{fig:hs_kondensator} gezeigt. Für jedes \acl{HS}-Wort gibt es eine Select-Leitung. Für jedes Bit des Wortes gibt es einen Kondensator und einen Transistor. Diese werden dann parallel geschaltet.
|
|
|
|
Mehrere 1-Bit-Worte hängen an der selben Datenleitung, werden aber über unterschiedliche Select-Leitungen angesteuert.
|
|
|
|
\begin{figure}[!ht]
|
|
\centering
|
|
\includegraphics[width=\textwidth-52mm]{./Bilder/HS_Kondensator.png}
|
|
\caption{Hauptspeicher -- 1-Bit-Kondensatorspeicher}
|
|
\label{fig:hs_kondensator}
|
|
\end{figure}
|
|
|
|
Um aus der $n$-Bit-\acs{HSA} $2^n$ Select-Leitungen zu erzeugen, welche die Bits abfragen, ist ein $n:2^n$-Decoder notwendig.
|
|
|
|
In \autoref{fig:4_16_dekoder} wird ein $4:16$-Decoder mit entsprechender Wertetabelle gezeigt.
|
|
|
|
\begin{figure}[!ht]
|
|
\centering
|
|
\includegraphics[width=7cm]{./Bilder/4_16_Dekoder.png}
|
|
\medskip
|
|
\begin{tabular}{cccc|cccccccccccccccc}
|
|
$a_3$ & $a_2$ & $a_1$ & $a_0$ & $s_{15}$ & $s_{14}$ & $s_{13}$ & $s_{12}$ & $s_{11}$ & $s_{10}$ & $s_{9}$ & $s_{8}$ & $s_{7}$ & $s_{6}$ & $s_{5}$ & $s_{4}$ & $s_{3}$ & $s_{2}$ & $s_{1}$ & $s_{0}$ \\ \midrule
|
|
0 & 0 & 0 & 0 & & & & & & & & & & & & & & & & 1 \\
|
|
0 & 0 & 0 & 1 & & & & & & & & & & & & & & & 1 & \\
|
|
0 & 0 & 1 & 0 & & & & & & & & & & & & & & 1 & & \\
|
|
0 & 0 & 1 & 1 & & & & & & & & & & & & & 1 & & & \\
|
|
0 & 1 & 0 & 0 & & & & & & & & & & & & 1 & & & & \\
|
|
0 & 1 & 0 & 1 & & & & & & & & & & & 1 & & & & & \\
|
|
0 & 1 & 1 & 0 & & & & & & & & & & 1 & & & & & & \\
|
|
0 & 1 & 1 & 1 & & & & & & & & & 1 & & & & & & & \\
|
|
1 & 0 & 0 & 0 & & & & & & & & 1 & & & & & & & & \\
|
|
1 & 0 & 0 & 1 & & & & & & & 1 & & & & & & & & & \\
|
|
1 & 0 & 1 & 0 & & & & & & 1 & & & & & & & & & & \\
|
|
1 & 0 & 1 & 1 & & & & & 1 & & & & & & & & & & & \\
|
|
1 & 1 & 0 & 0 & & & & 1 & & & & & & & & & & & & \\
|
|
1 & 1 & 0 & 1 & & & 1 & & & & & & & & & & & & & \\
|
|
1 & 1 & 1 & 0 & & 1 & & & & & & & & & & & & & & \\
|
|
1 & 1 & 1 & 1 & 1 & & & & & & & & & & & & & & &
|
|
\end{tabular}
|
|
\caption{Hauptspeicher -- 1-Bit-Kondensatorspeicher}
|
|
\label{fig:4_16_dekoder}
|
|
\end{figure}
|
|
|
|
Es müssen alle Minterme gebildet werden.
|
|
Die \acs{DNF} ist für jedes $s_i$ gleichzeitig die \acs{DMF} (da sie aus nur einem Minterm besteht). \newline
|
|
Somit besteht der $n:2^n$ Decoder aus genau $2^n$ Mintermen mit jeweils $n$ Literalen.
|
|
|
|
\begin{tabular}{@{}ll}
|
|
\textsf{\textbf{Zeitaufwand}}: & 1~\acs{GLZ} ($O(1)$) und damit perfekt \\ [1ex]
|
|
\textsf{\textbf{Hardwareaufwand}}: & $n\cdot 2^n$ Transistoren
|
|
\end{tabular}
|
|
|
|
\textbf{\textsf{Hardwareaufwand für Speicher und Decoder}}: \newline
|
|
Am Beispiel vom Apple \RNum{2}/C64/\ldots: 16~Bit~\acs{HSA}, 8~Bit~Worte
|
|
\begin{itemize}
|
|
\item[$\Rightarrow$] $2^{16}$ 8-Bit-Worte: 65536~Byte = 512~kBit Speicher
|
|
\item[$\Rightarrow$] für Speicher: 1 Mio. Bauelemente \newline
|
|
für $16:2^{16}$ Decoder: $16\cdot 2^{16}$ Transistoren $\approx$ 1 Mio. Transistoren
|
|
\item[$\Rightarrow$] der Decoder hat denselben Aufwand wie der Speicher!
|
|
\end{itemize}
|
|
|
|
\newpage % Nur für's Layout
|
|
|
|
\acs{PC} mit 32~Bit~\acs{CPU}:
|
|
\begin{itemize}[noitemsep]
|
|
\item[] 32~Bit = 4~Byte \acl{HS}-Wortgröße
|
|
\item[] 32~Bit-\acs{HSA}: $2^{32}$ \acs{HS}-Worte $\approx$ 4~Mrd. \acs{HS}-Worte
|
|
\end{itemize}
|
|
\bigskip
|
|
|
|
\begin{Tipp}
|
|
Intel-\acsp{CPU} adressieren nach wie vor jedes einzelne Byte und nicht \acl{HS}-Worte der Größe 4 oder 8~Byte.
|
|
\end{Tipp}
|
|
|
|
Eine Ideale 32~Bit~\acs{CPU} hätte $2^{32}$ Werte je 32~Bit:
|
|
\begin{itemize}[noitemsep]
|
|
\item[$\Rightarrow$] $2^{32}\cdot 32$~Bit $\approx$ 128~Mrd.~Bit Speicher
|
|
\item[$\Rightarrow$] 256 Mrd. Bauelemente Hardwareaufwand für \acl{HS}
|
|
\item[$\Rightarrow$] Hardwareaufwand für einen $32:2^{32}$ Decoder: $32\cdot 2^{32}$ Tr. = 128~Mrd. Transistoren.
|
|
\end{itemize}
|
|
|
|
Ideale 64~Bit~\acs{CPU} hätte $2^{64}$ Werte je 64~Bit:
|
|
\begin{itemize}[noitemsep]
|
|
\item[$\Rightarrow$] $2^{64}\cdot 64$~Bit $=2^{70}$ $\approx$ 1~Trilliarde~Bit
|
|
\item[$\Rightarrow$] 2 Trilliarden Bauelemente Hardwareaufwand für \acs{HS}.
|
|
\item[$\Rightarrow$] $64:2^{64}$ Decoder: $64\cdot 2^{64}$ Transistoren $\approx$ 1 Trilliarde Transistoren
|
|
\end{itemize}
|
|
|
|
In jedem Fall ist der Hardwareaufwand für den Decoder in derselben Größenordnung wie für den eigentlichen Hauptspeicher und damit sehr (zu) groß!
|
|
|
|
\textit{Abhilfe}: matrixförmige Speicherorganisation
|
|
|
|
\section{Matrixförmige Speicherorganisation}
|
|
Eine matrixförmige Speicherorganisation: zweidimensionale Anordnung der Speicherwerte in Zeilen und Spalten, siehe \autoref{fig:matrix_decoder} auf \autopageref{fig:matrix_decoder}.
|
|
|
|
\begin{figure}[!ht]
|
|
\centering
|
|
\includegraphics[width=\textwidth-5cm]{./Bilder/Matrix_Decoder.png}
|
|
\caption{Matrixdecoder}
|
|
\label{fig:matrix_decoder}
|
|
\end{figure}
|
|
|
|
$a_3a_2$ gibt die Zeilennummer an und $a_1a_0$ die Spaltennummer. Somit reicht es statt eines 4:16-Decoders einen 2:4~Zeilen- und einen 2:4~Spalten-Decoder zu verwenden.
|
|
|
|
\textbf{Aufwand} \newline
|
|
Anstatt wie bei einem $4:16$-Decoder mit 64 Transistoren beträgt der Aufwand bei zwei $2:4$-Decodern mit $2\cdot 8$ Transistoren = 16 Transistoren.
|
|
|
|
64-Bit \acs{HSA}: als $64:2^{64}$ Decoder: $2^{70}$ Transistoren
|
|
|
|
als Matrix mit $2^{32}$ Zeilen und $2^{32}$ Spalten:
|
|
\begin{itemize}
|
|
\item $32:2^{32}$ Decoder mit jeweils $32\cdot 2^{32}$ Transistoren = $2^{37}$ Transistoren
|
|
\item 2 Stück: $2^{38}$ Transistoren: 256 Mrd. Transistoren
|
|
\end{itemize}
|
|
|
|
In linearer Organisation betrüge der Decoder-Aufwand das 4-Mrd.-fache! Damit ergibt sich eine große Einsparung beim Decoder-Aufwand!
|
|
|
|
\textit{Aber}: für die Realisierung des 2. Select-Eingangs wird ein weiterer Transistor je Bit benötigt \newline
|
|
$\Rightarrow$ dieselbe Größenordnung Zusatzaufwand wie Einsparung?
|
|
|
|
Statt eines Spalten-Decoders werden die Datenleitungen aller Speicherbits einer Spalte zusammengeschaltet (als jeweils eine Spalten-Datenleitung). Von diesen wird aber über einen Spalten-Multiplexer ein Spalten-Daten-Signal ausgewählt. Dies wird in \autoref{fig:matrix_multiplexer} dargestellt.
|
|
|
|
\begin{figure}[ht]
|
|
\centering
|
|
\includegraphics[width=\textwidth-5cm]{./Bilder/Matrix_Multiplexer.png}
|
|
\caption{Matrixmultiplexer}
|
|
\label{fig:matrix_multiplexer}
|
|
\end{figure}
|
|
|
|
\begin{description}
|
|
\item[$2^n:1$-MUX] Baustein, welcher aus $2^n$-Dateneingängen anhand einer $n$-stelligen Adresse eine Datenleitung auswählt und ausgibt.
|
|
\item[$2^4:1$-MUX] Hat 4 Adresseingänge und $2^4=16$ Dateneingänge
|
|
\end{description}
|
|
|
|
\begin{figure}[!ht]
|
|
\centering
|
|
\includegraphics[width=\textwidth-2cm]{./Bilder/Schaltnetz_MUX.png}
|
|
\caption{Schaltnetz eines $4:1$-MUX}
|
|
\label{fig:schaltnetz_MUX}
|
|
\end{figure}
|
|
|
|
Realisierung über $2:4$ Decoder sowie 4 \code{UND} mit jeweils 2 Eingängen und ein \code{ODER} mit 4 Eingängen.
|
|
|
|
$2^n:1$ MUX: \newline
|
|
\hspace*{5mm}ein $n:2^n$ Decoder \newline
|
|
\hspace*{5mm}$2^n$ \code{UND} mit jeweils 2 Eingängen \newline
|
|
\hspace*{5mm}ein \code{ODER} mit $2^n$ Eingängen \newline
|
|
\hspace*{5mm}\textit{Gesamtaufwand}: $n\cdot 2^n+2\cdot 2^n+2^n$ Transistoren $=(n+3)\cdot 2^n$ Transistoren
|
|
|
|
Insgesamt braucht man für einen kleinen Decoder und einem kleinen Multiplexer immer noch deutlich weniger Hardwareaufwand wie für einen großen Decoder.
|
|
|
|
Vor den Multiplexer kann ein Cache geschaltet werden, sodass eine ganze \acs{HSS} (=Matrixzeile) eingelesen werden kann.
|
|
|
|
\subsection{Gründe für Matrixorganisation}
|
|
\begin{enumerate}[noitemsep]
|
|
\item weniger Aufwand für Adressdecodierung
|
|
\item Einlesen einer ganzen \acs{HSS} (=Matrixzeile) in den Cache
|
|
\item zeilenweiser Refresh des \acs{HS} (wortweiser Refresh-Zyklus dauert viel zu lange)
|
|
\end{enumerate} |