Changeset 000d68f

Timestamp:

Jul 31, 2023, 4:18:49 PM (17 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:

• actors.tex (modified) (8 diffs)
• channels.tex (modified) (1 diff)
• conclusion.tex (modified) (1 diff)
• intro.tex (modified) (1 diff)
• mutex_stmt.tex (modified) (1 diff)
• waituntil.tex (modified) (6 diffs)

doc/theses/colby_parsons_MMAth/text/actors.tex

@@ -251 +251 @@
 Therefore, it is up to the actor program to manage message life-time across receives.
 However, for a message to appear on multiple message queues, it needs an arbitrary number of associated destination behaviours.
-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.
-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.
+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.
+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.
 
 % In actor systems, messages are sent and received by actors.
@@ -342 +342 @@
 
 Users could be expected to write the @?|?@ routines, but this approach is error prone and creates maintenance issues.
-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.
-This workaround is outside of the type system, but performing a type-system like action.
+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.
+This workaround is outside of the type system, but performs a type-system like action.
 The workaround requires no annotation or additional code to be written by users;
 thus, it resolves the maintenance and error problems.
@@ -352 +352 @@
 The routine sets @rec_fn@ to the matching @receive@ routine using the left-hand type to perform the selection.
 Then the routine packages the actor and message, along with the receive routine into an envelope.
-Finally, the envelop is added to the executor queue designated by the actor using the executor routine @send@.
+Finally, the envelope is added to the executor queue designated by the actor using the executor routine @send@.
 
 \begin{figure}
@@ -396 +396 @@
 \subsection{Actor Termination}\label{s:ActorTerm}
 During a message send, the receiving actor and message being sent are stored via pointers in the envelope.
-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.
+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.
 After the receive routine is done, the executor must clean up the actor and message according to their allocation status.
 If the allocation status is @Delete@ or @Destroy@, the appropriate destructor must be called by the executor.
@@ -402 +402 @@
 the derived type of the actor or message is not available to the executor, but it needs to call the derived destructor.
 This requires downcasting from the base type to the derived type, which requires a virtual system.
-To accomplish the dowcast, I implemented a rudimentary destructor-only virtual system in \CFA.
+To accomplish the downcast, a rudimentary destructor-only virtual system was implemented in \CFA as part of this work.
 This virtual system is used via Plan-9 inheritance of the @virtual_dtor@ type, shown in Figure~\ref{f:VirtDtor}.
 The @virtual_dtor@ type maintains a pointer to the start of the object, and a pointer to the correct destructor.
@@ -517 +517 @@
 
 Since 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 many workload, the copy queues grow in size to facilitate the average number of messages in flight and there is no further dynamic allocations.
+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.
 The downside of this approach is that more storage is allocated than needed, \ie each copy queue is only partially full.
 Comparatively, 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.
@@ -662 +662 @@
 However, any form of locking here creates contention between thief and victim.
 
-The alternative to locking is allowing the race and resolving it lazily (lock-free approach).
+The alternative to locking is allowing the race and resolving it lazily.
 % 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 
@@ -1262 +1262 @@
 Because $Z$ is contiguous in memory, there can be small cache write-contention at the row boundaries.
 
-Figures~\ref{f:MatrixAMD} and \ref{f:MatrixIntel} show the matrix multiple results.
+Figures~\ref{f:MatrixAMD} and \ref{f:MatrixIntel} show the matrix-multiply results.
 There are two groupings with Akka and ProtoActor being slightly slower than \uC, \CFA, and CAF.
 On the Intel, there is an unknown divergence between \uC and \CFA/CAF at 24 cores.

doc/theses/colby_parsons_MMAth/text/channels.tex

@@ -106 +106 @@
 \item A @flush@ routine that delivers copies of an element to all waiting consumers, flushing the buffer.
 Programmers use this mechanism to broadcast a sentinel value to multiple consumers.
-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.
+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.
 
 \item Go-style @?<<?@ shorthand operator for inserting and removing.

doc/theses/colby_parsons_MMAth/text/conclusion.tex

@@ -14 +14 @@
 \begin{enumerate}
 \item The mutex statement, which provides performant and deadlock-free multiple lock acquisition.
-\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.
+\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.
 \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.
 \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

@@ -14 +14 @@
 This thesis builds on top of that foundation by providing a suite of high-level concurrent features. 
 The features include a @mutex@ statement, channels, a @waituntil@ statement, and an actor system. 
-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.
+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.

doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex

@@ -83 +83 @@
 \end{figure}
 
-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.
+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.
 For 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.
 Monitor objects can be passed through multiple helper functions without acquiring mutual exclusion, until a designated function associated with the object is called.
 \CFA functions are designated MX by one or more pointer/reference parameters having qualifier @mutex@.
 Java members are designated MX with \lstinline[language=java]{synchronized}, which applies only to the implicit receiver parameter.
-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.
+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.
 
 As 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

@@ -163 +163 @@
 
 Another example of programming-language \gls{synch_multiplex} is Go using a @select@ statement with channels~\cite{go:selectref}.
-Figure~\ref{l:BB_Go} shows the outline of a bounded buffer implemented with a Go routine.
+Figure~\ref{l:BB_Go} shows the outline of a bounded buffer administrator implemented with a Go routine.
 Here two channels are used for inserting and removing by client producers and consumers, respectively.
-(The @term@ and @stop@ channels are used to synchronize with the program main.)
+(The @done@ channel is used to synchronize with the program main.)
 Go'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.
 However, unlike Ada and ALT, Go does not provide guards for the \lstinline[language=go]{case} clauses of the \lstinline[language=go]{select}.
+As such, the exponential blowup can be seen comparing Go and \uC in Figure~\label{f:AdaMultiplexing}.
 Go also provides a timeout via a channel and a @default@ clause like Ada @else@ for asynchronous multiplexing.
 
@@ -175 +176 @@
 \begin{lrbox}{\myboxA}
 \begin{lstlisting}[language=go,literate=]
+insert := make( chan int )
+remove := make( chan * int )
+buffer := make( chan int Size )
+done := make( chan int )
+count := 0
+func in_buf( int val ) {
+    buffer <- val
+    count++
+}
+func out_buf( int * ptr ) {
+    *ptr := <-buffer
+    count--
+}
+func BoundedBuffer {
+    L: for {
+        if ( count < Size && count > 0 ) {
+            select { // wait for message
+                case i := <- insert: in_buf( i )
+                case p := <- remove: out_buf( p )
+                case <- done: break L
+            }
+        } else if ( count < Size ) {
+            select { // wait for message
+                case i := <- insert: in_buf( i )
+                case <- done: break L
+            }
+        } else ( count > 0 ) {
+            select { // wait for message
+                case p := <- remove: out_buf( p )
+                case <- done: break L;
+            }
+        }
+    }
+    done <- 0
+}
 func main() {
-        insert := make( chan int, Size )
-        remove := make( chan int, Size )
-        term := make( chan string )
-        finish := make( chan string )
-
-        buf := func() {
-                L: for {
-                        select { // wait for message
-                          case i = <- buffer:
-                          case <- term: break L
-                        }
-                        remove <- i;
-                }
-                finish <- "STOP" // completion
-        }
-        go buf() // start thread in buf
+        go BoundedBuffer() // start administrator
 }
 
@@ -203 +224 @@
 \begin{lstlisting}[language=uC++=]
 _Task BoundedBuffer {
-        ... // buffer declarations
-        int count = 0;
+        int * buffer;
+        int front = back = count = 0;
   public:
+    // ... constructor implementation
         void insert( int elem ) {
-                ... // add to buffer
+                buffer[front] = elem;
+        front = ( front + 1 ) % Size;
                 count += 1;
         }
         int remove() {
-                ... // remove and return from buffer
+                int ret = buffer[back];
+        back = ( back + 1 ) % Size;
                 count -= 1;
+        return ret;
         }
   private:
@@ -240 +265 @@
 The @_Select@ statement extends the ALT/Go @select@ by offering both @and@ and @or@ semantics, which can be used together in the same statement.
 Both @_Accept@ and @_Select@ statements provide guards for multiplexing clauses, as well as, timeout, and @else@ clauses.
+Figure~\ref{l:BB_uC++} shows the outline of a bounded buffer administrator implemented with \uC @_Accept@ statements.
 
 There 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}.
@@ -741 +767 @@
                 when_conditions[node] = true;
 
-if ( any when_conditions[node] == true ) {
-
-select_nodes nodes[N];                                                                  $\C{// declare N select nodes}$
-try {
-    // ... set statuses for nodes with when_conditions[node] == false ...
-
-    for ( node in nodes )                                                               $\C{// register nodes}$
-        if ( when_conditions[node] )
-            register_select( resource, node );
-
-    while ( !check_completion( nodes ) ) {      $\C{// check predicate}$
-        // block
-        for ( resource in waituntil statement ) {       $\C{// run true code blocks}$
-            if ( check_completion( nodes ) ) break;
-            if ( resource is avail )
-                try {
-                    if( on_selected( resource ) )       $\C{// conditionally run block}$
-                        run code block
-                } finally                                                       $\C{// for exception safety}$
-                    unregister_select( resource, node ); $\C{// immediate unregister}$
+if ( any when_conditions[node] are true ) {
+    select_nodes nodes[N];                                                                      $\C{// declare N select nodes}$
+    try {
+        // ... set statuses for nodes with when_conditions[node] == false ...
+
+        for ( node in nodes )                                                           $\C{// register nodes}$
+            if ( when_conditions[node] )
+                register_select( resource, node );
+
+        while ( !check_completion( nodes ) ) {  $\C{// check predicate}$
+            // block
+            for ( resource in waituntil statement ) {   $\C{// run true code blocks}$
+                if ( check_completion( nodes ) ) break;
+                if ( resource is avail )
+                    try {
+                        if( on_selected( resource ) )   $\C{// conditionally run block}$
+                            run code block
+                    } finally                                                   $\C{// for exception safety}$
+                        unregister_select( resource, node ); $\C{// immediate unregister}$
+            }
         }
+    } finally {                                                                                 $\C{// for exception safety}$
+        for ( registered nodes in nodes )                                       $\C{// deregister nodes}$
+            if ( when_conditions[node] && unregister_select( resource, node )
+                    && on_selected( resource ) ) 
+                run code block                                                  $\C{// run code block upon unregister}\CRT$
     }
-} finally {                                                                                     $\C{// for exception safety}$
-        for ( registered nodes in nodes )                                       $\C{// deregister nodes}$
-                if ( when_conditions[node] && unregister_select( resource, node )
-                                && on_selected( resource ) ) 
-                        run code block                                                  $\C{// run code block upon unregister}\CRT$
-}
-
 }
 \end{cfa}
@@ -914 +938 @@
 \setlength{\tabcolsep}{5pt}
 
-\caption{Throughput (channel operations per second) of \CFA and Go for a pathologically case for contention in Go's select implementation}
+\caption{Throughput (channel operations per second) of \CFA and Go in a pathological case for contention in Go's select implementation}
 \label{t:pathGo}
 \begin{tabular}{r|r|r}