\documentclass[aspectratio=169]{beamer}

\usepackage{appendixnumberbeamer}

\usepackage[utf8]{inputenc}
\usepackage[english]{babel}

\usepackage{standalone}

\usepackage{booktabs}
\usepackage{multirow}

\usepackage{csquotes}

\usepackage[backend=biber, style=authortitle-icomp]{biblatex}
\bibliography{bibliography}

\input{common.tex}

\setlist[itemize]{noitemsep, label={\color{i4blue}\raise1pt\hbox{\vrule width 0.8ex height 0.8ex}}}

\drefinput{syscall-measurements}
\drefinput[sl/]{sleep-latency-eval-results}

\usepackage{wasysym}
\usepackage{subcaption}
\usepackage{cellspace}

\usepackage{multicol}

\newcommand{\pro}{\item[\color{brightGreen} \smiley{}]}
\newcommand{\neutral}{\item[\color{gray} \smiley{}]}
\newcommand{\contra}{\item[\color{red} \frownie{}]}

\renewcommand{\io}{I/O}

\usetheme[sectionpage=none]{neo}
\neoset{frametitle icon=i4}
\neoset{block=fill}
\setbeamercolor{block body alerted}{bg=alerted text.fg!20}

\title{Elevating System Requests to First-Class Citizens of Work-Stealing Concurrency Platforms}
\date{\today}
\author{Florian Fischer}
\institute{Friedrich-Alexander-Universität Erlangen-Nürnberg}

\titlegraphic{
  \includegraphics[height=1.2cm]{logo-i4-de.pdf}
  \hfill
  \includegraphics[height=1.2cm]{logo-fau-tf-de.pdf}
}

\begin{document}

\maketitle[intern]

\begin{frame}[t]
  \frametitle{Motivation}

  \vspace{1cm}

  \begin{columns}
    \begin{column}{0.5\textwidth}
      \only<1-2> {
        \inputminted[frame=none, tabsize=2, fontsize=\footnotesize]{cpp}{code/emper-server-slides.cpp}
      }

      \only<3> {
        What We Still Want:

        {\small
        \begin{itemize}
          \item Reduce Special Treatment of System-Request Completions
          \item Apply CP Research Knowledge to System-Requests
          \item Minimize Latency and Maximize Throughput
          \item Adapt To Heterogeneous System-Request Work Loads
        \end{itemize}
        }
      }
    \end{column}

    \begin{column}{0.5\textwidth}
      \only<1> {
        What We Have:

        \begin{itemize}
          \item Simple pseudo-blocking API
          \item Efficient Asynchronous System-Requests
          \item Fiber Aware Worker Suspension
        \end{itemize}
      }

      \only<3> {
        \vspace{-0.56cm}
      }
      \only<2-3> {
        \inputminted[frame=none, tabsize=2, fontsize=\footnotesize]{cpp}{code/emper-fibers.cpp}
      }
    \end{column}
  \end{columns}

  \only<2>{
    \begin{center}
      Should Differ as Less as Possible
    \end{center}
  }
\end{frame}

\begin{frame}{Overview}
  \tableofcontents
\end{frame}

\section{Fundamentals}
\subsection{Concurrency Platforms}
\begin{frame}<8>[fragile, t, label=cp]{Concurrency Platform}
  \hspace{2.5cm}
  \begin{adjustbox}{max totalsize={.8\textwidth}{.135\textheight}}
    \input{figures/concurrency_platform.tikz}
  \end{adjustbox}
\end{frame}

\begin{frame}
  \frametitle{Scheduling Theory}
  \begin{figure}
    \includegraphics[height=0.3\textheight, keepaspectratio]{dag}
    \caption{Concurrent Computation modelled as DAG\footcite{erhardt2020phd}}
  \end{figure}
  \vspace{-0.5cm}
  \begin{block}{Greedy Schedule}
    \begin{itemize}
      \item Execute $P$ or all available computations in each steap
      \item Speedup: $T_P \leq \frac{T_1}{P} + T_\infty$~\footcite{blumofe1999scheduling}
    \end{itemize}
  \end{block}
  \vspace{0.5cm}
\end{frame}

