Index: doc/theses/colby_parsons_MMAth/text/actors.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/actors.tex (revision afb3d68419e40020edeb24ec6f52f94c972fccb1) +++ doc/theses/colby_parsons_MMAth/text/actors.tex (revision 210c7379c97a824c2ee7f5e3a7ba500aa7d4deee) @@ -251,6 +251,6 @@ 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,6 +342,6 @@ 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,5 +352,5 @@ 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,5 +396,5 @@ \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,5 +402,5 @@ 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,5 +517,5 @@ 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,5 +662,5 @@ However, any form of locking here creates contention between thief and victim. -The alternative to locking is allowing the race and resolving it lazily (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,5 +1262,5 @@ 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. Index: doc/theses/colby_parsons_MMAth/text/channels.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/channels.tex (revision afb3d68419e40020edeb24ec6f52f94c972fccb1) +++ doc/theses/colby_parsons_MMAth/text/channels.tex (revision 210c7379c97a824c2ee7f5e3a7ba500aa7d4deee) @@ -106,5 +106,5 @@ \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 @?< 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,14 +224,18 @@ \begin{lstlisting}[language=uC++,{moredelim={**[is][\color{red}]{@}{@}}}] _Task BoundedBuffer { - ... // buffer declarations - int count = 0; + int * buffer; + int front = back = count = 0; public: - @void insert( int elem )@ { - ... // add to buffer + // ... constructor implementation + void insert( int elem ) { + buffer[front] = elem; + front = ( front + 1 ) % Size; count += 1; } - @int remove()@ { - ... // remove and return from buffer + int remove() { + int ret = buffer[back]; + back = ( back + 1 ) % Size; count -= 1; + return ret; } private: @@ -240,4 +265,5 @@ 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}, Java's @allof@/@anyof@ over futures~\cite{java:allof:anyof}, OCaml's @select@ over channels~\cite{ocaml:channel}, and C++14's @when_any@ over futures~\cite{cpp:whenany}. @@ -745,33 +771,31 @@ 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} @@ -918,5 +942,5 @@ \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}