March 2012 - Triton-commits - mailman3.cels.anl.gov

Triton-private Repository branch, master, updated. d85b33448e54d0ac8f38bc71b03d4753d83dc8d3
by noreply＠mcs.anl.gov 05 Mar '12

05 Mar '12

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Triton-private Repository". The branch, master has been updated via d85b33448e54d0ac8f38bc71b03d4753d83dc8d3 (commit) via ac260f8ca67f57b691a8f3eea42d562706bbf769 (commit) from e8b5bb860e45d135b45133cfae137dca1071f2f3 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit d85b33448e54d0ac8f38bc71b03d4753d83dc8d3 Author: Phil Carns <carns(a)mcs.anl.gov> Date: Mon Mar 5 11:30:43 2012 -0500 edits and some comments on context/related text commit ac260f8ca67f57b691a8f3eea42d562706bbf769 Author: Phil Carns <carns(a)mcs.anl.gov> Date: Mon Mar 5 11:21:43 2012 -0500 minor edit: figure 1 shows a write, not a read ----------------------------------------------------------------------- Summary of changes: papers/2011/aesop/context.tex | 16 ++++++++++++++-- papers/2011/aesop/related.tex | 5 +---- 2 files changed, 15 insertions(+), 6 deletions(-) Diff of changes: diff --git a/papers/2011/aesop/context.tex b/papers/2011/aesop/context.tex index 7a6aa13..8aadf86 100644 --- a/papers/2011/aesop/context.tex +++ b/papers/2011/aesop/context.tex @@ -72,8 +72,8 @@ Consider the file server diagrammed in Figure~\ref{fig:sm}. The operation starts when the client issues a call to the server, triggering the top receive. The server then simultaneously issues four concurrent operations: 1) a non-blocking send to peer server to -request user data from a replica, 2) a non-blocking receive to accept -the response from the peer server, 3) a timer call to time +forward data to a replica, 2) a non-blocking receive to accept +the response from the replica server, 3) a timer call to time the whole operation and perform a timeout if necessary, and 4) a sequence of metadata operations. Finally, when all four operations complete, the result is posted to the client. @@ -219,6 +219,12 @@ send/receive and one-sided put/get communication. MPI-2~\cite{gropp1999ump,snir1995mcr} offers non-blocking messaging calls for point-to-point communication. +\color{red}PHC: the following paragraph needs some work. You can't actually +use select, poll, or epoll on files in practice. Maybe just cut all of that +and just point out the POSIX AIO stuff? There are other async disk I/O +libraries, but none of them are widely used and portable so I don't know +that they are worth mentioning.\color{black} + Disk operations also have a wide range of non-blocking access methods. Unix systems have traditionally offered the select/poll paradigm, in which file descriptors are collected into a data structure; the @@ -278,6 +284,12 @@ state machines instances can be active simultaneously, allowing PVFS to track the state of an arbitrary number of concurrent requests and make progress on them without the overhead of explicit threading. +\color{red}PHC: I think it would be appropriate here to point out that the +PVFS state machines are really just a framework for event-driven +programming, and as such suffers from the general limitations of the +event-driven model, including "...." Keep most of the below text, just spin +a little differently.\color{black} + This state machine architecture has proved successful in achieving high performance in large-scale production HPC environments~\cite{pvfs-bgp-sc09}, but it poses a number of problems diff --git a/papers/2011/aesop/related.tex b/papers/2011/aesop/related.tex index 1f8a70e..886d698 100644 --- a/papers/2011/aesop/related.tex +++ b/papers/2011/aesop/related.tex @@ -32,11 +32,8 @@ If the tasks block on device activity, then it may instantiate a larger number of threads. The primary advantages of GCD are that it simplifies multi-threaded programming and automatically adjusts concurrency according to the workload and the system architecture. Unlike \aesop, however, GCD -always uses threads to achieve concurrency and provides no framework for +always uses threads to achieve concurrency and provides no general framework for integration with device API's that provide more scalable asynchronous interfaces. -\color{red} Clarify this. You can use events (like timers and fd changes) -to trigger queued code blocks, but this gets you back to an event-driven -model.\color{black} In addition to programming models and languages, a number of support libraries have also been developed to aid in portably managing a large hooks/post-receive -- Triton-private Repository

1 0

Triton-private Repository branch, master, updated. e8b5bb860e45d135b45133cfae137dca1071f2f3
by noreply＠mcs.anl.gov 05 Mar '12

05 Mar '12

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Triton-private Repository". The branch, master has been updated via e8b5bb860e45d135b45133cfae137dca1071f2f3 (commit) from 35ea611a5c4239d0daa62f3e8608fe8fbacbaa33 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit e8b5bb860e45d135b45133cfae137dca1071f2f3 Author: Phil Carns <carns(a)mcs.anl.gov> Date: Mon Mar 5 11:20:12 2012 -0500 minor edits to intro ----------------------------------------------------------------------- Summary of changes: papers/2011/aesop/intro.tex | 18 +++++++++++------- 1 files changed, 11 insertions(+), 7 deletions(-) Diff of changes: diff --git a/papers/2011/aesop/intro.tex b/papers/2011/aesop/intro.tex index c520c3f..8c04208 100644 --- a/papers/2011/aesop/intro.tex +++ b/papers/2011/aesop/intro.tex @@ -39,21 +39,21 @@ loops~\cite{memcached-threads}. Multithreading is popular for several reasons. First and foremost, this model is widely used and therefore well understood in the development community. -It produces a natural, readable control flow in algorithm implementations -because each thread can execute sequentially and issue simple blocking -device operations. Threads also provide a clear, deterministic model +It produces a natural control flow in algorithm implementations +because each thread executes sequentially and issues simple blocking +device operations. Threads also provide a clear model to express concurrency. There are a number of challenges to building a multi-threaded service, however. The first is that it is not always intuitive how to best provision thread resources; threads can be assigned per client, per request, or per underlying device operation, and they may be allocated on demand or from an existing pool. Each technique or combination of techniques presents tradeoffs in scalability, performance, -and readability, yet it is often difficult to transition between them +and readability, yet it is difficult to transition between them during the development process. The second challenge is the disconnect between the number of threads needed to express logical concurrency and the number of threads needed to make optimal use of local resources. For example, even if there -are 1,000 client requests in flight at once, the server may only have a few +are 1,000 client requests in flight at once, the server may have only a few processing cores and a storage device that can only effectively handle a few operations at a time. This disconnect can cause a seemingly simple thread model to evolve into a more @@ -80,7 +80,7 @@ generalized. This makes it difficult to verify dependencies or perform type checking between states. Pure event-driven models also do not directly address the requirement of multi-core architectures or high performance peripherals that must use multiple threads to achieve maximize throughput. -Event-driven servers may therefore evolve during the development process to take on +Event-driven servers therefore tend to evolve during the development process to take on characteristics of both event-driven and multithreaded services in order to compensate for these issues. @@ -104,7 +104,11 @@ tuned to match different system architectures, different device APIs, and different workloads without any change to the core system software algorithms. Unlike event-driven architectures, the \aesop extensions also preserve readable control flow regardless of how many steps or -concurrent devices are utilized in a given algorithm. +concurrent devices are utilized in a given algorithm. Aesop also offers +functionality that is simply not available in a traditional multithreaded or +event-driven framework, including the ability to mark variables as being +shared or private across concurrent execution paths as well as a robust +mechanism to cancel concurrent execution paths. \todo{Fill this in:} hooks/post-receive -- Triton-private Repository

1 0

Triton-private Repository branch, master, updated. 35ea611a5c4239d0daa62f3e8608fe8fbacbaa33
by noreply＠mcs.anl.gov 05 Mar '12

