talk.tex

% $Header$

\documentclass{beamer}

% Diese Datei enthält eine Lösungsvorlage für:


% - Vorträge über ein beliebiges Thema.
% - Vortragslänge zwischen 15 und 45 Minuten. 
% - Aussehen des Vortrags ist verschnörkelt/dekorativ.



% Copyright 2004 by Till Tantau <tantau@users.sourceforge.net>.
%
% In principle, this file can be redistributed and/or modified under
% the terms of the GNU Public License, version 2.
%
% However, this file is supposed to be a template to be modified
% for your own needs. For this reason, if you use this file as a
% template and not specifically distribute it as part of a another
% package/program, I grant the extra permission to freely copy and
% modify this file as you see fit and even to delete this copyright
% notice. 

\mode<presentation>
{
  \usetheme{Copenhagen}
  % oder ...
  
  \setbeamercovered{transparent}
  % oder auch nicht
}


\usepackage[german]{babel}
% oder was auch immer

\usepackage[latin1]{inputenc}
% oder was auch immer

%\usepackage{pxfonts}
%\usepackage{listings}
\usepackage{etex}
%\usepackage{ngerman}
\usepackage{xcolor}
\usepackage[retainorgcmds]{IEEEtrantools}

%\usepackage{times}
%\usepackage[T1]{fontenc}
% Oder was auch immer. Zu beachten ist, das Font und Encoding passen
% müssen. Falls T1 nicht funktioniert, kann man versuchen, die Zeile
% mit fontenc zu löschen.


\title[] % (optional, nur bei langen Titeln nötig)
{Optimierung durch Ganzzahl-Arithmetik für Mikrokontroller}

%\subtitle
%{Labortage 2011} % (optional)

\author[] % (optional, nur bei vielen Autoren)
{Martin~Ongsiek}
% - Der \inst{?} Befehl sollte nur verwendet werden, wenn die Autoren
%   unterschiedlichen Instituten angehören.


% - Der \inst{?} Befehl sollte nur verwendet werden, wenn die Autoren
%   unterschiedlichen Instituten angehören.
% - Keep it simple, niemand interessiert sich für die genau Adresse.

\date[labortage] % (optional)
{29.10.2011 / LABORTAGE}


\subject{Iabortalk}
% Dies wird lediglich in den PDF Informationskatalog einfügt. Kann gut
% weggelassen werden.


% Falls eine Logodatei namens "university-logo-filename.xxx" vorhanden
% ist, wobei xxx ein von latex bzw. pdflatex lesbares Graphikformat
% ist, so kann man wie folgt ein Logo einfügen:

% \pgfdeclareimage[height=0.5cm]{university-logo}{university-logo-filename}
% \logo{\pgfuseimage{university-logo}}


% Folgendes sollte gelöscht werden, wenn man nicht am Anfang jedes
% Unterabschnitts die Gliederung nochmal sehen möchte.
\AtBeginSubsection[]
{
  \begin{frame}<beamer>{Gliederung}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}


% Falls Aufzählungen immer schrittweise gezeigt werden sollen, kann
% folgendes Kommando benutzt werden:

%\beamerdefaultoverlayspecification{<+->}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}{Gliederung}
  \tableofcontents
  % Die Option [pausesections] könnte nützlich sein.
\end{frame}

% Da dies ein Vorlage für beliebige Vorträge ist, lassen sich kaum
% allgemeine Regeln zur Strukturierung angeben. Da die Vorlage für
% einen Vortrag zwischen 15 und 45 Minuten gedacht ist, fährt man aber
% mit folgenden Regeln oft gut.  

% - Es sollte genau zwei oder drei Abschnitte geben (neben der
%   Zusammenfassung). 
% - *Höchstens* drei Unterabschnitte pro Abschnitt.
% - Pro Rahmen sollte man zwischen 30s und 2min reden. Es sollte also
%   15 bis 30 Rahmen geben.

\section{Einleitung}

\subsection{Wann sollte man optimieren?}

\begin{frame}{Vorsicht vor Optimierungen!}
\begin{quote}
Rules of Optimization: \newline
Rule 1: Don't do it.\newline
Rule 2 (for experts only): Don't do it yet. \newline
Michael A. Jackson
\end{quote}

