\chapter{Micro-Benchmarks}\label{microbench}

The first step of evaluation is always to test-out small controlled cases, to ensure that the basics are working properly.
This sections presents five different experimental setup, evaluating some of the basic features of \CFA's scheduler.

\section{Benchmark Environment}
All of these benchmarks are run on two distinct hardware environment, an AMD and an INTEL machine.

For all benchmarks, \texttt{taskset} is used to limit the experiment to 1 NUMA Node with no hyper threading.
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.


\paragraph{AMD} The AMD machine is a server with two AMD EPYC 7662 CPUs and 256GB of DDR4 RAM.
The server runs Ubuntu 20.04.2 LTS on top of Linux Kernel 5.8.0-55.
These EPYCs have 64 cores per CPUs and 2 \glspl{hthrd} per core, for a total of 256 \glspl{hthrd}.
The cpus each have 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}.

\paragraph{Intel} The Intel machine is a server with four Intel Xeon Platinum 8160 CPUs and 384GB of DDR4 RAM.
The server runs Ubuntu 20.04.2 LTS on top of Linux Kernel 5.8.0-55.
These Xeon Platinums have 24 cores per CPUs and 2 \glspl{hthrd} per core, for a total of 192 \glspl{hthrd}.
The cpus each have 3 MB, 96 MB and 132 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 across the entire CPU, therefore 48 \glspl{hthrd}.

This 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.


\section{Cycling latency}
\begin{figure}
	\centering
	\input{cycle.pstex_t}
	\caption[Cycle benchmark]{Cycle benchmark\smallskip\newline Each \gls{at} unparks the next \gls{at} in the cycle before parking itself.}
	\label{fig:cycle}
\end{figure}
The most basic evaluation of any ready queue is to evaluate the latency needed to push and pop one element from the ready-queue.
Since these two operation also describe a \texttt{yield} operation, many systems use this as the most basic benchmark.
However, 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.
Not all systems use this information, but those which do may appear to have better performance than they would for disconnected push/pop pairs.
For this reason, I chose a different first benchmark, which I call the Cycle Benchmark.
This benchmark arranges many \glspl{at} into multiple rings of \glspl{at}.
Each ring is effectively a circular singly-linked list.
At runtime, each \gls{at} unparks the next \gls{at} before parking itself.
This corresponds to the desired pair of ready queue operations.
Unparking 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.
Figure~\ref{fig:cycle} shows a visual representation of this arrangement.

The 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.
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.
The 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.
While this would not be a correctness problem, every runtime system must handle that race, it could lead to pushes and pops being optimized away.
Since 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.
Note that this problem is only present on SMP machines and is significantly mitigated by the fact that there are multiple rings in the system.

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 \glspl{proc} available.
Beyond this point, adding more rings serves to mitigate even more the idle sleep handling.
This 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.

The 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.
Figure~\ref{fig:cycle:code} shows pseudo code for this benchmark.

\begin{figure}
	\begin{lstlisting}
		Thread.main() {
			count := 0
			for {
				wait()
				this.next.wake()
				count ++
				if must_stop() { break }
			}
			global.count += count
		}
	\end{lstlisting}
	\caption[Cycle Benchmark : Pseudo Code]{Cycle Benchmark : Pseudo Code}
	\label{fig:cycle:code}
\end{figure}



\subsection{Results}
\begin{figure}
	\subfloat[][Throughput, 100 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.cycle.jax.ops.pstex_t}
		}
		\label{fig:cycle:jax:ops}
	}
	\subfloat[][Throughput, 1 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.cycle.low.jax.ops.pstex_t}
		}
		\label{fig:cycle:jax:low:ops}
	}

	\subfloat[][Latency, 100 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.cycle.jax.ns.pstex_t}
		}

	}
	\subfloat[][Latency, 1 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.cycle.low.jax.ns.pstex_t}
		}
		\label{fig:cycle:jax:low:ns}
	}
	\caption[Cycle Benchmark on Intel]{Cycle Benchmark on Intel\smallskip\newline Throughput as a function of \proc count, using 100 cycles per \proc, 5 \ats per cycle.}
	\label{fig:cycle:jax}
\end{figure}
Figure~\ref{fig:cycle:jax} shows the throughput as a function of \proc count, with the following constants:
Each run uses 100 cycles per \proc, 5 \ats per cycle.

\todo{results discussion}

\section{Yield}
For completion, I also include the yield benchmark.
This benchmark is much simpler than the cycle tests, it simply creates many \glspl{at} that call \texttt{yield}.
As 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.
Its 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.
This sometimes puts more strain on the idle sleep handling, compared to scenarios where there is clearly plenty of work to be done.
Figure~\ref{fig:yield:code} shows pseudo code for this benchmark, the ``wait/wake-next'' is simply replaced by a yield.

\begin{figure}
	\begin{lstlisting}
		Thread.main() {
			count := 0
			for {
				yield()
				count ++
				if must_stop() { break }
			}
			global.count += count
		}
	\end{lstlisting}
	\caption[Yield Benchmark : Pseudo Code]{Yield Benchmark : Pseudo Code}
	\label{fig:yield:code}