05 Mar '12

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Triton-private Repository". The branch, master has been updated via 35ea611a5c4239d0daa62f3e8608fe8fbacbaa33 (commit) from 8830309377545a0b0c8f32aaad7e3bdb938ecdef (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit 35ea611a5c4239d0daa62f3e8608fe8fbacbaa33 Author: Kevin Harms <harms(a)alcf.anl.gov> Date: Mon Mar 5 01:58:55 2012 -0600 Latex fixes for aesop paper ----------------------------------------------------------------------- Summary of changes: papers/2011/aesop/aesop.bib | 2 +- papers/2011/aesop/aesop.tex | 2 +- papers/2011/aesop/evaluation.tex | 38 +++++++++++++++++++------------------- 3 files changed, 21 insertions(+), 21 deletions(-) Diff of changes: diff --git a/papers/2011/aesop/aesop.bib b/papers/2011/aesop/aesop.bib index 28c7f5c..582c92e 100644 --- a/papers/2011/aesop/aesop.bib +++ b/papers/2011/aesop/aesop.bib @@ -339,7 +339,7 @@ year = 2008 @INPROCEEDINGS{mccabe, author = {McCabe, T.J}, title = {A Complexity Measure}, - booktitle = {IEEE Transactions on Software Engineering, vol.SE-2, no.4} + booktitle = {IEEE Transactions on Software Engineering, vol.SE-2, no.4}, year = {1976}, } @Comment pages = {308--320}, diff --git a/papers/2011/aesop/aesop.tex b/papers/2011/aesop/aesop.tex index 771bc5c..05a3d96 100644 --- a/papers/2011/aesop/aesop.tex +++ b/papers/2011/aesop/aesop.tex @@ -7,7 +7,7 @@ \usepackage{listing} \usepackage{hyperref} \usepackage{listings} -\usepackage{subfig} +\usepackage{subfigure} \usepackage{xspace} \graphicspath{{./}} diff --git a/papers/2011/aesop/evaluation.tex b/papers/2011/aesop/evaluation.tex index c8b185d..179118f 100644 --- a/papers/2011/aesop/evaluation.tex +++ b/papers/2011/aesop/evaluation.tex @@ -164,7 +164,7 @@ used for the clients. We scaled the clients from 16 (1 node) to 1024 (64 nodes). \subsection{Runtime Efficiency} -Figure~\subref{fig:writehist} shows the overall run time of the concurrent write +Figure~\ref{fig:write} shows the overall run time of the concurrent write workload for each server implementation as the number of client processes is scaled from 16 to 1024. In this graph we see that {aesop} does not perform as well as the other servers for small workloads (taking 3.2 @@ -173,7 +173,7 @@ server). However, {aesop} is the fastest server at the largest scale (taking 119.8 seconds verses 130.8 seconds for the nearest competitors in thread-per-client and thread-per-client-nb). -Figure~\subref{fig:readhist} shows the results of the read experiment. +Figure~\ref{fig:read} shows the results of the read experiment. Aesop performs more favorably at small scale for this workload than in the previously shown write workload. At the largest scale, Aesop completes the test in 48.3 seconds verses 46.1 seconds for the fastest server (thread-pool). @@ -188,8 +188,8 @@ in terms of its relative performance. Aesop is competitive with (and in most cases better than) the other implementations except for the thread-per-client server in both the -write-null (Figure~\subref{fig:writenull}) and read-null -(Figure~\subref{fig:readnull}) evaluation. We were unable to +write-null (Figure~\ref{fig:writenull}) and read-null +(Figure~\ref{fig:readnull}) evaluation. We were unable to isolate a concrete reason for this discrepancy in profiling. One notable difference in the two implementations, however, is that the thread-per-client server uses blocking socket operations, while the Aesop @@ -211,26 +211,26 @@ section that poor Aesop performance at small scale is likely a tuning flaw in the file resource used in the Aesop standard library, rather than a fundamental programming language problem. -\begin{figure}[t] +\begin{figure}[ht] \centering \subfigure[Read performance]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/read-hist.pdf} - \label{fig:read-hist} + \label{fig:read} } \subfigure[Write performance]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/write-hist.pdf} - \label{fig:write-hist} + \label{fig:write} } \subfigure[Read-null performance]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/read-null-hist.pdf} - \label{fig:read-null-hist} + \label{fig:readnull} } \subfigure[Write-null performance]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/write-null-hist.pdf} - \label{fig:write-null-hist} + \label{fig:writenull} } \end{figure} @@ -241,22 +241,15 @@ the minimum and maximum latency, the first quartile latency and third quartile latency. The box represents the first and third quartiles and the whiskers are the minimum and maximum values. The following results are for the 1024 client size selected from the same iteration as the maximum runtime -graphs. Figure~\subref{fig:writelat} shows Aesop offers vary comparative +graphs. Figure~\ref{fig:writelat} shows Aesop offers vary comparative latency performance as the other configurations and only notably thread-per-op and event are significantly worse. The relative latency metrics are similar for the other test cases. \begin{figure}[t] \centering - \subfigure[Write memory usage]{ - \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/write-mem.pdf} - \label{fig:write-mem} - } - - \subfigure[Write Latency]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/write-lat.pdf} - \label{fig:write-lat} - } + \caption{Write latency\label{fig:writelat}} \end{figure} \subsection{Memory Efficiency} @@ -270,7 +263,7 @@ server when the client test was completed. The VmHWM stat is a Linux-specific metric that represents the peak resident set size (RSS) of an executable, where RSS corresponds to the amount of paged-in memory used by the executable. -In Figure~\subref{fig:writemem} we see that thread-pool limits the +In Figure~\ref{fig:writemem} we see that thread-pool limits the memory usage as the client work load increases because the thread-pool by design limits the number of requests that can be in progress at once. The other server implementations scale as the number of clients increase. @@ -283,6 +276,12 @@ as the resident memory seems to be a more relevant metric in practice. Again, the memory usage graphs for the other test cases are similar to those shown in the write test case. +\begin{figure}[t] + \centering + \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/write-mem.pdf} + \caption{Write memory usage \label{fig:writemem}} +\end{figure} + \subsection{Productivity} \begin{table} @@ -463,5 +462,6 @@ the timeout is reached. Listing~\ref{lst:timeout} shows an example. The same effect is not easily achieved using the event or threaded models, since neither model offers any help in cancelling an outstanding call. +\color{black} % hooks/post-receive -- Triton-private Repository

1 0

Triton-private Repository branch, master, updated. 8830309377545a0b0c8f32aaad7e3bdb938ecdef
by noreply＠mcs.anl.gov 05 Mar '12

