Index: doc/theses/thierry_delisle_PhD/thesis/Makefile =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/Makefile (revision cc287800d7bddd7ca9acd23c50bb33d0a4fa3439) +++ doc/theses/thierry_delisle_PhD/thesis/Makefile (revision a633f6fa702673747b3ee86a0f8e2e48456226f4) @@ -20,4 +20,6 @@ practice \ io \ + eval_micro \ + eval_macro \ }} @@ -35,4 +37,5 @@ pivot_ring \ system \ + cycle \ } Index: doc/theses/thierry_delisle_PhD/thesis/fig/cycle.fig =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/fig/cycle.fig (revision a633f6fa702673747b3ee86a0f8e2e48456226f4) +++ doc/theses/thierry_delisle_PhD/thesis/fig/cycle.fig (revision a633f6fa702673747b3ee86a0f8e2e48456226f4) @@ -0,0 +1,34 @@ +#FIG 3.2 Produced by xfig version 3.2.7b +Landscape +Center +Inches +Letter +100.00 +Single +-2 +1200 2 +5 1 0 1 0 7 50 -1 -1 0.000 0 1 1 0 3144.643 2341.072 3525 2250 3375 2025 3150 1950 + 2 0 1.00 60.00 120.00 +5 1 0 1 0 7 50 -1 -1 0.000 0 1 1 0 1955.357 2341.072 1950 1950 1725 2025 1575 2250 + 2 0 1.00 60.00 120.00 +5 1 0 1 0 7 50 -1 -1 0.000 0 1 1 0 3637.500 3487.500 3750 3750 3900 3600 3900 3375 + 2 0 1.00 60.00 120.00 +5 1 0 1 0 7 50 -1 -1 0.000 0 1 1 0 2587.500 4087.500 2325 4500 2550 4575 2850 4500 + 2 0 1.00 60.00 120.00 +5 1 0 1 0 7 50 -1 -1 0.000 0 1 1 0 1612.500 3487.500 1200 3375 1200 3600 1350 3825 + 2 0 1.00 60.00 120.00 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3675 2850 586 586 3675 2850 4125 3225 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 3300 4125 586 586 3300 4125 3750 4500 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1875 4125 586 586 1875 4125 2325 4500 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1425 2850 586 586 1425 2850 1875 3225 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2550 1950 586 586 2550 1950 3000 2325 +4 0 0 50 -1 0 11 0.0000 2 135 720 1125 2925 Thread 2\001 +4 2 0 50 -1 0 11 0.0000 2 165 540 1650 1950 Unpark\001 +4 0 0 50 -1 0 11 0.0000 2 165 540 4050 3600 Unpark\001 +4 2 0 50 -1 0 11 0.0000 2 165 540 1125 3750 Unpark\001 +4 2 0 50 -1 0 11 0.0000 2 165 540 2850 4800 Unpark\001 +4 0 0 50 -1 0 11 0.0000 2 135 720 2250 2025 Thread 1\001 +4 0 0 50 -1 0 11 0.0000 2 135 720 3000 4200 Thread 4\001 +4 0 0 50 -1 0 11 0.0000 2 135 720 1575 4200 Thread 3\001 +4 0 0 50 -1 0 11 0.0000 2 165 540 3525 2025 Unpark\001 +4 0 0 50 -1 0 11 0.0000 2 135 720 3375 2925 Thread 5\001 Index: doc/theses/thierry_delisle_PhD/thesis/text/eval_macro.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/eval_macro.tex (revision a633f6fa702673747b3ee86a0f8e2e48456226f4) +++ doc/theses/thierry_delisle_PhD/thesis/text/eval_macro.tex (revision a633f6fa702673747b3ee86a0f8e2e48456226f4) @@ -0,0 +1,15 @@ +\chapter{Macro-Benchmarks}\label{macrobench} + +\section{Static Web-Server} + +In Memory Plain Text + +Networked Plain Text + +Networked ZIPF + +\section{Memcached} + +In Memory + +Networked Index: doc/theses/thierry_delisle_PhD/thesis/text/eval_micro.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/eval_micro.tex (revision a633f6fa702673747b3ee86a0f8e2e48456226f4) +++ doc/theses/thierry_delisle_PhD/thesis/text/eval_micro.tex (revision a633f6fa702673747b3ee86a0f8e2e48456226f4) @@ -0,0 +1,50 @@ +\chapter{Micro-Benchmarks}\label{microbench} + +The first step of evaluation is always to test-out small controlled cases, to ensure that the basics are working properly. +This sections presents four different experimental setup, evaluating some of the basic features of \CFA's scheduler. + +\section{Cycling latency} +The most basic evaluation of any ready queue is to evaluate the latency needed to push and pop one element from the ready-queue. +While these two operation also describe a \texttt{yield} operation, many systems use this as the most basic benchmark. +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. +Not all systems use this information, but those which do may appear to have better performance than they would for disconnected push/pop pairs. +For this reason, I chose a different first benchmark, which I call the Cycle Benchmark. +This benchmark arranges many threads into multiple rings of threads. +Each ring is effectively a circular singly-linked list. +At runtime, each thread unparks the next thread before parking itself. +This corresponds to the desired pair of ready queue operations. +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. +Figure~\ref{fig:cycle} shows a visual representation of this arrangement. + +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. +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. +The 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 thread can park. +While this would not be a correctness problem, every runtime system must handle that race, it could lead to pushes and pops being optimized away. +Since silently omitting ready-queue operations would throw off the measuring of these operations. +Therefore the ring of threads must be big enough so the threads have the time to fully park before they are unparked. +Note that this problem is only present on SMP machines and is significantly mitigated by the fact that there are multiple rings in the system. + +\begin{figure} + \centering + \input{cycle.pstex_t} + \caption[Cycle benchmark]{Cycle benchmark\smallskip\newline Each thread unparks the next thread in the cycle before parking itself.} + \label{fig:cycle} +\end{figure} + +\todo{check term ``idle sleep handling''} +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. +Beyond this point, adding more rings serves to mitigate even more the idle sleep handling. +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. + +The 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. + +\todo{mention where to get the code.} + +\section{Yield} +For completion, I also include the yield benchmark. +This benchmark is much simpler than the cycle tests, it simply creates many threads that call \texttt{yield}. + +\section{Locality} + +\section{Transfer} Index: doc/theses/thierry_delisle_PhD/thesis/thesis.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/thesis.tex (revision cc287800d7bddd7ca9acd23c50bb33d0a4fa3439) +++ doc/theses/thierry_delisle_PhD/thesis/thesis.tex (revision a633f6fa702673747b3ee86a0f8e2e48456226f4) @@ -1,6 +1,6 @@ %====================================================================== -% University of Waterloo Thesis Template for LaTeX -% Last Updated November, 2020 -% by Stephen Carr, IST Client Services, +% University of Waterloo Thesis Template for LaTeX +% Last Updated November, 2020 +% by Stephen Carr, IST Client Services, % University of Waterloo, 200 University Ave. W., Waterloo, Ontario, Canada % FOR ASSISTANCE, please send mail to request@uwaterloo.ca @@ -15,15 +15,15 @@ % Some important notes on using this template and making it your own... -% The University of Waterloo has required electronic thesis submission since October 2006. +% The University of Waterloo has required electronic thesis submission since October 2006. % See the uWaterloo thesis regulations at % https://uwaterloo.ca/graduate-studies/thesis. % This thesis template is geared towards generating a PDF version optimized for viewing on an electronic display, including hyperlinks within the PDF. -% DON'T FORGET TO ADD YOUR OWN NAME AND TITLE in the "hyperref" package configuration below. +% DON'T FORGET TO ADD YOUR OWN NAME AND TITLE in the "hyperref" package configuration below. % THIS INFORMATION GETS EMBEDDED IN THE PDF FINAL PDF DOCUMENT. % You can view the information if you view properties of the PDF document. -% Many faculties/departments also require one or more printed copies. -% This template attempts to satisfy both types of output. +% Many faculties/departments also require one or more printed copies. +% This template attempts to satisfy both types of output. % See additional notes below. % It is based on the standard "book" document class which provides all necessary sectioning structures and allows multi-part theses. @@ -32,15 +32,15 @@ % For people who prefer to install their own LaTeX distributions on their own computers, and process the source files manually, the following notes provide the sequence of tasks: - + % E.g. to process a thesis called "mythesis.tex" based on this template, run: % pdflatex mythesis -- first pass of the pdflatex processor % bibtex mythesis -- generates bibliography from .bib data file(s) -% makeindex -- should be run only if an index is used +% makeindex -- should be run only if an index is used % pdflatex mythesis -- fixes numbering in cross-references, bibliographic references, glossaries, index, etc. % pdflatex mythesis -- it takes a couple of passes to completely process all cross-references % If you use the recommended LaTeX editor, Texmaker, you would open the mythesis.tex file, then click the PDFLaTeX button. Then run BibTeX (under the Tools menu). -% Then click the PDFLaTeX button two more times. +% Then click the PDFLaTeX button two more times. % If you have an index as well,you'll need to run MakeIndex from the Tools menu as well, before running pdflatex % the last two times. @@ -51,5 +51,5 @@ % Tip: Photographs should be cropped and compressed so as not to be too large. -% To create a PDF output that is optimized for double-sided printing: +% To create a PDF output that is optimized for double-sided printing: % 1) comment-out the \documentclass statement in the preamble below, and un-comment the second \documentclass line. % 2) change the value assigned below to the boolean variable "PrintVersion" from " false" to "true". @@ -67,5 +67,5 @@ % If you have to, it's easier to make changes to nomenclature once here than in a million places throughout your thesis! \newcommand{\package}[1]{\textbf{#1}} % package names in bold text -\newcommand{\cmmd}[1]{\textbackslash\texttt{#1}} % command name in tt font +\newcommand{\cmmd}[1]{\textbackslash\texttt{#1}} % command name in tt font \newcommand{\href}[1]{#1} % does nothing, but defines the command so the print-optimized version will ignore \href tags (redefined by hyperref pkg). %\newcommand{\texorpdfstring}[2]{#1} % does nothing, but defines the command @@ -235,7 +235,7 @@ \part{Evaluation} \label{Evaluation} -\chapter{Theoretical and Existance Proofs} -\chapter{Micro-Benchmarks} -\chapter{Larger-Scale applications} +% \chapter{Theoretical and Existance Proofs} +\input{text/eval_micro.tex} +\input{text/eval_macro.tex} \part{Conclusion \& Annexes}