Index: doc/theses/thierry_delisle_PhD/thesis/text/eval_micro.tex =================================================================== --- doc/theses/thierry_delisle_PhD/thesis/text/eval_micro.tex (revision 507d48d0cb090a3bb374a14ca7882b10bf38695c) +++ doc/theses/thierry_delisle_PhD/thesis/text/eval_micro.tex (revision 31b9d3c500e5550cc1127210f69a12736a26ab4d) @@ -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 and two dashed lines 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 result 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.} @@ -51,7 +51,7 @@ In this representation, perfect scalability should appear as a horizontal line, \eg, if doubling the number of \procs doubles the throughput, then the relation stays the same. -The left column shows results for 100 cycles per \proc, enough cycles to always keep every \proc busy. -The right column shows results for 1 cycle per \proc, where the ready queues are expected to be near empty most of the time. -The distinction between 100 and 1 cycles is meaningful because the idle sleep subsystem is expected to matter only in the right column, where spurious effects can cause a \proc to run out of work temporarily. +The left column shows results for hundreds of \ats per \proc, enough to always keep every \proc busy. +The right column shows results for very few \ats per \proc, where the ready queues are expected to be near empty most of the time. +The distinction between many and few \ats is meaningful because the idle sleep subsystem is expected to matter only in the right column, where spurious effects can cause a \proc to run out of work temporarily. \section{Cycle} @@ -101,7 +101,6 @@ \caption[Cycle Benchmark : Pseudo Code]{Cycle Benchmark : Pseudo Code} \label{fig:cycle:code} -%\end{figure} - -\bigskip +%\end{figure}ll have a physical key so it's not urgent. + %\begin{figure} @@ -131,5 +130,7 @@ \label{fig:cycle:jax:low:ns} } - \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 count. For throughput, higher is better, for scalability, lower is better. Each series represent 15 independent runs, the dotted lines are maximums while the solid line is the medium.} + \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 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 mnimums.} \label{fig:cycle:jax} \end{figure} @@ -161,5 +162,7 @@ \label{fig:cycle:nasus:low:ns} } - \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 count. For throughput, higher is better, for scalability, lower is better. Each series represent 15 independent runs, the dotted lines are extremes while the solid line is the medium.} + \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 mnimums.} \label{fig:cycle:nasus} \end{figure} @@ -167,32 +170,34 @@ \subsection{Results} -For the Intel architecture, Figure~\ref{fig:cycle:jax}: -\begin{itemize} -\item -For 100 cycles per \proc (first column), \CFA, Go and Tokio all obtain effectively the same throughput performance. +Figure~\ref{fig:cycle:jax} and \ref{fig:cycle:nasus} show the results for the cycle experiment. +Looking at the left column on Intel first, Figure~\ref{fig:cycle:jax:ops} and \ref{fig:cycle:jax:ns}, which shows the results for many \ats, in this case 100 cycles of 5 \ats for each \proc. +\CFA, Go and Tokio all obtain effectively the same throughput performance. Libfibre is slightly behind in this case but still scales decently. -As a result of the \gls{kthrd} placement, additional \procs from 25 to 48 offer less performance improvement (flatting of the line) for all runtimes. +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. -\item -For 1 cycle per \proc, \CFA and Tokio obtain very similar results overall, but Tokio shows more variations in the results. -Go achieves slightly better performance. + +Looking next at the right column on Intel, Figure~\ref{fig:cycle:jax:low:ops} and \ref{fig:cycle:jax:low:ns}, which shows the results for few threads, in this case 1 cycle of 5 \ats for each \proc. +\CFA and Tokio obtain very similar results overall, but Tokio shows more variations in the results. +Go achieves slightly better performance than \CFA and Tokio, but all three display significantly workst 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. +Indeed, unlike the left column, it is likely that the ready-queue will be transiently empty, which likely triggers additional synchronization steps. Interestingly, libfibre achieves better performance with 1 cycle. -\end{itemize} - -For the AMD architecture, Figure~\ref{fig:cycle:nasus}, the results show the same story as on the Intel, with close to double the performance overall but with slightly increased variation. + +Looking now at the results for the AMD architecture, Figure~\ref{fig:cycle:nasus}, the results show a story that is overall similar to the results on the Intel, with close to double the performance overall but with slightly increased variation and some differences in the details. +Note that the maximum of the Y-axis on Intel and AMD differ significantly. +Looking at the left column first, Figure~\ref{fig:cycle:nasus:ops} and \ref{fig:cycle:nasus:ns}, unlike Intel, on AMD all 4 runtimes achieve very similar throughput and scalability. +However, as the number of \procs grows higher, the results on AMD show notably more variability than on Intel. The different performance improvements and plateaus are due to cache topology and appear at the expected \proc counts of 64, 128 and 192, for the same reasons as on Intel. -\begin{itemize} -\item -For 100 cycles per \proc, unlike Intel, all 4 runtimes achieve very similar throughput and scalability. -\item -For 1 cycle per \proc, unlike on Intel, Tokio and Go have the same throughput performance, while \CFA is slightly slower. -Again, the same performance increase for libfibre is visible. -\end{itemize} +Looking next at the right column, Figure~\ref{fig:cycle:nasus:low:ops} and \ref{fig:cycle:nasus:low:ns}, Tokio and Go have the same throughput performance, while \CFA is slightly slower. +This is different than on Intel, where Tokio behaved like \CFA rather than behaving like Go. +Again, the same performance increase for libfibre is visible when running fewer \ats. 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. -Clearly, the pathological case with 1 \at per \proc, can affect fairness algorithms managing mostly idle processors, \eg \CFA, but only at high core counts. +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. -For this experiment, the \CFA scheduler has achieved the goal of obtaining equivalent performance to other less fair schedulers, except for very unusual workloads. +For this experiment, the \CFA scheduler has achieved the goal of obtaining equivalent performance to other less fair schedulers. \section{Yield} @@ -246,5 +251,7 @@ \label{fig:yield:jax:low:ns} } - \caption[Yield Benchmark on Intel]{Yield Benchmark on Intel\smallskip\newline Throughput and scalability as a function of \proc count, using 1 \ats per \proc. For throughput, higher is better, for scalability, lower is better. Each series represent 15 independent runs, the dotted lines are extremes while the solid line is the medium.} + \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 mnimums.} \label{fig:yield:jax} \end{figure} @@ -252,27 +259,28 @@ \subsection{Results} -Figures~\ref{fig:yield:jax} and~\ref{fig:yield:nasus} show the same throughput graphs as @cycle@ on Intel and AMD, respectively. -Note, the Y-axis on the yield graph for Intel is twice as large as the Intel cycle-graph. -A visual glance between the cycle and yield graphs confirms my claim that the yield benchmark is unreliable. - -For the Intel architecture, Figure~\ref{fig:yield:jax}: -\begin{itemize} -\item +Figures~\ref{fig:yield:jax} and~\ref{fig:yield:nasus} show the results for the yield experiment. +Looking at the left column on Intel first, Figure~\ref{fig:yield:jax:ops} and \ref{fig:yield:jax:ns}, which shows the results for many \ats, in this case 100 \ats for each \proc. +Note, the Y-axis on the 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 for both 100 and 1 cycles/tasks per processor have similar shapes to the corresponding @cycle@ graphs. +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. -As for @cycle@, the cost of idle sleep also comes into play in a very significant way in Figure~\ref{fig:yield:jax:low:ns}, where the scaling is not flat. -\item -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. -Additionally, when only running 1 \at per \proc, libfibre optimizes further, and forgoes the context-switch entirely. -Hence, libfibre behaves very differently in the cycle and yield benchmarks, with a 4 times increase in performance for 100 cycles/tasks and an 8 times increase for 1 cycle/task. -\item +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. 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@ for both 100 and 1 cycles/tasks. -\item +Hence, Go behaves very differently in the cycle and yield benchmarks, with a complete performance collapse in @yield@. Tokio has a similar performance collapse after 16 processors, and therefore, its special @yield@ handling is probably related to a Go-like scheduler problem and/or a \CFA idle-sleep problem. (I did not dig through the Rust code to ascertain the exact reason for the collapse.) -\end{itemize} +Note that since there is no communication among \ats, locality problems are much less likely than for the cycle benchmark. +This lack of communication is probably why the plateaus due to topology are not present. + +Lookking next at the right column on Intel, Figure~\ref{fig:yield:jax:low:ops} and \ref{fig:yield:jax:low:ns}, which shows the results for few threads, in this case 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 is to be expected since fewet \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. \begin{figure} @@ -302,10 +310,19 @@ \label{fig:yield:nasus:low:ns} } - \caption[Yield Benchmark on AMD]{Yield Benchmark on AMD\smallskip\newline Throughput and scalability as a function of \proc count, using 1 \ats per \proc. For throughput, higher is better, for scalability, lower is better. Each series represent 15 independent runs, the dotted lines are extremes while the solid line is the medium.} + \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 mnimums.} \label{fig:yield:nasus} \end{figure} -For the AMD architecture, Figure~\ref{fig:yield:nasus}, the results show the same story as on the Intel, with slightly increased variations. -Also, some transition points on the X-axis differ because of the architectures, like at 16 versus 24 processors. +Looking now at the results for the AMD architecture, Figure~\ref{fig:yield:nasus}, the results again show a story that is overall similar to the results on the Intel, with increased variation and some differences in the details. +Note that the maximum of the Y-axis on Intel and AMD differ less in @yield@ than @cycle@. +Looking at the left column first, Figure~\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 suggest some amount of communication between the \procs that the Intel machine was able to mask where the AMD is not once hyperthreading is needed. +Go and Tokio still display the same performance collapse than on Intel. +Looking next at the right column, Figure~\ref{fig:yield:nasus:low:ops} and \ref{fig:yield:nasus:low:ns}, all runtime effectively behave the same as they did on the Intel machine. +At high \ats count the only difference was Libfibre's scaling and this difference disappears on the right column. +This suggest that whatever communication benchmark 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. @@ -321,5 +338,5 @@ With processor-specific ready-queues, when a \at is unblocked by a different \proc that means the unblocking \proc must either ``steal'' the \at from another processor or find it on a remote queue. 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 \proc are constantly accessing the each other's data. +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. @@ -364,5 +381,5 @@ } - \subfloat[][Latency, 100 \ats per \proc]{ + \subfloat[][Scalability, 100 \ats per \proc]{ \resizebox{0.5\linewidth}{!}{ \input{result.churn.jax.ns.pstex_t} @@ -370,5 +387,5 @@ \label{fig:churn:jax:ns} } - \subfloat[][Latency, 2 \ats per \proc]{ + \subfloat[][Scalability, 2 \ats per \proc]{ \resizebox{0.5\linewidth}{!}{ \input{result.churn.low.jax.ns.pstex_t} @@ -376,5 +393,7 @@ \label{fig:churn:jax:low:ns} } - \caption[Churn Benchmark on Intel]{\centering Churn Benchmark on Intel\smallskip\newline Throughput and latency of the Churn on the benchmark on the Intel machine. For throughput, higher is better, for scalability, lower is better. Each series represent 15 independent runs, the dotted lines are extremes while the solid line is the medium.} + \caption[Churn Benchmark on Intel]{\centering Churn Benchmark on Intel\smallskip\newline Throughput and scalability of the Churn on the benchmark on the Intel machine. + 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 mnimums.} \label{fig:churn:jax} \end{figure} @@ -382,10 +401,20 @@ \subsection{Results} -Figures~\ref{fig:churn:jax} and Figure~\ref{fig:churn:nasus} show the throughput on Intel and AMD respectively. - -The performance cost of crossing the cache boundaries is still visible at the same \proc count. - -Scalability is notably worst than the previous benchmarks since there is inherently more communication between processors. -Indeed, once the number of \glspl{hthrd} goes beyond a single socket, performance ceases to improve. +Figures~\ref{fig:churn:jax} and Figure~\ref{fig:churn:nasus} show the results for the churn experiment. +Looking at the left column on Intel first, Figure~\ref{fig:churn:jax:ops} and \ref{fig:churn:jax:ns}, which shows the results for many \ats, in this case 100 \ats for each \proc, all runtime obtain fairly similar throughput for most \proc counts. +\CFA does very well on a single \proc but quickly loses its advantage over the other runtimes. +As expected it scales decently up to 48 \procs and then basically plateaus. +Tokio achieves very similar performance to \CFA until 48 \procs, after which it takes a significant hit but does keep scaling somewhat. +Libfibre obtains effectively the same results as Tokio with slightly less scaling, \ie the scaling curve is the same but with slightly higher values. +Finally Go gets the most peculiar results, scaling worst than other runtimes until 48 \procs. +At 72 \procs, the results of the Go runtime vary significantly, sometimes scaling sometimes plateauing. +However, beyond this point Go keeps this level of variation but does not scale 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. +Indeed, none of the runtime 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 runtime 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. + An interesting aspect to note here is that the runtimes differ in how they handle this situation. Indeed, when a \proc unparks a \at that was last run on a different \proc, the \at could be appended to the ready-queue local \proc or to the ready-queue of the remote \proc, which previously ran the \at. @@ -393,4 +422,15 @@ In this particular benchmark, the inherent chaos of the benchmark in addition to small memory footprint means neither approach wins over the other. +Looking next at the right column on Intel, Figure~\ref{fig:churn:jax:low:ops} and \ref{fig:churn:jax:low:ns}, which shows the results for few threads, in this case 1 \at for each \proc, many of the differences between the runtime disappear. +\CFA outperforms other runtimes by a minuscule margin. +Libfibre follows very closely behind with basically the same performance and scaling. +Tokio maintains effectively the same curve shapes as it did with many threads, but it incurs extra costs for all \proc count. +As a result it is slightly outperformed by \CFA and libfibre. +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. + +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. + \begin{figure} \subfloat[][Throughput, 100 \ats per \proc]{ @@ -407,5 +447,5 @@ } - \subfloat[][Latency, 100 \ats per \proc]{ + \subfloat[][Scalability, 100 \ats per \proc]{ \resizebox{0.5\linewidth}{!}{ \input{result.churn.nasus.ns.pstex_t} @@ -413,5 +453,5 @@ \label{fig:churn:nasus:ns} } - \subfloat[][Latency, 2 \ats per \proc]{ + \subfloat[][Scalability, 2 \ats per \proc]{ \resizebox{0.5\linewidth}{!}{ \input{result.churn.low.nasus.ns.pstex_t} @@ -419,18 +459,15 @@ \label{fig:churn:nasus:low:ns} } - \caption[Churn Benchmark on AMD]{\centering Churn Benchmark on AMD\smallskip\newline Throughput and latency of the Churn on the benchmark on the AMD machine. - For throughput, higher is better, for scalability, lower is better. Each series represent 15 independent runs, the dotted lines are extremes while the solid line is the medium.} + \caption[Churn Benchmark on AMD]{\centering Churn Benchmark on AMD\smallskip\newline Throughput and scalability of the Churn on the benchmark on the AMD machine. + 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 mnimums.} \label{fig:churn:nasus} \end{figure} -Like for the cycle benchmark, here all runtimes achieve fairly similar performance. -Performance improves as long as all \procs fit on a single socket. -Beyond that performance starts to suffer from increased caching costs. - -Indeed on Figures~\ref{fig:churn:jax:ops} and \ref{fig:churn:jax:ns} show that with 1 and 100 \ats per \proc, \CFA, libfibre, Go and Tokio achieve effectively equivalent performance for most \proc count. - -However, Figure~\ref{fig:churn:nasus} again shows a somewhat different story on AMD. -While \CFA, libfibre, and Tokio achieve effectively equivalent performance for most \proc count, Go starts with better scaling at very low \proc counts but then performance quickly plateaus, resulting in worse performance at higher \proc counts. -This performance difference is visible at both high and low \at counts. + +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, Figure~\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 almost all run still outperform 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 this difference is that since Go has very few available concurrent primitives, a channel was used instead of a semaphore. @@ -445,6 +482,14 @@ Depending on how the heap is structure, this could also lead to false sharing. +I did not further investigate what causes these unusual results. + +Looking next at the right column, Figure~\ref{fig:churn:nasus:low:ops} and \ref{fig:churn:nasus:low:ns}, like for Intel all runtime obtain overall similar throughput between the left and right column. +\CFA, Libfibre and Tokio all have very close results. +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. + The objective of this benchmark is to demonstrate that unparking \ats from remote \procs do not cause too much contention on the local queues. -Indeed, the fact all runtimes achieve some scaling at lower \proc count demonstrate that migrations do not need to be serialized. +Indeed, the fact most runtimes achieve some scaling between various \proc count demonstrate that migrations do not need to be serialized. Again these result demonstrate \CFA achieves satisfactory performance.