05 Mar '12

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Triton-private Repository". The branch, master has been updated via 8830309377545a0b0c8f32aaad7e3bdb938ecdef (commit) from add9c7990d7c643190ba76fc4aa8ccc4a2ddacca (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit 8830309377545a0b0c8f32aaad7e3bdb938ecdef Author: Kevin Harms <harms(a)harms-macbook.local> Date: Mon Mar 5 01:44:59 2012 -0600 Updates to eval section of aesop paper, bringing content from aesop performance document. ----------------------------------------------------------------------- Summary of changes: papers/2011/aesop/aesop.bib | 26 +++ papers/2011/aesop/evaluation.tex | 357 ++++++++++++++++++++++++++------------ 2 files changed, 271 insertions(+), 112 deletions(-) Diff of changes: diff --git a/papers/2011/aesop/aesop.bib b/papers/2011/aesop/aesop.bib index 32f5ca5..28c7f5c 100644 --- a/papers/2011/aesop/aesop.bib +++ b/papers/2011/aesop/aesop.bib @@ -330,6 +330,32 @@ year = 2008 howpublished = {http://code.sixapart.com/svn/memcached/trunk/server/doc/threads.txt} } +@MISC{hp-cond-variable, + author = {Hewlet Packard Development Company L.P}, + title = {Techniques for Improving the Scalability of Applications Using POSIX Thread Condition Variables.}, + howpublished = {http://h21007.www2.hp.com/portal/download/files/unprot/hpux/MakingConditionVariablesPerform.pdf} +} + +@INPROCEEDINGS{mccabe, + author = {McCabe, T.J}, + title = {A Complexity Measure}, + booktitle = {IEEE Transactions on Software Engineering, vol.SE-2, no.4} + year = {1976}, +} + @Comment pages = {308--320}, + +@MISC{pmccabe, + author = {Paul Bame}, + title = {pmccabe}, + howpublished = {http://parisc-linux.org/~bame/pmccabe/} +} + +@MISC{sloccount, + author = {David A. Wheeler}, + title = {sloccount}, + howpublished = {http://www.dwheeler.com/sloc/} +} + @INPROCEEDINGS{BDB_1999, author = {Olson, Michael A. and Bostic, Keith and Seltzer, Margo}, title = {Berkeley DB}, diff --git a/papers/2011/aesop/evaluation.tex b/papers/2011/aesop/evaluation.tex index e2d14ba..c8b185d 100644 --- a/papers/2011/aesop/evaluation.tex +++ b/papers/2011/aesop/evaluation.tex @@ -1,159 +1,288 @@ -In this paper we evaluate Aesop based on two criteria, runtime efficiency -and progammer productivity. +In this paper we evaluate Aesop based on three criteria, runtime efficiency, +memory efficiency and progammer productivity. + +\subsection{Experiment} + +To evaluate the aesop we created a comparison of different server +implementations. We designed a simple server that uses TCP messaging. +The server recieves requests from a client, sends or recieves +a payload, and then sends an acknowledgement. +The paylod can be generated or discarded, read from a file or written to a file. + +Each of the example servers used for comparison in this document implement +an identical request protocol and are therefore evaluated using the same +client test harness. The client is a basic C program that uses TCP sockets +to send messages to the server. It uses MPI to coordinate processes and +generate a highly concurrent workload. + +The client will execute in a loop generating a specified number of +operations to the server. The general flow is that each client process sends +a request to the server that contains an optional payload. The client then +waits for the server to send an acknowledgment that also contains an +optional payload. + +Each client records the total amount of time taken to execute its workload +(beginning before the initial connection and ending after receipt of the last +acknowledgment). The time taken by the slowest client is reported as the +aggregate run time. Each client also records the time needed to service each +individual request (from before the request is sent until after the +acknowledgment is received) in order to calculate statistics about +individual request latencies. -\subsection{Runtime Efficiency} +\subsubsection{Experiment - Test Cases} -To evaluate the runtime effiecency of aesop we created a comparison of a -server implementations. We selected a simple test case to examine concurrency -within a server. We designed a simple server that uses TCP messaging. -The server recieves requests from a client, sends or recieves a payload, -and then sends an acknowledgement. The paylod can be generated or discarded, -read from a file or written to a file. +There are four distinct test cases run against each server implementation. +All file I/O is done using O\_DIRECT file access mode in order to bypass the +Linux buffer cache and ensure that disk is involved in each I/O transfer. +The number of requests and size of request were chosen to keep the +total runtime of each test case reasonable. -The client is an MPI program which allows launching an arbitrary number of -client instancess and coordinates startup. MPI is used for synchronization -on startup and commmunication of results, the core client program only uses -sockets for communication with the server. +\paragraph*{Read} -\subsubsection{Experiment - Test Types} +The client sends a request with a file name and a size. The server will +then open the file, read the contents up to the size specified. The server +returns the data with the acknowledgement of the operation. -We developed six versions of the server: Aesop, Thread-per-client, -Thread-per-client using non-blocking sockets, Thread-per-operation, -Thread-pool and Event. Each server is setup to report the VmHWM stat when -the application exits. +The read test had clients each issue 16 requests asking for 4 KiB from +disk. Each client specifies a unique file to be read on each request. All +clients specify unique files. The files are first generated by a script +before the tes truns. -\paragraph*{Aesop} +\paragraph*{Write} -The aesop server uses a 'lonely pbranch' to service each client. The underlying -configuration of aesop was using a thread-pool with 16 threads to to handle -network requests and a thread-pool with 4 threads to handle disk operations. +The client sends a request with a file name, size and payload. The server +will then create the file and write the payload. The server then sends an +acknowledgement to the client. -\paragraph*{Thread-per-client} +The write test has clients each issue 16 requests sending 4 KiB of data to +be written to disk. Each client specifies a unique file name for each +request and all clients specify unique files from each other. The directory +containing all the files is deleted between each test iteration. -The thread-per-client server spawns a thread for each client connection. -All requests for each client are handled within that thread. Network and -disk operations all use blocking calls. +\paragraph*{Read-null} -\paragraph*{Thread-per-client-nb} +The read-null test is identical to the read request, except that the +server sends uninitialized data rather than performing any file I/O. The +server allocates a buffer for the response based on the size the client +requested. -The thread-per-client-nb server is the same implementation as the -thread-per-client model but uses non-blocking sockets for network operations. +The read-null test had clients each issue 4096 requests requesting 4 KiB of +data to be returned from the server. -\paragraph*{Thread-per-operation} +\paragraph*{Write-null} -The thread-per-operation server uses an event loop to watch all sockets and then -spawns a thread to handle each request. The request for network and disk -operations are handled in the same thread. +The write-null test is identical to the write request, except that the +server discards incoming data rather than performing any file I/O. The +server will still send an acknowledgement to the client. -\paragraph*{Thread-pool} +The write test had clients each issue 4096 sending 4 KiB of data to be +discarded by the server. -The thread-pool server uses an event loop to watch all sockets for activity -and then puts the request on a queue for it to be handled by a thread within -the thread pool. The request for network and disk operations are handled in -the same thread. +\subsubsection{Experiment - Server Types} -\paragraph*{Event} +We implemented the same request protocol in multiple server daemons +in order to contrast different approaches to concurrent +request processing. Each server uses the same fundamental coding style to +the degree possible. One server is implemented using the Aesop language, +while all other servers are implemented in C. The pthread library was +used in all cases that required explicit threading, while the +libev~\ref{libev-web} library was used in all cases that required an +explicit event loop. -The event server uses a event loop to watch all sockets and handles all -network and disk operations occurs as callbacks from the event loop. The -event model uses on a single thread. +Each server is setup to report the VmHWM stat when the application exits. -All of the event loop implementations use libev [ref]. +\paragraph*{Aesop} -\subsubsection{Experiment - Test Cases} +The Aesop server is implemented in the Aesop programming language. The server +uses a 'lonely pbranch' to service each client. All operations for a client +are handled within a single pbranch. The socket nd file operations are +performed with blocking Aesop function that are provided by the Aesop +standard library. The underlying socket resource uses non-blocking sockets +with a thread pool of 12 threads. The file resource uses synchronous IO and +a thread pool with 4 threads. -Four sepearte tests were run again each server type: read, write, read-null -and write-null. +\paragraph*{Thread-per-client} -The client and server connect over Infiniband using IPoIB. The number of -requests and size of requests were chosen to keep the total runtime of the -test cases reasonable. +The thread-per-client server spawns a thread for each client connection. +All requests for a given client are handled within the same thread. This model +uses blocking socket operations and standard file read and write operations. +Each thread executes until the corresponding client disconnects. -\paragraph*{Read} +\paragraph*{Thread-per-client-nb} -The read test case reads data off of the local scratch disk on each compute -node. The request specifies which file to read and the data is returned in -the acknoledgement. The data is read using O\_DIRECT mode in order to -bypass file caching. The test starts by first generating a set of files -(1 file per client per request) for each client to read, which are used -for all six test types. Each client issues sixteen requests of 4096 bytes. +The thread-per-client-nb server is identical to the thread-per-client +server, except that is uses non-blocking socket calls in place of blocking +socket calls. For example, in order to send a message, a thread will +perform non-blocking sends until it encounters the EWOULDBLOCK error code. +It then polls the socket until it is ready and continues sending data. +We implemented this version to investigate the possible performance difference +between the synchronous and asynchronous socket calls in a scenario where +all other factors are held constant. -\paragraph*{Write} +\paragraph*{Thread-per-operation} -The write test case writes data from the client to the disk. The server sends -and acknowledgement after the write completes. Each write request -involves creating a new file on local disk. The data is written using O\_DIRECT -mode in order to bypass file caching. The files created are deleted between -each test type execution. Each client issues sixteen requests of 4096 bytes. +The thread-per-operation server uses an event loop to watch all sockets for +activity. When a new request is available, a thread is spawned and the request +is handled completely from within that thread. When the request is complete +the thread is destroyed. Blocking socket operations and standard file read +and write functions are used in this implementation. -\paragraph*{Read-null} +\paragraph*{Thread-pool} -The read-null test case has the server return a generated chunk of data -for each client request. The data is returned with the acknowledgement. -Each client issues 4096 requests for 4096 bytes of data. +The thread-pool server uses an event loop to watch all sockets for activity. +When a new request is available, the event loop puts the request on a queue and +wakes up a thread from the thread pool. The request is handled completely +from within a single thread of the thread pool. Blocking sockets and +standard file read and write functions are used in this implementation. The +thread pool was implemented following best practices for scalable condition +variable performance as described in \cite{hp-cond-variable}. -\paragraph*{Write-null} +\paragraph*{Event} -The write-null test case has the client send a payload but then the server -simple discards the data and returns an acknowledgement. Each client issues -4096 requests and send a payload of 4096 bytes of data. +The event server uses an event loop not only to detect incoming requests, +but to service them as well. Each request processing step is executed from +an event loop callback function. The event server uses non-blocking sockets +and asynchronous file I/O. Note that although this implementation does not +use any explicit threads, the operating system can still use multiple cores +to drive both the network and disk. \subsubsection{Experiment - Test System} -The experiment was run on the Argonne Lcaboratory Computing Resource Center -(LCRC) Fusion cluster. Fusion is an IBM iDataPlex dx360 M2 system which has -320 nodes. Each compute node contains two Intel Nehalem 2.6 GH Xeon -processors with a total of 36 GB of RAM. The cluster has Infinband QDR -interconnect. Each compute node also contains a local scratch space which -is a single SATA 7200 RPM hard disk. +All experiments were executed on the Fusion cluster managed by +the Argonne Laboratory Computing Resource Center +(LCRC). Fusion is a IBM iDataPlex dx360 M2 system. It features 320 compute +nodes which each consist of two Intel Nehalem 2.6 GHz Xeon processors and 36 GB +of RAM. The compute nodes have hyper threading disabled. The cluster has +an InfiniBand QDR interconnect. Each compute node also a single SATA 7200 RPM +hard disk for local scratch storage. All disk IO was performed using the +local scratch storage and client/server communication was done over the +IB network using IPoIB. -\subsubsection{Experiment - Results} +We executed 16 clients processes per phyiscal node. The tests were executed +on 65 nodes. One node was used for the server and the other 64 nodes were +used for the clients. We scaled the clients from 16 (1 node) to 1024 (64 nodes). -Aesop's runtime effiecency compares reasonably to the other hand-coded server -types. The thead-per-client test was the fastest method in all four test -cases. The thread-per-client-nb test type was contructed to examine the -performance difference between blocking and non-blocking socket operations. -Aesop uses non-blocking socket operations so this test case is a better -comparison between aesop and a hand tuned server. +\subsection{Runtime Efficiency} -% use subfigure for performance graphs +Figure~\subref{fig:writehist} shows the overall run time of the concurrent write +workload for each server implementation as the number of client processes +is scaled from 16 to 1024. In this graph we see that {aesop} does not +perform as well as the other servers for small workloads (taking 3.2 +seconds at the smallest scale, verses 1.9 seconds for the thread-per-op +server). However, {aesop} is the fastest server at the largest scale +(taking 119.8 seconds verses 130.8 seconds for the nearest competitors +in thread-per-client and thread-per-client-nb). + +Figure~\subref{fig:readhist} shows the results of the read experiment. +Aesop performs more favorably at small scale for this workload than in the +previously shown write workload. At the largest scale, Aesop completes the +test in 48.3 seconds verses 46.1 seconds for the fastest server (thread-pool). +The event server performs particularly poorly in all cases, ultimately +running the largest scale test in 77.2 seconds. + +The small scale results for Aesop may indicate that additional tuning +is needed to improve latency for small test runs. The issue is likely +isolated to the write path of the file I/O resource in the Aesop standard +library, as we see asymmetric results in the read and write tests for Aesop +in terms of its relative performance. + +Aesop is competitive with (and in most cases better than) the other +implementations except for the thread-per-client server in both the +write-null (Figure~\subref{fig:writenull}) and read-null +(Figure~\subref{fig:readnull}) evaluation. We were unable to +isolate a concrete reason for this discrepancy in profiling. One notable +difference in the two implementations, however, is that the +thread-per-client server uses blocking socket operations, while the Aesop +socket resource uses non-blocking operations. Based on this observation, +we implemented the +thread-per-client-nb server to isolate the impact of non-blocking socket +operations on performance. The thread-per-client-nb implementation is +identical to the thread-per-client implementation except that each socket +uses non-blocking operations and polling to transmit and receive data. As +seen in these tests, the use of non-blocking operations slows down the +thread-per-client server to the point that it is practically equivalent to +the Aesop server at scale. + +Another notable observation in these graphs is that the Aesop server is +competitive at small scale, and in fact is the fastest implementation in the +16 client process read-null test and nearly the fastest in the 16 client +process write-null test. This supports the observation from the previous +section that poor Aesop performance at small scale is likely a tuning flaw +in the file resource used in the Aesop standard library, rather than a +fundamental programming language problem. \begin{figure}[t] \centering + \subfigure[Read performance]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/read-hist.pdf} - \caption{Read performance \label{fig:read-hist}} -\end{figure} + \label{fig:read-hist} + } -\begin{figure}[t] - \centering + \subfigure[Write performance]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/write-hist.pdf} - \caption{Write performance \label{fig:write-hist}} -\end{figure} + \label{fig:write-hist} + } -\begin{figure}[t] - \centering + \subfigure[Read-null performance]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/read-null-hist.pdf} - \caption{Read-null performance \label{fig:read-null-hist}} -\end{figure} + \label{fig:read-null-hist} + } -\begin{figure}[t] - \centering + \subfigure[Write-null performance]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/write-null-hist.pdf} - \caption{Write-null performance \label{fig:write-null-hist}} + \label{fig:write-null-hist} + } \end{figure} +\subsubsection{Latency} + +The client measures the latency of each individual request and then computes +the minimum and maximum latency, the first quartile latency and third +quartile latency. The box represents the first and third quartiles and the +whiskers are the minimum and maximum values. The following results are for +the 1024 client size selected from the same iteration as the maximum runtime +graphs. Figure~\subref{fig:writelat} shows Aesop offers vary comparative +latency performance as the other configurations and only notably +thread-per-op and event are significantly worse. The relative latency metrics +are similar for the other test cases. + \begin{figure}[t] \centering + \subfigure[Write memory usage]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/write-mem.pdf} - \caption{Write memory usage \label{fig:write-mem}} -\end{figure} + \label{fig:write-mem} + } -\begin{figure}[t] - \centering + \subfigure[Write Latency]{ \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/write-lat.pdf} - \caption{Write Latency \label{fig:write-lat}} + \label{fig:write-lat} + } \end{figure} +\subsection{Memory Efficiency} + +Another aspect of the overall performance is the memory efficiency of each +server implementation. In this section we compare Aesop to the other server +implementations using the same runtime performance experitment. +The memory utilization of each server implementation was captured during +the runtime performance experiments. We recorded the VmHWM stat from the +server when the client test was completed. The VmHWM stat is a Linux-specific +metric that represents the peak resident set size (RSS) of an executable, +where RSS corresponds to the amount of paged-in memory used by the executable. + +In Figure~\subref{fig:writemem} we see that thread-pool limits the +memory usage as the client work load increases because the thread-pool +by design limits the number of requests that can be in progress at once. The +other server implementations scale as the number of clients increase. +Although the Aesop server cannot match the thread-pool server in terms of +memory usage, it does compare favorably to the thread-per-client and +thread-per op servers. Note that the thread-per-client and thread-per-op +models consume virtual memory at a much larger rate due to the number of +thread stacks allocated. We chose not to evaluate this metric, however, +as the resident memory seems to be a more relevant metric in practice. Again, +the memory usage graphs for the other test cases are similar to those shown +in the write test case. + \subsection{Productivity} \begin{table} @@ -164,10 +293,12 @@ comparison between aesop and a hand tuned server. \hline & CC & mod. CC & SLOC \\ \hline -aesop & 15 & 10 & 171 \\ -thread & 17 & 12 & 179 \\ -thread pool & 29 & 23 & 292 \\ -event & 26 & 21 & 328 \\ +aesop & 16 & 11 & 179 \\ +thread-per-client & 17 & 12 & 182 \\ +thread-per-client-nb & 17 & 12 & 184 \\ +thread-per-op & 22 & 17 & 249 \\ +thread-pool & 32 & 26 & 313 \\ +event & 28 & 23 & 341 \\ \hline \end{tabular} \label{tab:complexity} @@ -176,11 +307,13 @@ event & 26 & 21 & 328 \\ \vspace{-.2in} \end{table} -\color{red} -Table~\ref{tab:complexity} compares the code complexity of each -implemenation using McCabe Cyclomatic Complexity (CC), Modified McCabe Cyclomatic -Complexity (mod. CC), and Source Linex of Code (SLOC). TODO: reference the -metrics and the tools that we used to collect them (pmccabe and sloccount). +Table~\ref{tab:complexity} compares the code complexity of each server +implemenation using McCabe Cyclomatic Complexity (CC) \ref{mccabe}, +Modified McCabe Cyclomatic Complexity (mod. CC), and +Source Lines of Code (SLOC). The CC and Mod. CC metrics were measured +using the pmccabe tool, version 2.6, created by Paul Bame \ref{pmccabe}, +while the SLOC metrics were measured using the sloccount tool, +version 2.26, created by David A. Wheeler \ref{sloccount}. To simplify the comparison, all four servers had no error handling except for assertions on expected return codes. The protocol definition (ie, @@ -200,6 +333,7 @@ operation requires 5 disconnected event handlers. So although the event model appears less complex according to CC and mod. CC, qualitatively it is significantly more challenging to develop. +\color{red} \begin{figure}[t] \center \begin{minipage}[b]{.47\textwidth} @@ -307,7 +441,6 @@ __blocking void handleConnection (int fd) \end{minipage} \end{figure} - The aesop code (listing~\ref{lst:aesop}) strongly resembles the threaded code. Instead of creating a thread, a lonely pbranch is used to make sure new connections can be accepted even though the previous connection is still being hooks/post-receive -- Triton-private Repository

