%--*- latex -*-----------------------------------------------------------------
%$Author: saulius $
%$Date: 2020-06-04 14:58:32 +0300 (Thu, 04 Jun 2020) $ 
%$Revision: 1524 $
%$URL: svn+ssh://saulius-grazulis.lt/home/saulius/svn-repositories/seminarai/2020-verifikacjos-seminarui/slides.tex $
%------------------------------------------------------------------------------

\documentclass[mathserif]{beamer}
\usetheme{Warwick}
\useoutertheme{infolines}
\setbeamertemplate{headline}{} % removes the headline the infolines inserts
%\setbeamertemplate{footline}[frame number]
\renewcommand\familydefault{\rmdefault}
% For XeLaTeX:
% https://tex.stackexchange.com/questions/452151/how-do-i-render-the-word-v%C7%ABlundarkvi%C3%B0a-with-bookman-and-xelatex
% "Use an OpenType clone of Bookman, for instance TeX Gyre Bonum":
\usepackage{fontspec}
\setmainfont{TeX Gyre Bonum}

\usepackage[style=authoryear,maxnames=1,doi=true,url=true,backend=biber]{biblatex}
%\addbibresource{bibliography/citations.bib}
%% \addbibresource{bibliography/Intel.bib}
\addbibresource{bibliography/Upton.bib}
\newcommand{\mycite}{\parencite}


\usepackage{colordvi}
\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{snakes}
\usepackage{chemfig}
\usepackage{listings}
% https://tex.stackexchange.com/questions/212069/listings-cannot-load-requested-language
\lstset{defaultdialect=[x86masm]Assembler}

% https://en.wikibooks.org/wiki/LaTeX/Algorithms
% http://mirror.datacenter.by/pub/mirrors/CTAN/macros/latex/contrib/algorithmicx/algorithmicx.pdf
\usepackage{algpseudocode}
\usepackage{algorithm}
\usepackage{amssymb}

\include{commands}

\newcommand{\RCSid}[1]{\fontsize{7pt}{7pt}\selectfont $#1$ \today}


%%BEGIN LANGUAGE en
\title{Pipelines}
%%END LANGUAGE en


\author{Saulius Gražulis}

\date{Vilnius, \the\year}

% Define colors as in
% https://venngage.com/blog/color-blind-friendly-palette/ ``Retro''
\definecolor{Bluish}{HTML}{63ACBE}
\definecolor{Magentish}{HTML}{601A4A}
\definecolor{Orangish}{HTML}{EE442F}

\begin{document}

\colorlet{IdentifierColor}{red!40!black}
\colorlet{StringColor}{green!70!black}
\colorlet{KwdColor}{Bluish}
\colorlet{CommentColor}{Orangish}

\colorlet{SignColor}{Bluish}
\colorlet{ExponentColor}{Magentish}
\colorlet{SignificandColor}{Orangish}

\colorlet{SC}{SignColor}
\colorlet{EC}{ExponentColor}
\colorlet{FC}{SignificandColor} % a.k.a. ``Fraction Color''

%------------------------------------------------------------------------------

\begin{frame}
    \titlepage

\input{affiliation}
    
    \begin{center}
      \mbox{}
      \hfill\hfill\hfill
      \includegraphics[height=1.5cm]{images/sp_VU_zenklas.eps}
      \hfill
      \includegraphics[height=1.5cm]{images/2019-05-02_Melynas_MIF-zenklas242x244.png}
      \hfill\hfill\hfill
      \mbox{}
    \end{center}

    \vfill

    %% \tiny
    %% \RCSid{
    %%   $Id: slides.tex 1524 2020-06-04 11:58:32Z saulius $
    %% }
    \begin{flushright}
      \begin{minipage}[c]{0.67\textwidth}
        \tiny\raggedright
        %%BEGIN LANGUAGE en
        This set of slides may be copied and used as specified in the
        %%END LANGUAGE en
        \myhref{http://creativecommons.org/licenses/by-sa/4.0/}{Attribution-ShareAlike
          4.0 International}
license
      \end{minipage}
      %%
      \begin{minipage}[c]{1.5cm}
        \myhref{http://creativecommons.org/licenses/by-sa/4.0/}{
          \includegraphics[width=1.5cm]{images/CC-BY-SA.eps}
        }
      \end{minipage}
    \end{flushright}

\end{frame}

%==============================================================================

\begin{frame}
\frametitle{Single cycle CPU}

  \begin{center}
    \only<1-2>{
      \parbox{12cm}{
        \includegraphics[width=\linewidth]{drawings/Harvard-CPU-Logisim/overal-without-decoder.png}
      }
    }
    \only<3>{
      \parbox{12cm}{
        \includegraphics[width=\linewidth]{drawings/Harvard-CPU-Logisim/overal-without-decoder-possible-stages.png}
      }
    }
    \only<4>{
      \parbox{12cm}{
        \includegraphics[width=\linewidth]{drawings/Harvard-CPU-Logisim/overal-without-decoder-stage-registers.png}
      }
    }
  \end{center}

  \parbox[c]{1pt}{
    \rule[-2cm]{0pt}{2cm}
  }
  \begin{minipage}[c]{0.9\textwidth}
    \visible<2->{
Propagation delay:
    }
    \only<2-3>{
      $$
      t_{\text{total}} = t_{\text{PC}} + t_{\text{ROM}} +
      t_{\text{decoder}} + t_{\text{RAM}} + t_{\text{ALU}} +
      t_{\text{Acc}}
      $$
    }
    \only<4>{
      $$
      t_{\text{total}} = \max ( t_{\text{PC}} + t_{\text{ROM}},
      t_{\text{decoder}}, t_{\text{RAM}}, t_{\text{ALU}}, t_{\text{Acc}}
      ) + t_{register}
      $$
    }
  \end{minipage}

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Ripes RISC-V single cycle}

  \begin{center}
    \includegraphics[width=12cm]{images/from-Ripes/Ripes-RISC-V-single-cycle.png}
  \end{center}

  \rightline{\scriptsize\myhref{https://github.com/mortbopet/Ripes.git}{M. B. Petersen,
      The Ripes simulator}}
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Ripes RISC-V 5 stage}

