1045 lines
47 KiB
TeX
1045 lines
47 KiB
TeX
\chapter{Rechenwerk / Rechnen in Hardware}
|
|
|
|
\textsf{\textbf{Grundlagen: Addition}} \index{Addition}
|
|
|
|
\columnratio{0.25}
|
|
\begin{paracol}{2}
|
|
\begin{tabular}{l|c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}}
|
|
& & 4 & 7 & 1 & 1 \\
|
|
& + & 0 & 8 & 1 & 5 \\
|
|
Übertrag & 0 & 1 & 0 & 0 & \\
|
|
\hline
|
|
& & 5 & 5 & 2 & 6
|
|
\end{tabular}
|
|
|
|
\switchcolumn
|
|
Die Addition von mehrstelligen Zahlen wird reduziert auf die Addition von zwei (oder drei) einstelligen Zahlen (bzw. Ziffern) zu einer einstelligen Zahl sowie einem einstelligen Übertrag, also einer zweistelligen Zahl als Ergebnis $\Rightarrow$ genauso funktioniert dies im Binärsystem.
|
|
\end{paracol}
|
|
|
|
\begin{Hinweis}
|
|
Herr Röthig meint hier mit \enquote{einstellig} und \enquote{mehrstellig} die Anzahl der Zahlen und nicht die Stellenanzahl einer einzelnen Zahl. Im Beispiel oben werden zwei Zahlen addiert und daraus ergeben sich zwei weitere Zahlen als Ergebnis.
|
|
\end{Hinweis}
|
|
|
|
\section{Schaltnetzsysnthese -- Wiederholung / Grundlegendes}
|
|
|
|
\begin{description}
|
|
\item[Schaltnetz] \index{Schaltnetz} Kann nur die derzeitigen Eingangsdaten verarbeiten, da keine Rückkopplung vorliegt
|
|
\item[Schaltwerk] \index{Schaltwerk} \enquote{Hat ein Gedächtnis}, da eine Rückkopplung vorliegt
|
|
\item[Vollkonjunktion/Minterm] \texttt{UND}-Verknüpfung aller vorkommenden Variablen entweder in negierter oder nicht-negierter Form
|
|
\item[\acf{DNF}] \index{DNF} Eine Disjunktion (\texttt{ODER}-Verknüpfung) von Konjunktionstermen (\texttt{UND}-Verknüpfungen).
|
|
\item[\acf{DMF}] \index{DMF} Ist die minimale Darstellung einer Ausgabefunktion und damit eine Vereinfachung einer \acs{DNF}
|
|
\end{description}
|
|
|
|
\subsection{Schaltungsanalyse} \index{Schaltungsanalyse}
|
|
Eine Schaltungsanalyse ist die Bestimmung des \enquote{Aufwands}. Dabei kann der Aufwand sein:
|
|
|
|
\begin{itemize}
|
|
\item \enquote{Hardware-Aufwand} (in Anzahl an Transistoren)
|
|
\item Zeitaufwand (in \acl{GLZ})
|
|
\end{itemize}
|
|
|
|
\subsection{Warum soll der Zeitaufwand analysiert werden?} \index{Zeitaufwand}
|
|
Es wird der Zeitaufwand betrachtet, da Gatter Schaltzeiten haben, welche typischerweise \circa{10 Pikosekunden} betragen. Insgesamt werden bei einem Signaldurchgang auf dem \acs{IC} sehr viele Gatter durchlaufen. Damit sind die Schaltzeiten um Größenordnungen größer als die reine Laufzeit der Signale auf dem Leiter angegeben (letztere wird vernachlässigt, Zeitverzögerung wird in \enquote{Anzahl \acfp{GLZ}} angegeben).
|
|
|
|
\section{Halbaddierer} \index{Halbaddierer}
|
|
Ein Halbaddierer vollzieht die Addition von zwei einstelligen Binärzahlen $a$ und $b$ zu einer zweistelligen Binärzahl $c_{out}s$ (Übertrag und Summe). Schaltsymbol und Schaltnetz des Halbaddierers werden in \autoref{fig:halbaddierer} dargestellt.
|
|
|
|
Die folgende Tabelle zeigt den Gedankenweg, wie ein Halbaddierer funktioniert.
|
|
\begin{center}
|
|
\begin{tabular}{c|cc|ccc|c}
|
|
Nr. & $b$ & $a$ & $c_{out}$ & $s$ & Minterm & \acs{DNF} \\ \midrule
|
|
0 & 0 & 0 & 0 & 0 & & \\
|
|
1 & 0 & 1 & 0 & 1 & $\overline{b}a$ & $c_{out} = ba$ \\
|
|
2 & 1 & 0 & 0 & 1 & $b\overline{a}$ & $s=\overline{b}a \vee b\overline{a}$ \\
|
|
3 & 1 & 1 & 1 & 0 & $ba$ & $\Rightarrow$ beides gleichzeitig auch \acs{DMF}
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
\begin{figure}[ht]
|
|
\centering
|
|
\begin{tikzpicture}[font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
\node at (3,5.9) {Schaltnetz};
|
|
|
|
\node at (1,5.5) (B) {b};
|
|
\node at (1.5,5.5) (A) {a};
|
|
|
|
\node[and gate, inputs={nn}] at (3,4.5) (PORT1) {};
|
|
\node[and gate, inputs={in}] at (3,3) (PORT2) {};
|
|
\node[and gate, inputs={ni}] at (3,1.5) (PORT3) {};
|
|
\node[or gate, inputs={nn}] at (5,1.675) (PORT5) {};
|
|
|
|
% -| nutzt nur eine Koordinate
|
|
\draw (A) |- (PORT1.input 1); \node[knoten] at (PORT1.input 1 -| A) {};
|
|
\draw (A) |- (PORT2.input 1); \node[knoten] at (PORT2.input 1 -| A) {};
|
|
\draw (A) |- (PORT3.input 1);
|
|
|
|
\draw (B) |- (PORT1.input 2); \node[knoten] at (PORT1.input 2 -| B) {};
|
|
\draw (B) |- (PORT2.input 2); \node[knoten] at (PORT2.input 2 -| B) {};
|
|
\draw (B) |- (PORT3.input 2);
|
|
|
|
\draw (PORT2.output) -- ([xshift=5mm]PORT2.output) |- (PORT5.input 1);
|
|
\draw (PORT3.output) -- ([xshift=5mm]PORT3.output) |- (PORT5.input 2);
|
|
|
|
\draw (PORT5.output) -- ([xshift=8mm]PORT5.output);
|
|
\node[right=of PORT5.output] {$s$};
|
|
\node[font=\tiny] at ($(PORT5.output) + (0.5,0.25)$) {\textcolor{blue}{2 GLZ}};
|
|
|
|
\draw (PORT1.output) -- (PORT1.output) |- ++(1,0);
|
|
\node[right=of PORT1.output] {$c_{out}$};
|
|
\node[font=\tiny] at ($(PORT1.output) + (0.5,0.25)$) {\textcolor{blue}{1 GLZ}};
|
|
\end{tikzpicture}
|
|
\begin{tikzpicture}[font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
\node at (2.5,6.8) {Schaltnetz vereinfacht};
|
|
|
|
\node at (1,5.5) (B) {b};
|
|
\node at (1.5,5.5) (A) {a};
|
|
|
|
\node[and gate, inputs={nn}] at (3,4.5) (PORT1) {};
|
|
\node[xor gate, inputs={nn}] at (3,3) (PORT2) {};
|
|
|
|
% -| nutzt nur eine Koordinate
|
|
\draw (A) |- (PORT1.input 1); \node[knoten] at (PORT1.input 1 -| A) {};
|
|
\draw (A) |- (PORT2.input 1);
|
|
|
|
\draw (B) |- (PORT1.input 2); \node[knoten] at (PORT1.input 2 -| B) {};
|
|
\draw (B) |- (PORT2.input 2);
|
|
|
|
\draw (PORT2.output) -- ([xshift=8mm]PORT2.output);
|
|
\node[right=of PORT2.output] {$s$};
|
|
|
|
\draw (PORT1.output) -- (PORT1.output) |- ++(1,0);
|
|
\node[right=of PORT1.output] {$c_{out}$};
|
|
|
|
\node at (0,2) {}; % Nur fürs positionieren
|
|
\end{tikzpicture}
|
|
\begin{tikzpicture}[font=\sffamily]
|
|
\node at (-0.25,2.5) {Schaltsymbol};
|
|
|
|
\draw (-1, -1) rectangle ++(1.5,1.5);
|
|
\node[] at (-0.25,-0.25) (HA) {HA};
|
|
\node[] at ($(HA)+(1.6,0.5)$) (cout) {$c_{out}$};
|
|
\node[] at ($(HA)+(1.4,-0.5)$) (s) {$s$};
|
|
\node[] at ($(HA)+(-1.4,0.5)$) (b) {$b$};
|
|
\node[] at ($(HA)+(-1.4,-0.5)$) (a) {$a$};
|
|
|
|
\draw (-1, 0.25) -- ++(-0.4,0);
|
|
\draw (-1, -0.75) -- ++(-0.4,0);
|
|
|
|
\draw (0.5, 0.25) -- ++(0.4,0);
|
|
\draw (0.5, -0.75) -- ++(0.4,0);
|
|
|
|
\node at (0,-2.3) {}; % Nur fürs positionieren
|
|
\end{tikzpicture}
|
|
\caption{Halbaddierer -- Schaltnetz und Schaltsymbol}
|
|
\label{fig:halbaddierer}
|
|
\end{figure}
|
|
|
|
\section{Volladdierer}\index{Volladdierer}
|
|
Vollzieht die Addition von drei einstelligen Binärzahlen $a$, $b$ und $c_{in}$ zu einer zweistelligen Binärzahl $c_{out}s$ (Übertrag und Summe). Schaltsymbol und Schaltnetz des Volladdierer werden in \autoref{fig:volladdierer} dargestellt.
|
|
|
|
\begin{figure}[h!]
|
|
\centering
|
|
|
|
\begin{tikzpicture}[font=\sffamily]
|
|
\node at (4,1.5) {Schaltnetz};
|
|
|
|
\node[] at (0,0.75) (a) {$a$};
|
|
\node[] at (0,0) (b) {$b$};
|
|
\node[] at (0,-0.75) (c) {$c_{in}$};
|
|
|
|
% HA 1
|
|
\draw (1, -0.3) rectangle ++(1.5,1.5);
|
|
\node[] at (1.75,0.45) (HA1) {HA};
|
|
\draw (a) -- ($(a)+(1, 0)$);
|
|
\draw ($(a)+(2.5,0)$) -- ++(3.5,0);
|
|
\draw (b) -- ($(b)+(1, 0)$);
|
|
\node at ($(a)+(3,0.15)$) {$c_{out_1}$};
|
|
\node at ($(b)+(2.8,-0.24)$) {$s_1$};
|
|
|
|
% HA 2
|
|
\draw (3.5, -1.2) rectangle ++(1.5,1.5);
|
|
\node[] at (4.25,-0.45) (HA2) {HA};
|
|
\draw ($(b)+(2.5,0)$) -- ++(1,0);
|
|
\draw (c) -- ++(3.5,0);
|
|
\node at ($(b)+(5.5,-0.24)$) {$c_{out_2}$};
|
|
\node at ($(c)+(5.3,-0.24)$) {$s_2$};
|
|
|
|
% HA 3
|
|
\draw (6, -0.3) rectangle ++(1.5,1.5);
|
|
\node[font=\large] at (6.75,0.4) (HA2) {$\geq1$};
|
|
\draw ($(b)+(5,0)$) -- ++(1,0);
|
|
\draw ($(c)+(5,0)$) -- ++(3,0);
|
|
\node at ($(c)+(8.5,0)$) {$s$};
|
|
\draw ($(b)+(7.5,0)$) -- ++(0.5,0);
|
|
\node at ($(b)+(8.5,0)$) {$c_{out}$};
|
|
\end{tikzpicture}
|
|
\begin{tikzpicture}[font=\sffamily]
|
|
\node at (-0.25,1.1) {Schaltsymbol};
|
|
|
|
\draw (-1, -1) rectangle ++(1.5,1.5);
|
|
\node[] at (-0.25,-0.25) (VA) {VA};
|
|
\node[] at ($(VA)+(1.6,0.5)$) (cout) {$c_{out}$};
|
|
\node[] at ($(VA)+(1.4,-0.5)$) (s) {$s$};
|
|
|
|
\node[] at ($(VA)+(-1.4,0.5)$) (c) {$c_{in}$};
|
|
\node[] at ($(VA)+(-1.4,0)$) (b) {$b$};
|
|
\node[] at ($(VA)+(-1.4,-0.5)$) (a) {$a$};
|
|
|
|
\draw (0.5, 0.25) -- ++(0.4,0);
|
|
\draw (0.5, -0.75) -- ++(0.4,0);
|
|
|
|
\draw (-1, 0.25) -- ++(-0.4,0);
|
|
\draw (-1, -0.25) -- ++(-0.4,0);
|
|
\draw (-1, -0.75) -- ++(-0.4,0);
|
|
|
|
\node at (0,-1.5) {}; % Nur fürs positionieren
|
|
\end{tikzpicture}
|
|
\caption{Volladdierer -- Schaltnetz und Schaltsymbol}
|
|
\label{fig:volladdierer}
|
|
\end{figure}
|
|
|
|
\textit{Hinweis:} Für die Verknüpfung von $c_{out_1}$ und $c_{out_2}$ zu $c_{out}$ wäre eigentlich ein \texttt{XOR} notwendig. Da aber der Fall $c_{out_1} = c_{out_2} = 1$ (also beide Eingänge des \texttt{XOR} \enquote{1}) nie auftritt, reicht ein \texttt{OR}.
|
|
|
|
\section{Paralleladdierer (4-Bit-Ripple-Carry-Paralleladdierer RC-PA)} \index{Paralleladdierer!RC-PA}
|
|
Der \acs{RC-PA} ist ein mehrstelliger Addierer für Binärzahlen. In den folgenden Beispielen ist er ein Addierer vierstelliger Binärzahlen $a_3a_2a_1a_0$ und $b_3b_2b_1b_0$. Das Ergebnis ist $s_4s_3s_2s_1s_0$ und somit eine 5-stellige Zahl. $s_4$ ist der Überlauf.
|
|
|
|
\autoref{fig:paralleladdierer_rc} zeigt das Schaltnetz und Schaltsymbol eines Paralleladdierers.
|
|
\newline
|
|
|
|
\begin{figure}[ht]
|
|
\centering
|
|
\begin{tikzpicture}[font=\sffamily]
|
|
\foreach \a in {0,...,3} {
|
|
% Calculate the index
|
|
\def\b{{\pgfmathparse{3-\a} % Evaluate the expression
|
|
\pgfmathprintnumber[ % Print the result
|
|
fixed,
|
|
fixed zerofill,
|
|
precision=0
|
|
]{\pgfmathresult}}}
|
|
|
|
\node at (\a*3 - 0.75,2) {$a_{\b}$};
|
|
\draw (\a*3 - 0.75,1.7) -- (\a*3 - 0.75,1);
|
|
\node at (\a*3,2) {$b_\b$};
|
|
\draw (\a*3,1.7) -- (\a*3,1);
|
|
|
|
\draw[black, thick] (-1 + \a*3,-1) rectangle (\a*3 + 1,1);
|
|
|
|
\ifnum\a<3
|
|
\node at (\a*3 + 1,2) {$c_{in_\b}$};
|
|
\draw (\a*3 + 0.75,1.7) -- (\a*3 + 0.75,1);
|
|
\draw (\a*3 + 0.75,1.7) -- (\a*3 + 1.25,1.7) -- (\a*3 + 1.5,-1.5)
|
|
-- (\a*3 + 2.5,-1.5) -- (\a*3 + 2.5,-1);
|
|
\node[font=\huge\sffamily] at (\a*3, 0) {VA};
|
|
\fi
|
|
\ifnum\a>2
|
|
\node[font=\huge\sffamily] at (\a*3, 0) {HA};
|
|
\fi
|
|
|
|
\node at (\a*3 + 0.25,-2) {$s_\b$};
|
|
\draw (\a*3 + 0.25,-1.7) -- (\a*3 + 0.25,-1);
|
|
}
|
|
\node at (-0.5,-2) {$s_4$};
|
|
\node[font=\small\sffamily] at (-1,-2.5) {\enquote{Überlauf}};
|
|
\draw (-0.5,-1.7) -- (-0.5,-1);
|
|
\end{tikzpicture}
|
|
\vspace{1cm}
|
|
\begin{tikzpicture}[font=\sffamily]
|
|
\draw[black, thick] (0,0) rectangle (10,2);
|
|
|
|
\foreach \a in {0,...,3} {
|
|
\node at (\a + 1,3) {$a_\a$};
|
|
\draw (\a + 1,2.7) -- (\a + 1,2);
|
|
\node at (\a + 6,3) {$b_\a$};
|
|
\draw (\a + 6,2.7) -- (\a + 6,2);
|
|
}
|
|
\foreach \a in {0,...,4} {
|
|
\node at (\a*2 + 1,-1) {$s_\a$};
|
|
\draw (\a*2 + 1,-0.7) -- (\a*2 + 1,0);
|
|
}
|
|
\node[font=\huge\sffamily] at (5, 1) {4-Bit-RC-PA};
|
|
\end{tikzpicture}
|
|
|
|
\caption{RC-Paralleladdierer -- Schaltnetz und Schaltsymbol}
|
|
\label{fig:paralleladdierer_rc}
|
|
\end{figure}
|
|
|
|
\begin{Hinweis}[frametitle={Hinweis: Schaltnetz}]
|
|
Ein $n$-Bit \acs{RC-PA} ist ein Schaltnetz, kein Schaltwerk! Eine zeichnerische Anordnung mit Verbindungen nur nach unten ist nämlich möglich.
|
|
\end{Hinweis}
|
|
|
|
\subsection{Hardwareaufwand des 4~Bit RC-PA}
|
|
|
|
\noindent\begin{tabular}{@{}l@{}ll}
|
|
Aufwand für einen \acs{HA}: & \quad 2 Tr. für $c_{out}$ und 6 Tr. für $s$ & $\Rightarrow$ 8 Transistoren \\
|
|
Aufwand für einen \acs{VA}: & \quad 2 \acs{HA} und 2 Transistoren für $c_{out}$ & $\Rightarrow$ $2\cdot8+2=18$ Transistoren
|
|
\end{tabular}
|
|
|
|
\textit{Für den 4~Bit \acs{RC-PA} werden benötigt:}
|
|
|
|
\begin{tabular}{@{}lcl}
|
|
1 \acs{HA} + $(n-1)$ \acs{VA} & $\Rightarrow$ & 8 Transistoren + $(n-1) \cdot 18~\text{Transistoren}$ \\
|
|
& $\Rightarrow$ & $8 + (18n - 18) $~Transistoren $ = 18n - 10$~Transistoren \\
|
|
& $ = $ & $O(n)$
|
|
\end{tabular}
|
|
|
|
Dies heißt, dass der \acs{HW}-Aufwand linear mit der Breite der Summanden steigt. Dies ist gut, denn besseres (also weniger Aufwand) ist kaum zu erwarten.
|
|
|
|
\subsection{Zeitaufwand des 4~Bit RC-PA}
|
|
|
|
Aufwand für \acs{HA}: max. 2 \acfp{GLZ} (\enquote{Tiefe 2}, siehe \autoref{fig:halbaddierer} auf \autopageref{fig:halbaddierer}) \newline
|
|
Aufwand für \acs{VA}:\, max. 4 \acfp{GLZ}
|
|
|
|
Beim \acs{RC-PA} liegen die einzelnen $s_i$ nach unterschiedlicher Zeit an. $s_i$ wird nach $(i+1)\cdot 2$ \acs{GLZ} erreicht.
|
|
Das längste $s_i$ ist beim $n$-Bit-\acs{RC-PA} $i=n-1$ und damit ergibt sich ein Zeitaufwand bei $n$-Bit-\acs{RC-PA} von $2n$~\acl{GLZ}!
|
|
|
|
Dies ist ein schlechter Zeitaufwand bei einem Paralleladdierer, denn zu erwarten wäre $O(1)$! \newline
|
|
\textit{Auswirkung}: Beim Wechsel von 32- auf 64-Bit-\acs{CPU} hätte sich die Taktfrequenz halbiert. Daraus lässt sich folgern, dass kein 64-Bit-\acs{RC-PA} in der \acs{CPU} verbaut ist.
|
|
\medskip
|
|
|
|
\begin{Hinweis}
|
|
Anmerkung zum \acs{RC-PA}: Die $2n$ \acs{GLZ} Zeitaufwand werden nur im \enquote{schlimmsten Fall} bei einer ununterbrochene Kette von $c_{out}$-Ausgängen, welche sich \textbf{alle} im Laufe der Berechnung von \texttt{0} auf \texttt{1} ändern, erreicht.
|
|
|
|
Diese Zeit muss aber trotzdem abgewartet werden!
|
|
\end{Hinweis}
|
|
|
|
\section{Paralleladdierer (4-Bit-Carry-Look-Ahead-Paralleladdierer CLA-PA)} \index{Paralleladdierer!CLA-PA}
|
|
\textit{Idee}: Der $c_{in}$-Eingang wird nicht von vorausgehenden \acs{VA} (oder \acs{HA}) übernommen, sondern durch ein \enquote{magisches CLA-Schaltnetz} nachberechnet. \textit{Genauer}: Für die Berechnung von $c_{in_i}$ müssen alle vorherigen Eingänge $a_j, b_j, j < i$ berücksichtigt werden. \autoref{fig:paralleladdierer_cla} zeigt dieses \enquote{magische CLA-Schaltnetz}.
|
|
|
|
\begin{figure}[ht]
|
|
\centering
|
|
\begin{tikzpicture}[font=\sffamily]
|
|
\foreach \a in {0,...,3} {
|
|
% Calculate the index
|
|
\def\b{{\pgfmathparse{3-\a} % Evaluate the expression
|
|
\pgfmathprintnumber[ % Print the result
|
|
fixed,
|
|
fixed zerofill,
|
|
precision=0
|
|
]{\pgfmathresult}}}
|
|
|
|
\node at (\a*3 - 0.75,2) {$a_{\b}$};
|
|
\draw (\a*3 - 0.75,1.7) -- (\a*3 - 0.75,1);
|
|
\node at (\a*3,2) {$b_\b$};
|
|
\draw (\a*3,1.7) -- (\a*3,1);
|
|
|
|
\draw[black, thick] (-1 + \a*3,-1) rectangle (\a*3 + 1,1);
|
|
|
|
\ifnum\a<3
|
|
\draw (\a*3 + 0.55,2.2) rectangle (\a*3 + 0.95,1.7);
|
|
\node at (\a*3 + 0.75,1.9) {?};
|
|
\node at (\a*3 + 1.2,1.4) {$c_{in_\b}$};
|
|
\draw (\a*3 + 0.75,1.7) -- (\a*3 + 0.75,1);
|
|
\node[font=\huge\sffamily] at (\a*3, 0) {VA};
|
|
\fi
|
|
\ifnum\a>2
|
|
\node[font=\huge\sffamily] at (\a*3, 0) {HA};
|
|
\fi
|
|
|
|
\node at (\a*3 + 0.25,-2) {$s_\b$};
|
|
\draw (\a*3 + 0.25,-1.7) -- (\a*3 + 0.25,-1);
|
|
}
|
|
\node at (-0.5,-2) {$s_4$};
|
|
\node[font=\small\sffamily] at (-1,-2.5) {\enquote{Überlauf}};
|
|
\draw (-0.5,-1.7) -- (-0.5,-1);
|
|
\end{tikzpicture}
|
|
\caption{Carry-Look-Ahead-Paralleladdierer -- \enquote{magisches} Schaltnetz}
|
|
\label{fig:paralleladdierer_cla}
|
|
\end{figure}
|
|
|
|
Aber wie sieht das Schaltnetz (und die boolesche Formel) für die Berechnung von $c_{in_i}$ aus?
|
|
\begin{align*}
|
|
\text{\acs{HA}}:~ c_{out} & = a\wedge b & \\
|
|
s_{out} & = a\overline{b}\vee\overline{a}b & \\
|
|
\text{\acs{VA}}:~ c_{out} & = (a\wedge b)\vee(c_{in}\wedge(a\overline{b}\vee\overline{a}b)) & \\
|
|
& & \\
|
|
c_{in_1} = c_{out_0} & = a_0\wedge b_0 & \textit{\qquad \acs{HA}} \\
|
|
c_{in_2} = c_{out_1} & = (a_1\wedge b_1)\vee(\textcolor{Blue}{c_{in_1}} \wedge (a_1\overline{b}_1\vee\overline{a}_1b_1)) & \textit{\acs{VA}} \\
|
|
& =(a_1\wedge b_1)\vee(\textcolor{Blue}{a_0\wedge b_0} \wedge(a_1\overline{b}_1\vee\overline{a}_1b_1)) & \textit{Einsetzen} \\
|
|
c_{in_3} = c_{out_2} & = (a_2\wedge b_2)\vee(\textcolor{OliveGreen}{c_{in_2}} \wedge(a_2\overline{b}_2\vee\overline{a}_2b_2)) & \textit{\acs{VA}} \\
|
|
& = (a_2\wedge b_2)\vee \textcolor{OliveGreen}{((a_1\wedge b_1)\vee(a_0\wedge b_0\wedge(a_1\overline{b}_1\vee\overline{a}_1b_1))} \wedge & \textit{Einsetzen} \\
|
|
& \hspace{4mm} (a_2\overline{b}_2\vee\overline{a}_2b_2)) \cdots & \\
|
|
\cdots & &
|
|
\end{align*}
|
|
|
|
\subsection{Zeitaufwand}
|
|
Für die Berechnung der $c_{in_i}$ kann jeweils eine \acs{DNF}, \acs{DMF} oder jede andere DxF (oder KxF) verwendet werden. Diese haben jeweils nur genau (bzw. maximal) 2~\acs{GLZ} Zeitaufwand.
|
|
|
|
Insgesamt hat jedes $s_i$ beim \acs{CLA-PA} genau 6~\acs{GLZ} Zeitaufwand (außer $s_0$:~2~\acs{GLZ}, $s_1$:~5~\acs{GLZ}). \newline
|
|
Somit haben wir einen konstanten Zeitaufwand von $O(1)$.
|
|
|
|
\subsection{Hardwareaufwand des 4~Bit CLA-PA}
|
|
Für den Aufwand für die $c_{in_i}$-Berechnung gilt die Annahme, das Schaltnetz wäre eine Realisierung der \acs{DNF}.
|
|
|
|
\begin{itemize}[noitemsep]
|
|
\item[$\Rightarrow$] Für jedes $c_{in_i}$ gibt es insgesamt $2i$ Eingänge.
|
|
\item[$\Rightarrow$] Insgesamt gibt es max. $2^{2i}$ verschiedene Vollkonjunktionen für ein $c_{in_i}$, welche in der \acs{DNF} auftreten können (\enquote{Zeilen in der Wertetabelle}). \newline
|
|
Jede dieser Vollkonjunktionen wird mit $2i$ Transistoren realisiert.
|
|
\item[$\Rightarrow$] Falls alle Vollkonjunktionen verwendet werden müssten, wäre der Hardwareaufwand \newline
|
|
$2^{2i}\cdot 2i$ Transistoren $= 2i\cdot 4^{i} = O(n\cdot 4^{n})$.
|
|
\end{itemize}
|
|
|
|
In der Realität werden natürlich nicht alle Vollkonjunktionen benötigt, sondern ein (vermutlich halbwegs konstanter) Anteil $0 < k < i$. Damit ist der Aufwand für $c_{in_i} = O(i\cdot4^i)$ und somit der Aufwand für $n$-Bit-\acs{CLA-PA}: $O(n\cdot n\cdot4^n)=O(n^2\cdot4^n)$
|
|
|
|
\newpage % Nur für's Layout
|
|
|
|
\begin{Achtung}
|
|
Im folgenden wird fälschlicherweise von einem Aufwand $O(n^2\cdot 2^n)$ ausgegangen. Richtig wäre $O(n^2\cdot 4^n)$. Herr Röthig hat die $O$-Notation falsch vereinfacht. Der 2015er Jahrgang hat dies \enquote{noch falscher} gemacht und zu $O(4^n)$ vereinfacht.
|
|
\end{Achtung}
|
|
|
|
Der Hardwareaufwand steigt beim $n$-Bit-\acs{CLA-PA} überexponentiell mit $n$.
|
|
Beim Wechsel von $32$-Bit auf 64-Bit-\acs{CLA-PA} wäre der 16~Trillionen-fache Aufwand an Transistoren nötig gewesen.
|
|
|
|
\begin{tabular}{@{}l@{}c@{}c@{}l}
|
|
Bei $n=4$: \quad $4^2\cdot 2^4=$~ & $16\cdot 16$~ $=$ & $256$ & ~Transistoren \\
|
|
Bei $n=8$: \quad $8^2\cdot 2^8=$~ & $64\cdot 256=$ & ~ \circa{$16384$} & ~Transistoren (64-fache von $n=4$) $\Rightarrow$ \textit{zu viel für die \acs{CPU}}
|
|
\end{tabular}
|
|
|
|
\subsection{Kombination mehrerer kleinen \acsp{CLA-PA}}
|
|
|
|
Der 32-Bit Addierer wird in acht 4-Bit-\acs{CLA-PA} gesplittet (siehe \autoref{fig:casc_cla_ca}).
|
|
|
|
$\Rightarrow$ hintereinander geschaltet nach RC-Prinzip \newline
|
|
$\Rightarrow$ damit ist das $n$ der nicht-\acs{CLA-PA} noch klein $\Rightarrow$ erträglicher Hardwareaufwand \newline
|
|
|
|
\begin{figure}[ht]
|
|
\centering
|
|
\begin{tikzpicture}[font=\sffamily,scale=1.3]
|
|
\foreach \a in {0,...,3} {
|
|
% Calculate the index
|
|
\def\b{{\pgfmathparse{3-\a} % Evaluate the expression
|
|
\pgfmathprintnumber[ % Print the result
|
|
fixed,
|
|
fixed zerofill,
|
|
precision=0
|
|
]{\pgfmathresult}}}
|
|
\def\cstart{{\pgfmathparse{(3-\a)*4}
|
|
\pgfmathprintnumber[
|
|
fixed,
|
|
fixed zerofill,
|
|
precision=0
|
|
]{\pgfmathresult}}}
|
|
\def\cend{{\pgfmathparse{(3-\a)*4+3}
|
|
\pgfmathprintnumber[
|
|
fixed,
|
|
fixed zerofill,
|
|
precision=0
|
|
]{\pgfmathresult}}}
|
|
|
|
\node[font=\small] at (\a*3 - 0.9,1.5) {$a_{\cend}$};
|
|
\draw (\a*3 - 0.9,1.2) -- (\a*3 - 0.9,0.5);
|
|
\node[font=\small] at (\a*3 - 0.5,1.5) {$b_\cend$};
|
|
\draw (\a*3 - 0.5,1.2) -- (\a*3 - 0.5,0.5);
|
|
|
|
\node[font=\small] at (\a*3 + 0.8,1.5) {$b_{\cstart}$};
|
|
\draw (\a*3 + 0.8,1.2) -- (\a*3 + 0.8,0.5);
|
|
\node[font=\small] at (\a*3 + 0.4,1.5) {$a_\cstart$};
|
|
\draw (\a*3 + 0.4,1.2) -- (\a*3 + 0.4,0.5);
|
|
|
|
\node[font=\small] at (\a*3,1.5) {\ldots};
|
|
\draw (\a*3,1.2) -- (\a*3,0.5);
|
|
|
|
\draw[black, thick] (-1 + \a*3,-1) rectangle (\a*3 + 1,0.5);
|
|
|
|
\ifnum\a<3
|
|
\draw (\a*3 + 0.95,1.1) -- (\a*3 + 0.95,0.5);
|
|
\draw (\a*3 + 0.95,1.1) -- (\a*3 + 1.25,1.1) -- (\a*3 + 1.5,-1.5)
|
|
-- (\a*3 + 2.5,-1.5) -- (\a*3 + 2.5,-1);
|
|
|
|
\node[font=\small\sffamily] at (\a*3, 0) {kaskadierbarer};
|
|
\node[font=\small\sffamily] at (\a*3, -0.4) {4~Bit~CLA-PA};
|
|
\fi
|
|
\ifnum\a>2
|
|
\node[font=\small\sffamily] at (\a*3, -0.2) {4~Bit~CLA-PA};
|
|
\fi
|
|
|
|
\node[font=\small] at (\a*3 - 0.35,-2) {$s_\cend$};
|
|
\draw (\a*3 - 0.35,-1.7) -- (\a*3 - 0.35,-1);
|
|
\node[font=\small] at (\a*3 + 0.8,-2) {$s_\cstart$};
|
|
\draw (\a*3 + 0.8,-1.7) -- (\a*3 + 0.8,-1);
|
|
\node[font=\small] at (\a*3 + 0.2,-2) {\ldots};
|
|
\draw (\a*3 + 0.2,-1.7) -- (\a*3 + 0.2,-1);
|
|
}
|
|
\node[font=\small] at (-0.9,-2) {$s_{16}$};
|
|
\node[font=\small\sffamily] at (-1.2,-2.5) {\enquote{Überlauf}};
|
|
\draw (-0.9,-1.7) -- (-0.9,-1);
|
|
\end{tikzpicture}
|
|
\caption{Kaskadierbarer 4-Bit-CLA-PA}
|
|
\label{fig:casc_cla_ca}
|
|
\end{figure}
|
|
|
|
\newpage % Für das Layout
|
|
|
|
\section{Serielladdierer} \index{Serielladdierer}
|
|
\textit{Idee}: Angelehnt an die Verfahrensweise des Menschen sollen die Stellen der beiden Summanden nacheinander (und nicht gleichzeitig) addiert werden. Dadurch wird nur \textbf{ein} \acf{VA} und mehrere \acf{SR} benötigt. Daher ist der \acf{SA} ein Schaltwerk, kein Schaltnetz! \autoref{fig:serielladdierer} zeigt das Schaltwerk eines Serielladdierers.
|
|
|
|
\begin{figure}[h!]
|
|
\centering
|
|
\begin{tikzpicture}[font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
|
|
% Rechteck | VA
|
|
\draw (-2, -1.35) rectangle ++(4,3);
|
|
\node at (0,0) (VA) {VA};
|
|
\node at (-1.63,1.15) (cin) {$c_{in}$};
|
|
\node at (-1.7,0) (b) {$b$};
|
|
\node at (-1.7,-0.9) (a) {$a$};
|
|
\node at (1.56,1.15) (cout) {$c_{out}$};
|
|
\node at (1.7,-0.9) (s) {$s$};
|
|
|
|
% Register Eingang
|
|
\draw (-2.7,-0.2) rectangle ++(-2.1,0.5);
|
|
\draw (-2.7,0.05) -- ++(0.7,0);
|
|
\node at (-3.6, 0.05) {$n$-Bit SR};
|
|
\draw (-4.8, -0.15) -- ++(0.3,0.20) -- ++(-0.3,0.20); % Takt
|
|
\node at (-2.7, 0.78) {$b_{0}$};
|
|
\node at (-4.8, 0.8) {$b_{n-1}$};
|
|
|
|
\draw (-2.7,-1.2) rectangle ++(-2.1,0.5);
|
|
\draw (-2.7,-0.95) -- ++(0.7,0);
|
|
\node at (-3.6, -0.95) {$n$-Bit SR};
|
|
\draw (-4.8, -1.15) -- ++(0.3,0.20) -- ++(-0.3,0.20); % Takt
|
|
\node at (-2.7, -1.75) {$a_{0}$};
|
|
\node at (-4.8, -1.75) {$a_{n-1}$};
|
|
\foreach \a in {0,...,7} {
|
|
\draw ($(-2.7,0.3)+(\a*-0.3,0)$) -- ++(0,0.3);
|
|
\draw ($(-2.7,-1.2)+(\a*-0.3,0)$) -- ++(0,-0.3);
|
|
}
|
|
|
|
% Register Ausgang
|
|
\draw (2.7,-1.2) rectangle ++(2.1,0.5);
|
|
\draw (2.7,-0.95) -- ++(-0.7,0);
|
|
\node at (3.6, -0.95) {$n$-Bit SR};
|
|
\foreach \a in {0,...,7} {
|
|
\draw ($(2.7,-0.7)+(\a*0.3,0)$) -- ++(0,0.3);
|
|
}
|
|
\draw (4.8, -1.15) -- ++(-0.3,0.20) -- ++(0.3,0.20); % Takt
|
|
\node at (2.7, -0.25) {$s_{n-1}$};
|
|
\node at (4.8, -0.25) {$s_{0}$};
|
|
|
|
% Beide D-FF
|
|
\draw (-3, 2.5) rectangle ++(2,1.5);
|
|
\node at (-1.3, 2.8) {D};
|
|
\node at (-2.7, 2.8) {Q};
|
|
\draw (-1, 3.4) -- ++(-0.3,0.24) -- ++(0.3,0.24); % Takt
|
|
\draw (-3,2.7) -- ++(-0.75,0) |- (cin);
|
|
|
|
\draw (1, 2.5) rectangle ++(2,1.5);
|
|
\node at (2.7, 2.8) {D};
|
|
\node at (1.3, 2.8) {Q};
|
|
\draw (3, 3.4) -- ++(-0.3,0.24) -- ++(0.3,0.24); % Takt
|
|
\draw (3,2.7) -- ++(0.75,0) |- (cout);
|
|
|
|
\draw (-1,2.8) -- ++(2,0);
|
|
\node at (0,2.2) {$s_n$};
|
|
\draw (0,2.8) -- ++(0,-0.4);
|
|
\node[knoten] at (0,2.8) {};
|
|
|
|
% Gate: NOT
|
|
\node[not gate] at (0.5,5) (NOT) {};
|
|
\node[knoten] at (-5.5, 5) {};
|
|
\node[knoten] at (-0.5, 5) (d1k) {};
|
|
\draw (d1k) |- ++(-0.5,-1.3);
|
|
|
|
\node[knoten] at (3.5, 5) (d2k) {};
|
|
\draw (d2k) |- ++(-0.5,-1.3);
|
|
|
|
% Äußere "Linien"
|
|
\draw (-5.5, 5.5) -- ++(0, -6.5) -- ++(0.7, 0); % außen links
|
|
\draw (-5.5, 0) -- ++(0.7,0);
|
|
\node[knoten] at (-5.5, 0) (d1k) {};
|
|
\draw (-5.5, 5) -- (NOT.input);
|
|
\draw (5.5, 5) -- ++(0, -6) -- ++(-0.7, 0); % außen rechts
|
|
\draw (5.5, 5) -- (NOT.output);
|
|
|
|
% Hinweistexte
|
|
\node at (-5.5,5.8) {Takt};
|
|
\node at (-3,5.3) {Eingangstakt};
|
|
\node at (3,5.3) {Ausgangstakt};
|
|
|
|
\end{tikzpicture}
|
|
\caption{Serielladdierer}
|
|
\label{fig:serielladdierer}
|
|
\end{figure}
|
|
|
|
\subsection{Zeitaufwand ($n$-Bit-SA)}
|
|
|
|
Der Zeitaufwand für einen $n$-Bit-\acl{SA} beträgt $n$ Taktzyklen, also $O(n)$
|
|
|
|
\textit{Ist dies wie beim \acs{RC-PA}?} \newline
|
|
Jein, denn $1$ Taktzyklus dauert deutlich mehr als doppelt solang wie die Berechnung des \acs{VA} (Sicherheitsmargen!). Beispiel: 1 Taktzyklus > \circa{10}~\acs{GLZ} $\Rightarrow$ fünffache Berechnungszeit des \acs{RC-PA}
|
|
|
|
\subsection{Hardwareaufwand ($n$-Bit-SA)}
|
|
|
|
\begin{tabular}{@{}l@{}l}
|
|
1 \acs{VA} & $ =18$ Transistoren \\
|
|
2 \acs{D-FF} = $2\cdot 6$ & $ =12$ Transistoren. \hspace*{12.5mm} \textit{(siehe \autoref{fig:aufwand_dff})} \\
|
|
3 $n$-Bit-\acs{SR} & $ =3\cdot 6n = 18n$ Transistoren \textit{(siehe \autoref{fig:schieberegister})} \\
|
|
Takterzeugung~~ & \textit{(im folgenden nicht näher betrachtet)} \\
|
|
\textbf{gesamt} & $18n+30$ Transistoren
|
|
\end{tabular}
|
|
|
|
Zum Vergleich: \acs{RC-PA}: $18n-10$, \dash der \acl{SA} braucht 40 Transistoren mehr (bei längerer Bearbeitungszeit)!
|
|
|
|
|
|
\begin{figure}[h!]
|
|
\centering
|
|
\begin{subfigure}[h]{0.47\textwidth}
|
|
\medskip
|
|
\includegraphics[width=\textwidth]{Bilder/Serielladdierer_2.png}
|
|
\medskip
|
|
\caption{4-Bit Schieberegister}
|
|
\label{fig:schieberegister}
|
|
\end{subfigure}
|
|
~
|
|
\begin{subfigure}[h]{0.47\textwidth}
|
|
\begin{tikzpicture}[scale=0.9,font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
\node[nand gate, inputs={inn}] at (0,1) (NAND1) {};
|
|
\node[nand gate, inputs={nnn}] at (0,-1) (NAND2) {};
|
|
|
|
\node at (-2,0) (T) {T};
|
|
\node[right=of NAND1] (Q1) {Q*};
|
|
\node[right=of NAND2] (Q2) {Q~};
|
|
|
|
\node[knoten] at ($(Q1)+(-0.6,0)$) (K2) {};
|
|
\node[knoten] at ($(Q2)+(-0.6,0)$) (K3) {};
|
|
\draw (K2) -- ($(K2)+(0,-0.7)$)
|
|
-- ($(NAND2.input 2) + (-0.4,0.5)$)
|
|
|- (NAND2.input 1);
|
|
\draw (K3) -- ($(K3)+(0,0.7)$)
|
|
-- ($(NAND1.input 3) + (-0.4,-0.5)$)
|
|
|- (NAND1.input 3);
|
|
|
|
\node[] at ($(NAND2.input 3) + (-2.8,0)$) (D) {D};
|
|
|
|
\draw (T) -- ($(T)+(1,0)$) |- (NAND1.input 2);
|
|
\draw ($(T)+(1,0)$) |- (NAND2.input 2);
|
|
\node[knoten] at ($(T)+(1,0)$) {};
|
|
\draw (Q1) -- (NAND1.output) (Q2) -- (NAND2.output);
|
|
|
|
\draw (NAND1.input 1) -- ($(NAND1.input 1) + (-2,0)$) |- ($(NAND2.input 3) + (-2,0)$) -- (NAND2.input 3);
|
|
\draw ($(NAND2.input 3) + (-2,0)$) -- ($(NAND2.input 3) + (-2.4,0)$);
|
|
\node[knoten] at ($(NAND2.input 3) + (-2.12,0)$) {};
|
|
\end{tikzpicture}
|
|
\caption{Hardwareaufwand für einen D-FF: 6 Tr.}
|
|
\label{fig:aufwand_dff}
|
|
\end{subfigure}
|
|
\caption{Schieberegister aus D-FF mit Hardwareaufwand}
|
|
\end{figure}
|
|
|
|
\begin{Achtung}
|
|
Die Takterzeugung muss in der Klausur für den \acl{SA} auf jeden Fall genannt werden, auch wenn sie hier nicht weiter betrachtet wird!
|
|
\end{Achtung}
|
|
|
|
\subsection{Hardwareoptimierung des Serielladdierers}
|
|
|
|
\begin{figure}[ht]
|
|
\centering
|
|
\begin{tikzpicture}[font=\sffamily, circuit logic IEC, large circuit symbols,
|
|
knoten/.style={circle,fill,draw,inner sep=0pt,minimum size=1.5mm}]
|
|
% Rechteck | VA
|
|
\draw (-2, -1.35) rectangle ++(4,3);
|
|
\node at (0,0) (VA) {VA};
|
|
\node at (-1.63,1.15) (cin) {$c_{in}$};
|
|
\node at (-1.7,0) (b) {$b$};
|
|
\node at (-1.7,-0.9) (a) {$a$};
|
|
\node at (1.56,1.15) (cout) {$c_{out}$};
|
|
\node at (1.7,-0.9) (s) {$s$};
|
|
|
|
% Register Eingang
|
|
\draw (-2.7,-0.2) rectangle ++(-2.1,0.5);
|
|
\draw (-2.7,0.05) -- ++(0.7,0);
|
|
\node at (-3.6, 0.05) {$n$-Bit SR};
|
|
\draw (-4.8, -0.15) -- ++(0.3,0.20) -- ++(-0.3,0.20); % Takt
|
|
\node at (-2.7, 0.78) {$b_{0}$};
|
|
\node at (-4.8, 0.8) {$b_{n-1}$};
|
|
|
|
\draw (-2.7,-1.2) rectangle ++(-2.1,0.5);
|
|
\draw (-2.7,-0.95) -- ++(0.7,0);
|
|
\node at (-3.6, -0.95) {$n$-Bit SR};
|
|
\draw (-4.8, -0.95) -- ++(0.3,0.10) -- ++(-0.3,0.10); % Takt
|
|
\node at (-2.7, -1.75) {$s_{0}$};
|
|
\node at (-4.8, -1.75) {$s_{n-1}$};
|
|
\foreach \a in {0,...,7} {
|
|
\draw ($(-2.7,0.3)+(\a*-0.3,0)$) -- ++(0,0.3);
|
|
\draw ($(-2.7,-1.2)+(\a*-0.3,0)$) -- ++(0,-0.3);
|
|
}
|
|
|
|
% Beide D-FF
|
|
\draw (-3, 2.5) rectangle ++(2,1.5);
|
|
\node at (-1.3, 2.8) {D};
|
|
\node at (-2.7, 2.8) {Q};
|
|
\draw (-1, 3.4) -- ++(-0.3,0.24) -- ++(0.3,0.24); % Takt
|
|
\draw (-3,2.7) -- ++(-0.75,0) |- (cin);
|
|
|
|
\draw (1, 2.5) rectangle ++(2,1.5);
|
|
\node at (2.7, 2.8) {D};
|
|
\node at (1.3, 2.8) {Q};
|
|
\draw (3, 3.4) -- ++(-0.3,0.24) -- ++(0.3,0.24); % Takt
|
|
\draw (3,2.7) -- ++(0.75,0) |- (cout);
|
|
|
|
\draw (-1,2.8) -- ++(2,0);
|
|
\node at (0,2.2) {$s_n$};
|
|
\draw (0,2.8) -- ++(0,-0.4);
|
|
\node[knoten] at (0,2.8) {};
|
|
|
|
% Gate: NOT
|
|
\node[not gate] at (0.5,5) (NOT) {};
|
|
\node[knoten] at (-5.5, 5) {};
|
|
\node[knoten] at (-0.5, 5) (d1k) {};
|
|
\draw (d1k) |- ++(-0.5,-1.3);
|
|
|
|
\node[knoten] at (3.5, 5) (d2k) {};
|
|
\draw (d2k) |- ++(-0.5,-1.3);
|
|
|
|
% Äußere "Linien"
|
|
\draw (-5.5, 5.5) -- ++(0, -6.35) -- ++(0.7, 0); % außen links
|
|
\draw (-5.5, 0) -- ++(0.7,0);
|
|
\node[knoten] at (-5.5, 0) (d1k) {};
|
|
\draw (-5.5, 5) -- (NOT.input);
|
|
\draw[red] (5.5, 5) -- ++(0, -8) -- ++(-4, 0); % außen rechts
|
|
\draw (5.5, 5) -- (NOT.output);
|
|
|
|
% Hinweistexte
|
|
\node at (-5.5,5.8) {Takt};
|
|
\node at (-3,5.3) {Eingangstakt};
|
|
\node at (3,5.3) {Ausgangstakt};
|
|
|
|
% Neuer D-FF
|
|
\draw[red] (-0.5, -3.5) rectangle ++(2,1.5);
|
|
\node[red] at (1.2, -2.4) {D};
|
|
\node[red] at (-0.2, -2.4) {Q};
|
|
\draw[red] (1.5, -3.3) -- ++(-0.3,0.24) -- ++(0.3,0.24); % Takt
|
|
\draw[red] (1.5, -2.4) -- ++(1,0) |- (s);
|
|
\draw[red] (-0.5, -2.4) -- ++(-5,0) |- ++(0.7,1.3);
|
|
\end{tikzpicture}
|
|
\caption{Serielladdierer mit Hardwareoptimierung}
|
|
\label{fig:serielladdierer_hw_optimierung}
|
|
\end{figure}
|
|
|
|
Wie in \autoref{fig:serielladdierer_hw_optimierung} zu sehen ist, wird ein Schieberegister weniger benötigt \newline
|
|
\hspace*{3mm}$\Rightarrow 12n+36$ Transistoren
|
|
|
|
\newpage % Für's Layout
|
|
|
|
\subsubsection{Vergleich eines RC-PA mit dem verbesserten SA}
|
|
\begin{table}
|
|
\centering
|
|
\begin{tabular}{c|c|c}
|
|
n & \acs{RC-PA} ($18n - 10$) & \acs{SA} ($12n + 36$) \\ \midrule
|
|
1 & 8 & 48 \\
|
|
2 & 26 & 60 \\
|
|
3 & 44 & 72 \\
|
|
4 & 62 & 84
|
|
\end{tabular}
|
|
\caption{Vergleich des Hardwareaufwand eines \acs{RC-PA} mit dem verbesserten \acs{SA}}
|
|
\label{tbl:vergleich_rcpa_sa}
|
|
\end{table}
|
|
|
|
Tabelle \autoref{tbl:vergleich_rcpa_sa} vergleicht einen \acs{RC-PA} mit dem verbesserten \acs{SA}.
|
|
|
|
Break-Even (\enquote{\textit{Gewinnschwelle}}): $18n -10 = 12n + 36 \Rightarrow 46 = 6n \Rightarrow n = 7\frac{2}{3} $ \newline
|
|
\hspace*{3mm} $\Rightarrow$ Ab 8-Bit lohnt sich der \acs{SA}
|
|
|
|
\textbf{Mögliche Anwendung eines \acl{SA}}:
|
|
\begin{itemize}[noitemsep]
|
|
\item nicht im Rechenwerk der \acs{CPU} (aufgrund der Geschwindigkeit)!
|
|
\item aber möglicherweise in \enquote{embedded systems}, falls \zB Sensordaten sowieso seriell angeliefert werden
|
|
\item[$\Rightarrow$] eventuell sind sogar weitere Hardware-Einsparungen möglich!
|
|
\end{itemize}
|
|
|
|
|
|
\section{Subtraktion} \index{Subtraktion}
|
|
Es ist kein spezieller Hardware-Subtrahierer notwendig. Eine Subtraktion wird über die Addition des 2er-Komplements realisiert:
|
|
|
|
\begin{enumerate}[noitemsep]
|
|
\item Bits invertieren (Inverter)
|
|
\item $+1$ addieren (Addierer)
|
|
\end{enumerate}
|
|
|
|
\begin{figure}[ht]
|
|
\centering
|
|
\includegraphics[width=13cm]{Bilder/Subtrahierer.png}
|
|
\caption{Schaltnetz Subtrahierer}
|
|
\label{fig:subtraktion}
|
|
\end{figure}
|
|
|
|
\newpage % Nur für's Layout
|
|
|
|
\section{Multiplikation} \index{Multiplikation}
|
|
|
|
\columnratio{0.17}
|
|
\begin{paracol}{2}
|
|
\begin{tabular}{c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}}
|
|
4 & 7 & 1 & 1 & $\times$ & 8 & 1 & 5 \\ \midrule
|
|
& \textit{\small 3} & \textit{\small 5} & & & & & \\
|
|
& 6 & 7 & 6 & 8 & 8 & & \\
|
|
& & & 4 & 7 & 1 & 1 & \\
|
|
& & & \textit{\small 2} & \textit{\small 3} & & & \\
|
|
& & & 2 & 3 & 5 & 5 & 5 \\ \midrule
|
|
& 3 & 8 & 3 & 9 & 4 & 6 & 5
|
|
\end{tabular}
|
|
\switchcolumn
|
|
\textbf{\textsf{Mögliche Probleme / Schwierigkeiten}}
|
|
\begin{enumerate}[noitemsep]
|
|
\item kleines $1\times 1$ ist ein wenig Lernaufwand
|
|
\item Überträge beim kleinen $1\times 1$ sind möglich
|
|
\item Addition von mehr als zwei Ziffern gleichzeitig
|
|
\item mehrstellige Überträge bei der Summenbildung möglich
|
|
\item \label{lst:item:zwischensumme_stellen} für jede Zwischensumme muss der Addierer eine Stelle mehr verarbeiten
|
|
\end{enumerate}
|
|
\end{paracol}
|
|
|
|
\autoref{lst:item:zwischensumme_stellen} wird deutlich durch eine Multiplikation einer 6- und 4-stelligen Zahl im Binärsystem \enquote{von links nach rechts}, wie sie in \autoref{tbl:multi_lr} dargestellt wird.
|
|
\begin{table}[ht]
|
|
\centering
|
|
\begin{tabular}{c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}l}
|
|
1 & 0 & 1 & 0 & 1 & 0 & $\times$ & 1 & 0 & 1 & 0 & \quad ($42\times 10$) \\ \midrule
|
|
& & 1 & 0 & 1 & 0 & 1 & 0 & & & & \\
|
|
& & & 0 & 0 & 0 & 0 & 0 & 0 & & & \quad \textit{7-stellige Addition} \\ \midrule
|
|
& & 1 & 0 & 1 & 0 & 1 & 0 & 0 & & & \quad \textit{Zwischensumme} \\
|
|
& & & & 1 & 0 & 1 & 0 & 1 & 0 & & \quad \textit{8-stellige Addition} \\ \midrule
|
|
& & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & & \quad \textit{Zwischensumme} \\
|
|
& & & & & 0 & 0 & 0 & 0 & 0 & 0 & \quad \textit{9-stellige Addition} \\ \midrule
|
|
& & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & \quad \textit{10-stelliges Ergebnis (Übertrag: 0)}
|
|
\end{tabular}
|
|
\caption{Schriftliche Multiplikation \enquote{von links nach rechts}}
|
|
\label{tbl:multi_lr}
|
|
\end{table}
|
|
|
|
\columnratio{0.17}
|
|
\begin{paracol}{2}
|
|
\bigskip
|
|
\begin{center}
|
|
\begin{tabular}{cc|c}
|
|
b & a & ab \\
|
|
\midrule
|
|
0 & 0 & 0 \\
|
|
0 & 1 & 0 \\
|
|
1 & 0 & 0 \\
|
|
1 & 1 & 1
|
|
\end{tabular}
|
|
\end{center}
|
|
\switchcolumn
|
|
\textbf{\textsf{Abhilfe}}
|
|
\begin{enumerate}[noitemsep]
|
|
\item Kleines $1\times 1$ im Binärsystem ist ein einfaches \code{UND}
|
|
\item Es gibt keine Überträge beim kleinen $1\times 1$ im Binärsystem
|
|
\item Bilden von Zwischensummen
|
|
\item Keine mehrstelligen Überträge bei Addition von zwei Summanden
|
|
\item Rechten Faktor beginnend mit niederwertigster Stelle abarbeiten, siehe \autoref{tbl:multi_rl}
|
|
\end{enumerate}
|
|
\end{paracol}
|
|
|
|
\begin{table}[ht]
|
|
\centering
|
|
\begin{tabular}{c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c}
|
|
1 & 0 & 1 & 0 & 1 & 0 & $\times$ & 1 & 0 & 1 & 0 & ($42\times 10$) \\ \midrule
|
|
& & & & & 0 & 0 & 0 & 0 & 0 & \textcolor{purple}{\textbf{0}} & \\
|
|
& & & & 1 & 0 & 1 & 0 & 1 & 0 & \textcolor{purple}{$p_0$} & \\ \midrule
|
|
& & & & 1 & 0 & 1 & 0 & 1 & \textcolor{OliveGreen}{\textbf{0}} & & \\
|
|
& & & 0 & 0 & 0 & 0 & 0 & 0 & \textcolor{OliveGreen}{$p_1$} & & \\ \midrule
|
|
& & & 0 & 1 & 0 & 1 & 0 & \textcolor{BrickRed}{\textbf{1}} & & & \\
|
|
& & 1 & 0 & 1 & 0 & 1 & 0 & \textcolor{BrickRed}{$p_2$} & & & \\ \midrule
|
|
& \textcolor{blue}{0} & \textcolor{blue}{1} & \textcolor{blue}{1} & \textcolor{blue}{0} & \textcolor{blue}{1} & \textcolor{blue}{0} & \textcolor{blue}{0} & & & & \\
|
|
& \textcolor{blue}{$p_9$} & \textcolor{blue}{$p_8$} & \textcolor{blue}{$p_7$} & \textcolor{blue}{$p_6$} & \textcolor{blue}{$p_5$} & \textcolor{blue}{$p_4$} & \textcolor{blue}{$p_3$} & & & &
|
|
\end{tabular}
|
|
\caption{Schriftliche Multiplikation \enquote{von rechts nach links}}
|
|
\label{tbl:multi_rl}
|
|
\end{table}
|
|
|
|
\newpage % Nur für's Layout
|
|
|
|
\subsection{Multiplikation mit Paralleladdierer}
|
|
|
|
Ein $n\times m$-Bit-\acf{PM}, bspw. ein $5\times 4$-Bit-\acl{PM} ist in \autoref{fig:parallelmultiplizierer} dargestellt.
|
|
|
|
\begin{figure}[ht]
|
|
\centering
|
|
\includegraphics[width=13cm]{Bilder/Parallelmultiplizierer.png}
|
|
\caption{5-Bit Parallelmultiplizierer}
|
|
\label{fig:parallelmultiplizierer}
|
|
\end{figure}
|
|
|
|
\begin{Achtung}[frametitle={Hinweis zur Abbildung}]
|
|
Unbedingt auf die \enquote{0} als Eingang achten! Ansonsten gibt es in der Klausur punktabzug! Die \enquote{0} ist sogesehen der erste Übertrag.
|
|
\end{Achtung}
|
|
|
|
\begin{Hinweis}
|
|
In der Klausur muss evtl. ein 4-Bit \acl{PM} gezeichnet werden, also nicht mit 5 oder 6~Bit.
|
|
\end{Hinweis}
|
|
|
|
\subsubsection{Analyse: Hardwareaufwand für die Multiplikation mit Paralleladdierer}
|
|
\textit{Benötigt werden}:
|
|
|
|
\begin{itemize}[noitemsep]
|
|
\item $m-1$ ~ $n$-Bit-\acs{PA}
|
|
\item $n\cdot m$ ~~ \code{UND} mit jeweils 2 Eingängen $\Rightarrow$ $2\cdot n\cdot m$ Transistoren
|
|
\end{itemize}
|
|
|
|
\newpage % Nur für's Layout
|
|
|
|
\textit{Somit ergibt sich bei\ldots}
|
|
\begin{enumerate}%[leftmargin=0pt]
|
|
\item[\ldots] Verwendung eines \textbf{\acs{RC-PA}}:
|
|
\begin{itemize}[noitemsep]
|
|
\item[$\Rightarrow$] $n$-Bit-\acs{RC-PA}: ~ $18n-10$ Transistoren
|
|
\item[$\Rightarrow$] davon $m-1$: $(m-1)(18n-10)$ Transistoren = $18nm-18n-10m+10$ Transistoren
|
|
\item[$\Rightarrow$] Insgesamt: ~~~ $20nm-18n-10m+10$ Transistoren $\Rightarrow O(nm)$
|
|
\end{itemize}
|
|
|
|
\item[\ldots] Verwendung eines \textbf{\acs{CLA-PA}}
|
|
\begin{itemize}[noitemsep]
|
|
\item $n$-Bit-\acs{CLA-PA}: $\approx O(n\cdot 2^n)$ \textit{(Achtung: eigentlich $O(n^2\cdot 4^n)$)}
|
|
\item[$\Rightarrow$] davon $m-1$: ~ $(m-1)\cdot O(n\cdot 2^n) = O(n\cdot m\cdot 2^n)$
|
|
\end{itemize}
|
|
\end{enumerate}
|
|
|
|
Hier bei verschieden großen Faktoren also besser $m>n$ bei \ac{CLA-PA} für einen geringeren \acs{HW}-Aufwand.
|
|
|
|
Demgegenüber sollte bei Verwendung von \acs{RC-PA} besser $n>m$ für geringeren \acs{HW}-Aufwand sein.
|
|
|
|
\subsubsection{Analyse: Zeitaufwand für die Multiplikation mit Paralleladdierer}
|
|
1 \acs{GLZ} für einstellige Multiplikation (\code{UND}-Gatter) sowie $(m-1)~\times$ Berechnungszeit($n$-Bit-\acs{PA})
|
|
|
|
\begin{enumerate}
|
|
\item Annahme: \acs{PA} sind $n$-Bit-\acs{RC-PA}. \newline
|
|
Berechnungszeit eines $n$-Bit-\acs{RC-PA}: $2n$ \acs{GLZ} \newline
|
|
Insgesamt: $1+(m-1)\cdot 2n=2nm-2n+1$ \acs{GLZ} \newline
|
|
Damit besser $n>m$ bei Verwendung von \acs{RC-PA}, um geringeren Zeitaufwand zu bekommen.
|
|
|
|
\item Annahme: \acs{PA} sind $n$-Bit-\acs{CLA-PA} \newline
|
|
Berechnungszeit eines $n$-Bit-\acs{CLA-PA}: $6$ \acs{GLZ} \newline
|
|
Insgesamt: $1 + (m-1)\cdot 6$ \acs{GLZ} $=6m-5$ \acs{GLZ} $=O(m)$ \newline
|
|
Damit besser $n>m$ bei Verwendung von \acs{CLA-PA}, um geringeren Zeitaufwand zu bekommen
|
|
|
|
\textcolor{red}{$\lightning$} zu großer \acs{HW}-Aufwand (wächst exponentiell mit $n$)
|
|
\end{enumerate}
|
|
\bigskip
|
|
\bigskip
|
|
|
|
\begin{Hinweis}[frametitle={Hinweis für die Klausur}]
|
|
Den logarithmischen Aufwand für \acs{CLA-PA} auf \href{https://de.wikipedia.org/wiki/Paralleladdierer_mit_\%C3\%9Cbertragsvorausberechnung}{Wikipedia} nachschauen. Dies wird zwar wahrscheinlich nicht in der Klausur abgefragt, aber er könnte abfragen, welche Alternativen es gibt. Unserer Variante hat exponentiellen Hardwareaufwand und konstanten Zeitaufwand. Die Variante auf \href{https://de.wikipedia.org/wiki/Paralleladdierer_mit_\%C3\%9Cbertragsvorausberechnung}{Wikipedia} nicht.
|
|
\end{Hinweis}
|
|
|
|
\subsection{Seriellmultiplizierer} \index{Seriellmultiplizierer}
|
|
Motivation: Wir wollen eine noch engere Anlehung an das schriftliche Multiplikationsverfahren, um den Aufwand für die Addierglieder gering zu halten.
|
|
|
|
\autoref{fig:seriellmultiplizierer} zeigt einen 5-Bit-\acl{SM}.
|
|
|
|
\begin{figure}[ht]
|
|
\centering
|
|
\includegraphics[width=15cm]{Bilder/Seriellmultiplizierer.png}
|
|
\caption{5-Bit Seriellmultiplizierer}
|
|
\label{fig:seriellmultiplizierer}
|
|
\end{figure}
|
|
|
|
\bigskip
|
|
\begin{Hinweis}
|
|
Vor dem ersten Takt müssen alle \acsp{D-FF} auf \code{0} gesetzt werden \newline
|
|
(\enquote{Reset-Eingang} oder ähnliches)
|
|
\end{Hinweis}
|
|
|
|
\subsubsection{Analyse: Hardwareaufwand für $n\times m$-Seriellmultiplizierer}
|
|
\textit{Benötigt werden:}
|
|
|
|
\begin{tabular}{c@{}ll}
|
|
\textbullet~ & $n$-Bit-\acs{PA} $\Rightarrow$ $n$-Bit-\acs{RC-PA} & $\Rightarrow$ $18n-10$ Transistoren \\
|
|
\textbullet~ & $n$ \code{UND} mit jeweils 2 Eingängen & $\Rightarrow$ $2n$ Transistoren \\
|
|
\textbullet~ & $2n$ \acsp{D-FF} & $\Rightarrow$ $12n$ Transistoren \\
|
|
\textbullet~ & $2m$-Bit-\acs{SR} & $\Rightarrow$ $12m$ Transistoren \\
|
|
\textbullet~ & \multicolumn{2}{@{}l}{Takterzeugung (wird im folgenden nicht berücksichtigt)}
|
|
\end{tabular}
|
|
|
|
gesamt: $18n-10+2n+12n+12m=32n+12m-10$ Transistoren % stimmt so; verglichen mit 15er
|
|
|
|
\qquad $\Rightarrow$ $O(n+m)$
|
|
|
|
\subsubsection{Analyse: Zeitaufwand für $n\times m$-Seriellmultiplizierer mit RC-PA}
|
|
Zeitaufwand: $m$ Taktzyklen
|
|
|
|
Mindestdauer eines halben Taktzyklus: Berechnungszeit \enquote{innen}
|
|
|
|
\begin{tabular}{rl}
|
|
$\frac{1}{2}$ Taktzyklus & $\gtrsim$ Auslesezeit(\acs{SR}) + \code{UND} + $n$-Bit-\acs{PA} + Einlesezeit(\acs{SR}) \\
|
|
& $= 1+1+2n+1=2n+3$ \acs{GLZ} \\
|
|
$\Rightarrow$ 1 Taktzyklus & $\gtrsim$ $4n+6$ \acs{GLZ} \\
|
|
gesamt: & $\gtrsim m\cdot(4n+6)=4mn+6m=O(nm)$
|
|
\end{tabular}
|
|
|
|
|
|
\section{Division} \index{Division}
|
|
\columnratio{0.24}
|
|
\begin{paracol}{2}
|
|
\begin{tabular}{c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}}
|
|
4 & 7 & 1 & 1 & $:$ & 1 & 3 & $=0362,\ldots$ \\
|
|
0 & & & & & & & \\ \cline{1-2}
|
|
4 & 7 & & & & & & \\
|
|
3 & 9 & & & & & & \\ \cline{1-3}
|
|
& 8 & 1 & & & & & \\
|
|
& 7 & 8 & & & & & \\ \cline{1-4}
|
|
& & 3 & 1 & & & & \\
|
|
& & 2 & 6 & & & & \\ \cline{3-4}
|
|
& & & 5 & & & &
|
|
\end{tabular}
|
|
\switchcolumn
|
|
Die Division wird runter gebrochen auf mehrere Divisionen mit einstelligen Ergebnissen.
|
|
|
|
Dies ist recht komplex bei einem großem Divisor. Aber im Binärsystem ist es ein einfacher Größenvergleich, da das einstellige Ergebnis nur \code{1} oder \code{0} sein kann. \newline
|
|
(besser wäre Integration in anschließend notwendiger Subtraktion)
|
|
|
|
Trotzdem bleiben einige Schritte zu tun, was aufwändig ist. In heutigen \acsp{CPU} ist deshalb (meist) kein Hardware-Dividierer eingebaut.
|
|
\end{paracol}
|
|
|
|
\begin{tabular}{rp{13.5cm}}
|
|
\textit{Grund}: & Die Division wird deutlich seltener als Addition, Subtraktion und Multiplikation gebraucht. \\
|
|
\textit{Stattdessen}: & Division \enquote{in Software}/\enquote{als Programm}, \zB als Bibliotheksroutine (\enquote{Funktion}), evtl. bereitgestellt vom Betriebssystem oder als Mikroprogramm, welches Bestandteil der \acs{CPU} ist und aufgerufen wird, wenn ein entsprechender Maschinensprachenbefehl ausgeführt werden soll.
|
|
\end{tabular}
|
|
|
|
|
|
|
|
\section{CPUs} \index{RISC} \index{CISC}
|
|
In \autoref{tbl:risc_cisc} werden \acs{RISC} und \acs{CISC} verglichen.
|
|
\begin{table}[ht]
|
|
\centering
|
|
\hspace*{-6mm}
|
|
\begin{tabular}{cp{7.55cm}|cp{7.55cm}}
|
|
\multicolumn{2}{p{8.2cm}|}{\textbf{\acf{RISC}}}
|
|
& \multicolumn{2}{p{8.2cm}}{\textbf{\acf{CISC}}}
|
|
\\[1.5ex] \midrule
|
|
|
|
\multicolumn{2}{p{8.2cm}|}{für jeden Maschinensprachenbefehl gibt es eine \enquote{passende} Hardwareeinheit}
|
|
& \multicolumn{2}{p{8.2cm}}{manche Maschinensprachenbefehle werden als Mikroprogramm ausgeführt}
|
|
\\[1.5ex] \midrule
|
|
|
|
$\oplus$ & Einheit für Mikroprogrammausführung kann bei der Produktion entfallen \newline
|
|
(CPU weniger komplex)
|
|
& $\oplus$ & komfortables Programmieren in Maschinensprache
|
|
\\[4.5ex]
|
|
|
|
$\ominus$ & \acs{CPU} wird komplex, falls die Forderung nach komplexen Befehlen in Maschinensprache realisiert, besteht.
|
|
& $\ominus$ & bei manchen Befehlen (welche als Mikroprogramm ausgeführt werden) ist die Bearbeitungszeit sehr groß und variabel.
|
|
\\[1.5ex]
|
|
|
|
$\oplus$ & jeder Befehl kann in wenigen (und jeweils einer festen Zahl an) Taktzyklen ausgeführt werden.
|
|
& $\ominus$ & Mikroprogramme sind Software, komplex und fehleranfällig, ggf. Austausch der \acs{CPU} für \enquote{Bugfix} notwendig (vgl. \href{https://de.wikipedia.org/wiki/Pentium-FDIV-Bug}{Intel Pentium FDIV Bug})
|
|
\\[1.5ex]
|
|
\end{tabular}
|
|
\medskip
|
|
\hspace*{-6mm}
|
|
\begin{tabular}{p{8.2cm}|p{8.2cm}}
|
|
\multicolumn{2}{c}{\textbf{Einsatz}} \\ \midrule
|
|
|
|
PowerPC-\acs{CPU} in Apple-Rechnern bis vor 10 Jahren
|
|
& Intel-\acsp{CPU} in heutigen Universalrechnern (und AMD-Äquivalent)
|
|
\\
|
|
|
|
oft in \enquote{embedded systems} (Bsp. ARM)
|
|
|
|
\end{tabular}
|
|
\caption{Vergleich von RISC und CISC}
|
|
\label{tbl:risc_cisc}
|
|
\end{table}
|