Changes in / [4852232:17c13b9]


Ignore:
Location:
doc/theses/colby_parsons_MMAth/text
Files:
6 edited

Legend:

Unmodified
Added
Removed

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

    r4852232 r17c13b9  
    251251Therefore, it is up to the actor program to manage message life-time across receives.
    252252However, for a message to appear on multiple message queues, it needs an arbitrary number of associated destination behaviours.
    253 Hence, there is the concept of an envelope, which is dynamically allocated on each send, that wraps a message with any extra implementation fields needed to persist between send and receive.
    254 Managing the envelope is straightforward because it is created at the send and deleted after the receive, \ie there is 1:1 relationship for an envelope and a many to one relationship for a message.
     253Hence, there is the concept of an envelop, which is dynamically allocated on each send, that wraps a message with any extra implementation fields needed to persist between send and receive.
     254Managing the envelop is straightforward because it is created at the send and deleted after the receive, \ie there is 1:1 relationship for an envelop and a many to one relationship for a message.
    255255
    256256% In actor systems, messages are sent and received by actors.
    … …  
    342342
    343343Users could be expected to write the @?|?@ routines, but this approach is error prone and creates maintenance issues.
    344 As a stopgap until the \CFA type-system matures, a workaround was created using a template-like approach, where the compiler generates a matching @?|?@ routine for each @receive@ routine it finds with the correct actor/message type-signature.
    345 This workaround is outside of the type system, but performs a type-system like action.
     344Until the \CFA type-system matures, I created a workaround using a template-like approach, where the compiler generates a matching @?|?@ routine for each @receive@ routine it finds with the correct actor/message type-signature.
     345This workaround is outside of the type system, but performing a type-system like action.
    346346The workaround requires no annotation or additional code to be written by users;
    347347thus, it resolves the maintenance and error problems.
    … …  
    352352The routine sets @rec_fn@ to the matching @receive@ routine using the left-hand type to perform the selection.
    353353Then the routine packages the actor and message, along with the receive routine into an envelope.
    354 Finally, the envelope is added to the executor queue designated by the actor using the executor routine @send@.
     354Finally, the envelop is added to the executor queue designated by the actor using the executor routine @send@.
    355355
    356356\begin{figure}
    … …  
    396396\subsection{Actor Termination}\label{s:ActorTerm}
    397397During a message send, the receiving actor and message being sent are stored via pointers in the envelope.
    398 These pointers have the base actor and message types, so type information of the derived actor and message is lost and must be recovered later when the typed receive routine is called.
     398These pointers are the base actor and message types, so type information of the derived actor and message is lost and must be recovered later when the typed receive routine is called.
    399399After the receive routine is done, the executor must clean up the actor and message according to their allocation status.
    400400If the allocation status is @Delete@ or @Destroy@, the appropriate destructor must be called by the executor.
    … …  
    402402the derived type of the actor or message is not available to the executor, but it needs to call the derived destructor.
    403403This requires downcasting from the base type to the derived type, which requires a virtual system.
    404 To accomplish the downcast, a rudimentary destructor-only virtual system was implemented in \CFA as part of this work.
     404To accomplish the dowcast, I implemented a rudimentary destructor-only virtual system in \CFA.
    405405This virtual system is used via Plan-9 inheritance of the @virtual_dtor@ type, shown in Figure~\ref{f:VirtDtor}.
    406406The @virtual_dtor@ type maintains a pointer to the start of the object, and a pointer to the correct destructor.
    … …  
    517517
    518518Since 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.
    519 For many workloads, the copy queues grow in size to facilitate the average number of messages in flight and there are no further dynamic allocations.
     519For many workload, the copy queues grow in size to facilitate the average number of messages in flight and there is no further dynamic allocations.
    520520The downside of this approach is that more storage is allocated than needed, \ie each copy queue is only partially full.
    521521Comparatively, the individual envelope allocations of a list-based queue mean that the actor system always uses the minimum amount of heap space and cleans up eagerly.
    … …  
    662662However, any form of locking here creates contention between thief and victim.
    663663
    664 The alternative to locking is allowing the race and resolving it lazily.
     664The alternative to locking is allowing the race and resolving it lazily (lock-free approach).
    665665% 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.
    666666% Furthermore, after a thief steals, there is moment when victim gulps but the queue no longer
    … …  
    12621262Because $Z$ is contiguous in memory, there can be small cache write-contention at the row boundaries.
    12631263
    1264 Figures~\ref{f:MatrixAMD} and \ref{f:MatrixIntel} show the matrix-multiply results.
     1264Figures~\ref{f:MatrixAMD} and \ref{f:MatrixIntel} show the matrix multiple results.
    12651265There are two groupings with Akka and ProtoActor being slightly slower than \uC, \CFA, and CAF.
    12661266On the Intel, there is an unknown divergence between \uC and \CFA/CAF at 24 cores.

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

    r4852232 r17c13b9  
    106106\item A @flush@ routine that delivers copies of an element to all waiting consumers, flushing the buffer.
    107107Programmers use this mechanism to broadcast a sentinel value to multiple consumers.
    108 Additionally, the @flush@ routine is more performant than looping around the @insert@ operation since it can deliver the elements without having to reacquire mutual exclusion for each element sent.
     108Additionally, the @flush@ routine is more performant then looping around the @insert@ operation since it can deliver the elements without having to reacquire mutual exclusion for each element sent.
    109109
    110110\item Go-style @?<<?@ shorthand operator for inserting and removing.

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

    r4852232 r17c13b9  
    1414\begin{enumerate}
    1515\item The mutex statement, which provides performant and deadlock-free multiple lock acquisition.
    16 \item Channels with comparable performance to Go, that have safety and productivity features including deadlock detection, and an easy-to-use exception-based channel @close@ routine.
     16\item Channels with comparable performance to Go, that have safety and productivity features including deadlock detection and an easy-to-use exception-based channel @close@ routine.
    1717\item An in-memory actor system that achieved the lowest latency message send of systems tested due to the novel copy-queue data structure. The actor system presented has built-in detection of six common actor errors, and it has good performance compared to other systems on all benchmarks.
    1818\item A @waituntil@ statement which tackles the hard problem of allowing a thread to safely synchronously wait for some set of concurrent resources.

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

    r4852232 r17c13b9  
    1414This thesis builds on top of that foundation by providing a suite of high-level concurrent features.
    1515The features include a @mutex@ statement, channels, a @waituntil@ statement, and an actor system.
    16 All of these features exist in other programming languages in some shape or form, however this thesis extends the original ideas by improving performance, productivity, and safety.
     16All of these features exist in other programming in some shape or form, however this thesis extends the original ideas by improving performance, productivity, and safety.

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

    r4852232 r17c13b9  
    8383\end{figure}
    8484
    85 Like Java, \CFA monitors have \Newterm{multi-acquire} semantics so the thread in the monitor may acquire it multiple times without deadlock, allowing recursion and calling of other MX functions.
     85Like Java, \CFA monitors have \Newterm{multi-acquire} semantics so the thread in the monitor may acquire it multiple times without deadlock, allowing recursion and calling other MX functions.
    8686For robustness, \CFA monitors ensure the monitor lock is released regardless of how an acquiring function ends, normal or exceptional, and returning a shared variable is safe via copying before the lock is released.
    8787Monitor objects can be passed through multiple helper functions without acquiring mutual exclusion, until a designated function associated with the object is called.
    8888\CFA functions are designated MX by one or more pointer/reference parameters having qualifier @mutex@.
    8989Java members are designated MX with \lstinline[language=java]{synchronized}, which applies only to the implicit receiver parameter.
    90 In the example above, the increment and setter operations need mutual exclusion, while the read-only getter operation is not MX because reading an integer is atomic.
     90In the example, the increment and setter operations need mutual exclusion, while the read-only getter operation is not MX because reading an integer is atomic.
    9191
    9292As stated, the non-object-oriented nature of \CFA monitors allows a function to acquire multiple mutex objects.

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

    r4852232 r17c13b9  
    163163
    164164Another example of programming-language \gls{synch_multiplex} is Go using a @select@ statement with channels~\cite{go:selectref}.
    165 Figure~\ref{l:BB_Go} shows the outline of a bounded buffer administrator implemented with a Go routine.
     165Figure~\ref{l:BB_Go} shows the outline of a bounded buffer implemented with a Go routine.
    166166Here two channels are used for inserting and removing by client producers and consumers, respectively.
    167 (The @done@ channel is used to synchronize with the program main.)
     167(The @term@ and @stop@ channels are used to synchronize with the program main.)
    168168Go's @select@ has the same exclusive-or semantics as the ALT primitive from Occam and associated code blocks for each clause like ALT and Ada.
    169169However, unlike Ada and ALT, Go does not provide guards for the \lstinline[language=go]{case} clauses of the \lstinline[language=go]{select}.
    170 As such, the exponential blowup can be seen comparing Go and \uC in Figure~\label{f:AdaMultiplexing}.
    171170Go also provides a timeout via a channel and a @default@ clause like Ada @else@ for asynchronous multiplexing.
    172171
    … …  
    176175\begin{lrbox}{\myboxA}
    177176\begin{lstlisting}[language=go,literate=]
    178 insert := make( chan int )
    179 remove := make( chan * int )
    180 buffer := make( chan int Size )
    181 done := make( chan int )
    182 count := 0
    183 func in_buf( int val ) {
    184     buffer <- val
    185     count++
    186 }
    187 func out_buf( int * ptr ) {
    188     *ptr := <-buffer
    189     count--
    190 }
    191 func BoundedBuffer {
    192     L: for {
    193         if ( count < Size && count > 0 ) {
    194             select { // wait for message
    195                 case i := <- insert: in_buf( i )
    196                 case p := <- remove: out_buf( p )
    197                 case <- done: break L
    198             }
    199         } else if ( count < Size ) {
    200             select { // wait for message
    201                 case i := <- insert: in_buf( i )
    202                 case <- done: break L
    203             }
    204         } else ( count > 0 ) {
    205             select { // wait for message
    206                 case p := <- remove: out_buf( p )
    207                 case <- done: break L;
    208             }
    209         }
    210     }
    211     done <- 0
    212 }
    213177func main() {
    214         go BoundedBuffer() // start administrator
     178        insert := make( chan int, Size )
     179        remove := make( chan int, Size )
     180        term := make( chan string )
     181        finish := make( chan string )
     182
     183        buf := func() {
     184                L: for {
     185                        select { // wait for message
     186                          case i = <- buffer:
     187                          case <- term: break L
     188                        }
     189                        remove <- i;
     190                }
     191                finish <- "STOP" // completion
     192        }
     193        go buf() // start thread in buf
    215194}
    216195
    … …  
    224203\begin{lstlisting}[language=uC++=]
    225204_Task BoundedBuffer {
    226         int * buffer;
    227         int front = back = count = 0;
     205        ... // buffer declarations
     206        int count = 0;
    228207  public:
    229     // ... constructor implementation
    230208        void insert( int elem ) {
    231                 buffer[front] = elem;
    232         front = ( front + 1 ) % Size;
     209                ... // add to buffer
    233210                count += 1;
    234211        }
    235212        int remove() {
    236                 int ret = buffer[back];
    237         back = ( back + 1 ) % Size;
     213                ... // remove and return from buffer
    238214                count -= 1;
    239         return ret;
    240215        }
    241216  private:
    … …  
    265240The @_Select@ statement extends the ALT/Go @select@ by offering both @and@ and @or@ semantics, which can be used together in the same statement.
    266241Both @_Accept@ and @_Select@ statements provide guards for multiplexing clauses, as well as, timeout, and @else@ clauses.
    267 Figure~\ref{l:BB_uC++} shows the outline of a bounded buffer administrator implemented with \uC @_Accept@ statements.
    268242
    269243There are other languages that provide \gls{synch_multiplex}, including Rust's @select!@ over futures~\cite{rust:select}, OCaml's @select@ over channels~\cite{ocaml:channel}, and C++14's @when_any@ over futures~\cite{cpp:whenany}.
    … …  
    767741                when_conditions[node] = true;
    768742
    769 if ( any when_conditions[node] are true ) {
    770     select_nodes nodes[N];                                                                      $\C{// declare N select nodes}$
    771     try {
    772         // ... set statuses for nodes with when_conditions[node] == false ...
    773 
    774         for ( node in nodes )                                                           $\C{// register nodes}$
    775             if ( when_conditions[node] )
    776                 register_select( resource, node );
    777 
    778         while ( !check_completion( nodes ) ) {  $\C{// check predicate}$
    779             // block
    780             for ( resource in waituntil statement ) {   $\C{// run true code blocks}$
    781                 if ( check_completion( nodes ) ) break;
    782                 if ( resource is avail )
    783                     try {
    784                         if( on_selected( resource ) )   $\C{// conditionally run block}$
    785                             run code block
    786                     } finally                                                   $\C{// for exception safety}$
    787                         unregister_select( resource, node ); $\C{// immediate unregister}$
    788             }
     743if ( any when_conditions[node] == true ) {
     744
     745select_nodes nodes[N];                                                                  $\C{// declare N select nodes}$
     746try {
     747    // ... set statuses for nodes with when_conditions[node] == false ...
     748
     749    for ( node in nodes )                                                               $\C{// register nodes}$
     750        if ( when_conditions[node] )
     751            register_select( resource, node );
     752
     753    while ( !check_completion( nodes ) ) {      $\C{// check predicate}$
     754        // block
     755        for ( resource in waituntil statement ) {       $\C{// run true code blocks}$
     756            if ( check_completion( nodes ) ) break;
     757            if ( resource is avail )
     758                try {
     759                    if( on_selected( resource ) )       $\C{// conditionally run block}$
     760                        run code block
     761                } finally                                                       $\C{// for exception safety}$
     762                    unregister_select( resource, node ); $\C{// immediate unregister}$
    789763        }
    790     } finally {                                                                                 $\C{// for exception safety}$
    791         for ( registered nodes in nodes )                                       $\C{// deregister nodes}$
    792             if ( when_conditions[node] && unregister_select( resource, node )
    793                     && on_selected( resource ) )
    794                 run code block                                                  $\C{// run code block upon unregister}\CRT$
    795764    }
     765} finally {                                                                                     $\C{// for exception safety}$
     766        for ( registered nodes in nodes )                                       $\C{// deregister nodes}$
     767                if ( when_conditions[node] && unregister_select( resource, node )
     768                                && on_selected( resource ) )
     769                        run code block                                                  $\C{// run code block upon unregister}\CRT$
     770}
     771
    796772}
    797773\end{cfa}
    … …  
    938914\setlength{\tabcolsep}{5pt}
    939915
    940 \caption{Throughput (channel operations per second) of \CFA and Go in a pathological case for contention in Go's select implementation}
     916\caption{Throughput (channel operations per second) of \CFA and Go for a pathologically case for contention in Go's select implementation}
    941917\label{t:pathGo}
    942918\begin{tabular}{r|r|r}
Note: See TracChangeset for help on using the changeset viewer.