\begin{frame}
  \frametitle{Work Stealing}

  \begin{columns}
    \begin{column}{.5\textwidth}
      \begin{figure}
        \includegraphics[width=\textwidth, keepaspectratio]{ws}
      \end{figure}
    \end{column}

    \begin{column}{.5\textwidth}
      \begin{block}{Theory}
        \begin{itemize}[]
          \item Well-Known
          \item Efficient, Optimistic, Distributed
          \item Specialized Data Structures
          \item Good Locality
        \end{itemize}
      \end{block}

      \begin{block}{Implementation}
        \begin{itemize}
          \item Exclusive CL-Queue~\footcite{chase2005dynamic}
          \item Exclusive MPSC Queue
          \item Global Queue
        \end{itemize}
      \end{block}
    \end{column}
  \end{columns}
\end{frame}

\subsection{System Requests}

\begin{frame}
  \frametitle{Synchronous System Requests}

  \begin{columns}
    \begin{column}{.4\textwidth}
      \begin{figure}
        \includestandalone[height=0.8\textheight, keepaspectratio]{sync-request}
      \end{figure}
    \end{column}
    \begin{column}{.6\textwidth}
      E.g., \texttt{read/write}, \texttt{send/recv}, ...
      \begin{block}{Pro/Cons}
        \begin{itemize}
          \pro Simple
          \contra Many Context-Switches
          \contra May Cause the Blocking Anomaly
          \contra No Overlapping of Heterogenous Requests
        \end{itemize}
      \end{block}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Asynchronous System Requests}

  \begin{columns}
    \begin{column}{.4\textwidth}
      \begin{figure}
        \includestandalone[height=0.8\textheight, keepaspectratio]{async-request}
      \end{figure}
    \end{column}
    \begin{column}{.6\textwidth}
      E.g., \texttt{IoCompletionPorts}, \texttt{io\_uring}, ...
      \begin{block}{Pro/Cons}
        \begin{itemize}
          \pro Latency hiding
          \pro Potentially Exception-Less~\footcite{soares2010flexsc}
          \contra Complex
        \end{itemize}
      \end{block}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{io\_uring - Asynchronous Queue-Based}

  \begin{columns}
    \begin{column}{.7\textwidth}
      \begin{figure}
        \vspace{-0.5cm}
        \includestandalone[width=1.075\textwidth, keepaspectratio]{iouring}
      \end{figure}
    \end{column}

    \begin{column}{.3\textwidth}
      \begin{block}{Features}
        % \begin{itemize}
          \small
          % \item Memory-Mapped Rings
          % \item Worker-Pool
          % \item Internal Poll
          % \item Cancelation
          % \item Linking Requests
        % \end{itemize}
         \vspace{0.1cm}
         Memory-Mapped Rings

         Completion Notifications

         Internal Poll

         Worker-Pool

         Cancelation

         Linking Requests

         SQPOLL
      \end{block}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{System Request Interface Comparison~\footnote{Based on \cite{schmaus2021modern}}}
  \begin{table}[h]
    \centering
    % \caption{Comparison of \io{} syscall techniques based on Schmaus, Fischer et al.~\cite{schmaus2021modern}}
    \label{tab:syscall-techniques}
    \resizebox{\columnwidth}{!}{%
      \begin{tabular}{l l l c c r @{\hspace{.6mm}} l c}
      \toprule
      & & & \multicolumn{2}{c}{\textbf{Per \io{} request}} & & &\\
      \cmidrule(r){4-5}
      \textbf{Kind} & \textbf{Mechanism} & \textbf{Examples} & \textbf{Syscalls} & \textbf{CSW} & \multicolumn{2}{c}{\textbf{Cost[ns}} & \textbf{Mitigation cost}\\
      \midrule
      Sync & Blocking & \texttt{read()}, \texttt{write()} & 1 & 2 & \absTime{blocking} & \mitigationOverhead{blocking}\\
      Sync & Non-Blocking & O\_NONBLOCK \& \texttt{epoll()} & $[1, 3]$ & $[2, 6]$ & \absTime{epoll} & \mitigationOverhead{epoll}\\
      \midrule
      % Async & Queue-based & Linux~AIO~\footcite{bhattacharya2003asynchronous} & $]0, 2]$ & $]1, 4]$ & \absTime{linux-aio} & \mitigationOverhead{linux-aio}\\
      Async & Queue-based & \iouring{} & $]0, 2]$ & $]1, 4]$ & \absTime{io-uring} & \mitigationOverhead{io-uring}\\
      Async & Queue-based & \iouring{} \& $\text{Batch}_3$& $]0, 2]$ & $]1, 4]$ & \color{Green} \absTime{io-uring-batch3} & \mitigationOverhead{io-uring-batch3}\\
      Async & Queue-based & \iouring{} \& SQPOLL & $[0, 2]$ & $[0, 4]$ & \color{Green} \absTime{io-uring-no-syscall} & \mitigationOverhead{io-uring-no-syscall}\\
      \bottomrule
      \end{tabular}
    }
  \end{table}
