Select Git revision
rtech-20230621.tex
Peter Gerwinski authored
rtech-20230621.tex 28.95 KiB
% rtech-20230621.pdf - Lecture Slides on Computer Technology
% Copyright (C) 2012, 2013, 2014, 2021, 2022, 2023 Peter Gerwinski
%
% This document is free software: you can redistribute it and/or
% modify it either under the terms of the Creative Commons
% Attribution-ShareAlike 3.0 License, or under the terms of the
% GNU General Public License as published by the Free Software
% Foundation, either version 3 of the License, or (at your option)
% any later version.
%
% This document is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
% GNU General Public License for more details.
%
% You should have received a copy of the GNU General Public License
% along with this document. If not, see <http://www.gnu.org/licenses/>.
%
% You should have received a copy of the Creative Commons
% Attribution-ShareAlike 3.0 Unported License along with this
% document. If not, see <http://creativecommons.org/licenses/>.
% README: Dateiformate, Pipelining
\documentclass[10pt,t]{beamer}
\usepackage{pgslides}
\usepackage{pdftricks}
%\usepackage[obeyfamily=false,mathrm=mathsf,textrm=sffamily]{siunitx}
%\usepackage{eurosym}
\usepackage{tikz}
\newcommand{\vfilll}{\vspace{0pt plus 1 filll}}
\lstdefinestyle{asm}{basicstyle=\color{structure},
language={},
gobble=4}
\begin{psinputs}
\usepackage[utf8]{inputenc}
\usepackage[german]{babel}
\usepackage[T1]{fontenc}
\usepackage{helvet}
\renewcommand*\familydefault{\sfdefault}
\usepackage{pstricks,pst-grad,pst-circ-pg}
\newcommand{\invisible}{\tiny\color{white}}
\psset{unit=1cm}
\psset{logicLabelstyle=\invisible}
\newcommand{\logicSymbol}{\small\boldmath\bf\rule{0pt}{0.5cm}}
\psset{logicSymbolstyle=\logicSymbol}
\newcommand{\Cin}{C\raisebox{-0.5ex}{\footnotesize in}}
\newcommand{\Cout}{C\raisebox{-0.5ex}{\footnotesize out}}
\end{psinputs}
\title{Rechnertechnik}
\author{Prof.\ Dr.\ rer.\ nat.\ Peter Gerwinski}
\date{21.\ Juni 2023}
\begin{document}
\maketitleframe
\nosectionnonumber{\inserttitle}
\begin{frame}
\shownosectionnonumber
\begin{itemize}
\item[\textbf{1}] \textbf{Einführung} \item[\textbf{2}] \textbf{Vom Schaltkreis zum Computer}
\item[\textbf{3}] \textbf{Assembler-Programmierung}
\item[\textbf{4}] \textbf{Hardwarenahe Programmierung}
\begin{itemize}
\item[4.1] Bit-Operationen
\item[4.2] I/O-Ports
\color{medgreen}
\item[4.3] Interrupts
\color{orange}
\item[4.4] Byte-Reihenfolge -- Endianness
\end{itemize}
\item[\textbf{5}] \textbf{Dateiformate}
\item[\textbf{6}] \textbf{Pipelining}
\end{itemize}
\end{frame}
\setcounter{section}{3}
\section{Hardwarenahe Programmierung}
\setcounter{subsection}{2}
\subsection{Interrupts}
\begin{frame}[fragile]
\showsubsection
Externes Gerät ruft (per Stromsignal) Unterprogramm auf
Zeiger hinterlegen: "`Interrupt-Vektor"'
Beispiel: eingebaute Uhr\hfill
\makebox(0,0)[tr]{%
\only<1->{\begin{minipage}[t]{4.7cm}
\vspace*{-0.3cm}%
statt Zählschleife (\lstinline{_delay_ms}):\\
Hauptprogramm kann\\
andere Dinge tun
\end{minipage}}%
}
\medskip
\begin{lstlisting}
#include <avr/interrupt.h>
...
ISR (TIMER0B_COMP_vect)
{
PORTD ^= 0x40;
}
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(1.9,3.1){\makebox(0,0)[tr]{\tikz{\draw[-latex](0,0)--(-1.4,-1.0);}}}
\put(2.0,3.2){\makebox(0,0)[l]{"`Dies ist ein Interrupt-Handler."'}}
\put(2.3,2.6){\makebox(0,0)[tr]{\tikz{\draw[-latex](0,0)--(-0.6,-0.55);}}}
\put(2.4,2.6){\makebox(0,0)[l]{Interrupt-Vektor darauf zeigen lassen}}
\end{picture}
Initialisierung über spezielle Ports:
\lstinline{TCCR0B}, \lstinline{TIMSK0}
\bigskip
\emph{Details: siehe Datenblatt und Schaltplan}
\vspace*{-2.5cm}\hfill
{\color{red}Herstellerspezifisch!}% \hspace*{1cm}
\end{frame}
\subsection{Byte-Reihenfolge -- Endianness}
\subsubsection{Konzept}
\begin{frame}[fragile]
\showsubsection
\showsubsubsection
Eine Zahl geht über mehrere Speicherzellen.\\
Beispiel: 16-Bit-Zahl in 2 8-Bit-Speicherzellen
\smallskip
Welche Bits liegen wo?
% \pause
\bigskip
$1027 = 1024 + 2 + 1 = 0000\,0100\,0000\,0011_2 = 0403_{16}$
% \pause
\bigskip
Speicherzellen:
\medskip
\begin{tabular}{|c|c|l}\cline{1-2}
\raisebox{-0.25ex}{04} & \raisebox{-0.25ex}{03} & \strut Big-Endian "`großes Ende zuerst"' \\\cline{1-2}
\multicolumn{2}{c}{} & % \pause
für Menschen leichter lesbar % \pause
\\
\multicolumn{3}{c}{} \\[-5pt]\cline{1-2}
\raisebox{-0.25ex}{03} & \raisebox{-0.25ex}{04} & \strut Little-Endian "`kleines Ende zuerst"' \\\cline{1-2}
\multicolumn{2}{c}{} & % \pause
bei Additionen effizienter
\end{tabular}
% \pause
\medskip
\textarrow\ Geschmackssache
% \pause\\
\quad\textbf{\dots\ außer bei Datenaustausch!}
% \pause
% \bigskip
%
% Aber: nicht verwechseln! \qquad $0304_{16} = 772$
\end{frame}
\begin{frame}
\showsubsection
\showsubsubsection
Eine Zahl geht über mehrere Speicherzellen.\\
Beispiel: 16-Bit-Zahl in 2 8-Bit-Speicherzellen
\smallskip
Welche Bits liegen wo?
\medskip
\textarrow\ Geschmackssache\\
\textbf{\dots\ außer bei Datenaustausch!}
\begin{itemize}
\item
Dateiformate
\item
Datenübertragung
\end{itemize}
\end{frame}
\subsubsection{Dateiformate}
\begin{frame}
\showsubsection
\showsubsubsection
Audio-Formate: Reihenfolge der Bytes in 16- und 32-Bit-Zahlen
\begin{itemize}
\item
RIFF-WAVE-Dateien (\file{.wav}): Little-Endian
\item
Au-Dateien (\file{.au}): Big-Endian
% \pause
\item
ältere AIFF-Dateien (\file{.aiff}): Big-Endian
\item
neuere AIFF-Dateien (\file{.aiff}): Little-Endian
\end{itemize}
% \pause
\bigskip
Grafik-Formate: Reihenfolge der Bits in den Bytes
\begin{itemize}
\item
PBM-Dateien: Big-Endian\only<1->{, MSB first}
\item
XBM-Dateien: Little-Endian\only<1->{, LSB first}
\end{itemize}
\only<1->{MSB/LSB = most/least significant bit}
\end{frame}
\subsubsection{Datenübertragung}
\begin{frame}
\showsubsection
\showsubsubsection
\begin{itemize}
\item
RS-232 (serielle Schnittstelle): LSB first
\item
I$^2$C: MSB first
\item
USB: beides
\pause
\medskip
\item
Ethernet: LSB first
\item
TCP/IP (Internet): Big-Endian
\end{itemize}
\end{frame}
\begin{frame}[fragile]
\showsubsection
Frage: \emph{Für welche Zahl steht der Speicherinhalt\,
\raisebox{2pt}{%
\tabcolsep0.25em
\begin{tabular}{|c|c|}\hline
\rule{0pt}{11pt}a3 & 90 \\\hline
\end{tabular}}
(hexadezimal)?}
\pause
\smallskip
Antwort: \emph{Das kommt darauf an.} ;--)
\pause
\medskip
Little-Endian:
\smallskip
\begin{tabular}{lrl}
als \lstinline,int8_t,: & $-93$ & (nur erstes Byte)\\
als \lstinline,uint8_t,: & $163$ & (nur erstes Byte)\\
als \lstinline,int16_t,: & $-28509$\\
als \lstinline,uint16_t,: & $37027$\\
\lstinline,int32_t, oder größer: & $37027$
& (zusätzliche Bytes mit Nullen aufgefüllt)
\end{tabular}
\pause
\medskip
Big-Endian:
\smallskip
\begin{tabular}{lrl}
als \lstinline,int8_t,: & $-93$ & (nur erstes Byte)\\
als \lstinline,uint8_t,: & $163$ & (nur erstes Byte)\\
als \lstinline,int16_t,: & $-23664$\\
als \lstinline,uint16_t,: & $41872$\\ als \lstinline,int32_t,: & $-1550843904$ & (zusätzliche Bytes\\
als \lstinline,uint32_t,: & $2744123392$ & mit Nullen aufgefüllt)\\
als \lstinline,int64_t,: & $-6660823848880963584$\\
als \lstinline,uint64_t,: & $11785920224828588032$\\
\end{tabular}
\vspace*{-1cm}
\end{frame}
\section{Dateiformate}
\subsection{Grafikdateien}
\subsubsection{Pixelgrafik}
\begin{frame}
\showsection
\showsubsection
\showsubsubsection
Jeden Bildpunkt einzeln abspeichern
\begin{itemize}
\item
Farben als Zahlen abspeichern, z.\,B.\ Rot-, Grün- und Blauanteil\\
verbreitet: jeweils 8 Bit pro Farbkanal
\item
Farben als Tabelle abspeichern:\\
pro Bildpunkt ein Index für Tabelle, in der der Farbwert steht
\item
Speziell: nur 2 Farben (Vordergrund, Hintergrund)\\
1 Bit pro Pixel
\end{itemize}
\medskip
Kompression
\begin{itemize}
\item
unkomprimiert: PBM, PGM, PPM, XBM
\item
verlustfrei: GIF, PNG (für Grafiken)
\item
verlustbehaftet: JPEG (für Fotos)
\end{itemize}
\vfilll
\strut\hfill
\begin{picture}(0,0)
\put(0,0){\makebox(0,0)[br]{\includegraphics[height=1cm]{logo-hochschule-bochum.jpg}}}
\put(0,1.5){\makebox(0,0)[br]{\includegraphics[height=1cm]{logo-hochschule-bochum.png}}}
\end{picture}
\end{frame}
\subsubsection{Vektorgrafik}
\begin{frame}
\showsection
\showsubsection
\showsubsubsection
Bildelemente über ihre Koordinaten abspeichern
\begin{itemize}
\item
geeignet für Grafiken, normalerweise nicht für Fotos
\item
kleine Dateigrößen, skalierbar
\end{itemize}
\medskip
Kompression
\begin{itemize}
\item
unkomprimiert: PostScript, SVG
\item
komprimiert: PDF\\
(kann auch PNG oder JPEG enthalten)
\end{itemize}
\vfilll
\strut\hfill
\begin{picture}(0,0)
\put(0,0){\makebox(0,0)[br]{\includegraphics[height=1cm]{logo-hochschule-bochum.jpg}}}
\put(0,1.5){\makebox(0,0)[br]{\includegraphics[height=1cm]{logo-hochschule-bochum.png}}}
\put(0,3){\makebox(0,0)[br]{\includegraphics[height=1cm]{logo-hochschule-bochum.pdf}}}
\end{picture}
\end{frame}
\subsection{Textdateien}
\begin{frame}
\showsection
\showsubsection
Zeichenkodierungen
\begin{itemize}
\item 7 Bit: ASCII
\item
8 Bit: CP-437, CP-850, ISO 8859-1, ISO 8859-5, ISO 8859-15, \dots
\item
32 Bit: Unicode\\
16-Bit-Kodierung: UTF-16\\
8-Bit-Kodierung: UTF-8
\item
für URLs: Punycode
\item
historisch: Baudot-Code (5 Bit), EBCDIC (8 Bit)
\end{itemize}
\medskip
Zeilentrennzeichen
\begin{itemize}
\item
Unix: LF
\item
MS-DOS/Windows, HTTP: CR LF
\item
frühere Mac-Rechner: CR
\end{itemize}
\end{frame}
\subsection{Archiv-Dateien}
\begin{frame}
\showsection
\showsubsection
\begin{itemize}\itemsep\medskipamount
\item
einzelne Datei, komprimiert:\\
.gz, .bz2, .xz\\
.ppm.xz-Dateien sind kleiner als .png-Dateien
\item
mehrere Dateien, zusammengefaßt:\\
.a, .tar
\item
mehrere Dateien, zusammengefaßt und komprimiert:\\
.tar.gz, .tar.bz2, .tar.xz, .zip, .7z
\item
Spezialfall: mehrere standardisierte Text-Dateien (XML)\\
in standardisierter .zip-Datei:\\[\smallskipamount]
OpenDocument (LibreOffice u.\,a.): .odt, .ods, .odp, \dots\\
Office-Open-XML (Microsoft): .docx, .xlsx, .pptx, \dots
\end{itemize}
\end{frame}
\subsection{Binärdateien}
\begin{frame}
\showsection
\showsubsection
\begin{itemize}
\item
Ein Programm speichert seine Speicherinhalte\\
i.\,w.\ "`einfach so"' auf einem Datenträger.
\arrowitem
Bereits kleinste Versionsunterschiede führen zu Problemen.
\item
Beispiel: MS-Office-Dateien (.doc, .xls, .ppt)
\item
Besser: komprimierte Text-Dateien (.odt, .ods, .odp, .docx, .xlsx, .pptx)
\end{itemize}
\end{frame}
\subsection{Ausführbare Dateien}
\begin{frame}
\visible<1->{\showsection\showsubsection}
Man kann Maschinenprogramme nicht "`einfach so"' in den Speicher laden.
% \pause
\bigskip
Sprünge anpassen
\begin{itemize}
\item
Relokation: Relokationstabelle
\item
Linken: Symboltabelle
\end{itemize}
\end{frame}
\begin{frame}
\showsubsection
\vspace*{-0.5cm}
\begin{center}
\setlength{\unitlength}{0.8cm}
\begin{picture}(15,6)(0,-1.25)
\footnotesize
\put(0,1.0){\line(1,0){15}}
\multiput(0,1)(0.1,0){151}{\line(0,1){0.1}}
\put(0,1.1){\line(1,0){15}}
\put(0,0.8){\makebox(0,0)[tl]{Ausführbare Binärdatei}}
\put(0.5,1.2){$\overbrace{\rule{1.0\unitlength}{0pt}}$}
\put(2.0,1.2){$\overbrace{\rule{1.0\unitlength}{0pt}}$}
\put(3.5,1.2){$\overbrace{\rule{11.5\unitlength}{0pt}}$}
\put(0,4.0){\line(1,0){5}}
\multiput(0,3.5)(0.5,0){11}{\line(0,1){0.5}}
\put(0,3.5){\line(1,0){5}}
\put(0,4.2){\makebox(0,0)[bl]{Relokationstabelle}}
\put(1.0,3.4){\line(0,-1){1.9}}
\put(3.75,3.4){\vector(1,-2){1.2}}
\put(4.25,3.4){\vector(1,-1){2.4}}
\put(4.75,3.4){\vector(2,-1){4.8}}
\put(4.95,0.7){\line(0,1){0.25}}
\put(4.95,0.7){\line(1,0){0.5}}
\put(5.45,0.7){\vector(0,1){0.25}}
\put(6.65,0.7){\line(0,1){0.25}}
\put(6.65,0.7){\line(1,0){0.8}}
\put(7.45,0.7){\vector(0,1){0.25}}
\put(9.55,0.6){\line(0,1){0.35}}
\put(9.55,0.6){\line(-1,0){3.2}}
\put(6.35,0.6){\vector(0,1){0.35}}
\put(7.25,0.4){\makebox(0,0)[t]{Sprünge innerhalb des Programms}}
\put(6,4.0){\line(1,0){5}}
\multiput(6,3.5)(0.5,0){11}{\line(0,1){0.5}}
\put(6,3.5){\line(1,0){5}}
\put(6,4.2){\makebox(0,0)[bl]{Symboltabelle}}
\put(6.4,3.4){\line(-2,-1){3.8}}
\put(10.25,3.4){\vector(1,-2){1.2}}
\put(10.75,3.4){\vector(1,-1){2.4}}
\put(9.25,1.55){\line(0,1){1}}
\put(8.50,2.60){\makebox(0,0)[b]{Maschinenprogramm}}
\put(11.45,0.95){\vector(0,-1){1}}
\put(11.45,-0.10){\makebox(0,0)[t]{\lstinline{scanf}}}
\put(13.15,0.95){\vector(0,-1){1}}
\put(13.15,-0.10){\makebox(0,0)[t]{\lstinline{printf}}}
\put(12.30,-0.50){\makebox(0,0)[t]{Sprünge aus dem Programm heraus}}
\end{picture}
\end{center}
\vspace*{-1.2cm}
\begin{onlyenv}<2>
Ausführbare Binärdatei:
\smallskip
Relokationstabelle,\\
Symboltabelle für dynamischen Linker
\smallskip
Formate: a.out, COFF, ELF, \dots\\
Dateiendungen: (keine), .elf, .com, .exe, .scr
\end{onlyenv}
\begin{onlyenv}<3>
Objektdatei:
\smallskip
Relokationstabelle,\\
Symboltabellen für statischen und dynamischen Linker
\smallskip
Formate: a.out, COFF, ELF, \dots\\
Dateiendungen: .o, .obj
\end{onlyenv}
\begin{onlyenv}<4->
\strut\\
Bibliothek:
\smallskip
Zusammenfassung mehrerer Objekt-Dateien
\smallskip
Statische Bibliotheken: .a, .lib\\
Dynamische Bibliotheken: .so, .dll
\end{onlyenv}
\end{frame}
\subsubsection{Die Toolchain}
\begin{frame}[fragile]
\showsubsection \showsubsubsection
\vspace*{-1.5cm}
\begin{center}
\addtolength{\leftskip}{4cm}
\small
\newcommand{\vtextarrow}[1]{%
\begin{picture}(0,0.8)
\put(0,0.8){\vector(0,-1){0.8}}
\put(0.125,0.4){\makebox(0,0)[l]{#1}}
\end{picture}}
\framebox{\shortstack{\strut menschliche Gedanken}}
\vtextarrow{Texteditor}
\framebox{\shortstack{\strut C-Quelltext}} % (z.\,B.\ hello.c)}}
\vtextarrow{Compiler}
\framebox{\shortstack{\strut Assembler-Quelltext}} % (z.\,B.\ hello.s, hello.asm)}}
\vtextarrow{Assembler}
\framebox{\shortstack{\strut Objekt- und Bibliothek-Dateien}} % (z.\,B.\ hello.o, hello.obj)}}
\vtextarrow{Linker}
\framebox{\shortstack{\strut ausführbare Binärdatei}} % (z.\,B.\ hello, hello.exe)}}
\vtextarrow{Loader}
\framebox{\shortstack{\strut Programm im Speicher bereit zur Ausführung}}
\end{center}
% \pause
\vspace*{-7cm}
Automatischer Aufruf:
\begin{itemize}
\item
Entwicklungsumgebungen\\
(z.\,B.\ Eclipse, Code::Blocks, \dots)
\medskip
\item
\file{gcc} = Compiler\\
\hspace*{3em}+ Assembler\\
\hspace*{3em}+ Linker\\
\hspace*{3em}+ \dots
\medskip
\item
\file{make} kann \emph{alles} aufrufen
\end{itemize}
\end{frame}
\subsubsection{Besonderheiten von Mikrocontrollern}
\begin{frame}
\showsubsection
\showsubsubsection
Kein Betriebssystem\\ % \pause\\
\textarrow\ kein Relocator, kein dynamischer Linker\\ % \pause\\
\textarrow\ Wir müssen dem Mikrocontroller alles "`mundgerecht"' servieren.
% \pause
\smallskip
\begin{itemize} \item
fertiges ROM: Hersteller
\item
Flash-Speicher und In-System Programmer (ISP)
\item
Flash-Speicher und Boot-Loader
\end{itemize}
\smallskip
In jedem Fall: statisch linken, Relokation vorher
\begin{picture}(0,0)
\color{red}
\put(0.1,0.1){\line(1,0){1.2}}
\put(1.3,0.1){\vector(0,1){2.2}}
\end{picture}\\
\textarrow\ ELF-Datei in HEX-Datei umwandeln
\smallskip
Format: Intel-Hex-Format\\
Dateiendung: .hex
\end{frame}
\section{Pipelining}
\subsection{Konzept}
\newcommand{\wm}{\raisebox{-0.3cm}{\includegraphics[width=1.0cm]{Waschen_30.pdf}}}
\newcommand{\wt}{\raisebox{-0.3cm}{\includegraphics[width=1.0cm]{Trommeltrocknen.pdf}}}
\newcommand{\be}{\raisebox{-0.3cm}{\includegraphics[width=1.0cm]{Buegeln.pdf}}}
\begin{frame}
\showsection
% \pause
\showsubsection
\begin{itemize}
\item
Aufgabe in Teilaufgaben zerlegen
\item
Teilaufgaben parallel ausführen
\end{itemize}
\pause
\bigskip
Beispiel: Wäsche waschen
% \pause
\begin{itemize}
\item
Teilaufgaben: \wm, \wt, \be
\pause
\item
müssen nacheinander ausgeführt werden\pause: Datenfluß
\pause
\item
belegen jeweils 1 Ressource
\end{itemize}
\end{frame}
\begin{frame}
3 Ladungen Wäsche
\begin{center}
\begin{onlyenv}<1-2>
\begin{picture}(12,3.5)
\thicklines
\put(1,1){\wm}
\put(2,1){\wt} \put(3,1){\be}
\put(4,2){\wm}
\put(5,2){\wt}
\put(6,2){\be}
\put(7,3){\wm}
\put(8,3){\wt}
\put(9,3){\be}
\put(-0.1,0.5){\vector(1,0){11.1}}
\put(11.5,0.5){\makebox(0,0){$t$}}
\put(10.5,1.0){\makebox(0,0)[r]{ineffizient}}
\end{picture}\\[\medskipamount]
\end{onlyenv}
\begin{onlyenv}<2-4>
\begin{picture}(12,3.5)
\thicklines
\put(1,1){\wm}
\put(2,1){\wt}
\put(3,1){\be}
\put(2,2){\wm}
\put(3,2){\wt}
\put(4,2){\be}
\put(3,3){\wm}
\put(4,3){\wt}
\put(5,3){\be}
\put(-0.1,0.5){\vector(1,0){11.1}}
\put(11.5,0.5){\makebox(0,0){$t$}}
\put(10.5,1.0){\makebox(0,0)[r]{effizient}}
\end{picture}\\[\medskipamount]
\end{onlyenv}
\begin{onlyenv}<3->
\begin{picture}(12,3.5)
\thicklines
\put(1,1){\wm}
\put(2,1){\wt}
\put(3,1){\be}
\put(1,2){\wm}
\put(2,2){\wt}
\put(3,2){\be}
\put(1,3){\wm}
\put(2,3){\wt}
\put(3,3){\be}
\put(-0.1,0.5){\vector(1,0){11.1}}
\put(11.5,0.5){\makebox(0,0){$t$}}
\put(10.5,1.0){\makebox(0,0)[r]{noch effizienter}}
\color{red}
\thicklines
\put(0.5,0.8){\only<4->{\line(4,1){10}}}
\put(0.5,3.3){\only<4->{\line(4,-1){10}}}
\put(7.5,1.7){\only<4->{\mbox{\shortstack{Ressourcen-\\konflikt}}}}
\end{picture}\\[\medskipamount]
\end{onlyenv}
\begin{onlyenv}<5->
\begin{picture}(12,3.5)
\thicklines
\put(1,1){\wm}
\put(2,1){\wt}
\put(3,1){\be}
\put(1,2){\wt}
\put(2,2){\be}
\put(3,2){\wm}
\put(1,3){\be}
\put(2,3){\wm}
\put(3,3){\wt}
\put(-0.1,0.5){\vector(1,0){11.1}}
\put(11.5,0.5){\makebox(0,0){$t$}}
\put(10.5,1.0){\makebox(0,0)[r]{noch effizienter}}
\color{red}
\thicklines
\put(0.5,0.8){\only<6->{\line(4,1){10}}}
\put(0.5,3.3){\only<6->{\line(4,-1){10}}} \put(7.5,1.7){\only<6->{\mbox{\shortstack{Daten-\\konflikt}}}}
\end{picture}%
\end{onlyenv}
\end{center}
\end{frame}
\subsection{Arithmetik-Pipelines}
\newcommand{\insns}[1]{%
\begin{picture}(0,0)
\put(0,0){\line(1,0){2}}
\put(2,0){\line(0,-1){#1}}
\put(2,-#1){\vector(-1,0){2}}
\end{picture}}
\newcommand{\insnsup}[1]{%
\begin{picture}(0,0)
\put(0,0){\line(1,0){2}}
\put(2,0){\line(0,1){#1}}
\put(2,#1){\vector(-1,0){2}}
\end{picture}}
\begin{frame}
\showsubsection
"`Register-FIFO"'
\pause
\smallskip
Pseudo-Code: Berechnung von
\begin{displaymath}
S = \left(\begin{array}{c}a_1\\a_2\\a_3\end{array}\right)
\cdot\left(\begin{array}{c}b_1\\b_2\\b_3\end{array}\right)
= a_1 \cdot b_1
+ a_2 \cdot b_2
+ a_3 \cdot b_3
\end{displaymath}
mit einer Pipeline der Länge 3
\pause
\medskip
\begingroup
\setlength{\unitlength}{\baselineskip}%
\begin{picture}(0,0)(-5.0,-0.25)
\color{red}
\put(0,0.0){\only<4->{\insns{3}}}
\put(0.5,-1){\only<5->{\insns{2.9}}}
\put(1.0,-2){\only<6->{\insns{3}}}
\put(0.5,-4.1){\only<8->{\insns{2.8}}}
\put(0.5,-7.1){\only<11->{\insns{2.9}}}
\put(-1.5,-9.25){\only<15->{\shortstack{Daten-\\konflikt}}}
\end{picture}%
\color{structure}
push $a_1 \cdot b_1$\\
\pause
\pause
push $a_2 \cdot b_2$\\
\pause
push $a_3 \cdot b_3$\\
\pause
$s_1$ = pop\\
\pause
push $s_1 + \mbox{pop}$\\
\pause
$s_3$ = pop\\
\pause
nop\\ \pause
push $s_3 + \mbox{pop}$\\
\pause
nop\\
\pause
nop\\
\pause
$S$ = pop\\
\endgroup
\pause
\pause
\begin{picture}(0,0)
\color{red}
\put(5,3.8){\makebox(0,0)[l]{$\left.\rule{0pt}{1.2cm}\right\}$ effizient: Pipeline gefüllt}}
\put(5,1.4){\makebox(0,0)[l]{$\left.\rule{0pt}{1.2cm}\right\}$ ineffizient: "`Blasen"'}}
\end{picture}
\pause
\vspace*{-1.25cm}
\begin{flushright}
\dots\ aber immer noch effizienter als\\
3 Schritte für jede Operation
\end{flushright}
\end{frame}
\subsectionnonumber{Reales Beispiel: \break Vektor-Addition auf i860}
\begin{frame}[fragile]
\begin{minipage}[t]{5cm}
\raggedright
\showsubsectionnonumber
\begin{lstlisting}
.align 8
.globl _vadd
nop
_vadd:
shr 1,r19,r19
bte r19,r0,exitadd
addu 0x000F,r16,r16
andnot 0x000F,r16,r16
adds -16,r16,r16
addu 0x000F,r17,r17
andnot 0x000F,r17,r17
adds -16,r17,r17
addu 0x000F,r18,r18
andnot 0x000F,r18,r18
adds -16,r18,r18
mov -1,r20
\end{lstlisting}
\end{minipage}
\begin{minipage}[t]{5cm}
\begin{lstlisting}
fld.q 16(r16)++,f16
fld.q 16(r17)++,f20
pfadd.dd f16,f20,f0
bla r20,r19,loopadd
pfadd.dd f18,f22,f0
loopadd:
d.pfadd.dd f0,f0,f0
fld.q 16(r16)++,f16
d.pfadd.dd f0,f0,f24
fld.q 16(r17)++,f20
d.pfadd.dd f16,f20,f26
bla r20,r19,loopadd
d.pfadd.dd f18,f22,f0
fst.q f24,16(r18)++
nop
nop
nop exitadd:
bri r1
nop
\end{lstlisting}
\end{minipage}
\end{frame}
\lstdefinestyle{shybubble}{basicstyle=\color{lightgray},
moredelim=**[is][\color{structure}]{¡}{¿},
moredelim=**[is][\only<7->{\color{red}}]{°}{¿}}
\begin{frame}[fragile]
\begin{minipage}[t]{5cm}
\raggedright
\showsubsectionnonumber
\begin{lstlisting}[style=shybubble]
.align 8
.globl _vadd
nop
_vadd:
shr 1,r19,r19
bte r19,r0,exitadd
addu 0x000F,r16,r16
andnot 0x000F,r16,r16
adds -16,r16,r16
addu 0x000F,r17,r17
andnot 0x000F,r17,r17
adds -16,r17,r17
addu 0x000F,r18,r18
andnot 0x000F,r18,r18
adds -16,r18,r18
mov -1,r20
\end{lstlisting}
\end{minipage}
\begin{minipage}[t]{5cm}
\begin{lstlisting}[style=shybubble]
¡fld.q 16(r16)++,f16
fld.q 16(r17)++,f20
pfadd.dd f16,f20,f0
bla r20,r19,loopadd
pfadd.dd f18,f22,f0
loopadd:
d.pfadd.dd °f0,f0,f0¿
fld.q 16(r16)++,f16
d.pfadd.dd °f0,f0¿,f24
fld.q 16(r17)++,f20
d.pfadd.dd f16,f20,f26
bla r20,r19,loopadd
d.pfadd.dd f18,f22,°f0¿
fst.q f24,16(r18)++¿
nop
nop
nop
exitadd:
bri r1
nop
\end{lstlisting}
\end{minipage}
\pause
\begingroup
\setlength{\unitlength}{\baselineskip}%
\begin{picture}(0,0)(-21.0,-17.6)
\color{red}
\put(0,0){\only<2->{\insns{5.9}}}
\put(1.0,-2){\only<3->{\insns{6.0}}}
\put(-7,-9){\only<4->{\line(-1,0){1}}}
\put(-8,-9){\only<4->{\line(0,-1){2}}} \put(-8,-11){\only<4->{\line(-1,0){1}}}
\put(-9,-11){\only<4->{\line(0,1){8}}}
\put(-9,-3){\only<4->{\vector(1,0){0.7}}}
\put(0.8,-7.8){\only<5->{\insnsup{1.7}}}
\put(0.8,-10){\only<6->{\insnsup{1.8}}}
\put(-0.5,-12.5){\only<7->{\mbox{6mal f0 = 2 Blasen}}}
\end{picture}%
\endgroup
\vspace{-2cm}
\begin{flushright}
\only<8->{Immerhin: 2 Additionen in 4 Taktzyklen}
\medskip
\only<9->{Dies ist ein \emph{einfaches} Beispiel.}
\end{flushright}
\end{frame}
\subsection{Instruktions-Pipelines}
\begin{frame}[fragile]
\showsubsection
Ein Prozessor benötigt Zeit, um einen Befehl zu verstehen.
\textarrow\ Während Befehlsausführung nächste Befehle vorauslesen
\medskip
\begin{lstlisting}[style=shy]
².L3:
movw r30,r20¿
³add r30,r18¿
°adc r31,r19¿
¤mov r24,r18
subi r24,lo8(-(1))
st Z,r24
subi r18,lo8(-(1))
sbci r19,hi8(-(1))
cp r22,r18
cpc r23,r19¿
¢brge .L3¿
æret¿
\end{lstlisting}
\begin{picture}(0,0)
\color{red}
\put(0.5,1.00){\only<8->{\line(-1,0){0.4}}}
\put(0.1,1.00){\only<8->{\line(0,1){4.15}}}
\put(0.1,5.15){\only<8->{\vector(1,0){0.4}}}
\put(0.5,0.90){\only<9->{\line(-1,0){0.4}}}
\put(0.1,0.90){\only<9->{\line(0,-1){0.35}}}
\put(0.1,0.55){\only<9->{\vector(1,0){0.4}}}
\put(2.5,0.825){\only<10->{\begin{minipage}[t]{8cm}
bedingter Sprung:
Welche Befehle vorauslesen?\\[\smallskipamount]
\only<11->{Kontrollflußkonflikt}
\end{minipage}}}
\end{picture}
\begin{flushright}
\vspace*{-0.5cm}
\only<12->{Lösungsansatz: Zweigvorhersage}
\vspace*{-1cm}
\end{flushright}
\end{frame}
\subsubsectionnonumber{Zweigvorhersage -- Branch Prediction}
\begin{frame}[fragile]
\showsubsection
\showsubsubsectionnonumber
\begin{itemize}
\setlength{\unitlength}{\baselineskip}%
\pause
\item
Sprünge nach oben sind Schleifen: "`Ja"'\\
Sprünge nach unten sind Auswahl-Verzweigungen: "`Nein"'
\pause
\item
Delayed Branches: Sprungbefehl verspätet ausführen\\
\textarrow\ Optimierung manuell oder durch Compiler
\pause
\medskip
\begin{lstlisting}
loopadd:
d.pfadd.dd f0,f0,f0
fld.q 16(r16)++,f16
d.pfadd.dd f0,f0,f24
fld.q 16(r17)++,f20
d.pfadd.dd f16,f20,f26
bla r20,r19,loopadd
d.pfadd.dd f18,f22,f0
fst.q f24,16(r18)++
\end{lstlisting}
\begin{picture}(0,0)(-9.6,-12.2)
\color{red}
\put(-7,-9){\line(-1,0){1}}
\put(-8,-9){\line(0,-1){2}}
\put(-8,-11){\line(-1,0){1}}
\put(-9,-11){\line(0,1){8}}
\put(-9,-3){\vector(1,0){0.7}}
\end{picture}
\pause
\item
Branch History Table: Sprünge merken
\pause
\item
\dots
\end{itemize}
\end{frame}
\subsectionnonumber{Zusammenfassung}
\begin{frame}
\showsection
\showsubsectionnonumber
\begin{itemize}
\item
Teilaufgaben parallel ausführen
\item
Arithmetik-Pipelines führen Berechnungen parallel aus,\\
Instruktions-Pipelines lesen Befehle voraus
\item
Ressourcen-, Daten- und Kontrollflußkonflikte führen zu "`Blasen"'
\item
Zweigvorhersage reduziert Kontrollflußkonflikte in Instruktions-Pipelines
\begin{itemize}
\item
nach oben / nach unten
\item Delayed Branches: manuell optimieren
\item
Branch History Table: Sprünge merken
\end{itemize}
\end{itemize}
\end{frame}
\nosectionnonumber{\inserttitle}
\begin{frame}
\shownosectionnonumber
\begin{itemize}
\item[\textbf{1}] \textbf{Einführung}
\item[\textbf{2}] \textbf{Vom Schaltkreis zum Computer}
\item[\textbf{3}] \textbf{Assembler-Programmierung}
\item[\textbf{4}] \textbf{Hardwarenahe Programmierung}
\item[\textbf{5}] \textbf{Dateiformate}
\begin{itemize}
\color{medgreen}
\item[5.1] Grafikdateien
\item[5.2] Textdateien
\item[5.3] Archiv-Dateien
\item[5.4] Binärdateien
\item[5.5] Ausführbare Dateien
\end{itemize}
\item[\textbf{6}] \textbf{Pipelining}
\begin{itemize}
\color{medgreen}
\item[6.1]Konzept
\item[6.2]Arithmetik-Pipelines
\item[6.3]Instruktions-Pipelines
\end{itemize}
\end{itemize}
\bigskip
\hfill{\large\color{medgreen}\em Viel Erfolg bei der Klausur!}
\end{frame}
\end{document}