\pause
  \begin{itemize}
  \item Zeitverschwendung \pause
  \item Wartung und Verständis ist schwerer \pause
  \item Fehler \pause
  \item Notwendig?
  \end{itemize}
\small{http://www.clean-code-developer.de/Vorsicht-vor-Optimierungen.ashx}
\end{frame}

\begin{frame}{Wie sollte man vorgehen?}

  \begin{itemize}
 \item Die Software so einfach halten wie möglich.\pause 
 \item Das Rad nicht neu erfinden.\newline Bibithecksfunktionen sind bereits optimiert und getestet.\pause
 \item Vermeidung von blockierenden Code. z.B. delay(100);\newline Betriebssystem notwendig? \pause
 \item Zeit messen.\pause
 \item Kritische Programmteile finden 
  \end{itemize}
\end{frame}

\begin{frame}{Zahlensysteme}

\begin{tabular}[c] {ccc}
C-Grundtyp 		& int-Type 	& Wertebeich \\
\hline
unsigned char 	& uint8\_t 	& 0 \ldots 255 (0x00 \ldots 0xff) \\
signed char 		& int8\_t 	& -128 \ldots 127 (0x80 \ldots 0xff, 0 \ldots 0x7f)\\
unsigned short 	& uint16\_t 	& 0 \ldots 65535 \\
signed short 		& int16\_t 	& -32.768 \ldots 32.767\\
unsigned long 	& uint32\_t 	& 0 \ldots 4.294.967.295\\
signed long 		& int32\_t 	& -2.147.483.648 \ldots 2.147.483.647\\
\hline
\\
unsigned algemein& f\"ur n Bits & $0 \ldots (2^n-1)$ \\
signed algemein& f\"ur n Bits& $-(2^{n-1}) \ldots (2^{n-1}-1)$ \\
\end{tabular}
\end{frame}

\begin{frame}{Zeit messen}

\begin{itemize}
 \item Auf das Wesentliche beschränken.\pause 
 \item Störer abschalten, z.B. Interrupts.\pause
 \item Einen Timer zum Zeit messen verwenden.
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Zeit messen von Funktionen}
\begin{verbatim}
#define TIME_FUNC(func) print_exe_time(func,""#func) 
typedef void (*test_func_t)(void);
void print_exec_time(test_func_t func, char name[]) {
  TCCR1A = 0; TCCR1B = 0; TCNT1 = 0; TIFR  = 0; 
  TCCR1B = 1; // prescaler 1 Timer starten
  func();
  TCCR1B = 0; // Timer stoppen
  PrintSignedShortFormated(TCNT1);
  PrintString(" : ");
  PrintString(name);	
  PrintString("\n");
}
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Beispiel unoptimiert}
\begin{verbatim}
for (uint8_t t = 0; 
t < 100; t++) {
  for (uint8_t x = 0; x < 16; x++) {
    for (uint8_t y = 0; y < 16; y++) {
      buffer[x][y] = sqrt(t*t*x*x)*sin(y*y) + 566*t*y/300 
                     + 3*t*t;
    }
  }
  ausgabe(buffer);
}
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Optimierung Schritt 1}
Berrechnungen nicht unnötig wiederholen.
\begin{verbatim}
for (uint8_t t = 0; t < 100; t++) {
  uint32_t h1 = 566L*t, h2 = t*t; // 256 mal seltener
  uint32_t h3 = h2*3; 
  for (uint8_t x = 0; x < 16; x++) {
    uint16_t h4 = sqrt(h2*x*x);  // 16 mal seltener
    for (uint8_t y = 0; y < 16; y++) {
      buffer[x][y] = h4*sin(y*y) + h1*y/300 + h3;
    }
  }
  ausgabe(buffer);
}
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Optimierung Schritt 2}
Division ist langsam! \newline
Es sei denn, es wird durch eine 2er Potenzen geteilt.
\begin{IEEEeqnarray*}{c}
%\begin{eqnarray*}
\frac{\overbrace{566}^k \cdot t \cdot y}{300} \ 
\uncover<2->{= \frac{k \cdot c \cdot t \cdot y}{\underbrace{300 \cdot c}_{2^n}}} 
\uncover<6->{\alert{\approx \frac{483 \cdot t}{256}}} \\
\uncover<3->{n = 8 \Rightarrow c = \frac{256}{300}} 
\uncover<4->{\Rightarrow k \cdot c = \frac{256 \cdot 566}{300} = 482,9866} \\
\uncover<5->{Fehler = \frac{482,9866 - 483}{482,9866} = 0,00276 \%} 
%\end{eqnarray*}
\end{IEEEeqnarray*}
\end{frame}