\end{frame}

\subsection{System-Request Integration}

\begin{frame}
  \frametitle{System-Request Integration Goals}
  \begin{itemize}
    \setlength\itemsep{0.5em}
    \item Prevent the Blocking Anomaly
    \item Reduce Synchronization and Syscalls for Scalability
    \item Utilize Parallel Hardware via Parallel Submission
    \item Distribute the Resulting Request Continuations
    \item Exploit Locality by Continuing Fibers on the Same Worker
    \item Provide a Simple and Safe API with Powerful Features (Linking, Canceling)
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Status Quo}

  \begin{columns}
    \begin{column}{.65\textwidth}
      \vspace{-0.5cm}
      \begin{figure}
        \includestandalone[width=1.1\textwidth, keepaspectratio]{emper-io-arch-completer-static}
      \end{figure}
    \end{column}
    \begin{column}{.35\textwidth}
      % {\small
      \begin{block}{Implementation}
        \begin{itemize}
          \item Exclusive Rings
          \item Pseudo-Blocking API
          \item Semaphore Suspension
          \item Completer Thread
        \end{itemize} 
      \end{block}

      \pause

      \begin{block}{Pro/Cons}
        \begin{itemize}
          \pro Scalable
          \pro Simple
          \contra Result Disribution 
        \end{itemize}
      \end{block}
      % }
    \end{column}
  \end{columns}
\end{frame}

\section{Mitigate Request-Continuation Latency}

\begin{frame}
  \frametitle{Request-Continuation Latency}

  \begin{block}{Request-Continuation}
    \textit{New or Unblocked Fiber Scheduled due to Reaping a Request Completion}
  \end{block}

  \vspace{0.5cm}

  \pause

  \begin{block}{Request-Continuation Latency}
    \textit{Time between Completion Generation and Execution of a caused Continuation}
  \end{block}

  \vspace{0.5cm}

  \pause

  \begin{block}{Sources of Delay}
    \begin{itemize}
      \item High System Load
      \item Context- or Task-Switch Overhead
      \item Completions are not considered in the Schedule
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Request-Continuation Latency Mitigation}
  \begin{figure}
    \begin{subfigure}[t]{0.49\textwidth}
      \includestandalone[width=0.9\textwidth, keepaspectratio]{io-dag}
      \caption{Status Quo - Asynchronously Created Completions not Included in the Schedule}
    \end{subfigure}
    \pause
    \hfill
    \begin{subfigure}[t]{0.49\textwidth}
      \includestandalone[width=0.9\textwidth, keepaspectratio]{integrated-io-dag}
      \caption{Ideal - Asynchronously Created Completions Considered in the Scheduling}
    \end{subfigure}
  \end{figure}

  \pause

  \begin{block}{Missing Pieces}
    \begin{itemize}
      \item Workers do not distribute Completions
      \item Workers are not notified about Completions
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Status Quo - Completer}
  \begin{block}{Completer}
    \begin{itemize}
      \item Dedicated Thread and \iouring{}
      \item Monitors Worker-Exclusive Rings
      \item Reaps Completions and Schedules Continuations
      \item Guarantees Progress when Suspending not Completion-Aware
    \end{itemize}
  \end{block}

  \pause

  \begin{block}{Pros/Cons}
    \begin{itemize}
      \pro No Overhead if not Used
      \contra Oversaturating Available Cores
      \contra Schedules to Expensive Global Queue
      % \contra Destroys Locality
    \end{itemize}
  \end{block}
\end{frame}

\subsection{Request-Continuation Distribution}