\end{figure}

\subsection{Results}
\begin{figure}
	\subfloat[][Throughput, 100 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.yield.jax.ops.pstex_t}
		}
		\label{fig:yield:jax:ops}
	}
	\subfloat[][Throughput, 1 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
		\input{result.yield.low.jax.ops.pstex_t}
		}
		\label{fig:yield:jax:low:ops}
	}

	\subfloat[][Latency, 100 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
		\input{result.yield.jax.ns.pstex_t}
		}
		\label{fig:yield:jax:ns}
	}
	\subfloat[][Latency, 1 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
		\input{result.yield.low.jax.ns.pstex_t}
		}
		\label{fig:yield:jax:low:ns}
	}
	\caption[Yield Benchmark on Intel]{Yield Benchmark on Intel\smallskip\newline Throughput as a function of \proc count, using 1 \ats per \proc.}
	\label{fig:yield:jax}
\end{figure}
Figure~\ref{fig:yield:ops:jax} shows the throughput as a function of \proc count, with the following constants:
Each run uses 100 \ats per \proc.

\todo{results discussion}


\section{Churn}
The Cycle and Yield benchmark represents an ``easy'' scenario for a scheduler, \eg, an embarrassingly parallel application.
In 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.

The 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.
When 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.
This results can result in either contention on the remote queue or \glspl{rmr} on \gls{at} data structure.
In 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.

To achieve this the benchmark uses a fixed size array of semaphores.
Each \gls{at} picks a random semaphore, \texttt{V}s it to unblock a \at waiting and then \texttt{P}s on the semaphore.
This creates a flow where \glspl{at} push each other out of the semaphores before being pushed out themselves.
For this benchmark to work however, the number of \glspl{at} must be equal or greater to the number of semaphores plus the number of \glspl{proc}.
Note that the nature of these semaphores mean the counter can go beyond 1, which could lead to calls to \texttt{P} not blocking.

\todo{code, setup, results}
\begin{lstlisting}
	Thread.main() {
		count := 0
		for {
			r := random() % len(spots)
			spots[r].V()
			spots[r].P()
			count ++
			if must_stop() { break }
		}
		global.count += count
	}
\end{lstlisting}

\begin{figure}
	\subfloat[][Throughput, 100 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.churn.jax.ops.pstex_t}
		}
		\label{fig:churn:jax:ops}
	}
	\subfloat[][Throughput, 1 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.churn.low.jax.ops.pstex_t}
		}
		\label{fig:churn:jax:low:ops}
	}

	\subfloat[][Latency, 100 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.churn.jax.ns.pstex_t}
		}

	}
	\subfloat[][Latency, 1 \ats per \proc]{
		\resizebox{0.5\linewidth}{!}{
			\input{result.churn.low.jax.ns.pstex_t}
		}
		\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. Throughput is the total operation per second across all cores. Latency is the duration of each opeartion.}
	\label{fig:churn:jax}
\end{figure}

\section{Locality}

\todo{code, setup, results}

\section{Transfer}
The last benchmark is more exactly characterize as an experiment than a benchmark.
It tests the behavior of the schedulers for a particularly misbehaved workload.
In this workload, one of the \gls{at} is selected at random to be the leader.
The leader then spins in a tight loop until it has observed that all other \glspl{at} have acknowledged its leadership.
The leader \gls{at} then picks a new \gls{at} to be the ``spinner'' and the cycle repeats.

The benchmark comes in two flavours for the behavior of the non-leader \glspl{at}:
once they acknowledged the leader, they either block on a semaphore or yield repeatadly.

This experiment is designed to evaluate the short term load balancing of the scheduler.
Indeed, schedulers where the runnable \glspl{at} are partitioned on the \glspl{proc} may need to balance the \glspl{at} for this experient to terminate.
This is because the spinning \gls{at} is effectively preventing the \gls{proc} from runnning any other \glspl{thrd}.
In the semaphore flavour, the number of runnable \glspl{at} will eventually dwindle down to only the leader.
This is a simpler case to handle for schedulers since \glspl{proc} eventually run out of work.
In the yielding flavour, the number of runnable \glspl{at} stays constant.
This is a harder case to handle because corrective measures must be taken even if work is still available.
Note that languages that have mandatory preemption do circumvent this problem by forcing the spinner to yield.

\todo{code, setup, results}
\begin{lstlisting}
	Thread.lead() {
		this.idx_seen = ++lead_idx
		if lead_idx > stop_idx {
			done := true
			return
		}

		// Wait for everyone to acknowledge my leadership
		start: = timeNow()
		for t in threads {
			while t.idx_seen != lead_idx {
				asm pause
				if (timeNow() - start) > 5 seconds { error() }
			}
		}

		// pick next leader
		leader := threads[ prng() % len(threads) ]

		// wake every one
		if !exhaust {
			for t in threads {
				if t != me { t.wake() }
			}
		}
	}

	Thread.wait() {
		this.idx_seen := lead_idx
		if exhaust { wait() }
		else { yield() }
	}

	Thread.main() {
		while !done  {
			if leader == me { this.lead() }
			else { this.wait() }
		}
	}
\end{lstlisting}