Index: doc/theses/colby_parsons_MMAth/text/actors.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/actors.tex (revision 9b0c193665908871eccf91544fefe7ce1698b7e4) +++ doc/theses/colby_parsons_MMAth/text/actors.tex (revision e6e1a1206cdd5defb28fcd401966d2d7b93b358d) @@ -555,5 +555,5 @@ In theory, this goal is not achievable, but practical results show the goal is virtually achieved. -One important lesson learned while working on \uC actors~\cite{} and through discussions with fellow student Thierry Delisle, who examined work-stealing for user-threads in his Ph.D.~\cite{Delisle22}, is \emph{not} to aggressively steal. +One important lesson learned while working on \uC actors~\cite{Buhr22} and through discussions with fellow student Thierry Delisle, who examined work-stealing for user-threads in his Ph.D.~\cite{Delisle22}, is \emph{not} to aggressively steal. With reasonable workloads, being a thief should be a temporary state, \ie eventually work appears on the thief's ready-queues and it returns to normal operation. Furthermore, the act of \emph{looking} to find work is invasive (Heisenberg uncertainty principle), possibly disrupting multiple victims. @@ -563,5 +563,5 @@ The outline for lazy-stealing by a thief is: select a victim, scan its queues once, and return immediately if a queue is stolen. The thief then returns to normal operation and conducts a regular scan over its own queues looking for work, where stolen work is placed at the end of the scan. -Hence, only one victim is affected and there is a reasonable delay between stealing events as the thief will scan its ready queue looking for its own work before potentially stealing again. +Hence, only one victim is affected and there is a reasonable delay between stealing events as the thief scans its ready queue looking for its own work before potentially stealing again. This lazy examination by the thief has a low perturbation cost for victims, while still finding work in a moderately loaded system. In all work-stealing algorithms, there is the pathological case where there is too little work and too many workers; @@ -584,14 +584,14 @@ \begin{cfa} struct work_queue { - spinlock_t mutex_lock; $\C[2.75in]{// atomicity for queue operations}$ - copy_queue * owned_queue; $\C{// copy queue}$ - copy_queue * c_queue; $\C{// current queue}$ - volatile bool being_processed; $\C{// flag to prevent concurrent processing}$ + spinlock_t mutex_lock; $\C[2.75in]{// atomicity for queue operations}$ + copy_queue * owned_queue; $\C{// copy queue}$ + copy_queue * c_queue; $\C{// current queue}$ + volatile bool being_processed; $\C{// flag to prevent concurrent processing}$ }; -work_queue * mailboxes; $\C{// master array of work request queues}$ -work_queue ** worker_queues; $\C{// secondary array of work queues to allow for swapping}\CRT$ +work_queue * mailboxes; $\C{// master array of work request queues}$ +work_queue ** worker_queues; $\C{// secondary array of work queues to allow for swapping}\CRT$ \end{cfa} A send inserts a request at the end of one of @mailboxes@. -A steal swaps two pointers in @worker_queues@. +A steal swaps two pointers in \snake{worker_queues}. Conceptually, @worker_queues@ represents the ownership relation between mailboxes and workers. Given $M$ workers and $N$ mailboxes, each worker owns a contiguous $M$/$N$ block of pointers in @worker_queues@. @@ -599,5 +599,5 @@ To transfer ownership of a mailbox from one worker to another, a pointer from each of the workers' ranges are swapped. This structure provides near-complete separation of stealing and gulping/send operations. -As such, operations can happen on @mailboxes@ independent of stealing, which avoids almost all contention between thief threads and victim threads. +As such, operations can happen on @mailboxes@ independent of stealing, which avoids almost all contention between thief and victim threads. \begin{figure} @@ -627,5 +627,5 @@ The thief then resumes normal execution and ceases being a thief. Hence, it iterates over its own worker queues because new messages may have arrived during stealing, including ones in the potentially stolen queue. -Stealing is only repeated after the worker completes two consecutive iterations over its owned queues without finding work. +Stealing is only repeated after the worker completes two consecutive iterations over its message queues without finding work. \end{enumerate} @@ -637,5 +637,5 @@ temp = worker_queues[x]; // preemption and steal -transfer( local_queue, temp->c_queue ); // @being_processed@ set in transfer with mutual exclusion +transfer( local_queue, temp->c_queue ); // atomically sets being_processed \end{cfa} where @transfer@ gulps the work from @c_queue@ to the victim's @local_queue@ and leaves @c_queue@ empty, partitioning the mailbox. @@ -648,5 +648,5 @@ \end{enumerate} If the victim is preempted after the dereference, a thief can steal the mailbox pointer before the victim calls @transfer@. -The thief then races ahead, transitions back to a victim, searches its mailboxes, finds the stolen non-empty mailbox, and gulps its queue. +The thief then races ahead, transitions back to a victim, searches its mailboxes, finds the stolen non-empty mailbox, and gulps this queue. The original victim now continues and gulps from the stolen mailbox pointed to by its dereference, even though the thief has logically subdivided this mailbox by gulping it. At this point, the mailbox has been subdivided a second time, and the victim and thief are possibly processing messages sent to the same actor, which violates mutual exclusion and the message-ordering guarantee. @@ -654,5 +654,5 @@ However, any form of locking here creates contention between thief and victim. -The alternative to locking is allowing the race and resolving it lazily. +The alternative to locking is allowing the race and resolving it lazily (lock-free approach). % As mentioned, there is a race between a victim gulping and a thief stealing because gulping partitions a mailbox queue making it ineligible for stealing. % Furthermore, after a thief steals, there is moment when victim gulps but the queue no longer @@ -668,5 +668,5 @@ The flag indicates that a mailbox has been gulped (logically subdivided) by a worker and the gulped queue is being processed locally. The @being_processed@ flag is reset once the local processing is finished. -If a worker, either victim or thief turned victim, attempts to gulp from a mailbox and find the @being_processed@ flag set, it does not gulp and moves on to the next mailbox in its range. +If a worker, either victim or thief turned victim, attempts to gulp from a mailbox and finds the @being_processed@ flag set, it does not gulp and moves onto the next mailbox in its range. This resolves the race no matter the winner. If the thief wins the race, it steals the mailbox and gulps, and the victim sees the flag set and skips gulping from the mailbox. @@ -675,42 +675,53 @@ There is a final case where the race occurs and is resolved with \emph{both} gulps occurring. Here, the winner of the race finishes processing the queue and resets the @being_processed@ flag. -Then the loser unblocks and completes its gulp from the same mailbox and atomically sets the @being_processed@ flag. -The loser is now processing messages from a temporarily shared mailbox, which is safe because the winner will ignore this mailbox if it attempts another gulp, since @being_processed@ is set. +Then the loser unblocks and completes its gulp from the same mailbox and atomically sets the \snake{being_processed} flag. +The loser is now processing messages from a temporarily shared mailbox, which is safe because the winner ignores this mailbox, if it attempts another gulp since @being_processed@ is set. The victim never attempts to gulp from the stolen mailbox again because its next cycle sees the swapped mailbox from the thief (which may or may not be empty at this point). This race is now the only source of contention between victim and thief as they both try to acquire a lock on the same queue during a transfer. However, the window for this race is extremely small, making this contention rare. -In theory, if this race occurs multiple times consecutively \ie a thief steals, dereferences stolen mailbox pointer, is interrupted and stolen from, etc., this scenario can cascade across multiple workers all attempting to gulp from one mailbox. +In theory, if this race occurs multiple times consecutively, \ie a thief steals, dereferences a stolen mailbox pointer, is interrupted, and stolen from, etc., this scenario can cascade across multiple workers all attempting to gulp from one mailbox. The @being_processed@ flag ensures correctness even in this case, and the chance of a cascading scenario across multiple workers is even rarer. -It is straightforward to count the number of missed gulps due to the @being_processed@ flag at runtime. -With the exception of the repeat benchmark, the median count of missed gulps for each number of cores for all benchmarks presented in Section~\ref{s:actor_perf} is \emph{zero}. + +It is straightforward to count the number of missed gulps due to the @being_processed@ flag and this counter is added to all benchmarks presented in Section~\ref{s:actor_perf}. +The results show the median count of missed gulps for each experiment is \emph{zero}, except for the repeat benchmark. The repeat benchmark is an example the pathological case described earlier where there is too little work and too many workers. -In the repeat benchmark one actor has the majority of the workload, and no other actor has a consistent workload which results in rampant stealing. -None of the work stealing actor systems compared in this work perform well on the repeat benchmark. -Hence, the claim is made that this stealing mechanism has a (probabilistically) zero-victim-cost in practice. +In the repeat benchmark, one actor has the majority of the workload, and no other actor has a consistent workload, which results in rampant stealing. +None of the work-stealing actor-systems examined in this work perform well on the repeat benchmark. +Hence, for all non-pathological cases, the claim is made that this stealing mechanism has a (probabilistically) zero-victim-cost in practice. \subsection{Queue Pointer Swap}\label{s:swap} -Two atomically swap two pointers in @worker_queues@, a novel wait-free swap algorithm is used. -The novel wait-free swap is effectively a special case of a DCAS. -DCAS stands for Double Compare-And-Swap, which is a more general version of the Compare-And-Swap (CAS) atomic operation~\cite{Doherty04}. -CAS compares is a read-modify-write operation available on most modern architectures which atomically compares an expected value with a memory location. -If the expected value and value in memory are equal it then writes a new value into the memory location. -A sample software implemention of CAS follows. + +To atomically swap the two @worker_queues@ pointers during work stealing, a novel wait-free swap-algorithm is needed. +The \gls{cas} is a read-modify-write instruction available on most modern architectures. +It atomically compares two memory locations, and if the values are equal, it writes a new value into the first memory location. +A software implementation of \gls{cas} is: \begin{cfa} // assume this routine executes atomically -bool CAS( val * ptr, val expected, val new ) { - if ( *ptr != expected ) - return false; - *ptr = new; +bool CAS( T * assn, T comp, T new ) { // T is a basic type + if ( *assn != comp ) return false; + *assn = new; return true; } \end{cfa} -As shown CAS only operates on one memory location. -Where CAS operates on a single memory location and some values, DCAS operates on two memory locations. +However, this instruction does \emph{not} swap @assn@ and @new@, which is why compare-and-swap is a misnomer. +If @T@ can be a double-wide address-type (128 bits on a 64-bit machine), called a \gls{dwcas}, then it is possible to swap two values, if and only if the two addresses are juxtaposed in memory. +\begin{cfa} +union Pair { + struct { void * ptr1, * ptr2; }; // 64-bit pointers + __int128 atom; +}; +Pair pair1 = { addr1, addr2 }, pair2 = { addr2, addr1 }; +Pair top = pair1; +DWCAS( top.atom, pair1.atom, pair2.atom ); +\end{cfa} +However, this approach does not apply because the mailbox pointers are seldom juxtaposed. + +Only a few architectures provide a \gls{dcas}, which extends \gls{cas} to two memory locations~\cite{Doherty04}. \begin{cfa} // assume this routine executes atomically -bool DCAS( val * addr1, val * addr2, val old1, val old2, val new1, val new2 ) { - if ( ( *addr1 == old1 ) && ( *addr2 == old2 ) ) { - *addr1 = new1; - *addr2 = new2; +bool DCAS( T * assn1, T * assn2, T comp1, T comp2, T new1, T new2 ) { + if ( *assn1 == comp1 && *assn2 == comp2 ) { + *assn1 = new1; + *assn2 = new2; return true; } @@ -718,28 +729,94 @@ } \end{cfa} -The DCAS implemented in this work is special cased in two ways. -First of all, a DCAS is more powerful than what is needed to swap two pointers. -A double atomic swap (DAS) is all that is needed for this work. -The atomic swap provided by most modern hardware requires that at least one operand is a register. -A DAS would relax that restriction so that both operands of the swap could be memory locations. -As such a DAS can be written in terms of the DCAS above as follows. -\begin{cfa} -bool DAS( val * addr1, val * addr2 ) { - return DCAS( addr1, addr2, *addr1, *addr2, *addr2, *addr1 ); +and can swap two values, where the comparisons are superfluous. +\begin{cfa} +DCAS( x, y, x, y, y, x ); +\end{cfa} +A restrictive form of \gls{dcas} can be simulated using \gls{ll}/\gls{sc}~\cite{Brown13} or more expensive transactional memory the same progress property problems as LL/SC. +(There is waning interest in transactional memory and it seems to be fading away.) + +Similarly, very few architectures have a true memory/memory swap instruction (Motorola M68K, SPARC 32-bit). +The x86 XCHG instruction (and most other architectures with a similar instruction) only works between a register and memory location. +In this case, there is a race between loading the register and performing the swap (discussed shortly). + +Hence, a novel swap is constructed, called \gls{das}, special cased in two ways: +\begin{enumerate} +\item +It works on two separate memory locations, and hence, is logically the same as. +\begin{cfa} +bool DAS( T * assn1, T * assn2 ) { + return DCAS( assn1, assn2, *assn1, *assn2, *assn2, *assn1 ); } \end{cfa} -The other special case is that the values being swapped will never null pointers. -This allows the DAS implementation presented to use null pointers as intermediate values during the swap. - -Given the wait-free swap used is novel, it is important to show that it is correct. -It is clear to show that the swap is wait-free since all thieves will fail or succeed in swapping the queues in a finite number of steps since there are no locks or looping. -There is no retry mechanism in the case of a failed swap, since a failed swap either means the work was already stolen, or that work was stolen from the thief. -In both cases it is apropos for a thief to give up on stealing. -\CFA-style pseudocode for the queue swap is presented below. -The swap uses compare-and-swap (@CAS@) which is just pseudocode for C's @__atomic_compare_exchange_n@. -A pseudocode implementation of @CAS@ is also shown below. -The correctness of the wait-free swap will now be discussed in detail. -To first verify sequential correctness, consider the equivalent sequential swap below: - +\item +The values swapped are never null pointers, so a null pointer can be used as an intermediate values during the swap. +\end{enumerate} +Figure~\ref{c:swap} shows the \CFA pseudocode for the \gls{das}. +In detail, a thief performs the following steps to swap two pointers: +\begin{enumerate}[start=0] +\item +stores local copies of the two pointers to be swapped. +\item +verifies the stored copy of the victim queue pointer, @vic_queue@, is valid. +If @vic_queue@ is null, then the victim queue is part of another swap so the operation fails. +No state has changed at this point so no fixup is needed. +Note, @my_queue@ can never be equal to null at this point since thieves only set their own queues pointers to null when stealing. +At no other point is a queue pointer set to null. +Since each worker owns a disjoint range of the queue array, it is impossible for @my_queue@ to be null. +\item +attempts to atomically set the thief's queue pointer to null. +The @CAS@ only fails if the thief's queue pointer is no longer equal to @my_queue@, which implies this thief has become a victim and its queue has been stolen. +At this point, the thief-turned-victim fails, and since it has not changed any state, it just returns false. +If the @CAS@ succeeds, the thief's queue pointer is now null. +Nulling the pointer is safe since only thieves look at other worker's queue ranges, and whenever thieves need to dereference a queue pointer, it is checked for null. +\item +attempts to atomically set the victim's queue pointer to @my_queue@. +If the @CAS@ succeeds, the victim's queue pointer has been set and the swap can no longer fail. +If the @CAS@ fails, the thief's queue pointer must be restored to its previous value before returning. +\item +set the thief's queue pointer to @vic_queue@ completing the swap. +\end{enumerate} + +\begin{figure} +\begin{cfa} +bool try_swap_queues( worker & this, uint victim_idx, uint my_idx ) with(this) { + // Step 0: mailboxes is the shared array of all sharded queues + work_queue * my_queue = mailboxes[my_idx]; + work_queue * vic_queue = mailboxes[victim_idx]; + + // Step 1 If the victim queue is 0p then they are in the process of stealing so return false + // 0p is Cforall's equivalent of C++'s nullptr + if ( vic_queue == 0p ) return false; + + // Step 2 Try to set our own (thief's) queue ptr to be 0p. + // If this CAS fails someone stole our (thief's) queue so return false + if ( !CAS( &mailboxes[my_idx], &my_queue, 0p ) ) + return false; + + // Step 3: Try to set victim queue ptr to be our (thief's) queue ptr. + // If it fails someone stole the other queue, so fix up then return false + if ( !CAS( &mailboxes[victim_idx], &vic_queue, my_queue ) ) { + mailboxes[my_idx] = my_queue; // reset queue ptr back to prev val + return false; + } + // Step 4: Successfully swapped. + // Thief's ptr is 0p so no one will touch it + // Write back without CAS is safe + mailboxes[my_idx] = vic_queue; + return true; +} +\end{cfa} +\caption{DAS Concurrent} +\label{c:swap} +\end{figure} + +\begin{theorem} +\gls{das} is correct in both the success and failure cases. +\end{theorem} +To verify sequential correctness, Figure~\ref{s:swap} shows a simplified \gls{das}. +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. + +\begin{figure} \begin{cfa} void swap( uint victim_idx, uint my_idx ) { @@ -755,96 +832,40 @@ } \end{cfa} - -Step 1 is missing in the sequential example since it only matters in the concurrent context presented later. -By looking at the sequential swap it is easy to see that it is correct. -Temporary copies of each pointer being swapped are stored, and then the original values of each pointer are set using the copy of the other pointer. - -\begin{cfa} - -bool try_swap_queues( worker & this, uint victim_idx, uint my_idx ) with(this) { - // Step 0: - // mailboxes is the shared array of all sharded queues - work_queue * my_queue = mailboxes[my_idx]; - work_queue * vic_queue = mailboxes[victim_idx]; - - // Step 1: - // If the victim queue is 0p then they are in the process of stealing so return false - // 0p is Cforall's equivalent of C++'s nullptr - if ( vic_queue == 0p ) return false; - - // Step 2: - // Try to set our own (thief's) queue ptr to be 0p. - // If this CAS fails someone stole our (thief's) queue so return false - if ( !CAS( &mailboxes[my_idx], &my_queue, 0p ) ) - return false; - - // Step 3: - // Try to set victim queue ptr to be our (thief's) queue ptr. - // If it fails someone stole the other queue, so fix up then return false - if ( !CAS( &mailboxes[victim_idx], &vic_queue, my_queue ) ) { - mailboxes[my_idx] = my_queue; // reset queue ptr back to prev val - return false; - } - - // Step 4: - // Successfully swapped. - // Thief's ptr is 0p so no one will touch it - // Write back without CAS is safe - mailboxes[my_idx] = vic_queue; - return true; -} -\end{cfa}\label{c:swap} - -Now consider the concurrent implementation of the swap. -\begin{enumerate}[topsep=5pt,itemsep=3pt,parsep=0pt] -\item -Step 0 is the same as the sequential example, and the thief stores local copies of the two pointers to be swapped. -\item -Step 1 verifies that the stored copy of the victim queue pointer, @vic_queue@, is valid. -If @vic_queue@ is equal to @0p@, then the victim queue is part of another swap so the operation fails. -No state has changed at this point so no fixups are needed. -Note, @my_queue@ can never be equal to @0p@ at this point since thieves only set their own queues pointers to @0p@ when stealing. -At no other point will a queue pointer be set to @0p@. -Since each worker owns a disjoint range of the queue array, it is impossible for @my_queue@ to be @0p@. -\item -Step 2 attempts to set the thief's queue pointer to @0p@ via @CAS@. -The @CAS@ will only fail if the thief's queue pointer is no longer equal to @my_queue@, which implies that this thief has become a victim and its queue has been stolen. -At this point the thief-turned-victim will fail and since it has not changed any state it just fails and returns false. -If the @CAS@ succeeds then the thief's queue pointer will now be @0p@. -Nulling the pointer is safe since only thieves look at other worker's queue ranges, and whenever thieves need to dereference a queue pointer they check for @0p@. -\item -Step 3 attempts to set the victim's queue pointer to be @my_queue@ via @CAS@. -If the @CAS@ succeeds then the victim's queue pointer has been set and swap can no longer fail. -If the @CAS@ fails then the thief's queue pointer must be restored to its previous value before returning. -\item -Step 4 sets the thief's queue pointer to be @vic_queue@ completing the swap. -\end{enumerate} - -\begin{theorem} -The presented swap is correct and concurrently safe in both the success and failure cases. -\end{theorem} - -Correctness of the swap is shown through the existence of an invariant. -The invariant is that when a queue pointer is set to @0p@ by a thief, then the next write to the pointer can only be performed by the same thief. +\caption{DAS Sequential} +\label{s:swap} +\end{figure} + +To verify concurrent correctness, it is necessary to show \gls{das} is wait-free, \ie all thieves fail or succeed in swapping the queues in a finite number of steps. +This property is straightforward, because there are no locks or looping. +As well, there is no retry mechanism in the case of a failed swap, since a failed swap either means the work is already stolen or that work is stolen from the thief. +In both cases, it is apropos for a thief to give up stealing. + +The proof of correctness is shown through the existence of an invariant. +The invariant states when a queue pointer is set to @0p@ by a thief, then the next write to the pointer can only be performed by the same thief. To show that this invariant holds, it is shown that it is true at each step of the swap. +\begin{itemize} +\item Step 0 and 1 do not write and as such they cannot invalidate the invariant of any other thieves. -In step 2 a thief attempts to write @0p@ to one of their queue pointers. +\item +In step 2, a thief attempts to write @0p@ to one of their queue pointers. This queue pointer cannot be @0p@. -As stated above, @my_queue@ is never equal to @0p@ since thieves will only write @0p@ to queue pointers from their own queue range and all worker's queue ranges are disjoint. -As such step 2 upholds the invariant since in a failure case no write occurs, and in the success case, the value of the queue pointer is guaranteed to not be 0p. -In step 3 the thief attempts to write @my_queue@ to the victim's queue pointer. -If the current value of the victim's queue pointer is @0p@, then the CAS will fail since @vic_queue@ cannot be equal to @0p@ because of the check in step 1. -Therefore in the success case where the @CAS@ succeeds, the value of the victim's queue pointer must not be @0p@. -As such, the write will never overwrite a value of @0p@, hence the invariant is held in the @CAS@ of step 3. -The write back to the thief's queue pointer that happens in the failure case of step three and in step 4 hold the invariant since they are the subsequent write to a @0p@ queue pointer and they are being set by the same thief that set the pointer to @0p@. +As stated above, @my_queue@ is never equal to @0p@ since thieves only write @0p@ to queue pointers from their own queue range and all worker's queue ranges are disjoint. +As such, step 2 upholds the invariant, since in a failure case no write occurs, and in the success case, the value of the queue pointer is guaranteed to not be 0p. +\item +In step 3, the thief attempts to write @my_queue@ to the victim's queue pointer. +If the current value of the victim's queue pointer is @0p@, then the CAS fails since @vic_queue@ cannot be equal to @0p@ because of the check in step 1. +Therefore, when the @CAS@ succeeds, the value of the victim's queue pointer must not be @0p@. +As such, the write never overwrites a value of @0p@, hence the invariant is held in the @CAS@ of step 3. +\item +The write back to the thief's queue pointer that happens in the failure case of step 3 and in step 4 hold the invariant since they are the subsequent write to a @0p@ queue pointer and are being set by the same thief that set the pointer to @0p@. +\end{itemize} Given this informal proof of invariance it can be shown that the successful swap is correct. -Once a thief atomically sets their queue pointer to be @0p@ in step 2, the invariant guarantees that pointer will not change. -As such, in the success case step 3 it is known that the value of the victim's queue pointer that was overwritten must be @vic_queue@ due to the use of @CAS@. +Once a thief atomically sets their queue pointer to be @0p@ in step 2, the invariant guarantees that that pointer does not change. +In the success case of step 3, it is known the value of the victim's queue-pointer, which is not overwritten, must be @vic_queue@ due to the use of @CAS@. Given that pointers all have unique memory locations, this first write of the successful swap is correct since it can only occur when the pointer has not changed. -By the invariant the write back in the successful case is correct since no other worker can write to the @0p@ pointer. - -In the failed case the outcome is correct in steps 1 and 2 since no writes have occurred so the program state is unchanged. -In the failed case of step 3 the program state is safely restored to its state it had prior to the @0p@ write in step 2, thanks to the invariant that makes the write back to the @0p@ pointer safe. +By the invariant, the write back in the successful case is correct since no other worker can write to the @0p@ pointer. +In the failed case of step 3, the outcome is correct in steps 1 and 2 since no writes have occurred so the program state is unchanged. +Therefore, the program state is safely restored to the state it had prior to the @0p@ write in step 2, because the invariant makes the write back to the @0p@ pointer safe. \begin{comment} @@ -957,95 +978,108 @@ % C_TODO: go through and use \paragraph to format to make it look nicer \subsection{Victim Selection}\label{s:victimSelect} -In any work stealing algorithm thieves have some heuristic to determine which victim to choose from. + +In any work stealing algorithm, thieves use a heuristic to determine which victim to choose. Choosing this algorithm is difficult and can have implications on performance. -There is no one selection heuristic that is known to be the best on all workloads. -Recent work focuses on locality aware scheduling in actor systems\cite{barghi18}\cite{wolke17}. -However, while locality aware scheduling provides good performance on some workloads, something as simple as randomized selection performs better on other workloads\cite{barghi18}. -Since locality aware scheduling has been explored recently, this work introduces a heuristic called \textbf{longest victim} and compares it to randomized work stealing. -The longest victim heuristic maintains a timestamp per executor threads that is updated every time a worker attempts to steal work. -Thieves then attempt to steal from the thread with the oldest timestamp. -This means that if two thieves look to steal at the same time, they likely will attempt to steal from the same victim. -This does increase the chance at contention between thieves, however given that workers have multiple queues under them, often in the tens or hundreds of queues per worker it is rare for two queues to attempt so steal the same queue. -Furthermore in the case they attempt to steal the same queue at least one of them is guaranteed to successfully steal the queue as shown in Theorem \ref{t:one_vic}. -Additionally, the longest victim heuristic makes it very improbable that the no swap scenario presented in Theorem \ref{t:vic_cycle} manifests. -Given the longest victim heuristic, for a cycle to manifest it would require all workers to attempt to steal in a short timeframe. -This is the only way that more than one thief could choose another thief as a victim, since timestamps are only updated upon attempts to steal. -In this case, the probability of lack of any successful swaps is a non issue, since it is likely that these steals were not important if all workers are trying to steal. +There is no one selection heuristic known to be best for all workloads. +Recent work focuses on locality aware scheduling in actor systems~\cite{barghi18,wolke17}. +However, while locality-aware scheduling provides good performance on some workloads, sometime randomized selection performs better on other workloads~\cite{barghi18}. +Since locality aware scheduling has been explored recently, this work introduces a heuristic called \Newterm{longest victim} and compares it to randomized work stealing. + +The longest-victim heuristic maintains a timestamp per executor thread that is updated every time a worker attempts to steal work. +\PAB{Explain the timestamp, \ie how is it formed?} +Thieves then attempt to steal from the worker with the oldest timestamp. +This heuristic means that if two thieves look to steal at the same time, they likely attempt to steal from the same victim. +\PAB{This idea seems counter intuitive so what is the intuition?} +This consequence 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. +\PAB{Both of these theorems are commented out.} +Furthermore, in the case they attempt to steal the same queue, at least one of them is guaranteed to successfully steal the queue as shown in Theorem~\ref{t:one_vic}. +Additionally, the longest victim heuristic makes it very improbable that the no swap scenario presented in Theorem~\ref{t:vic_cycle} manifests. +Given the longest victim heuristic, for a cycle to manifest it requires all workers to attempt to steal in a short timeframe. +This scenario is the only way that more than one thief could choose another thief as a victim, since timestamps are only updated upon attempts to steal. +In this case, the probability of an unsuccessful swap is rare, since it is likely these steals are not important when all workers are trying to steal. \section{Safety and Productivity}\label{s:SafetyProductivity} + \CFA's actor system comes with a suite of safety and productivity features. -Most of these features are present in \CFA's debug mode, but are removed when code is compiled in nodebug mode. +Most of these features are only present in \CFA's debug mode, and hence, have have zero-cost in nodebug mode. The suit of features include the following. - \begin{itemize} -\item Static-typed message sends. -If an actor does not support receiving a given message type, the actor program is rejected at compile time, allowing unsupported messages to never be sent to actors. -\item Detection of message sends to Finished/Destroyed/Deleted actors. -All actors have a ticket that assigns them to a respective queue. -The maximum integer value of the ticket is reserved to indicate that an actor is dead, and subsequent message sends result in an error. -\item Actors made before the executor can result in undefined behaviour since an executor needs to be created beforehand so it can give out the tickets to actors. -As such, this is detected and an error is printed. -\item When an executor is created, the queues are handed out to executor threads in round robin order. -If there are fewer queues than executor threads, then some workers will spin and never do any work. -There is no reasonable use case for this behaviour so an error is printed if the number of queues is fewer than the number of executor threads. -\item A warning is printed when messages are deallocated without being sent. +\item Static-typed message sends: +If an actor does not support receiving a given message type, the receive call is rejected at compile time, allowing unsupported messages to never be sent to an actor. + +\item Detection of message sends to Finished/Destroyed/Deleted actors: +All actors receive a ticket from the executor at creation that assigns them to a specific mailbox queue of a worker. +The maximum integer value of the ticket is reserved to indicate an actor is terminated, and assigned to an actor's ticket at termination. +Any subsequent message sends to this terminated actor results in an error. + +\item Actors cannot be created before the executor starts: +Since the executor distributes mailbox tickets, correctness implies it must be created before an actors so it can give out the tickets. + +\item When an executor is configured, $M >= N$. +That is, each worker must receive at least one mailbox queue, otherwise the worker spins and never does any work. + +\item Detection of unsent messages: +At program termination, a warning is printed for all deallocated messages that are not sent. Since the @Finished@ allocation status is unused for messages, it is used internally to detect if a message has been sent. -Deallocating a message without sending it could indicate to a user that they are touching freed memory later, or it could point out extra allocations that could be removed. -\item Detection of messages sent but not received -As discussed in Section~\ref{s:executor}, once all actors have terminated shutdown is communicated to executor threads via a status flag. Upon termination the executor threads check their queues to see if any contain messages. If they do, an error is reported. Messages being sent but not received means that their allocation action did not occur and their payload was not delivered. Missing the allocation action can lead to memory leaks and missed payloads can cause unpredictable behaviour. Detecting this can indicate a race or logic error in the user's code. +Deallocating a message without sending it could indicate problems in the program design. + +\item Detection of messages sent but not received: +As discussed in Section~\ref{s:executor}, once all actors have terminated, shutdown is communicated to the executor threads via a status flag. +During termination of the executor threads, each worker checks its mailbox queues for any messages. +If so, an error is reported. +Messages being sent but not received means their allocation action has not occur and their payload is not delivered. +Missed deallocations can lead to memory leaks and unreceived payloads can mean logic problems. +% Detecting can indicate a race or logic error in the user's code. \end{itemize} -In addition to these features, \CFA's actor system comes with a suite of statistics that can be toggled on and off. -These statistics have minimal impact on the actor system's performance since they are counted on a per executor threads basis. -During shutdown of the actor system they are aggregated, ensuring that the only atomic instructions used by the statistics counting happen at shutdown. +In addition to these features, the \CFA's actor system comes with a suite of statistics that can be toggled on and off when \CFA is built. +These statistics have minimal impact on the actor system's performance since they are counted independently by each worker thread. +During shutdown of the actor system, these counters are aggregated sequentially. The statistics measured are as follows. - \begin{description} \item[\LstBasicStyle{\textbf{Actors Created}}] -Actors created. -Includes both actors made by the main and ones made by other actors. -\item[\LstBasicStyle{\textbf{Messages Sent}}] -Messages sent and received. +Includes both actors made in the program main and ones made by other actors. +\item[\LstBasicStyle{\textbf{Messages Sent and Received}}] Includes termination messages send to the executor threads. \item[\LstBasicStyle{\textbf{Gulps}}] -Gulps that occurred across the executor threads. +Gulps across all worker threads. \item[\LstBasicStyle{\textbf{Average Gulp Size}}] Average number of messages in a gulped queue. \item[\LstBasicStyle{\textbf{Missed gulps}}] -Occurrences where a worker missed a gulp due to the concurrent queue processing by another worker. +Missed gulps due to the current queue being processed by another worker. \item[\LstBasicStyle{\textbf{Steal attempts}}] -Worker threads attempts to steal work. - +All worker thread attempts to steal work. \item[\LstBasicStyle{\textbf{Steal failures (no candidates)}}] -Work stealing failures due to selected victim not having any non empty or non-being-processed queues. +Work stealing failures due to selected victim not having any non-empty or non-being-processed queues. \item[\LstBasicStyle{\textbf{Steal failures (failed swaps)}}] -Work stealing failures due to the two stage atomic swap failing. +Work stealing failures due to the two-stage atomic-swap failing. \item[\LstBasicStyle{\textbf{Messages stolen}}] -Aggregate of the number of messages in queues as they were stolen. +Aggregate number of messages in stolen queues. \item[\LstBasicStyle{\textbf{Average steal size}}] -Average number of messages in a stolen queue. +Average number of messages across stolen queues. \end{description} -These statistics enable a user of \CFA's actor system to make informed choices about how to configure their executor, or how to structure their actor program. -For example, if there is a lot of messages being stolen relative to the number of messages sent, it could indicate to a user that their workload is heavily imbalanced across executor threads. -In another example, if the average gulp size is very high, it could indicate that the executor could use more queue sharding. - -Another productivity feature that is included is a group of poison-pill messages. -Poison-pill messages are common across actor systems, including Akka and ProtoActor \cite{Akka,ProtoActor}. -Poison-pill messages inform an actor to terminate. +These statistics enable a user of the \CFA's actor system to make informed choices about how to configure their executor or how to structure their actor program. +For example, if there are a lot of messages being stolen relative to the number of messages sent, it indicates that the workload is heavily imbalanced across executor threads. +Another example is if the average gulp size is very high, it indicates the executor needs more queue sharding, \ie increase $M$. + +Another productivity feature is a group of \Newterm{poison-pill} messages. +Poison-pill messages are common across actor systems, including Akka and ProtoActor~\cite{Akka,ProtoActor} to inform an actor to terminate. In \CFA, due to the allocation of actors and lack of garbage collection, there needs to be a suite of poison-pills. The messages that \CFA provides are @DeleteMsg@, @DestroyMsg@, and @FinishedMsg@. -These messages are supported on all actor types via inheritance and when sent to an actor, the actor takes the corresponding allocation action after receiving the message. -Note that any pending messages to the actor will still be sent. -It is still the user's responsibility to ensure that an actor does not receive any messages after termination. +These messages are supported on all actor types via inheritance. +When sent to an actor, the actor takes the corresponding allocation action after receiving the message, regardless of what the actor returns to the executor. +\PAB{What does this mean? Note that any pending messages to the actor will still be sent. +It is still the user's responsibility to ensure that an actor does not receive any messages after termination.} \section{Performance}\label{s:actor_perf} + The performance of \CFA's actor system is tested using a suite of microbenchmarks, and compared with other actor systems. -Most of the benchmarks are the same as those presented in \ref{}, with a few additions. +Most of the benchmarks are the same as those presented in \cite{Buhr22}, with a few additions. % C_TODO cite actor paper -At the time of this work the versions of the actor systems are as follows. -\CFA 1.0, \uC 7.0.0, Akka Typed 2.7.0, CAF 0.18.6, and ProtoActor-Go v0.0.0-20220528090104-f567b547ea07. -Akka Classic is omitted as Akka Typed is their newest version and seems to be the direction they are headed in. -The experiments are run on +This work compares with the following actor systems: \CFA 1.0, \uC 7.0.0, Akka Typed 2.7.0, CAF 0.18.6, and ProtoActor-Go v0.0.0-20220528090104-f567b547ea07. +Akka Classic is omitted as Akka Typed is their newest version and seems to be the direction they are headed. +The experiments are run on two popular architectures: \begin{list}{\arabic{enumi}.}{\usecounter{enumi}\topsep=5pt\parsep=5pt\itemsep=0pt} \item @@ -1055,14 +1089,29 @@ \end{list} -The benchmarks are run on up to 48 cores. -On the Intel, when going beyond 24 cores there is the choice to either hop sockets or to use hyperthreads. -Either choice will cause a blip in performance trends, which can be seen in the following performance figures. -On the Intel the choice was made to hyperthread instead of hopping sockets for experiments with more than 24 cores. - -All benchmarks presented are run 5 times and the median is taken. -Error bars showing the 95\% confidence intervals are drawn on each point on the graphs. +The benchmarks are run on 1--48 cores. +On the Intel, with 24 core sockets, there is the choice to either hopping sockets or using hyperthreads on the same socket. +Either choice causes a blip in performance, which is seen in the subsequent performance graphs. +The choice is to use hyperthreading instead of hopping sockets for experiments with more than 24 cores. + +All benchmarks are run 5 times and the median is taken. +Error bars showing the 95\% confidence intervals appear on each point in the graphs. If the confidence bars are small enough, they may be obscured by the point. -In this section \uC will be compared to \CFA frequently, as the actor system in \CFA was heavily based off \uC's actor system. -As such the performance differences that arise are largely due to the contributions of this work. +In this section, \uC is compared to \CFA frequently, as the actor system in \CFA is heavily based off of the \uC's actor system. +As such, the performance differences that arise are largely due to the contributions of this work. +Future work is to port some of the new \CFA work back to \uC. + +\subsection{Message Sends} + +Message sending is the key component of actor communication. +As such, latency of a single message send is the fundamental unit of fast-path performance for an actor system. +The static and dynamic microbenchmarks evaluate the average latency for a static actor/message send and a dynamic actor/message send. +In the static-send benchmark, a message and actor are allocated once and then the message is sent to the same actor 100 million (100M) times. +The average latency per message send is then calculated by dividing the duration by the number of sends. +This benchmark evaluates the cost of message sends in the actor use case where all actors and messages are allocated ahead of time and do not need to be created dynamically during execution. +The CAF static-send benchmark only sends a message 10M times to avoid extensively long run times. + +In the dynamic-send benchmark, the same experiment is used, but for each send, a new actor and message is allocated. +This benchmark evaluates the cost of message sends in the other common actor pattern where actors and messages are created on the fly as the actor program tackles a workload of variable or unknown size. +Since dynamic sends are more expensive, this benchmark repeats the actor/message creation and send 20M times (\uC, \CFA), or 2M times (Akka, CAF, ProtoActor), to give an appropriate benchmark duration. \begin{table}[t] @@ -1070,7 +1119,7 @@ \setlength{\extrarowheight}{2pt} \setlength{\tabcolsep}{5pt} - -\caption{Static Actor/Message Performance: message send, program memory} +\caption{Static Actor/Message Performance: message send, program memory (lower is better)} \label{t:StaticActorMessagePerformance} +\PAB{Put uC++ beside \CFA.} \begin{tabular}{*{5}{r|}r} & \multicolumn{1}{c|}{\CFA (100M)} & \multicolumn{1}{c|}{CAF (10M)} & \multicolumn{1}{c|}{Akka (100M)} & \multicolumn{1}{c|}{\uC (100M)} & \multicolumn{1}{c@{}}{ProtoActor (100M)} \\ @@ -1083,6 +1132,7 @@ \bigskip -\caption{Dynamic Actor/Message Performance: message send, program memory} +\caption{Dynamic Actor/Message Performance: message send, program memory (lower is better)} \label{t:DynamicActorMessagePerformance} +\PAB{The uC++ AMD looks high. It is 65ns in the Actor paper.} \begin{tabular}{*{5}{r|}r} @@ -1095,64 +1145,25 @@ \end{table} -\subsection{Message Sends} -Message sending is the key component of actor communication. -As such latency of a single message send is the fundamental unit of fast-path performance for an actor system. -The following two microbenchmarks evaluate the average latency for a static actor/message send and a dynamic actor/message send. -Static and dynamic refer to the allocation of the message and actor. -In the static send benchmark a message and actor are allocated once and then the message is sent to the same actor repeatedly until it has been sent 100 million (100M) times. -The average latency per message send is then calculated by dividing the duration by the number of sends. -This benchmark evaluates the cost of message sends in the actor use case where all actors and messages are allocated ahead of time and do not need to be created dynamically during execution. -The CAF static send benchmark only sends a message 10M times to avoid extensively long run times. - -In the dynamic send benchmark the same experiment is performed, with the change that with each send a new actor and message is allocated. -This evaluates the cost of message sends in the other common actor pattern where actors and message are created on the fly as the actor program tackles a workload of variable or unknown size. -Since dynamic sends are more expensive, this benchmark repeats the actor/message creation and send 20M times (\uC, \CFA), or 2M times (Akka, CAF, ProtoActor), to give an appropriate benchmark duration. - -The results from the static/dynamic send benchmarks are shown in Figures~\ref{t:StaticActorMessagePerformance} and \ref{t:DynamicActorMessagePerformance} respectively. -\CFA leads the charts in both benchmarks, largely due to the copy queue removing the majority of the envelope allocations. -Additionally, the receive of all messages sent in \CFA is statically known and is determined via a function pointer cast, which incurs a compile-time cost. -All the other systems use their virtual system to find the correct behaviour at message send. -This requires two virtual dispatch operations, which is an additional runtime send cost that \CFA does not have. -Note that Akka also statically checks message sends, but still uses their virtual system at runtime. -In the static send benchmark all systems except CAF have static send costs that are in the same ballpark, only varying by ~70ns. -In the dynamic send benchmark all systems experience slower message sends, as expected due to the extra allocations. -However, Akka and ProtoActor, slow down by a more significant margin than the \uC and \CFA. -This is likely a result of Akka and ProtoActor's garbage collection, which can suffer from hits in performance for allocation heavy workloads, whereas \uC and \CFA have explicit allocation/deallocation. +The results from the static/dynamic-send benchmarks are shown in Tables~\ref{t:StaticActorMessagePerformance} and \ref{t:DynamicActorMessagePerformance}, respectively. +\CFA has the best results in both benchmarks, largely due to the copy queue removing the majority of the envelope allocations. +Additionally, the receive of all messages sent in \CFA is statically known and is determined via a function pointer cast, which incurs no runtime cost. +All the other systems use virtual dispatch to find the correct behaviour at message send. +This operation actually requires two virtual dispatches, which is an additional runtime send cost. +Note that Akka also statically checks message sends, but still uses the Java virtual system. +In the static-send benchmark, all systems except CAF have static send costs that are in the same ballpark, only varying by ~70ns. +In the dynamic-send benchmark, all systems experience slower message sends, due to the memory allocations. +However, Akka and ProtoActor, slow down by two-orders of magnitude. +This difference is likely a result of Akka and ProtoActor's garbage collection, which results in performance delays for allocation-heavy workloads, whereas \uC and \CFA have explicit allocation/deallocation. +Tuning the garage collection might reduce garbage-collection cost, but this exercise is beyond the scope of this work. \subsection{Work Stealing} -\CFA's actor system has a work stealing mechanism which uses the longest victim heuristic, introduced in Section~ref{s:victimSelect}. -In this performance section, \CFA with the longest victim heuristic is compared with other actor systems on the benchmark suite, and is separately compared with vanilla non-stealing \CFA and \CFA with randomized work stealing. - -\begin{figure} - \centering - \subfloat[AMD \CFA Balance-One Benchmark]{ - \resizebox{0.5\textwidth}{!}{\input{figures/nasusCFABalance-One.pgf}} - \label{f:BalanceOneAMD} - } - \subfloat[Intel \CFA Balance-One Benchmark]{ - \resizebox{0.5\textwidth}{!}{\input{figures/pykeCFABalance-One.pgf}} - \label{f:BalanceOneIntel} - } - \caption{The balance-one benchmark comparing stealing heuristics (lower is better).} -\end{figure} - -\begin{figure} - \centering - \subfloat[AMD \CFA Balance-Multi Benchmark]{ - \resizebox{0.5\textwidth}{!}{\input{figures/nasusCFABalance-Multi.pgf}} - \label{f:BalanceMultiAMD} - } - \subfloat[Intel \CFA Balance-Multi Benchmark]{ - \resizebox{0.5\textwidth}{!}{\input{figures/pykeCFABalance-Multi.pgf}} - \label{f:BalanceMultiIntel} - } - \caption{The balance-multi benchmark comparing stealing heuristics (lower is better).} -\end{figure} - -There are two benchmarks in which \CFA's work stealing is solely evaluated. -The main goal of introducing work stealing to \CFA's actor system is to eliminate the pathological unbalanced cases that can present themselves in a system without some form of load balancing. -The following two microbenchmarks construct two such pathological cases, and compare the work stealing variations of \CFA. -The balance benchmarks adversarially takes advantage of the round robin assignment of actors to load all actors that will do work on specific cores and create 'dummy' actors that terminate after a single message send on all other cores. + +\CFA's work stealing mechanism uses the longest-victim heuristic, introduced in Section~\ref{s:victimSelect}. +In this performance section, \CFA's approach is first tested in isolation on pathological unbalanced benchmarks, then with other actor systems on general benchmarks. + +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 loading the receive actors on even cores and the send actors on the odd cores. The workload on the loaded cores is the same as the executor benchmark described in \ref{s:executorPerf}, but with fewer rounds. + The balance-one benchmark loads all the work on a single core, whereas the balance-multi loads all the work on half the cores (every other core). Given this layout, one expects the ideal speedup of work stealing in the balance-one case to be $N / N - 1$ where $N$ is the number of threads. @@ -1161,4 +1172,30 @@ In the balance-multi experiment, the workload increases with the number of cores so an increasing or constant runtime is expected. +\begin{figure} + \centering + \subfloat[AMD \CFA Balance-One Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/nasusCFABalance-One.pgf}} + \label{f:BalanceOneAMD} + } + \subfloat[Intel \CFA Balance-One Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/pykeCFABalance-One.pgf}} + \label{f:BalanceOneIntel} + } + \caption{The balance-one benchmark comparing stealing heuristics (lower is better).} +\end{figure} + +\begin{figure} + \centering + \subfloat[AMD \CFA Balance-Multi Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/nasusCFABalance-Multi.pgf}} + \label{f:BalanceMultiAMD} + } + \subfloat[Intel \CFA Balance-Multi Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/pykeCFABalance-Multi.pgf}} + \label{f:BalanceMultiIntel} + } + \caption{The balance-multi benchmark comparing stealing heuristics (lower is better).} +\end{figure} + On both balance microbenchmarks slightly less than ideal speedup compared to the non stealing variation is achieved by both the random and longest victim stealing heuristics. On the balance-multi benchmark \ref{f:BalanceMultiAMD},\ref{f:BalanceMultiIntel} the random heuristic outperforms the longest victim. @@ -1171,8 +1208,8 @@ \subsection{Executor}\label{s:executorPerf} + The microbenchmarks in this section are designed to stress the executor. The executor is the scheduler of an actor system and is responsible for organizing the interaction of executor threads to service the needs of a workload. -In the executor benchmark, 40'000 actors are created and assigned a group. -Each group of actors is a group of 100 actors who send and receive 100 messages from all other actors in their group. +In the executor benchmark, 40,000 actors are created and each actor is placed into a group of 100, who send and receive 100 messages to/from each actors in their group. Each time an actor completes all their sends and receives, they are done a round. After all groups have completed 400 rounds the system terminates.