chapter9.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Test file for the Wuppertal beamer style
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Karsten Kahl, 15.10.2012
% kkahl@math.uni-wuppertal.de
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass[12pt,rgb]{beamer}
%%% Switch to for top-aligned frames
%\documentclass[12pt,t]{beamer}

\usetheme[green,minimal,nologo,total,german]{Wuppertal}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Options :
%% Style (see outer themes) :
%%% minimal : no navigation; no outline; plain and simple.
%%% presentation (default): no navigation; outline at begin of each section
%%%           (suppress with section*)
%%% talk : horizontal section navigation in headline
%%% talkext : horizontal section navigation in headline with logo in top left corner
%%% lecture : adds section and subsection navigation in headline
%%%           if #sections or #subsections greater 3 adds logo in top left corner
%% ----------------
%% Color (see color themes) :
%%% vier (default): built around colours of Fakultaet 4
%%%% Additional Color-Option
%%% inverted: white on black.
%% ----------------
%% Logo in lower right corner (see outer themes) :
%%% lion: half lion in color of style
%%% logo (default): BUW logo papperl
%%% biglion: half lion in background
%%% nologo: no logo
%% ----------------
%% Miscellaneous:
%%% german: sets main language to german (Part X to Teil X)
%%% nototal: no display of total page numbers ("page/total number of pages" to "page")
%%% imacm: places IMACM papperl on title page and 
%%%        replaces logo in top left corner by IMACM logo (if applicable)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Algorithm package with beamer friendly option-set
\usepackage[linesnumberedhidden,vlined]{algorithm2e}
\usepackage{tikz}
\usepackage{tcolorbox}
% Use Option linesnumbered if you want to have line numbers
\DontPrintSemicolon
\SetKwFor{For}{for}{}{}
\SetKwFor{While}{while}{}{}
% Change to increase or decrease font size or appearance in the algorithm
\SetAlFnt{\footnotesize}

% Used for the TikZ example
\usetikzlibrary{shapes}
\usepackage{minted}