1 0

Triton-private Repository branch, master, updated. add9c7990d7c643190ba76fc4aa8ccc4a2ddacca
by noreply＠mcs.anl.gov 01 Mar '12

01 Mar '12

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Triton-private Repository". The branch, master has been updated via add9c7990d7c643190ba76fc4aa8ccc4a2ddacca (commit) from b20f8980e7aacc16b30df9a9f22156f61c0b9851 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit add9c7990d7c643190ba76fc4aa8ccc4a2ddacca Author: Dries Kimpe <dkimpe(a)mcs.anl.gov> Date: Thu Mar 1 23:14:16 2012 -0600 Make sure figures are built ----------------------------------------------------------------------- Summary of changes: papers/2011/aesop/Makefile | 6 +++++- 1 files changed, 5 insertions(+), 1 deletions(-) Diff of changes: diff --git a/papers/2011/aesop/Makefile b/papers/2011/aesop/Makefile index a68bcd4..44199d9 100644 --- a/papers/2011/aesop/Makefile +++ b/papers/2011/aesop/Makefile @@ -7,7 +7,11 @@ all: $(BASEPDF) .phony: dummy dummy: -%.pdf: %.tex dummy +.phony: figures +figures: + make -C fig + +%.pdf: %.tex dummy figures TEXMFOUTPUT=`pwd` rubber -d $< # || (rm $@; exit 1) write_response_test_service_time.eps: fig/write_response_test_service_time.gplt hooks/post-receive -- Triton-private Repository

