Changeset 1dc58fd


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

Location:
doc
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/bibliography/pl.bib

    r03bd407 r1dc58fd  
    375375    year        = 1991,
    376376    pages       = {21-65},
     377}
     378
     379@article{Hoare61,
     380    keywords    = {quick sort},
     381    contributer = {pabuhr@plg},
     382    author      = {C. A. R. Hoare},
     383    title       = {Algorithms 63/64: Partition/Quicksort},
     384    journal     = cacm,
     385    volume      = 4,
     386    number      = 7,
     387    month       = jul,
     388    year        = 1961,
     389    pages       = {321},
    377390}
    378391
     
    57915804@manual{Python,
    57925805    keywords    = {Python},
    5793     contributer = {pabuhr},
     5806    contributer = {pabuhr@plg},
    57945807    title       = {Python Reference Manual, Release 2.5},
    57955808    author      = {Guido van Rossum},
     
    58225835}
    58235836
    5824 @article{Hoare61,
    5825     keywords    = {quick sort},
    5826     contributer = {pabuhr@plg},
    5827     author      = {C. A. R. Hoare},
    5828     title       = {Algorithms 63/64: Partition/Quicksort},
    5829     journal     = cacm,
    5830     volume      = 4,
    5831     number      = 7,
    5832     month       = jul,
    5833     year        = 1961,
    5834     pages       = {321},
     5837@article{Nakaike15,
     5838    keywords    = {hardware transactional memory},
     5839    contributer = {pabuhr@plg},
     5840    author      = {Nakaike, Takuya and Odaira, Rei and Gaudet, Matthew and Michael, Maged M. and Tomari, Hisanobu},
     5841    title       = {Quantitative Comparison of Hardware Transactional Memory for Blue Gene/Q, zEnterprise {EC12}, {I}ntel Core, and {POWER8}},
     5842    journal     = {SIGARCH Comput. Archit. News},
     5843    volume      = {43},
     5844    number      = {3},
     5845    month       = jun,
     5846    year        = {2015},
     5847    pages       = {144--157},
     5848    publisher   = {ACM},
     5849    address     = {New York, NY, USA},
    58355850}
    58365851
  • 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.