Ignore:
Timestamp:
Mar 2, 2023, 2:09:58 PM (21 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, ast-experimental, master
Children:
397c4392
Parents:
8bb46d2 (diff), 997324c (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/colby_parsons_MMAth/text/actors.tex

    r8bb46d2 r1f951abd  
    11% ======================================================================
    22% ======================================================================
    3 \chapter{Concurrent Actors}\label{actors}
     3\chapter{Concurrent Actors}\label{s:actors}
    44% ======================================================================
    55% ======================================================================
    … …  
    88Before discussing \CFA's actor system in detail, it is important to first describe the actor model, and the classic approach to implementing an actor system.
    99
    10 \section{The Actor Model}
    11 The actor model is a paradigm of concurrent computation, where tasks are broken into units of work that are distributed to actors in the form of messages \cite{Hewitt73}. Actors execute asynchronously upon receiving a message and can modify their own state, make decisions, spawn more actors, and send messages to other actors. The actor model is an implicit model of concurrency. As such, one strength of the actor model is that it abstracts away many considerations that are needed in other paradigms of concurrent computation. Mutual exclusion, and locking are rarely relevant concepts to users of an actor model, as actors traditionally operate on local state.
    12 
    13 % C_TODO: make and insert a classic actor system diagram
     10\section{The Actor Model} % \cite{Hewitt73}
     11The actor model is a paradigm of concurrent computation, where tasks are broken into units of work that are distributed to actors in the form of messages \cite{}. Actors execute asynchronously upon receiving a message and can modify their own state, make decisions, spawn more actors, and send messages to other actors. The actor model is an implicit model of concurrency. As such, one strength of the actor model is that it abstracts away many considerations that are needed in other paradigms of concurrent computation. Mutual exclusion, and locking are rarely relevant concepts to users of an actor model, as actors typically operate on local state.
    1412
    1513\section{Classic Actor System}
    16 An implementation of the actor model with a community of actors is called an actor system. Actor systems largely follow the actor model, but differ in some ways. While the definition of the actor model provides no restrictions on message ordering, actor systems tend to guarantee that messages sent from a given actor i to actor j will arrive at actor j in the order they were sent. Another way an actor system varies from the model is that actors are often allowed to access non-local state. When this occurs it can complicate the implementation as this will break any mutual exclusion guarantees given by accessing only local state.
    17 
    18 Actor systems \cite{} have often been implemented as an actor-centric system. As such they are constructed as a set of actors that are scheduled and run on some underlying threads. Each actor has their own mailbox for receiving messages. When they receive messages in their mailbox, actors are moved from idle to ready queues and then scheduled on a thread.
     14An implementation of the actor model with a community of actors is called an actor system. Actor systems largely follow the actor model, but differ in some ways. While the definition of the actor model provides no restrictions on message ordering, actor systems tend to guarantee that messages sent from a given actor $i$ to actor $j$ will arrive at actor $j$ in the order they were sent. Another way an actor system varies from the model is that actors are often allowed to access non-local state. When this occurs it can complicate the implementation as this will break any mutual exclusion guarantees given by accessing only local state.
     15
     16\begin{figure}
     17\begin{tabular}{l|l}
     18\subfloat[Actor-centric system]{\label{f:standard_actor}\input{figures/standard_actor.tikz}} &
     19\subfloat[Message-centric system]{\label{f:inverted_actor}\raisebox{.1\height}{\input{figures/inverted_actor.tikz}}}
     20\end{tabular}
     21\caption{Classic and inverted actor implementation approaches with sharded queues.}
     22\end{figure}
     23
     24\section{\CFA Actors}
     25Actor systems \cite{} have often been implemented as an actor-centric system. As such they are constructed as a set of actors that are scheduled and run on some underlying threads. Each actor has their own queue for receiving messages, sometimes called a mailbox. When they receive messages in their mailbox, actors are moved from idle to ready queues and then scheduled on a thread to run their unit of work. This approach can be implemented with a global queue of actors, but is often implemented as each worker thread owning a queue of actors. This is known as sharding the actor queue, which is done to decrease contention across worker threads. A diagram of an actor-centric system with a sharded actor queue is shown in Figure \ref{f:standard_actor}.
     26
     27% cite parallel theatre and our paper
     28The actor system in \CFA is instead message-centric, an uses what is called an inverted actor system \cite{}. In this inverted actor system instead of each worker thread owning a queue of actors, they each own a queue of messages. This system is called inverted since in this scheme, actors belong to a message queue, whereas in the classic approach a message queue belongs to each actor. Since multiple actors belong to each message queue, messages to each actor are interleaved in the queue. In this scheme work is consumed from their queue and executed by underlying threads. In High-Performance Extended Actors \cite{} this inverted model is taken a step further and the message queues are sharded, so that each worker now instead owns a set of queues. A diagram of an inverted actor scheme with a sharded message queue is shown in Figure \ref{f:inverted_actor}. The arrows from the message queues to the actors in the diagram indicate interleaved messages addressed to each actor.
     29
     30The actor system in \CFA builds on top of the architecture laid out in High-Performance Extended Actors \cite{} and adds the following contributions:
     31
     32\begin{enumerate}[topsep=5pt,itemsep=3pt,parsep=0pt]
     33\item
     34Provides insight into the impact of envelope allocation in actor systems. In all actor systems dynamic allocation is needed to ensure that the lifetime of a unit of work persists from its creation until the unit of work is executed. This allocation is often called an envelope as it "packages" the information needed to run the unit of work, alongside any other information needed to send the unit of work, such as an actor's address or link fields for a list. This dynamic allocation occurs once per message sent. This is a large source of contention on the memory allocator since all these allocations occur concurrently. A novel data structure is used to consolidate allocations to improve performance by minimizing contention on the allocator.
     35
     36\item
     37Introduces work stealing in the inverted actor system. Work stealing in actor-centric systems tends to involve stealing one or more actors. In the inverted system the notion of stealing queues is introduced. The queue stealing is implemented such that the act of stealing work does not contend with non-stealing actors that are saturated with work.
     38
     39\item
     40Introduces and evaluates a timestamp based work stealing heuristic with the goal of maintaining non-workstealing performance in work-saturated workloads, and improving performance on unbalanced workloads.
     41
     42\item
     43Improves performance of the inverted actor system using multiple approaches to minimize contention on queues, such as queue gulping and avoiding atomic operations.
     44
     45\item
     46Creates a static-typed actor system that catches actor-message mismatches at compile time.
     47% C_TODO: create and/or mention other safety features (allocation/deadlock/etc)
     48\end{enumerate}
     49
     50\subsection{\CFA Actor Syntax}
     51\CFA is not an object oriented language and it does not have run-time type information (RTTI). As such all message sends and receives between actors occur using exact type matching. To use actors in \CFA you must \code{\#include <actors.hfa>}. To create an actor type one must define a struct which inherits from the base \code{actor} struct via the \code{inline} keyword. This is the Plan-9 C-style nominal inheritance discussed in Section \ref{s:poly}. Similarly to create a message type a user must define a struct which \code{inline}'s the base \code{message} struct.
     52
     53\begin{cfacode}
     54struct derived_actor {
     55    inline actor;       // Plan-9 C inheritance
     56};
     57void ?{}( derived_actor & this ) { // Default ctor
     58    ((actor &)this){};  // Call to actor ctor
     59}
     60
     61struct derived_msg {
     62    inline message;     // Plan-9 C nominal inheritance
     63    char word[12];
     64};
     65void ?{}( derived_msg & this, char * new_word ) { // Overloaded ctor
     66    ((message &) this){ Nodelete }; // Passing allocation to ctor
     67    strcpy(this.word, new_word);
     68}
     69
     70Allocation receive( derived_actor & receiver, derived_msg & msg ) {
     71    printf("The message contained the string: %s\n", msg.word);
     72    return Finished; // Return inished since actor is done
     73}
     74
     75int main() {
     76    start_actor_system(); // Sets up executor
     77    derived_actor my_actor;         
     78    derived_msg my_msg{ "Hello World" }; // Constructor call
     79    my_actor | my_msg;   // Send message via bar operator
     80    stop_actor_system(); // Waits until actors are finished
     81    return 0;
     82}
     83\end{cfacode}
     84
     85The above code is a simple actor program in \CFA. There is one derived actor type and one derived message type. A single message containing a string is sent from the program main to an actor. Key things to highlight include the \code{receive} signature, and calls to \code{start_actor_system}, and \code{stop_actor_system}. To define a behaviour for some derived actor and derived message type, one must declare a routine with the signature:
     86\begin{cfacode}
     87Allocation receive( derived_actor & receiver, derived_msg & msg )
     88\end{cfacode}
     89Where \code{derived_actor} and \code{derived_msg} can be any derived actor and derived message types respectively. The return value of \code{receive} must be a value from the \code{Allocation} enum:
     90\begin{cfacode}
     91enum Allocation { Nodelete, Delete, Destroy, Finished };
     92\end{cfacode}
     93The \code{Allocation} enum is a set of actions that dictate what the executor should do with a message or actor after a given behaviour has been completed. In the case of an actor, the \code{receive} routine returns the \code{Allocation} status to the executor which sets the status on the actor and takes the appropriate action. For messages, they either default to \code{Nodelete}, or they can be passed an \code{Allocation} via the \code{message} constructor. Message state can be updated via a call to:
     94\begin{cfacode}
     95void set_allocation( message & this, Allocation state )
     96\end{cfacode}
     97
     98The following describes the use of each of the \code{Allocation} values:
     99
     100\begin{description}
     101\item[\LstBasicStyle{\textbf{Nodelete}}]
     102tells the executor that no action is to be taken with regard to a message or actor with this status. This indicates that the actor will receive future behaviours, and that a message may be reused.
     103
     104\item[\LstBasicStyle{\textbf{Delete}}]
     105tells the executor to call the appropriate destructor and then deallocate the respective actor or message. This status is typically used with dynamically allocated actors and messages.
     106
     107\item[\LstBasicStyle{\textbf{Destroy}}]
     108tells the executor to call the object's destructor. The executor will not deallocate the respective actor or message. This status is typically used with dynamically allocated actors and messages whose storage will be reused.
     109
     110\item[\LstBasicStyle{\textbf{Finished}}]
     111tells the executor to mark the respective actor as being finished executing. In this case the executor will not call any destructors or deallocate any objects. This status is used when the actors are stack allocated or if the user wants to manage deallocation of actors themselves. In the case of messages, \code{Finished} is no different than \code{Nodelete} since the executor does not need to track if messages are done work.
     112\end{description}
     113
     114For the actor system to gracefully terminate, all actors must have returned a status other than \code{Nodelete}. Once an actor's allocation status has been set to something other than \code{Nodelete}, it is erroneous for the actor to receive a message. Similarly messages cannot be safely reused after their related behaviour if their status is not \code{Nodelete}. Note, it is safe to construct a message with a non-\code{Nodelete} status since the executor will only take the appropriate allocation action after a message has been delivered.
     115
     116The calls to \code{start_actor_system}, and \code{stop_actor_system} mark the start and end of a \CFA actor system. The call to \code{start_actor_system} sets up the executor and worker threads for the actor system. \code{start_actor_system} has three overloaded signatures which all start the actor system, but vary in executor configuration:
     117
     118\noindent\code{void start_actor_system()} configures the executor with one underlying worker thread and processor.
     119
     120\noindent\code{void start_actor_system( size_t num_thds )} configures the executor with \code{num_thds} underlying processors and \code{num_thds} worker threads. It chooses amount of queue sharding as a function of \code{num_thds}.
     121
     122\noindent\code{void start_actor_system( executor & this )} allows the user to allocate, configure, and pass an executor so that they have full control of executor parameterization. Executor configuration options include number of worker threads, number of queues, number of processors, and a few other toggles.
     123
     124All actors must be created after calling \code{start_actor_system} so that the executor can keep track of the number of actors that have been allocated but have not yet terminated.
     125
     126All message sends are done using the bar operater, \ie |. The signature of the bar operator is:
     127\begin{cfacode}
     128Allocation ?|?( derived_actor & receiver, derived_msg & msg )
     129\end{cfacode}
     130
     131An astute eye will notice that this is the same signature as the \code{receive} routine which is no coincidence. The \CFA compiler generates a bar operator routine definition and forward declaration of the bar operator for each \code{receive} routine that has the appropriate signature. The generated routine packages the message and actor in an \hyperref[s:envelope]{envelope} and adds it to the executor's queues via an executor routine. As part of packaging the envelope, the bar operator routine sets a function pointer in the envelope to point to the appropriate receive routine for given actor and message types.
     132
     133\subsection{\CFA Executor}\label{s:executor}
     134This section will describe the basic architecture of the \CFA executor. Any discussion of work stealing is omitted until Section \ref{s:steal}. The executor of an actor system is the scheduler that organizes where actors behaviours are run and how messages are sent and delivered. In \CFA the executor lays out actors across the sharded message queues in round robin order as they are created. The message queues are split across worker threads in equal chunks, or as equal as possible if the number of message queues is not divisible by the number of workers threads.
     135
     136\begin{figure}
     137\begin{center}
     138\input{figures/gulp.tikz}
     139\end{center}
     140\caption{Diagram of the queue gulping mechanism.}
     141\label{f:gulp}
     142\end{figure}
     143
     144Each worker thread iterates over its own message queues until it finds one that contains messages. At this point the worker thread \newterm{gulps} the queue. A \newterm{gulp} is a term for consuming the contents of message queue and transferring them to the local queue of worker thread. After the gulp is done atomically, this allows the worker thread to process the queue locally without any need for atomicity until the next gulp. Messages can be added to the queue that was gulped in parallel with the processing of the local queue. Additionally, prior to each gulp, the worker non-atomically checks if a queue is empty before attempting to gulp it. Between this and the gulp, the worker avoids many potentially costly lock acquisitions. An example of the queue gulping operation is shown in Figure \ref{f:gulp} where a worker thread gulps queue 0 and begins to process it locally.
     145
     146To process its local queue, a worker thread takes each unit of work off the queue and executes it. Since all messages to a given actor will be in the same queue, this guarantees atomicity across behaviours of that actor since it can only execute on one thread at a time. After running behaviour, the worker thread looks at the returned allocation status and takes the corresponding action. Once all actors have marked themselves as being finished the executor initiates shutdown by inserting a sentinel value into the message queues. Once a worker thread sees a sentinel it stops running. After all workers stop running the actor system shutdown is complete.
     147
     148\subsection{Envelopes}\label{s:envelope}
     149In actor systems messages are sent and received by actors. When a actor receives a message it  executes its behaviour that is associated with that message type. However the unit of work that stores the message, the receiving actor's address, and other pertinent information needs to persist between send and the receive. Furthermore the unit of work needs to be able to be stored in some fashion, usually in a queue, until it is executed by an actor. All these requirements are fulfilled by a construct called an envelope. The envelope wraps up the unit of work and also stores any information needed by data structures such as link fields. To meet the persistence requirement the envelope is dynamically allocated and cleaned up after it has been delivered and its payload has run.
     150
     151One may ask, "Could the link fields and other information be stored in the message?". This is a good question to ask since messages also need to have a lifetime that persists beyond the work it delivers. However, if one were to use messages as envelopes then a message would not be able to be sent to multiple actors at a time. Therefore this approach would just push the allocation into another location, and require the user to dynamically allocate a message for every send, or require careful ordering to allow for message reuse.
     152
     153This frequent allocation of envelopes with each message send between actors results in heavy contention on the memory allocator. As such, a way to alleviate contention on the memory allocator could result in performance improvement. Contention was reduced using a novel data structure that called a \newterm{copy queue}.
     154
     155\subsubsection{The Copy Queue}
     156The copy queue is a thin layer over a dynamically sized array that is designed with the envelope use case in mind. A copy queue supports the typical queue operations of push/pop but in a different way than a typical array based queue. The copy queue is designed to take advantage of the \hyperref[s:executor]{gulping} pattern. As such the amortized rutime cost of each push/pop operation for the copy queue is $O(1)$. In contrast, a naive array based queue often has either push or pop cost $O(n)$ and the other cost $O(1)$ since for at least one of the operations all the elements of the queue have to be shifted over. Since the worker threads gulp each queue to operate on locally, this creates a usage pattern of the queue where all elements are popped from the copy queue without any interleaved pushes. As such, during pop operations there is no need to shift array elements. An index is stored in the copy queue data structure which keeps track of which element to pop next allowing pop to be $O(1)$. Push operations are amortized $O(1)$ since pushes may cause doubling reallocations of the underlying dynamic sized array.
     157
     158% C_TODO: maybe make copy_queue diagram
     159
     160Since the copy queue is an array, envelopes are allocated first on the stack and then copied into the copy queue to persist until they are no longer needed. For a fixed message throughput workload, once the copy queues grow in size to facilitate the number of messages in flight, there are no longer any dynamic allocations occuring in the actor system. One problem that arises with this approach is that this array based approach will often allocate more storage than what is needed. Comparitively the individual envelope allocations of a list based queue mean that the actor system will always use the minimum amount of heap space needed and will clean up eagerly. Additionally, a workload with variable message throughput could cause copy queues to allocate large amounts of space to accomodate the peaks of the throughput, even if most of that storage is not needed for the rest of the workload's execution.
     161
     162To mitigate this a memory reclamation scheme was introduced. Initially the memory reclamation naively reclaimed one index of the array per gulp if the array size was above a low fixed threshold. This approach had a problem. The high memory usage watermark nearly doubled with this change! The issue with this approach can easily be highlighted with an example. Say that there is a fixed throughput workload where a queue never has more than 19 messages at a time. If the copy queue starts with a size of 10, it will end up doubling at some point to size 20 to accomodate 19 messages. However, after 2 gulps and subsequent reclamations the array would be size 18. The next time 19 messages are enqueued, the array size is doubled to 36! To avoid this issue a second check was added to reclamation. Each copy queue started tracking the utilization of their array size. Reclamation would only occur if less than half of the array was being utilized. In doing this the reclamation scheme was able to achieve a lower high watermark and a lower overall memory utilization when compared to the non-reclamation copy queues. However, the use of copy queues still incurs a higher memory cost than the list based queueing. With the inclusion of a memory reclamation scheme the increase in memory usage is reasonable considering the performance gains and will be discussed further in Section \ref{s:actor_perf}.
     163
     164\subsection{Work Stealing}\label{s:steal}
     165Work stealing is a scheduling strategy that attempts to load balance, and increase resource untilization by having idle threads steal work. There are many parts that make up a work stealing actor scheduler, but the two that will be highlighted in this work are the stealing mechanism and victim selection.
     166
     167% C_TODO enter citation for langs
     168\subsubsection{Stealing Mechanism}
     169In this discussion of work stealing the worker being stolen from will be referred to as the \newterm{victim} and the worker stealing work will be called the \newterm{thief}. The stealing mechanism presented here differs from existing work stealing actor systems due the inverted actor system. Other actor systems such as Akka \cite{} and CAF \cite{} have work stealing, but since they use an classic actor system that is actor-centric, stealing work is the act of stealing an actor from a dequeue. As an example, in CAF, the sharded actor queue is a set of double ended queues (dequeues). Whenever an actor is moved to a ready queue, it is inserted into a worker's dequeue. Workers then consume actors from the dequeue and execute their behaviours. To steal work, thieves take one or more actors from a victim's dequeue. This action creates contention on the dequeue, which can slow down the throughput of the victim. The notion of which end of the dequeue is used for stealing, consuming, and inserting is not discussed since it isn't relevant. By the pigeon hole principle there are three dequeue operations (push/victim pop/thief pop) that can occur concurrently and only two ends to a dequeue, so work stealing being present in a dequeue based system will always result in a potential increase in contention on the dequeues.
     170
     171% C_TODO: insert stealing diagram
     172
     173In \CFA, the work stealing is unique, since existing work stealing systems do not use the inverted actor system. While other systems are concerned with stealing actors, the \CFA actor system steals queues. The goal of the \CFA actor work stealing mechanism is to have a zero-victim-cost stealing mechanism. This does not means that stealing has no cost. This goal is to ensure that stealing work does not impact the performance of victim workers. This means that thieves can not contend with victims, and that victims should perform no stealing related work unless they become a thief. In theory this goal is not achieved, but results will be presented that show the goal is achieved in practice. In \CFA's actor system workers own a set of sharded queues which they iterate over and gulp. If a worker has iterated over the queues they own twice without finding any work, they try to steal a queue from another worker. Stealing a queue is done wait-free with a few atomic instructions that can only create contention with other stealing workers. To steal a queue a worker does the following:
     174\begin{enumerate}[topsep=5pt,itemsep=3pt,parsep=0pt]
     175\item
     176The thief chooses a victim.
     177
     178\item
     179The thief starts at a random index in the array of the victim's queues and searches for a candidate queue. A candidate queue is any queue that is not empty, is not being stolen by another thief, and is not being processed by the victim. These are not strictly enforced rules. The candidate is identified non-atomically and as such queues that do not satisfy these rules may be stolen. However, steals that do not meet these requirements do not affect correctness so they are allowed and do not constitute failed steals as the queues will still be swapped.
     180
     181\item
     182Once a candidate queue is chosen, the thief attempts a wait-free swap of the victim's queue and a random on of the thief's queues. This swap can fail. If the swap is successful the thief swaps the two queues. If the swap fails, another thief must have attempted to steal one of the two queues being swapped. Failing to steal is good in this case since stealing a queue that was just swapped would likely result in stealing an empty queue.
     183\end{enumerate}
     184
     185% C_TODO insert array of queues diagram
     186Once a thief fails or succeeds in stealing a queue, it goes back to its own set of queues and iterates over them again. It will only try to steal again once it has completed two consecutive iterations over its owned queues without finding any work. The key to the stealing mechnism is that the queues can still be operated on while they are being swapped. This elimates any contention between thieves and victims. The first key to this is that actors and workers maintain two distinct arrays of references to queues. Actors will always receive messages via the same queues. Workers, on the other hand will swap the pointers to queues in their shared array and operate on queues in the range of that array that they own. Swapping queues is a matter of atomically swapping two pointers in the worker array. As such pushes to the queues can happen concurrently during the swap since pushes happen via the actor queue references.
     187
     188Gulping can also occur during queue swapping, but the implementation requires more nuance than the pushes. When a worker is not stealing it iterates across its own range of queues and gulps them one by one. When a worker operates on a queue it first copies the current pointer from the worker array of references to a local variable. It then uses that local variable for all queue operations until it moves to the next index of its range of the queue array. This ensures that any swaps do not interrupt gulping operations, however this introduces a correctness issue. If any behaviours from a queue are run by two workers at a time it violates both mutual exclusion and the actor ordering guarantees. As such this must be avoided. To avoid this each queue has a \code{being_processed} flag that is atomically set to \code{true} when a queue is gulped. The flag indicates that a queue is being processed locally and is set back to \code{false} once the local processing is finished. If a worker attempts to gulp a queue and finds that the \code{being_processed} flag is \code{true}, it does not gulp the queue and moves on to the next queue in its range. This is a source of contention between victims and thieves since a thief may steal a queue and set \code{being_processed} to \code{true} between a victim saving a pointer to a queue and gulping it. However, the window for this race is very small, making this contention rare. This is why the claim is made that this mechanism is zero-victim-cost in practice but not in theory. By collecting statistics on failed gulps due to the \code{being_processed} flag, it is found that this contention occurs ~0.05\% of the time when a gulp occurs. Hence, the claim is made that this stealing mechanism has zero-victim-cost in practice.
     189
     190
     191\subsubsection{Queue Swap Correctness}
     192Given the wait-free swap used is novel, it is important to show that it is correct. Firstly, it is clear to show that the swap is wait-free since all workers 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 given up on stealing. \CFA-style pseudocode for the queue swap is presented below. The swap uses compare-and-swap (\code{CAS}) which is just pseudocode for C's \code{__atomic_compare_exchange_n}. A pseudocode implementation of \code{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:
     193
     194\begin{cfacode}
     195void swap( uint victim_idx, uint my_idx  ) {
     196    // Step 0:
     197    work_queue * my_queue = request_queues[my_idx];
     198    work_queue * vic_queue = request_queues[victim_idx];
     199    // Step 2:
     200    request_queues[my_idx] = 0p;
     201    // Step 3:
     202    request_queues[victim_idx] = my_queue;
     203    // Step 4:
     204    request_queues[my_idx] = vic_queue;
     205}
     206\end{cfacode}
     207
     208Step 1 is missing in the sequential example since in only matter 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.
     209
     210\begin{cfacode}
     211// This routine is atomic
     212bool CAS( work_queue ** ptr, work_queue ** old, work_queue * new ) {
     213    if ( *ptr != *old )
     214        return false;
     215    *ptr = new;
     216    return true;
     217}
     218
     219bool try_swap_queues( worker & this, uint victim_idx, uint my_idx ) with(this) {
     220    // Step 0:
     221    // request_queues is the shared array of all sharded queues
     222    work_queue * my_queue = request_queues[my_idx];
     223    work_queue * vic_queue = request_queues[victim_idx];
     224
     225    // Step 1:
     226    // If either queue is 0p then they are in the process of being stolen
     227    // 0p is CForAll's equivalent of C++'s nullptr
     228    if ( vic_queue == 0p ) return false;
     229
     230    // Step 2:
     231    // Try to set thief's queue ptr to be 0p.
     232    // If this CAS fails someone stole thief's queue so return false
     233    if ( !CAS( &request_queues[my_idx], &my_queue, 0p ) )
     234        return false;
     235   
     236    // Step 3:
     237    // Try to set victim queue ptr to be thief's queue ptr.
     238    // If it fails someone stole the other queue, so fix up then return false
     239    if ( !CAS( &request_queues[victim_idx], &vic_queue, my_queue ) ) {
     240        request_queues[my_idx] = my_queue; // reset queue ptr back to prev val
     241        return false;
     242    }
     243
     244    // Step 4:
     245    // Successfully swapped.
     246    // Thief's ptr is 0p so no one will touch it
     247    // Write back without CAS is safe
     248    request_queues[my_idx] = vic_queue;
     249    return true;
     250}
     251\end{cfacode}\label{c:swap}
     252
     253Now consider the concurrent implementation of the swap.
     254\begin{enumerate}[topsep=5pt,itemsep=3pt,parsep=0pt]
     255\item
     256Step 0 is the same as the sequential example, and the thief stores local copies of the two pointers to be swapped.
     257\item
     258Step 1 verifies that the stored copy of the victim queue pointer, \code{vic_queue}, is valid. If \code{vic_queue} is equal to \code{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, \code{my_queue} can never be equal to \code{0p} at this point since thieves only set their own queues pointers to \code{0p} when stealing. At no other point will a queue pointer be set to \code{0p}. Since each worker owns a disjoint range of the queue array, it is impossible for \code{my_queue} to be \code{0p}.
     259\item
     260Step 2 attempts to set the thief's queue pointer to \code{0p} via \code{CAS}. The \code{CAS} will only fail if the thief's queue pointer is no longer equal to \code{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 \code{CAS} succeeds then the thief's queue pointer will now be \code{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 \code{0p}.
     261\item
     262Step 3 attempts to set the victim's queue pointer to be \code{my_queue} via \code{CAS}. If the \code{CAS} succeeds then the victim's queue pointer has been set and swap can no longer fail. If the \code{CAS} fails then the thief's queue pointer must be restored to its previous value before returning.
     263\item
     264Step 4 sets the thief's queue pointer to be \code{vic_queue} completing the swap.
     265\end{enumerate}
     266
     267\begin{theorem}
     268The presented swap is correct and concurrently safe in both the success and failure cases.
     269\end{theorem}
     270
     271Correctness of the swap is shown through the existence of an invariant. The invariant is that when a queue pointer is set to \code{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. 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 \code{0p} to one of their queue pointers. This queue pointer cannot be \code{0p}. As stated above, \code{my_queue} is never equal to \code{0p} since thieves will only write \code{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 \code{my_queue} to the victim's queue pointer. If the current value of the victim's queue pointer is \code{0p}, then the CAS will fail since \code{vic_queue} cannot be equal to \code{0p} because of the check in step 1. Therefore in the success case where the \code{CAS} succeeds, the value of the victim's queue pointer must not be \code{0p}. As such, the write will never overwrite a value of \code{0p}, hence the invariant is held in the \code{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 \code{0p} queue pointer and they are being set by the same thief that set the pointer to \code{0p}.
     272
     273Given 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 \code{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 \code{vic_queue} due to the use of \code{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 \code{0p} pointer.
     274
     275In the failed case the outcome is correct in steps 1 and 2 since no writes have occured 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 \code{0p} write in step 2, thanks to the invariant that makes the write back to the \code{0p} pointer safe.
     276
     277\subsubsection{Stealing Guarantees}
     278
     279% C_TODO insert graphs for each proof
     280Given that the stealing operation can potentially fail, it is important to discuss the guarantees provided by the stealing implementation. Given a set of $N$ swaps a set of connected directed graphs can be constructed where each vertex is a queue and each edge is a swap directed from a thief queue to a victim queue. Since each thief can only steal from one victim at a time, each vertex can only have at most one outgoing edge. A corollary that can be drawn from this, is that there are at most $V$ edges in this constructed set of connected directed graphs, where $V$ is the total number of vertices.
     281
     282\begin{theorem}
     283Given $M$ thieves queues all attempting to swap with one victim queue, and no other swaps occuring that involve these queues, at least one swap is guaranteed to succeed.
     284\end{theorem}\label{t:one_vic}
     285First 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 \code{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 \code{CAS} will win the race and successfully swap the queue pointer. Since it is the first one to \code{CAS} and \code{CAS} is atomic, there is no way for the \code{CAS} to fail since no other thief could have written to the victim's queue pointer and the victim did not write to the pointer since they aren't stealing. Hence at least one swap is guaranteed to succeed in this case.
     286
     287\begin{theorem}
     288Given $M$ > 1, ordered queues pointers all attempting to swap with the queue in front of them in the ordering, except the first queue, and no other swaps occuring that involve these queues, at least one swap is guaranteed to succeed.
     289\end{theorem}\label{t:vic_chain}
     290This is a proof by contradiction. Assume no swaps occur. Then all thieves must have failed at step 1, step 2 or step 3. For a given thief $b$ to fail at step 1, thief $b + 1$ must have succeded at step 2 before $b$ executes step 0. Hence, not all thieves can fail at step 1. Furthermore if a thief $b$ fails at step 1 it logically splits the chain into two subchains $0 <- b$ and $b + 1 <- M - 1$, where $b$ has become solely a victim since its swap has failed and it did not modify any state. There must exist at least one chain containing two or more queues after since it is impossible for a split to occur both before and after a thief, since that requires failing at step 1 and succeeding at step 2. Hence, without loss of generality, whether thieves succeed or fail at step 1, this proof can proceed inductively.
     291
     292For a given thief $i$ to fail at step 2, it means that another thief $j$ had to have written to $i$'s queue pointer between $i$'s step 0 and step 2. The only way for $j$ to write to $i$'s queue pointer would be if $j$ was stealing from $i$ and had successfully finished step 3. If $j$ finished step 3 then the at least one swap was successful. Therefore all thieves did not fail at step 2. Hence all thieves must successfully complete step 2 and fail at step 3. However, since the first worker, thief $0$, is solely a victim and not a thief, it does not change the state of any of its queue pointers. Hence, in this case thief $1$ will always succeed in step 3 if all thieves succeed in step 2. Thus, by contradiction with the earlier assumption that no swaps occur, at least one swap must succeed.
     293
     294\begin{theorem}
     295Given a set of $M > 1$ swaps occuring that form a single directed connected graph. At least one swap is guaranteed to suceed if and only if the graph does not contain a cycle.
     296\end{theorem}\label{t:vic_cycle}
     297First the reverse direction is proven. If the graph does not contain a cycle, then there must be at least one successful swap. Since the graph contains no cycles and is finite in size, then there must be a vertex $A$ with no outgoing edges. The graph can then be formulated as a tree with $A$ at the top since each node only has at most one outgoing edge and there are no cycles. The forward direction is proven by contradiction in a similar fashion to \ref{t:vic_chain}. Assume no swaps occur. Similar to \ref{t:vic_chain}, this graph can be inductively split into subgraphs of the same type by failure at step 1, so the proof proceeds without loss of generality. Similar to \ref{t:vic_chain} the conclusion is drawn that all thieves must successfully complete step 2 for no swaps to occur, since for step 2 to fail, a different thief has to successfully complete step 3, which would imply a successful swap. Hence, the only way forward is to assume all thieves successfully complete step 2. Hence for there to be no swaps all thieves must fail step 3. However, since $A$ has no outgoing edges, since the graph is connected there must be some $K$ such that $K < M - 1$ thieves are attempting to swap with $A$. Since all $K$ thieves have passed step 2, similar to \ref{t:one_vic} the first one of the $K$ thieves to attempt step 3 is guaranteed to succeed. Thus, by contradiction with the earlier assumption that no swaps occur, if the graph does not contain a cycle, at least one swap must succeed.
     298
     299The forward direction is proven by contrapositive. If the graph contains a cycle then there exists a situation where no swaps occur. This situation is constructed. Since all vertices have at most one outgoing edge the cycle must be directed. Furthermore, since the graph contains a cycle all vertices in the graph must have exactly one outgoing edge. This is shown through construction of an aribtrary cyclic graph. The graph contains a directed cycle by definition, so the construction starts with $T$ vertices in a directed cycle. Since the graph is connected, and each vertex has at most one outgoing edge, none of the vertices in the cycle have available outgoing edges to accomodate new vertices with no outgoing edges. Any vertices added to the graph must have an outgoing edge to connect, leaving the resulting graph with no available outgoing edges. Thus, by induction all vertices in the graph must have exactly one outgoing edge. Hence all vertices are thief queues. Now consider the case where all thieves successfully complete step 0-1, and then they all complete step 2. At this point all thieves are attempting to swap with a queue pointer whose value has changed to \code{0p}. If all thieves attempt the \code{CAS} before any write backs, then they will all fail. Thus, by contrapositive, if the graph contains a cycle then there exists a situation where no swaps occur. Hence, at least one swap is guaranteed to suceed if and only if the graph does not contain a cycle.
     300
     301% C_TODO: go through and use \paragraph to format to make it look nicer
     302\subsubsection{Victim Selection}
     303In any work stealing algorithm thieves have some heuristic to determine which victim to choose from. 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 \newterm{longest victim} and compares it to randomized work stealing. The longest victim heuristic maintains a timestamp per worker thread 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}. Additonally, 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.
     304
     305\subsection{Safety}
     306
     307\subsection{Performance}\label{s:actor_perf}
Note: See TracChangeset for help on using the changeset viewer.