1 0

Triton-private Repository branch, master, updated. b20f8980e7aacc16b30df9a9f22156f61c0b9851
by noreply＠mcs.anl.gov 01 Mar '12

01 Mar '12

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Triton-private Repository". The branch, master has been updated via b20f8980e7aacc16b30df9a9f22156f61c0b9851 (commit) via 1c83967ce72bbb27891049e7b2980eddf01ecccf (commit) from 3cea60a7d673ee0f6de164bf765fb0d166a0039c (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit b20f8980e7aacc16b30df9a9f22156f61c0b9851 Author: Dries Kimpe <dkimpe(a)mcs.anl.gov> Date: Thu Mar 1 23:10:00 2012 -0600 Rewrote language section commit 1c83967ce72bbb27891049e7b2980eddf01ecccf Author: Dries Kimpe <dkimpe(a)mcs.anl.gov> Date: Wed Feb 29 14:01:51 2012 -0600 Fix for bug with rubber/bibtex and LiveTex 2011 ----------------------------------------------------------------------- Summary of changes: papers/2011/aesop/Makefile | 2 +- papers/2011/aesop/aesop.tex | 63 ++++++++++------- papers/2011/aesop/context.tex | 4 +- papers/2011/aesop/intro.tex | 8 +- papers/2011/aesop/language.tex | 2 +- papers/2011/aesop/model.tex | 152 +++++++++++++++++++++++++++++++++------- papers/2011/aesop/related.tex | 22 +++--- 7 files changed, 180 insertions(+), 73 deletions(-) Diff of changes: diff --git a/papers/2011/aesop/Makefile b/papers/2011/aesop/Makefile index c5aa63e..a68bcd4 100644 --- a/papers/2011/aesop/Makefile +++ b/papers/2011/aesop/Makefile @@ -8,7 +8,7 @@ all: $(BASEPDF) dummy: %.pdf: %.tex dummy - rubber -d $< # || (rm $@; exit 1) + TEXMFOUTPUT=`pwd` rubber -d $< # || (rm $@; exit 1) write_response_test_service_time.eps: fig/write_response_test_service_time.gplt gnuplot $< diff --git a/papers/2011/aesop/aesop.tex b/papers/2011/aesop/aesop.tex index 4c89c32..771bc5c 100644 --- a/papers/2011/aesop/aesop.tex +++ b/papers/2011/aesop/aesop.tex @@ -8,6 +8,7 @@ \usepackage{hyperref} \usepackage{listings} \usepackage{subfig} +\usepackage{xspace} \graphicspath{{./}} \DeclareGraphicsExtensions{.pdf,.jpeg,.png} @@ -32,7 +33,6 @@ basicstyle=\small %\usepackage{wrapfig} %\usepackage{setspace} -%\usepackage{subfigure} % correct bad hyphenation here \hyphenation{op-tical net-works semi-conduc-tor} @@ -42,57 +42,66 @@ basicstyle=\small \newcommand{\todo}[1]{ {\textcolor{red} { TODO: #1 }}} \newcommand{\woz} [1]{ {\textcolor{blue} { Wozniak: #1 }}} + +\makeatletter +\newif\ifsc@active +\newif\ifnf@active +\def\upsc#1{{\sc@activefalse\nf@activetrue\@upsc#1\@nil}} +\def\@upsc#1{\ifx#1\@nil\else\@@upsc{#1}\expandafter\@upsc\fi} +\def\@@upsc#1{% + \ifnum\uccode`#1=`#1\relax + \ifsc@active\else\sc@activetrue\nf@activefalse\scshape\fi + \expandafter\@firstoftwo + \else + \ifsc@active\sc@activefalse\fi + \ifnf@active\else\nf@activetrue\normalfont\fi + \expandafter\@secondoftwo + \fi + {\lowercase{#1}}% + {#1}} +\makeatother + +\newcommand{\aesop}{A\upsc{ESOP}\xspace} + \begin{document} % % paper title % can use linebreaks \\ within to get better formatting as desired % I'd like to get AESOP in the title -\title{Aesop: Expressing Concurrency in High Performance\\System Software} -%% \author{Jason Cope\inst{1} \and Kamil Iskra\inst{1} \and Dries -%% Kimpe\inst{2} \and Robert Ross\inst{1}} - -%% \institute -%% { -%% \small Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL 60439 \\ -%% \and -%% \small Computation Insitute, University of Chicago, Chicago, IL 60637 \\ -%% \{copej,iskra,rross\}(a)mcs.anl.gov, dries(a)uchicago.edu -%% } +\title{\aesop: Expressing Concurrency in \\ High Performance System Software} + + +\author{Dries Kimpe\inst{1} \and Phil Carns\inst{1} \and Kevin Harms\inst{1} +\and Justin Wozniak\inst{1} \and Samuel Lang\inst{1} \and Robert Ross\inst{1}} % author names and affiliations % use a multiple column layout for up to two different % affiliations -\author{\IEEEauthorblockN{Authors Name/s per 1st Affiliation (Author)} -\IEEEauthorblockA{line 1 (of Affiliation): dept. name of organization\\ -line 2: name of organization, acronyms acceptable\\ -line 3: City, Country\\ -line 4: Email: name(a)xyz.com} -\and -\IEEEauthorblockN{Authors Name/s per 2nd Affiliation (Author)} -\IEEEauthorblockA{line 1 (of Affiliation): dept. name of organization\\ -line 2: name of organization, acronyms acceptable\\ -line 3: City, Country\\ -line 4: Email: name(a)xyz.com} +\author{\IEEEauthorblockN{Dries Kimpe, Phil Carns} +\IEEEauthorblockA{Mathematics and Computer Science Division\\ +Argonne National Laboratory\\ +Argonne, IL 60439\\ +\{dkimpe,carns,harns,wozniak,lang,rross\}(a)mcs.anl.gov} } % make the title area \maketitle \begin{abstract} -This paper describes Aesop, a new programming language and programming +This paper describes \aesop, a new programming language and programming model designed to implement distributed system software with high development productivity while maintining -run time efficiency. Aesop is implemented as a source-to-source compiler +run time efficiency. \aesop is implemented as a source-to-source compiler that extends the C language with a set of concurrency extensions designed for distributed computing. -We evaluate Aesop by implementing a simple file server and comparing its +We evaluate \aesop by implementing a simple file server and comparing its implementation and performance against traditional thread-based and event-based programming models. -Our work shows that Aesop succeeds in maintaining sequential program flow, +Our work shows that \aesop succeeds in maintaining sequential program flow, while at the same time generating ... \end{abstract} diff --git a/papers/2011/aesop/context.tex b/papers/2011/aesop/context.tex index fd63de6..7a6aa13 100644 --- a/papers/2011/aesop/context.tex +++ b/papers/2011/aesop/context.tex @@ -260,7 +260,7 @@ operation may be accessed. \subsection{PVFS state machines} -The Aesop language described in this work builds upon lessons learned +The \aesop language described in this work builds upon lessons learned from the event-driven state machine model used in the PVFS file system~\cite{pvfs-web}. @@ -301,7 +301,7 @@ making it difficult to reason about many development challenges. These drawbacks introduce a steep learning curve for researchers and a additional maintenance workload for maintainers. In this work, we -demonstrate that Aesop provides the same level of concurrency and +demonstrate that \aesop provides the same level of concurrency and support for asynchronous interfaces as the PVFS state machine engine while allowing file system developers to write their algorithms using a more familiar code organization, and expected concurrency features. diff --git a/papers/2011/aesop/intro.tex b/papers/2011/aesop/intro.tex index 93f1d84..c520c3f 100644 --- a/papers/2011/aesop/intro.tex +++ b/papers/2011/aesop/intro.tex @@ -89,12 +89,12 @@ best concurrent programming model for a given system software project, yet this decision affects every aspect of the design from algorithm implementation to device management. In order to help address this problem, we propose a new programming language and programming model, -Aesop, that targets the software engineering challenges associated +\aesop, that targets the software engineering challenges associated with developing distributed system software. It's goal is to improve programmer productivity and architecture flexibility without compromising the efficiency of large-scale system software. -Aesop is a superset of the C language. It describes blocks of code that +\aesop is a superset of the C language. It describes blocks of code that should be executed asynchronously or concurrently, without dictating whether those routines must be implemented with threads or not, and without dictating the asynchronous progress model to be used by any @@ -102,7 +102,7 @@ underlying devices. Because the core algorithm description is decoupled from these architecture-specific details, the run-time system can be tuned to match different system architectures, different device APIs, and different workloads without any change to the core system software -algorithms. Unlike event-driven architectures, the Aesop extensions +algorithms. Unlike event-driven architectures, the \aesop extensions also preserve readable control flow regardless of how many steps or concurrent devices are utilized in a given algorithm. @@ -112,7 +112,7 @@ The remainder of this paper is organized as follows. In Section~\ref{section:context} we survey challenges in developing concurrent system software and in Section~\ref{section:related} we identify related work in languages and programming models. In section -FOO we present an evaluation that contrasts Aesop with N common +FOO we present an evaluation that contrasts \aesop with N common alternative programming models for the case study of a simple file server. The implementations are compared both in terms of developer productivity and run time performance. Finally in section FOO we diff --git a/papers/2011/aesop/language.tex b/papers/2011/aesop/language.tex index 89e0583..35bf5bc 100644 --- a/papers/2011/aesop/language.tex +++ b/papers/2011/aesop/language.tex @@ -72,6 +72,6 @@ pwait { The \code{pprivate} keyword is especially relevant for pbranches created within \code{for} and \code{while} loops. Listing~\ref{lst:pprivate} shows an -example. +example demonstrating the use of pwait, pprivate and pbranch. diff --git a/papers/2011/aesop/model.tex b/papers/2011/aesop/model.tex index b58ce7c..fa1020d 100644 --- a/papers/2011/aesop/model.tex +++ b/papers/2011/aesop/model.tex @@ -1,12 +1,98 @@ -Highly concurrent syste +This section describes the \aesop progamming language and the associated +program model. -\subsection{Resources and Events} +\subsection{Parallel Branches} -We treat asynchronous events as being produced by \emph{resources}. -Resources are logical components of the system (on a single node) that perform -operations for a period of time. Examples include network cards, storage -devices, scheduling, timing +Concurrency is expressed in \aesop through the use of {\em parallel branches} +or {\em pbranches}. A parallel branch groups a list of statements and +supports branch-scoped variables, much like a regular function. However, when +multiple which will be executed sequentially, as in a normal C program. +However, when multiple pbranches are active, the \aesop language only enforces +sequential execution on the scope of a single pbranch. Statements from other +pbranches might interleave execution or might execute concurrently (using a +thread for example). + +It is possible to synchronize with pbranches using the {\em pwait} construct. +A pwait is similar to the barrier implicit in many OpenMP directives (such as +parallel for), in that no statements following the pwait will execute unless +all of the pbranches it encloses have completed. + +By default, variables in \aesop are shared between pbranches. Marking a +variable as {\em pprivate} gives each pbranch a private shadow copy, initialized +using the shared instance when the branch is created. + +It is possible for a pbranch to request the termination (or cancellation) of +all other pbranches within the same pwait by calling the +\code{aesop_cancel_branches} function. This function returns as soon as the +other pbranches have been marked for cancellation; it is asynchronous in that +it does not wait for the other pbranches to exit. While pbranches are not +forcibly terminated, a pbranch with an outstanding cancellation request +exhibits a slightly different behavior to ensure a race free delivery of the +cancellation signal. By design, it is not possible for a pbranch to clear its +cancellation flag. + +\aesop also supports {\em lonely pbranches}, i.e.\ pbranches created outside +of a pwait. A lonely pbranch is similar to a POSIX detached thread in that +lonely pbranches cannot be cancelled or synchronized with. + + +\subsection{Blocking Functions} + +\aesop adds extends the C programming language with a new function type: {\em +blocking} functions. The blocking qualifyier is part of the type. A pointer to +a regular C function is not compatible with a function pointer to a blocking +function with the same function arguments. Blocking functions differ from +regular C functions in that only blocking functions can contain pbranches. +In addition, blocking functions support {\em cancellation}. + +Functions can be made blocking by adding the \code{__blocking} +qualifyer to the function declaration. However, blocking functions can only be +called (either direct or indirect through a blocking function pointer) by +other blocking functions. This effectively requires the starting function of +an \aesop program to be blocking. + + +% cancellation + +A active blocking function in a pbranch receiving a cancellation request will +be notified of the cancellation. The effect of this notification, and the way +the function reacts to this request, depends on the implementation of that +particular function. Likewise, any subsequent blocking call initiated in that +pbranch will learn of the active cancellation request. While this is not +enforced by the language, a proper blocking function should return as soon as +possible when a branch is in a cancelled state. + + +% when to use blocking functions +The intention is that functions that are not completely cpu-bound (i.e. cannot +efficiently fully consume a thread) are to be made blocking. The \aesop +language provides a way for blocking functions to indicate they can no longer +make progress (for example because the function is waiting on an external +event or device). When this happens, execution will continue in another +branch. + +Because of the pbranch construct, the \aesop language does not describe or +require a thread concept in order to expose concurrency. In fact, instead of +promising explicit concurrent execution for pbranches, the language guarantees +that, when one or more pbranches within the program are ready to execute, at +least one of them will make progress. For example, in a pwait containing two +branches, if one branch should stall on a blocking function (for example +waiting for I/O), execution will proceed in the second pbranch provided that +pbranch is ready to do so. + +% multiple threads +In effect, the \aesop programming model provides for multiplexing multiple +pbranches onto a single thread or core, similar to application implemented +user space threading with voluntary yielding. This does not preclude true +multi-threading; \aesop is fully thread-safe, and it is possible to have +multiple OS threads executing within a single aesop program. In fact, to fully +exploit multi-core systems, we routinely use multiple threads to run aesop +code. In that case, if more than one pbranch becomes ready for execution, +multiple threads will be used to execute those branches concurrently. + + +\subsection{Example Aesop Code} \begin{figure} %\vskip -0.25in @@ -17,24 +103,43 @@ devices, scheduling, timing } \end{figure} -% I don't think limited in capacity is a resource requisite. -% From a usage point of view: maybe; From aesop language point of view: a -% resource is a undivisable blocking function. (i.e. a blocking function which -% itself doesn't call any aesop blocking functions) -% -Mention properties of resources: -limited in capacity, capability -often require or benefit from scheduling -This should invoke the notion of queueing, delaying, waiting, etc. -of operations that are given to resources. +Listing~\ref{lst:parallelfor} shows a common aesop code pattern. +Network servers, having a finite set of resources, have to protect against +unbounded resource consumption by misbehaving or failing peers. This is +typically done by placing an upper limit on the time resources are dedicated +to a request, cancelling the request when the allocated time is +exceeded. + + +\begin{figure} + \begin{lstlisting} +__blocking void doWrite (...) { + pwait { + pbranch { + aesop_timer (TIMEOUT); + ae_cancel_branches (); + } + pbranch { + replicateWrite (...); + ae_cancel_branches (); + } + } +} +__blocking void replicateWrite (...) { + pwait { + pprivate int i; + for (i=0; i<REPLICAS; ++i) + pbranch { + replicateWriteTo (i); + } + } +} +\end{lstlisting} +\caption{Aesop Code Example} +\end{figure} -In practice, interfaces to a resource usually consist -of a basic set of asynchronous or non-blocking function calls provided as -a userspace library. -\subsection{Serial Control Flow} -\subsection{Misc. notes} \color{red} Somewhere (not sure where in the paper) we should address how aesop uses @@ -46,9 +151,4 @@ whatever we end up settling on there. \color{black} -Aesop has no such restriction on which -thread executes non-async code. Continuation of aesop functions can -be driven by a single thread in the aesop poll engine, by threaded -callbacks from resources, or (hypothetically, we haven't implemented -this) by a thread pool in the aesop poll engine. \color{black} diff --git a/papers/2011/aesop/related.tex b/papers/2011/aesop/related.tex index 5fd9947..1f8a70e 100644 --- a/papers/2011/aesop/related.tex +++ b/papers/2011/aesop/related.tex @@ -13,13 +13,13 @@ Fortress~\cite{fortress}, CUDA~\cite{cuda-web}, and OpenCL~\cite{opencl08}. Such languages allow developers to annotate software to indicate blocks that should execute in parallel, including constructs for synchronization and sharing variables. While many of these constructs -share principles with Aesop, they were developed with the goal of +share principles with \aesop, they were developed with the goal of coordinating computation on multiple cores at the application level, rather than coordinating asynchronous activity on multiple I/O devices at the system software level. As a result these languages optimize for -maximum use of available CPU resources, while Aesop instead optimizes for +maximum use of available CPU resources, while \aesop instead optimizes for maximum use of underlying devices that may or may not require significant -CPU activity. The level of Aesop concurrency is not strongly correlated +CPU activity. The level of \aesop concurrency is not strongly correlated with the number of CPU cores available, though it does utilize multiple cores (if available) to improve latency. @@ -31,7 +31,7 @@ then GCD may match the number of threads to the number of CPU cores. If the tasks block on device activity, then it may instantiate a larger number of threads. The primary advantages of GCD are that it simplifies multi-threaded programming and automatically adjusts concurrency according -to the workload and the system architecture. Unlike Aesop, however, GCD +to the workload and the system architecture. Unlike \aesop, however, GCD always uses threads to achieve concurrency and provides no framework for integration with device API's that provide more scalable asynchronous interfaces. \color{red} Clarify this. You can use events (like timers and fd changes) @@ -79,16 +79,14 @@ his algorithm logic to the basic event-driven model. % task parallelism (asymmetric) - different operations (tasks) % this is repeated from above -Aesop has clear similarities to OpenMP, the C/Fortran language extensions for -expressing thread parallelism. In particular Aesop supports decoupling +\aesop has clear similarities to OpenMP, the C/Fortran language extensions for +expressing thread parallelism. In particular \aesop supports decoupling sequential control flow (i.e. parallel for), waiting for their completion (barrier) and the annotation of variables to indicate if they are to be shared or private with respect to concurrent execution flows. As all these concepts -are present in OpenMP as well, it's easy to see how Aesop might be used to +are present in OpenMP as well, it's easy to see how \aesop might be used to write multi-threaded applications. However, this is not the primary focus of -Aesop. While OpenMP mainly provides a portable thread abstraction, it does not +\aesop. While OpenMP mainly provides a portable thread abstraction, it does not offer any support for asynchronous device interfaces. - - - - +\aesop also differs from the related work in that only \aesop offers language +support for cleanly cancelling outstanding concurrent execution paths. hooks/post-receive -- Triton-private Repository

