Changeset 45af7e1


Ignore:
Timestamp:
Feb 19, 2019, 3:31:37 PM (3 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, persistent-indexer
Children:
5170d95
Parents:
b43ea9e
Message:

start rewrite of concurrency paper for SPE

Location:
doc
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/bibliography/pl.bib

    rb43ea9e r45af7e1  
    832832    howpublished= {\href{http://www.boost.org/doc/libs/1_61_0/libs/coroutine/doc/html/index.html}
    833833                  {http://www.boost.org/\-doc/\-libs/1\_61\_0/\-libs/\-coroutine/\-doc/\-html/\-index.html}},
    834     optnote     = {Accessed: 2016-09},
    835834}
    836835
     
    843842    howpublished= {\href{https://www.boost.org/doc/libs/1_61_0/doc/html/thread.html}
    844843                  {https://\-www.boost.org/\-doc/\-libs/\-1\_61\_0/\-doc/\-html/\-thread.html}},
    845     optnote     = {Accessed: 2016-09},
    846844}
    847845
     
    950948    author      = {{\textsf{C}{$\mathbf{\forall}$} Features}},
    951949    howpublished= {\href{https://plg.uwaterloo.ca/~cforall/features}{https://\-plg.uwaterloo.ca/\-$\sim$cforall/\-features}},
    952     optnote     = {Accessed: 2018-01-01},
    953950}
    954951
     
    970967    year        = 2018,
    971968    howpublished= {\href{https://cforall.uwaterloo.ca/CFAStackEvaluation.zip}{https://cforall.uwaterloo.ca/\-CFAStackEvaluation.zip}},
    972     optnote     = {[Accessed May 2018]},
    973969}
    974970
     
    14701466    title       = {concurrent-locking},
    14711467    howpublished= {\href{https://github.com/pabuhr/concurrent-locking}{https://\-github.com/\-pabuhr/\-concurrent-locking}},
    1472     optnote     = {[Accessed April 2017]},
    14731468}
    14741469
     
    17581753    howpublished= {\href{https://www.airs.com/blog/archives/428}
    17591754                  {https://www.airs.com/\-blog/\-archives/\-428}},
    1760     optnote     = {Accessed: 2018-05},
    17611755}
    17621756
     
    29172911    year        = 2014,
    29182912    howpublished= {\href{https://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/C-Extensions.html}{https://\-gcc.gnu.org/\-onlinedocs/\-gcc-4.7.2/\-gcc/\-C\-Extensions.html}},
    2919     optnote     = {Accessed: 2017-04-02},
    29202913}
    29212914
     
    33483341    year        = 2014,
    33493342    howpublished= {https://developer.gnome.org/gobject/stable/},
    3350     optnote     = {Accessed: 2017-04},
    33513343}
    33523344
     
    50265018    year        = 2014,
    50275019    howpublished= {\href{https://developer.apple.com/library/archive/documentation/Cocoa/Conceptual/ProgrammingWithObjectiveC}{https://\-developer.apple.com/\-library/archive/\-documentation/\-Cocoa/\-Conceptual/\-ProgrammingWithObjectiveC}},
    5028     optnote     = {Accessed: 2018-03}
    50295020}
    50305021
     
    50365027    year        = 2015,
    50375028    howpublished= {\href{https://developer.apple.com/library/content/documentation/Xcode/Conceptual/RN-Xcode-Archive/Chapters/xc7_release_notes.html}{https://\-developer.apple.com/\-library/\-content/\-documentation/\-Xcode/\-Conceptual/\-RN-Xcode-Archive/\-Chapters/\-xc7\_release\_notes.html}},
    5038     optnote     = {Accessed: 2017-04}
    50395029}
    50405030
     
    55495539    year        = 2012,
    55505540    howpublished= {\href{http://cs.brown.edu/research/pubs/theses/masters/2012/verch.pdf}{http://cs.brown.edu/\-research/\-pubs/\-theses/\-masters/\-2012/\-verch.pdf}},
    5551     optnote     = {Accessed: 2013-10-4}
    55525541}
    55535542
     
    60376026    institution = {Carnegie Mellon University},
    60386027    year        = 1991,
    6039     month       = feb, number = "CMU-CS-91-106",
     6028    month       = feb,
     6029    number      = {CMU-CS-91-106},
    60406030    annote      = {
    60416031        Discusses a typed lambda calculus with
     
    60946084    journal     = sigplan,
    60956085    year        = 1988,
    6096     month       = jul, volume = 23, number = 7, pages = {260-267},
    6097     note        = {Proceedings of the SIGPLAN '88 Conference on Programming Language
    6098          Design and Implementation},
     6086    month       = jul,
     6087    volume      = 23,
     6088    number      = 7,
     6089    pages       = {260-267},
     6090    note        = {Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation},
    60996091    abstract    = {
    61006092        This paper deals with the integration of an efficient asynchronous
     
    61446136    month       = jun,
    61456137    year        = 1987,
     6138}
     6139
     6140@misc{Pthreads,
     6141    keywords    = {pthreads, C concurrency},
     6142    contributer = {pabuhr@plg},
     6143    key         = {pthreads},
     6144    title       = {{Pthread}.h, Specifications Issue 7, {IEEE} Std 1003.1-2017},
     6145    author      = {IEEE and {The Open Group}},
     6146    year        = 2018,
     6147    howpublished= {\href{http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/pthread.h.html}
     6148                  {http://\-pubs.opengroup.org/\-onlinepubs/\-9699919799/\-basedefs/\-pthread.h.html}},
    61466149}
    61476150
     
    63276330    number      = 10,
    63286331    pages       = {27-32},
     6332}
     6333
     6334@article{Hesselink06,
     6335    author      = {Wim H. Hesselink},
     6336    title       = {Refinement Verification of the Lazy Caching Algorithm},
     6337    journal     = acta,
     6338    year        = 2006,
     6339    month       = oct,
     6340    volume      = 43,
     6341    number      = 3,
     6342    pages       = {195--222},
    63296343}
    63306344
     
    72657279    author      = {{TIOBE Index}},
    72667280    howpublished= {\href{http://www.tiobe.com/tiobe_index}{http://\-www.tiobe.com/\-tiobe\_index}},
    7267     optnote     = {Accessed: 2018-09},
     7281}
     7282
     7283@misc{ThreadModel,
     7284    contributer = {pabuhr@plg},
     7285    key         = {ThreadModel},
     7286    title       = {Thread (computing)},
     7287    author      = {{Threading Model}},
     7288    howpublished= {\href{https://en.wikipedia.org/wiki/Thread_(computing)}{https://\-en.wikipedia.org/\-wiki/\-Thread\_(computing)}},
    72687289}
    72697290
     
    75977618    year        = 2017,
    75987619    howpublished= {\url{https://wiki.gnome.org/Projects/Vala/Manual}},
    7599     optnote     = {Accessed: 2017-04}
    76007620}
    76017621
  • doc/papers/concurrency/Paper.tex

    rb43ea9e r45af7e1  
    241241
    242242\abstract[Summary]{
    243 \CFA is a modern, polymorphic, \emph{non-object-oriented} extension of the C programming language.
    244 This paper discusses the design of the concurrency and parallelism features in \CFA, and its concurrent runtime-system.
    245 These features are created from scratch as ISO C lacks concurrency, relying largely on the pthreads library for concurrency.
    246 Coroutines and lightweight (user) threads are introduced into \CFA;
    247 as well, monitors are added as a high-level mechanism for mutual exclusion and synchronization.
     243\CFA is a modern, polymorphic, \emph{non-object-oriented}, backwards-compatible extension of the C programming language.
     244This paper discusses the concurrency and parallelism features in \CFA, and its runtime system.
     245These features are created from scratch as ISO C's concurrency is low-level and unimplemented, so C programmers continue to rely on the C pthreads library.
     246\CFA provides high-level control-flow mechanisms, like coroutines and lightweight (user) threads, and monitors for mutual exclusion and synchronization.
    248247A unique contribution of this work is allowing multiple monitors to be safely acquired \emph{simultaneously}.
    249248All features respect the expectations of C programmers, while being fully integrate with the \CFA polymorphic type-system and other language features.
     
    251250}%
    252251
    253 \keywords{concurrency, parallelism, coroutines, threads, monitors, runtime, C, Cforall}
     252\keywords{concurrency, parallelism, coroutines, threads, monitors, runtime, C, \CFA (Cforall)}
    254253
    255254
     
    262261\section{Introduction}
    263262
     263This paper discusses the design of the high-level concurrency and parallelism features in \CFA, and its runtime.
     264\CFA is a modern, polymorphic, \emph{non-object-oriented}, backwards-compatible extension of the C programming language~\cite{Moss18}.
     265Within the \CFA framework, new concurrency features were created from scratch.
     266While ISO \Celeven defines concurrency~\cite[\S~7.26]{C11}, it is largely wrappers for a subset of the pthreads library~\cite{Butenhof97,Pthreads}.
     267Furthermore, \Celeven and pthreads concurrency is simple: create/join threads in a function and a few locks, which is low-level and error prone;
     268no high-level language concurrency features exist.
     269Interestingly, 8 years since publication of the \Celeven standard, neither gcc-8 nor clang-8 (most recent versions) support \Celeven @threads.h@, indicating little interest in the C concurrency approach.
     270Finally, while the \Celeven standard does not state a concurrent threading-model, the strong association with pthreads suggests the threading model is kernel-level threading (1:1)~\cite{ThreadModel}.
     271
     272There has been a re-interest during the past decade in user-level (M:N, green) threading in new and old programming languages, and providing high-level constructs like coroutines, monitors, tasks, and actors for presenting advanced control-flow.
     273As multi-core hardware became available in the 1980/90s, both user and kernel threading were examined.
     274Kernel threading was chosen, largely because of its simplicity and fit with the simpler operating systems and hardware architectures at the time, which gave it a performance advantage~\cite{Drepper03}.
     275Libraries like pthreads were developed for C and the Solaris operating-system switched from user (JDK 1.1~\cite{JDK1.1}) to kernel threads.
     276As a result, languages like Java, Scala~\cite{Scala}, Objective-C~\cite{obj-c-book}, \CCeleven~\cite{C11}, and C\#~\cite{Csharp} adopted the 1:1 kernel-threading model, with a variety of presentation mechanisms.
     277From 2000 onwards, languages like Go~\cite{Go}, Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, D~\cite{D}, and \uC~\cite{uC++,uC++book} have championed the M:N user-threading model, and many user-threading libraries have appeared~\cite{Qthreads,MPC,BoostThreads}, including putting green threads back into Java~\cite{Quasar}.
     278Because advanced control-flow (including exception handling) is pervasive in a programming language and its runtime, these features must be understood by the language (i.e., not added via a library) to prevent invalidation by sequential optimizations~\cite{Buhr95a,Boehm05}.
     279
     280The main argument for user-level threading is matching the concurrency model with the programming-language style, versus adapting language concurrency to one general approach.
     281For example, it is possible to provide coroutines, monitors, and tasks as specialized types in an object-oriented language, integrating these constructs to allow leveraging the type-system (static type-checking) and all other object-oriented capabilities~\cite{uC++}.
     282The user-threading approach facilitates a simpler concurrency construction using thread objects and leveraging sequential patterns versus call-backs and events~\cite{vonBehren03}.
     283As well, user-level threads are lighter weight than kernel threads, so there is less restriction on programming styles that encourage large numbers of threads performing smaller work-units to facilitate load balancing by the runtime~\cite{Verch12}.
     284User threading is also able to layer multiple concurrency models into a single language (locks, monitors, tasks, actors, futures), so programmers can chose the model that best fits an application.
     285Finally, it is possible to discretely fold locking and non-blocking I/O multiplexing into the language's I/O libraries, so threading implicitly dovetails with the I/O subsystem.
     286Performant user-threading implementations (both time and space) are appearing that are competitive with direct kernel-threading implementations, while achieving the programming advantages of high concurrency levels and safety.
     287
     288Adding advanced control-flow to \CFA is similar to current and future extensions in \CCeleven through to \CCtwenty.
     289However, we contend the \CFA extensions are demonstrably better than those proposed for \CC.
     290For example, a unique contribution of this work is allowing multiple monitors to be safely acquired \emph{simultaneously} (deadlock free), while integrating this capability with all monitor synchronization mechanisms.
     291As well, all control-flow features respect the expectations of C programmers, with statically type-safe interfaces that integrate with the \CFA polymorphic type-system and other language features.
     292Experimental results show comparable performance of the new features with similar mechanisms in other concurrent programming-languages.
     293
     294\begin{comment}
    264295This paper provides a minimal concurrency \newterm{Application Program Interface} (API) that is simple, efficient and can be used to build other concurrency features.
    265296While the simplest concurrency system is a thread and a lock, this low-level approach is hard to master.
     
    281312The proposed concurrency API is implemented in a dialect of C, called \CFA (pronounced C-for-all).
    282313The paper discusses how the language features are added to the \CFA translator with respect to parsing, semantics, and type checking, and the corresponding high-performance runtime-library to implement the concurrent features.
    283 
    284 
     314\end{comment}
     315
     316
     317\begin{comment}
    285318\section{\CFA Overview}
    286319
     
    551584\end{cfa}
    552585where the return type supplies the type/size of the allocation, which is impossible in most type systems.
     586\end{comment}
    553587
    554588
Note: See TracChangeset for help on using the changeset viewer.