Changeset b199e54 for doc/papers/concurrency/Paper.tex
- Timestamp:
- Jun 27, 2018, 6:37:47 PM (6 years ago)
- Branches:
- ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, no_list, persistent-indexer, pthread-emulation, qualifiedEnum
- Children:
- 6d6cf5a
- Parents:
- 203c667
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/papers/concurrency/Paper.tex
r203c667 rb199e54 21 21 \renewcommand{\thesubfigure}{(\Alph{subfigure})} 22 22 \captionsetup{justification=raggedright,singlelinecheck=false} 23 \usepackage{siunitx} 24 \sisetup{binary-units=true} 23 \usepackage{dcolumn} % align decimal points in tables 25 24 26 25 \hypersetup{breaklinks=true} … … 258 257 An easier approach for programmers is to support higher-level constructs as the basis of concurrency. 259 258 Indeed, for highly productive concurrent programming, high-level approaches are much more popular~\cite{Hochstein05}. 260 Examples of high-level approaches are task (work) based~\cite{TBB}, implicit threading~\cite{OpenMP}, monitors~\cite{Java}, channels~\cite{CSP,Go}, and message passing~\cite{Erlang,MPI}.259 Examples of high-level approaches are jobs (tasks) based~\cite{TBB}, implicit threading~\cite{OpenMP}, monitors~\cite{Java}, channels~\cite{CSP,Go}, and message passing~\cite{Erlang,MPI}. 261 260 262 261 The following terminology is used. … … 438 437 \begin{tabular}{@{}ll@{\hspace{\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}} 439 438 \begin{cfa} 440 int ++? 441 int ?++ 442 int `?+?` 439 int ++?(int op); 440 int ?++(int op); 441 int `?+?`(int op1, int op2); 443 442 int ?<=?(int op1, int op2); 444 443 int ?=? (int & op1, int op2); … … 508 507 \label{s:ParametricPolymorphism} 509 508 510 The signature feature of \CFA is parametric-polymorphic routines~\cite{ } with routines generalized using a @forall@ clause (giving the language its name), which allow separately compiled routines to support generic usage over multiple types.509 The signature feature of \CFA is parametric-polymorphic routines~\cite{Cforall} with routines generalized using a @forall@ clause (giving the language its name), which allow separately compiled routines to support generic usage over multiple types. 511 510 For example, the following sum routine works for any type that supports construction from 0 and addition: 512 511 \begin{cfa} … … 663 662 \end{lrbox} 664 663 665 \subfloat[3 States: global variables]{\ label{f:GlobalVariables}\usebox\myboxA}664 \subfloat[3 States: global variables]{\usebox\myboxA} 666 665 \qquad 667 \subfloat[1 State: external variables]{\ label{f:ExternalState}\usebox\myboxB}666 \subfloat[1 State: external variables]{\usebox\myboxB} 668 667 \caption{C Fibonacci Implementations} 669 668 \label{f:C-fibonacci} … … 980 979 symmetric_coroutine<>::yield_type 981 980 \end{cfa} 982 Similarly, the canonical threading paradigm is often based on routine pointers, \eg @pthreads@~\cite{ pthreads}, \Csharp~\cite{Csharp}, Go~\cite{Go}, and Scala~\cite{Scala}.981 Similarly, the canonical threading paradigm is often based on routine pointers, \eg @pthreads@~\cite{Butenhof97}, \Csharp~\cite{Csharp}, Go~\cite{Go}, and Scala~\cite{Scala}. 983 982 However, the generic thread-handle (identifier) is limited (few operations), unless it is wrapped in a custom type. 984 983 \begin{cfa} … … 1400 1399 } 1401 1400 \end{cfa} 1402 This example shows a trivial solution to the bank-account transfer problem ~\cite{BankTransfer}.1401 This example shows a trivial solution to the bank-account transfer problem. 1403 1402 Without multi- and bulk acquire, the solution to this problem requires careful engineering. 1404 1403 … … 1409 1408 Like Java, \CFA offers an alternative @mutex@ statement to reduce refactoring and naming. 1410 1409 \begin{cquote} 1411 \begin{tabular}{@{}c|@{\hspace{\parindentlnth}}c@{}} 1412 routine call & @mutex@ statement \\ 1410 \begin{tabular}{@{}l@{\hspace{3\parindentlnth}}l@{}} 1413 1411 \begin{cfa} 1414 1412 monitor M {}; … … 1430 1428 1431 1429 \end{cfa} 1430 \\ 1431 \multicolumn{1}{c}{\textbf{routine call}} & \multicolumn{1}{c}{\lstinline@mutex@ \textbf{statement}} 1432 1432 \end{tabular} 1433 1433 \end{cquote} … … 1572 1572 wait( Girls[ccode] ); 1573 1573 GirlPhNo = phNo; 1574 exchange.signal();1574 `exchange.signal();` 1575 1575 } else { 1576 1576 GirlPhNo = phNo; 1577 signal( Boys[ccode] );1578 exchange.wait();1577 `signal( Boys[ccode] );` 1578 `exchange.wait();` 1579 1579 } // if 1580 1580 return BoyPhNo; … … 1602 1602 } else { 1603 1603 GirlPhNo = phNo; // make phone number available 1604 signal_block( Boys[ccode] );// restart boy1604 `signal_block( Boys[ccode] );` // restart boy 1605 1605 1606 1606 } // if … … 1657 1657 Waitfor statically verifies the released monitors are the same as the acquired mutex-parameters of the given routine or routine pointer. 1658 1658 To statically verify the released monitors match with the accepted routine's mutex parameters, the routine (pointer) prototype must be accessible. 1659 1660 When an overloaded routine appears in an @waitfor@ statement, calls to any routine with that name are accepted. 1661 The rationale is that members with the same name should perform a similar function, and therefore, all should be eligible to accept a call. 1662 As always, overloaded routines can be disambiguated using a cast: 1663 \begin{cfa} 1664 void rtn( M & mutex m ); 1665 `int` rtn( M & mutex m ); 1666 waitfor( (`int` (*)( M & mutex ))rtn, m1, m2 ); 1667 \end{cfa} 1659 1668 1660 1669 Given the ability to release a subset of acquired monitors can result in a \newterm{nested monitor}~\cite{Lister77} deadlock. … … 1759 1768 This solution has the benefit that complexity is encapsulated into only two actions: passing monitors to the next owner when they should be released and conditionally waking threads if all conditions are met. 1760 1769 1761 \begin{comment}1762 Figure~\ref{f:dependency} shows a slightly different example where a third thread is waiting on monitor @A@, using a different condition variable.1763 Because the third thread is signalled when secretly holding @B@, the goal becomes unreachable.1764 Depending on the order of signals (listing \ref{f:dependency} line \ref{line:signal-ab} and \ref{line:signal-a}) two cases can happen:1765 1766 \paragraph{Case 1: thread $\alpha$ goes first.} In this case, the problem is that monitor @A@ needs to be passed to thread $\beta$ when thread $\alpha$ is done with it.1767 \paragraph{Case 2: thread $\beta$ goes first.} In this case, the problem is that monitor @B@ needs to be retained and passed to thread $\alpha$ along with monitor @A@, which can be done directly or possibly using thread $\beta$ as an intermediate.1768 \\1769 1770 Note that ordering is not determined by a race condition but by whether signalled threads are enqueued in FIFO or FILO order.1771 However, regardless of the answer, users can move line \ref{line:signal-a} before line \ref{line:signal-ab} and get the reverse effect for listing \ref{f:dependency}.1772 1773 In both cases, the threads need to be able to distinguish, on a per monitor basis, which ones need to be released and which ones need to be transferred, which means knowing when to release a group becomes complex and inefficient (see next section) and therefore effectively precludes this approach.1774 1775 1776 \subsubsection{Dependency graphs}1777 1778 \begin{figure}1779 \begin{multicols}{3}1780 Thread $\alpha$1781 \begin{cfa}[numbers=left, firstnumber=1]1782 acquire A1783 acquire A & B1784 wait A & B1785 release A & B1786 release A1787 \end{cfa}1788 \columnbreak1789 Thread $\gamma$1790 \begin{cfa}[numbers=left, firstnumber=6, escapechar=|]1791 acquire A1792 acquire A & B1793 |\label{line:signal-ab}|signal A & B1794 |\label{line:release-ab}|release A & B1795 |\label{line:signal-a}|signal A1796 |\label{line:release-a}|release A1797 \end{cfa}1798 \columnbreak1799 Thread $\beta$1800 \begin{cfa}[numbers=left, firstnumber=12, escapechar=|]1801 acquire A1802 wait A1803 |\label{line:release-aa}|release A1804 \end{cfa}1805 \end{multicols}1806 \begin{cfa}[caption={Pseudo-code for the three thread example.},label={f:dependency}]1807 \end{cfa}1808 \begin{center}1809 \input{dependency}1810 \end{center}1811 \caption{Dependency graph of the statements in listing \ref{f:dependency}}1812 \label{fig:dependency}1813 \end{figure}1814 1815 In listing \ref{f:int-bulk-cfa}, there is a solution that satisfies both barging prevention and mutual exclusion.1816 If ownership of both monitors is transferred to the waiter when the signaller releases @A & B@ and then the waiter transfers back ownership of @A@ back to the signaller when it releases it, then the problem is solved (@B@ is no longer in use at this point).1817 Dynamically finding the correct order is therefore the second possible solution.1818 The problem is effectively resolving a dependency graph of ownership requirements.1819 Here even the simplest of code snippets requires two transfers and has a super-linear complexity.1820 This complexity can be seen in listing \ref{f:explosion}, which is just a direct extension to three monitors, requires at least three ownership transfer and has multiple solutions.1821 Furthermore, the presence of multiple solutions for ownership transfer can cause deadlock problems if a specific solution is not consistently picked; In the same way that multiple lock acquiring order can cause deadlocks.1822 \begin{figure}1823 \begin{multicols}{2}1824 \begin{cfa}1825 acquire A1826 acquire B1827 acquire C1828 wait A & B & C1829 release C1830 release B1831 release A1832 \end{cfa}1833 1834 \columnbreak1835 1836 \begin{cfa}1837 acquire A1838 acquire B1839 acquire C1840 signal A & B & C1841 release C1842 release B1843 release A1844 \end{cfa}1845 \end{multicols}1846 \begin{cfa}[caption={Extension to three monitors of listing \ref{f:int-bulk-cfa}},label={f:explosion}]1847 \end{cfa}1848 \end{figure}1849 1850 Given the three threads example in listing \ref{f:dependency}, figure \ref{fig:dependency} shows the corresponding dependency graph that results, where every node is a statement of one of the three threads, and the arrows the dependency of that statement (\eg $\alpha1$ must happen before $\alpha2$).1851 The extra challenge is that this dependency graph is effectively post-mortem, but the runtime system needs to be able to build and solve these graphs as the dependencies unfold.1852 Resolving dependency graphs being a complex and expensive endeavour, this solution is not the preferred one.1853 \end{comment}1854 1855 1856 \begin{comment}1857 \section{External scheduling} \label{extsched}1858 1859 \begin{table}1860 \begin{tabular}{|c|c|c|}1861 Internal Scheduling & External Scheduling & Go\\1862 \hline1863 \begin{uC++}[tabsize=3]1864 _Monitor Semaphore {1865 condition c;1866 bool inUse;1867 public:1868 void P() {1869 if(inUse)1870 wait(c);1871 inUse = true;1872 }1873 void V() {1874 inUse = false;1875 signal(c);1876 }1877 }1878 \end{uC++}&\begin{uC++}[tabsize=3]1879 _Monitor Semaphore {1880 1881 bool inUse;1882 public:1883 void P() {1884 if(inUse)1885 _Accept(V);1886 inUse = true;1887 }1888 void V() {1889 inUse = false;1890 1891 }1892 }1893 \end{uC++}&\begin{Go}[tabsize=3]1894 type MySem struct {1895 inUse bool1896 c chan bool1897 }1898 1899 // acquire1900 func (s MySem) P() {1901 if s.inUse {1902 select {1903 case <-s.c:1904 }1905 }1906 s.inUse = true1907 }1908 1909 // release1910 func (s MySem) V() {1911 s.inUse = false1912 1913 // This actually deadlocks1914 // when single thread1915 s.c <- false1916 }1917 \end{Go}1918 \end{tabular}1919 \caption{Different forms of scheduling.}1920 \label{tbl:sched}1921 \end{table}1922 1923 For the @P@ member above using internal scheduling, the call to @wait@ only guarantees that @V@ is the last routine to access the monitor, allowing a third routine, say @isInUse()@, acquire mutual exclusion several times while routine @P@ is waiting.1924 On the other hand, external scheduling guarantees that while routine @P@ is waiting, no other routine than @V@ can acquire the monitor.1925 \end{comment}1926 1927 1770 1928 1771 \subsection{Loose Object Definitions} … … 1973 1816 The accepted list is a variable-sized array of accepted routine pointers, so the single instruction bitmask comparison is replaced by dereferencing a pointer followed by a linear search. 1974 1817 1975 \begin{comment}1976 \begin{figure}1977 \begin{cfa}[caption={Example of nested external scheduling},label={f:nest-ext}]1978 monitor M {};1979 void foo( M & mutex a ) {}1980 void bar( M & mutex b ) {1981 // Nested in the waitfor(bar, c) call1982 waitfor(foo, b);1983 }1984 void baz( M & mutex c ) {1985 waitfor(bar, c);1986 }1987 1988 \end{cfa}1989 \end{figure}1990 1991 Note that in the right picture, tasks need to always keep track of the monitors associated with mutex routines, and the routine mask needs to have both a routine pointer and a set of monitors, as is discussed in the next section.1992 These details are omitted from the picture for the sake of simplicity.1993 1994 At this point, a decision must be made between flexibility and performance.1995 Many design decisions in \CFA achieve both flexibility and performance, for example polymorphic routines add significant flexibility but inlining them means the optimizer can easily remove any runtime cost.1996 Here, however, the cost of flexibility cannot be trivially removed.1997 In the end, the most flexible approach has been chosen since it allows users to write programs that would otherwise be hard to write.1998 This decision is based on the assumption that writing fast but inflexible locks is closer to a solved problem than writing locks that are as flexible as external scheduling in \CFA.1999 \end{comment}2000 2001 1818 2002 1819 \subsection{Multi-Monitor Scheduling} … … 2009 1826 void f( M & mutex m1 ); 2010 1827 void g( M & mutex m1, M & mutex m2 ) { 2011 waitfor( f ); $\C{ // pass m1 or m2 to f?}$1828 waitfor( f ); $\C{\color{red}// pass m1 or m2 to f?}$ 2012 1829 } 2013 1830 \end{cfa} 2014 1831 The solution is for the programmer to disambiguate: 2015 1832 \begin{cfa} 2016 waitfor( f, m2 ); $\C{ // wait for call to f with argument m2}$2017 \end{cfa} 2018 Routine @g@ has acquired both locks, so when routine @f@ is called, the lock for monitor @m2@ is passed from @g@ to @f@ (while @g@ still holds lock @m1@).1833 waitfor( f, m2 ); $\C{\color{red}// wait for call to f with argument m2}$ 1834 \end{cfa} 1835 Routine @g@ has acquired both locks, so when routine @f@ is called, the lock for monitor @m2@ is passed from @g@ to @f@, while @g@ still holds lock @m1@. 2019 1836 This behaviour can be extended to the multi-monitor @waitfor@ statement. 2020 1837 \begin{cfa} … … 2022 1839 void f( M & mutex m1, M & mutex m2 ); 2023 1840 void g( M & mutex m1, M & mutex m2 ) { 2024 waitfor( f, m1, m2 ); $\C{ // wait for call to f with arguments m1 and m2}$1841 waitfor( f, m1, m2 ); $\C{\color{red}// wait for call to f with arguments m1 and m2}$ 2025 1842 } 2026 1843 \end{cfa} 2027 1844 Again, the set of monitors passed to the @waitfor@ statement must be entirely contained in the set of monitors already acquired by accepting routine. 2028 1845 2029 An important behaviour to note is when a set of monitors only match partially: 2030 \begin{cfa} 2031 mutex struct A {}; 2032 mutex struct B {}; 2033 void g( A & mutex m1, B & mutex m2 ) { 1846 Note, for internal and external scheduling with multiple monitors, a signalling or accepting thread must match exactly, \ie partial matching results in waiting. 1847 \begin{cquote} 1848 \lstDeleteShortInline@% 1849 \begin{tabular}{@{}l@{\hspace{\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}} 1850 \begin{cfa} 1851 monitor M1 {} m11, m12; 1852 monitor M2 {} m2; 1853 condition c; 1854 void f( M1 & mutex m1, M2 & mutex m2 ) { 1855 signal( c ); 1856 } 1857 void g( M1 & mutex m1, M2 & mutex m2 ) { 1858 wait( c ); 1859 } 1860 g( `m11`, m2 ); // block on accept 1861 f( `m12`, m2 ); // cannot fulfil 1862 \end{cfa} 1863 & 1864 \begin{cfa} 1865 monitor M1 {} m11, m12; 1866 monitor M2 {} m2; 1867 1868 void f( M1 & mutex m1, M2 & mutex m2 ) { 1869 1870 } 1871 void g( M1 & mutex m1, M2 & mutex m2 ) { 2034 1872 waitfor( f, m1, m2 ); 2035 1873 } 2036 A a1, a2; 2037 B b; 2038 void foo() { 2039 g( a1, b ); // block on accept 2040 } 2041 void bar() { 2042 f( a2, b ); // fulfill cooperation 2043 } 2044 \end{cfa} 2045 While the equivalent can happen when using internal scheduling, the fact that conditions are specific to a set of monitors means that users have to use two different condition variables. 2046 In both cases, partially matching monitor sets does not wakeup the waiting thread. 2047 It is also important to note that in the case of external scheduling the order of parameters is irrelevant; @waitfor(f,a,b)@ and @waitfor(f,b,a)@ are indistinguishable waiting condition. 2048 2049 2050 \subsection{\protect\lstinline|waitfor| Semantics} 2051 2052 Syntactically, the @waitfor@ statement takes a routine identifier and a set of monitors. 2053 While the set of monitors can be any list of expressions, the routine name is more restricted because the compiler validates at compile time the validity of the routine type and the parameters used with the @waitfor@ statement. 2054 It checks that the set of monitors passed in matches the requirements for a routine call. 2055 Figure~\ref{f:waitfor} shows various usages of the waitfor statement and which are acceptable. 2056 The choice of the routine type is made ignoring any non-@mutex@ parameter. 2057 One limitation of the current implementation is that it does not handle overloading, but overloading is possible. 1874 g( `m11`, m2 ); // block on accept 1875 f( `m12`, m2 ); // cannot fulfil 1876 \end{cfa} 1877 \end{tabular} 1878 \lstMakeShortInline@% 1879 \end{cquote} 1880 1881 1882 \subsection{Extended \protect\lstinline@waitfor@} 1883 1884 The extended form of the @waitfor@ statement conditionally accepts one of a group of mutex routines and allows a specific action to be performed \emph{after} the mutex routine finishes. 1885 \begin{cfa} 1886 `when` ( $\emph{conditional-expression}$ ) $\C{// optional guard}$ 1887 waitfor( $\emph{mutex-member-name}$ ) 1888 $\emph{statement}$ $\C{// action after call}$ 1889 `or` `when` ( $\emph{conditional-expression}$ ) $\C{// optional guard}$ 1890 waitfor( $\emph{mutex-member-name}$ ) 1891 $\emph{statement}$ $\C{// action after call}$ 1892 `or` ... $\C{// list of waitfor clauses}$ 1893 `when` ( $\emph{conditional-expression}$ ) $\C{// optional guard}$ 1894 `timeout` $\C{// optional terminating timeout clause}$ 1895 $\emph{statement}$ $\C{// action after timeout}$ 1896 `when` ( $\emph{conditional-expression}$ ) $\C{// optional guard}$ 1897 `else` $\C{// optional terminating clause}$ 1898 $\emph{statement}$ $\C{// action when no immediate calls}$ 1899 \end{cfa} 1900 For a @waitfor@ clause to be executed, its @when@ must be true and an outstanding call to its corresponding member(s) must exist. 1901 The \emph{conditional-expression} of a @when@ may call a routine, but the routine must not block or context switch. 1902 If there are several mutex calls that can be accepted, selection occurs top-to-bottom in the @waitfor@ clauses versus non-deterministically. 1903 If some accept guards are true and there are no outstanding calls to these members, the acceptor is accept-blocked until a call to one of these members is made. 1904 If all the accept guards are false, the statement does nothing, unless there is a terminating @else@ clause with a true guard, which is executed instead. 1905 Hence, the terminating @else@ clause allows a conditional attempt to accept a call without blocking. 1906 If there is a @timeout@ clause, it provides an upper bound on waiting, and can only appear with a conditional @else@, otherwise the timeout cannot be triggered. 1907 In all cases, the statement following is executed \emph{after} a clause is executed to know which of the clauses executed. 1908 1909 A group of conditional @waitfor@ clauses is \emph{not} the same as a group of @if@ statements, e.g.: 1910 \begin{cfa} 1911 if ( C1 ) waitfor( mem1 ); when ( C1 ) waitfor( mem1 ); 1912 else if ( C2 ) waitfor( mem2 ); or when ( C2 ) waitfor( mem2 ); 1913 \end{cfa} 1914 The left example accepts only @mem1@ if @C1@ is true or only @mem2@ if @C2@ is true. 1915 The right example accepts either @mem1@ or @mem2@ if @C1@ and @C2@ are true. 1916 1917 An interesting use of @waitfor@ is accepting the @mutex@ destructor to know when an object deallocated. 1918 \begin{cfa} 1919 void insert( Buffer(T) & mutex buffer, T elem ) with( buffer ) { 1920 if ( count == BufferSize ) 1921 waitfor( remove, buffer ) { 1922 elements[back] = elem; 1923 back = ( back + 1 ) % BufferSize; 1924 count += 1; 1925 } or `waitfor( ^?{}, buffer )` throw insertFail; 1926 } 1927 \end{cfa} 1928 However, the @waitfor@ semantics do not work, since using an object after its destructor is called is undefined. 1929 Therefore, to make this useful capability work, the semantics for accepting the destructor is the same as @signal@, \ie the call to the destructor is placed on the urgent queue and the acceptor continues execution, which throws an exception to the acceptor and then deallocates the object. 1930 Accepting the destructor is an idiomatic way to terminate a thread in \CFA. 1931 1932 1933 \subsection{\protect\lstinline@mutex@ Threads} 1934 1935 Threads in \CFA are monitors, so all monitor features are available when using threads. 1936 Figure~\ref{f:pingpong} shows an example of two threads calling and accepting calls from each other in a cycle. 1937 Note, both ping/pong threads are globally declared, @pi@/@po@, and hence, start (and possibly complete) before the program starts. 1938 2058 1939 \begin{figure} 2059 \begin{cfa}[caption={Various correct and incorrect uses of the waitfor statement},label={f:waitfor}] 2060 monitor A{}; 2061 monitor B{}; 2062 2063 void f1( A & mutex ); 2064 void f2( A & mutex, B & mutex ); 2065 void f3( A & mutex, int ); 2066 void f4( A & mutex, int ); 2067 void f4( A & mutex, double ); 2068 2069 void foo( A & mutex a1, A & mutex a2, B & mutex b1, B & b2 ) { 2070 A * ap = & a1; 2071 void (*fp)( A & mutex ) = f1; 2072 2073 waitfor(f1, a1); // Correct : 1 monitor case 2074 waitfor(f2, a1, b1); // Correct : 2 monitor case 2075 waitfor(f3, a1); // Correct : non-mutex arguments are ignored 2076 waitfor(f1, *ap); // Correct : expression as argument 2077 2078 waitfor(f1, a1, b1); // Incorrect : Too many mutex arguments 2079 waitfor(f2, a1); // Incorrect : Too few mutex arguments 2080 waitfor(f2, a1, a2); // Incorrect : Mutex arguments don't match 2081 waitfor(f1, 1); // Incorrect : 1 not a mutex argument 2082 waitfor(f9, a1); // Incorrect : f9 routine does not exist 2083 waitfor(*fp, a1 ); // Incorrect : fp not an identifier 2084 waitfor(f4, a1); // Incorrect : f4 ambiguous 2085 2086 waitfor(f2, a1, b2); // Undefined behaviour : b2 not mutex 2087 } 2088 \end{cfa} 1940 \lstDeleteShortInline@% 1941 \begin{cquote} 1942 \begin{cfa} 1943 thread Ping {} pi; 1944 thread Pong {} po; 1945 void ping( Ping & mutex ) {} 1946 void pong( Pong & mutex ) {} 1947 int main() {} 1948 \end{cfa} 1949 \begin{tabular}{@{}l@{\hspace{3\parindentlnth}}l@{}} 1950 \begin{cfa} 1951 void main( Ping & pi ) { 1952 for ( int i = 0; i < 10; i += 1 ) { 1953 `waitfor( ping, pi );` 1954 `pong( po );` 1955 } 1956 } 1957 \end{cfa} 1958 & 1959 \begin{cfa} 1960 void main( Pong & po ) { 1961 for ( int i = 0; i < 10; i += 1 ) { 1962 `ping( pi );` 1963 `waitfor( pong, po );` 1964 } 1965 } 1966 \end{cfa} 1967 \end{tabular} 1968 \lstMakeShortInline@% 1969 \end{cquote} 1970 \caption{Threads ping/pong using external scheduling} 1971 \label{f:pingpong} 2089 1972 \end{figure} 2090 1973 2091 Finally, for added flexibility, \CFA supports constructing a complex @waitfor@ statement using the @or@, @timeout@ and @else@. 2092 Indeed, multiple @waitfor@ clauses can be chained together using @or@; this chain forms a single statement that uses baton pass to any routine that fits one of the routine+monitor set passed in. 2093 To enable users to tell which accepted routine executed, @waitfor@s are followed by a statement (including the null statement @;@) or a compound statement, which is executed after the clause is triggered. 2094 A @waitfor@ chain can also be followed by a @timeout@, to signify an upper bound on the wait, or an @else@, to signify that the call should be non-blocking, which checks for a matching routine call already arrived and otherwise continues. 2095 Any and all of these clauses can be preceded by a @when@ condition to dynamically toggle the accept clauses on or off based on some current state. 2096 Figure~\ref{f:waitfor2} demonstrates several complex masks and some incorrect ones. 1974 \section{Parallelism} 1975 1976 Historically, computer performance was about processor speeds. 1977 However, with heat dissipation being a direct consequence of speed increase, parallelism has become the new source for increased performance~\cite{Sutter05, Sutter05b}. 1978 Now, high-performance applications must care about parallelism, which requires concurrency. 1979 The lowest-level approach of parallelism is to use \newterm{kernel threads} in combination with semantics like @fork@, @join@, \etc. 1980 However, kernel threads are better as an implementation tool because of complexity and high cost. 1981 Therefore, different abstractions are layered onto kernel threads to simplify them. 1982 1983 1984 \subsection{User Threads with Preemption} 1985 1986 A direct improvement on kernel threads is user threads, \eg Erlang~\cite{Erlang} and \uC~\cite{uC++book}. 1987 This approach provides an interface that matches the language paradigms, more control over concurrency in the language runtime, and an abstract (and portable) interface to the underlying kernel threads across operating systems. 1988 In many cases, user threads can be used on a much larger scale (100,000 threads). 1989 Like kernel threads, user threads support preemption, which maximizes nondeterminism, but introduces concurrency errors: race, livelock, starvation, and deadlock. 1990 \CFA adopts user-threads as they represent the truest realization of concurrency and can build the following approaches and more, \eg actors~\cite{Actors}. 1991 1992 1993 \subsection{User Threads without Preemption (Fiber)} 1994 \label{s:fibers} 1995 1996 A variant of user thread is \newterm{fibers}, which removes preemption, \eg Go~\cite{Go}. 1997 Like functional programming, which removes mutation and its associated problems, removing preemption from concurrency reduces nondeterminism, hence race and deadlock errors are more difficult to generate. 1998 However, preemption is necessary for concurrency that relies on spinning, so there are a class of problems that cannot be programmed without preemption. 1999 2000 2001 \subsection{Thread Pools} 2002 2003 In contrast to direct threading is indirect \newterm{thread pools}, where small jobs (work units) are insert into a work pool for execution. 2004 If the jobs are dependent, \ie interact, there is an implicit/explicit dependency graph that ties them together. 2005 While removing direct concurrency, and hence the amount of context switching, thread pools significantly limit the interaction that can occur among jobs. 2006 Indeed, jobs should not block because that also block the underlying thread, which effectively means the CPU utilization, and therefore throughput, suffers. 2007 While it is possible to tune the thread pool with sufficient threads, it becomes difficult to obtain high throughput and good core utilization as job interaction increases. 2008 As well, concurrency errors return, which threads pools are suppose to mitigate. 2009 The gold standard for thread pool is Intel's TBB library~\cite{TBB}. 2010 2011 2012 \section{\protect\CFA Runtime Structure} 2013 2014 Figure~\ref{f:RunTimeStructure} illustrates the runtime structure of a \CFA program. 2015 In addition to the new kinds of objects introduced by \CFA, there are two more runtime entities used to control parallel execution. 2016 An executing thread is illustrated by its containment in a processor. 2097 2017 2098 2018 \begin{figure} 2099 \lstset{language=CFA,deletedelim=**[is][]{`}{`}} 2100 \begin{cfa} 2101 monitor A{}; 2102 2103 void f1( A & mutex ); 2104 void f2( A & mutex ); 2105 2106 void foo( A & mutex a, bool b, int t ) { 2107 waitfor(f1, a); $\C{// Correct : blocking case}$ 2108 2109 waitfor(f1, a) { $\C{// Correct : block with statement}$ 2110 sout | "f1" | endl; 2111 } 2112 waitfor(f1, a) { $\C{// Correct : block waiting for f1 or f2}$ 2113 sout | "f1" | endl; 2114 } or waitfor(f2, a) { 2115 sout | "f2" | endl; 2116 } 2117 waitfor(f1, a); or else; $\C{// Correct : non-blocking case}$ 2118 2119 waitfor(f1, a) { $\C{// Correct : non-blocking case}$ 2120 sout | "blocked" | endl; 2121 } or else { 2122 sout | "didn't block" | endl; 2123 } 2124 waitfor(f1, a) { $\C{// Correct : block at most 10 seconds}$ 2125 sout | "blocked" | endl; 2126 } or timeout( 10`s) { 2127 sout | "didn't block" | endl; 2128 } 2129 // Correct : block only if b == true if b == false, don't even make the call 2130 when(b) waitfor(f1, a); 2131 2132 // Correct : block only if b == true if b == false, make non-blocking call 2133 waitfor(f1, a); or when(!b) else; 2134 2135 // Correct : block only of t > 1 2136 waitfor(f1, a); or when(t > 1) timeout(t); or else; 2137 2138 // Incorrect : timeout clause is dead code 2139 waitfor(f1, a); or timeout(t); or else; 2140 2141 // Incorrect : order must be waitfor [or waitfor... [or timeout] [or else]] 2142 timeout(t); or waitfor(f1, a); or else; 2143 } 2144 \end{cfa} 2145 \caption{Correct and incorrect uses of the or, else, and timeout clause around a waitfor statement} 2146 \label{f:waitfor2} 2019 \centering 2020 \input{RunTimeStructure} 2021 \caption{\CFA Runtime Structure} 2022 \label{f:RunTimeStructure} 2147 2023 \end{figure} 2148 2024 2149 2025 2150 \subsection{Waiting For The Destructor} 2151 2152 An interesting use for the @waitfor@ statement is destructor semantics. 2153 Indeed, the @waitfor@ statement can accept any @mutex@ routine, which includes the destructor (see section \ref{data}). 2154 However, with the semantics discussed until now, waiting for the destructor does not make any sense, since using an object after its destructor is called is undefined behaviour. 2155 The simplest approach is to disallow @waitfor@ on a destructor. 2156 However, a more expressive approach is to flip ordering of execution when waiting for the destructor, meaning that waiting for the destructor allows the destructor to run after the current @mutex@ routine, similarly to how a condition is signalled. 2157 \begin{figure} 2158 \begin{cfa}[caption={Example of an executor which executes action in series until the destructor is called.},label={f:dtor-order}] 2159 monitor Executer {}; 2160 struct Action; 2161 2162 void ^?{} (Executer & mutex this); 2163 void execute(Executer & mutex this, const Action & ); 2164 void run (Executer & mutex this) { 2165 while(true) { 2166 waitfor(execute, this); 2167 or waitfor(^?{} , this) { 2168 break; 2169 } 2170 } 2171 } 2172 \end{cfa} 2173 \end{figure} 2174 For example, listing \ref{f:dtor-order} shows an example of an executor with an infinite loop, which waits for the destructor to break out of this loop. 2175 Switching the semantic meaning introduces an idiomatic way to terminate a task and/or wait for its termination via destruction. 2176 2177 2178 \section{Parallelism} 2179 2180 Historically, computer performance was about processor speeds and instruction counts. 2181 However, with heat dissipation being a direct consequence of speed increase, parallelism has become the new source for increased performance~\cite{Sutter05, Sutter05b}. 2182 In this decade, it is no longer reasonable to create a high-performance application without caring about parallelism. 2183 Indeed, parallelism is an important aspect of performance and more specifically throughput and hardware utilization. 2184 The lowest-level approach of parallelism is to use \textbf{kthread} in combination with semantics like @fork@, @join@, \etc. 2185 However, since these have significant costs and limitations, \textbf{kthread} are now mostly used as an implementation tool rather than a user oriented one. 2186 There are several alternatives to solve these issues that all have strengths and weaknesses. 2187 While there are many variations of the presented paradigms, most of these variations do not actually change the guarantees or the semantics, they simply move costs in order to achieve better performance for certain workloads. 2188 2189 2190 \section{Paradigms} 2191 2192 2193 \subsection{User-Level Threads} 2194 2195 A direct improvement on the \textbf{kthread} approach is to use \textbf{uthread}. 2196 These threads offer most of the same features that the operating system already provides but can be used on a much larger scale. 2197 This approach is the most powerful solution as it allows all the features of multithreading, while removing several of the more expensive costs of kernel threads. 2198 The downside is that almost none of the low-level threading problems are hidden; users still have to think about data races, deadlocks and synchronization issues. 2199 These issues can be somewhat alleviated by a concurrency toolkit with strong guarantees, but the parallelism toolkit offers very little to reduce complexity in itself. 2200 2201 Examples of languages that support \textbf{uthread} are Erlang~\cite{Erlang} and \uC~\cite{uC++book}. 2202 2203 2204 \subsection{Fibers : User-Level Threads Without Preemption} \label{fibers} 2205 2206 A popular variant of \textbf{uthread} is what is often referred to as \textbf{fiber}. 2207 However, \textbf{fiber} do not present meaningful semantic differences with \textbf{uthread}. 2208 The significant difference between \textbf{uthread} and \textbf{fiber} is the lack of \textbf{preemption} in the latter. 2209 Advocates of \textbf{fiber} list their high performance and ease of implementation as major strengths, but the performance difference between \textbf{uthread} and \textbf{fiber} is controversial, and the ease of implementation, while true, is a weak argument in the context of language design. 2210 Therefore this proposal largely ignores fibers. 2211 2212 An example of a language that uses fibers is Go~\cite{Go} 2213 2214 2215 \subsection{Jobs and Thread Pools} 2216 2217 An approach on the opposite end of the spectrum is to base parallelism on \textbf{pool}. 2218 Indeed, \textbf{pool} offer limited flexibility but at the benefit of a simpler user interface. 2219 In \textbf{pool} based systems, users express parallelism as units of work, called jobs, and a dependency graph (either explicit or implicit) that ties them together. 2220 This approach means users need not worry about concurrency but significantly limit the interaction that can occur among jobs. 2221 Indeed, any \textbf{job} that blocks also block the underlying worker, which effectively means the CPU utilization, and therefore throughput, suffers noticeably. 2222 It can be argued that a solution to this problem is to use more workers than available cores. 2223 However, unless the number of jobs and the number of workers are comparable, having a significant number of blocked jobs always results in idles cores. 2224 2225 The gold standard of this implementation is Intel's TBB library~\cite{TBB}. 2226 2227 2228 \subsection{Paradigm Performance} 2229 2230 While the choice between the three paradigms listed above may have significant performance implications, it is difficult to pin down the performance implications of choosing a model at the language level. 2231 Indeed, in many situations one of these paradigms may show better performance but it all strongly depends on the workload. 2232 Having a large amount of mostly independent units of work to execute almost guarantees equivalent performance across paradigms and that the \textbf{pool}-based system has the best efficiency thanks to the lower memory overhead (\ie no thread stack per job). 2233 However, interactions among jobs can easily exacerbate contention. 2234 User-level threads allow fine-grain context switching, which results in better resource utilization, but a context switch is more expensive and the extra control means users need to tweak more variables to get the desired performance. 2235 Finally, if the units of uninterrupted work are large, enough the paradigm choice is largely amortized by the actual work done. 2236 2237 2238 \section{The \protect\CFA\ Kernel : Processors, Clusters and Threads}\label{kernel} 2239 2240 A \textbf{cfacluster} is a group of \textbf{kthread} executed in isolation. \textbf{uthread} are scheduled on the \textbf{kthread} of a given \textbf{cfacluster}, allowing organization between \textbf{uthread} and \textbf{kthread}. 2241 It is important that \textbf{kthread} belonging to a same \textbf{cfacluster} have homogeneous settings, otherwise migrating a \textbf{uthread} from one \textbf{kthread} to the other can cause issues. 2242 A \textbf{cfacluster} also offers a pluggable scheduler that can optimize the workload generated by the \textbf{uthread}. 2243 2244 \textbf{cfacluster} have not been fully implemented in the context of this paper. 2245 Currently \CFA only supports one \textbf{cfacluster}, the initial one. 2246 2247 2248 \subsection{Future Work: Machine Setup}\label{machine} 2249 2250 While this was not done in the context of this paper, another important aspect of clusters is affinity. 2251 While many common desktop and laptop PCs have homogeneous CPUs, other devices often have more heterogeneous setups. 2252 For example, a system using \textbf{numa} configurations may benefit from users being able to tie clusters and/or kernel threads to certain CPU cores. 2253 OS support for CPU affinity is now common~\cite{affinityLinux, affinityWindows, affinityFreebsd, affinityNetbsd, affinityMacosx}, which means it is both possible and desirable for \CFA to offer an abstraction mechanism for portable CPU affinity. 2254 2255 2256 \subsection{Paradigms}\label{cfaparadigms} 2257 2258 Given these building blocks, it is possible to reproduce all three of the popular paradigms. 2259 Indeed, \textbf{uthread} is the default paradigm in \CFA. 2260 However, disabling \textbf{preemption} on a cluster means threads effectively become fibers. 2261 Since several \textbf{cfacluster} with different scheduling policy can coexist in the same application, this allows \textbf{fiber} and \textbf{uthread} to coexist in the runtime of an application. 2262 Finally, it is possible to build executors for thread pools from \textbf{uthread} or \textbf{fiber}, which includes specialized jobs like actors~\cite{Actors}. 2263 2264 2265 \section{Behind the Scenes} 2266 2267 There are several challenges specific to \CFA when implementing concurrency. 2268 These challenges are a direct result of bulk acquire and loose object definitions. 2269 These two constraints are the root cause of most design decisions in the implementation. 2270 Furthermore, to avoid contention from dynamically allocating memory in a concurrent environment, the internal-scheduling design is (almost) entirely free of mallocs. 2271 This approach avoids the chicken and egg problem~\cite{Chicken} of having a memory allocator that relies on the threading system and a threading system that relies on the runtime. 2272 This extra goal means that memory management is a constant concern in the design of the system. 2273 2274 The main memory concern for concurrency is queues. 2275 All blocking operations are made by parking threads onto queues and all queues are designed with intrusive nodes, where each node has pre-allocated link fields for chaining, to avoid the need for memory allocation. 2276 Since several concurrency operations can use an unbound amount of memory (depending on bulk acquire), statically defining information in the intrusive fields of threads is insufficient.The only way to use a variable amount of memory without requiring memory allocation is to pre-allocate large buffers of memory eagerly and store the information in these buffers. 2277 Conveniently, the call stack fits that description and is easy to use, which is why it is used heavily in the implementation of internal scheduling, particularly variable-length arrays. 2278 Since stack allocation is based on scopes, the first step of the implementation is to identify the scopes that are available to store the information, and which of these can have a variable-length array. 2279 The threads and the condition both have a fixed amount of memory, while @mutex@ routines and blocking calls allow for an unbound amount, within the stack size. 2280 2281 Note that since the major contributions of this paper are extending monitor semantics to bulk acquire and loose object definitions, any challenges that are not resulting of these characteristics of \CFA are considered as solved problems and therefore not discussed. 2282 2283 2284 \section{Mutex Routines} 2285 2286 The first step towards the monitor implementation is simple @mutex@ routines. 2287 In the single monitor case, mutual-exclusion is done using the entry/exit procedure in listing \ref{f:entry1}. 2288 The entry/exit procedures do not have to be extended to support multiple monitors. 2289 Indeed it is sufficient to enter/leave monitors one-by-one as long as the order is correct to prevent deadlock~\cite{Havender68}. 2290 In \CFA, ordering of monitor acquisition relies on memory ordering. 2291 This approach is sufficient because all objects are guaranteed to have distinct non-overlapping memory layouts and mutual-exclusion for a monitor is only defined for its lifetime, meaning that destroying a monitor while it is acquired is undefined behaviour. 2292 When a mutex call is made, the concerned monitors are aggregated into a variable-length pointer array and sorted based on pointer values. 2026 \subsection{Cluster} 2027 \label{s:RuntimeStructureCluster} 2028 2029 A \newterm{cluster} is a collection of threads and virtual processors (abstraction a kernel thread) that execute the threads (like a virtual machine). 2030 The purpose of a cluster is to control the amount of parallelism that is possible among threads, plus scheduling and other execution defaults. 2031 The default cluster-scheduler is single-queue multi-server, which provides automatic load-balancing of threads on processors. 2032 However, the scheduler is pluggable, supporting alternative schedulers. 2033 If several clusters exist, both threads and virtual processors, can be explicitly migrated from one cluster to another. 2034 No automatic load balancing among clusters is performed by \CFA. 2035 2036 When a \CFA program begins execution, it creates two clusters: system and user. 2037 The system cluster contains a processor that does not execute user threads. 2038 Instead, the system cluster handles system-related operations, such as catching errors that occur on the user clusters, printing appropriate error information, and shutting down \CFA. 2039 A user cluster is created to contain the user threads. 2040 Having all threads execute on the one cluster often maximizes utilization of processors, which minimizes runtime. 2041 However, because of limitations of the underlying operating system, special hardware, or scheduling requirements (real-time), it is sometimes necessary to have multiple clusters. 2042 2043 2044 \subsection{Virtual Processor} 2045 \label{s:RuntimeStructureProcessor} 2046 2047 A virtual processor is implemented by a kernel thread (\eg UNIX process), which is subsequently scheduled for execution on a hardware processor by the underlying operating system. 2048 Programs may use more virtual processors than hardware processors. 2049 On a multiprocessor, kernel threads are distributed across the hardware processors resulting in virtual processors executing in parallel. 2050 (It is possible to use affinity to lock a virtual processor onto a particular hardware processor~\cite{affinityLinux, affinityWindows, affinityFreebsd, affinityNetbsd, affinityMacosx}, which is used when caching issues occur or for heterogeneous hardware processor.) 2051 The \CFA runtime attempts to block unused processors and unblock processors as the system load increases; 2052 balancing the workload with processors is difficult. 2053 Preemption occurs on virtual processors rather than user threads, via operating-system interrupts. 2054 Thus virtual processors execute user threads, where preemption frequency applies to a virtual processor, so preemption occurs randomly across the executed user threads. 2055 Turning off preemption transforms user threads into fibers. 2056 2057 2058 \subsection{Debug Kernel} 2059 2060 There are two versions of the \CFA runtime kernel: debug and non-debug. 2061 The debugging version has many runtime checks and internal assertions, \eg stack (non-writable) guard page, and checks for stack overflow whenever context switches occur among coroutines and threads, which catches most stack overflows. 2062 After a program is debugged, the non-debugging version can be used to decrease space and increase performance. 2063 2064 2065 \section{Implementation} 2066 2067 Currently, \CFA has fixed-sized stacks, where the stack size can be set at coroutine/thread creation but with no subsequent growth. 2068 Schemes exist for dynamic stack-growth, such as stack copying and chained stacks. 2069 However, stack copying requires pointer adjustment to items on the stack, which is impossible without some form of garage collection. 2070 As well, chained stacks require all modules be recompiled to use this feature, which breaks backward compatibility with existing C libraries. 2071 In the long term, it is likely C libraries will migrate to stack chaining to support concurrency, at only a minimal cost to sequential programs. 2072 Nevertheless, experience teaching \uC~\cite{CS343} shows fixed-sized stacks are rarely an issue in the most concurrent programs. 2073 2074 A primary implementation challenge is avoiding contention from dynamically allocating memory because of bulk acquire, \eg the internal-scheduling design is (almost) free of allocations. 2075 All blocking operations are made by parking threads onto queues, therefore all queues are designed with intrusive nodes, where each node has preallocated link fields for chaining. 2076 Furthermore, several bulk-acquire operations need a variable amount of memory. 2077 This storage is allocated at the base of a thread's stack before blocking, which means programmers must add a small amount of extra space for stacks. 2078 2079 In \CFA, ordering of monitor acquisition relies on memory ordering to prevent deadlock~\cite{Havender68}, because all objects are guaranteed to have distinct non-overlapping memory layouts, and mutual-exclusion for a monitor is only defined for its lifetime. 2080 When a mutex call is made, pointers to the concerned monitors are aggregated into a variable-length array and sorted. 2293 2081 This array persists for the entire duration of the mutual-exclusion and its ordering reused extensively. 2294 \begin{figure} 2295 \begin{multicols}{2} 2296 Entry 2297 \begin{cfa} 2298 if monitor is free 2299 enter 2300 elif already own the monitor 2301 continue 2302 else 2303 block 2304 increment recursions 2305 \end{cfa} 2306 \columnbreak 2307 Exit 2308 \begin{cfa} 2309 decrement recursion 2310 if recursion == 0 2311 if entry queue not empty 2312 wake-up thread 2313 \end{cfa} 2314 \end{multicols} 2315 \begin{cfa}[caption={Initial entry and exit routine for monitors},label={f:entry1}] 2316 \end{cfa} 2317 \end{figure} 2318 2319 2320 \subsection{Details: Interaction with polymorphism} 2321 2322 Depending on the choice of semantics for when monitor locks are acquired, interaction between monitors and \CFA's concept of polymorphism can be more complex to support. 2323 However, it is shown that entry-point locking solves most of the issues. 2324 2325 First of all, interaction between @otype@ polymorphism (see Section~\ref{s:ParametricPolymorphism}) and monitors is impossible since monitors do not support copying. 2326 Therefore, the main question is how to support @dtype@ polymorphism. 2327 It is important to present the difference between the two acquiring options: \textbf{callsite-locking} and entry-point locking, \ie acquiring the monitors before making a mutex routine-call or as the first operation of the mutex routine-call. 2328 For example: 2329 \begin{table} 2330 \begin{center} 2331 \begin{tabular}{|c|c|c|} 2332 Mutex & \textbf{callsite-locking} & \textbf{entry-point-locking} \\ 2333 call & cfa-code & cfa-code \\ 2334 \hline 2335 \begin{cfa}[tabsize=3] 2336 void foo(monitor& mutex a){ 2337 2338 // Do Work 2339 //... 2340 2341 } 2342 2343 void main() { 2344 monitor a; 2345 2346 foo(a); 2347 2348 } 2349 \end{cfa} & \begin{cfa}[tabsize=3] 2350 foo(& a) { 2351 2352 // Do Work 2353 //... 2354 2355 } 2356 2357 main() { 2358 monitor a; 2359 acquire(a); 2360 foo(a); 2361 release(a); 2362 } 2363 \end{cfa} & \begin{cfa}[tabsize=3] 2364 foo(& a) { 2365 acquire(a); 2366 // Do Work 2367 //... 2368 release(a); 2369 } 2370 2371 main() { 2372 monitor a; 2373 2374 foo(a); 2375 2376 } 2377 \end{cfa} 2378 \end{tabular} 2379 \end{center} 2380 \caption{Call-site vs entry-point locking for mutex calls} 2381 \label{tbl:locking-site} 2382 \end{table} 2383 2384 Note the @mutex@ keyword relies on the type system, which means that in cases where a generic monitor-routine is desired, writing the mutex routine is possible with the proper trait, \eg: 2385 \begin{cfa} 2386 // Incorrect: T may not be monitor 2387 forall(dtype T) 2388 void foo(T * mutex t); 2389 2390 // Correct: this routine only works on monitors (any monitor) 2391 forall(dtype T | is_monitor(T)) 2392 void bar(T * mutex t)); 2393 \end{cfa} 2394 2395 Both entry point and \textbf{callsite-locking} are feasible implementations. 2396 The current \CFA implementation uses entry-point locking because it requires less work when using \textbf{raii}, effectively transferring the burden of implementation to object construction/destruction. 2397 It is harder to use \textbf{raii} for call-site locking, as it does not necessarily have an existing scope that matches exactly the scope of the mutual exclusion, \ie the routine body. 2398 For example, the monitor call can appear in the middle of an expression. 2399 Furthermore, entry-point locking requires less code generation since any useful routine is called multiple times but there is only one entry point for many call sites. 2400 2401 2402 \section{Threading} \label{impl:thread} 2403 2404 Figure \ref{fig:system1} shows a high-level picture if the \CFA runtime system in regards to concurrency. 2405 Each component of the picture is explained in detail in the flowing sections. 2406 2407 \begin{figure} 2408 \begin{center} 2409 {\resizebox{\textwidth}{!}{\input{system.pstex_t}}} 2410 \end{center} 2411 \caption{Overview of the entire system} 2412 \label{fig:system1} 2413 \end{figure} 2414 2415 2416 \subsection{Processors} 2417 2418 Parallelism in \CFA is built around using processors to specify how much parallelism is desired. \CFA processors are object wrappers around kernel threads, specifically @pthread@s in the current implementation of \CFA. 2419 Indeed, any parallelism must go through operating-system libraries. 2420 However, \textbf{uthread} are still the main source of concurrency, processors are simply the underlying source of parallelism. 2421 Indeed, processor \textbf{kthread} simply fetch a \textbf{uthread} from the scheduler and run it; they are effectively executers for user-threads. 2422 The main benefit of this approach is that it offers a well-defined boundary between kernel code and user code, for example, kernel thread quiescing, scheduling and interrupt handling. 2423 Processors internally use coroutines to take advantage of the existing context-switching semantics. 2424 2425 2426 \subsection{Stack Management} 2427 2428 One of the challenges of this system is to reduce the footprint as much as possible. 2429 Specifically, all @pthread@s created also have a stack created with them, which should be used as much as possible. 2430 Normally, coroutines also create their own stack to run on, however, in the case of the coroutines used for processors, these coroutines run directly on the \textbf{kthread} stack, effectively stealing the processor stack. 2431 The exception to this rule is the Main Processor, \ie the initial \textbf{kthread} that is given to any program. 2432 In order to respect C user expectations, the stack of the initial kernel thread, the main stack of the program, is used by the main user thread rather than the main processor, which can grow very large. 2433 2434 2435 \subsection{Context Switching} 2436 2437 As mentioned in section \ref{coroutine}, coroutines are a stepping stone for implementing threading, because they share the same mechanism for context-switching between different stacks. 2438 To improve performance and simplicity, context-switching is implemented using the following assumption: all context-switches happen inside a specific routine call. 2439 This assumption means that the context-switch only has to copy the callee-saved registers onto the stack and then switch the stack registers with the ones of the target coroutine/thread. 2440 Note that the instruction pointer can be left untouched since the context-switch is always inside the same routine 2441 Threads, however, do not context-switch between each other directly. 2442 They context-switch to the scheduler. 2443 This method is called a 2-step context-switch and has the advantage of having a clear distinction between user code and the kernel where scheduling and other system operations happen. 2444 Obviously, this doubles the context-switch cost because threads must context-switch to an intermediate stack. 2445 The alternative 1-step context-switch uses the stack of the ``from'' thread to schedule and then context-switches directly to the ``to'' thread. 2446 However, the performance of the 2-step context-switch is still superior to a @pthread_yield@ (see section \ref{results}). 2447 Additionally, for users in need for optimal performance, it is important to note that having a 2-step context-switch as the default does not prevent \CFA from offering a 1-step context-switch (akin to the Microsoft @SwitchToFiber@~\cite{switchToWindows} routine). 2448 This option is not currently present in \CFA, but the changes required to add it are strictly additive. 2449 2450 2451 \subsection{Preemption} \label{preemption} 2452 2453 Finally, an important aspect for any complete threading system is preemption. 2454 As mentioned in section \ref{basics}, preemption introduces an extra degree of uncertainty, which enables users to have multiple threads interleave transparently, rather than having to cooperate among threads for proper scheduling and CPU distribution. 2455 Indeed, preemption is desirable because it adds a degree of isolation among threads. 2456 In a fully cooperative system, any thread that runs a long loop can starve other threads, while in a preemptive system, starvation can still occur but it does not rely on every thread having to yield or block on a regular basis, which reduces significantly a programmer burden. 2457 Obviously, preemption is not optimal for every workload. 2458 However any preemptive system can become a cooperative system by making the time slices extremely large. 2459 Therefore, \CFA uses a preemptive threading system. 2460 2461 Preemption in \CFA\footnote{Note that the implementation of preemption is strongly tied with the underlying threading system. 2462 For this reason, only the Linux implementation is cover, \CFA does not run on Windows at the time of writting} is based on kernel timers, which are used to run a discrete-event simulation. 2463 Every processor keeps track of the current time and registers an expiration time with the preemption system. 2464 When the preemption system receives a change in preemption, it inserts the time in a sorted order and sets a kernel timer for the closest one, effectively stepping through preemption events on each signal sent by the timer. 2465 These timers use the Linux signal {\tt SIGALRM}, which is delivered to the process rather than the kernel-thread. 2466 This results in an implementation problem, because when delivering signals to a process, the kernel can deliver the signal to any kernel thread for which the signal is not blocked, \ie: 2082 2083 To improve performance and simplicity, context switching occur inside a routine call, so only callee-saved registers are copied onto the stack and then the stack register is switched; 2084 the corresponding registers are then restored for the other context. 2085 Note, the instruction pointer is untouched since the context switch is always inside the same routine. 2086 Unlike coroutines, threads do not context switch among each other; 2087 they context switch to the cluster scheduler. 2088 This method is a 2-step context-switch and provides a clear distinction between user and kernel code, where scheduling and other system operations happen. 2089 The alternative 1-step context-switch uses the \emph{from} thread's stack to schedule and then context-switches directly to the \emph{to} thread's stack. 2090 Experimental results (not shown) show the performance difference between these two approaches is virtually equivalent, because the 1-step performance is dominated by locking instructions to prevent a race condition. 2091 2092 All kernel threads (@pthreads@) created a stack. 2093 Each \CFA virtual processor is implemented as a coroutine and these coroutines run directly on the kernel-thread stack, effectively stealing this stack. 2094 The exception to this rule is the program main, \ie the initial kernel thread that is given to any program. 2095 In order to respect C expectations, the stack of the initial kernel thread is used by program main rather than the main processor, allowing it to grow dynamically as in a normal C program. 2096 2097 Finally, an important aspect for a complete threading system is preemption, which introduces extra non-determinism via transparent interleaving, rather than cooperation among threads for proper scheduling and processor fairness from long-running threads. 2098 Because preemption frequency is usually long, 1 millisecond, performance cost is negligible. 2099 2100 Preemption is normally handled by setting a count-down timer on each virtual processor. 2101 When the timer expires, an interrupt is delivered, and the interrupt handler resets the count-down timer, and if the virtual processor is executing in user code, the signal handler performs a user-level context-switch, or if executing in the language runtime-kernel, the preemption is ignored or rolled forward to the point where the runtime kernel context switches back to user code. 2102 Multiple signal handlers may be pending. 2103 When control eventually switches back to the signal handler, it returns normally, and execution continues in the interrupted user thread, even though the return from the signal handler may be on a different kernel thread than the one where the signal was delivered. 2104 The only issue with this approach is that signal masks from one kernel thread may be restored on another as part of returning from the signal handler; 2105 therefore, all virtual processors in a cluster need to have the same signal mask. 2106 2107 However, on UNIX systems: 2467 2108 \begin{quote} 2468 2109 A process-directed signal may be delivered to any one of the threads that does not currently have the signal blocked. … … 2470 2111 SIGNAL(7) - Linux Programmer's Manual 2471 2112 \end{quote} 2472 For the sake of simplicity, and in order to prevent the case of having two threads receiving alarms simultaneously, \CFA programs block the {\tt SIGALRM} signal on every kernel thread except one. 2473 2474 Now because of how involuntary context-switches are handled, the kernel thread handling {\tt SIGALRM} cannot also be a processor thread. 2475 Hence, involuntary context-switching is done by sending signal {\tt SIGUSR1} to the corresponding proces\-sor and having the thread yield from inside the signal handler. 2476 This approach effectively context-switches away from the signal handler back to the kernel and the signal handler frame is eventually unwound when the thread is scheduled again. 2477 As a result, a signal handler can start on one kernel thread and terminate on a second kernel thread (but the same user thread). 2478 It is important to note that signal handlers save and restore signal masks because user-thread migration can cause a signal mask to migrate from one kernel thread to another. 2479 This behaviour is only a problem if all kernel threads, among which a user thread can migrate, differ in terms of signal masks\footnote{Sadly, official POSIX documentation is silent on what distinguishes ``async-signal-safe'' routines from other routines}. 2480 However, since the kernel thread handling preemption requires a different signal mask, executing user threads on the kernel-alarm thread can cause deadlocks. 2481 For this reason, the alarm thread is in a tight loop around a system call to @sigwaitinfo@, requiring very little CPU time for preemption. 2482 One final detail about the alarm thread is how to wake it when additional communication is required (\eg on thread termination). 2483 This unblocking is also done using {\tt SIGALRM}, but sent through the @pthread_sigqueue@. 2484 Indeed, @sigwait@ can differentiate signals sent from @pthread_sigqueue@ from signals sent from alarms or the kernel. 2485 2486 2487 \subsection{Scheduler} 2488 Finally, an aspect that was not mentioned yet is the scheduling algorithm. 2489 Currently, the \CFA scheduler uses a single ready queue for all processors, which is the simplest approach to scheduling. 2490 Further discussion on scheduling is present in section \ref{futur:sched}. 2491 2492 2493 \section{Internal Scheduling} \label{impl:intsched} 2494 2495 The following figure is the traditional illustration of a monitor (repeated from page~\pageref{fig:ClassicalMonitor} for convenience): 2496 2497 \begin{figure} 2498 \begin{center} 2499 {\resizebox{0.4\textwidth}{!}{\input{monitor.pstex_t}}} 2500 \end{center} 2501 \caption{Traditional illustration of a monitor} 2502 \end{figure} 2503 2504 This picture has several components, the two most important being the entry queue and the AS-stack. 2505 The entry queue is an (almost) FIFO list where threads waiting to enter are parked, while the acceptor/signaller (AS) stack is a FILO list used for threads that have been signalled or otherwise marked as running next. 2506 2507 For \CFA, this picture does not have support for blocking multiple monitors on a single condition. 2508 To support bulk acquire two changes to this picture are required. 2509 First, it is no longer helpful to attach the condition to \emph{a single} monitor. 2510 Secondly, the thread waiting on the condition has to be separated across multiple monitors, seen in figure \ref{fig:monitor_cfa}. 2511 2512 \begin{figure} 2513 \begin{center} 2514 {\resizebox{0.8\textwidth}{!}{\input{int_monitor}}} 2515 \end{center} 2516 \caption{Illustration of \CFA Monitor} 2517 \label{fig:monitor_cfa} 2518 \end{figure} 2519 2520 This picture and the proper entry and leave algorithms (see listing \ref{f:entry2}) is the fundamental implementation of internal scheduling. 2521 Note that when a thread is moved from the condition to the AS-stack, it is conceptually split into N pieces, where N is the number of monitors specified in the parameter list. 2522 The thread is woken up when all the pieces have popped from the AS-stacks and made active. 2523 In this picture, the threads are split into halves but this is only because there are two monitors. 2524 For a specific signalling operation every monitor needs a piece of thread on its AS-stack. 2525 2526 \begin{figure} 2527 \begin{multicols}{2} 2528 Entry 2529 \begin{cfa} 2530 if monitor is free 2531 enter 2532 elif already own the monitor 2533 continue 2534 else 2535 block 2536 increment recursion 2537 2538 \end{cfa} 2539 \columnbreak 2540 Exit 2541 \begin{cfa} 2542 decrement recursion 2543 if recursion == 0 2544 if signal_stack not empty 2545 set_owner to thread 2546 if all monitors ready 2547 wake-up thread 2548 2549 if entry queue not empty 2550 wake-up thread 2551 \end{cfa} 2552 \end{multicols} 2553 \begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling},label={f:entry2}] 2554 \end{cfa} 2555 \end{figure} 2556 2557 The solution discussed in \ref{s:InternalScheduling} can be seen in the exit routine of listing \ref{f:entry2}. 2558 Basically, the solution boils down to having a separate data structure for the condition queue and the AS-stack, and unconditionally transferring ownership of the monitors but only unblocking the thread when the last monitor has transferred ownership. 2559 This solution is deadlock safe as well as preventing any potential barging. 2560 The data structures used for the AS-stack are reused extensively for external scheduling, but in the case of internal scheduling, the data is allocated using variable-length arrays on the call stack of the @wait@ and @signal_block@ routines. 2561 2562 \begin{figure} 2563 \begin{center} 2564 {\resizebox{0.8\textwidth}{!}{\input{monitor_structs.pstex_t}}} 2565 \end{center} 2566 \caption{Data structures involved in internal/external scheduling} 2567 \label{fig:structs} 2568 \end{figure} 2569 2570 Figure \ref{fig:structs} shows a high-level representation of these data structures. 2571 The main idea behind them is that, a thread cannot contain an arbitrary number of intrusive ``next'' pointers for linking onto monitors. 2572 The @condition node@ is the data structure that is queued onto a condition variable and, when signalled, the condition queue is popped and each @condition criterion@ is moved to the AS-stack. 2573 Once all the criteria have been popped from their respective AS-stacks, the thread is woken up, which is what is shown in listing \ref{f:entry2}. 2574 2575 % ====================================================================== 2576 % ====================================================================== 2577 \section{External Scheduling} 2578 % ====================================================================== 2579 % ====================================================================== 2580 Similarly to internal scheduling, external scheduling for multiple monitors relies on the idea that waiting-thread queues are no longer specific to a single monitor, as mentioned in section \ref{extsched}. 2581 For internal scheduling, these queues are part of condition variables, which are still unique for a given scheduling operation (\ie no signal statement uses multiple conditions). 2582 However, in the case of external scheduling, there is no equivalent object which is associated with @waitfor@ statements. 2583 This absence means the queues holding the waiting threads must be stored inside at least one of the monitors that is acquired. 2584 These monitors being the only objects that have sufficient lifetime and are available on both sides of the @waitfor@ statement. 2585 This requires an algorithm to choose which monitor holds the relevant queue. 2586 It is also important that said algorithm be independent of the order in which users list parameters. 2587 The proposed algorithm is to fall back on monitor lock ordering (sorting by address) and specify that the monitor that is acquired first is the one with the relevant waiting queue. 2588 This assumes that the lock acquiring order is static for the lifetime of all concerned objects but that is a reasonable constraint. 2589 2590 This algorithm choice has two consequences: 2591 \begin{itemize} 2592 \item The queue of the monitor with the lowest address is no longer a true FIFO queue because threads can be moved to the front of the queue. 2593 These queues need to contain a set of monitors for each of the waiting threads. 2594 Therefore, another thread whose set contains the same lowest address monitor but different lower priority monitors may arrive first but enter the critical section after a thread with the correct pairing. 2595 \item The queue of the lowest priority monitor is both required and potentially unused. 2596 Indeed, since it is not known at compile time which monitor is the monitor which has the lowest address, every monitor needs to have the correct queues even though it is possible that some queues go unused for the entire duration of the program, for example if a monitor is only used in a specific pair. 2597 \end{itemize} 2598 Therefore, the following modifications need to be made to support external scheduling: 2599 \begin{itemize} 2600 \item The threads waiting on the entry queue need to keep track of which routine they are trying to enter, and using which set of monitors. 2601 The @mutex@ routine already has all the required information on its stack, so the thread only needs to keep a pointer to that information. 2602 \item The monitors need to keep a mask of acceptable routines. 2603 This mask contains for each acceptable routine, a routine pointer and an array of monitors to go with it. 2604 It also needs storage to keep track of which routine was accepted. 2605 Since this information is not specific to any monitor, the monitors actually contain a pointer to an integer on the stack of the waiting thread. 2606 Note that if a thread has acquired two monitors but executes a @waitfor@ with only one monitor as a parameter, setting the mask of acceptable routines to both monitors will not cause any problems since the extra monitor will not change ownership regardless. 2607 This becomes relevant when @when@ clauses affect the number of monitors passed to a @waitfor@ statement. 2608 \item The entry/exit routines need to be updated as shown in listing \ref{f:entry3}. 2609 \end{itemize} 2610 2611 \subsection{External Scheduling - Destructors} 2612 Finally, to support the ordering inversion of destructors, the code generation needs to be modified to use a special entry routine. 2613 This routine is needed because of the storage requirements of the call order inversion. 2614 Indeed, when waiting for the destructors, storage is needed for the waiting context and the lifetime of said storage needs to outlive the waiting operation it is needed for. 2615 For regular @waitfor@ statements, the call stack of the routine itself matches this requirement but it is no longer the case when waiting for the destructor since it is pushed on to the AS-stack for later. 2616 The @waitfor@ semantics can then be adjusted correspondingly, as seen in listing \ref{f:entry-dtor} 2617 2618 \begin{figure} 2619 \begin{multicols}{2} 2620 Entry 2621 \begin{cfa} 2622 if monitor is free 2623 enter 2624 elif already own the monitor 2625 continue 2626 elif matches waitfor mask 2627 push criteria to AS-stack 2628 continue 2629 else 2630 block 2631 increment recursion 2632 \end{cfa} 2633 \columnbreak 2634 Exit 2635 \begin{cfa} 2636 decrement recursion 2637 if recursion == 0 2638 if signal_stack not empty 2639 set_owner to thread 2640 if all monitors ready 2641 wake-up thread 2642 endif 2643 endif 2644 2645 if entry queue not empty 2646 wake-up thread 2647 endif 2648 \end{cfa} 2649 \end{multicols} 2650 \begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling and external scheduling},label={f:entry3}] 2651 \end{cfa} 2652 \end{figure} 2653 2654 \begin{figure} 2655 \begin{multicols}{2} 2656 Destructor Entry 2657 \begin{cfa} 2658 if monitor is free 2659 enter 2660 elif already own the monitor 2661 increment recursion 2662 return 2663 create wait context 2664 if matches waitfor mask 2665 reset mask 2666 push self to AS-stack 2667 baton pass 2668 else 2669 wait 2670 increment recursion 2671 \end{cfa} 2672 \columnbreak 2673 Waitfor 2674 \begin{cfa} 2675 if matching thread is already there 2676 if found destructor 2677 push destructor to AS-stack 2678 unlock all monitors 2679 else 2680 push self to AS-stack 2681 baton pass 2682 endif 2683 return 2684 endif 2685 if non-blocking 2686 Unlock all monitors 2687 Return 2688 endif 2689 2690 push self to AS-stack 2691 set waitfor mask 2692 block 2693 return 2694 \end{cfa} 2695 \end{multicols} 2696 \begin{cfa}[caption={Pseudo code for the \protect\lstinline|waitfor| routine and the \protect\lstinline|mutex| entry routine for destructors},label={f:entry-dtor}] 2697 \end{cfa} 2698 \end{figure} 2699 2700 2701 % ====================================================================== 2702 % ====================================================================== 2703 \section{Putting It All Together} 2704 % ====================================================================== 2705 % ====================================================================== 2706 2707 2708 \section{Threads As Monitors} 2709 As it was subtly alluded in section \ref{threads}, @thread@s in \CFA are in fact monitors, which means that all monitor features are available when using threads. 2710 For example, here is a very simple two thread pipeline that could be used for a simulator of a game engine: 2711 \begin{figure} 2712 \begin{cfa}[caption={Toy simulator using \protect\lstinline|thread|s and \protect\lstinline|monitor|s.},label={f:engine-v1}] 2713 // Visualization declaration 2714 thread Renderer {} renderer; 2715 Frame * simulate( Simulator & this ); 2716 2717 // Simulation declaration 2718 thread Simulator{} simulator; 2719 void render( Renderer & this ); 2720 2721 // Blocking call used as communication 2722 void draw( Renderer & mutex this, Frame * frame ); 2723 2724 // Simulation loop 2725 void main( Simulator & this ) { 2726 while( true ) { 2727 Frame * frame = simulate( this ); 2728 draw( renderer, frame ); 2729 } 2730 } 2731 2732 // Rendering loop 2733 void main( Renderer & this ) { 2734 while( true ) { 2735 waitfor( draw, this ); 2736 render( this ); 2737 } 2738 } 2739 \end{cfa} 2740 \end{figure} 2741 One of the obvious complaints of the previous code snippet (other than its toy-like simplicity) is that it does not handle exit conditions and just goes on forever. 2742 Luckily, the monitor semantics can also be used to clearly enforce a shutdown order in a concise manner: 2743 \begin{figure} 2744 \begin{cfa}[caption={Same toy simulator with proper termination condition.},label={f:engine-v2}] 2745 // Visualization declaration 2746 thread Renderer {} renderer; 2747 Frame * simulate( Simulator & this ); 2748 2749 // Simulation declaration 2750 thread Simulator{} simulator; 2751 void render( Renderer & this ); 2752 2753 // Blocking call used as communication 2754 void draw( Renderer & mutex this, Frame * frame ); 2755 2756 // Simulation loop 2757 void main( Simulator & this ) { 2758 while( true ) { 2759 Frame * frame = simulate( this ); 2760 draw( renderer, frame ); 2761 2762 // Exit main loop after the last frame 2763 if( frame->is_last ) break; 2764 } 2765 } 2766 2767 // Rendering loop 2768 void main( Renderer & this ) { 2769 while( true ) { 2770 waitfor( draw, this ); 2771 or waitfor( ^?{}, this ) { 2772 // Add an exit condition 2773 break; 2774 } 2775 2776 render( this ); 2777 } 2778 } 2779 2780 // Call destructor for simulator once simulator finishes 2781 // Call destructor for renderer to signify shutdown 2782 \end{cfa} 2783 \end{figure} 2784 2785 \section{Fibers \& Threads} 2786 As mentioned in section \ref{preemption}, \CFA uses preemptive threads by default but can use fibers on demand. 2787 Currently, using fibers is done by adding the following line of code to the program~: 2788 \begin{cfa} 2789 unsigned int default_preemption() { 2790 return 0; 2791 } 2792 \end{cfa} 2793 This routine is called by the kernel to fetch the default preemption rate, where 0 signifies an infinite time-slice, \ie no preemption. 2794 However, once clusters are fully implemented, it will be possible to create fibers and \textbf{uthread} in the same system, as in listing \ref{f:fiber-uthread} 2795 \begin{figure} 2796 \lstset{language=CFA,deletedelim=**[is][]{`}{`}} 2797 \begin{cfa}[caption={Using fibers and \textbf{uthread} side-by-side in \CFA},label={f:fiber-uthread}] 2798 // Cluster forward declaration 2799 struct cluster; 2800 2801 // Processor forward declaration 2802 struct processor; 2803 2804 // Construct clusters with a preemption rate 2805 void ?{}(cluster& this, unsigned int rate); 2806 // Construct processor and add it to cluster 2807 void ?{}(processor& this, cluster& cluster); 2808 // Construct thread and schedule it on cluster 2809 void ?{}(thread& this, cluster& cluster); 2810 2811 // Declare two clusters 2812 cluster thread_cluster = { 10`ms }; // Preempt every 10 ms 2813 cluster fibers_cluster = { 0 }; // Never preempt 2814 2815 // Construct 4 processors 2816 processor processors[4] = { 2817 //2 for the thread cluster 2818 thread_cluster; 2819 thread_cluster; 2820 //2 for the fibers cluster 2821 fibers_cluster; 2822 fibers_cluster; 2823 }; 2824 2825 // Declares thread 2826 thread UThread {}; 2827 void ?{}(UThread& this) { 2828 // Construct underlying thread to automatically 2829 // be scheduled on the thread cluster 2830 (this){ thread_cluster } 2831 } 2832 2833 void main(UThread & this); 2834 2835 // Declares fibers 2836 thread Fiber {}; 2837 void ?{}(Fiber& this) { 2838 // Construct underlying thread to automatically 2839 // be scheduled on the fiber cluster 2840 (this.__thread){ fibers_cluster } 2841 } 2842 2843 void main(Fiber & this); 2844 \end{cfa} 2845 \end{figure} 2846 2847 2848 % ====================================================================== 2849 % ====================================================================== 2850 \section{Performance Results} \label{results} 2851 % ====================================================================== 2852 % ====================================================================== 2853 \section{Machine Setup} 2854 Table \ref{tab:machine} shows the characteristics of the machine used to run the benchmarks. 2855 All tests were made on this machine. 2856 \begin{table} 2857 \begin{center} 2858 \begin{tabular}{| l | r | l | r |} 2113 Hence, the timer-expiry signal, which is generated \emph{externally} by the UNIX kernel to the UNIX process, is delivered to any of its UNIX subprocesses (kernel threads). 2114 To ensure each virtual processor receives its own preemption signals, a discrete-event simulation is run on one virtual processor, and only it sets timer events. 2115 Virtual processors register an expiration time with the discrete-event simulator, which is inserted in sorted order. 2116 The simulation sets the count-down timer to the value at the head of the event list, and when the timer expires, all events less than or equal to the current time are processed. 2117 Processing a preemption event sends an \emph{internal} @SIGUSR1@ signal to the registered virtual processor, which is always delivered to that processor. 2118 2119 2120 \section{Performance} 2121 \label{results} 2122 2123 To verify the implementation of the \CFA runtime, a series of microbenchmarks are performed comparing \CFA with other widely used programming languages with concurrency. 2124 Table~\ref{t:machine} shows the specifications of the computer used to run the benchmarks, and the versions of the software used in the comparison. 2125 2126 \begin{table}[h] 2127 \centering 2128 \caption{Experiment environment} 2129 \label{t:machine} 2130 2131 \begin{tabular}{|l|r||l|r|} 2859 2132 \hline 2860 Architecture & x86\_64 & NUMA node(s) & 8 \\2133 Architecture & x86\_64 & NUMA node(s) & 8 \\ 2861 2134 \hline 2862 CPU op-mode(s) & 32-bit, 64-bit & Model name & AMD Opteron\texttrademark 2135 CPU op-mode(s) & 32-bit, 64-bit & Model name & AMD Opteron\texttrademark\ Processor 6380 \\ 2863 2136 \hline 2864 Byte Order & Little Endian & CPU Freq & 2.5 \si{\giga\hertz}\\2137 Byte Order & Little Endian & CPU Freq & 2.5 GHz \\ 2865 2138 \hline 2866 CPU(s) & 64 & L1d cache & \SI{16}{\kibi\byte}\\2139 CPU(s) & 64 & L1d cache & 16 KiB \\ 2867 2140 \hline 2868 Thread(s) per core & 2 & L1i cache & \SI{64}{\kibi\byte}\\2141 Thread(s) per core & 2 & L1i cache & 64 KiB \\ 2869 2142 \hline 2870 Core(s) per socket & 8 & L2 cache & \SI{2048}{\kibi\byte}\\2143 Core(s) per socket & 8 & L2 cache & 2048 KiB \\ 2871 2144 \hline 2872 Socket(s) & 4 & L3 cache & \SI{6144}{\kibi\byte}\\2145 Socket(s) & 4 & L3 cache & 6144 KiB \\ 2873 2146 \hline 2874 2147 \hline 2875 Operating system 2148 Operating system & Ubuntu 16.04.3 LTS & Kernel & Linux 4.4-97-generic \\ 2876 2149 \hline 2877 Compiler & GCC 6.3 & Translator & CFA 1\\2150 gcc & 6.3 & \CFA & 1.0.0 \\ 2878 2151 \hline 2879 Java version & OpenJDK-9 & Go version& 1.9.2 \\2152 Java & OpenJDK-9 & Go & 1.9.2 \\ 2880 2153 \hline 2881 2154 \end{tabular} 2882 \end{center}2883 \caption{Machine setup used for the tests}2884 \label{tab:machine}2885 2155 \end{table} 2886 2156 2887 \section{Micro Benchmarks} 2888 All benchmarks are run using the same harness to produce the results, seen as the @BENCH()@ macro in the following examples. 2889 This macro uses the following logic to benchmark the code: 2890 \begin{cfa} 2891 #define BENCH(run, result) \ 2892 before = gettime(); \ 2893 run; \ 2894 after = gettime(); \ 2895 result = (after - before) / N; 2896 \end{cfa} 2897 The method used to get time is @clock_gettime(CLOCK_THREAD_CPUTIME_ID);@. 2898 Each benchmark is using many iterations of a simple call to measure the cost of the call. 2899 The specific number of iterations depends on the specific benchmark. 2900 2901 \subsection{Context-Switching} 2902 The first interesting benchmark is to measure how long context-switches take. 2903 The simplest approach to do this is to yield on a thread, which executes a 2-step context switch. 2904 Yielding causes the thread to context-switch to the scheduler and back, more precisely: from the \textbf{uthread} to the \textbf{kthread} then from the \textbf{kthread} back to the same \textbf{uthread} (or a different one in the general case). 2905 In order to make the comparison fair, coroutines also execute a 2-step context-switch by resuming another coroutine which does nothing but suspending in a tight loop, which is a resume/suspend cycle instead of a yield. 2906 Figure~\ref{f:ctx-switch} shows the code for coroutines and threads with the results in table \ref{tab:ctx-switch}. 2907 All omitted tests are functionally identical to one of these tests. 2908 The difference between coroutines and threads can be attributed to the cost of scheduling. 2157 All benchmarks are run using the following harness: 2158 \begin{cfa} 2159 unsigned int N = 10_000_000; 2160 #define BENCH( run, result ) Time before = getTimeNsec(); run; result = (getTimeNsec() - before) / N; 2161 \end{cfa} 2162 The method used to get time is @clock_gettime( CLOCK_REALTIME )@. 2163 Each benchmark is performed @N@ times, where @N@ varies depending on the benchmark, the total time is divided by @N@ to obtain the average time for a benchmark. 2164 2165 2166 \paragraph{Context-Switching} 2167 2168 In procedural programming, the cost of a routine call is important as modularization (refactoring) increases. 2169 (In many cases, a compiler inlines routine calls to eliminate this cost.) 2170 Similarly, when modularization extends to coroutines/tasks, the time for a context switch becomes a relevant factor. 2171 The coroutine context-switch is 2-step using resume/suspend, \ie from resumer to suspender and from suspender to resumer. 2172 The thread context switch is 2-step using yield, \ie enter and return from the runtime kernel. 2173 Figure~\ref{f:ctx-switch} shows the code for coroutines/threads with all results in Table~\ref{tab:ctx-switch}. 2174 All omitted tests for other languages are functionally identical to this test (as for all other tests). 2175 The difference in performance between coroutine and thread context-switch is the cost of scheduling for threads, whereas coroutines are self-scheduling. 2176 2909 2177 \begin{figure} 2910 \ begin{multicols}{2}2911 \CFA Coroutines 2912 \ begin{cfa}2913 coroutine GreatSuspender {}; 2914 void main(GreatSuspender& this) { 2915 while(true) { suspend(); } 2916 }2178 \lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} 2179 2180 \newbox\myboxA 2181 \begin{lrbox}{\myboxA} 2182 \begin{cfa}[aboveskip=0pt,belowskip=0pt] 2183 coroutine C {} c; 2184 void main( C & ) { for ( ;; ) { @suspend();@ } } 2917 2185 int main() { 2918 GreatSuspender s; 2919 resume(s); 2186 Duration result; 2920 2187 BENCH( 2921 for(size_t i=0; i<n; i++) { 2922 resume(s); 2923 }, 2188 for ( size_t i = 0; i < N; i += 1 ) { @resume( c );@ }, 2924 2189 result 2925 2190 ) 2926 printf("%llu\n", result);2927 } 2928 \end{cfa} 2929 \ columnbreak2930 \CFA Threads 2931 \ begin{cfa}2932 2933 2191 sout | result`ns | endl; 2192 } 2193 \end{cfa} 2194 \end{lrbox} 2195 2196 \newbox\myboxB 2197 \begin{lrbox}{\myboxB} 2198 \begin{cfa}[aboveskip=0pt,belowskip=0pt] 2934 2199 2935 2200 2936 2201 int main() { 2937 2938 2202 Duration result; 2939 2203 BENCH( 2940 for(size_t i=0; i<n; i++) { 2941 yield(); 2942 }, 2204 for ( size_t i = 0; i < N; i += 1 ) { @yield();@ }, 2943 2205 result 2944 2206 ) 2945 printf("%llu\n", result); 2946 } 2947 \end{cfa} 2948 \end{multicols} 2949 \begin{cfa}[caption={\CFA benchmark code used to measure context-switches for coroutines and threads.},label={f:ctx-switch}] 2950 \end{cfa} 2207 sout | result`ns | endl; 2208 } 2209 \end{cfa} 2210 \end{lrbox} 2211 2212 \subfloat[Coroutine]{\label{f:GlobalVariables}\usebox\myboxA} 2213 \quad 2214 \subfloat[Thread]{\label{f:ExternalState}\usebox\myboxB} 2215 \caption{\CFA Context-switch benchmark} 2216 \label{f:ctx-switch} 2951 2217 \end{figure} 2952 2218 2953 2219 \begin{table} 2954 \begin{center} 2955 \begin{tabular}{| l | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] |} 2220 \centering 2221 \caption{Context Switch comparison (nanoseconds)} 2222 \label{tab:ctx-switch} 2223 2224 \begin{tabular}{|r|*{3}{D{.}{.}{3.2}|}} 2956 2225 \cline{2-4} 2957 \multicolumn{1}{c |}{} & \multicolumn{1}{c |}{ Median } &\multicolumn{1}{c |}{ Average } & \multicolumn{1}{c |}{ Standard Deviation} \\2226 \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} &\multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\ 2958 2227 \hline 2959 Kernel Thread & 241.5 & 243.86 & 5.08 \\2228 Kernel Thread & 241.5 & 243.86 & 5.08 \\ 2960 2229 \CFA Coroutine & 38 & 38 & 0 \\ 2961 2230 \CFA Thread & 103 & 102.96 & 2.96 \\ 2962 \uC Coroutine & 46 & 45.86 & 0.35 \\2963 \uC Thread & 98 & 99.11 & 1.42 \\2231 \uC Coroutine & 46 & 45.86 & 0.35 \\ 2232 \uC Thread & 98 & 99.11 & 1.42 \\ 2964 2233 Goroutine & 150 & 149.96 & 3.16 \\ 2965 2234 Java Thread & 289 & 290.68 & 8.72 \\ 2966 2235 \hline 2967 2236 \end{tabular} 2968 \end{center}2969 \caption{Context Switch comparison.2970 All numbers are in nanoseconds(\si{\nano\second})}2971 \label{tab:ctx-switch}2972 2237 \end{table} 2973 2238 2974 \subsection{Mutual-Exclusion} 2975 The next interesting benchmark is to measure the overhead to enter/leave a critical-section. 2976 For monitors, the simplest approach is to measure how long it takes to enter and leave a monitor routine. 2977 Figure~\ref{f:mutex} shows the code for \CFA. 2239 2240 \paragraph{Mutual-Exclusion} 2241 2242 Mutual exclusion is measured by entering/leaving a critical section. 2243 For monitors, entering and leaving a monitor routine is measured. 2244 Figure~\ref{f:mutex} shows the code for \CFA with all results in Table~\ref{tab:mutex}. 2978 2245 To put the results in context, the cost of entering a non-inline routine and the cost of acquiring and releasing a @pthread_mutex@ lock is also measured. 2979 The results can be shown in table \ref{tab:mutex}. 2980 2981 \begin{figure} 2982 \begin{cfa}[caption={\CFA benchmark code used to measure mutex routines.},label={f:mutex}] 2983 monitor M {}; 2984 void __attribute__((noinline)) call( M & mutex m /*, m2, m3, m4*/ ) {} 2985 2246 Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects. 2247 2248 \begin{samepage} 2249 \begin{figure}[!p] 2250 \lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} 2251 \begin{cfa} 2252 monitor M {} m1/*, m2, m3, m4*/; 2253 void __attribute__((noinline)) do_call( M & mutex m/*, m2, m3, m4*/ ) {} 2986 2254 int main() { 2987 M m/*, m2, m3, m4*/; 2988 BENCH( 2989 for(size_t i=0; i<n; i++) { 2990 call(m/*, m2, m3, m4*/); 2991 }, 2992 result 2993 ) 2994 printf("%llu\n", result); 2995 } 2996 \end{cfa} 2255 Duration result; 2256 BENCH( for( size_t i = 0; i < N; i += 1 ) { @do_call( m1/*, m2, m3, m4*/ );@ }, result ) 2257 sout | result`ns | endl; 2258 } 2259 \end{cfa} 2260 \caption{\CFA benchmark code used to measure mutex routines.} 2261 \label{f:mutex} 2997 2262 \end{figure} 2998 2263 2999 \begin{table} 3000 \begin{center} 3001 \begin{tabular}{| l | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] |} 2264 \begin{table}[!p] 2265 \centering 2266 \caption{Mutex routine comparison (nanoseconds)} 2267 \label{tab:mutex} 2268 2269 \begin{tabular}{|r|*{3}{D{.}{.}{3.2}|}} 3002 2270 \cline{2-4} 3003 \multicolumn{1}{c |}{} & \multicolumn{1}{c |}{ Median } &\multicolumn{1}{c |}{ Average } & \multicolumn{1}{c |}{ Standard Deviation} \\2271 \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} &\multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\ 3004 2272 \hline 3005 C routine & 2 & 2& 0 \\3006 FetchAdd + FetchSub & 26 & 26 & 0 \\3007 Pthreads Mutex Lock & 31 & 31.86& 0.99 \\2273 C routine & 2 & 2 & 0 \\ 2274 FetchAdd + FetchSub & 26 & 26 & 0 \\ 2275 Pthreads Mutex Lock & 31 & 31.86 & 0.99 \\ 3008 2276 \uC @monitor@ member routine & 30 & 30 & 0 \\ 3009 \CFA @mutex@ routine, 1 argument & 41 & 41.57 & 0.9 \\3010 \CFA @mutex@ routine, 2 argument & 76 & 76.96 & 1.57 \\2277 \CFA @mutex@ routine, 1 argument & 41 & 41.57 & 0.9 \\ 2278 \CFA @mutex@ routine, 2 argument & 76 & 76.96 & 1.57 \\ 3011 2279 \CFA @mutex@ routine, 4 argument & 145 & 146.68 & 3.85 \\ 3012 Java synchronized routine & 27 & 28.57 & 2.6 \\2280 Java synchronized routine & 27 & 28.57 & 2.6 \\ 3013 2281 \hline 3014 2282 \end{tabular} 3015 \end{center}3016 \caption{Mutex routine comparison.3017 All numbers are in nanoseconds(\si{\nano\second})}3018 \label{tab:mutex}3019 2283 \end{table} 3020 3021 \subsection{Internal Scheduling} 3022 The internal-scheduling benchmark measures the cost of waiting on and signalling a condition variable. 3023 Figure~\ref{f:int-sched} shows the code for \CFA, with results table \ref{tab:int-sched}. 3024 As with all other benchmarks, all omitted tests are functionally identical to one of these tests. 3025 3026 \begin{figure} 3027 \begin{cfa}[caption={Benchmark code for internal scheduling},label={f:int-sched}] 2284 \end{samepage} 2285 2286 2287 \paragraph{Internal Scheduling} 2288 2289 Internal scheduling is measured by waiting on and signalling a condition variable. 2290 Figure~\ref{f:int-sched} shows the code for \CFA, with results in Table~\ref{tab:int-sched}. 2291 Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects. 2292 2293 \begin{samepage} 2294 \begin{figure}[!p] 2295 \lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} 2296 \begin{cfa} 3028 2297 volatile int go = 0; 3029 2298 condition c; 3030 monitor M {}; 3031 M m1; 3032 3033 void __attribute__((noinline)) do_call( M & mutex a1 ) { signal(c); } 3034 2299 monitor M {} m; 2300 void __attribute__((noinline)) do_call( M & mutex a1 ) { signal( c ); } 3035 2301 thread T {}; 3036 void ^?{}( T & mutex this ) {}3037 2302 void main( T & this ) { 3038 while(go == 0) { yield(); } 3039 while(go == 1) { do_call(m1); } 3040 } 3041 int __attribute__((noinline)) do_wait( M & mutex a1 ) { 3042 go = 1; 3043 BENCH( 3044 for(size_t i=0; i<n; i++) { 3045 wait(c); 3046 }, 3047 result 3048 ) 3049 printf("%llu\n", result); 3050 go = 0; 3051 return 0; 2303 while ( go == 0 ) { yield(); } // wait for other thread to start 2304 while ( go == 1 ) { @do_call( m );@ } 2305 } 2306 int __attribute__((noinline)) do_wait( M & mutex m ) { 2307 Duration result; 2308 go = 1; // continue other thread 2309 BENCH( for ( size_t i = 0; i < N; i += 1 ) { @wait( c );@ }, result ); 2310 go = 0; // stop other thread 2311 sout | result`ns | endl; 3052 2312 } 3053 2313 int main() { 3054 2314 T t; 3055 return do_wait(m1); 3056 } 3057 \end{cfa} 2315 do_wait( m ); 2316 } 2317 \end{cfa} 2318 \caption{Internal scheduling benchmark} 2319 \label{f:int-sched} 3058 2320 \end{figure} 3059 2321 3060 \begin{table} 3061 \begin{center} 3062 \begin{tabular}{| l | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] |} 2322 \begin{table}[!p] 2323 \centering 2324 \caption{Internal scheduling comparison (nanoseconds)} 2325 \label{tab:int-sched} 2326 \begin{tabular}{|r|*{3}{D{.}{.}{5.2}|}} 3063 2327 \cline{2-4} 3064 \multicolumn{1}{c |}{} & \multicolumn{1}{c |}{ Median } &\multicolumn{1}{c |}{ Average } & \multicolumn{1}{c |}{ Standard Deviation} \\2328 \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} &\multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\ 3065 2329 \hline 3066 Pthreads Condition Variable 3067 \uC @signal@ & 322 & 323 & 3.36 \\3068 \CFA @signal@, 1 @monitor@ & 352.5& 353.11 & 3.66 \\3069 \CFA @signal@, 2 @monitor@ & 430 & 430.29 & 8.97 \\3070 \CFA @signal@, 4 @monitor@ & 594.5& 606.57 & 18.33 \\3071 Java @notify@ & 13831.5 & 15698.21 & 4782.3 \\2330 Pthreads Condition Variable & 5902.5 & 6093.29 & 714.78 \\ 2331 \uC @signal@ & 322 & 323 & 3.36 \\ 2332 \CFA @signal@, 1 @monitor@ & 352.5 & 353.11 & 3.66 \\ 2333 \CFA @signal@, 2 @monitor@ & 430 & 430.29 & 8.97 \\ 2334 \CFA @signal@, 4 @monitor@ & 594.5 & 606.57 & 18.33 \\ 2335 Java @notify@ & 13831.5 & 15698.21 & 4782.3 \\ 3072 2336 \hline 3073 2337 \end{tabular} 3074 \end{center}3075 \caption{Internal scheduling comparison.3076 All numbers are in nanoseconds(\si{\nano\second})}3077 \label{tab:int-sched}3078 2338 \end{table} 3079 3080 \subsection{External Scheduling} 3081 The Internal scheduling benchmark measures the cost of the @waitfor@ statement (@_Accept@ in \uC). 3082 Figure~\ref{f:ext-sched} shows the code for \CFA, with results in table \ref{tab:ext-sched}. 3083 As with all other benchmarks, all omitted tests are functionally identical to one of these tests. 3084 2339 \end{samepage} 2340 2341 2342 \paragraph{External Scheduling} 2343 2344 External scheduling is measured by accepting a call using the @waitfor@ statement (@_Accept@ in \uC). 2345 Figure~\ref{f:ext-sched} shows the code for \CFA, with results in Table~\ref{tab:ext-sched}. 2346 Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects. 2347 2348 \begin{samepage} 3085 2349 \begin{figure} 3086 \begin{cfa}[caption={Benchmark code for external scheduling},label={f:ext-sched}] 2350 \lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} 2351 \begin{cfa} 3087 2352 volatile int go = 0; 3088 monitor M {}; 3089 M m1; 2353 monitor M {} m; 3090 2354 thread T {}; 3091 3092 void __attribute__((noinline)) do_call( M & mutex a1 ) {} 3093 3094 void ^?{}( T & mutex this ) {} 3095 void main( T & this ) { 3096 while(go == 0) { yield(); } 3097 while(go == 1) { do_call(m1); } 3098 } 3099 int __attribute__((noinline)) do_wait( M & mutex a1 ) { 3100 go = 1; 3101 BENCH( 3102 for(size_t i=0; i<n; i++) { 3103 waitfor(call, a1); 3104 }, 3105 result 3106 ) 3107 printf("%llu\n", result); 3108 go = 0; 3109 return 0; 2355 void __attribute__((noinline)) do_call( M & mutex ) {} 2356 void main( T & ) { 2357 while ( go == 0 ) { yield(); } // wait for other thread to start 2358 while ( go == 1 ) { @do_call( m );@ } 2359 } 2360 int __attribute__((noinline)) do_wait( M & mutex m ) { 2361 Duration result; 2362 go = 1; BENCH( for ( size_t i = 0; i < N; i += 1 ) { @waitfor( do_call, m );@ }, result ) go = 0; 2363 sout | result`ns | endl; 3110 2364 } 3111 2365 int main() { 3112 2366 T t; 3113 return do_wait(m1); 3114 } 3115 \end{cfa} 2367 do_wait( m ); 2368 } 2369 \end{cfa} 2370 \caption{Benchmark code for external scheduling} 2371 \label{f:ext-sched} 3116 2372 \end{figure} 3117 2373 3118 2374 \begin{table} 3119 \begin{center} 3120 \begin{tabular}{| l | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] |} 2375 \centering 2376 \caption{External scheduling comparison (nanoseconds)} 2377 \label{tab:ext-sched} 2378 \begin{tabular}{|r|*{3}{D{.}{.}{3.2}|}} 3121 2379 \cline{2-4} 3122 \multicolumn{1}{c |}{} & \multicolumn{1}{c |}{ Median } &\multicolumn{1}{c |}{ Average } & \multicolumn{1}{c |}{ Standard Deviation} \\2380 \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} &\multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\ 3123 2381 \hline 3124 \uC @Accept@ 3125 \CFA @waitfor@, 1 @monitor@ & 358.5 & 358.36 & 3.82 \\2382 \uC @Accept@ & 350 & 350.61 & 3.11 \\ 2383 \CFA @waitfor@, 1 @monitor@ & 358.5 & 358.36 & 3.82 \\ 3126 2384 \CFA @waitfor@, 2 @monitor@ & 422 & 426.79 & 7.95 \\ 3127 \CFA @waitfor@, 4 @monitor@ & 579.5 & 585.46 & 11.25 \\2385 \CFA @waitfor@, 4 @monitor@ & 579.5 & 585.46 & 11.25 \\ 3128 2386 \hline 3129 2387 \end{tabular} 3130 \end{center}3131 \caption{External scheduling comparison.3132 All numbers are in nanoseconds(\si{\nano\second})}3133 \label{tab:ext-sched}3134 2388 \end{table} 3135 3136 3137 \subsection{Object Creation} 3138 Finally, the last benchmark measures the cost of creation for concurrent objects. 3139 Figure~\ref{f:creation} shows the code for @pthread@s and \CFA threads, with results shown in table \ref{tab:creation}. 3140 As with all other benchmarks, all omitted tests are functionally identical to one of these tests. 3141 The only note here is that the call stacks of \CFA coroutines are lazily created, therefore without priming the coroutine, the creation cost is very low. 2389 \end{samepage} 2390 2391 2392 \paragraph{Object Creation} 2393 2394 Object creation is measured by creating/deleting the specific kind of concurrent object. 2395 Figure~\ref{f:creation} shows the code for \CFA, with results in Table~\ref{tab:creation}. 2396 The only note here is that the call stacks of \CFA coroutines are lazily created, therefore without priming the coroutine to force stack creation, the creation cost is artificially low. 3142 2397 3143 2398 \begin{figure} 3144 \begin{center} 3145 @pthread@ 3146 \begin{cfa} 2399 \centering 2400 \lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}} 2401 \begin{cfa} 2402 thread MyThread {}; 2403 void main( MyThread & ) {} 3147 2404 int main() { 3148 BENCH( 3149 for(size_t i=0; i<n; i++) { 3150 pthread_t thread; 3151 if(pthread_create(&thread,NULL,foo,NULL)<0) { 3152 perror( "failure" ); 3153 return 1; 3154 } 3155 3156 if(pthread_join(thread, NULL)<0) { 3157 perror( "failure" ); 3158 return 1; 3159 } 3160 }, 3161 result 3162 ) 3163 printf("%llu\n", result); 3164 } 3165 \end{cfa} 3166 3167 3168 3169 \CFA Threads 3170 \begin{cfa} 3171 int main() { 3172 BENCH( 3173 for(size_t i=0; i<n; i++) { 3174 MyThread m; 3175 }, 3176 result 3177 ) 3178 printf("%llu\n", result); 3179 } 3180 \end{cfa} 3181 \end{center} 3182 \caption{Benchmark code for \protect\lstinline|pthread|s and \CFA to measure object creation} 2405 Duration result; 2406 BENCH( for ( size_t i = 0; i < N; i += 1 ) { @MyThread m;@ }, result ) 2407 sout | result`ns | endl; 2408 } 2409 \end{cfa} 2410 \caption{Benchmark code for \CFA object creation} 3183 2411 \label{f:creation} 3184 2412 \end{figure} 3185 2413 3186 2414 \begin{table} 3187 \begin{center} 3188 \begin{tabular}{| l | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] |} 2415 \centering 2416 \caption{Creation comparison (nanoseconds)} 2417 \label{tab:creation} 2418 \begin{tabular}{|r|*{3}{D{.}{.}{5.2}|}} 3189 2419 \cline{2-4} 3190 \multicolumn{1}{c |}{} & \multicolumn{1}{c |}{ Median } &\multicolumn{1}{c |}{ Average } & \multicolumn{1}{c |}{ Standard Deviation} \\2420 \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} & \multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\ 3191 2421 \hline 3192 Pthreads & 26996& 26984.71 & 156.6 \\3193 \CFA Coroutine Lazy & 6 & 5.71& 0.45 \\2422 Pthreads & 26996 & 26984.71 & 156.6 \\ 2423 \CFA Coroutine Lazy & 6 & 5.71 & 0.45 \\ 3194 2424 \CFA Coroutine Eager & 708 & 706.68 & 4.82 \\ 3195 \CFA Thread & 1173.5 & 1176.18 & 15.18 \\3196 \uC Coroutine & 109 & 107.46 & 1.74 \\3197 \uC Thread & 526 & 530.89 & 9.73 \\3198 Goroutine & 2520.5 & 2530.93 & 61,56 \\3199 Java Thread & 91114.5 & 92272.79 & 961.58 \\2425 \CFA Thread & 1173.5 & 1176.18 & 15.18 \\ 2426 \uC Coroutine & 109 & 107.46 & 1.74 \\ 2427 \uC Thread & 526 & 530.89 & 9.73 \\ 2428 Goroutine & 2520.5 & 2530.93 & 61.56 \\ 2429 Java Thread & 91114.5 & 92272.79 & 961.58 \\ 3200 2430 \hline 3201 2431 \end{tabular} 3202 \end{center}3203 \caption{Creation comparison.3204 All numbers are in nanoseconds(\si{\nano\second}).}3205 \label{tab:creation}3206 2432 \end{table} 3207 2433 3208 2434 3209 3210 2435 \section{Conclusion} 3211 This paper has achieved a minimal concurrency \textbf{api} that is simple, efficient and usable as the basis for higher-level features. 3212 The approach presented is based on a lightweight thread-system for parallelism, which sits on top of clusters of processors. 3213 This M:N model is judged to be both more efficient and allow more flexibility for users. 3214 Furthermore, this document introduces monitors as the main concurrency tool for users. 3215 This paper also offers a novel approach allowing multiple monitors to be accessed simultaneously without running into the Nested Monitor Problem~\cite{Lister77}. 3216 It also offers a full implementation of the concurrency runtime written entirely in \CFA, effectively the largest \CFA code base to date. 3217 3218 3219 % ====================================================================== 3220 % ====================================================================== 2436 2437 This paper demonstrate a concurrency API that is simple, efficient, and able to build higher-level concurrency features. 2438 The approach provides concurrency based on a preemptive M:N user-level threading-system, executing in clusters, which encapsulate scheduling of work on multiple kernel threads providing parallelism. 2439 The M:N model is judged to be efficient and provide greater flexibility than a 1:1 threading model. 2440 High-level objects (monitor/task) are the core mechanism for mutual exclusion and synchronization. 2441 A novel aspect is allowing multiple mutex-objects to be accessed simultaneously reducing the potential for deadlock for this complex scenario. 2442 These concepts and the entire \CFA runtime-system are written in the \CFA language, demonstrating the expressiveness of the \CFA language. 2443 Performance comparisons with other concurrent systems/languages show the \CFA approach is competitive across all low-level operations, which translates directly into good performance in well-written concurrent applications. 2444 C programmers should feel comfortable using these mechanisms for developing concurrent applications, with the ability to obtain maximum available performance by mechanisms at the appropriate level. 2445 2446 3221 2447 \section{Future Work} 3222 % ====================================================================== 3223 % ====================================================================== 3224 3225 \subsection{Performance} \label{futur:perf} 3226 This paper presents a first implementation of the \CFA concurrency runtime. 3227 Therefore, there is still significant work to improve performance. 3228 Many of the data structures and algorithms may change in the future to more efficient versions. 3229 For example, the number of monitors in a single bulk acquire is only bound by the stack size, this is probably unnecessarily generous. 3230 It may be possible that limiting the number helps increase performance. 3231 However, it is not obvious that the benefit would be significant. 3232 3233 \subsection{Flexible Scheduling} \label{futur:sched} 2448 2449 While concurrency in \CFA has a strong start, development is still underway and there are missing features. 2450 2451 \paragraph{Flexible Scheduling} 2452 \label{futur:sched} 2453 3234 2454 An important part of concurrency is scheduling. 3235 2455 Different scheduling algorithms can affect performance (both in terms of average and variation). 3236 2456 However, no single scheduler is optimal for all workloads and therefore there is value in being able to change the scheduler for given programs. 3237 One solution is to offer various tweaking options to users, allowing the scheduler to be adjusted to the requirements of the workload. 3238 However, in order to be truly flexible, it would be interesting to allow users to add arbitrary data and arbitrary scheduling algorithms. 3239 For example, a web server could attach Type-of-Service information to threads and have a ``ToS aware'' scheduling algorithm tailored to this specific web server. 3240 This path of flexible schedulers will be explored for \CFA. 3241 3242 \subsection{Non-Blocking I/O} \label{futur:nbio} 3243 While most of the parallelism tools are aimed at data parallelism and control-flow parallelism, many modern workloads are not bound on computation but on IO operations, a common case being web servers and XaaS (anything as a service). 3244 These types of workloads often require significant engineering around amortizing costs of blocking IO operations. 3245 At its core, non-blocking I/O is an operating system level feature that allows queuing IO operations (\eg network operations) and registering for notifications instead of waiting for requests to complete. 3246 In this context, the role of the language makes Non-Blocking IO easily available and with low overhead. 3247 The current trend is to use asynchronous programming using tools like callbacks and/or futures and promises, which can be seen in frameworks like Node.js~\cite{NodeJs} for JavaScript, Spring MVC~\cite{SpringMVC} for Java and Django~\cite{Django} for Python. 3248 However, while these are valid solutions, they lead to code that is harder to read and maintain because it is much less linear. 3249 3250 \subsection{Other Concurrency Tools} \label{futur:tools} 3251 While monitors offer a flexible and powerful concurrent core for \CFA, other concurrency tools are also necessary for a complete multi-paradigm concurrency package. 3252 Examples of such tools can include simple locks and condition variables, futures and promises~\cite{promises}, executors and actors. 2457 One solution is to offer various tweaking options, allowing the scheduler to be adjusted to the requirements of the workload. 2458 However, to be truly flexible, it is necessary to have a pluggable scheduler. 2459 Currently, the \CFA pluggable scheduler is too simple to handle complex scheduling, \eg quality of service and real-time, where the scheduler must interact with mutex objects to deal with issues like priority inversion. 2460 2461 \paragraph{Non-Blocking I/O} 2462 \label{futur:nbio} 2463 2464 Many modern workloads are not bound by computation but IO operations, a common case being web servers and XaaS~\cite{XaaS} (anything as a service). 2465 These types of workloads require significant engineering to amortizing costs of blocking IO-operations. 2466 At its core, non-blocking I/O is an operating-system level feature queuing IO operations, \eg network operations, and registering for notifications instead of waiting for requests to complete. 2467 Current trends use asynchronous programming like callbacks, futures, and/or promises, \eg Node.js~\cite{NodeJs} for JavaScript, Spring MVC~\cite{SpringMVC} for Java, and Django~\cite{Django} for Python. 2468 However, these solutions lead to code that is hard create, read and maintain. 2469 A better approach is to tie non-blocking I/O into the concurrency system to provide ease of use with low overhead, \eg thread-per-connection web-services. 2470 A non-blocking I/O library is currently under development for \CFA. 2471 2472 \paragraph{Other Concurrency Tools} 2473 \label{futur:tools} 2474 2475 While monitors offer a flexible and powerful concurrent for \CFA, other concurrency tools are also necessary for a complete multi-paradigm concurrency package. 2476 Examples of such tools can include futures and promises~\cite{promises}, executors and actors. 3253 2477 These additional features are useful when monitors offer a level of abstraction that is inadequate for certain tasks. 3254 2478 3255 \subsection{Implicit Threading} \label{futur:implcit} 3256 Simpler applications can benefit greatly from having implicit parallelism. 3257 That is, parallelism that does not rely on the user to write concurrency. 3258 This type of parallelism can be achieved both at the language level and at the library level. 3259 The canonical example of implicit parallelism is parallel for loops, which are the simplest example of a divide and conquer algorithms~\cite{uC++book}. 3260 Table \ref{f:parfor} shows three different code examples that accomplish point-wise sums of large arrays. 3261 Note that none of these examples explicitly declare any concurrency or parallelism objects. 3262 3263 \begin{table} 3264 \begin{center} 3265 \begin{tabular}[t]{|c|c|c|} 3266 Sequential & Library Parallel & Language Parallel \\ 3267 \begin{cfa}[tabsize=3] 3268 void big_sum( 3269 int* a, int* b, 3270 int* o, 3271 size_t len) 3272 { 3273 for( 3274 int i = 0; 3275 i < len; 3276 ++i ) 3277 { 3278 o[i]=a[i]+b[i]; 3279 } 3280 } 3281 3282 3283 3284 3285 3286 int* a[10000]; 3287 int* b[10000]; 3288 int* c[10000]; 3289 //... fill in a & b 3290 big_sum(a,b,c,10000); 3291 \end{cfa} &\begin{cfa}[tabsize=3] 3292 void big_sum( 3293 int* a, int* b, 3294 int* o, 3295 size_t len) 3296 { 3297 range ar(a, a+len); 3298 range br(b, b+len); 3299 range or(o, o+len); 3300 parfor( ai, bi, oi, 3301 []( int* ai, 3302 int* bi, 3303 int* oi) 3304 { 3305 oi=ai+bi; 3306 }); 3307 } 3308 3309 3310 int* a[10000]; 3311 int* b[10000]; 3312 int* c[10000]; 3313 //... fill in a & b 3314 big_sum(a,b,c,10000); 3315 \end{cfa}&\begin{cfa}[tabsize=3] 3316 void big_sum( 3317 int* a, int* b, 3318 int* o, 3319 size_t len) 3320 { 3321 parfor (ai,bi,oi) 3322 in (a, b, o ) 3323 { 3324 oi = ai + bi; 3325 } 3326 } 3327 3328 3329 3330 3331 3332 3333 3334 int* a[10000]; 3335 int* b[10000]; 3336 int* c[10000]; 3337 //... fill in a & b 3338 big_sum(a,b,c,10000); 3339 \end{cfa} 3340 \end{tabular} 3341 \end{center} 3342 \caption{For loop to sum numbers: Sequential, using library parallelism and language parallelism.} 3343 \label{f:parfor} 3344 \end{table} 3345 3346 Implicit parallelism is a restrictive solution and therefore has its limitations. 3347 However, it is a quick and simple approach to parallelism, which may very well be sufficient for smaller applications and reduces the amount of boilerplate needed to start benefiting from parallelism in modern CPUs. 3348 3349 3350 % A C K N O W L E D G E M E N T S 3351 % ------------------------------- 2479 \paragraph{Implicit Threading} 2480 \label{futur:implcit} 2481 2482 Basic concurrent (embarrassingly parallel) applications can benefit greatly from implicit concurrency, where sequential programs are converted to concurrent, possibly with some help from pragmas to guide the conversion. 2483 This type of concurrency can be achieved both at the language level and at the library level. 2484 The canonical example of implicit concurrency is concurrent nested @for@ loops, which are amenable to divide and conquer algorithms~\cite{uC++book}. 2485 The \CFA language features should make it possible to develop a reasonable number of implicit concurrency mechanism to solve basic HPC data-concurrency problems. 2486 However, implicit concurrency is a restrictive solution and has its limitations, so it can never replace explicit concurrent programming. 2487 2488 3352 2489 \section{Acknowledgements} 3353 2490 3354 Thanks to Aaron Moss, Rob Schluntz and Andrew Beach for their work on the \CFA project as well as all the discussions which helped concretize the ideas in this paper. 3355 Partial funding was supplied by the Natural Sciences and Engineering Research Council of Canada and a corporate partnership with Huawei Ltd. 3356 3357 3358 % B I B L I O G R A P H Y 3359 % ----------------------------- 3360 %\bibliographystyle{plain} 2491 The authors would like to recognize the design assistance of Aaron Moss, Rob Schluntz and Andrew Beach on the features described in this paper. 2492 Funding for this project has been provided by Huawei Ltd.\ (\url{http://www.huawei.com}), and Peter Buhr is partially funded by the Natural Sciences and Engineering Research Council of Canada. 2493 2494 {% 2495 \fontsize{9bp}{12bp}\selectfont% 3361 2496 \bibliography{pl,local} 3362 2497 }% 3363 2498 3364 2499 \end{document}
Note: See TracChangeset
for help on using the changeset viewer.