Changeset 1dc58fd for doc/papers


Ignore:
Timestamp:
May 24, 2018, 12:56:10 PM (3 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, with_gc
Children:
c0a33d2, e982385
Parents:
03bd407
Message:

more writing

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/papers/concurrency/Paper.tex

    r03bd407 r1dc58fd  
    7070%\DeclareTextCommandDefault{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}
    7171\renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
    72 %\def\myCHarFont{\fontencoding{T1}\selectfont}%
    73 % \def\{{\ttfamily\upshape\myCHarFont \char`\}}}%
    7472
    7573\renewcommand*{\thefootnote}{\Alph{footnote}} % hack because fnsymbol does not work
     
    11711169The heap-based approach allows arbitrary thread-creation topologies, with respect to fork/join-style concurrency.
    11721170
     1171Figure~\ref{s:ConcurrentMatrixSummation} shows concurrently adding the rows of a matrix and then totalling the subtotals sequential, after all the row threads have terminated.
     1172The program uses heap-based threads because each thread needs different constructor values.
     1173(Python provides a simple iteration mechanism to initialize array elements to different values allowing stack allocation.)
     1174The allocation/deallocation pattern appears unusual because allocated objects are immediately deleted without any intervening code.
     1175However, for threads, the deletion provides implicit synchronization, which is the intervening code.
     1176While the subtotals are added in linear order rather than completion order, which slight inhibits concurrency, the computation is restricted by the critical-path thread (\ie the thread that takes the longest), and so any inhibited concurrency is very small as totalling the subtotals is trivial.
     1177
     1178\begin{figure}
     1179\begin{cfa}
     1180thread Adder {
     1181    int * row, cols, * subtotal;                        $\C{// communication}$
     1182};
     1183void ?{}( Adder & adder, int row[], int cols, int & subtotal ) {
     1184    adder.[ row, cols, subtotal ] = [ row, cols, &subtotal ];
     1185}
     1186void main( Adder & adder ) with( adder ) {
     1187    *subtotal = 0;
     1188    for ( int c = 0; c < cols; c += 1 ) {
     1189                *subtotal += row[c];
     1190    }
     1191}
     1192int main() {
     1193    const int rows = 10, cols = 1000;
     1194    int matrix[rows][cols], subtotals[rows], total = 0;
     1195    // read matrix
     1196    Adder * adders[rows];
     1197    for ( int r = 0; r < rows; r += 1 ) {       $\C{// start threads to sum rows}$
     1198                adders[r] = new( matrix[r], cols, &subtotals[r] );
     1199    }
     1200    for ( int r = 0; r < rows; r += 1 ) {       $\C{// wait for threads to finish}$
     1201                delete( adders[r] );                            $\C{// termination join}$
     1202                total += subtotals[r];                          $\C{// total subtotal}$
     1203    }
     1204    sout | total | endl;
     1205}
     1206\end{cfa}
     1207\caption{Concurrent Matrix Summation}
     1208\label{s:ConcurrentMatrixSummation}
     1209\end{figure}
     1210
    11731211
    11741212\section{Synchronization / Mutual Exclusion}
     
    11831221In contrast, approaches based on statefull models more closely resemble the standard call/return programming-model, resulting in a single programming paradigm.
    11841222
    1185 At the lowest level, concurrent control is implemented as atomic operations, upon which difference kinds of locks/approaches are constructed, \eg semaphores~\cite{Dijkstra68b} and path expressions~\cite{Campbell74}.
     1223At the lowest level, concurrent control is implemented as atomic operations, upon which different kinds of locks mechanism are constructed, \eg semaphores~\cite{Dijkstra68b} and path expressions~\cite{Campbell74}.
    11861224However, for productivity it is always desirable to use the highest-level construct that provides the necessary efficiency~\cite{Hochstein05}.
    1187 An newer approach worth mentioning is transactional memory~\cite{Herlihy93}.
    1188 While this approach is pursued in hardware~\cite{} and system languages, like \CC~\cite{Cpp-Transactions}, the performance and feature set is still too restrictive to be the main concurrency paradigm for system languages, which is why it was rejected as the core paradigm for concurrency in \CFA.
     1225A newer approach is transactional memory~\cite{Herlihy93}.
     1226While this approach is pursued in hardware~\cite{Nakaike15} and system languages, like \CC~\cite{Cpp-Transactions}, the performance and feature set is still too restrictive to be the main concurrency paradigm for system languages, which is why it was rejected as the core paradigm for concurrency in \CFA.
    11891227
    11901228One of the most natural, elegant, and efficient mechanisms for synchronization and mutual exclusion for shared-memory systems is the \emph{monitor}.
    11911229Monitors were first proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}.
    1192 Many programming languages---\eg Concurrent Pascal~\cite{ConcurrentPascal}, Mesa~\cite{Mesa}, Modula~\cite{Modula-2}, Turing~\cite{Turing:old}, Modula-3~\cite{Modula-3}, NeWS~\cite{NeWS}, Emerald~\cite{Emerald}, \uC~\cite{Buhr92a} and Java~\cite{Java}---provide monitors as explicit language constructs.
     1230Many programming languages -- \eg Concurrent Pascal~\cite{ConcurrentPascal}, Mesa~\cite{Mesa}, Modula~\cite{Modula-2}, Turing~\cite{Turing:old}, Modula-3~\cite{Modula-3}, NeWS~\cite{NeWS}, Emerald~\cite{Emerald}, \uC~\cite{Buhr92a} and Java~\cite{Java} -- provide monitors as explicit language constructs.
    11931231In addition, operating-system kernels and device drivers have a monitor-like structure, although they often use lower-level primitives such as semaphores or locks to simulate monitors.
    11941232For these reasons, this project proposes monitors as the core concurrency construct, upon which even higher-level approaches can be easily constructed..
Note: See TracChangeset for help on using the changeset viewer.