# source:doc/theses/thierry_delisle_PhD/thesis/text/core.tex@628a7c5

Last change on this file since 628a7c5 was 86c1f1c3, checked in by Thierry Delisle <tdelisle@…>, 2 years ago

First draft at my thesis

• Property mode set to 100644
File size: 1.8 KB
Line
1\chapter{Scheduling Core}\label{core}
2
3This chapter addresses the need of scheduling on a somewhat ideal scenario
4
5\section{Existing Schedulers}
6\subsection{Feedback Scheduling}
7
8\subsection{Priority Scheduling}\label{priority}
9
10\subsection{Work Stealing}
11
12\section{Design}
13While avoiding the pitfalls of Feedback Scheduling is fairly easy, scheduling does not innately require feedback, avoiding prioritization of \glspl{thrd} is more difficult because of implicitly priorities, see Subsection~\ref{priority}.
14
15\subsection{Sharding}
16
17\begin{figure}
18        \begin{center}
19                \input{base.pstex_t}
20        \end{center}
21        \caption{Relaxed FIFO list at the base of the scheduler: an array of strictly FIFO lists.
22        The timestamp is in all nodes and cell arrays.}
23        \label{fig:base}
24\end{figure}
25
27Once threads have been distributed onto multiple queues, indentifying which queues are empty and which aren't can become a problem.
28Indeed, if the number of \glspl{thrd} does not far exceed the number of queues, it is probable that several of these queues are empty.
29Figure~\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.
30This can lead to performance problems since picks that do not yield a \gls{thrd} are not useful and do not necessarily help make more informed guesses.
31
32Solutions to this problem can take many forms, but they ultimately all have to encode where the threads are in some form. My results show that the density and locality of this encoding is generally the dominating factor in these scheme.
33
34\paragraph{Dense Information}
35
36
37
38
39
40\begin{figure}
41        \begin{center}
42                \input{empty.pstex_t}
43        \end{center}
44        \caption{More empty'' state of the queue: the array contains many empty cells.}
45        \label{fig:empty}
46\end{figure}
Note: See TracBrowser for help on using the repository browser.