Index: doc/theses/colby_parsons_MMAth/text/CFA_concurrency.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/CFA_concurrency.tex (revision 0da718119b2ce64d4fe7e641a9d6cdfd960b073d) +++ doc/theses/colby_parsons_MMAth/text/CFA_concurrency.tex (revision 0da718119b2ce64d4fe7e641a9d6cdfd960b073d) @@ -0,0 +1,24 @@ +\chapter{Concurrency in \CFA}\label{s:cfa_concurrency} + +The groundwork for concurrency in \CFA was laid by Thierry Delisle in his Master's Thesis\cite{Delisle18}. In that work he introduced coroutines, user level threading, and monitors. Not listed in that work were the other concurrency features that were needed as building blocks, such as locks, futures, and condition variables which he also added to \CFA. + +\section{Threading Model}\label{s:threading} +\CFA has user level threading and supports a $M:N$ threading model where $M$ user threads are scheduled on $N$ cores, where both $M$ and $N$ can be explicitly set by the user. Cores are used by a program by creating instances of a \code{processor} struct. User threads types are defined using the \code{thread} keyword, in the place where a \code{struct} keyword is typically used. For each thread type a corresponding main must be defined, which is where the thread starts running once it is created. Listing~\ref{l:cfa_thd_init} shows an example of processor and thread creation. When processors are added, they are added alongside the existing processor given to each program. Thus if you want $N$ processors you need to allocate $N-1$. To join a thread the thread must be deallocated, either deleted if it is allocated on the heap, or go out of scope if stack allocated. The thread performing the deallocation will wait for the thread being deallocated to terminate before the deallocation can occur. A thread terminates by returning from the main routine where it starts. + +\begin{cfacode}[tabsize=3,caption={\CFA user thread and processor creation},label={l:cfa_thd_init}] + +thread my_thread {} // user thread type +void main( my_thread & this ) { // thread start routine + printf("Hello threading world\n"); +} + +int main() { + // add 2 processors, now 3 total + processor p[2]; + { + my_thread t1; + my_thread t2; + } // waits for threads to end before going out of scope +} + +\end{cfacode} Index: doc/theses/colby_parsons_MMAth/text/CFA_intro.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/CFA_intro.tex (revision 601bd9e9f3b5aea55f6bb776a5794aa880af3c04) +++ doc/theses/colby_parsons_MMAth/text/CFA_intro.tex (revision 0da718119b2ce64d4fe7e641a9d6cdfd960b073d) @@ -5,15 +5,235 @@ % ====================================================================== -% potentially discuss rebindable references, with stmt, and operators - \section{Overview} +The following serves as an introduction to \CFA. \CFA is a layer over C, is transpiled to C and is largely considered to be an extension of C. Beyond C, it adds productivity features, libraries, a type system, and many other language constructions. However, \CFA stays true to C as a language, with most code revolving around \code{struct}'s and routines, and respects the same rules as C. \CFA is not object oriented as it has no notion of \code{this} and no classes or methods, but supports some object oriented adjacent ideas including costructors, destructors, and limited inheritance. \CFA is rich with interesting features, but a subset that is pertinent to this work will be discussed. + +\section{References} +References in \CFA are similar to references in \CC, however in \CFA references are rebindable, and support multi-level referencing. References in \CFA are a layer of syntactic sugar over pointers to reduce the number of ref/deref operations needed with pointer usage. Some examples of references in \CFA are shown in Listing~\ref{l:cfa_ref}. + + +\begin{cfacode}[tabsize=3,caption={Example of \CFA references},label={l:cfa_ref}] +int i = 2; +int & ref_i = i; // declare ref to i +int * ptr_i = &i; // ptr to i + +// address of ref_i is the same as address of i +assert( &ref_i == ptr_i ); + +int && ref_ref_i = ref_i; // can have a ref to a ref +ref_i = 3; // set i to 3 +int new_i = 4; + +// syntax to rebind ref_i (must cancel implicit deref) +&ref_i = &new_i; // (&*)ref_i = &new_i; (sets underlying ptr) +\end{cfacode} + + +\section{Overloading} +In \CFA routines can be overloaded on parameter type, number of parameters, and return type. Variables can also be overloaded on type, meaning that two variables can have the same name so long as they have different types. The variables will be disambiguated via type, sometimes requiring a cast. The code snippet in Listing~\ref{l:cfa_overload} contains examples of overloading. + + +\begin{cfacode}[tabsize=3,caption={Example of \CFA function overloading},label={l:cfa_overload}] +int foo() { printf("A\n"); return 0;} +int foo( int bar ) { printf("B\n"); return 1; } +int foo( double bar ) { printf("C\n"); return 2; } +double foo( double bar ) { printf("D\n"); return 3;} +void foo( double bar ) { printf("%.0f\n", bar); } + +int main() { + foo(); // prints A + foo( 0 ); // prints B + int a = foo( 0.0 ); // prints C + double a = foo( 0.0 ); // prints D + foo( a ); // prints 3 +} +\end{cfacode} + + +\section{With Statement} +The with statement is a tool for exposing members of aggregate types within a scope in \CFA. It allows users to use fields of aggregate types without using their fully qualified name. This feature is also implemented in Pascal. It can exist as a stand-alone statement or it can be used on routines to expose fields in the body of the routine. An example is shown in Listing~\ref{l:cfa_with}. + + +\begin{cfacode}[tabsize=3,caption={Usage of \CFA with statement},label={l:cfa_with}] +struct obj { + int a, b, c; +}; +struct pair { + double x, y; +}; + +// Stand-alone with stmt: +pair p; +with( p ) { + x = 6.28; + y = 1.73; +} + +// Can be used on routines: +void foo( obj o, pair p ) with( o, p ) { + a = 1; + b = 2; + c = 3; + x = 3.14; + y = 2.71; +} + +// routine foo is equivalent to routine bar: +void bar( obj o, pair p ) { + o.a = 1; + o.b = 2; + o.c = 3; + p.x = 3.14; + p.y = 2.71; +} +\end{cfacode} + + +\section{Operators} +Operators can be overloaded in \CFA with operator routines. Operators in \CFA are named using the operator symbol and '?' to respresent operands. +An example is shown in Listing~\ref{l:cfa_operate}. + + +\begin{cfacode}[tabsize=3,caption={Example of \CFA operators},label={l:cfa_operate}] +struct coord { + double x; + double y; + double z; +}; +coord ++?( coord & c ) with(c) { + x++; + y++; + z++; + return c; +} +coord ?<=?( coord op1, coord op2 ) with( op1 ) { + return (x*x + y*y + z*z) <= + (op2.x*op2.x + op2.y*op2.y + op2.z*op2.z); +} +\end{cfacode} + + +\section{Constructors and Destructors} +Constructors and destructors in \CFA are two special operator routines that are used for creation and destruction of objects. The default constructor and destructor for a type are called implicitly upon creation and deletion respectively if they are defined. An example is shown in Listing~\ref{l:cfa_ctor}. + + +\begin{cfacode}[tabsize=3,caption={Example of \CFA constructors and destructors},label={l:cfa_ctor}] +struct discrete_point { + int x; + int y; +}; +void ?{}( discrete_point & this ) with(this) { // ctor + x = 0; + y = 0; +} +void ?{}( discrete_point & this, int x, int y ) { // ctor + this.x = x; + this.y = y; +} +void ^?{}( discrete_point & this ) with(this) { // dtor + x = 0; + y = 0; +} + +int main() { + discrete_point d; // implicit call to ?{} + discrete_point p{}; // same call as line above + discrete_point dp{ 2, -4 }; // specialized ctor +} // ^d{}, ^p{}, ^dp{} all called as they go out of scope +\end{cfacode} + \section{Polymorphism}\label{s:poly} - -\section{Overloading} - -\section{Constructors and Destructors} - -\section{With Statement} - -\section{Threading Model}\label{s:threading} +C does not natively support polymorphism, and requires users to implement polymorphism themselves if they want to use it. \CFA extends C with two styles of polymorphism that it supports, parametric polymorphism and nominal inheritance. + +\subsection{Parametric Polymorphism} +\CFA provides parametric polymorphism in the form of \code{forall}, and \code{trait}s. A \code{forall} takes in a set of types and a list of constraints. The declarations that follow the \code{forall} are parameterized over the types listed that satisfy the constraints. Sometimes the list of constraints can be long, which is where a \code{trait} can be used. A \code{trait} is a collection of constraints that is given a name and can be reused in foralls. An example of the usage of parametric polymorphism in \CFA is shown in Listing~\ref{l:cfa_poly}. + +\begin{cfacode}[tabsize=3,caption={Example of \CFA polymorphism},label={l:cfa_poly}] +// sized() is a trait that means the type has a size +forall( V & | sized(V) ) // type params for trait +trait vector_space { + V add( V, V ); // vector addition + V scalar_mult( int, V ); // scalar multiplication + + // dtor and copy ctor needed in constraints to pass by copy + void ?{}( V &, V & ); // copy ctor for return + void ^?{}( V & ); // dtor +}; + +forall( V & | vector_space( V )) { + V get_inverse( V v1 ) { + return scalar_mult( -1, v1 ); // can use ?*? routine defined in trait + } + V add_and_invert( V v1, V v2 ) { + return get_inverse( add( v1, v2 ) ); // can use ?*? routine defined in trait + } +} +struct Vec1 { int x; }; +void ?{}( Vec1 & this, Vec1 & other ) { this.x = other.x; } +void ?{}( Vec1 & this, int x ) { this.x = x; } +void ^?{}( Vec1 & this ) {} +Vec1 add( Vec1 v1, Vec1 v2 ) { v1.x += v2.x; return v1; } +Vec1 scalar_mult( int c, Vec1 v1 ) { v1.x = v1.x * c; return v1; } + +struct Vec2 { int x; int y; }; +void ?{}( Vec2 & this, Vec2 & other ) { this.x = other.x; this.y = other.y; } +void ?{}( Vec2 & this, int x ) { this.x = x; this.y = x; } +void ^?{}( Vec2 & this ) {} +Vec2 add( Vec2 v1, Vec2 v2 ) { v1.x += v2.x; v1.y += v2.y; return v1; } +Vec2 scalar_mult( int c, Vec2 v1 ) { v1.x = v1.x * c; v1.y = v1.y * c; return v1; } + +int main() { + Vec1 v1{ 1 }; // create Vec1 and call ctor + Vec2 v2{ 2 }; // create Vec2 and call ctor + + // can use forall defined routines since types satisfy trait + add_and_invert( get_inverse( v1 ), v1 ); + add_and_invert( get_inverse( v2 ), v2 ); +} + +\end{cfacode} + +\subsection{Inheritance} +Inheritance in \CFA copies its style from Plan-9 C nominal inheritance. In \CFA structs can \code{inline} another struct type to gain its fields and to be able to be passed to routines that require a parameter of the inlined type. An example of \CFA inheritance is shown in Listing~\ref{l:cfa_inherit}. + +\begin{cfacode}[tabsize=3,caption={Example of \CFA inheritance},label={l:cfa_inherit}] +struct one_d { double x; }; +struct two_d { + inline one_d; + double y; +}; +struct three_d { + inline two_d; + double z; +}; +double get_x( one_d & d ){ return d.x; } + +struct dog {}; +struct dog_food { + int count; +}; +struct pet { + inline dog; + inline dog_food; +}; +void pet_dog( dog & d ){printf("woof\n");} +void print_food( dog_food & f ){printf("%d\n", f.count);} + +int main() { + one_d x; + two_d y; + three_d z; + x.x = 1; + y.x = 2; + z.x = 3; + get_x( x ); // returns 1; + get_x( y ); // returns 2; + get_x( z ); // returns 3; + pet p; + p.count = 5; + pet_dog( p ); // prints woof + print_food( p ); // prints 5 +} +\end{cfacode} + + Index: doc/theses/colby_parsons_MMAth/text/actors.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/actors.tex (revision 601bd9e9f3b5aea55f6bb776a5794aa880af3c04) +++ doc/theses/colby_parsons_MMAth/text/actors.tex (revision 0da718119b2ce64d4fe7e641a9d6cdfd960b073d) @@ -1,13 +1,13 @@ % ====================================================================== % ====================================================================== -\chapter{Concurrent Actors}\label{s:actors} +\chapter{Actors}\label{s:actors} % ====================================================================== % ====================================================================== -% C_TODO: add citations -Before 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. - -\section{The Actor Model} % \cite{Hewitt73} -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{}. 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. +% C_TODO: add citations throughout chapter +Actors are a concurrent feature that abstracts threading away from a user, and instead provides \newterm{actors} and \newterm{messages} as building blocks for concurrency. This is a form of what is called \newterm{implicit concurrency}, where programmers write concurrent code without having to worry about explicit thread synchronization and mutual exclusion. The study of actors can be broken into two concepts, the \newterm{actor model}, which describes the model of computation and the \newterm{actor system}, which refers to the implementation of the model in practice. Before 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. + +\section{The Actor Model} +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 typically operate on local state. \section{Classic Actor System} @@ -16,6 +16,6 @@ \begin{figure} \begin{tabular}{l|l} -\subfloat[Actor-centric system]{\label{f:standard_actor}\input{figures/standard_actor.tikz}} & -\subfloat[Message-centric system]{\label{f:inverted_actor}\raisebox{.1\height}{\input{figures/inverted_actor.tikz}}} +\subfloat[Actor-centric system]{\label{f:standard_actor}\input{diagrams/standard_actor.tikz}} & +\subfloat[Message-centric system]{\label{f:inverted_actor}\raisebox{.1\height}{\input{diagrams/inverted_actor.tikz}}} \end{tabular} \caption{Classic and inverted actor implementation approaches with sharded queues.} @@ -44,9 +44,8 @@ \item -Creates a static-typed actor system that catches actor-message mismatches at compile time. -% C_TODO: create and/or mention other safety features (allocation/deadlock/etc) +Provides a suite of safety and productivity features including static-typing, detection of erroneous message sends, statistics tracking, and more. \end{enumerate} -\subsection{\CFA Actor Syntax} +\section{\CFA Actor Syntax} \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 }. 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. @@ -70,5 +69,5 @@ Allocation receive( derived_actor & receiver, derived_msg & msg ) { printf("The message contained the string: %s\n", msg.word); - return Finished; // Return inished since actor is done + return Finished; // Return finished since actor is done } @@ -77,5 +76,5 @@ derived_actor my_actor; derived_msg my_msg{ "Hello World" }; // Constructor call - my_actor | my_msg; // Send message via bar operator + my_actor << my_msg; // Send message via left shift operator stop_actor_system(); // Waits until actors are finished return 0; @@ -109,5 +108,5 @@ \item[\LstBasicStyle{\textbf{Finished}}] -tells 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. +tells 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. As such \code{Finished} is not supported for messages and is used internally by the executor to track if messages have been used for debugging purposes. \end{description} @@ -124,17 +123,17 @@ All 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. -All message sends are done using the bar operater, \ie |. The signature of the bar operator is: +All message sends are done using the left shift operater, \ie <<, similar to the syntax of \CC's output. The signature of the left shift operator is: \begin{cfacode} -Allocation ?|?( derived_actor & receiver, derived_msg & msg ) +Allocation ?< 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. \end{theorem}\label{t:vic_chain} +A graph of the chain of swaps discussed in this theorem is presented in Figure~\ref{f:chain_swap}. +\\ This 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. For 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. + +% \raisebox{.1\height}{} +\begin{figure} +\centering +\begin{tabular}{l|l} +\subfloat[Cyclic Swap Graph]{\label{f:cyclic_swap}\input{diagrams/cyclic_swap.tikz}} & +\subfloat[Acyclic Swap Graph]{\label{f:acyclic_swap}\input{diagrams/acyclic_swap.tikz}} +\end{tabular} +\caption{Illustrations of cyclic and acyclic swap graphs.} +\end{figure} \begin{theorem} Given 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. \end{theorem}\label{t:vic_cycle} +Representations of cyclic and acylic swap graphs discussed in this theorem are presented in Figures~\ref{f:cyclic_swap} and \ref{f:acyclic_swap}. +\\ First 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. @@ -300,8 +330,277 @@ % C_TODO: go through and use \paragraph to format to make it look nicer -\subsubsection{Victim Selection} +\subsection{Victim Selection}\label{s:victimSelect} In 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. -\subsection{Safety} - -\subsection{Performance}\label{s:actor_perf} +\section{Safety and Productivity} +\CFA's actor system comes with a suite of safety and productivity features. Most of these features are present in \CFA's debug mode, but are removed when code is compiled in nodebug mode. Some of the features include: + +\begin{itemize} +\item Static-typed message sends. If an actor does not support receiving a given message type, the actor program is rejected at compile time, allowing unsupported messages to never be sent to actors. +\item Detection of message sends to Finished/Destroyed/Deleted actors. All actors have a ticket that assigns them to a respective queue. The maximum integer value of the ticket is reserved to indicate that an actor is dead, and subsequent message sends result in an error. +\item Actors made before the executor can result in undefined behaviour since an executor needs to be created beforehand so it can give out the tickets to actors. As such, this is detected and an error is printed. +\item When an executor is created, the queues are handed out to worker threads in round robin order. If there are fewer queues than worker threads, then some workers will spin and never do any work. There is no reasonable use case for this behaviour so an error is printed if the number of queues is fewer than the number of worker threads. +\item A warning is printed when messages are deallocated without being sent. Since the \code{Finished} allocation status is unused for messages, it is used internally to detect if a message has been sent. Deallocating a message without sending it could indicate to a user that they are touching freed memory later, or it could point out extra allocations that could be removed. +\end{itemize} + +In addition to these features, \CFA's actor system comes with a suite of statistics that can be toggled on and off. These statistics have minimal impact on the actor system's performance since they are counted on a per worker thread basis. During shutdown of the actor system they are aggregated, ensuring that the only atomic instructions used by the statistics counting happen at shutdown. The statistics measured are as follows. + +\begin{description} +\item[\LstBasicStyle{\textbf{Actors Created}}] +Actors created. Includes both actors made by the main and ones made by other actors. +\item[\LstBasicStyle{\textbf{Messages Sent}}] +Messages sent and received. Includes termination messages send to the worker threads. +\item[\LstBasicStyle{\textbf{Gulps}}] +Gulps that occured across the worker threads. +\item[\LstBasicStyle{\textbf{Average Gulp Size}}] +Average number of messages in a gulped queue. +\item[\LstBasicStyle{\textbf{Missed gulps}}] +Occurences where a worker missed a gulp due to the concurrent queue processing by another worker. +\item[\LstBasicStyle{\textbf{Steal attempts}}] +Worker threads attempts to steal work. +\item[\LstBasicStyle{\textbf{Steal failures (no candidates)}}] +Work stealing failures due to selected victim not having any non empty or non-being-processed queues. +\item[\LstBasicStyle{\textbf{Steal failures (failed swaps)}}] +Work stealing failures due to the two stage atomic swap failing. +\item[\LstBasicStyle{\textbf{Messages stolen}}] +Aggregate of the number of messages in queues as they were stolen. +\item[\LstBasicStyle{\textbf{Average steal size}}] +Average number of messages in a stolen queue. +\end{description} + +These statistics enable a user of \CFA's actor system to make informed choices about how to configure their executor, or how to structure their actor program. For example, if there is a lot of messages being stolen relative to the number of messages sent, it could indicate to a user that their workload is heavily imbalanced across worker threads. In another example, if the average gulp size is very high, it could indicate that the executor could use more queue sharding. + +% C_TODO cite poison pill messages and add languages +Another productivity feature that is included is a group of poison-pill messages. Poison-pill messages are common across actor systems, including Akka and ProtoActor \cite{}. Poison-pill messages inform an actor to terminate. In \CFA, due to the allocation of actors and lack of garbage collection, there needs to be a suite of poison-pills. The messages that \CFA provides are \code{DeleteMsg}, \code{DestroyMsg}, and \code{FinishedMsg}. These messages are supported on all actor types via inheritance and when sent to an actor, the actor takes the corresponding allocation action after receiving the message. Note that any pending messages to the actor will still be sent. It is still the user's responsibility to ensure that an actor does not receive any messages after termination. + +\section{Performance}\label{s:actor_perf} +The performance of \CFA's actor system is tested using a suite of microbenchmarks, and compared with other actor systems. +Most of the benchmarks are the same as those presented in \ref{}, with a few additions. % C_TODO cite actor paper +At the time of this work the versions of the actor systems are as follows. \CFA 1.0, \uC 7.0.0, Akka Typed 2.7.0, CAF 0.18.6, and ProtoActor-Go v0.0.0-20220528090104-f567b547ea07. Akka Classic is omitted as Akka Typed is their newest version and seems to be the direction they are headed in. +The experiments are run on +\begin{list}{\arabic{enumi}.}{\usecounter{enumi}\topsep=5pt\parsep=5pt\itemsep=0pt} +\item +Supermicro SYS--6029U--TR4 Intel Xeon Gold 5220R 24--core socket, hyper-threading $\times$ 2 sockets (48 process\-ing units) 2.2GHz, running Linux v5.8.0--59--generic +\item +Supermicro AS--1123US--TR4 AMD EPYC 7662 64--core socket, hyper-threading $\times$ 2 sockets (256 processing units) 2.0 GHz, running Linux v5.8.0--55--generic +\end{list} + +The benchmarks are run on up to 48 cores. On the Intel, when going beyond 24 cores there is the choice to either hop sockets or to use hyperthreads. Either choice will cause a blip in performance trends, which can be seen in the following performance figures. On the Intel the choice was made to hyperthread instead of hopping sockets for experiments with more than 24 cores. + +All benchmarks presented are run 5 times and the median is taken. Error bars showing the 95\% confidence intervals are drawn on each point on the graphs. If the confidence bars are small enough, they may be obscured by the point. In this section \uC will be compared to \CFA frequently, as the actor system in \CFA was heavily based off \uC's actor system. As such the peformance differences that arise are largely due to the contributions of this work. + +\begin{table}[t] +\centering +\setlength{\extrarowheight}{2pt} +\setlength{\tabcolsep}{5pt} + +\caption{Static Actor/Message Performance: message send, program memory} +\label{t:StaticActorMessagePerformance} +\begin{tabular}{*{5}{r|}r} + & \multicolumn{1}{c|}{\CFA (100M)} & \multicolumn{1}{c|}{CAF (10M)} & \multicolumn{1}{c|}{Akka (100M)} & \multicolumn{1}{c|}{\uC (100M)} & \multicolumn{1}{c@{}}{ProtoActor (100M)} \\ + \hline + AMD & \input{data/pykeSendStatic} \\ + \hline + Intel & \input{data/nasusSendStatic} +\end{tabular} + +\bigskip + +\caption{Dynamic Actor/Message Performance: message send, program memory} +\label{t:DynamicActorMessagePerformance} + +\begin{tabular}{*{5}{r|}r} + & \multicolumn{1}{c|}{\CFA (20M)} & \multicolumn{1}{c|}{CAF (2M)} & \multicolumn{1}{c|}{Akka (2M)} & \multicolumn{1}{c|}{\uC (20M)} & \multicolumn{1}{c@{}}{ProtoActor (2M)} \\ + \hline + AMD & \input{data/pykeSendDynamic} \\ + \hline + Intel & \input{data/nasusSendDynamic} +\end{tabular} +\end{table} + +\subsection{Message Sends} +Message sending is the key component of actor communication. As such latency of a single message send is the fundamental unit of fast-path performance for an actor system. The following two microbenchmarks evaluate the average latency for a static actor/message send and a dynamic actor/message send. Static and dynamic refer to the allocation of the message and actor. In the static send benchmark a message and actor are allocated once and then the message is sent to the same actor repeatedly until it has been sent 100 million (100M) times. The average latency per message send is then calculated by dividing the duration by the number of sends. This benchmark evaluates the cost of message sends in the actor use case where all actors and messages are allocated ahead of time and do not need to be created dynamically during execution. The CAF static send benchmark only sends a message 10M times to avoid extensively long run times. + +In the dynamic send benchmark the same experiment is performed, with the change that with each send a new actor and message is allocated. This evaluates the cost of message sends in the other common actor pattern where actors and message are created on the fly as the actor program tackles a workload of variable or unknown size. Since dynamic sends are more expensive, this benchmark repeats the actor/message creation and send 20M times (\uC, \CFA), or 2M times (Akka, CAF, ProtoActor), to give an appropriate benchmark duration. + +The results from the static/dynamic send benchmarks are shown in Figures~\ref{t:StaticActorMessagePerformance} and \ref{t:DynamicActorMessagePerformance} respectively. \CFA leads the charts in both benchmarks, largely due to the copy queue removing the majority of the envelope allocations. In the static send benchmark all systems except CAF have static send costs that are in the same ballpark, only varying by ~70ns. In the dynamic send benchmark all systems experience slower message sends, as expected due to the extra allocations. However, Akka and ProtoActor, slow down by a more significant margin than the \uC and \CFA. This is likely a result of Akka and ProtoActor's garbage collection, which can suffer from hits in performance for allocation heavy workloads, whereas \uC and \CFA have explicit allocation/deallocation. + +\subsection{Work Stealing} +\CFA's actor system has a work stealing mechanism which uses the longest victim heuristic, introduced in Section~ref{s:victimSelect}. In this performance section, \CFA with the longest victim heuristic is compared with other actor systems on the benchmark suite, and is separately compared with vanilla non-stealing \CFA and \CFA with randomized work stealing. + +\begin{figure} + \centering + \begin{subfigure}{0.5\textwidth} + \centering + \scalebox{0.5}{\input{figures/nasusCFABalance-One.pgf}} + \subcaption{AMD \CFA Balance-One Benchmark} + \label{f:BalanceOneAMD} + \end{subfigure}\hfill + \begin{subfigure}{0.5\textwidth} + \centering + \scalebox{0.5}{\input{figures/pykeCFABalance-One.pgf}} + \subcaption{Intel \CFA Balance-One Benchmark} + \label{f:BalanceOneIntel} + \end{subfigure} + \caption{The balance-one benchmark comparing stealing heuristics (lower is better).} +\end{figure} + +\begin{figure} + \centering + \begin{subfigure}{0.5\textwidth} + \centering + \scalebox{0.5}{\input{figures/nasusCFABalance-Multi.pgf}} + \subcaption{AMD \CFA Balance-Multi Benchmark} + \label{f:BalanceMultiAMD} + \end{subfigure}\hfill + \begin{subfigure}{0.5\textwidth} + \centering + \scalebox{0.5}{\input{figures/pykeCFABalance-Multi.pgf}} + \subcaption{Intel \CFA Balance-Multi Benchmark} + \label{f:BalanceMultiIntel} + \end{subfigure} + \caption{The balance-multi benchmark comparing stealing heuristics (lower is better).} +\end{figure} + +There are two benchmarks in which \CFA's work stealing is solely evaluated. The main goal of introducing work stealing to \CFA's actor system is to eliminate the pathological unbalanced cases that can present themselves in a system without some form of load balancing. The following two microbenchmarks construct two such pathological cases, and compare the work stealing variations of \CFA. The balance benchmarks adversarily takes advantage of the round robin assignment of actors to load all actors that will do work on specific cores and create 'dummy' actors that terminate after a single message send on all other cores. The workload on the loaded cores is the same as the executor benchmark described in \ref{s:executorPerf}, but with fewer rounds. The balance-one benchmark loads all the work on a single core, whereas the balance-multi loads all the work on half the cores (every other core). Given this layout, one expects the ideal speedup of work stealing in the balance-one case to be $N / N - 1$ where $N$ is the number of threads. In the balance-multi case the ideal speedup is 0.5. Note that in the balance-one benchmark the workload is fixed so decreasing runtime is expected. In the balance-multi experiment, the workload increases with the number of cores so an increasing or constant runtime is expected. + +On both balance microbenchmarks slightly less than ideal speedup compared to the non stealing variation is achieved by both the random and longest victim stealing heuristics. On the balance-multi benchmark \ref{f:BalanceMultiAMD},\ref{f:BalanceMultiIntel} the random heuristic outperforms the longest victim. This is likely a result of the longest victim heuristic having a higher stealing cost as it needs to maintain timestamps and look at all timestamps before stealing. Additionally, a performance cost can be observed when hyperthreading kicks in in Figure~\ref{f:BalanceMultiIntel}. + +In the balance-one benchmark on AMD \ref{f:BalanceOneAMD}, the performance bottoms out at 32 cores onwards likely due to the amount of work becoming less than the cost to steal it and move it across cores and cache. On Intel \ref{f:BalanceOneIntel}, above 32 cores the performance gets worse for all variants due to hyperthreading. Note that the non stealing variation of balance-one will slow down marginally as the cores increase due to having to create more dummy actors on the inactive cores during startup. + +\subsection{Executor}\label{s:executorPerf} +The microbenchmarks in this section are designed to stress the executor. The executor is the scheduler of an actor system and is responsible for organizing the interaction of worker threads to service the needs of a workload. In the executor benchmark, 40'000 actors are created and assigned a group. Each group of actors is a group of 100 actors who send and receive 100 messages from all other actors in their group. Each time an actor completes all their sends and receives, they are done a round. After all groups have completed 400 rounds the system terminates. This microbenchmark is designed to flood the executor with a large number of messages flowing between actors. Given there is no work associated with each message, other than sending more messages, the intended bottleneck of this experiment is the executor message send process. + +\begin{figure} + \centering + \begin{subfigure}{0.5\textwidth} + \centering + \scalebox{0.5}{\input{figures/nasusExecutor.pgf}} + \subcaption{AMD Executor Benchmark} + \label{f:ExecutorAMD} + \end{subfigure}\hfill + \begin{subfigure}{0.5\textwidth} + \centering + \scalebox{0.5}{\input{figures/pykeExecutor.pgf}} + \subcaption{Intel Executor Benchmark} + \label{f:ExecutorIntel} + \end{subfigure} + \caption{The executor benchmark comparing actor systems (lower is better).} +\end{figure} + +The results of the executor benchmark in Figures~\ref{f:ExecutorIntel} and \ref{f:ExecutorAMD} show \CFA with the lowest runtime relative to its peers. The difference in runtime between \uC and \CFA is largely due to the usage of the copy queue described in Section~\ref{s:copyQueue}. The copy queue both reduces and consolidates allocations, heavily reducing contention on the memory allocator. Additionally, due to the static typing in \CFA's actor system, it is able to get rid of expensive dynamic casts that occur in \uC to disciminate messages by type. Note that dynamic casts are ususally not very expensive, but relative to the high performance of the rest of the implementation of the \uC actor system, the cost is significant. + +\begin{figure} + \centering + \begin{subfigure}{0.5\textwidth} + \centering + \scalebox{0.5}{\input{figures/nasusCFAExecutor.pgf}} + \subcaption{AMD \CFA Executor Benchmark}\label{f:cfaExecutorAMD} + \end{subfigure}\hfill + \begin{subfigure}{0.5\textwidth} + \centering + \scalebox{0.5}{\input{figures/pykeCFAExecutor.pgf}} + \subcaption{Intel \CFA Executor Benchmark}\label{f:cfaExecutorIntel} + \end{subfigure} + \caption{Executor benchmark comparing \CFA stealing heuristics (lower is better).} +\end{figure} + +When comparing the \CFA stealing heuristics in Figure~\ref{f:cfaExecutorAMD} it can be seen that the random heuristic falls slightly behind the other two, but in Figure~\ref{f:cfaExecutorIntel} the runtime of all heuristics are nearly identical to eachother. + +\begin{figure} + \centering + \begin{subfigure}{0.5\textwidth} + \centering + \scalebox{0.5}{\input{figures/nasusRepeat.pgf}} + \subcaption{AMD Repeat Benchmark}\label{f:RepeatAMD} + \end{subfigure}\hfill + \begin{subfigure}{0.5\textwidth} + \centering + \scalebox{0.5}{\input{figures/pykeRepeat.pgf}} + \subcaption{Intel Repeat Benchmark}\label{f:RepeatIntel} + \end{subfigure} + \caption{The repeat benchmark comparing actor systems (lower is better).} +\end{figure} + +The repeat microbenchmark also evaluates the executor. It stresses the executor's ability to withstand contention on queues, as it repeatedly fans out messages from a single client to 100000 servers who then all respond to the client. After this scatter and gather repeats 200 times the benchmark terminates. The messages from the servers to the client will likely all come in on the same queue, resulting in high contention. As such this benchmark will not scale with the number of processors, since more processors will result in higher contention. In Figure~\ref{f:RepeatAMD} we can see that \CFA performs well compared to \uC, however by less of a margin than the executor benchmark. One factor in this result is that the contention on the queues poses a significant bottleneck. As such the gains from using the copy queue are much less apparent. + +\begin{figure} + \centering + \begin{subfigure}{0.5\textwidth} + \centering + \scalebox{0.5}{\input{figures/nasusCFARepeat.pgf}} + \subcaption{AMD \CFA Repeat Benchmark}\label{f:cfaRepeatAMD} + \end{subfigure}\hfill + \begin{subfigure}{0.5\textwidth} + \centering + \scalebox{0.5}{\input{figures/pykeCFARepeat.pgf}} + \subcaption{Intel \CFA Repeat Benchmark}\label{f:cfaRepeatIntel} + \end{subfigure} + \caption{The repeat benchmark comparing \CFA stealing heuristics (lower is better).} +\end{figure} + +In Figure~\ref{f:RepeatIntel} \uC and \CFA are very comparable. +In comparison with the other systems \uC does well on the repeat benchmark since it does not have work stealing. The client of this experiment is long running and maintains a lot of state, as it needs to know the handles of all the servers. When stealing the client or its respective queue (in \CFA's inverted model), moving the client incurs a high cost due to cache invalidation. As such stealing the client can result in a hit in performance. +This result is shown in Figure~\ref{f:cfaRepeatAMD} and \ref{f:cfaRepeatIntel} where the no-stealing version of \CFA performs better than both stealing variations. +In particular on the Intel machine in Figure~\ref{f:cfaRepeatIntel}, the cost of stealing is higher, which can be seen in the vertical shift of Akka, CAF and CFA results in Figure~\ref{f:RepeatIntel} (\uC and ProtoActor do not have work stealing). The shift for CAF is particularly large, which further supports the hypothesis that CAF's work stealing is particularly eager. +In both the executor and the repeat benchmark CAF performs poorly. It is hypothesized that CAF has an aggressive work stealing algorithm, that eagerly attempts to steal. This results in poor performance in benchmarks with small messages containing little work per message. On the other hand, in \ref{f:MatrixAMD} CAF performs much better since each message has a large amount of work, and few messages are sent, so the eager work stealing allows for the clean up of loose ends to occur faster. This hypothesis stems from experimentation with \CFA. CAF uses a randomized work stealing heuristic. In \CFA if the system is tuned so that it steals work much more eagerly with a randomized it was able to replicate the results that CAF achieves in the matrix benchmark, but this tuning performed much worse on all other microbenchmarks that we present, since they all perform a small amount of work per message. + +\begin{table}[t] + \centering + \setlength{\extrarowheight}{2pt} + \setlength{\tabcolsep}{5pt} + + \caption{Executor Program Memory High Watermark} + \label{t:ExecutorMemory} + \begin{tabular}{*{5}{r|}r} + & \multicolumn{1}{c|}{\CFA} & \multicolumn{1}{c|}{CAF} & \multicolumn{1}{c|}{Akka} & \multicolumn{1}{c|}{\uC} & \multicolumn{1}{c@{}}{ProtoActor} \\ + \hline + AMD & \input{data/pykeExecutorMem} \\ + \hline + Intel & \input{data/nasusExecutorMem} + \end{tabular} +\end{table} + +Figure~\ref{t:ExecutorMemory} shows the high memory watermark of the actor systems when running the executor benchmark on 48 cores. \CFA has a high watermark relative to the other non-garbage collected systems \uC, and CAF. This is a result of the copy queue data structure, as it will overallocate storage and not clean up eagerly, whereas the per envelope allocations will always allocate exactly the amount of storage needed. + +\subsection{Matrix Multiply} +The matrix benchmark evaluates the actor systems in a practical application, where actors concurrently multiplies two matrices. The majority of the computation in this benchmark involves computing the final matrix, so this benchmark stresses the actor systems' ability to have actors run work, rather than stressing the executor or message sending system. + +Given $Z_{m,r} = X_{m,n} \cdot Y_{n,r}$, the matrix multiply is defined as: +\begin{displaymath} +X_{i,j} \cdot Y_{j,k} = \left( \sum_{c=1}^{j} X_{row,c}Y_{c,column} \right)_{i,k} +\end{displaymath} + +The benchmark uses input matrices $X$ and $Y$ that are both $3072$ by $3072$ in size. An actor is made for each row of $X$ and is passed via message the information needed to calculate a row of the result matrix $Z$. + +Given that the bottleneck of the benchmark is the computation of the result matrix, it follows that the results in Figures~\ref{f:MatrixAMD} and \ref{f:MatrixIntel} are clustered closer than other experiments. In Figure~\ref{f:MatrixAMD} \uC and \CFA have identical performance and in Figure~\ref{f:MatrixIntel} \uC pulls ahead og \CFA after 24 cores likely due to costs associated with work stealing while hyperthreading. As mentioned in \label{s:executorPerf}, it is hypothesized that CAF performs better in this benchmark compared to others due to its eager work stealing implementation. In Figures~\ref{f:cfaMatrixAMD} and \ref{f:cfaMatrixIntel} there is little negligible performance difference across \CFA stealing heuristics. + +\begin{figure} + \centering + \begin{subfigure}{0.5\textwidth} + \centering + \scalebox{0.5}{\input{figures/nasusMatrix.pgf}} + \subcaption{AMD Matrix Benchmark}\label{f:MatrixAMD} + \end{subfigure}\hfill + \begin{subfigure}{0.5\textwidth} + \centering + \scalebox{0.5}{\input{figures/pykeMatrix.pgf}} + \subcaption{Intel Matrix Benchmark}\label{f:MatrixIntel} + \end{subfigure} + \caption{The matrix benchmark comparing actor systems (lower is better).} +\end{figure} + +\begin{figure} + \centering + \begin{subfigure}{0.5\textwidth} + \centering + \scalebox{0.5}{\input{figures/nasusCFAMatrix.pgf}} + \subcaption{AMD \CFA Matrix Benchmark}\label{f:cfaMatrixAMD} + \end{subfigure}\hfill + \begin{subfigure}{0.5\textwidth} + \centering + \scalebox{0.5}{\input{figures/pykeCFAMatrix.pgf}} + \subcaption{Intel \CFA Matrix Benchmark}\label{f:cfaMatrixIntel} + \end{subfigure} + \caption{The matrix benchmark comparing \CFA stealing heuristics (lower is better).} +\end{figure} Index: doc/theses/colby_parsons_MMAth/text/frontpgs.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/frontpgs.tex (revision 0da718119b2ce64d4fe7e641a9d6cdfd960b073d) +++ doc/theses/colby_parsons_MMAth/text/frontpgs.tex (revision 0da718119b2ce64d4fe7e641a9d6cdfd960b073d) @@ -0,0 +1,165 @@ +% T I T L E P A G E +% ------------------- +% Last updated May 24, 2011, by Stephen Carr, IST-Client Services +% The title page is counted as page `i' but we need to suppress the +% page number. We also don't want any headers or footers. +\pagestyle{empty} +\pagenumbering{roman} + +% The contents of the title page are specified in the "titlepage" +% environment. +\begin{titlepage} + \begin{center} + \vspace*{1.0cm} + + \Huge + {\bf High Level Concurrency in \CFA} + + \vspace*{1.0cm} + + \normalsize + by \\ + + \vspace*{1.0cm} + + \Large + Colby Parsons \\ + + \vspace*{3.0cm} + + \normalsize + A thesis \\ + presented to the University of Waterloo \\ + in fulfillment of the \\ + thesis requirement for the degree of \\ + Master of Mathematics \\ + in \\ + Computer Science \\ + + \vspace*{2.0cm} + + Waterloo, Ontario, Canada, 2023 \\ + + \vspace*{1.0cm} + + \copyright\ Colby Parsons 2023 \\ + \end{center} +\end{titlepage} + +% The rest of the front pages should contain no headers and be numbered using Roman numerals starting with `ii' +\pagestyle{plain} +\setcounter{page}{2} + +\cleardoublepage % Ends the current page and causes all figures and tables that have so far appeared in the input to be printed. +% In a two-sided printing style, it also makes the next page a right-hand (odd-numbered) page, producing a blank page if necessary. + + + +% D E C L A R A T I O N P A G E +% ------------------------------- + % The following is the sample Delaration Page as provided by the GSO + % December 13th, 2006. It is designed for an electronic thesis. + \noindent + I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. + \bigskip + + \noindent + I understand that my thesis may be made electronically available to the public. + +\cleardoublepage +%\newpage + +% A B S T R A C T +% --------------- + +\begin{center}\textbf{Abstract}\end{center} + +Concurrent programs are notoriously hard to program and even harder to debug. Furthermore concurrent programs must be performant, as the introduction of concurrency into a program is often done to achieve some form of speedup. This thesis presents a suite of high level concurrent language features in \CFA, all of which are implemented with the aim of improving the performance, productivity, and safety of concurrent programs. \CFA is a non object-oriented programming language that extends C. The foundation for concurrency in \CFA was laid by Thierry Delisle, who implemented coroutines, user-level threads, and monitors\cite{Delisle18}. This thesis builds upon that groundwork and introduces a suite of concurrent features as its main contribution. The features include a diverse set of polymorphic locks, Go-like channels, mutex statements (similar to \CC scoped locks or Java synchronized statement), an actor system, and a Go-like select statement. The root idea behind these features are not new, but the \CFA implementations improve upon the original ideas in performance, productivity, and safety. + +\cleardoublepage +%\newpage + +% A C K N O W L E D G E M E N T S +% ------------------------------- + +\begin{center}\textbf{Acknowledgements}\end{center} + +\noindent +To begin, I would like to thank my supervisor Professor Peter Buhr. Your guidance, wisdom and support has been invaluable in my learning and development of my research abilities, and in the implementation and writing of this thesis. +\bigskip + +\noindent +Thank you Thierry Delisle for your insight and knowledge regarding all things concurrency. You challenged my ideas and taught me skills that aid in both thinking about and writing concurrent programs. +\bigskip + +\noindent +Thanks to Michael Brooks, Andrew Beach, Fangren Yu, and Jiada Liang. Your work on \CFA continues to make it the best language it can be, and our discussions in meetings clarified the ideas that make up this thesis. +\bigskip + +\noindent +Finally, this work could not have happened without the financial support of David R. Cheriton School of Computer Science and the corporate partnership with Huawei Ltd. + +\cleardoublepage +%\newpage + +% % D E D I C A T I O N +% % ------------------- + +% \begin{center}\textbf{Dedication}\end{center} + +% +% \cleardoublepage +% %\newpage + +% T A B L E O F C O N T E N T S +% --------------------------------- +\renewcommand\contentsname{Table of Contents} +\tableofcontents +\cleardoublepage +\phantomsection +%\newpage + +% L I S T O F T A B L E S +% --------------------------- +\addcontentsline{toc}{chapter}{List of Tables} +\listoftables +\cleardoublepage +\phantomsection % allows hyperref to link to the correct page +%\newpage + +% L I S T O F F I G U R E S +% ----------------------------- +\addcontentsline{toc}{chapter}{List of Figures} +\listoffigures +\cleardoublepage +\phantomsection % allows hyperref to link to the correct page +%\newpage + +% L I S T O F L I S T I N G S +% ----------------------------- +\addcontentsline{toc}{chapter}{List of Listings} +\lstlistoflistings +\cleardoublepage +\phantomsection % allows hyperref to link to the correct page +%\newpage + +% L I S T O F S Y M B O L S +% ----------------------------- +% To include a Nomenclature section +% \addcontentsline{toc}{chapter}{\textbf{Nomenclature}} +% \renewcommand{\nomname}{Nomenclature} +% \printglossary +% \cleardoublepage +% \phantomsection % allows hyperref to link to the correct page +% \newpage + +% L I S T O F T A B L E S +% ----------------------------- +\addcontentsline{toc}{chapter}{List of Acronyms} +\printglossary[type=\acronymtype,title={List of Acronyms}] +\cleardoublepage +\phantomsection % allows hyperref to link to the correct page + +% Change page numbering back to Arabic numerals +\pagenumbering{arabic} + Index: doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex (revision 0da718119b2ce64d4fe7e641a9d6cdfd960b073d) +++ doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex (revision 0da718119b2ce64d4fe7e641a9d6cdfd960b073d) @@ -0,0 +1,5 @@ +% ====================================================================== +% ====================================================================== +\chapter{Mutex Statement}\label{s:mutexstmt} +% ====================================================================== +% ======================================================================