\begin{frame}
  \frametitle{Completion-Stealing}

  \begin{columns}
    \begin{column}{0.6\textwidth}
      \begin{figure}
        \includegraphics[width=0.92\textheight, keepaspectratio]{io-stealing}
      \end{figure}
    \end{column}

    \begin{column}{0.4\textwidth}
      \begin{block}{Implementation}
        \begin{itemize}
          \item Steal During Work-Stealing
          \item Try-Lock Synchronization
          \item Not Stealing New Work Notifications
        \end{itemize}
      \end{block}

      \pause

      \begin{block}{Pro/Cons}
        \begin{itemize}
          \pro Same as Work-Stealing
          \contra Synchronization Overhead
        \end{itemize}
      \end{block}
    \end{column}
  \end{columns}
\end{frame}

\subsection{Completion-Aware Worker Suspension}

\begin{frame}
  \frametitle{Worker Suspension}
  \begin{block}{Requirements}
    \begin{itemize}
      \item Suspend Idle Worker Threads
      \item Notify Any, Many, All, Specific
      \item Guarantee Process
    \end{itemize}
  \end{block}

  \pause

  \begin{block}{Nice-to-Have}
    \begin{itemize}
      \item Do Nothing if System is Saturated
      \item Hint Locations (Mitigate Initial Random Stealing)
      \item Integrate Kernel (Multiprogramming)
      \item Notify About Completions
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Status Quo - Semaphore-Based Suspension}

  \begin{columns}
    \begin{column}{.5\textwidth}
      \begin{figure}
        \includegraphics[width=\textwidth, keepaspectratio]{sem-suspension}
      \end{figure}
    \end{column}
    \begin{column}{.5\textwidth}
      \begin{block}{Implementation}
        \begin{itemize}
          \item Global Semaphore $c$ Tracking Work
          \item Notification Elision Threshold $t$
          \item Notify Specific via \texttt{futex\_waitv}
        \end{itemize}
      \end{block}

      \pause

      \begin{block}{Pro/Cons}
        \begin{itemize}
          \pro Efficient
          \neutral Fair
          \contra Not Aware of Completions
          \item[$\Rightarrow$] Requires Completer
          \contra No Improvements Possible
        \end{itemize}
      \end{block}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}[t]
  \frametitle{io\_uring-Based Suspension}

  \vspace{0.25cm}

  \begin{block}{Implementation}
    \begin{itemize}
      \item Global Sleeper Count
      \item Suspend Workers Waiting for Completions
      \item Notify Workers by Writing to a Global I/O Object
      \item Notify Specific via \texttt{IORING\_OP\_MSG\_RING}
      \item Pass Location Information
    \end{itemize} 
  \end{block}

  \pause

  \begin{block}{Pro/Cons}
    \begin{itemize}
      \pro Suspended Workers are Notified about Local Completions
      \pro Guarantees Progress Without the Completer
      \pro Location Hints Mitigate Ramp-Up
      \contra There is No Really Suitable I/O Object
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{suspendfd}

  \begin{block}{Implementation}
    \begin{itemize}
      \item Linux Kernel \texttt{futex}-Inspired I/O Object
      \item Queue, Mapped Sleeper Count and Spinlock
      \item Pass Data Onto Stack on Rendezvous
    \end{itemize}
  \end{block}

  \pause

  \begin{block}{Pro/Cons}
    \begin{itemize}
      \pro Efficient
      \pro Allows Kernel to Notify
      \neutral Unfair
      \contra Not Pollable
      \contra No Location when Skipping Sleeps
    \end{itemize}
  \end{block}
\end{frame}

\section{Results}