\framesubtitle{w/o forwarding or hazard detection}

  \begin{center}
    \includegraphics[width=12cm]{images/from-Ripes/Ripes-RISC-V-5-stage-no-hazard.png}
  \end{center}

  \rightline{\scriptsize\myhref{https://github.com/mortbopet/Ripes.git}{M. B. Petersen,
      The Ripes simulator}}
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Classic 5-stage pipeline}

  \begin{center}
    \includegraphics[width=12cm]{images/CPU-pipelines/Fivestagespipeline.eps}
  \end{center}

  \rightline{
    \scriptsize
    Sandstorm de, \myhref{https://creativecommons.org/licenses/by-sa/4.0}{CC BY-SA 4.0}
    via
    \myhref{https://commons.wikimedia.org/wiki/File:Fivestagespipeline.svg}{Wikimedia
      Commons}
  }

  \begin{itemize}
  \item
    RISC-V:
example cores with 5 stages;
  \item
    ARM:
ARM11 (Raspberry Pi) – 8-stage instruction pipeline
    \mycite{Upton2016};
  \item
    Intel:
many current CPUs have 20 stages or more
    \mycite{Upton2016};
  \end{itemize}
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Architecture of a really existing CPU}

Command
  \texttt{lstopo}
  
  \begin{center}
    \includegraphics[height=0.75\textheight]{images/lstopo-starta.png}
  \end{center}
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Hazards}

  \begin{itemize}
  \item
Control hazards: Caused by conditional branch instruction
  \item
Data hazards: Caused by data dependency between instructions
  \item
Structural hazards: Caused by resource conflicts
  \end{itemize}
  
\end{frame}

%------------------------------------------------------------------------------

\lstset{
  keywordstyle=\color{KwdColor},
  commentstyle=\color{CommentColor}\ttfamily,
  identifierstyle=\color{IdentifierColor},
  stringstyle=\color{StringColor},
  basicstyle=\ttfamily\tiny
}

\begin{frame}[containsverbatim]
\frametitle{Data hazards}

  \begin{center}
    \begin{minipage}{0.3\textwidth}
\begin{lstlisting}[language=Assembler,basicstyle=\ttfamily\normalsize]
add x5,x1,x2
add x7,x5,x1
\end{lstlisting}
    \end{minipage}
  \end{center}
  
  %%TODO: draw instruction positions in a pipline here (S.G.).

  \vspace{-\baselineskip}
  \begin{itemize}
  \item
Stages:

    \begin{tabular}{ll}
      \tt add \textbf{x5},x1,x2 & Memory (MEM) \\
      \tt add x7,\textbf{x5},x1 & Execute (EX) \\
    \end{tabular}
  \item
    \texttt{x5}
is not yet ready for the second instruction
  \item
Solutions:
    \begin{itemize}
    \item
Stall the pipeline/insert ``bubbles''
    \item
Reorder instructions (in software)

\begin{lstlisting}[language=Assembler,basicstyle=\ttfamily\normalsize,morekeywords={lw}]
add x5,x1,x2
lw  x20,(x11)
add x7,x5,x1
\end{lstlisting}
    \item
Reorder instructions (in hardware)
    \item
Fast-forward the data
    \end{itemize}
  \end{itemize}
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}[containsverbatim]
\frametitle{Control hazards}

  \begin{center}
    \begin{minipage}{0.3\textwidth}
\begin{lstlisting}[language=Assembler,basicstyle=\ttfamily\normalsize]
add x5,x1,x2
bgt x1,x2,label
add x7,x5,x1
\end{lstlisting}
    \end{minipage}
  \end{center}
  
  %%TODO: draw instruction positions in a pipline here (S.G.).

  \vspace{-\baselineskip}
  \begin{itemize}
  \item
Stages:

    \begin{tabular}{ll}
      \tt add \textbf{x5},x1,x2 & Memory (WB) \\
      \tt bgt x1,x2,label       & Execute (MEM) \\ 
      \tt add x7,\textbf{x5},x1 & Decode (EX) \\
    \end{tabular}
  \item
    \texttt{x5}
The next \texttt{add} must not be executed!
  \item
Solutions:
    \begin{itemize}
    \item
Reset the pipeline/insert ``bubbles'';
    \item
Execute \texttt{add} anyway (delay slot);
    \item
Speculative execution;
    \end{itemize}
  \end{itemize}
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Convergence of CISC and RISC}

  \begin{itemize}
  \item
Large number of registers ($\ge 16$);
  \item
Orthogonal instruction sets;
  \item
Load/Store operation
  \item
Pipelines
  \item
Instruction and data caches
  \item
Modified Harvard architecture
  \end{itemize}
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}[allowframebreaks]
\frametitle{References}

  \setmainfont{Liberation Serif}
  \renewcommand{\bibfont}{\scriptsize}
  \printbibliography

\end{frame}

%------------------------------------------------------------------------------                                                                                                          
\end{document}
% 2023-12-18 11:00:12 EET