Context Navigation

-                      re0069bd
+                      rd6d2136
 The longest-victim heuristic maintains a timestamp per executor thread that is updated every time a worker attempts to steal work.
 The timestamps are generated using @rdtsc@~\cite{IntelManual} and are stored in a shared array, with one index per worker.
+Thieves then attempt to steal from the worker with the oldest timestamp.
+\PAB{How does a thief find the oldest timestamp?}
+Thieves then attempt to steal from the worker with the oldest timestamp, which is found by performing a linear search across the array of timestamps.
 The intuition behind this heuristic is that the slowest worker receives help via work stealing until it becomes a thief, which indicates that it has caught up to the pace of the rest of the workers.
 This heuristic should ideally result in lowered latency for message sends to victim workers that are overloaded with work.
 …
 Finally, \CFA runs consistently on both of the AMD and Intel, and is faster than \uC on the AMD, but slightly slower on the Intel.
 This benchmark is a pathological case for work stealing actor systems, as the majority of work is being performed by the single actor conducting the scatter/gather.
 The impact of work stealing on this benchmark are discussed further in Section~\ref{s:steal_perf}.
+The impact of work stealing on this benchmark is discussed further in Section~\ref{s:steal_perf}.
 Here, gains from using the copy queue are much less apparent, due to the costs of stealing.
 …
 Two pathological unbalanced cases are created, and compared using vanilla and randomized work stealing in \CFA.
 These benchmarks adversarially takes advantage of the round-robin assignment of actors to workers by isolating the receive and send actors on different cores.
+These benchmarks adversarially takes advantage of the round-robin assignment of actors to workers to load actors only on specific cores (there is one worker per core).
 The workload on the loaded cores is the same as the executor benchmark described in \ref{s:executorPerf}, but with fewer rounds.
 …
 On Intel in Figure~\ref{f:BalanceOneIntel}, above 32 cores the performance gets worse for all variants due to hyperthreading.
 Here, the longest-victim and random heuristic are the same.
 Note, the non-stealing variation of balance-one slows down (no decrease in graph) as the cores increase \PAB{not sure I understand this part: due to having to create more dummy actors on the inactive cores during startup}.
+Note, the non-stealing variation of balance-one slows down slightly (no decrease in graph) as the cores increase, since a few "dummy" actors need to be made for each of the extra cores beyond the first to adversarially layout all loaded actors on the first core.
 For the balance-multi benchmark in Figures~\ref{f:BalanceMultiAMD} and~\ref{f:BalanceMultiIntel}, the random heuristic outperforms the longest victim.
 …
 \end{figure}
-\PAB{Something is wrong here because there are no graphs containing all the benchmarks.
 Figures~\ref{f:cfaRepeatAMD} and~\ref{f:cfaRepeatIntel} show the effects of the stealing heuristics for the repeat benchmark.
-% Here, the no-stealing version of \CFA performs better than both stealing variations.
 As mentioned, the repeat benchmark is a pathological case for work stealing systems since there is one actor with the majority of the work, and not enough other work to go around.
 The worst-case scenario is if the actor doing the majority of work or its mail queue is stolen by the work stealing system, as this a huge cost to move the work and refill the local cache.
+The worst-case scenario is if the actor doing the majority of work or its mail queue is stolen by the work stealing system, as this incurs a huge cost to move the work and refill the local cache.
 This worst-case steal is likely to happen since there is little other work in the system between scatter/gather rounds.
+In particular on the Intel machine in Figure~\ref{f:cfaRepeatIntel}, the cost of stealing is higher, which can be seen in the vertical shift of Akka, CAF and \CFA results in Figure~\ref{f:RepeatIntel} (\uC and ProtoActor do not have work stealing).
+The shift for CAF is particularly large, which further supports the hypothesis that CAF's work stealing is particularly eager.
+All \CFA variants are comparable in performance on the repeat benchmark.
+This is surprising, since this is a pathological case for work stealing, and one would expect the No-Stealing variant to have better performance.
+It is likely that the \CFA No-Stealing variant may be minorly impacted by other design decisions in the \CFA actor system that were made with work stealing in mind.
+Work stealing performance in the repeat benchmark can be further examined by discussing Figures \ref{f:RepeatAMD} and \ref{f:RepeatIntel}.
+In particular, on the Intel machine in Figure~\ref{f:RepeatIntel}, the cost of stealing is higher, which can be seen in the vertical shift of Akka, CAF and \CFA when comparing the AMD results in Figure~\ref{f:RepeatAMD} results in Figure~\ref{f:RepeatIntel} (\uC and ProtoActor do not have work stealing).
+The shift for CAF is particularly large, which supports the hypothesis that CAF's work stealing is particularly eager.
 In both the executor and the repeat benchmark CAF performs poorly.
 It is hypothesized that CAF has an aggressive work stealing algorithm, that eagerly attempts to steal.
 This results in poor performance in benchmarks with small messages containing little work per message.
+On the other hand, in \ref{f:MatrixAMD} CAF performs much better since each message has a large amount of work, and few messages are sent, so the eager work stealing allows for the clean up of loose ends to occur faster.
+In comparison with the other systems \uC does well on the repeat benchmark since it does not have work stealing.
+The client of this experiment is long running and maintains a lot of state, as it needs to know the handles of all the servers.
+When stealing the client or its respective queue (in \CFA's inverted model), moving the client incurs a high cost due to cache invalidation.
+As such stealing the client can result in a hit in performance.
+Finally, Figures~\ref{f:cfaMatrixAMD} and~\ref{f:cfaMatrixIntel} show the effects of the stealing heuristics for the matrix-multiply benchmark.
+Here, there is negligible performance difference across stealing heuristics, likely due to the long running workload of each message.
+Stealing can still improve performance marginally in the matrix-multiply benchmark.
+In \ref{f:MatrixAMD} CAF performs much better; few messages are sent, so the eager work stealing allows for the clean up of loose ends to occur faster.
 This hypothesis stems from experimentation with \CFA.
 CAF uses a randomized work stealing heuristic.
 Tuning the \CFA actor system to steal work much more eagerly with randomized victim selection heuristics provided similar results to what CAF achieved in the matrix benchmark.
+This experimental tuning performed much worse on all other microbenchmarks that we present, since they all perform a small amount of work per message.
+In comparison with the other systems \uC does well on the repeat benchmark since it does not have work stealing.
+The client of this experiment is long running and maintains a lot of state, as it needs to know the handles of all the servers.
+When stealing the client or its respective queue (in \CFA's inverted model), moving the client incurs a high cost due to cache invalidation.
+As such stealing the client can result in a hit in performance.}
+Finally, Figures~\ref{f:cfaMatrixAMD} and~\ref{f:cfaMatrixIntel} show the effects of the stealing heuristics for the matrix-multiple benchmark.
+Here, there is negligible performance difference across stealing heuristics.
+This experimental tuning performed much worse on all other microbenchmarks that we present, since they all perform a small amount of work per message, which may partially explain CAF's poor performance on other benchmarks.
 \begin{figure}

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset d6d2136 for doc/theses/colby_parsons_MMAth

Legend:

doc/theses/colby_parsons_MMAth/text/actors.tex

Download in other formats: