Changeset ea1bb94 for doc/theses/colby_parsons_MMAth

Timestamp:

Jul 11, 2023, 9:25:01 AM (11 months ago)

Author:

caparsons <caparson@…>

Branches:

master

Children:

39e6309

Parents:

614868b

Message:

actor perf cleanup following reordering

Location:

doc/theses/colby_parsons_MMAth

Files:

• local.bib (modified) (1 diff)
• text/actors.tex (modified) (7 diffs)

doc/theses/colby_parsons_MMAth/local.bib

@@ -196 +196 @@
   year={2004}
 }
+
+@manual{IntelManual,
+    keywords    = {Intel},
+    title       = {Intel 64 and IA-32 Architectures Software Developer’s Manual},
+    version = {Version 080},
+    organization= {Intel},
+    month       = March,
+    year        = 2023,
+}

doc/theses/colby_parsons_MMAth/text/actors.tex

@@ -752 +752 @@
 The values swapped are never null pointers, so a null pointer can be used as an intermediate value during the swap.
 \end{enumerate}
-Figure~\ref{c:swap} shows the \CFA pseudocode for the \gls{dcasw}.
+Figure~\ref{f:dcaswImpl} shows the \CFA pseudocode for the \gls{dcasw}.
 In detail, a thief performs the following steps to swap two pointers:
 \begin{enumerate}[start=0]
@@ -765 +765 @@
 Since each worker owns a disjoint range of the queue array, it is impossible for @my_queue@ to be null.
 Note, this algorithm is simplified due to each worker owning a disjoint range, allowing only the @vic_queue@ to be checked for null.
-This was not listed as a special case of this algorithm, since this requirement can be avoided by modifying Step 1 of Figure~\ref{c:swap} to also check @my_queue@ for null.
+This was not listed as a special case of this algorithm, since this requirement can be avoided by modifying Step 1 of Figure~\ref{f:dcaswImpl} to also check @my_queue@ for null.
 Further discussion of this generalization is omitted since it is not needed for the presented application.
 \item
@@ -811 +811 @@
 \end{cfa}
 \caption{DCASW Concurrent}
-\label{c:swap}
+\label{f:dcaswImpl}
 \end{figure}
 
@@ -817 +817 @@
 \gls{dcasw} is correct in both the success and failure cases.
 \end{theorem}
-To verify sequential correctness, Figure~\ref{s:swap} shows a simplified \gls{dcasw}.
+To verify sequential correctness, Figure~\ref{f:seqSwap} shows a simplified \gls{dcasw}.
 Step 1 is missing in the sequential example since it only matters in the concurrent context.
 By inspection, the sequential swap copies each pointer being swapped, and then the original values of each pointer are reset using the copy of the other pointer.
@@ -836 +836 @@
 \end{cfa}
 \caption{DCASW Sequential}
-\label{s:swap}
+\label{f:seqSwap}
 \end{figure}
 
@@ -895 +895 @@
 First it is important to state that a thief will not attempt to steal from themselves.
 As such, the victim here is not also a thief.
-Stepping through the code in \ref{c:swap}, for all thieves steps 0-1 succeed since the victim is not stealing and will have no queue pointers set to be @0p@.
+Stepping through the code in \ref{f:dcaswImpl}, for all thieves steps 0-1 succeed since the victim is not stealing and will have no queue pointers set to be @0p@.
 Similarly for all thieves step 2 will succeed since no one is stealing from any of the thieves.
 In step 3 the first thief to @CAS@ will win the race and successfully swap the queue pointer.
@@ -991 +991 @@
 
 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{} and are stored in a shared array, with one index per worker.
+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.
 The intuition behind this heuristic is that the slowest worker will receive 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 means that if two thieves look to steal at the same time, they likely attempt to steal from the same victim.
+This heuristic should ideally result in lowered latency for message sends to victim workers that are overloaded with work.
+However, a side-effect of this heuristic is that if two thieves look to steal at the same time, they likely attempt to steal from the same victim.
 This approach consequently does increase the chance at contention among thieves;
 however, given that workers have multiple queues, often in the tens or hundreds of queues, it is rare for two thieves to attempt stealing from the same queue.