Ignore:
Timestamp:
Feb 1, 2022, 7:42:31 PM (8 months ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
enum, forall-pointer-decay, master, pthread-emulation, qualifiedEnum
Children:
3b0bc16
Parents:
ab1a9ea
Message:

Re-starting work on my thesis.

File:
1 edited

Legend:

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

    rab1a9ea r729c991  
    22
    33The first step of evaluation is always to test-out small controlled cases, to ensure that the basics are working properly.
    4 This sections presents four different experimental setup, evaluating some of the basic features of \CFA's scheduler.
     4This sections presents five different experimental setup, evaluating some of the basic features of \CFA's scheduler.
    55
    66\section{Cycling latency}
    77The most basic evaluation of any ready queue is to evaluate the latency needed to push and pop one element from the ready-queue.
    8 While these two operation also describe a \texttt{yield} operation, many systems use this as the most basic benchmark.
    9 However, yielding can be treated as a special case, since it also carries the information that the length of the ready queue will not change.
     8Since these two operation also describe a \texttt{yield} operation, many systems use this as the most basic benchmark.
     9However, yielding can be treated as a special case, since it also carries the information that the number of the ready \glspl{at} will not change.
    1010Not all systems use this information, but those which do may appear to have better performance than they would for disconnected push/pop pairs.
    1111For this reason, I chose a different first benchmark, which I call the Cycle Benchmark.
    12 This benchmark arranges many threads into multiple rings of threads.
     12This benchmark arranges many \glspl{at} into multiple rings of \glspl{at}.
    1313Each ring is effectively a circular singly-linked list.
    14 At runtime, each thread unparks the next thread before parking itself.
     14At runtime, each \gls{at} unparks the next \gls{at} before parking itself.
    1515This corresponds to the desired pair of ready queue operations.
    16 Unparking the next thread requires pushing that thread onto the ready queue and the ensuing park will cause the runtime to pop a thread from the ready-queue.
     16Unparking the next \gls{at} requires pushing that \gls{at} onto the ready queue and the ensuing park will cause the runtime to pop a \gls{at} from the ready-queue.
    1717Figure~\ref{fig:cycle} shows a visual representation of this arrangement.
    1818
    19 The goal of this ring is that the underlying runtime cannot rely on the guarantee that the number of ready threads will stay constant over the duration of the experiment.
    20 In fact, the total number of threads waiting on the ready is expected to vary a little because of the race between the next thread unparking and the current thread parking.
    21 The size of the cycle is also decided based on this race: cycles that are too small may see the
    22 chain of unparks go full circle before the first thread can park.
     19The goal of this ring is that the underlying runtime cannot rely on the guarantee that the number of ready \glspl{at} will stay constant over the duration of the experiment.
     20In 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.
     21The size of the cycle is also decided based on this race: cycles that are too small may see the chain of unparks go full circle before the first \gls{at} can park.
    2322While this would not be a correctness problem, every runtime system must handle that race, it could lead to pushes and pops being optimized away.
    24 Since silently omitting ready-queue operations would throw off the measuring of these operations.
    25 Therefore the ring of threads must be big enough so the threads have the time to fully park before they are unparked.
     23Since silently omitting ready-queue operations would throw off the measuring of these operations, the ring of \glspl{at} must be big enough so the \glspl{at} have the time to fully park before they are unparked.
    2624Note that this problem is only present on SMP machines and is significantly mitigated by the fact that there are multiple rings in the system.
    2725
     
    2927        \centering
    3028        \input{cycle.pstex_t}
    31         \caption[Cycle benchmark]{Cycle benchmark\smallskip\newline Each thread unparks the next thread in the cycle before parking itself.}
     29        \caption[Cycle benchmark]{Cycle benchmark\smallskip\newline Each \gls{at} unparks the next \gls{at} in the cycle before parking itself.}
    3230        \label{fig:cycle}
    3331\end{figure}
    3432
    3533\todo{check term ``idle sleep handling''}
    36 To avoid this benchmark from being dominated by the idle sleep handling, the number of rings is kept at least as high as the number of processors available.
     34To avoid this benchmark from being dominated by the idle sleep handling, the number of rings is kept at least as high as the number of \glspl{proc} available.
    3735Beyond this point, adding more rings serves to mitigate even more the idle sleep handling.
    38 This is to avoid the case where one of the worker threads runs out of work because of the variation on the number of ready threads mentionned above.
     36This is to avoid the case where one of the worker \glspl{at} runs out of work because of the variation on the number of ready \glspl{at} mentionned above.
    3937
    4038The actual benchmark is more complicated to handle termination, but that simply requires using a binary semphore or a channel instead of raw \texttt{park}/\texttt{unpark} and carefully picking the order of the \texttt{P} and \texttt{V} with respect to the loop condition.
    4139
    42 \todo{mention where to get the code.}
     40\todo{code, setup, results}
     41\begin{lstlisting}
     42        Thread.main() {
     43                count := 0
     44                for {
     45                        wait()
     46                        this.next.wake()
     47                        count ++
     48                        if must_stop() { break }
     49                }
     50                global.count += count
     51        }
     52\end{lstlisting}
     53
    4354
    4455\section{Yield}
    4556For completion, I also include the yield benchmark.
    46 This benchmark is much simpler than the cycle tests, it simply creates many threads that call \texttt{yield}.
     57This benchmark is much simpler than the cycle tests, it simply creates many \glspl{at} that call \texttt{yield}.
     58As mentionned in the previous section, this benchmark may be less representative of usages that only make limited use of \texttt{yield}, due to potential shortcuts in the routine.
     59Its only interesting variable is the number of \glspl{at} per \glspl{proc}, where ratios close to 1 means the ready queue(s) could be empty.
     60This sometimes puts more strain on the idle sleep handling, compared to scenarios where there is clearly plenty of work to be done.
     61
     62\todo{code, setup, results}
     63
     64\begin{lstlisting}
     65        Thread.main() {
     66                count := 0
     67                while !stop {
     68                        yield()
     69                        count ++
     70                }
     71                global.count += count
     72        }
     73\end{lstlisting}
     74
     75
     76\section{Churn}
     77The Cycle and Yield benchmark represents an ``easy'' scenario for a scheduler, \eg, an embarrassingly parallel application.
     78In these benchmarks, \glspl{at} can be easily partitioned over the different \glspl{proc} up-front and none of the \glspl{at} communicate with each other.
     79
     80The Churn benchmark represents more chaotic usages, where there is no relation between the last \gls{proc} on which a \gls{at} ran and the \gls{proc} that unblocked it.
     81When a \gls{at} is unblocked from a different \gls{proc} than the one on which it last ran, the unblocking \gls{proc} must either ``steal'' the \gls{at} or place it on a remote queue.
     82This results can result in either contention on the remote queue or \glspl{rmr} on \gls{at} data structure.
     83In either case, this benchmark aims to highlight how each scheduler handles these cases, since both cases can lead to performance degradation if they are not handled correctly.
     84
     85To achieve this the benchmark uses a fixed size array of \newterm{chair}s, where a chair is a data structure that holds a single blocked \gls{at}.
     86When a \gls{at} attempts to block on the chair, it must first unblocked the \gls{at} currently blocked on said chair, if any.
     87This creates a flow where \glspl{at} push each other out of the chairs before being pushed out themselves.
     88For this benchmark to work however, the number of \glspl{at} must be equal or greater to the number of chairs plus the number of \glspl{proc}.
     89
     90\todo{code, setup, results}
     91\begin{lstlisting}
     92        Thread.main() {
     93                count := 0
     94                for {
     95                        r := random() % len(spots)
     96                        next := xchg(spots[r], this)
     97                        if next { next.wake() }
     98                        wait()
     99                        count ++
     100                        if must_stop() { break }
     101                }
     102                global.count += count
     103        }
     104\end{lstlisting}
    47105
    48106\section{Locality}
    49107
     108\todo{code, setup, results}
     109
    50110\section{Transfer}
     111The last benchmark is more exactly characterize as an experiment than a benchmark.
     112It tests the behavior of the schedulers for a particularly misbehaved workload.
     113In this workload, one of the \gls{at} is selected at random to be the leader.
     114The leader then spins in a tight loop until it has observed that all other \glspl{at} have acknowledged its leadership.
     115The leader \gls{at} then picks a new \gls{at} to be the ``spinner'' and the cycle repeats.
     116
     117The benchmark comes in two flavours for the behavior of the non-leader \glspl{at}:
     118once they acknowledged the leader, they either block on a semaphore or yield repeatadly.
     119
     120This experiment is designed to evaluate the short term load balancing of the scheduler.
     121Indeed, schedulers where the runnable \glspl{at} are partitioned on the \glspl{proc} may need to balance the \glspl{at} for this experient to terminate.
     122This is because the spinning \gls{at} is effectively preventing the \gls{proc} from runnning any other \glspl{thrd}.
     123In the semaphore flavour, the number of runnable \glspl{at} will eventually dwindle down to only the leader.
     124This is a simpler case to handle for schedulers since \glspl{proc} eventually run out of work.
     125In the yielding flavour, the number of runnable \glspl{at} stays constant.
     126This is a harder case to handle because corrective measures must be taken even if work is still available.
     127Note that languages that have mandatory preemption do circumvent this problem by forcing the spinner to yield.
     128
     129\todo{code, setup, results}
     130\begin{lstlisting}
     131        Thread.lead() {
     132                this.idx_seen = ++lead_idx
     133                if lead_idx > stop_idx {
     134                        done := true
     135                        return
     136                }
     137
     138                // Wait for everyone to acknowledge my leadership
     139                start: = timeNow()
     140                for t in threads {
     141                        while t.idx_seen != lead_idx {
     142                                asm pause
     143                                if (timeNow() - start) > 5 seconds { error() }
     144                        }
     145                }
     146
     147                // pick next leader
     148                leader := threads[ prng() % len(threads) ]
     149
     150                // wake every one
     151                if !exhaust {
     152                        for t in threads {
     153                                if t != me { t.wake() }
     154                        }
     155                }
     156        }
     157
     158        Thread.wait() {
     159                this.idx_seen := lead_idx
     160                if exhaust { wait() }
     161                else { yield() }
     162        }
     163
     164        Thread.main() {
     165                while !done  {
     166                        if leader == me { this.lead() }
     167                        else { this.wait() }
     168                }
     169        }
     170\end{lstlisting}
Note: See TracChangeset for help on using the changeset viewer.