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

Last change on this file since 562ccf9 was 5657de9, checked in by Thierry Delisle <tdelisle@…>, 2 years ago

Changes needed for UWSpace

  • 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        \> 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\begin{center}\textbf{Author's Declaration}\end{center}
111\noindent
112I 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.
113
114\bigskip
115
116\noindent
117I understand that my thesis may be made electronically available to the public.
118
119\cleardoublepage
120
121% A B S T R A C T
122% ---------------
123
124\begin{center}\textbf{Abstract}\end{center}
125
126User-Level threading (M:N) is gaining popularity over kernel-level threading (1:1) in many programming languages.
127The user threading approach is often a better mechanism to express complex concurrent applications by efficiently running 10,000+ threads on multicore systems.
128Indeed, over-partitioning into small work-units with user threading significantly eases load bal\-ancing, while simultaneously providing advanced synchronization and mutual exclusion capabilities.
129To manage these high levels of concurrency, the underlying runtime must efficiently schedule many user threads across a few kernel threads;
130which raises the question of how many kernel threads are needed and should the number be dynamically reevaluated.
131Furthermore, scheduling must prevent kernel threads from blocking, otherwise user-thread parallelism drops.
132When user-threading parallelism does drop, how and when should idle \glspl{kthrd} be put to sleep to avoid wasting CPU resources?
133Finally, the scheduling system must provide fairness to prevent a user thread from monopolizing a kernel thread;
134otherwise, other user threads can experience short/long term starvation or kernel threads can deadlock waiting for events to occur on busy kernel threads.
135
136This thesis analyses multiple scheduler systems, where each system attempts to fulfill the requirements for user-level threading.
137The 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.
138Preventing 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.
139Fairness is handled through preemption and/or ad-hoc solutions, which leads to coarse-grained fairness with some pathological cases.
140
141After 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.
142\CFA is a modern extension of C using user-level threading as its fundamental threading model.
143As one of its primary goals, \CFA aims to offer increased safety and productivity without sacrificing performance.
144The new scheduler achieves this goal by demonstrating equivalent performance to work-stealing schedulers while offering better fairness.
145The implementation uses several optimizations that successfully balance the cost of fairness against performance;
146some of these optimizations rely on interesting hardware optimizations present on modern CPUs.
147The 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}.
148The 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.
149To complete the scheduler, an idle sleep mechanism is implemented that significantly reduces wasted CPU cycles, which are then available outside the application.
150
151\cleardoublepage
152
153% A C K N O W L E D G E M E N T S
154% -------------------------------
155
156\begin{center}\textbf{Acknowledgements}\end{center}
157
158I would like to thank my supervisor, Professor Peter Buhr, for his guidance through my degree as well as the editing of this document.
159
160I would like to thank Professors Martin Karsten and Trevor Brown, for reading my thesis and providing helpful feedback.
161
162Thanks 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.
163
164Finally, 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.
165\cleardoublepage
166
167% D E D I C A T I O N
168% -------------------
169
170% \begin{center}\textbf{Dedication}\end{center}
171
172% This is dedicated to the one I love.
173% \cleardoublepage
174
175% T A B L E   O F   C O N T E N T S
176% ---------------------------------
177\renewcommand\contentsname{Table of Contents}
178\tableofcontents
179\cleardoublepage
180\phantomsection    % allows hyperref to link to the correct page
181
182% L I S T   O F   F I G U R E S
183% -----------------------------
184\addcontentsline{toc}{chapter}{List of Figures}
185\listoffigures
186\cleardoublepage
187\phantomsection         % allows hyperref to link to the correct page
188
189% L I S T   O F   T A B L E S
190% ---------------------------
191\addcontentsline{toc}{chapter}{List of Tables}
192\listoftables
193\cleardoublepage
194\phantomsection         % allows hyperref to link to the correct page
195
196% GLOSSARIES (Lists of definitions, abbreviations, symbols, etc. provided by the glossaries-extra package)
197% -----------------------------
198\printglossary[type=\acronymtype,title={List of Abbreviations}]
199\cleardoublepage
200\phantomsection         % allows hyperref to link to the correct page
201
202% Change page numbering back to Arabic numerals
203\pagenumbering{arabic}
204
Note: See TracBrowser for help on using the repository browser.