\begin{frame}[fragile]{Optimierung Schritt 3}
Berrechnungen nicht unnötig wiederholen.
\begin{verbatim}
for (uint8_t t = 0; t < 100; t++) {
  uint32_t h1 = ((256*566+150)/300)*t, h2 = t*t; 
  uint32_t h3 = h2*3; 
  for (uint8_t x = 0; x < 16; x++) {
    uint16_t h4 = sqrt(h2*x*x);  // 16 mal seltener
    for (uint8_t y = 0; y < 16; y++) {
      buffer[x][y] = h4*sin(y*y) + ((h1*y) >> 8) + h3;
    }
  }
  ausgabe(buffer);
}
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Lookuptable mit Interpolation}
\begin{verbatim}
int16_t PROGMEM sin_table[66] = {0, 804, 1608 ... 32757};
static int16_t Sine(uint16_t phase) {
    int16_t s0;
    uint16_t tmp_phase= phase & 0x7fff, tmp_phase_hi;
    if (tmp_phase & 0x4000) //90 bis 180° 240 bis 360° 
        tmp_phase = 0x8000 - tmp_phase; //Tab. rückwärts
    tmp_phase_hi = tmp_phase >> 8; // 0...64
    s0 = PW(sin_table[tmp_phase_hi]); // Star
    s0 += ((int16_t)((((int32_t)(PW(sin_table[
         tmp_phase_hi+1]) - s0))*(tmp_phase&0xff))>>8));
    if (phase & 0x8000)  s0 = -s0; // Sinus ab 180° negativ
    return s0;
}
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Benutzen des Sinus}
\begin{tabular}[c] {cccc}
float sin in 	& float sin out  & int sin in & int sin out \\
\hline
$0,0$		& $0,0$	        	& 0        & 0 \\
$\frac{\pi}{2}$&$1,0$	        	& 0x4000   & 0x7FFF \\
$\frac{3\cdot\pi}{2}$&$-1,0$  	& 0xC000   & 0x8001 \\
\end{tabular}
\newline
Floatingpoint: sin(x) \\
Integer: Sine(x\_int) \\
Umwandlung von x nach x\_int $ \frac{x \cdot 0x7fff}{\pi} = 10430,06 $ 
\end{frame}

\begin{frame}[fragile]{Optimierung Schritt 4}
\begin{verbatim}
for (uint8_t t = 0; t < 100; t++) {
  uint32_t h1 = ((256*566+150)/300)*t, h2 = t*t; 
  uint32_t h3 = h2*3; 
  for (uint8_t x = 0; x < 16; x++) {
    uint32_t h4 = isqrt32(h2*x*x);  // 16 mal seltener
    for (uint8_t y = 0; y < 16; y++) {
      buffer[x][y] = (h4*Sine(10430L*y*y)) >> 15) + 
                     ((h1*y) >> 8) + h3;
    }
  }
  ausgabe(buffer);
}
\end{verbatim}
\end{frame}

\begin{frame}{Küstliche Nachkommastellen}

Durch Multiplikation eines Faktors $f$ zur einer Variablen $x$ kann man sich künstliche 
Nachkommastellen aus Ganzzahlen machen. Am effizentesten sind dabei 2er Protenz, da Dividieren und
und Modulo rechenaufwendig sind. \\
\begin{IEEEeqnarray*}{c}
\uncover<2->{x_n = x \cdot f }\uncover<3->{\Rightarrow x_n^2 = x \cdot f \cdot x \cdot f} \\
\uncover<4->{\frac{2 \cdot x_n}{y_n} = \frac{2\cdot x \cdot f}{y \cdot f}}
\end{IEEEeqnarray*}
\uncover<5->{Am Besten eien Einheit suchen in der man keine Nachkommastellen brauch.}
\end{frame}

% http://www.atmel.com/dyn/resources/prod_documents/doc1497.pdf

\end{document}