Changeset e76fa30


Ignore:
Timestamp:
Aug 4, 2022, 8:47:12 PM (2 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, ast-experimental, master, pthread-emulation
Children:
0c11d3c
Parents:
e5e2334
Message:

Filled up the eval micro section

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/thierry_delisle_PhD/thesis/text/eval_micro.tex

    re5e2334 re76fa30  
    3232        \centering
    3333        \input{cycle.pstex_t}
    34         \caption[Cycle benchmark]{Cycle benchmark\smallskip\newline Each \gls{at} unparks the next \gls{at} in the cycle before parking itself.}
     34        \caption[Cycle benchmark]{Cycle benchmark\smallskip\newline Each \at unparks the next \at in the cycle before parking itself.}
    3535        \label{fig:cycle}
    3636\end{figure}
    3737The most basic evaluation of any ready queue is to evaluate the latency needed to push and pop one element from the ready queue.
    3838Since these two operation also describe a @yield@ operation, many systems use this operation as the most basic benchmark.
    39 However, yielding can be treated as a special case by optimizing it away since the number of ready \glspl{at} does not change.
     39However, yielding can be treated as a special case by optimizing it away since the number of ready \ats does not change.
    4040Not all systems perform this optimization, but those that do have an artificial performance benefit because the yield becomes a \emph{nop}.
    4141For this reason, I chose a different first benchmark, called \newterm{Cycle Benchmark}.
    42 This benchmark arranges a number of \glspl{at} into a ring, as seen in Figure~\ref{fig:cycle}, where the ring is a circular singly-linked list.
    43 At runtime, each \gls{at} unparks the next \gls{at} before parking itself.
    44 Unparking the next \gls{at} pushes that \gls{at} onto the ready queue as does the ensuing park.
    45 
    46 Hence, the underlying runtime cannot rely on the number of ready \glspl{at} staying constant over the duration of the experiment.
    47 In fact, the total number of \glspl{at} waiting on the ready queue is expected to vary because of the race between the next \gls{at} unparking and the current \gls{at} parking.
     42This 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.
     43At runtime, each \at unparks the next \at before parking itself.
     44Unparking the next \at pushes that \at onto the ready queue while the ensuing park leads to a \at being popped from the ready queue.
     45
     46Hence, the underlying runtime cannot rely on the number of ready \ats staying constant over the duration of the experiment.
     47In fact, the total number of \ats waiting on the ready queue is expected to vary because of the race between the next \at unparking and the current \at parking.
    4848That is, the runtime cannot anticipate that the current task will immediately park.
    49 As well, the size of the cycle is also decided based on this race, \eg a small cycle may see the chain of unparks go full circle before the first \gls{at} parks because of time-slicing or multiple \procs.
     49As well, the size of the cycle is also decided based on this race, \eg a small cycle may see the chain of unparks go full circle before the first \at parks because of time-slicing or multiple \procs.
    5050Every runtime system must handle this race and cannot optimized away the ready-queue pushes and pops.
    51 To prevent any attempt of silently omitting ready-queue operations, the ring of \glspl{at} is made big enough so the \glspl{at} have time to fully park before being unparked again.
     51To 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.
    5252(Note, an unpark is like a V on a semaphore, so the subsequent park (P) may not block.)
    5353Finally, to further mitigate any underlying push/pop optimizations, especially on SMP machines, multiple rings are created in the experiment.
    54 
    55 To avoid this benchmark being affected by idle-sleep handling, the number of rings is multiple times greater than the number of \glspl{proc}.
    56 This design avoids the case where one of the \glspl{proc} runs out of work because of the variation on the number of ready \glspl{at} mentioned above.
    5754
    5855Figure~\ref{fig:cycle:code} shows the pseudo code for this benchmark.
     
    6461        count := 0
    6562        for {
     63                @this.next.wake()@
    6664                @wait()@
    67                 @this.next.wake()@
    6865                count ++
    6966                if must_stop() { break }
     
    103100                \label{fig:cycle:jax:low:ns}
    104101        }
    105         \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.}
     102        \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 extremums while the solid line is the medium.}
    106103        \label{fig:cycle:jax}
    107104\end{figure}
     
    125122                        \input{result.cycle.nasus.ns.pstex_t}
    126123                }
    127 
     124                \label{fig:cycle:nasus:ns}
    128125        }
    129126        \subfloat[][Scalability, 1 cycle per \proc]{
     
    133130                \label{fig:cycle:nasus:low:ns}
    134131        }
    135         \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.}
     132        \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 extremums while the solid line is the medium.}
    136133        \label{fig:cycle:nasus}
    137134\end{figure}
    138135Figure~\ref{fig:cycle:jax} and Figure~\ref{fig:cycle:nasus} shows the throughput as a function of \proc count on Intel and AMD respectively, where each cycle has 5 \ats.
    139136The graphs show traditional throughput on the top row and \newterm{scalability} on the bottom row.
    140 Where scalability uses the same data but the Y axis is calculated as throughput over the number of \procs.
     137Where scalability uses the same data but the Y axis is calculated as the number of \procs over the throughput.
    141138In 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.
    142139The left column shows results for 100 cycles per \proc, enough cycles to always keep every \proc busy.
     
    150147This effect is again repeated from 73 and 96 \procs, where it happens on the second CPU.
    151148When running only a single cycle, most runtime achieve lower throughput because of the idle-sleep mechanism.
    152 In Figure~\ref{fig:cycle:jax:ops} and \ref{fig:cycle:jax:ns}
    153149
    154150Figure~\ref{fig:cycle:nasus} show effectively the same story happening on AMD as it does on Intel.
     
    159155\section{Yield}
    160156For completion, the classic yield benchmark is included.
    161 This benchmark is simpler than the cycle test: it creates many \glspl{at} that call @yield@.
     157This benchmark is simpler than the cycle test: it creates many \ats that call @yield@.
    162158As mentioned, this benchmark may not be representative because of optimization shortcuts in @yield@.
    163 The only interesting variable in this benchmark is the number of \glspl{at} per \glspl{proc}, where ratios close to 1 means the ready queue(s) can be empty.
     159The only interesting variable in this benchmark is the number of \ats per \procs, where ratios close to 1 means the ready queue(s) can be empty.
    164160This scenario can put a strain on the idle-sleep handling compared to scenarios where there is plenty of work.
    165161Figure~\ref{fig:yield:code} shows pseudo code for this benchmark, where the @wait/next.wake@ is replaced by @yield@.
     
    208204                \label{fig:yield:jax:low:ns}
    209205        }
    210         \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.}
     206        \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 extremums while the solid line is the medium.}
    211207        \label{fig:yield:jax}
    212208\end{figure}
     
    230226                        \input{result.yield.nasus.ns.pstex_t}
    231227                }
    232 
     228                \label{fig:yield:nasus:ns}
    233229        }
    234230        \subfloat[][Scalability, 1 \at per \proc]{
     
    238234                \label{fig:yield:nasus:low:ns}
    239235        }
    240         \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.}
     236        \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 extremums while the solid line is the medium.}
    241237        \label{fig:yield:nasus}
    242238\end{figure}
    243 
    244 Figure~\ref{fig:yield:jax} shows the throughput as a function of \proc count, where each run uses 100 \ats per \proc.
     239Figure~\ref{fig:yield:jax} shows the throughput as a function of \proc count on Intel.
    245240It is fairly obvious why I claim this benchmark is more artificial.
    246241The throughput is dominated by the mechanism used to handle the @yield@.
     
    265260\section{Churn}
    266261The Cycle and Yield benchmark represent an \emph{easy} scenario for a scheduler, \eg an embarrassingly parallel application.
    267 In these benchmarks, \glspl{at} can be easily partitioned over the different \glspl{proc} upfront and none of the \glspl{at} communicate with each other.
    268 
    269 The Churn benchmark represents more chaotic execution, where there is no relation between the last \gls{proc} on which a \gls{at} ran and blocked and the \gls{proc} that subsequently unblocks it.
    270 With processor-specific ready-queues, when a \gls{at} is unblocked by a different \gls{proc} that means the unblocking \gls{proc} must either ``steal'' the \gls{at} from another processor or find it on a global queue.
    271 This dequeuing results in either contention on the remote queue and/or \glspl{rmr} on \gls{at} data structure.
    272 In either case, this benchmark aims to highlight how each scheduler handles these cases, since both cases can lead to performance degradation if not handled correctly.
     262In these benchmarks, \ats can be easily partitioned over the different \procs upfront and none of the \ats communicate with each other.
     263
     264The Churn benchmark represents more chaotic executions, where there is more communication among \ats but no relation between the last \proc on which a \at ran and blocked and the \proc that subsequently unblocks it.
     265With 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 global queue.
     266This dequeuing results in either contention on the remote queue and/or \glspl{rmr} on \at data structure.
     267In either case, this benchmark aims to measure how well each scheduler handles these cases, since both cases can lead to performance degradation if not handled correctly.
    273268
    274269This benchmark uses a fixed-size array of counting semaphores.
    275 Each \gls{at} picks a random semaphore, @V@s it to unblock any \at waiting, and then @P@s on the semaphore.
    276 This creates a flow where \glspl{at} push each other out of the semaphores before being pushed out themselves.
    277 For this benchmark to work, the number of \glspl{at} must be equal or greater than the number of semaphores plus the number of \glspl{proc}.
     270Each \at picks a random semaphore, @V@s it to unblock any \at waiting, and then @P@s on the semaphore.
     271This creates a flow where \ats push each other out of the semaphores before being pushed out themselves.
     272For this benchmark to work, the number of \ats must be equal or greater than the number of semaphores plus the number of \procs.
    278273Note, the nature of these semaphores mean the counter can go beyond 1, which can lead to nonblocking calls to @P@.
    279274Figure~\ref{fig:churn:code} shows pseudo code for this benchmark, where the @yield@ is replaced by @V@ and @P@.
     
    298293
    299294\subsection{Results}
    300 Figure~\ref{fig:churn:jax} shows the throughput as a function of \proc count, where each run uses 100 cycles per \proc and 5 \ats per cycle.
    301 
    302295\begin{figure}
    303296        \subfloat[][Throughput, 100 \ats per \proc]{
     
    318311                        \input{result.churn.jax.ns.pstex_t}
    319312                }
    320 
     313                \label{fig:churn:jax:ns}
    321314        }
    322315        \subfloat[][Latency, 1 \ats per \proc]{
     
    326319                \label{fig:churn:jax:low:ns}
    327320        }
    328         \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.
    329         Throughput is the total operation per second across all cores. Latency is the duration of each operation.}
     321        \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 extremums while the solid line is the medium.}
    330322        \label{fig:churn:jax}
    331323\end{figure}
    332324
    333 \todo{results discussion}
     325\begin{figure}
     326        \subfloat[][Throughput, 100 \ats per \proc]{
     327                \resizebox{0.5\linewidth}{!}{
     328                        \input{result.churn.nasus.ops.pstex_t}
     329                }
     330                \label{fig:churn:nasus:ops}
     331        }
     332        \subfloat[][Throughput, 1 \ats per \proc]{
     333                \resizebox{0.5\linewidth}{!}{
     334                        \input{result.churn.low.nasus.ops.pstex_t}
     335                }
     336                \label{fig:churn:nasus:low:ops}
     337        }
     338
     339        \subfloat[][Latency, 100 \ats per \proc]{
     340                \resizebox{0.5\linewidth}{!}{
     341                        \input{result.churn.nasus.ns.pstex_t}
     342                }
     343                \label{fig:churn:nasus:ns}
     344        }
     345        \subfloat[][Latency, 1 \ats per \proc]{
     346                \resizebox{0.5\linewidth}{!}{
     347                        \input{result.churn.low.nasus.ns.pstex_t}
     348                }
     349                \label{fig:churn:nasus:low:ns}
     350        }
     351        \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.
     352        For Throughput higher is better, for Scalability lower is better. Each series represent 15 independent runs, the dotted lines are extremums while the solid line is the medium.}
     353        \label{fig:churn:nasus}
     354\end{figure}
     355Figure~\ref{fig:churn:jax} shows the throughput as a function of \proc count on Intel.
     356Like for the cycle benchmark, here are runtimes achieve fairly similar performance.
     357Scalability is notably worst than the previous benchmarks since there is inherently more communication between processors.
     358Indeed, once the number of \glspl{hthrd} goes beyond a single socket, performance ceases to improve.
     359An interesting aspect to note here is that the runtimes differ in how they handle this situation.
     360Indeed, 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.
     361\CFA, tokio and Go all use the approach of unparking to the local \proc while Libfibre unparks to the remote \proc.
     362In this particular benchmark, the inherent chaos of the benchmark in addition to small memory footprint means neither approach wins over the other.
     363
     364Figure~\ref{fig:churn:nasus} shows effectively the same picture.
     365Performance improves as long as all \procs fit on a single socket.
     366Beyond that performance plateaus.
     367
     368Again this performance demonstrate \CFA achieves satisfactory performance.
    334369
    335370\section{Locality}
    336 
    337 \todo{code, setup, results}
     371\begin{figure}
     372\begin{cfa}
     373Thread.main() {
     374        count := 0
     375        for {
     376                r := random() % len(spots)
     377                // go through the array
     378                @work( a )@
     379                spots[r].V()
     380                spots[r].P()
     381                count ++
     382                if must_stop() { break }
     383        }
     384        global.count += count
     385}
     386\end{cfa}
     387\begin{cfa}
     388Thread.main() {
     389        count := 0
     390        for {
     391                r := random() % len(spots)
     392                // go through the array
     393                @work( a )@
     394                // pass array to next thread
     395                spots[r].V( @a@ )
     396                @a = @spots[r].P()
     397                count ++
     398                if must_stop() { break }
     399        }
     400        global.count += count
     401}
     402\end{cfa}
     403\caption[Locality Benchmark : Pseudo Code]{Locality Benchmark : Pseudo Code}
     404\label{fig:locality:code}
     405\end{figure}
     406As mentionned in the churn benchmark, when unparking a \at, it is possible to either unpark to the local or remote ready-queue.
     407\footnote{It is also possible to unpark to a third unrelated ready-queue, but unless the scheduler has additional knowledge about the situation, it is unlikely to result in good cache locality.}
     408The locality experiment includes two variations of the churn benchmark, where an array of data is added.
     409In both variations, before @V@ing the semaphore, each \at increment random cells inside the array.
     410The @share@ variation then passes the array to the shadow-queue of the semaphore, effectively transferring ownership of the array to the woken thread.
     411In the @noshare@ variation the array is not passed on and each thread continously accesses its private array.
     412
     413The objective here is to highlight the different decision made by the runtime when unparking.
     414Since each thread unparks a random semaphore, it means that it is unlikely that a \at will be unparked from the last \proc it ran on.
     415In the @share@ version, this means that unparking the \at on the local \proc is appropriate since the data was last modified on that \proc.
     416In the @noshare@ version, the reverse is true.
     417
     418The expectation for this benchmark is to see a performance inversion, where runtimes will fare notably better in the variation which matches their unparking policy.
     419This should lead to \CFA, Go and Tokio achieving better performance in @share@ while libfibre achieves better performance in @noshare@.
     420
     421\subsection{Results}
     422\begin{figure}
     423        \subfloat[][Throughput share]{
     424                \resizebox{0.5\linewidth}{!}{
     425                        \input{result.locality.share.jax.ops.pstex_t}
     426                }
     427                \label{fig:locality:jax:share:ops}
     428        }
     429        \subfloat[][Throughput noshare]{
     430                \resizebox{0.5\linewidth}{!}{
     431                        \input{result.locality.noshare.jax.ops.pstex_t}
     432                }
     433                \label{fig:locality:jax:noshare:ops}
     434        }
     435
     436        \subfloat[][Scalability share]{
     437                \resizebox{0.5\linewidth}{!}{
     438                        \input{result.locality.share.jax.ns.pstex_t}
     439                }
     440                \label{fig:locality:jax:share:ns}
     441        }
     442        \subfloat[][Scalability noshare]{
     443                \resizebox{0.5\linewidth}{!}{
     444                        \input{result.locality.noshare.jax.ns.pstex_t}
     445                }
     446                \label{fig:locality:jax:noshare:ns}
     447        }
     448        \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 dotted lines are extremums while the solid line is the medium.}
     449        \label{fig:locality:jax}
     450\end{figure}
     451\begin{figure}
     452        \subfloat[][Throughput share]{
     453                \resizebox{0.5\linewidth}{!}{
     454                        \input{result.locality.share.nasus.ops.pstex_t}
     455                }
     456                \label{fig:locality:nasus:share:ops}
     457        }
     458        \subfloat[][Throughput noshare]{
     459                \resizebox{0.5\linewidth}{!}{
     460                        \input{result.locality.noshare.nasus.ops.pstex_t}
     461                }
     462                \label{fig:locality:nasus:noshare:ops}
     463        }
     464
     465        \subfloat[][Scalability share]{
     466                \resizebox{0.5\linewidth}{!}{
     467                        \input{result.locality.share.nasus.ns.pstex_t}
     468                }
     469                \label{fig:locality:nasus:share:ns}
     470        }
     471        \subfloat[][Scalability noshare]{
     472                \resizebox{0.5\linewidth}{!}{
     473                        \input{result.locality.noshare.nasus.ns.pstex_t}
     474                }
     475                \label{fig:locality:nasus:noshare:ns}
     476        }
     477        \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 dotted lines are extremums while the solid line is the medium.}
     478        \label{fig:locality:nasus}
     479\end{figure}
     480
     481Figure~\ref{fig:locality:jax} shows that the results somewhat follow the expectation.
     482On the left of the figure showing the results for the shared variation, where \CFA and tokio outperform libfibre as expected.
     483And correspondingly on the right, we see the expected performance inversion where libfibre now outperforms \CFA and tokio.
     484Otherwise the results are similar to the churn benchmark, with lower throughtput due to the array processing.
     485It is unclear why Go's performance is notably worst than the other runtimes.
     486
     487Figure~\ref{fig:locality:nasus} shows the same experiment on AMD.
     488\todo{why is cfa slower?}
     489Again, we see the same story, where tokio and libfibre swap places and Go trails behind.
    338490
    339491\section{Transfer}
    340492The last benchmark is more of an experiment than a benchmark.
    341493It tests the behaviour of the schedulers for a misbehaved workload.
    342 In this workload, one of the \gls{at} is selected at random to be the leader.
    343 The leader then spins in a tight loop until it has observed that all other \glspl{at} have acknowledged its leadership.
    344 The leader \gls{at} then picks a new \gls{at} to be the ``spinner'' and the cycle repeats.
    345 The benchmark comes in two flavours for the non-leader \glspl{at}:
     494In this workload, one of the \at is selected at random to be the leader.
     495The leader then spins in a tight loop until it has observed that all other \ats have acknowledged its leadership.
     496The leader \at then picks a new \at to be the next leader and the cycle repeats.
     497The benchmark comes in two flavours for the non-leader \ats:
    346498once they acknowledged the leader, they either block on a semaphore or spin yielding.
    347499
    348500The experiment is designed to evaluate the short-term load-balancing of a scheduler.
    349 Indeed, schedulers where the runnable \glspl{at} are partitioned on the \glspl{proc} may need to balance the \glspl{at} for this experiment to terminate.
    350 This problem occurs because the spinning \gls{at} is effectively preventing the \gls{proc} from running any other \glspl{thrd}.
    351 In the semaphore flavour, the number of runnable \glspl{at} eventually dwindles down to only the leader.
    352 This scenario is a simpler case to handle for schedulers since \glspl{proc} eventually run out of work.
    353 In the yielding flavour, the number of runnable \glspl{at} stays constant.
     501Indeed, schedulers where the runnable \ats are partitioned on the \procs may need to balance the \ats for this experiment to terminate.
     502This problem occurs because the spinning \at is effectively preventing the \proc from running any other \at.
     503In the semaphore flavour, the number of runnable \ats eventually dwindles down to only the leader.
     504This scenario is a simpler case to handle for schedulers since \procs eventually run out of work.
     505In the yielding flavour, the number of runnable \ats stays constant.
    354506This scenario is a harder case to handle because corrective measures must be taken even when work is available.
    355507Note, runtime systems with preemption circumvent this problem by forcing the spinner to yield.
    356508
    357 \todo{code, setup, results}
     509I both flavours, the experiment effectively measures how long it takes for all \ats to run once after a given synchronization point.
     510In 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:
     511$ \frac{CSL + SL}{NP - 1}$, where $CSL$ is the context switch latency, $SL$ is the cost for enqueuing and dequeuing a \at and $NP$ is the number of \procs.
     512However, if the scheduler allows \ats to run many times before other \ats are able to run once, this delay will increase.
     513The semaphore version is an approximation of the strictly FIFO scheduling, where none of the \ats \emph{attempt} to run more than once.
     514The benchmark effectively provides the fairness guarantee in this case.
     515In the yielding version however, the benchmark provides no such guarantee, which means the scheduler has full responsability and any unfairness will be measurable.
     516
     517While this is a fairly artificial scenario, it requires only a few simple pieces.
     518The yielding version of this simply creates a scenario where a \at runs uninterrupted in a saturated system, and starvation has a easily measured impact.
     519However, \emph{any} \at that runs uninterrupted for a significant period of time in a saturated system could lead to this kind of starvation.
    358520
    359521\begin{figure}
     
    365527                return
    366528        }
    367 
    368529        // Wait for everyone to acknowledge my leadership
    369530        start: = timeNow()
     
    374535                }
    375536        }
    376 
    377537        // pick next leader
    378538        leader := threads[ prng() % len(threads) ]
    379 
    380539        // wake every one
    381540        if ! exhaust {
     
    385544        }
    386545}
    387 
    388546Thread.wait() {
    389547        this.idx_seen := lead_idx
     
    391549        else { yield() }
    392550}
    393 
    394551Thread.main() {
    395552        while !done  {
     
    404561
    405562\subsection{Results}
    406 Figure~\ref{fig:transfer:jax} shows the throughput as a function of \proc count, where each run uses 100 cycles per \proc and 5 \ats per cycle.
    407 
    408 \todo{results discussion}
     563\begin{figure}
     564\begin{centering}
     565\begin{tabular}{r | c c c c | c c c c }
     566Machine   &                     \multicolumn{4}{c |}{Intel}                &          \multicolumn{4}{c}{AMD}                    \\
     567Variation & \multicolumn{2}{c}{Park} & \multicolumn{2}{c |}{Yield} & \multicolumn{2}{c}{Park} & \multicolumn{2}{c}{Yield} \\
     568\procs    &      2      &      192   &      2      &      192      &      2      &      256   &      2      &      256    \\
     569\hline
     570\CFA      & 106 $\mu$s  & j200       & 68.4 $\mu$s & ~1.2 ms       & 174 $\mu$s  & ~28.4 ms   & 78.8~~$\mu$s& ~~1.21 ms   \\
     571libfibre  & 127 $\mu$s  &            & DNC         & DNC           & 156 $\mu$s  & ~36.7 ms   & DNC         & DNC         \\
     572Go        & 106 $\mu$s  & j200       & 24.6 ms     & 74.3 ms       & 271 $\mu$s  & 121.6 ms   & ~~1.21~ms   & 117.4 ms    \\
     573tokio     & 289 $\mu$s  &            & DNC         & DNC           & 157 $\mu$s  & 111.0 ms   & DNC         & DNC
     574\end{tabular}
     575\end{centering}
     576\caption[Transfer Benchmark on Intel and AMD]{Transfer Benchmark on Intel and AMD\smallskip\newline Average measurement of how long it takes for all \ats to acknowledge the leader \at. DNC stands for ``did not complete'', meaning that after 5 seconds of a new leader being decided, some \ats still had not acknowledged the new leader. }
     577\label{fig:transfer:res}
     578\end{figure}
     579Figure~\ref{fig:transfer:res} shows the result for the transfer benchmark with 2 \procs and all \procs, where each experiement runs 100 \at per \proc.
     580Note 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.
     581As such, data points that are the on the same order of magnitude as eachother should be basically considered equal.
     582The takeaway of this experiement is the presence of very large differences.
     583The semaphore variation is denoted ``Park'', where the number of \ats dwindles down as the new leader is acknowledged.
     584The yielding variation is denoted ``Yield''.
     585The experiement was only run for the extremums of the number of cores since the scaling per core behaves like previous experiements.
     586This experiments clearly demonstrate that while the other runtimes achieve similar performance, \CFA achieves significantly better fairness.
     587The semaphore variation serves as a control group, where all runtimes are expected to transfer leadership fairly quickly.
     588Since \ats block after acknowledging the leader, this experiment effectively measures how quickly \procs can steal \ats from the \proc running leader.
     589Figure~\ref{fig:transfer:res} shows that while Go and Tokio are slower, all runtime achieve decent latency.
     590However, the yielding variation shows an entirely different picture.
     591Since libfibre and tokio have a traditional work-stealing scheduler, \procs that have \ats on their local queues will never steal from other \procs.
     592The result is that the experiement simply does not complete for these runtime.
     593Without \procs stealing from the \proc running the leader, the experiment will simply never terminate.
     594Go manages to complete the experiement because it adds preemption on top of classic work-stealing.
     595However, since preemption is fairly costly it achieves significantly worst performance.
     596In contrast, \CFA achieves equivalent performance in both variations, demonstrating very good fairness.
     597Interestingly \CFA achieves better delays in the yielding version than the semaphore version, however, that is likely due to fairness being equivalent but removing the cost of the semaphores.
Note: See TracChangeset for help on using the changeset viewer.