\begin{document}
    \title[Kommunikation und Synchronization]{Kommunikation und Synchronization}
    \subtitle{Kapitel 9 - Data Parallel C++}
    \author[Alexander Wallrodt]{Alexander Wallrodt}
    \institute{Bergische Universität Wuppertal}
    
    \maketitle
    
    \begin{frame}{Rückblick}
        \begin{itemize}
            \item Work-Groups: Beinhalten mehrere Work-Items
            \item Work-Items: Eine Instanz eines Kernels
            \item ND-range: Dimensionale Ausführung von Work-Items
        \end{itemize}
        \begin{figure}
            \centering
            \includegraphics[width=110mm]{images/Chapter 9-3}
            \label{fig:chapter-9-3}
        \end{figure}
    \end{frame}

    \begin{frame}[fragile]{Naive Anwendung}
        \framesubtitle{Rückblick}

        \begin{itemize}
            \item Einfacher Parallelismus
        \end{itemize}
        \vspace{0.5em}
        \inputminted[breaklines,mathescape,linenos,numbersep=5pt,frame=single,numbersep=5pt,xleftmargin=0pt,fontsize=\footnotesize]{cpp}{code/naive_mat_mul.cpp}
        \vspace{0.5em}
        \begin{itemize}
            \item Weiterführende Beispiele auch anhand von Matrix-Multiplikation
            \item Nun wollen wir Kommunikation und Synchronization ermöglichen
        \end{itemize}
    \end{frame}

    \begin{frame}{Synchronization über Barriers}
        \framesubtitle{Grundlagen für effiziente Kommunikation}
        \begin{itemize}
            \item Synchronisiert Work-Items innerhalb ihrer Work-Group
            \item Falls eine Teilberechnung fertig ist, wartet diese
            \item Jedes Work-Item benötigt ein Barrier-Aufruf
            \item Ermöglicht Speicherbeständigkeit (\textit{memory consistency} oder \textit{fencing} gennant)
        \end{itemize}
        \vspace{0.5em}
        \begin{figure}
            \centering
            \includegraphics[width=80mm]{images/Chapter 9-1-hydraulic-press-channel-tm}
            \label{fig:chapter 9-1-hydraulic-press-channel-tm}
        \end{figure}
    \end{frame}

    \begin{frame}{Lokale Speicher für Work-Groups}
        \framesubtitle{Grundlagen für effiziente Kommunikation}
        \begin{itemize}
            \item Effizienter und einfacher als USM oder Buffer
            \item Ermöglicht lokalen Zugriff innerhalb einer Gruppe
            \item Einfachheitshalber, aber auch sehr schnell auf bestimmten Hardwareumgebungen
            \item Temporärer Speicher zur Laufzeit
            \vspace{0.5em}
            \begin{figure}
                \centering
                \includegraphics[width=90mm]{images/Chapter 9-2}
                \label{fig:chapter 9-2}
            \end{figure}
        \end{itemize}
    \end{frame}

    \begin{frame}[fragile]{Local Accessors}
        \framesubtitle{Anwendung mit ND-Range Kernel}
        \begin{itemize}
            \item Wird deklariert vor der Ausführung der Kernels
            \item Zunächst uninitialisiert
            \item Angabe der Länge (Aber auch 1, 2 oder 3 dimensional)
            \item Nur nutzbar mit ND-Range
        \end{itemize}
        \vspace{0.5em}
        \inputminted[breaklines,mathescape,linenos,numbersep=5pt,frame=single,numbersep=5pt,xleftmargin=0pt,fontsize=\footnotesize]{cpp}{code/local_accessor.cpp}
    \end{frame}

    \begin{frame}{Synchronisierungsfunktionen}
        \framesubtitle{Anwendung mit ND-Range Kernel}
        \begin{itemize}
            \item Aufruf über die \texttt{group\_barrier(g)} Funktion
            \item Synchronisierung innerhalb der Work-Group
            \item Ebenfalls nur nutzbar mit ND-Range
            \item Scopes
            \begin{itemize}
                \item Meist automatisch gewählt (Nur Work-Group)
                \item Kann den Zugriff erweitern
                \item Z.B. \texttt{g, group\_barrier(g, memory\_scope::device)} oder \texttt{group\_barrier(g, memory\_scope::system)}
            \end{itemize}
        \end{itemize}
    \end{frame}

    \begin{frame}[fragile]{Beispiel \textrm{I}}
        \framesubtitle{Anwendung mit ND-Range Kernel}
        \inputminted[breaklines,firstline=1,lastline=10,mathescape,linenos,numbersep=5pt,frame=single,numbersep=5pt,xleftmargin=0pt,fontsize=\footnotesize]{cpp}{code/usecase_nd_range.cpp}
    \end{frame}

    \begin{frame}[fragile]{Beispiel \textrm{II}}
        \framesubtitle{Anwendung mit ND-Range Kernel}
        \inputminted[breaklines,firstline=11,lastline=19,mathescape,linenos,numbersep=5pt,frame=single,numbersep=5pt,xleftmargin=0pt,fontsize=\footnotesize]{cpp}{code/usecase_nd_range.cpp}
    \end{frame}

    \begin{frame}[fragile]{Beispiel \textrm{III}}
        \framesubtitle{Anwendung mit ND-Range Kernel}
        \inputminted[breaklines,firstline=20,lastline=36,mathescape,linenos,numbersep=5pt,frame=single,numbersep=5pt,xleftmargin=0pt,fontsize=\footnotesize]{cpp}{code/usecase_nd_range.cpp}
    \end{frame}

    \begin{frame}{Sub-Groups}
        \framesubtitle{Anwendung mit ND-Range Kernel und Sub-Groups}
        \begin{itemize}
            \item Zusammenfassung bestimmter Work-Items
            \item Ermöglicht Garantien bezüglich Hardwareressourcen und Scheduling
            \item Es folgt mehr Effizienz
            \item Basiert auf Work-Groups, daher auch abhängig von ND-Range
        \end{itemize}
    \end{frame}

    \begin{frame}{Synchronisierung innerhalb Sub-Groups}
        \framesubtitle{Anwendung mit ND-Range Kernel und Sub-Groups}
        \begin{itemize}
            \item Funktioniert auf gleiche Weise wie bei Work-Groups nur wird nun die Sub-Group angegeben \texttt{group\_barrier(sg)}
            \item Potentiell nicht benötigt, da durch Hardware eine Step-by-Step-Ausführung gegeben sein kann
        \end{itemize}
        \vspace{0.5em}
        \inputminted[breaklines,mathescape,linenos,numbersep=5pt,frame=single,numbersep=5pt,xleftmargin=0pt,fontsize=\footnotesize]{cpp}{code/sync_sub_groups.cpp}
    \end{frame}

    \begin{frame}{Datenaustausch}
        \framesubtitle{Anwendung mit ND-Range Kernel und Sub-Groups}
        \begin{itemize}
            \item Lokaler Speicher ist nicht mehr die bevorzugte Variante Daten auszutauschen
            \item Stattdessen wird die \texttt{group\_broadcast(sg, x, id)} Funktion verwendet
            \begin{itemize}
                \item \texttt{sg}: Sub Group ID
                \item \texttt{x}: zu teilender Wert
                \item \texttt{id}: Lokale ID des Work-Items
            \end{itemize}
            \item Die lokale ID muss immer gleich sein, damit andere Work-Items den Wert erhalten können
            \item Auch innerhalb von normalen Work-Groups möglich, aber tendenziell langsamer
        \end{itemize}
    \end{frame}

    \begin{frame}{Beispiel \textrm{I}}
        \framesubtitle{Anwendung mit ND-Range Kernel und Sub-Groups}
        \inputminted[breaklines,firstline=1,lastline=10,mathescape,linenos,numbersep=5pt,frame=single,numbersep=5pt,xleftmargin=0pt,fontsize=\footnotesize]{cpp}{code/usecase_sub_groups.cpp}
    \end{frame}

    \begin{frame}{Beispiel \textrm{II}}
        \framesubtitle{Anwendung mit ND-Range Kernel und Sub-Groups}
        \inputminted[breaklines,firstline=11,lastline=24,mathescape,linenos,numbersep=5pt,frame=single,numbersep=5pt,xleftmargin=0pt,fontsize=\footnotesize]{cpp}{code/usecase_sub_groups.cpp}
    \end{frame}

    \begin{frame}{Gruppenfunktionen}
        \begin{itemize}
            \item Auch \textit{collective functions} genannt
            \item Z. B. \textit{Barriers} oder \textit{Broadcast}
            \item Funktionen welche von jedem einzelnen Work-Item aufgerufen werden
            \item Meistens stark optimiert und an Hardware angepasst
        \end{itemize}
    \end{frame}

    \begin{frame}{Votes}
        \framesubtitle{Gruppenfunktionen}
        \begin{figure}
            \centering
            \includegraphics[width=100mm]{images/Chapter 9-6}
            \label{fig:chapter 9-6}
        \end{figure}
        \begin{itemize}
            \item Ermöglicht Austausch von Entscheidungen basierend auf \textit{bool}-Werten
            \item Möglichkeit auch andere Datenobjekte zu vergleichen \textit{joint\_any\_of}, \textit{joint\_all\_of} und \textit{joint\_none\_of}
            \item Durch Groups und Sub-Groups unterstützt
        \end{itemize}
    \end{frame}

    \begin{frame}{Shuffels \textrm{I}}
        \framesubtitle{Gruppenfunktionen}
        \begin{itemize}
            \item Direkte Kommunikation ohne explizit den Speicher nutzen zu müssen
            \item \texttt{select\_from\_group(sg, x, id)}
            \begin{itemize}
                \item Ermöglicht Zugriff auf Werte aud bestimmten Work-Items
                \item In spezieller Form identisch mit \texttt{group\_broadcast()}
            \end{itemize}
            \item \texttt{shift\_group\_right(sg, x, delta)} und \texttt{shift\_group\_left(sg, x, delta)}
            \begin{itemize}
                \item Werte innerhalb eine Sub-Group nach rechts / links verschieben.
                \item Verschobene Zellen werden nicht wieder aufgefüllt
            \end{itemize}
        \end{itemize}
    \end{frame}

    \begin{frame}{Shuffels \textrm{II}}
        \framesubtitle{Gruppenfunktionen}
        \begin{figure}
            \centering
            \includegraphics[width=100mm]{images/Chapter 9-9}
            \label{fig:chapter 9-9}
        \end{figure}
        \begin{itemize}
            \item \texttt{permute\_group\_by\_xor(sg, x, mask)}
            \begin{itemize}
                \item Wended ein XOR auf jeden Wert mit dem Wert von mask an
            \end{itemize}
        \end{itemize}
        \vspace{0.5em}
        \begin{itemize}
            \item Shuffles nur durch Sub-Groups unterstützt
        \end{itemize}
    \end{frame}
\end{document}