Ignore:
File:
1 edited

Legend:

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

    r35a9e41 r2ebcb28  
    764764};
    765765void main( Format & fmt ) with( fmt ) {
    766         for ( ;; ) {
     766        for ( ;; ) {   
    767767                for ( g = 0; g < 5; g += 1 ) {      // group
    768768                        for ( b = 0; b < 4; b += 1 ) { // block
     
    13091309void print( Tree & mutex tree ) {                       $\C{// prefix traversal}$
    13101310        // write value
    1311         print( tree->left );                                    $\C{// multiply acquire monitor lock for tree on each recursion}$
    1312         print( tree->right );
     1311        print( *tree->left );                                   $\C{// multiply acquire monitor lock for tree on each recursion}$
     1312        print( *tree->right );
    13131313}
    13141314\end{cfa}
     
    15461546A thread blocks until an appropriate partner arrives.
    15471547The complexity is exchanging phone numbers in the monitor because of the mutual-exclusion property.
    1548 For signal scheduling, the @exchange@ condition is necessary to block the thread finding the match, while the matcher unblocks to take the opposite number, post its phone number, and unblock the partner.
     1548For signal scheduling, the @exchange@ condition is necessary to block the thread finding the match, while the matcher unblocks to take the opposite number, post its phone number, and unblock the partner. 
    15491549For signal-block scheduling, the implicit urgent-queue replaces the explict @exchange@-condition and @signal_block@ puts the finding thread on the urgent condition and unblocks the matcher.
    15501550
     
    20892089In \CFA, ordering of monitor acquisition relies on memory ordering to prevent deadlock~\cite{Havender68}, because all objects have distinct non-overlapping memory layouts, and mutual-exclusion for a monitor is only defined for its lifetime.
    20902090When a mutex call is made, pointers to the concerned monitors are aggregated into a variable-length array and sorted.
    2091 This array persists for the entire duration of the mutual-exclusion and is used extensively for synchronization operations.
     2091This array persists for the entire duration of the mutual exclusion and is used extensively for synchronization operations.
    20922092
    20932093To improve performance and simplicity, context switching occurs inside a routine call, so only callee-saved registers are copied onto the stack and then the stack register is switched;
     
    21702170\end{cfa}
    21712171The method used to get time is @clock_gettime( CLOCK_REALTIME )@.
    2172 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.
     2172Each benchmark is performed @N@ times, where @N@ varies depending on the benchmark;
     2173the total time is divided by @N@ to obtain the average time for a benchmark.
    21732174All omitted tests for other languages are functionally identical to the shown \CFA test.
    21742175
     
    22282229\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} &\multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\
    22292230\hline
    2230 Kernel Thread   & 333.5 & 332.96        & 4.1 \\
    2231 \CFA Coroutine  & 49            & 48.68 & 0.47    \\
    2232 \CFA Thread             & 105           & 105.57        & 1.37 \\
    2233 \uC Coroutine   & 44            & 44            & 0 \\
    2234 \uC Thread              & 100           & 99.29 & 0.96 \\
    2235 Goroutine               & 145           & 147.25        & 4.15 \\
    2236 Java Thread             & 373.5 & 375.14        & 8.72 \\
     2231Kernel Thread   & 241.5         & 243.86        & 5.08 \\
     2232\CFA Coroutine  & 38            & 38            & 0    \\
     2233\CFA Thread             & 103           & 102.96        & 2.96 \\
     2234\uC Coroutine   & 46            & 45.86         & 0.35 \\
     2235\uC Thread              & 98            & 99.11         & 1.42 \\
     2236Goroutine               & 150           & 149.96        & 3.16 \\
     2237Java Thread             & 289           & 290.68        & 8.72 \\
    22372238\hline
    22382239\end{tabular}
     
    22632264\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} &\multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\
    22642265\hline
    2265 C routine                                       & 2             & 2             & 0    \\
    2266 FetchAdd + FetchSub                     & 26            & 26            & 0    \\
    2267 Pthreads Mutex Lock                     & 31            & 31.71 & 0.97 \\
    2268 \uC @monitor@ member routine            & 31            & 31            & 0    \\
    2269 \CFA @mutex@ routine, 1 argument        & 46            & 46.68 & 0.93  \\
    2270 \CFA @mutex@ routine, 2 argument        & 84            & 85.36 & 1.99 \\
    2271 \CFA @mutex@ routine, 4 argument        & 158           & 161           & 4.22 \\
    2272 Java synchronized routine               & 27.5  & 29.79 & 2.93  \\
     2266C routine                                                       & 2                     & 2                     & 0    \\
     2267FetchAdd + FetchSub                                     & 26            & 26            & 0    \\
     2268Pthreads Mutex Lock                                     & 31            & 31.86         & 0.99 \\
     2269\uC @monitor@ member routine            & 30            & 30            & 0    \\
     2270\CFA @mutex@ routine, 1 argument        & 41            & 41.57         & 0.9  \\
     2271\CFA @mutex@ routine, 2 argument        & 76            & 76.96         & 1.57 \\
     2272\CFA @mutex@ routine, 4 argument        & 145           & 146.68        & 3.85 \\
     2273Java synchronized routine                       & 27            & 28.57         & 2.6  \\
    22732274\hline
    22742275\end{tabular}
     
    23152316}
    23162317\end{cfa}
    2317 \captionof{figure}{\CFA Internal scheduling benchmark}
     2318\captionof{figure}{\CFA Internal-scheduling benchmark}
    23182319\label{f:int-sched}
    23192320
    23202321\centering
    2321 \captionof{table}{Internal scheduling comparison (nanoseconds)}
     2322\captionof{table}{Internal-scheduling comparison (nanoseconds)}
    23222323\label{tab:int-sched}
    23232324\bigskip
     
    23272328\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} &\multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\
    23282329\hline
    2329 Pthreads Condition Variable             & 6005  & 5681.43       & 835.45 \\
    2330 \uC @signal@                                    & 324           & 325.54        & 3,02   \\
    2331 \CFA @signal@, 1 @monitor@              & 368.5         & 370.61        & 4.77   \\
    2332 \CFA @signal@, 2 @monitor@              & 467           & 470.5 & 6.79   \\
    2333 \CFA @signal@, 4 @monitor@              & 700.5         & 702.46        & 7.23  \\
    2334 Java @notify@                                   & 15471 & 172511        & 5689 \\
     2330Pthreads 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  \\
     2335Java @notify@                                   & 13831.5       & 15698.21      & 4782.3 \\
    23352336\hline
    23362337\end{tabular}
     
    23662367}
    23672368\end{cfa}
    2368 \captionof{figure}{\CFA external scheduling benchmark}
     2369\captionof{figure}{\CFA external-scheduling benchmark}
    23692370\label{f:ext-sched}
    23702371
    23712372\centering
    23722373
    2373 \captionof{table}{External scheduling comparison (nanoseconds)}
     2374\captionof{table}{External-scheduling comparison (nanoseconds)}
    23742375\label{tab:ext-sched}
    23752376\bigskip
     
    23782379\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} &\multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\
    23792380\hline
    2380 \uC @_Accept@                           & 358           & 359.11        & 2.53  \\
    2381 \CFA @waitfor@, 1 @monitor@     & 359           & 360.93        & 4.07  \\
    2382 \CFA @waitfor@, 2 @monitor@     & 450           & 449.39        & 6.62  \\
    2383 \CFA @waitfor@, 4 @monitor@     & 652           & 655.64        & 7.73 \\
     2381\uC @_Accept@                           & 350           & 350.61        & 3.11  \\
     2382\CFA @waitfor@, 1 @monitor@     & 358.5         & 358.36        & 3.82  \\
     2383\CFA @waitfor@, 2 @monitor@     & 422           & 426.79        & 7.95  \\
     2384\CFA @waitfor@, 4 @monitor@     & 579.5         & 585.46        & 11.25 \\
    23842385\hline
    23852386\end{tabular}
     
    23972398}
    23982399\end{cfa}
    2399 \captionof{figure}{\CFA object creation benchmark}
     2400\captionof{figure}{\CFA object-creation benchmark}
    24002401\label{f:creation}
    24012402
     
    24102411\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} & \multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\
    24112412\hline
    2412 Pthreads                                & 28091         & 28073.39      & 163.1  \\
    2413 \CFA Coroutine Lazy             & 6                     & 6.07          & 0.26   \\
    2414 \CFA Coroutine Eager    & 520           & 520.61        & 2.04   \\
    2415 \CFA Thread                             & 2032  & 2016.29       & 112.07  \\
    2416 \uC Coroutine                   & 106           & 107.36        & 1.47   \\
    2417 \uC Thread                              & 536.5 & 537.07        & 4.64   \\
    2418 Goroutine                               & 3103  & 3086.29       & 90.25  \\
    2419 Java Thread                             & 103416.5      & 103732.29     & 1137 \\
     2413Pthreads                                & 26996         & 26984.71      & 156.6  \\
     2414\CFA Coroutine Lazy             & 6                     & 5.71          & 0.45   \\
     2415\CFA Coroutine Eager    & 708           & 706.68        & 4.82   \\
     2416\CFA Thread                             & 1173.5        & 1176.18       & 15.18  \\
     2417\uC Coroutine                   & 109           & 107.46        & 1.74   \\
     2418\uC Thread                              & 526           & 530.89        & 9.73   \\
     2419Goroutine                               & 2520.5        & 2530.93       & 61.56  \\
     2420Java Thread                             & 91114.5       & 92272.79      & 961.58 \\
    24202421\hline
    24212422\end{tabular}
Note: See TracChangeset for help on using the changeset viewer.