Index: doc/theses/thierry_delisle_PhD/thesis/text/eval_micro.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/eval_micro.tex (revision 3e8dacc1abad059c518c1de3a0cd43bdf3c7cd7b) +++ doc/theses/thierry_delisle_PhD/thesis/text/eval_micro.tex (revision 5548175b1844129458cdc52ce5b9f999d5f0aa4b) @@ -4,6 +4,6 @@ This chapter presents five different experimental setups for evaluating the basic features of the \CFA, libfibre~\cite{libfibre}, Go, and Tokio~\cite{Tokio} schedulers. All of these systems have a \gls{uthrding} model. -The goal in this chapter is show the \CFA scheduler obtains equivalent performance to other less fair schedulers through the different experiments. -Note, only the code of the \CFA tests is shown; +The goal of this chapter is show that the \CFA scheduler obtains equivalent performance to other less fair schedulers through the different experiments. +Note that only the code of the \CFA tests is shown; all tests in the other systems are functionally identical and available online~\cite{GITHUB:SchedulingBenchmarks}. @@ -13,7 +13,7 @@ \begin{description} \item[AMD] is a server with two AMD EPYC 7662 CPUs and 256GB of DDR4 RAM. -The EPYC CPU has 64 cores with 2 \glspl{hthrd} per core, for 128 \glspl{hthrd} per socket with 2 sockets for a total of 256 \glspl{hthrd}. +The EPYC CPU has 64 cores with 2 \glspl{hthrd} per core, for a total of 128 \glspl{hthrd} per socket with 2 sockets for a total of 256 \glspl{hthrd}. Each CPU has 4 MB, 64 MB and 512 MB of L1, L2 and L3 caches, respectively. -Each L1 and L2 instance are only shared by \glspl{hthrd} on a given core, but each L3 instance is shared by 4 cores, therefore 8 \glspl{hthrd}. +Each L1 and L2 instance is only shared by \glspl{hthrd} on a given core, but each L3 instance is shared by 4 cores, therefore 8 \glspl{hthrd}. The server runs Ubuntu 20.04.2 LTS on top of Linux Kernel 5.8.0-55. @@ -25,5 +25,5 @@ \end{description} -For all benchmarks, @taskset@ is used to limit the experiment to 1 NUMA node with no hyper threading. +For all benchmarks, @taskset@ is used to limit the experiment to 1 NUMA node with no hyperthreading. If more \glspl{hthrd} are needed, then 1 NUMA node with hyperthreading is used. If still more \glspl{hthrd} are needed, then the experiment is limited to as few NUMA nodes as needed. @@ -32,8 +32,8 @@ On AMD, the same algorithm is used, but the machine only has 2 sockets. So hyperthreading\footnote{ -Hyperthreading normally refers specifically to the technique used by Intel, however it is often used generically to refer to any equivalent feature.} -is used when the \proc count reach 65 and 193. - -The limited sharing of the last-level cache on the AMD machine is markedly different than the Intel machine. +Hyperthreading normally refers specifically to the technique used by Intel, however, it is often used generically to refer to any equivalent feature.} +is used when the \proc count reaches 65 and 193. + +The limited sharing of the last-level cache on the AMD machine is markedly different from the Intel machine. Indeed, while on both architectures L2 cache misses that are served by L3 caches on a different CPU incur a significant latency, on the AMD it is also the case that cache misses served by a different L3 instance on the same CPU also incur high latency. @@ -42,5 +42,5 @@ Each experiment is run 15 times varying the number of processors depending on the two different computers. All experiments gather throughput data and secondary data for scalability or latency. -The data is graphed using a solid, a dashed, and a dotted line, representing the median, maximum and minimum result respectively, where the minimum/maximum lines are referred to as the \emph{extremes}.\footnote{ +The data is graphed using a solid, a dashed, and a dotted line, representing the median, maximum and minimum results respectively, where the minimum/maximum lines are referred to as the \emph{extremes}.\footnote{ An alternative display is to use error bars with min/max as the bottom/top for the bar. However, this approach is not truly an error bar around a mean value and I felt the connected lines are easier to read.} @@ -62,5 +62,5 @@ Hence, systems that perform this optimization have an artificial performance benefit because the yield becomes a \emph{nop}. For this reason, I designed a different push/pop benchmark, called \newterm{Cycle Benchmark}. -This benchmark arranges a number of \ats into a ring, as seen in Figure~\ref{fig:cycle}, where the ring is a circular singly-linked list. +This benchmark arranges several \ats into a ring, as seen in Figure~\ref{fig:cycle}, where the ring is a circular singly-linked list. At runtime, each \at unparks the next \at before \glslink{atblock}{parking} itself. Unparking the next \at pushes that \at onto the ready queue while the ensuing \park leads to a \at being popped from the ready queue. @@ -79,5 +79,5 @@ If this happens, the scheduler push and pop are avoided and the results of the experiment are skewed. (Note, an \unpark is like a V on a semaphore, so the subsequent \park (P) may not block.) -Every runtime system must handle this race and cannot optimized away the ready-queue pushes and pops. +Every runtime system must handle this race and cannot optimize away the ready-queue pushes and pops. To prevent any attempt of silently omitting ready-queue operations, the ring of \ats is made big enough so the \ats have time to fully \park before being unparked again. Finally, to further mitigate any underlying push/pop optimizations, especially on SMP machines, multiple rings are created in the experiment. @@ -99,5 +99,5 @@ } \end{cfa} -\caption[Cycle Benchmark : Pseudo Code]{Cycle Benchmark : Pseudo Code} +\caption[Cycle Benchmark: Pseudo Code]{Cycle Benchmark: Pseudo Code} \label{fig:cycle:code} \bigskip @@ -129,5 +129,5 @@ \caption[Cycle Benchmark on Intel]{Cycle Benchmark on Intel\smallskip\newline Throughput and scalability as a function of \proc count, 5 \ats per cycle, and different cycle counts. For throughput, higher is better, for scalability, lower is better. - Each series represent 15 independent runs, the dashed lines are maximums of each series while the solid lines are the median and the dotted lines are the minimums.} + Each series represent 15 independent runs, the dashed lines are the maximums of each series while the solid lines are the median and the dotted lines are the minimums.} \label{fig:cycle:jax} \end{figure} @@ -161,5 +161,5 @@ \caption[Cycle Benchmark on AMD]{Cycle Benchmark on AMD\smallskip\newline Throughput and scalability as a function of \proc count, 5 \ats per cycle, and different cycle counts. For throughput, higher is better, for scalability, lower is better. - Each series represent 15 independent runs, the dashed lines are maximums of each series while the solid lines are the median and the dotted lines are the minimums.} + Each series represent 15 independent runs, the dashed lines are the maximums of each series while the solid lines are the median and the dotted lines are the minimums.} \label{fig:cycle:nasus} \end{figure} @@ -173,5 +173,5 @@ As a result of the \gls{kthrd} placement, additional \procs from 25 to 48 offer less performance improvement for all runtimes, which can be seen as a flatting of the line. This effect even causes a decrease in throughput in libfibre's case. -As expected, this pattern repeats again between \proc count 72 and 96. +As expected, this pattern repeats between \proc count 72 and 96. Looking next at the right column on Intel, Figures~\ref{fig:cycle:jax:low:ops} and \ref{fig:cycle:jax:low:ns} show the results for 1 cycle of 5 \ats for each \proc. @@ -179,5 +179,5 @@ Go achieves slightly better performance than \CFA and Tokio, but all three display significantly worst performance compared to the left column. This decrease in performance is likely due to the additional overhead of the idle-sleep mechanism. -This can either be the result of \procs actually running out of work, or simply additional overhead from tracking whether or not there is work available. +This can either be the result of \procs actually running out of work or simply additional overhead from tracking whether or not there is work available. Indeed, unlike the left column, it is likely that the ready-queue is transiently empty, which likely triggers additional synchronization steps. Interestingly, libfibre achieves better performance with 1 cycle. @@ -193,7 +193,7 @@ Note, I did not investigate the libfibre performance boost for 1 cycle in this experiment. -The conclusion from both architectures is that all of the compared runtime have fairly equivalent performance for this micro-benchmark. +The conclusion from both architectures is that all of the compared runtimes have fairly equivalent performance for this micro-benchmark. Clearly, the pathological case with 1 cycle per \proc can affect fairness algorithms managing mostly idle processors, \eg \CFA, but only at high core counts. -For this case, \emph{any} helping is likely to cause a cascade of \procs running out of work and attempting to steal. +In this case, \emph{any} helping is likely to cause a cascade of \procs running out of work and attempting to steal. For this experiment, the \CFA scheduler has achieved the goal of obtaining equivalent performance to other less fair schedulers. @@ -218,5 +218,5 @@ } \end{cfa} -\caption[Yield Benchmark : Pseudo Code]{Yield Benchmark : Pseudo Code} +\caption[Yield Benchmark: Pseudo Code]{Yield Benchmark: Pseudo Code} \label{fig:yield:code} %\end{figure} @@ -229,5 +229,5 @@ \label{fig:yield:jax:ops} } - \subfloat[][Throughput, 1 \ats per \proc]{ + \subfloat[][Throughput, 1 \at per \proc]{ \resizebox{0.5\linewidth}{!}{ \input{result.yield.low.jax.ops.pstex_t} @@ -242,5 +242,5 @@ \label{fig:yield:jax:ns} } - \subfloat[][Scalability, 1 \ats per \proc]{ + \subfloat[][Scalability, 1 \at per \proc]{ \resizebox{0.5\linewidth}{!}{ \input{result.yield.low.jax.ns.pstex_t} @@ -250,5 +250,5 @@ \caption[Yield Benchmark on Intel]{Yield Benchmark on Intel\smallskip\newline Throughput and scalability as a function of \proc count. For throughput, higher is better, for scalability, lower is better. - Each series represent 15 independent runs, the dashed lines are maximums of each series while the solid lines are the median and the dotted lines are the minimums.} + Each series represent 15 independent runs, the dashed lines are the maximums of each series while the solid lines are the median and the dotted lines are the minimums.} \label{fig:yield:jax} \end{figure} @@ -258,12 +258,12 @@ Figures~\ref{fig:yield:jax} and \ref{fig:yield:nasus} show the results for the yield experiment on Intel and AMD, respectively. Looking at the left column on Intel, Figures~\ref{fig:yield:jax:ops} and \ref{fig:yield:jax:ns} show the results for 100 \ats for each \proc. -Note, the Y-axis on this graph is twice as large as the Intel cycle-graph. +Note, taht the Y-axis on this graph is twice as large as the Intel cycle graph. A visual glance between the left columns of the cycle and yield graphs confirms my claim that the yield benchmark is unreliable. \CFA has no special handling for @yield@, but this experiment requires less synchronization than the @cycle@ experiment. Hence, the @yield@ throughput and scalability graphs have similar shapes to the corresponding @cycle@ graphs. -The only difference is sightly better performance for @yield@ because of less synchronization. +The only difference is slightly better performance for @yield@ because of less synchronization. Libfibre has special handling for @yield@ using the fact that the number of ready fibres does not change, and therefore, by-passing the idle-sleep mechanism entirely. Hence, libfibre behaves very differently in the cycle and yield benchmarks, with a 4 times increase in performance on the left column. -Go has special handling for @yield@ by putting a yielding goroutine on a secondary global ready-queue, giving it lower priority. +Go has special handling for @yield@ by putting a yielding goroutine on a secondary global ready-queue, giving it a lower priority. The result is that multiple \glspl{hthrd} contend for the global queue and performance suffers drastically. Hence, Go behaves very differently in the cycle and yield benchmarks, with a complete performance collapse in @yield@. @@ -275,9 +275,9 @@ Looking next at the right column on Intel, Figures~\ref{fig:yield:jax:low:ops} and \ref{fig:yield:jax:low:ns} show the results for 1 \at for each \proc. As for @cycle@, \CFA's cost of idle sleep comes into play in a very significant way in Figure~\ref{fig:yield:jax:low:ns}, where the scaling is not flat. -This result is to be expected since fewer \ats means \procs are more likely to run out of work. -On the other hand, when only running 1 \at per \proc, libfibre optimizes further, and forgoes the context-switch entirely. -This results in libfibre outperforming other runtimes even more, achieving 8 times more throughput than for @cycle@. -Finally, Go and Tokio performance collapse is still the same with fewer \ats. -The only exception is Tokio running on 24 \proc, deepening the mystery of its yielding mechanism further. +This result is to be expected since fewer \ats mean \procs are more likely to run out of work. +On the other hand, when only running 1 \at per \proc, libfibre optimizes further and forgoes the context switch entirely. +This results in libfibre outperforming other runtimes, even more, achieving 8 times more throughput than for @cycle@. +Finally, Go and Tokio's performance collapse is still the same with fewer \ats. +The only exception is Tokio running on 24 \procs, deepening the mystery of its yielding mechanism further. \begin{figure} @@ -309,5 +309,5 @@ \caption[Yield Benchmark on AMD]{Yield Benchmark on AMD\smallskip\newline Throughput and scalability as a function of \proc count. For throughput, higher is better, for scalability, lower is better. - Each series represent 15 independent runs, the dashed lines are maximums of each series while the solid lines are the median and the dotted lines are the minimums.} + Each series represent 15 independent runs, the dashed lines are the maximums of each series while the solid lines are the median and the dotted lines are the minimums.} \label{fig:yield:nasus} \end{figure} @@ -316,12 +316,12 @@ Note that the maximum of the Y-axis on Intel and AMD differ less in @yield@ than @cycle@. Looking at the left column first, Figures~\ref{fig:yield:nasus:ops} and \ref{fig:yield:nasus:ns}, \CFA achieves very similar throughput and scaling. -Libfibre still outpaces all other runtimes, but it encounter a performance hit at 64 \procs. -This anomaly suggest some amount of communication between the \procs that the Intel machine is able to mask where the AMD is not once hyperthreading is needed. +Libfibre still outpaces all other runtimes, but it encounters a performance hit at 64 \procs. +This anomaly suggests some amount of communication between the \procs that the Intel machine is able to mask where the AMD is not once hyperthreading is needed. Go and Tokio still display the same performance collapse as on Intel. Looking next at the right column on AMD, Figures~\ref{fig:yield:nasus:low:ops} and \ref{fig:yield:nasus:low:ns}, all runtime systems effectively behave the same as they did on the Intel machine. At the high \ats count, the only difference is Libfibre's scaling and this difference disappears on the right column. -This behaviour suggest whatever communication issue it encountered on the left is completely circumvented on the right. - -It is difficult to draw conclusions for this benchmark when runtime system treat @yield@ so differently. +This behaviour suggests whatever communication issue it encountered on the left is completely circumvented on the right. + +It is difficult to draw conclusions for this benchmark when runtime systems treat @yield@ so differently. The win for \CFA is its consistency between the cycle and yield benchmarks making it simpler for programmers to use and understand, \ie the \CFA semantics match with programmer intuition. @@ -329,5 +329,5 @@ \section{Churn} -The Cycle and Yield benchmark represent an \emph{easy} scenario for a scheduler, \eg an embarrassingly parallel application. +The Cycle and Yield benchmarks represent an \emph{easy} scenario for a scheduler, \eg an embarrassingly parallel application. In these benchmarks, \ats can be easily partitioned over the different \procs upfront and none of the \ats communicate with each other. @@ -336,12 +336,12 @@ This dequeuing results in either contention on the remote queue and/or \glspl{rmr} on the \at data structure. Hence, this benchmark has performance dominated by the cache traffic as \procs are constantly accessing each other's data. -In either case, this benchmark aims to measure how well a scheduler handles these cases, since both cases can lead to performance degradation if not handled correctly. +In either case, this benchmark aims to measure how well a scheduler handles these cases since both cases can lead to performance degradation if not handled correctly. This benchmark uses a fixed-size array of counting semaphores. Each \at picks a random semaphore, @V@s it to unblock any waiting \at, and then @P@s (maybe blocks) the \at on the semaphore. This creates a flow where \ats push each other out of the semaphores before being pushed out themselves. -For this benchmark to work, the number of \ats must be equal or greater than the number of semaphores plus the number of \procs; -\eg if there are 10 semaphores and 5 \procs, but only 3 \ats, all 3 \ats can block (P) on a random semaphore and now there is no \ats to unblock (V) them. -Note, the nature of these semaphores mean the counter can go beyond 1, which can lead to nonblocking calls to @P@. +For this benchmark to work, the number of \ats must be equal to or greater than the number of semaphores plus the number of \procs; +\eg if there are 10 semaphores and 5 \procs, but only 3 \ats, all 3 \ats can block (P) on a random semaphore and now there are no \ats to unblock (V) them. +Note that the nature of these semaphores means the counter can go beyond 1, which can lead to nonblocking calls to @P@. Figure~\ref{fig:churn:code} shows pseudo code for this benchmark, where the @yield@ is replaced by @V@ and @P@. @@ -360,5 +360,5 @@ } \end{cfa} -\caption[Churn Benchmark : Pseudo Code]{Churn Benchmark : Pseudo Code} +\caption[Churn Benchmark: Pseudo Code]{Churn Benchmark: Pseudo Code} \label{fig:churn:code} %\end{figure} @@ -390,7 +390,7 @@ \label{fig:churn:jax:low:ns} } - \caption[Churn Benchmark on Intel]{Churn Benchmark on Intel\smallskip\newline Throughput and scalability of the Churn on the benchmark on the Intel machine. + \caption[Churn Benchmark on Intel]{Churn Benchmark on Intel\smallskip\newline Throughput and scalability as a function of \proc count. For throughput, higher is better, for scalability, lower is better. - Each series represent 15 independent runs, the dashed lines are maximums of each series while the solid lines are the median and the dotted lines are the minimums.} + Each series represent 15 independent runs, the dashed lines are the maximums of each series while the solid lines are the median and the dotted lines are the minimums.} \label{fig:churn:jax} \end{figure} @@ -408,7 +408,7 @@ However, beyond this point Go keeps this level of variation but does not scale further in any of the runs. -Throughput and scalability is notably worst for all runtimes than the previous benchmarks since there is inherently more communication between processors. +Throughput and scalability are notably worst for all runtimes than the previous benchmarks since there is inherently more communication between processors. Indeed, none of the runtimes reach 40 million operations per second while in the cycle benchmark all but libfibre reached 400 million operations per second. -Figures~\ref{fig:churn:jax:ns} and \ref{fig:churn:jax:low:ns} show that for all \proc count, all runtimes produce poor scaling. +Figures~\ref{fig:churn:jax:ns} and \ref{fig:churn:jax:low:ns} show that for all \proc counts, all runtimes produce poor scaling. However, once the number of \glspl{hthrd} goes beyond a single socket, at 48 \procs, scaling goes from bad to worst and performance completely ceases to improve. At this point, the benchmark is dominated by inter-socket communication costs for all runtimes. @@ -417,5 +417,5 @@ Indeed, when a \proc unparks a \at that was last run on a different \proc, the \at could be appended to the ready queue of the local \proc or to the ready queue of the remote \proc, which previously ran the \at. \CFA, Tokio and Go all use the approach of \glslink{atsched}{unparking} to the local \proc, while Libfibre unparks to the remote \proc. -In this particular benchmark, the inherent chaos of the benchmark, in addition to small memory footprint, means neither approach wins over the other. +In this particular benchmark, the inherent chaos of the benchmark, in addition to the small memory footprint, means neither approach wins over the other. Looking next at the right column on Intel, Figures~\ref{fig:churn:jax:low:ops} and \ref{fig:churn:jax:low:ns} show the results for 1 \at for each \proc, and many of the differences between the runtimes disappear. @@ -424,8 +424,8 @@ Tokio maintains effectively the same curve shapes as \CFA and libfibre, but it incurs extra costs for all \proc counts. While Go maintains overall similar results to the others, it again encounters significant variation at high \proc counts. -Inexplicably resulting in super-linear scaling for some runs, \ie the scalability curves displays a negative slope. +Inexplicably resulting in super-linear scaling for some runs, \ie the scalability curves display a negative slope. Interestingly, unlike the cycle benchmark, running with fewer \ats does not produce drastically different results. -In fact, the overall throughput stays almost exactly the same on the left and right column. +In fact, the overall throughput stays almost exactly the same on the left and right columns. \begin{figure} @@ -455,7 +455,7 @@ \label{fig:churn:nasus:low:ns} } - \caption[Churn Benchmark on AMD]{Churn Benchmark on AMD\smallskip\newline Throughput and scalability of the Churn on the benchmark on the AMD machine. + \caption[Churn Benchmark on AMD]{Churn Benchmark on AMD\smallskip\newline Throughput and scalability as a function of \proc count. For throughput, higher is better, for scalability, lower is better. - Each series represent 15 independent runs, the dashed lines are maximums of each series while the solid lines are the median and the dotted lines are the minimums.} + Each series represent 15 independent runs, the dashed lines are the maximums of each series while the solid lines are the median and the dotted lines are the minimums.} \label{fig:churn:nasus} \end{figure} @@ -464,17 +464,17 @@ Looking now at the results for the AMD architecture, Figure~\ref{fig:churn:nasus}, the results show a somewhat different story. Looking at the left column first, Figures~\ref{fig:churn:nasus:ops} and \ref{fig:churn:nasus:ns}, \CFA, Libfibre and Tokio all produce decent scalability. -\CFA suffers particular from a larger variations at higher \proc counts, but largely outperforms the other runtimes. +\CFA suffers particularly from larger variations at higher \proc counts, but largely outperforms the other runtimes. Go still produces intriguing results in this case and even more intriguingly, the results have fairly low variation. One possible explanation for Go's difference is that it has very few available concurrent primitives, so a channel is substituted for a semaphore. -On paper a semaphore can be replaced by a channel, and with zero-sized objects passed through the channel, equivalent performance could be expected. -However, in practice, there are implementation difference between the two, \eg if the semaphore count can get somewhat high so object accumulate in the channel. +On paper, a semaphore can be replaced by a channel, and with zero-sized objects passed through the channel, equivalent performance could be expected. +However, in practice, there are implementation differences between the two, \eg if the semaphore count can get somewhat high so objects accumulate in the channel. Note that this substitution is also made in the cycle benchmark; however, in that context, it did not have a notable impact. -As second possible explanation is that Go may use the heap when allocating variables based on the result of escape analysis of the code. +A second possible explanation is that Go may use the heap when allocating variables based on the result of the escape analysis of the code. It is possible for variables that could be placed on the stack to instead be placed on the heap. This placement could cause extra pointer chasing in the benchmark, heightening locality effects. -Depending on how the heap is structure, this could also lead to false sharing. +Depending on how the heap is structured, this could also lead to false sharing. I did not investigate what causes these unusual results. @@ -483,9 +483,9 @@ Go still suffers from poor scalability but is now unusual in a different way. While it obtains effectively constant performance regardless of \proc count, this ``sequential'' performance is higher than the other runtimes for low \proc count. -Up to 32 \procs, after which the other runtime manage to outscale Go. +Up to 32 \procs, after which the other runtimes manage to outscale Go. In conclusion, the objective of this benchmark is to demonstrate that \glslink{atsched}{unparking} \ats from remote \procs does not cause too much contention on the local queues. Indeed, the fact that most runtimes achieve some scaling between various \proc count demonstrate migrations do not need to be serialized. -Again these result demonstrate \CFA achieves satisfactory performance with respect to the other runtimes. +Again these results demonstrate that \CFA achieves satisfactory performance compared to the other runtimes. \section{Locality} @@ -496,8 +496,8 @@ In both variations, before @V@ing the semaphore, each \at calls a @work@ function which increments random cells inside the data array. In the noshare variation, the array is not passed on and each thread continuously accesses its private array. -In the share variation, the array is passed to another thread via the semaphore's shadow-queue (each blocking thread can save a word of user data in its blocking node), transferring ownership of the array to the woken thread. -Figure~\ref{fig:locality:code} shows pseudo code for this benchmark. - -The objective here is to highlight the different decision made by the runtime when \glslink{atsched}{unparking}. +In the share variation, the array is passed to another thread via the semaphore's shadow queue (each blocking thread can save a word of user data in its blocking node), transferring ownership of the array to the woken thread. +Figure~\ref{fig:locality:code} shows the pseudo-code for this benchmark. + +The objective here is to highlight the different decisions made by the runtime when \glslink{atsched}{unparking}. Since each thread unparks a random semaphore, it means that it is unlikely that a \at is unparked from the last \proc it ran on. In the noshare variation, \glslink{atsched}{unparking} the \at on the local \proc is an appropriate choice since the data was last modified on that \proc. @@ -506,5 +506,5 @@ The expectation for this benchmark is to see a performance inversion, where runtimes fare notably better in the variation which matches their \glslink{atsched}{unparking} policy. This decision should lead to \CFA, Go and Tokio achieving better performance in the share variation while libfibre achieves better performance in noshare. -Indeed, \CFA, Go and Tokio have the default policy of \glslink{atsched}{unparking} \ats on the local \proc, where as libfibre has the default policy of \glslink{atsched}{unparking} \ats wherever they last ran. +Indeed, \CFA, Go and Tokio have the default policy of \glslink{atsched}{unparking} \ats on the local \proc, whereas libfibre has the default policy of \glslink{atsched}{unparking} \ats wherever they last ran. \begin{figure} @@ -556,5 +556,5 @@ \subfloat[Share]{\label{fig:locality:code:T2}\usebox\myboxB} -\caption[Locality Benchmark : Pseudo Code]{Locality Benchmark : Pseudo Code} +\caption[Locality Benchmark: Pseudo Code]{Locality Benchmark: Pseudo Code} \label{fig:locality:code} \end{figure} @@ -570,5 +570,5 @@ Go trails behind in this experiment, presumably for the same reasons that were observable in the churn benchmark. Otherwise, the results are similar to the churn benchmark, with lower throughput due to the array processing. -As for most previous results, all runtimes suffer a performance hit after 48 \proc, which is the socket boundary, and climb again from 96 to 192 \procs. +As for most previous results, all runtimes suffer a performance hit after 48 \procs, which is the socket boundary, and climb again from 96 to 192 \procs. \begin{figure} @@ -600,5 +600,5 @@ \caption[Locality Benchmark on Intel]{Locality Benchmark on Intel\smallskip\newline Throughput and scalability as a function of \proc count. For throughput, higher is better, for scalability, lower is better. - Each series represent 15 independent runs, the dashed lines are maximums of each series while the solid lines are the median and the dotted lines are the minimums.} + Each series represent 15 independent runs, the dashed lines are the maximums of each series while the solid lines are the median and the dotted lines are the minimums.} \label{fig:locality:jax} \end{figure} @@ -632,5 +632,5 @@ \caption[Locality Benchmark on AMD]{Locality Benchmark on AMD\smallskip\newline Throughput and scalability as a function of \proc count. For throughput, higher is better, for scalability, lower is better. - Each series represent 15 independent runs, the dashed lines are maximums of each series while the solid lines are the median and the dotted lines are the minimums.} + Each series represent 15 independent runs, the dashed lines are the maximums of each series while the solid lines are the median and the dotted lines are the minimums.} \label{fig:locality:nasus} \end{figure} @@ -640,8 +640,8 @@ Indeed, in this case, unparking remotely means the unparked \at is less likely to suffer a cache miss on the array, which leaves the \at data structure and the remote queue as the only source of likely cache misses. Results show both are amortized fairly well in this case. -\CFA and Tokio both \unpark locally and as a result suffer a marginal performance degradation from the cache miss on the array. +\CFA and Tokio both \unpark locally and as a result, suffer a marginal performance degradation from the cache miss on the array. Looking at the results for the AMD architecture, Figure~\ref{fig:locality:nasus}, shows results similar to the Intel. -Again overall performance is higher and slightly more variation is visible. +Again the overall performance is higher and slightly more variation is visible. Looking at the left column first, Figures~\ref{fig:locality:nasus:share:ops} and \ref{fig:locality:nasus:share:ns}, \CFA and Tokio still outperform libfibre, this time more significantly. This advantage is expected from the AMD server with its smaller and more narrow caches that magnify the costs of processing the array. @@ -685,5 +685,5 @@ // pick next leader leader := threads[ prng() % len(threads) ] - // wake every one + // wake everyone if ! exhaust { for t in threads { @@ -704,16 +704,16 @@ } \end{cfa} -\caption[Transfer Benchmark : Pseudo Code]{Transfer Benchmark : Pseudo Code} +\caption[Transfer Benchmark: Pseudo Code]{Transfer Benchmark: Pseudo Code} \label{fig:transfer:code} \end{figure} -The experiment is designed to evaluate the short-term load-balancing of a scheduler. +The experiment is designed to evaluate the short-term load balancing of a scheduler. Indeed, schedulers where the runnable \ats are partitioned on the \procs may need to balance the \ats for this experiment to terminate. This problem occurs because the spinning \at is effectively preventing the \proc from running any other \at. -In the semaphore variation, the number of runnable \ats eventually dwindles down to only the leader. +In the semaphore variation, the number of runnable \ats eventually dwindles to only the leader. This scenario is a simpler case to handle for schedulers since \procs eventually run out of work. In the yielding variation, the number of runnable \ats stays constant. This scenario is a harder case to handle because corrective measures must be taken even when work is available. -Note, runtimes with preemption circumvent this problem by forcing the spinner to yield. +Note that runtimes with preemption circumvent this problem by forcing the spinner to yield. In \CFA preemption was disabled as it only obfuscates the results. I am not aware of a method to disable preemption in Go. @@ -722,12 +722,12 @@ In an ideal scenario where the scheduler is strictly FIFO, every thread would run once after the synchronization and therefore the delay between leaders would be given by, $(CSL + SL) / (NP - 1)$, where $CSL$ is the context-switch latency, $SL$ is the cost for enqueueing and dequeuing a \at, and $NP$ is the number of \procs. -However, if the scheduler allows \ats to run many times before other \ats are able to run once, this delay increases. +However, if the scheduler allows \ats to run many times before other \ats can run once, this delay increases. The semaphore version is an approximation of strictly FIFO scheduling, where none of the \ats \emph{attempt} to run more than once. The benchmark effectively provides the fairness guarantee in this case. -In the yielding version however, the benchmark provides no such guarantee, which means the scheduler has full responsibility and any unfairness is measurable. - -While this is an artificial scenario, in real-life it requires only a few simple pieces. +In the yielding version, however the benchmark provides no such guarantee, which means the scheduler has full responsibility and any unfairness is measurable. + +While this is an artificial scenario, in real life it requires only a few simple pieces. The yielding version simply creates a scenario where a \at runs uninterrupted in a saturated system and the starvation has an easily measured impact. -Hence, \emph{any} \at that runs uninterrupted for a significant period of time in a saturated system could lead to this kind of starvation. +Hence, \emph{any} \at that runs uninterrupted for a significant time in a saturated system could lead to this kind of starvation. \subsection{Results} @@ -755,14 +755,14 @@ \end{table} -Table~\ref{fig:transfer:res} shows the result for the transfer benchmark with 2 \procs and all \procs on the computer, where each experiment runs 100 \at per \proc. +Table~\ref{fig:transfer:res} shows the result for the transfer benchmark with 2 \procs and all \procs on the computer, where each experiment runs 100 \ats per \proc. Note that the results here are only meaningful as a coarse measurement of fairness, beyond which small cost differences in the runtime and concurrent primitives begin to matter. -As such, data points within the same order of magnitude are basically considered equal. +As such, data points within the same order of magnitude are considered equal. That is, the takeaway of this experiment is the presence of very large differences. -The semaphore variation is denoted ``Park'', where the number of \ats dwindles down as the new leader is acknowledged. +The semaphore variation is denoted ``Park'', where the number of \ats dwindles as the new leader is acknowledged. The yielding variation is denoted ``Yield''. -The experiment is only run for few and many \procs, since scaling is not the focus of this experiment. +The experiment is only run for a few and many \procs since scaling is not the focus of this experiment. The first two columns show the results for the semaphore variation on Intel. -While there are some differences in latencies, \CFA is consistently the fastest and Tokio the slowest, all runtimes achieve results that are fairly close. +While there are some differences in latencies, \CFA is consistently the fastest and Tokio the slowest, all runtimes achieve fairly close results. Again, this experiment is meant to highlight major differences so latencies within $10\times$ of each other are considered equal. @@ -773,5 +773,5 @@ This difference is because Go has a classic work-stealing scheduler, but it adds coarse-grain preemption , which interrupts the spinning leader after a period. -Neither Libfibre or Tokio complete the experiment. +Neither Libfibre nor Tokio complete the experiment. Both runtimes also use classical work-stealing scheduling without preemption, and therefore, none of the work queues are ever emptied so no load balancing occurs. @@ -779,7 +779,7 @@ The first two columns show all runtime obtaining results well within $10\times$ of each other. The next two columns again show \CFA producing low latencies, while Go still has notably higher latency but the difference is less drastic on 2 \procs, where it produces a $15\times$ difference as opposed to a $100\times$ difference on 256 \procs. -Neither Libfibre or Tokio complete the experiment. - -This experiments clearly demonstrates \CFA achieves significantly better fairness. +Neither Libfibre nor Tokio complete the experiment. + +This experiment clearly demonstrates that \CFA achieves significantly better fairness. The semaphore variation serves as a control, where all runtimes are expected to transfer leadership fairly quickly. Since \ats block after acknowledging the leader, this experiment effectively measures how quickly \procs can steal \ats from the \proc running the leader.