1 0

Triton-private Repository branch, master, updated. 3cea60a7d673ee0f6de164bf765fb0d166a0039c
by noreply＠mcs.anl.gov 01 Mar '12

01 Mar '12

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Triton-private Repository". The branch, master has been updated via 3cea60a7d673ee0f6de164bf765fb0d166a0039c (commit) from 80500c343bcc8981737d20f828eb85b5542dff5e (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit 3cea60a7d673ee0f6de164bf765fb0d166a0039c Author: Kevin Harms <harms(a)alcf.anl.gov> Date: Thu Mar 1 15:13:48 2012 -0600 Add memory usage and latency graph ----------------------------------------------------------------------- Summary of changes: papers/2011/aesop/evaluation.tex | 14 ++++++++++++++ 1 files changed, 14 insertions(+), 0 deletions(-) Diff of changes: diff --git a/papers/2011/aesop/evaluation.tex b/papers/2011/aesop/evaluation.tex index 35c7cdb..e2d14ba 100644 --- a/papers/2011/aesop/evaluation.tex +++ b/papers/2011/aesop/evaluation.tex @@ -116,6 +116,8 @@ performance difference between blocking and non-blocking socket operations. Aesop uses non-blocking socket operations so this test case is a better comparison between aesop and a hand tuned server. +% use subfigure for performance graphs + \begin{figure}[t] \centering \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/read-hist.pdf} @@ -140,6 +142,18 @@ comparison between aesop and a hand tuned server. \caption{Write-null performance \label{fig:write-null-hist}} \end{figure} +\begin{figure}[t] + \centering + \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/write-mem.pdf} + \caption{Write memory usage \label{fig:write-mem}} +\end{figure} + +\begin{figure}[t] + \centering + \includegraphics[keepaspectratio,width=0.45\textwidth]{fig/write-lat.pdf} + \caption{Write Latency \label{fig:write-lat}} +\end{figure} + \subsection{Productivity} \begin{table} hooks/post-receive -- Triton-private Repository

