source: doc/theses/thierry_delisle_PhD/thesis/text/eval_micro.tex @ bfd5512

ADTast-experimentalpthread-emulationqualifiedEnum
Last change on this file since bfd5512 was 6db62fa, checked in by Thierry Delisle <tdelisle@…>, 3 years ago

Added some experiments, some graph generation and a whole lot of text

  • Property mode set to 100644
File size: 9.7 KB
Line 
1\chapter{Micro-Benchmarks}\label{microbench}
2
3The first step of evaluation is always to test-out small controlled cases, to ensure that the basics are working properly.
4This sections presents five different experimental setup, evaluating some of the basic features of \CFA's scheduler.
5
6\section{Benchmark Environment}
7All of these benchmarks are run on two distinct hardware environment, an AMD and an INTEL machine.
8
9\paragraph{AMD} The AMD machine is a server with two AMD EPYC 7662 CPUs and 256GB of DDR4 RAM.
10The server runs Ubuntu 20.04.2 LTS on top of Linux Kernel 5.8.0-55.
11These EPYCs have 64 cores per CPUs and 2 \glspl{hthrd} per core, for a total of 256 \glspl{hthrd}.
12The cpus each have 4 MB, 64 MB and 512 MB of L1, L2 and L3 caches respectively.
13Each 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}.
14
15\paragraph{Intel} The Intel machine is a server with four Intel Xeon Platinum 8160 CPUs and 384GB of DDR4 RAM.
16The server runs Ubuntu 20.04.2 LTS on top of Linux Kernel 5.8.0-55.
17These Xeon Platinums have 24 cores per CPUs and 2 \glspl{hthrd} per core, for a total of 192 \glspl{hthrd}.
18The cpus each have 3 MB, 96 MB and 132 MB of L1, L2 and L3 caches respectively.
19Each L1 and L2 instance are only shared by \glspl{hthrd} on a given core, but each L3 instance is shared across the entire CPU, therefore 48 \glspl{hthrd}.
20
21This limited sharing of the last level cache on the AMD machine is markedly different than the Intel machine. Indeed, while on both architectures L2 cache misses that are served by L3 caches on a different cpu incurr a significant latency, on AMD it is also the case that cache misses served by a different L3 instance on the same cpu still incur high latency.
22
23
24\section{Cycling latency}
25The most basic evaluation of any ready queue is to evaluate the latency needed to push and pop one element from the ready-queue.
26Since these two operation also describe a \texttt{yield} operation, many systems use this as the most basic benchmark.
27However, 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.
28Not all systems use this information, but those which do may appear to have better performance than they would for disconnected push/pop pairs.
29For this reason, I chose a different first benchmark, which I call the Cycle Benchmark.
30This benchmark arranges many \glspl{at} into multiple rings of \glspl{at}.
31Each ring is effectively a circular singly-linked list.
32At runtime, each \gls{at} unparks the next \gls{at} before parking itself.
33This corresponds to the desired pair of ready queue operations.
34Unparking 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.
35Figure~\ref{fig:cycle} shows a visual representation of this arrangement.
36
37The 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.
38In 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.
39The 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.
40While this would not be a correctness problem, every runtime system must handle that race, it could lead to pushes and pops being optimized away.
41Since 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.
42Note that this problem is only present on SMP machines and is significantly mitigated by the fact that there are multiple rings in the system.
43
44\begin{figure}
45        \centering
46        \input{cycle.pstex_t}
47        \caption[Cycle benchmark]{Cycle benchmark\smallskip\newline Each \gls{at} unparks the next \gls{at} in the cycle before parking itself.}
48        \label{fig:cycle}
49\end{figure}
50
51To 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.
52Beyond this point, adding more rings serves to mitigate even more the idle sleep handling.
53This is to avoid the case where one of the \glspl{proc} runs out of work because of the variation on the number of ready \glspl{at} mentionned above.
54
55The 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.
56
57\begin{lstlisting}
58        Thread.main() {
59                count := 0
60                for {
61                        wait()
62                        this.next.wake()
63                        count ++
64                        if must_stop() { break }
65                }
66                global.count += count
67        }
68\end{lstlisting}
69
70\begin{figure}
71        \centering
72        \input{result.cycle.jax.ops.pstex_t}
73        \vspace*{-10pt}
74        \label{fig:cycle:ns:jax}
75\end{figure}
76
77\section{Yield}
78For completion, I also include the yield benchmark.
79This benchmark is much simpler than the cycle tests, it simply creates many \glspl{at} that call \texttt{yield}.
80As 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.
81Its 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.
82This sometimes puts more strain on the idle sleep handling, compared to scenarios where there is clearly plenty of work to be done.
83
84\todo{code, setup, results}
85
86\begin{lstlisting}
87        Thread.main() {
88                count := 0
89                while !stop {
90                        yield()
91                        count ++
92                }
93                global.count += count
94        }
95\end{lstlisting}
96
97
98\section{Churn}
99The Cycle and Yield benchmark represents an ``easy'' scenario for a scheduler, \eg, an embarrassingly parallel application.
100In 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.
101
102The 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.
103When 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.
104This results can result in either contention on the remote queue or \glspl{rmr} on \gls{at} data structure.
105In 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.
106
107To 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}.
108When a \gls{at} attempts to block on the chair, it must first unblocked the \gls{at} currently blocked on said chair, if any.
109This creates a flow where \glspl{at} push each other out of the chairs before being pushed out themselves.
110For 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}.
111
112\todo{code, setup, results}
113\begin{lstlisting}
114        Thread.main() {
115                count := 0
116                for {
117                        r := random() % len(spots)
118                        next := xchg(spots[r], this)
119                        if next { next.wake() }
120                        wait()
121                        count ++
122                        if must_stop() { break }
123                }
124                global.count += count
125        }
126\end{lstlisting}
127
128\section{Locality}
129
130\todo{code, setup, results}
131
132\section{Transfer}
133The last benchmark is more exactly characterize as an experiment than a benchmark.
134It tests the behavior of the schedulers for a particularly misbehaved workload.
135In this workload, one of the \gls{at} is selected at random to be the leader.
136The leader then spins in a tight loop until it has observed that all other \glspl{at} have acknowledged its leadership.
137The leader \gls{at} then picks a new \gls{at} to be the ``spinner'' and the cycle repeats.
138
139The benchmark comes in two flavours for the behavior of the non-leader \glspl{at}:
140once they acknowledged the leader, they either block on a semaphore or yield repeatadly.
141
142This experiment is designed to evaluate the short term load balancing of the scheduler.
143Indeed, schedulers where the runnable \glspl{at} are partitioned on the \glspl{proc} may need to balance the \glspl{at} for this experient to terminate.
144This is because the spinning \gls{at} is effectively preventing the \gls{proc} from runnning any other \glspl{thrd}.
145In the semaphore flavour, the number of runnable \glspl{at} will eventually dwindle down to only the leader.
146This is a simpler case to handle for schedulers since \glspl{proc} eventually run out of work.
147In the yielding flavour, the number of runnable \glspl{at} stays constant.
148This is a harder case to handle because corrective measures must be taken even if work is still available.
149Note that languages that have mandatory preemption do circumvent this problem by forcing the spinner to yield.
150
151\todo{code, setup, results}
152\begin{lstlisting}
153        Thread.lead() {
154                this.idx_seen = ++lead_idx
155                if lead_idx > stop_idx {
156                        done := true
157                        return
158                }
159
160                // Wait for everyone to acknowledge my leadership
161                start: = timeNow()
162                for t in threads {
163                        while t.idx_seen != lead_idx {
164                                asm pause
165                                if (timeNow() - start) > 5 seconds { error() }
166                        }
167                }
168
169                // pick next leader
170                leader := threads[ prng() % len(threads) ]
171
172                // wake every one
173                if !exhaust {
174                        for t in threads {
175                                if t != me { t.wake() }
176                        }
177                }
178        }
179
180        Thread.wait() {
181                this.idx_seen := lead_idx
182                if exhaust { wait() }
183                else { yield() }
184        }
185
186        Thread.main() {
187                while !done  {
188                        if leader == me { this.lead() }
189                        else { this.wait() }
190                }
191        }
192\end{lstlisting}
Note: See TracBrowser for help on using the repository browser.