\begin{frame}
  \frametitle{Benchmarks}

  \begin{block}{Micro-Benchmarks}
    \begin{itemize}
      \item Pulse Benchmark
      \item \io{}-Continuation Benchmark
    \end{itemize}
  \end{block}

  \vspace{1cm}

  \begin{block}{Application-Benchmarks}
    \begin{itemize}
      \item Echo Server
      \item File Search
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Completion-Stealing Impact - Echo Server}

  \begin{columns}
    \begin{column}{.55\textwidth}
      \begin{figure}
        \vspace{-0.25cm}
        \includestandalone[width=1.05\textwidth, keepaspectratio]{io-stealing-slides}
      \end{figure}
    \end{column}

    \begin{column}{.45\textwidth}
      \begin{block}{Experiment}
        \begin{itemize}
          \item Echo Server
          \item Server on \texttt{big02} (80 Cores)
          \item Client on \texttt{big03} (96 Cores)
        \end{itemize}
      \end{block}

      \begin{block}{Observations}
        \begin{itemize}
          \pro Stealing Improves Status Quo
          \pro \waitfd{} Marginally Better
          \neutral I/O Suspension and Stealing are Agonists
        \end{itemize}
      \end{block}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Completion-Aware Suspension Impact - Pulse Micro-Benchmark}

  \vspace{0.5cm}

  \begin{block}{Experiment}
    \begin{itemize}
      \item Introduce Computational Work
      \item Target System Utilization: $U * P = W$
      \item Measure Work Latency and Energy
    \end{itemize}
  \end{block}

  \vspace{0.5cm}

  \pause

  \begin{block}{Observations}
    \begin{itemize}
      \pro Hints are Great ({\color{Green} -\slAvgHintMedianImprovement{waitfd}\%})
      \pro Completer Increases Latency when Oversaturating
      \contra More Complex \iouring{} Code is Expensive 
      \vspace{0.5cm}
      \item[$\Rightarrow$] Completion-Aware Suspension only Reasonable when Doing Requests
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}[t]
  \frametitle{Completion-Aware Suspension Impact - Latency Micro-Benchmark}

  Baseline Not-Sleeping and Stealing Completions: ~10 microseconds

  \only<1>{
    \vspace{1cm}
    \begin{block}{Experiment}
      \begin{itemize}
        \item Prepare Read from \texttt{eventfd}
        \item Enter Busy Loop for 100 milliseconds
        \item Write to \texttt{eventfd} When the Read is Prepared
        \item Measure the Time Between Writing and Execution of the Read Continuation
      \end{itemize}
    \end{block}
  }

  \pause
  
  \begin{columns}
    \begin{column}{.5\textwidth}
      \begin{figure}
        \includestandalone[width=\textwidth, keepaspectratio]{iol-strategies-slides}
      \end{figure}
    \end{column}

    \pause

    \begin{column}{.5\textwidth}
      \begin{figure}
        \includestandalone[width=\textwidth, keepaspectratio]{iol-notification-stealing-completer-slides}
      \end{figure}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Completion-Aware Suspension Impact - File Search}

  \begin{columns}
    \begin{column}{.55\textwidth}
      \begin{figure}
        \includestandalone[width=1.2\textwidth, keepaspectratio]{fs-ssd-slides}
      \end{figure}
    \end{column}

    \begin{column}{.45\textwidth}
      \begin{block}{Experiment}
        \begin{itemize}
          \item Searching \texttt{io\_uring} in Linux
          \item Using a SSD
          \item On \texttt{big03} Using 96 Cores
        \end{itemize}
      \end{block}

      \begin{block}{Observations}
        \begin{itemize}
          \pro Completion Aware Suspension
          \pro \waitfd{} Marginally Better 
          \pro Not Relying on the Completer
        \end{itemize}
      \end{block}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}[standout]
  \begin{center}
    {\Large Thank you for your attention!}
  \end{center}
\end{frame}

\begin{frame}[standout]
  \begin{center}
    Free Software
  \end{center}

  \begin{itemize}
    \setlength\itemsep{0.15em}
  \item {\small \url{https://gitlab.cs.fau.de/i4/manycore/emper}}
  \item {\small \url{https://gitlab.cs.fau.de/i4/manycore/kernel-emper}}
  \item {\small \url{https://gitlab.cs.fau.de/i4/manycore/emper-io-latency-eval}}
  \item {\small \url{https://gitlab.cs.fau.de/i4/manycore/emper-sleep-latency-eval}}
  \item {\small \url{https://gitlab.cs.fau.de/i4/manycore/emper-io-eval}}
  \item {\small \url{https://gitlab.cs.fau.de/i4/manycore/emper-fs-eval}}
  \item {\small \url{https://github.com/axboe/liburing}}
  \end{itemize}
\end{frame}

\begin{frame}{futex\_waitv Specific Worker Notification}
  \begin{figure}
    \includestandalone[keepaspectratio, height=0.92\textheight]{waitv-suspension-slides}
  \end{figure}
\end{frame}

\begin{frame}{File Search Algorithm}
  \begin{multicols}{2}
    \inputminted[frame=none, tabsize=2, fontsize=\small]{cpp}{code/fsearch.cpp}
  \end{multicols}
\end{frame}

\end{document}