1 0

Triton-private Repository branch, master, updated. 80500c343bcc8981737d20f828eb85b5542dff5e
by noreply＠mcs.anl.gov 01 Mar '12

01 Mar '12

This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Triton-private Repository". The branch, master has been updated via 80500c343bcc8981737d20f828eb85b5542dff5e (commit) from ae59435a6f4aaf4f56a87cfa91b7fe96c4eb951f (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit 80500c343bcc8981737d20f828eb85b5542dff5e Author: Justin M Wozniak <wozniak(a)mcs.anl.gov> Date: Thu Mar 1 14:30:21 2012 -0600 Minor change to figure ----------------------------------------------------------------------- Summary of changes: papers/2011/aesop/model.pdf | Bin 27111 -> 24961 bytes papers/2011/aesop/model.svg | 98 +++++++++++++++++++++--------------------- 2 files changed, 49 insertions(+), 49 deletions(-) Diff of changes: diff --git a/papers/2011/aesop/model.pdf b/papers/2011/aesop/model.pdf index d83fa5d..ddbc43f 100644 Binary files a/papers/2011/aesop/model.pdf and b/papers/2011/aesop/model.pdf differ diff --git a/papers/2011/aesop/model.svg b/papers/2011/aesop/model.svg index ea33f2e..2d63649 100644 --- a/papers/2011/aesop/model.svg +++ b/papers/2011/aesop/model.svg @@ -368,7 +368,7 @@ <dc:format>image/svg+xml</dc:format> <dc:type rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> - <dc:title></dc:title> + <dc:title /> </cc:Work> </rdf:RDF> </metadata> @@ -669,15 +669,15 @@ <text sodipodi:linespacing="125%" id="text2985-5-2-8-8" - y="517.36218" + y="521.36218" x="717.5" style="font-size:36px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;font-family:Arial;-inkscape-font-specification:Arial" xml:space="preserve"><tspan - y="517.36218" + y="521.36218" x="717.5" sodipodi:role="line" id="tspan3304-3-6">state</tspan><tspan - y="562.36218" + y="566.36218" x="717.5" sodipodi:role="line" id="tspan4263">transitions</tspan></text> @@ -685,20 +685,20 @@ sodipodi:linespacing="125%" id="text2985-5-2-8-5" y="377.36218" - x="1297.5" + x="1317.5" style="font-size:36px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;font-family:Arial;-inkscape-font-specification:Arial" xml:space="preserve"><tspan y="377.36218" - x="1297.5" + x="1317.5" sodipodi:role="line" id="tspan4291" - style="font-weight:bold">{ user code }</tspan><tspan + style="font-weight:bold">{ server code }</tspan><tspan y="422.36218" - x="1302.4922" + x="1322.4922" sodipodi:role="line" id="tspan4293">... </tspan><tspan y="467.36218" - x="1297.5" + x="1317.5" sodipodi:role="line" id="tspan4295" /></text> <path @@ -708,46 +708,6 @@ inkscape:connector-type="polyline" inkscape:connector-curvature="0" sodipodi:nodetypes="cc" /> - <text - sodipodi:linespacing="125%" - id="text2985-5-2-8-5-4" - y="497.36218" - x="1297.5" - style="font-size:36px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;font-family:Arial;-inkscape-font-specification:Arial" - xml:space="preserve"><tspan - y="497.36218" - x="1297.5" - sodipodi:role="line" - id="tspan4291-0" - style="font-weight:bold">{ user code }</tspan><tspan - y="542.36218" - x="1302.4922" - sodipodi:role="line" - id="tspan4293-3">... </tspan><tspan - y="587.36218" - x="1297.5" - sodipodi:role="line" - id="tspan4295-7" /></text> - <text - sodipodi:linespacing="125%" - id="text2985-5-2-8-5-0" - y="617.36218" - x="1297.5" - style="font-size:36px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;font-family:Arial;-inkscape-font-specification:Arial" - xml:space="preserve"><tspan - y="617.36218" - x="1297.5" - sodipodi:role="line" - id="tspan4291-8" - style="font-weight:bold">{ user code }</tspan><tspan - y="662.36218" - x="1302.4922" - sodipodi:role="line" - id="tspan4293-30">... </tspan><tspan - y="707.36218" - x="1297.5" - sodipodi:role="line" - id="tspan4295-0" /></text> <path style="fill:url(#linearGradient5244);fill-opacity:1;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;marker-start:none;marker-end:url(#TriangleOutL);display:inline" d="m 817.5,577.36218 340,20" @@ -762,5 +722,45 @@ inkscape:connector-type="polyline" inkscape:connector-curvature="0" sodipodi:nodetypes="cc" /> + <text + sodipodi:linespacing="125%" + id="text2985-5-2-8-5-2" + y="503.36218" + x="1317.5" + style="font-size:36px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;font-family:Arial;-inkscape-font-specification:Arial" + xml:space="preserve"><tspan + y="503.36218" + x="1317.5" + sodipodi:role="line" + id="tspan4291-9" + style="font-weight:bold">{ server code }</tspan><tspan + y="548.36218" + x="1322.4922" + sodipodi:role="line" + id="tspan4293-4">... </tspan><tspan + y="593.36218" + x="1317.5" + sodipodi:role="line" + id="tspan4295-1" /></text> + <text + sodipodi:linespacing="125%" + id="text2985-5-2-8-5-8" + y="607.36218" + x="1317.5" + style="font-size:36px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;font-family:Arial;-inkscape-font-specification:Arial" + xml:space="preserve"><tspan + y="607.36218" + x="1317.5" + sodipodi:role="line" + id="tspan4291-3" + style="font-weight:bold">{ server code }</tspan><tspan + y="652.36218" + x="1322.4922" + sodipodi:role="line" + id="tspan4293-9">... </tspan><tspan + y="697.36218" + x="1317.5" + sodipodi:role="line" + id="tspan4295-7" /></text> </g> </svg> hooks/post-receive -- Triton-private Repository

1 0