Ignore:
Timestamp:
Feb 1, 2022, 7:42:31 PM (3 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, ast-experimental, enum, forall-pointer-decay, master, pthread-emulation, qualifiedEnum
Children:
3b0bc16
Parents:
ab1a9ea
Message:

Re-starting work on my thesis.

Location:
doc/theses/thierry_delisle_PhD/thesis
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/thierry_delisle_PhD/thesis/fig/base.fig

    rab1a9ea r729c991  
    12121 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6900 4200 20 20 6900 4200 6920 4200
    13131 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6975 4200 20 20 6975 4200 6995 4200
     14-6
     156 6375 5100 6675 5250
     161 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6450 5175 20 20 6450 5175 6470 5175
     171 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6525 5175 20 20 6525 5175 6545 5175
     181 3 0 1 0 0 50 -1 20 0.000 1 0.0000 6600 5175 20 20 6600 5175 6620 5175
    1419-6
    15201 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3900 2400 300 300 3900 2400 4200 2400
    … …  
    75802 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
    7681         2400 2475 3000 2475
     822 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
     83         3300 5210 3150 4950 2850 4950 2700 5210 2850 5470 3150 5470
     84         3300 5210
     852 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
     86         4500 5210 4350 4950 4050 4950 3900 5210 4050 5470 4350 5470
     87         4500 5210
     882 3 0 1 0 7 50 -1 -1 0.000 0 0 0 0 0 7
     89         5700 5210 5550 4950 5250 4950 5100 5210 5250 5470 5550 5470
     90         5700 5210
    77914 2 -1 50 -1 0 12 0.0000 2 135 630 2100 3075 Threads\001
    78924 2 -1 50 -1 0 12 0.0000 2 165 450 2100 2850 Ready\001
    … …  
    82964 1 -1 50 -1 0 11 0.0000 2 135 180 2700 3550 TS\001
    83974 1 -1 50 -1 0 11 0.0000 2 135 180 2700 2650 TS\001
     984 2 -1 50 -1 0 12 0.0000 2 135 900 2100 5175 Processors\001

  • doc/theses/thierry_delisle_PhD/thesis/glossary.tex

    rab1a9ea r729c991  
    4040
    4141\textit{Synonyms : User threads, Lightweight threads, Green threads, Virtual threads, Tasks.}
     42}
     43
     44\longnewglossaryentry{rmr}
     45{name={remote memory reference}}
     46{
     47
    4248}
    4349

  • doc/theses/thierry_delisle_PhD/thesis/text/core.tex

    rab1a9ea r729c991  
    4949
    5050\section{Design}
    51 In general, a na\"{i}ve \glsxtrshort{fifo} ready-queue does not scale with increased parallelism from \glspl{hthrd}, resulting in decreased performance. The problem is adding/removing \glspl{thrd} is a single point of contention. As shown in the evaluation sections, most production schedulers do scale when adding \glspl{hthrd}. The common solution to the single point of contention is to shard the ready-queue so each \gls{hthrd} can access the ready-queue without contention, increasing performance.
     51In general, a na\"{i}ve \glsxtrshort{fifo} ready-queue does not scale with increased parallelism from \glspl{hthrd}, resulting in decreased performance. The problem is adding/removing \glspl{thrd} is a single point of contention. As shown in the evaluation sections, most production schedulers do scale when adding \glspl{hthrd}. The solution to this problem is to shard the ready-queue : create multiple sub-ready-queues that multiple \glspl{hthrd} can access and modify without interfering.
    5252
    53 \subsection{Sharding} \label{sec:sharding}
    54 An interesting approach to sharding a queue is presented in \cit{Trevors paper}. This algorithm presents a queue with a relaxed \glsxtrshort{fifo} guarantee using an array of strictly \glsxtrshort{fifo} sublists as shown in Figure~\ref{fig:base}. Each \emph{cell} of the array has a timestamp for the last operation and a pointer to a linked-list with a lock. Each node in the list is marked with a timestamp indicating when it is added to the list. A push operation is done by picking a random cell, acquiring the list lock, and pushing to the list. If the cell is locked, the operation is simply retried on another random cell until a lock is acquired. A pop operation is done in a similar fashion except two random cells are picked. If both cells are unlocked with non-empty lists, the operation pops the node with the oldest timestamp. If one of the cells is unlocked and non-empty, the operation pops from that cell. If both cells are either locked or empty, the operation picks two new random cells and tries again.
     53Before going into the design of \CFA's scheduler proper, I want to discuss two sharding solutions which served as the inspiration scheduler in this thesis.
    5554
     55\subsection{Work-Stealing}
     56
     57As I mentioned in \ref{existing:workstealing}, a popular pattern shard the ready-queue is work-stealing. As mentionned, in this pattern each \gls{proc} has its own ready-queue and \glspl{proc} only access each other's ready-queue if they run out of work.
     58The interesting aspect of workstealing happen in easier scheduling cases, \ie enough work for everyone but no more and no load balancing needed. In these cases, work-stealing is close to optimal scheduling: it can achieve perfect locality and have no contention.
     59On the other hand, work-stealing schedulers only attempt to do load-balancing when a \gls{proc} runs out of work.
     60This means that the scheduler may never balance unfairness that does not result in a \gls{proc} running out of work.
     61Chapter~\ref{microbench} shows that in pathological cases this problem can lead to indefinite starvation.
     62
     63
     64Based on these observation, I conclude that \emph{perfect} scheduler should behave very similarly to work-stealing in the easy cases, but should have more proactive load-balancing if the need arises.
     65
     66\subsection{Relaxed-Fifo}
     67An entirely different scheme is to create a ``relaxed-FIFO'' queue as in \todo{cite Trevor's paper}. This approach forgos any ownership between \gls{proc} and ready-queue, and simply creates a pool of ready-queues from which the \glspl{proc} can pick from.
     68\Glspl{proc} choose ready-queus at random, but timestamps are added to all elements of the queue and dequeues are done by picking two queues and dequeing the oldest element.
     69The result is a queue that has both decent scalability and sufficient fairness.
     70The lack of ownership means that as long as one \gls{proc} is still able to repeatedly dequeue elements, it is unlikely that any element will stay on the queue for much longer than any other element.
     71This contrasts with work-stealing, where \emph{any} \gls{proc} busy for an extended period of time results in all the elements on its local queue to have to wait. Unless another \gls{proc} runs out of work.
     72
     73An important aspects of this scheme's fairness approach is that the timestamps make it possible to evaluate how long elements have been on the queue.
     74However, another major aspect is that \glspl{proc} will eagerly search for these older elements instead of focusing on specific queues.
     75
     76While the fairness, of this scheme is good, it does suffer in terms of performance.
     77It requires very wide sharding, \eg at least 4 queues per \gls{hthrd}, and the randomness means locality can suffer significantly and finding non-empty queues can be difficult.
     78
     79\section{\CFA}
     80The \CFA is effectively attempting to merge these two approaches, keeping the best of both.
     81It is based on the
    5682\begin{figure}
    5783        \centering
    5884        \input{base.pstex_t}
    59         \caption[Relaxed FIFO list]{Relaxed FIFO list \smallskip\newline List at the base of the scheduler: an array of strictly FIFO lists. The timestamp is in all nodes and cell arrays.}
     85        \caption[Base \CFA design]{Base \CFA design \smallskip\newline A list of sub-ready queues offers the sharding, two per \glspl{proc}. However, \glspl{proc} can access any of the sub-queues.}
    6086        \label{fig:base}
    6187\end{figure}
    6288
    63 \subsection{Finding threads}
    64 Once threads have been distributed onto multiple queues, identifying empty queues becomes a problem. Indeed, if the number of \glspl{thrd} does not far exceed the number of queues, it is probable that several of the cell queues are empty. Figure~\ref{fig:empty} shows an example with 2 \glspl{thrd} running on 8 queues, where the chances of getting an empty queue is 75\% per pick, meaning two random picks yield a \gls{thrd} only half the time. This scenario leads to performance problems since picks that do not yield a \gls{thrd} are not useful and do not necessarily help make more informed guesses.
    6589
    66 \begin{figure}
    67         \centering
    68         \input{empty.pstex_t}
    69         \caption[``More empty'' Relaxed FIFO list]{``More empty'' Relaxed FIFO list \smallskip\newline Emptier state of the queue: the array contains many empty cells, that is strictly FIFO lists containing no elements.}
    70         \label{fig:empty}
    71 \end{figure}
    7290
    73 There are several solutions to this problem, but they ultimately all have to encode if a cell has an empty list. My results show the density and locality of this encoding is generally the dominating factor in these scheme. Classic solutions to this problem use one of three techniques to encode the information:
     91% The common solution to the single point of contention is to shard the ready-queue so each \gls{hthrd} can access the ready-queue without contention, increasing performance.
    7492
    75 \paragraph{Dense Information} Figure~\ref{fig:emptybit} shows a dense bitmask to identify the cell queues currently in use. This approach means processors can often find \glspl{thrd} in constant time, regardless of how many underlying queues are empty. Furthermore, modern x86 CPUs have extended bit manipulation instructions (BMI2) that allow searching the bitmask with very little overhead compared to the randomized selection approach for a filled ready queue, offering good performance even in cases with many empty inner queues. However, this technique has its limits: with a single word\footnote{Word refers here to however many bits can be written atomically.} bitmask, the total amount of ready-queue sharding is limited to the number of bits in the word. With a multi-word bitmask, this maximum limit can be increased arbitrarily, but the look-up time increases. Finally, a dense bitmap, either single or multi-word, causes additional contention problems that reduces performance because of cache misses after updates. This central update bottleneck also means the information in the bitmask is more often stale before a processor can use it to find an item, \ie mask read says there are available \glspl{thrd} but none on queue when the subsequent atomic check is done.
     93% \subsection{Sharding} \label{sec:sharding}
     94% An interesting approach to sharding a queue is presented in \cit{Trevors paper}. This algorithm presents a queue with a relaxed \glsxtrshort{fifo} guarantee using an array of strictly \glsxtrshort{fifo} sublists as shown in Figure~\ref{fig:base}. Each \emph{cell} of the array has a timestamp for the last operation and a pointer to a linked-list with a lock. Each node in the list is marked with a timestamp indicating when it is added to the list. A push operation is done by picking a random cell, acquiring the list lock, and pushing to the list. If the cell is locked, the operation is simply retried on another random cell until a lock is acquired. A pop operation is done in a similar fashion except two random cells are picked. If both cells are unlocked with non-empty lists, the operation pops the node with the oldest timestamp. If one of the cells is unlocked and non-empty, the operation pops from that cell. If both cells are either locked or empty, the operation picks two new random cells and tries again.
    7695
    77 \begin{figure}
    78         \centering
    79         \vspace*{-5pt}
    80         {\resizebox{0.75\textwidth}{!}{\input{emptybit.pstex_t}}}
    81         \vspace*{-5pt}
    82         \caption[Underloaded queue with bitmask]{Underloaded queue with bitmask indicating array cells with items.}
    83         \label{fig:emptybit}
     96% \begin{figure}
     97%       \centering
     98%       \input{base.pstex_t}
     99%       \caption[Relaxed FIFO list]{Relaxed FIFO list \smallskip\newline List at the base of the scheduler: an array of strictly FIFO lists. The timestamp is in all nodes and cell arrays.}
     100%       \label{fig:base}
     101% \end{figure}
    84102
    85         \vspace*{10pt}
    86         {\resizebox{0.75\textwidth}{!}{\input{emptytree.pstex_t}}}
    87         \vspace*{-5pt}
    88         \caption[Underloaded queue with binary search-tree]{Underloaded queue with binary search-tree indicating array cells with items.}
    89         \label{fig:emptytree}
     103% \subsection{Finding threads}
     104% Once threads have been distributed onto multiple queues, identifying empty queues becomes a problem. Indeed, if the number of \glspl{thrd} does not far exceed the number of queues, it is probable that several of the cell queues are empty. Figure~\ref{fig:empty} shows an example with 2 \glspl{thrd} running on 8 queues, where the chances of getting an empty queue is 75\% per pick, meaning two random picks yield a \gls{thrd} only half the time. This scenario leads to performance problems since picks that do not yield a \gls{thrd} are not useful and do not necessarily help make more informed guesses.
    90105
    91         \vspace*{10pt}
    92         {\resizebox{0.95\textwidth}{!}{\input{emptytls.pstex_t}}}
    93         \vspace*{-5pt}
    94         \caption[Underloaded queue with per processor bitmask]{Underloaded queue with per processor bitmask indicating array cells with items.}
    95         \label{fig:emptytls}
    96 \end{figure}
     106% \begin{figure}
     107%       \centering
     108%       \input{empty.pstex_t}
     109%       \caption[``More empty'' Relaxed FIFO list]{``More empty'' Relaxed FIFO list \smallskip\newline Emptier state of the queue: the array contains many empty cells, that is strictly FIFO lists containing no elements.}
     110%       \label{fig:empty}
     111% \end{figure}
    97112
    98 \paragraph{Sparse Information} Figure~\ref{fig:emptytree} shows an approach using a hierarchical tree data-structure to reduce contention and has been shown to work in similar cases~\cite{ellen2007snzi}. However, this approach may lead to poorer performance due to the inherent pointer chasing cost while still allowing significant contention on the nodes of the tree if the tree is shallow.
     113% There are several solutions to this problem, but they ultimately all have to encode if a cell has an empty list. My results show the density and locality of this encoding is generally the dominating factor in these scheme. Classic solutions to this problem use one of three techniques to encode the information:
    99114
    100 \paragraph{Local Information} Figure~\ref{fig:emptytls} shows an approach using dense information, similar to the bitmap, but each \gls{hthrd} keeps its own independent copy. While this approach can offer good scalability \emph{and} low latency, the liveliness and discovery of the information can become a problem. This case is made worst in systems with few processors where even blind random picks can find \glspl{thrd} in a few tries.
     115% \paragraph{Dense Information} Figure~\ref{fig:emptybit} shows a dense bitmask to identify the cell queues currently in use. This approach means processors can often find \glspl{thrd} in constant time, regardless of how many underlying queues are empty. Furthermore, modern x86 CPUs have extended bit manipulation instructions (BMI2) that allow searching the bitmask with very little overhead compared to the randomized selection approach for a filled ready queue, offering good performance even in cases with many empty inner queues. However, this technique has its limits: with a single word\footnote{Word refers here to however many bits can be written atomically.} bitmask, the total amount of ready-queue sharding is limited to the number of bits in the word. With a multi-word bitmask, this maximum limit can be increased arbitrarily, but the look-up time increases. Finally, a dense bitmap, either single or multi-word, causes additional contention problems that reduces performance because of cache misses after updates. This central update bottleneck also means the information in the bitmask is more often stale before a processor can use it to find an item, \ie mask read says there are available \glspl{thrd} but none on queue when the subsequent atomic check is done.
    101116
    102 I built a prototype of these approaches and none of these techniques offer satisfying performance when few threads are present. All of these approach hit the same 2 problems. First, randomly picking sub-queues is very fast. That speed means any improvement to the hit rate can easily be countered by a slow-down in look-up speed, whether or not there are empty lists. Second, the array is already sharded to avoid contention bottlenecks, so any denser data structure tends to become a bottleneck. In all cases, these factors meant the best cases scenario, \ie many threads, would get worst throughput, and the worst-case scenario, few threads, would get a better hit rate, but an equivalent poor throughput. As a result I tried an entirely different approach.
     117% \begin{figure}
     118%       \centering
     119%       \vspace*{-5pt}
     120%       {\resizebox{0.75\textwidth}{!}{\input{emptybit.pstex_t}}}
     121%       \vspace*{-5pt}
     122%       \caption[Underloaded queue with bitmask]{Underloaded queue with bitmask indicating array cells with items.}
     123%       \label{fig:emptybit}
    103124
    104 \subsection{Dynamic Entropy}\cit{https://xkcd.com/2318/}
    105 In the worst-case scenario there are only few \glspl{thrd} ready to run, or more precisely given $P$ \glspl{proc}\footnote{For simplicity, this assumes there is a one-to-one match between \glspl{proc} and \glspl{hthrd}.}, $T$ \glspl{thrd} and $\epsilon$ a very small number, than the worst case scenario can be represented by $T = P + \epsilon$, with $\epsilon \ll P$. It is important to note in this case that fairness is effectively irrelevant. Indeed, this case is close to \emph{actually matching} the model of the ``Ideal multi-tasking CPU'' on page \pageref{q:LinuxCFS}. In this context, it is possible to use a purely internal-locality based approach and still meet the fairness requirements. This approach simply has each \gls{proc} running a single \gls{thrd} repeatedly. Or from the shared ready-queue viewpoint, each \gls{proc} pushes to a given sub-queue and then pops from the \emph{same} subqueue. The challenge is for the the scheduler to achieve good performance in both the $T = P + \epsilon$ case and the $T \gg P$ case, without affecting the fairness guarantees in the later.
     125%       \vspace*{10pt}
     126%       {\resizebox{0.75\textwidth}{!}{\input{emptytree.pstex_t}}}
     127%       \vspace*{-5pt}
     128%       \caption[Underloaded queue with binary search-tree]{Underloaded queue with binary search-tree indicating array cells with items.}
     129%       \label{fig:emptytree}
    106130
    107 To handle this case, I use a \glsxtrshort{prng}\todo{Fix missing long form} in a novel way. There exist \glsxtrshort{prng}s that are fast, compact and can be run forward \emph{and} backwards.  Linear congruential generators~\cite{wiki:lcg} are an example of \glsxtrshort{prng}s of such \glsxtrshort{prng}s. The novel approach is to use the ability to run backwards to ``replay'' the \glsxtrshort{prng}. The scheduler uses an exclusive \glsxtrshort{prng} instance per \gls{proc}, the random-number seed effectively starts an encoding that produces a list of all accessed subqueues, from latest to oldest. Replaying the \glsxtrshort{prng} to identify cells accessed recently and which probably have data still cached.
     131%       \vspace*{10pt}
     132%       {\resizebox{0.95\textwidth}{!}{\input{emptytls.pstex_t}}}
     133%       \vspace*{-5pt}
     134%       \caption[Underloaded queue with per processor bitmask]{Underloaded queue with per processor bitmask indicating array cells with items.}
     135%       \label{fig:emptytls}
     136% \end{figure}
    108137
    109 The algorithm works as follows:
    110 \begin{itemize}
    111         \item Each \gls{proc} has two \glsxtrshort{prng} instances, $F$ and $B$.
    112         \item Push and Pop operations occur as discussed in Section~\ref{sec:sharding} with the following exceptions:
    113         \begin{itemize}
    114                 \item Push operations use $F$ going forward on each try and on success $F$ is copied into $B$.
    115                 \item Pop operations use $B$ going backwards on each try.
    116         \end{itemize}
    117 \end{itemize}
     138% \paragraph{Sparse Information} Figure~\ref{fig:emptytree} shows an approach using a hierarchical tree data-structure to reduce contention and has been shown to work in similar cases~\cite{ellen2007snzi}. However, this approach may lead to poorer performance due to the inherent pointer chasing cost while still allowing significant contention on the nodes of the tree if the tree is shallow.
    118139
    119 The main benefit of this technique is that it basically respects the desired properties of Figure~\ref{fig:fair}. When looking for work, a \gls{proc} first looks at the last cell they pushed to, if any, and then move backwards through its accessed cells. As the \gls{proc} continues looking for work, $F$ moves backwards and $B$ stays in place. As a result, the relation between the two becomes weaker, which means that the probablisitic fairness of the algorithm reverts to normal. Chapter~\ref{proofs} discusses more formally the fairness guarantees of this algorithm.
     140% \paragraph{Local Information} Figure~\ref{fig:emptytls} shows an approach using dense information, similar to the bitmap, but each \gls{hthrd} keeps its own independent copy. While this approach can offer good scalability \emph{and} low latency, the liveliness and discovery of the information can become a problem. This case is made worst in systems with few processors where even blind random picks can find \glspl{thrd} in a few tries.
    120141
    121 \section{Details}
     142% I built a prototype of these approaches and none of these techniques offer satisfying performance when few threads are present. All of these approach hit the same 2 problems. First, randomly picking sub-queues is very fast. That speed means any improvement to the hit rate can easily be countered by a slow-down in look-up speed, whether or not there are empty lists. Second, the array is already sharded to avoid contention bottlenecks, so any denser data structure tends to become a bottleneck. In all cases, these factors meant the best cases scenario, \ie many threads, would get worst throughput, and the worst-case scenario, few threads, would get a better hit rate, but an equivalent poor throughput. As a result I tried an entirely different approach.
     143
     144% \subsection{Dynamic Entropy}\cit{https://xkcd.com/2318/}
     145% In the worst-case scenario there are only few \glspl{thrd} ready to run, or more precisely given $P$ \glspl{proc}\footnote{For simplicity, this assumes there is a one-to-one match between \glspl{proc} and \glspl{hthrd}.}, $T$ \glspl{thrd} and $\epsilon$ a very small number, than the worst case scenario can be represented by $T = P + \epsilon$, with $\epsilon \ll P$. It is important to note in this case that fairness is effectively irrelevant. Indeed, this case is close to \emph{actually matching} the model of the ``Ideal multi-tasking CPU'' on page \pageref{q:LinuxCFS}. In this context, it is possible to use a purely internal-locality based approach and still meet the fairness requirements. This approach simply has each \gls{proc} running a single \gls{thrd} repeatedly. Or from the shared ready-queue viewpoint, each \gls{proc} pushes to a given sub-queue and then pops from the \emph{same} subqueue. The challenge is for the the scheduler to achieve good performance in both the $T = P + \epsilon$ case and the $T \gg P$ case, without affecting the fairness guarantees in the later.
     146
     147% To handle this case, I use a \glsxtrshort{prng}\todo{Fix missing long form} in a novel way. There exist \glsxtrshort{prng}s that are fast, compact and can be run forward \emph{and} backwards.  Linear congruential generators~\cite{wiki:lcg} are an example of \glsxtrshort{prng}s of such \glsxtrshort{prng}s. The novel approach is to use the ability to run backwards to ``replay'' the \glsxtrshort{prng}. The scheduler uses an exclusive \glsxtrshort{prng} instance per \gls{proc}, the random-number seed effectively starts an encoding that produces a list of all accessed subqueues, from latest to oldest. Replaying the \glsxtrshort{prng} to identify cells accessed recently and which probably have data still cached.
     148
     149% The algorithm works as follows:
     150% \begin{itemize}
     151%       \item Each \gls{proc} has two \glsxtrshort{prng} instances, $F$ and $B$.
     152%       \item Push and Pop operations occur as discussed in Section~\ref{sec:sharding} with the following exceptions:
     153%       \begin{itemize}
     154%               \item Push operations use $F$ going forward on each try and on success $F$ is copied into $B$.
     155%               \item Pop operations use $B$ going backwards on each try.
     156%       \end{itemize}
     157% \end{itemize}
     158
     159% The main benefit of this technique is that it basically respects the desired properties of Figure~\ref{fig:fair}. When looking for work, a \gls{proc} first looks at the last cell they pushed to, if any, and then move backwards through its accessed cells. As the \gls{proc} continues looking for work, $F$ moves backwards and $B$ stays in place. As a result, the relation between the two becomes weaker, which means that the probablisitic fairness of the algorithm reverts to normal. Chapter~\ref{proofs} discusses more formally the fairness guarantees of this algorithm.
     160
     161% \section{Details}

  • doc/theses/thierry_delisle_PhD/thesis/text/eval_macro.tex

    rab1a9ea r729c991  
    44
    55In Memory Plain Text
    6 
    7 Networked Plain Text
    86
    97Networked ZIPF

  • doc/theses/thierry_delisle_PhD/thesis/text/eval_micro.tex

    rab1a9ea r729c991  
    22
    33The first step of evaluation is always to test-out small controlled cases, to ensure that the basics are working properly.
    4 This sections presents four different experimental setup, evaluating some of the basic features of \CFA's scheduler.
     4This sections presents five different experimental setup, evaluating some of the basic features of \CFA's scheduler.
    55
    66\section{Cycling latency}
    77The most basic evaluation of any ready queue is to evaluate the latency needed to push and pop one element from the ready-queue.
    8 While these two operation also describe a \texttt{yield} operation, many systems use this as the most basic benchmark.
    9 However, yielding can be treated as a special case, since it also carries the information that the length of the ready queue will not change.
     8Since these two operation also describe a \texttt{yield} operation, many systems use this as the most basic benchmark.
     9However, yielding can be treated as a special case, since it also carries the information that the number of the ready \glspl{at} will not change.
    1010Not all systems use this information, but those which do may appear to have better performance than they would for disconnected push/pop pairs.
    1111For this reason, I chose a different first benchmark, which I call the Cycle Benchmark.
    12 This benchmark arranges many threads into multiple rings of threads.
     12This benchmark arranges many \glspl{at} into multiple rings of \glspl{at}.
    1313Each ring is effectively a circular singly-linked list.
    14 At runtime, each thread unparks the next thread before parking itself.
     14At runtime, each \gls{at} unparks the next \gls{at} before parking itself.
    1515This corresponds to the desired pair of ready queue operations.
    16 Unparking the next thread requires pushing that thread onto the ready queue and the ensuing park will cause the runtime to pop a thread from the ready-queue.
     16Unparking the next \gls{at} requires pushing that \gls{at} onto the ready queue and the ensuing park will cause the runtime to pop a \gls{at} from the ready-queue.
    1717Figure~\ref{fig:cycle} shows a visual representation of this arrangement.
    1818
    19 The goal of this ring is that the underlying runtime cannot rely on the guarantee that the number of ready threads will stay constant over the duration of the experiment.
    20 In fact, the total number of threads waiting on the ready is expected to vary a little because of the race between the next thread unparking and the current thread parking.
    21 The size of the cycle is also decided based on this race: cycles that are too small may see the
    22 chain of unparks go full circle before the first thread can park.
     19The goal of this ring is that the underlying runtime cannot rely on the guarantee that the number of ready \glspl{at} will stay constant over the duration of the experiment.
     20In fact, the total number of \glspl{at} waiting on the ready queue is expected to vary because of the race between the next \gls{at} unparking and the current \gls{at} parking.
     21The size of the cycle is also decided based on this race: cycles that are too small may see the chain of unparks go full circle before the first \gls{at} can park.
    2322While this would not be a correctness problem, every runtime system must handle that race, it could lead to pushes and pops being optimized away.
    24 Since silently omitting ready-queue operations would throw off the measuring of these operations.
    25 Therefore the ring of threads must be big enough so the threads have the time to fully park before they are unparked.
     23Since silently omitting ready-queue operations would throw off the measuring of these operations, the ring of \glspl{at} must be big enough so the \glspl{at} have the time to fully park before they are unparked.
    2624Note that this problem is only present on SMP machines and is significantly mitigated by the fact that there are multiple rings in the system.
    2725
    … …  
    2927        \centering
    3028        \input{cycle.pstex_t}
    31         \caption[Cycle benchmark]{Cycle benchmark\smallskip\newline Each thread unparks the next thread in the cycle before parking itself.}
     29        \caption[Cycle benchmark]{Cycle benchmark\smallskip\newline Each \gls{at} unparks the next \gls{at} in the cycle before parking itself.}
    3230        \label{fig:cycle}
    3331\end{figure}
    3432
    3533\todo{check term ``idle sleep handling''}
    36 To avoid this benchmark from being dominated by the idle sleep handling, the number of rings is kept at least as high as the number of processors available.
     34To avoid this benchmark from being dominated by the idle sleep handling, the number of rings is kept at least as high as the number of \glspl{proc} available.
    3735Beyond this point, adding more rings serves to mitigate even more the idle sleep handling.
    38 This is to avoid the case where one of the worker threads runs out of work because of the variation on the number of ready threads mentionned above.
     36This is to avoid the case where one of the worker \glspl{at} runs out of work because of the variation on the number of ready \glspl{at} mentionned above.
    3937
    4038The actual benchmark is more complicated to handle termination, but that simply requires using a binary semphore or a channel instead of raw \texttt{park}/\texttt{unpark} and carefully picking the order of the \texttt{P} and \texttt{V} with respect to the loop condition.
    4139
    42 \todo{mention where to get the code.}
     40\todo{code, setup, results}
     41\begin{lstlisting}
     42        Thread.main() {
     43                count := 0
     44                for {
     45                        wait()
     46                        this.next.wake()
     47                        count ++
     48                        if must_stop() { break }
     49                }
     50                global.count += count
     51        }
     52\end{lstlisting}
     53
    4354
    4455\section{Yield}
    4556For completion, I also include the yield benchmark.
    46 This benchmark is much simpler than the cycle tests, it simply creates many threads that call \texttt{yield}.
     57This benchmark is much simpler than the cycle tests, it simply creates many \glspl{at} that call \texttt{yield}.
     58As mentionned in the previous section, this benchmark may be less representative of usages that only make limited use of \texttt{yield}, due to potential shortcuts in the routine.
     59Its only interesting variable is the number of \glspl{at} per \glspl{proc}, where ratios close to 1 means the ready queue(s) could be empty.
     60This sometimes puts more strain on the idle sleep handling, compared to scenarios where there is clearly plenty of work to be done.
     61
     62\todo{code, setup, results}
     63
     64\begin{lstlisting}
     65        Thread.main() {
     66                count := 0
     67                while !stop {
     68                        yield()
     69                        count ++
     70                }
     71                global.count += count
     72        }
     73\end{lstlisting}
     74
     75
     76\section{Churn}
     77The Cycle and Yield benchmark represents an ``easy'' scenario for a scheduler, \eg, an embarrassingly parallel application.
     78In these benchmarks, \glspl{at} can be easily partitioned over the different \glspl{proc} up-front and none of the \glspl{at} communicate with each other.
     79
     80The Churn benchmark represents more chaotic usages, where there is no relation between the last \gls{proc} on which a \gls{at} ran and the \gls{proc} that unblocked it.
     81When a \gls{at} is unblocked from a different \gls{proc} than the one on which it last ran, the unblocking \gls{proc} must either ``steal'' the \gls{at} or place it on a remote queue.
     82This results can result in either contention on the remote queue or \glspl{rmr} on \gls{at} data structure.
     83In either case, this benchmark aims to highlight how each scheduler handles these cases, since both cases can lead to performance degradation if they are not handled correctly.
     84
     85To achieve this the benchmark uses a fixed size array of \newterm{chair}s, where a chair is a data structure that holds a single blocked \gls{at}.
     86When a \gls{at} attempts to block on the chair, it must first unblocked the \gls{at} currently blocked on said chair, if any.
     87This creates a flow where \glspl{at} push each other out of the chairs before being pushed out themselves.
     88For this benchmark to work however, the number of \glspl{at} must be equal or greater to the number of chairs plus the number of \glspl{proc}.
     89
     90\todo{code, setup, results}
     91\begin{lstlisting}
     92        Thread.main() {
     93                count := 0
     94                for {
     95                        r := random() % len(spots)
     96                        next := xchg(spots[r], this)
     97                        if next { next.wake() }
     98                        wait()
     99                        count ++
     100                        if must_stop() { break }
     101                }
     102                global.count += count
     103        }
     104\end{lstlisting}
    47105
    48106\section{Locality}
    49107
     108\todo{code, setup, results}
     109
    50110\section{Transfer}
     111The last benchmark is more exactly characterize as an experiment than a benchmark.
     112It tests the behavior of the schedulers for a particularly misbehaved workload.
     113In this workload, one of the \gls{at} is selected at random to be the leader.
     114The leader then spins in a tight loop until it has observed that all other \glspl{at} have acknowledged its leadership.
     115The leader \gls{at} then picks a new \gls{at} to be the ``spinner'' and the cycle repeats.
     116
     117The benchmark comes in two flavours for the behavior of the non-leader \glspl{at}:
     118once they acknowledged the leader, they either block on a semaphore or yield repeatadly.
     119
     120This experiment is designed to evaluate the short term load balancing of the scheduler.
     121Indeed, schedulers where the runnable \glspl{at} are partitioned on the \glspl{proc} may need to balance the \glspl{at} for this experient to terminate.
     122This is because the spinning \gls{at} is effectively preventing the \gls{proc} from runnning any other \glspl{thrd}.
     123In the semaphore flavour, the number of runnable \glspl{at} will eventually dwindle down to only the leader.
     124This is a simpler case to handle for schedulers since \glspl{proc} eventually run out of work.
     125In the yielding flavour, the number of runnable \glspl{at} stays constant.
     126This is a harder case to handle because corrective measures must be taken even if work is still available.
     127Note that languages that have mandatory preemption do circumvent this problem by forcing the spinner to yield.
     128
     129\todo{code, setup, results}
     130\begin{lstlisting}
     131        Thread.lead() {
     132                this.idx_seen = ++lead_idx
     133                if lead_idx > stop_idx {
     134                        done := true
     135                        return
     136                }
     137
     138                // Wait for everyone to acknowledge my leadership
     139                start: = timeNow()
     140                for t in threads {
     141                        while t.idx_seen != lead_idx {
     142                                asm pause
     143                                if (timeNow() - start) > 5 seconds { error() }
     144                        }
     145                }
     146
     147                // pick next leader
     148                leader := threads[ prng() % len(threads) ]
     149
     150                // wake every one
     151                if !exhaust {
     152                        for t in threads {
     153                                if t != me { t.wake() }
     154                        }
     155                }
     156        }
     157
     158        Thread.wait() {
     159                this.idx_seen := lead_idx
     160                if exhaust { wait() }
     161                else { yield() }
     162        }
     163
     164        Thread.main() {
     165                while !done  {
     166                        if leader == me { this.lead() }
     167                        else { this.wait() }
     168                }
     169        }
     170\end{lstlisting}

  • doc/theses/thierry_delisle_PhD/thesis/text/existing.tex

    rab1a9ea r729c991  
    3333
    3434
    35 \section{Work Stealing}
     35\section{Work Stealing}\label{existing:workstealing}
    3636One of the most popular scheduling algorithm in practice (see~\ref{existing:prod}) is work-stealing. This idea, introduce by \cite{DBLP:conf/fpca/BurtonS81}, effectively has each worker work on its local tasks first, but allows the possibility for other workers to steal local tasks if they run out of tasks. \cite{DBLP:conf/focs/Blumofe94} introduced the more familiar incarnation of this, where each workers has queue of tasks to accomplish and workers without tasks steal tasks from random workers. (The Burton and Sleep algorithm had trees of tasks and stole only among neighbours). Blumofe and Leiserson also prove worst case space and time requirements for well-structured computations.
    3737
Note: See TracChangeset for help on using the changeset viewer.