Ignore:
Timestamp:
Jul 31, 2023, 4:18:49 PM (11 months ago)
Author:
caparsons <caparson@…>
Branches:
master
Children:
4852232
Parents:
d3c3261
Message:

various small changes across entire thesis

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

Legend:

Unmodified
Added
Removed

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

    rd3c3261 r000d68f  
    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 envelop, 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 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.
     253Hence, 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.
     254Managing 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.
    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 Until 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.
    345 This workaround is outside of the type system, but performing a type-system like action.
     344As 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.
     345This workaround is outside of the type system, but performs 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 envelop is added to the executor queue designated by the actor using the executor routine @send@.
     354Finally, the envelope 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 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.
     398These 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.
    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 dowcast, I implemented a rudimentary destructor-only virtual system in \CFA.
     404To accomplish the downcast, a rudimentary destructor-only virtual system was implemented in \CFA as part of this work.
    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 workload, the copy queues grow in size to facilitate the average number of messages in flight and there is no further dynamic allocations.
     519For many workloads, the copy queues grow in size to facilitate the average number of messages in flight and there are 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 (lock-free approach).
     664The alternative to locking is allowing the race and resolving it lazily.
    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 multiple results.
     1264Figures~\ref{f:MatrixAMD} and \ref{f:MatrixIntel} show the matrix-multiply 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

    rd3c3261 r000d68f  
    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 then 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 than 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

    rd3c3261 r000d68f  
    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

    rd3c3261 r000d68f  
    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 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 languages 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

    rd3c3261 r000d68f  
    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 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 of 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, 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 above, 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

    rd3c3261 r000d68f  
    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 implemented with a Go routine.
     165Figure~\ref{l:BB_Go} shows the outline of a bounded buffer administrator implemented with a Go routine.
    166166Here two channels are used for inserting and removing by client producers and consumers, respectively.
    167 (The @term@ and @stop@ channels are used to synchronize with the program main.)
     167(The @done@ channel is 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}.
     170As such, the exponential blowup can be seen comparing Go and \uC in Figure~\label{f:AdaMultiplexing}.
    170171Go also provides a timeout via a channel and a @default@ clause like Ada @else@ for asynchronous multiplexing.
    171172
    … …  
    175176\begin{lrbox}{\myboxA}
    176177\begin{lstlisting}[language=go,literate=]
     178insert := make( chan int )
     179remove := make( chan * int )
     180buffer := make( chan int Size )
     181done := make( chan int )
     182count := 0
     183func in_buf( int val ) {
     184    buffer <- val
     185    count++
     186}
     187func out_buf( int * ptr ) {
     188    *ptr := <-buffer
     189    count--
     190}
     191func 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}
    177213func main() {
    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
     214        go BoundedBuffer() // start administrator
    194215}
    195216
    … …  
    203224\begin{lstlisting}[language=uC++=]
    204225_Task BoundedBuffer {
    205         ... // buffer declarations
    206         int count = 0;
     226        int * buffer;
     227        int front = back = count = 0;
    207228  public:
     229    // ... constructor implementation
    208230        void insert( int elem ) {
    209                 ... // add to buffer
     231                buffer[front] = elem;
     232        front = ( front + 1 ) % Size;
    210233                count += 1;
    211234        }
    212235        int remove() {
    213                 ... // remove and return from buffer
     236                int ret = buffer[back];
     237        back = ( back + 1 ) % Size;
    214238                count -= 1;
     239        return ret;
    215240        }
    216241  private:
    … …  
    240265The @_Select@ statement extends the ALT/Go @select@ by offering both @and@ and @or@ semantics, which can be used together in the same statement.
    241266Both @_Accept@ and @_Select@ statements provide guards for multiplexing clauses, as well as, timeout, and @else@ clauses.
     267Figure~\ref{l:BB_uC++} shows the outline of a bounded buffer administrator implemented with \uC @_Accept@ statements.
    242268
    243269There 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}.
    … …  
    741767                when_conditions[node] = true;
    742768
    743 if ( any when_conditions[node] == true ) {
    744 
    745 select_nodes nodes[N];                                                                  $\C{// declare N select nodes}$
    746 try {
    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}$
     769if ( 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            }
    763789        }
     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$
    764795    }
    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 
    772796}
    773797\end{cfa}
    … …  
    914938\setlength{\tabcolsep}{5pt}
    915939
    916 \caption{Throughput (channel operations per second) of \CFA and Go for a pathologically case for contention in Go's select implementation}
     940\caption{Throughput (channel operations per second) of \CFA and Go in a pathological case for contention in Go's select implementation}
    917941\label{t:pathGo}
    918942\begin{tabular}{r|r|r}
Note: See TracChangeset for help on using the changeset viewer.