source: doc/theses/thierry_delisle_PhD/thesis/text/front.tex @ eb9f7f9

ADTast-experimental
Last change on this file since eb9f7f9 was eb9f7f9, checked in by Thierry Delisle <tdelisle@…>, 17 months ago

Added NSERC to acknowledgements

  • Property mode set to 100644
File size: 8.4 KB
Line 
1% T I T L E   P A G E
2% -------------------
3% Last updated June 14, 2017, by Stephen Carr, IST-Client Services
4% The title page is counted as page `i' but we need to suppress the
5% page number. Also, we don't want any headers or footers.
6\pagestyle{empty}
7\pagenumbering{roman}
8
9% The contents of the title page are specified in the "titlepage"
10% environment.
11\begin{titlepage}
12        \begin{center}
13                \vspace*{1.0cm}
14
15                \Huge
16                {\bf The \CFA Scheduler}
17
18                \vspace*{1.0cm}
19
20                \normalsize
21                by \\
22
23                \vspace*{1.0cm}
24
25                \Large
26                Thierry Delisle \\
27
28                \vspace*{3.0cm}
29
30                \normalsize
31                A thesis \\
32                presented to the University of Waterloo \\
33                in fulfillment of the \\
34                thesis requirement for the degree of \\
35                Doctor of Philosophy \\
36                in \\
37                Computer Science \\
38
39                \vspace*{2.0cm}
40
41                Waterloo, Ontario, Canada, 2022 \\
42
43                \vspace*{1.0cm}
44
45                \copyright\ Thierry Delisle 2022 \\
46        \end{center}
47\end{titlepage}
48
49% The rest of the front pages should contain no headers and be numbered using Roman numerals starting with `ii'
50\pagestyle{plain}
51\setcounter{page}{2}
52
53\cleardoublepage % Ends the current page and causes all figures and tables that have so far appeared in the input to be printed.
54% In a two-sided printing style, it also makes the next page a right-hand (odd-numbered) page, producing a blank page if necessary.
55
56
57% E X A M I N I N G   C O M M I T T E E (Required for Ph.D. theses only)
58% Remove or comment out the lines below to remove this page
59\begin{center}\textbf{Examining Committee Membership}\end{center}
60\noindent
61        The following served on the Examining Committee for this thesis. The decision of the Examining Committee is by majority vote.
62\bigskip
63
64\noindent
65\begin{tabbing}
66        Internal-External Member: \=  \kill % using longest text to define tab length
67        External Examiner: \>  Doug Lea \\
68        \> Professor, Computer Science Department \\
69        \> State University of New York at Oswego \\
70\end{tabbing}
71\bigskip
72
73\noindent
74\begin{tabbing}
75        Internal-External Member: \=  \kill % using longest text to define tab length
76        Supervisor(s): \> Peter Buhr \\
77        \> Associate Professor, School of Computer Science \\
78        \> University of Waterloo \\
79\end{tabbing}
80\bigskip
81
82\noindent
83\begin{tabbing}
84        Internal-External Member: \=  \kill % using longest text to define tab length
85        Internal Member: \> Trevor Brown \\
86        \> Assistant Professor, School of Computer Science \\
87        \> University of Waterloo \\
88        \\
89        Internal Member: \> Martin Karsten \\
90        \> Associate Professor, School of Computer Science \\
91        \> University of Waterloo \\
92\end{tabbing}
93\bigskip
94
95\noindent
96\begin{tabbing}
97        Internal-External Member: \=  \kill % using longest text to define tab length
98        Internal-External Member: \> Patrick Lam \\
99        \> Associate Professor, Department of Electrical and Computer Engineering \\
100        \> University of Waterloo \\
101\end{tabbing}
102\bigskip
103
104\cleardoublepage
105
106% D E C L A R A T I O N   P A G E
107% -------------------------------
108% The following is a sample Declaration Page as provided by the GSO
109% December 13th, 2006.  It is designed for an electronic thesis.
110\noindent
111I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners.
112
113\bigskip
114
115\noindent
116I understand that my thesis may be made electronically available to the public.
117
118\cleardoublepage
119
120% A B S T R A C T
121% ---------------
122
123\begin{center}\textbf{Abstract}\end{center}
124
125User-Level threading (M:N) is gaining popularity over kernel-level threading (1:1) in many programming languages.
126The user threading approach is often a better mechanism to express complex concurrent applications by efficiently running 10,000+ threads on multicore systems.
127Indeed, over-partitioning into small work-units with user threading significantly eases load bal\-ancing, while simultaneously providing advanced synchronization and mutual exclusion capabilities.
128To manage these high levels of concurrency, the underlying runtime must efficiently schedule many user threads across a few kernel threads;
129which begs the question of how many kernel threads are needed and should the number be dynamically reevaluated.
130Furthermore, scheduling must prevent kernel threads from blocking, otherwise user-thread parallelism drops.
131When user-threading parallelism does drop, how and when should idle \glspl{kthrd} be put to sleep to avoid wasting CPU resources.
132Finally, the scheduling system must provide fairness to prevent a user thread from monopolizing a kernel thread;
133otherwise, other user threads can experience short/long term starvation or kernel threads can deadlock waiting for events to occur on busy kernel threads.
134
135This thesis analyses multiple scheduler systems, where each system attempts to fulfill the requirements for user-level threading.
136The predominant technique for managing high levels of concurrency is sharding the ready queue with one queue per \gls{kthrd} and using some form of work stealing/sharing to dynamically rebalance workload shifts.
137Preventing kernel blocking is accomplished by transforming kernel locks and I/O operations into user-level operations that do not block the kernel thread or spin up new kernel threads to manage the blocking.
138Fairness is handled through preemption and/or ad-hoc solutions, which leads to coarse-grained fairness with some pathological cases.
139
140After examining, selecting and testing specific approaches to these scheduling issues, a complete implementation was created and tested in the \CFA (C-for-all) runtime system.
141\CFA is a modern extension of C using user-level threading as its fundamental threading model.
142As one of its primary goals, \CFA aims to offer increased safety and productivity without sacrificing performance.
143The new scheduler achieves this goal by demonstrating equivalent performance to work-stealing schedulers while offering better fairness.
144The implementation uses several optimizations that successfully balance the cost of fairness against performance;
145some of these optimizations rely on interesting hardware optimizations present on modern CPUs.
146The new scheduler also includes support for implicit nonblocking \io, allowing applications to have more user-threads blocking on \io operations than there are \glspl{kthrd}.
147The implementation is based on @io_uring@, a recent addition to the Linux kernel, and achieves the same performance and fairness as systems using @select@, @epoll@, \etc.
148To complete the scheduler, an idle sleep mechanism is implemented that significantly reduces wasted CPU cycles, which are then available outside the application.
149
150\cleardoublepage
151
152% A C K N O W L E D G E M E N T S
153% -------------------------------
154
155\begin{center}\textbf{Acknowledgements}\end{center}
156
157I would like to thank my supervisor, Professor Peter Buhr, for his guidance through my degree as well as the editing of this document.
158
159I would like to thank Professors Martin Karsten and Trevor Brown, for reading my thesis and providing helpful feedback.
160
161Thanks to Andrew Beach, Michael Brooks, Colby Parsons, Mubeen Zulfiqar, Fangren Yu and Jiada Liang for their work on the \CFA project as well as all the discussions which have helped me concretize the ideas in this thesis.
162
163Finally, I acknowledge that this has been possible thanks to the financial help offered by the David R. Cheriton School of Computer Science, the corporate partnership with Huawei Ltd. and the Natural Sciences and Engineering Research Council.
164\cleardoublepage
165
166% D E D I C A T I O N
167% -------------------
168
169% \begin{center}\textbf{Dedication}\end{center}
170
171% This is dedicated to the one I love.
172% \cleardoublepage
173
174% T A B L E   O F   C O N T E N T S
175% ---------------------------------
176\renewcommand\contentsname{Table of Contents}
177\tableofcontents
178\cleardoublepage
179\phantomsection    % allows hyperref to link to the correct page
180
181% L I S T   O F   F I G U R E S
182% -----------------------------
183\addcontentsline{toc}{chapter}{List of Figures}
184\listoffigures
185\cleardoublepage
186\phantomsection         % allows hyperref to link to the correct page
187
188% L I S T   O F   T A B L E S
189% ---------------------------
190\addcontentsline{toc}{chapter}{List of Tables}
191\listoftables
192\cleardoublepage
193\phantomsection         % allows hyperref to link to the correct page
194
195% GLOSSARIES (Lists of definitions, abbreviations, symbols, etc. provided by the glossaries-extra package)
196% -----------------------------
197\printglossary[type=\acronymtype]
198\cleardoublepage
199\phantomsection         % allows hyperref to link to the correct page
200
201% Change page numbering back to Arabic numerals
202\pagenumbering{arabic}
203
Note: See TracBrowser for help on using the repository browser.