# HG changeset patch # User Nina Engelhardt # Date 1341307633 -7200 # Node ID 59a4161e7bf237eafec8ac1503f00944549d5c45 # Parent cce09bfd652f646e67e586554d933e713ca37186 updated figures diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/figures/10.pdf Binary file 0__Papers/Holistic_Model/Perf_Tune/figures/10.pdf has changed diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/figures/10.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/Holistic_Model/Perf_Tune/figures/10.svg Tue Jul 03 11:27:13 2012 +0200 @@ -0,0 +1,8081 @@ + + + + + diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/figures/12.pdf Binary file 0__Papers/Holistic_Model/Perf_Tune/figures/12.pdf has changed diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/figures/12.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/Holistic_Model/Perf_Tune/figures/12.svg Tue Jul 03 11:27:13 2012 +0200 @@ -0,0 +1,8047 @@ + + + + + diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/figures/15.pdf Binary file 0__Papers/Holistic_Model/Perf_Tune/figures/15.pdf has changed diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/figures/15.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/Holistic_Model/Perf_Tune/figures/15.svg Tue Jul 03 11:27:13 2012 +0200 @@ -0,0 +1,30379 @@ + + + + + diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/figures/2.pdf Binary file 0__Papers/Holistic_Model/Perf_Tune/figures/2.pdf has changed diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/figures/2.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/Holistic_Model/Perf_Tune/figures/2.svg Tue Jul 03 11:27:13 2012 +0200 @@ -0,0 +1,7895 @@ + + + + + diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/figures/222.pdf Binary file 0__Papers/Holistic_Model/Perf_Tune/figures/222.pdf has changed diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/figures/222.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/Holistic_Model/Perf_Tune/figures/222.svg Tue Jul 03 11:27:13 2012 +0200 @@ -0,0 +1,8109 @@ + + + + + diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/figures/5.pdf Binary file 0__Papers/Holistic_Model/Perf_Tune/figures/5.pdf has changed diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/figures/5.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/Holistic_Model/Perf_Tune/figures/5.svg Tue Jul 03 11:27:13 2012 +0200 @@ -0,0 +1,7899 @@ + + + + + diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/figures/6.pdf Binary file 0__Papers/Holistic_Model/Perf_Tune/figures/6.pdf has changed diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/figures/6.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/Holistic_Model/Perf_Tune/figures/6.svg Tue Jul 03 11:27:13 2012 +0200 @@ -0,0 +1,12933 @@ + + + + + diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/figures/7.pdf Binary file 0__Papers/Holistic_Model/Perf_Tune/figures/7.pdf has changed diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/figures/7.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/0__Papers/Holistic_Model/Perf_Tune/figures/7.svg Tue Jul 03 11:27:13 2012 +0200 @@ -0,0 +1,28979 @@ + + + + + diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/latex/Holistic_Perf_Tuning.pdf Binary file 0__Papers/Holistic_Model/Perf_Tune/latex/Holistic_Perf_Tuning.pdf has changed diff -r cce09bfd652f -r 59a4161e7bf2 0__Papers/Holistic_Model/Perf_Tune/latex/Holistic_Perf_Tuning.tex --- a/0__Papers/Holistic_Model/Perf_Tune/latex/Holistic_Perf_Tuning.tex Wed Jun 27 05:00:03 2012 -0700 +++ b/0__Papers/Holistic_Model/Perf_Tune/latex/Holistic_Perf_Tuning.tex Tue Jul 03 11:27:13 2012 +0200 @@ -84,7 +84,7 @@ Performance visualizations and tuning tools for parallel programs are critical to achieving good performance, and yet current solutions leave something to be desired. All too often, performance tuning consists of staring at abstract views of usage or statistics, trying to \emph{guess} the cause of performance loss. Despite many different views of performance measurements, such as frequency by line of code, message sends and receives, and core usage timelines, the user doesn't know why a function runs in a particular spot on a particular core, nor whether that is desired behavior or erroneous behavior. -Examining these myriad views can feel like being advised by the fabled six blind men examining an elephant by touching the part nearest to each\ref{The poems of John Godfrey Saxe/The Blind Men and the Elephant}: one, reaching the side, proclaims it much like a wall; the second, feeling the tusk, compares it to a spear; the next, feeling the trunk, is reminded of a snake, and so on. All of these views are indeed correct and supply important information, but they don't connect to each other, to provide a view of how the parts interact to form a whole. +Examining these myriad views can feel like being advised by the fabled six blind men examining an elephant by touching the part nearest to each\ref{The poems of John Godfrey Saxe/The Blind Men and the Elephant}: one, reaching the side, says it is much like a wall; the second, feeling the tusk, compares it to a spear; the next, feeling the trunk, is reminded of a snake, and so on. All of these views are indeed correct and supply important information, but they don't connect to each other, to provide a view of how the parts interact to form a whole. Current tools may cover all the parts of the application code, but fail to adequately connect their observations to the runtime behavior, scheduling decisions, and consequent hardware behavior. The decision about which task or virtual processor is assigned to which core at what point in time is at the heart of parallel performance, so these choices need to be highlighted and connected to the application features influencing them. @@ -92,10 +92,9 @@ The model relates the measurements to each other and to the application. -Using the model, we generate views that show the schedulable units in the code, runtime overhead assigned to each, the scheduling decisions made for them by the runtime, and consequent usage of the cores. Identifying idle cores is immediate, and the connections indicated by visual features enable more quickly generating the correct hypotheses for the causes of the performance losses. The visual features connect each unit to the segment of code executed, and to the constraint in the code that combined with the runtime to cause its placement in time and location. The pattern of placements, combined with contents of the code, leads to the hypothesis. - - - +Using the model, we generate views that show the schedulable units in the code, runtime overhead assigned to each, the scheduling decisions made for them by the runtime, and consequent usage of the cores. Identifying idle cores is immediate, and the connections indicated by visual features enable more quickly generating the correct hypotheses for the causes of the performance losses. The visual features connect each unit to the segment of code executed, and +%% hard to understand +to the constraint in the code that combined with the runtime to cause its placement in time and location. The pattern of placements, combined with contents of the code, leads to the hypothesis. In this paper, we describe our model of computation, and illustrate its usage with a story line of performance tuning a standard parallel application on a large multi-core system. @@ -105,9 +104,9 @@ \section{Background and Related Work} \label{sec:related} -A quick review of the process of performance tuning will provide much needed context for the shortcomings of other tools. +A quick review of the process of performance tuning will provide much needed context for the shortcomings of other tools. %too negative - Performance tuning is an iterative process that involves a mental model. The programmer takes measurements during execution that are then compared to the desired outcome. A mental model, constructed through experience and knowledge of the mechanics of execution, is used to generate a hypothesis explaining any discrepancies between the measurement and expectations. This hypothesis is then linked, again through a mental model, to things within the programmer's control, to suggest a change to make to the code. The modified code is then run again, and these steps are repeated until the programmer is satisfied with the performance of the program. + Performance tuning is an iterative process that involves a mental model. The programmer takes measurements during execution that are then compared to the desired outcome. A mental model, constructed through experience and knowledge of the mechanics of execution, is used to generate a hypothesis explaining any discrepancies between the measurement and expectations. This hypothesis is then linked, again through a mental model, to things within the programmer's control, to suggest a change to make to the code. The modified code is run again, and these steps are repeated until the programmer is satisfied with the performance of the program. For parallel performance tuning, the rest of the paper will support the position that the quantities best to measure are scheduling decisions and the consequent usage of communication hardware and cores. Hence, the mental model should have, as concepts, units of scheduled work, and scheduling decisions made on them, then relate those to consequent hardware behavior. It should also relate all of those to application code, such as code boundaries that identify units, and constraints (dependencies) the application places on scheduling decisions. @@ -133,7 +132,7 @@ Paragraph also follows an event-based model, but represents the large collection of simpler tools that instrument the MPI or other message-passing library. It shows whether cores are busy, and indicates communication overhead, but lacks an underlying computation model to tie the communication pattern realized to application code features, which are what is under programmer control. It also fails to show runtime overhead, and which portions of idle time are caused by runtime internal constraints. -Note that Paraver and Vampir are just painting tools that take event measurements and paint them on the screen. +%Note that Paraver and Vampir are just painting tools that take event measurements and paint them on the screen. \subsection{Performance-counter approaches} Performance-counter approaches, such as VTune, POPI, and so forth concentrate on identifying hot-spots and potential false-sharing. These suffer from a lack of encompassing computation model, leaving the user to guess at what might be the cause of measured numbers. They do a good job of saying that something might be wrong, but a poor job of pointing to what is causing the problem, and hence leave the user baffled as to what to change in their code to get better performance. @@ -143,7 +142,7 @@ These shortcomings are rectified by recent parallel languages such as CnC[] and StarSs[], which cleanly identify tasks and the constraints on them. The people who develop such a language usually also develop tools to go with it. -The StarSs tool[]\ prioritizes simplifying the view for the user. It doesn't give performance information directly, but instead identifies tasks and tells the user whether it thinks the task size is too small, just right, or tool big. Too small has too much runtime overhead, while too big has too few tasks to keep the cores busy. +The StarSs tool[]\ prioritizes simplifying the view for the user. It doesn't give performance information directly, but instead identifies tasks and tells the user whether it thinks the task size is too small, just right, or too big. Too small has too much runtime overhead, while too big has too few tasks to keep the cores busy. This is a step in the right direction, but it doesn't include effects of code choices on communication, and gives the programmer only limited information. Subtle and complex interactions between code, runtime, and hardware are often to blame for performance loss, and the limited information supplied here is no help with such complexities. @@ -169,7 +168,7 @@ How many pieces is set by a tuning parameter in the code, and the number of cores. The appliation uses language features to distribute the VPs across the cores, in a round-robin fashion (before tuning). -It then creates a results VP that receives a partial-result from each piece and accumulates the results. The original divider VP then waits for the results VP to indicate completion, after which the language shuts down. +It then creates a results VP that receives a partial-result from each piece and accumulates the results. The original divider VP then waits for the results VP to indicate completion, after which the language runtime shuts down. \subsection{The language} The language used is SSR, which is based on rendez-vous style send and receive operations made between virtual processors (VPs). It has commands for creating and destroying VPs, and three kinds of send-receive paired operations. @@ -230,7 +229,7 @@ \begin{figure*}[t!] \begin{minipage}[b]{0.2\textwidth} \subfloat[Original] - {\quad\quad \includegraphics[scale=0.015]{../figures/192.pdf} \quad + {\quad\quad \includegraphics[scale=0.015]{../figures/222.pdf} \quad \label{fig:story:a}}\quad \end{minipage} \begin{minipage}[b]{0.7\textwidth} @@ -238,10 +237,10 @@ % {\includegraphics[scale=0.015]{../figures/194.pdf} % }\quad \subfloat[Fix load balancer] - {\includegraphics[scale=0.015]{../figures/196.pdf} + {\includegraphics[scale=0.015]{../figures/2.pdf} \label{story:b}}\quad \subfloat[Solution~1 (portable)] - {\includegraphics[scale=0.015]{../figures/199.pdf} + {\includegraphics[scale=0.015]{../figures/5.pdf} \label{story:c}}\quad % \subfloat[S1+divide factor 0.2] % {\includegraphics[scale=0.015]{../figures/208.pdf} @@ -250,19 +249,19 @@ % {\includegraphics[scale=0.015]{../figures/209.pdf} % }\quad \subfloat[S1+divide factor 0.5] - {\includegraphics[scale=0.015]{../figures/212.pdf} + {\includegraphics[scale=0.015]{../figures/6.pdf} \label{story:d}}\quad \subfloat[S1+divide factor 0.4] - {\includegraphics[scale=0.015]{../figures/210.pdf} + {\includegraphics[scale=0.015]{../figures/7.pdf} \label{story:e}}\quad\\ \subfloat[Solution~2] - {\includegraphics[scale=0.015]{../figures/201.pdf} + {\includegraphics[scale=0.015]{../figures/12.pdf} \label{story:f}}\quad \subfloat[S2+move receive pr] - {\includegraphics[scale=0.015]{../figures/204.pdf} + {\includegraphics[scale=0.015]{../figures/10.pdf} \label{story:g}}\quad \subfloat[S2+divide factor 0.4] - {\includegraphics[scale=0.015]{../figures/216.pdf} + {\includegraphics[scale=0.015]{../figures/15.pdf} \label{story:h}}\quad % \subfloat[S2+divide factor 0.3] % {\includegraphics[scale=0.015]{../figures/217.pdf} @@ -283,7 +282,7 @@ In this subsection, many SCGs are shown, within Fig \ref{story}, that display the measurements collected on various runs during tuning. They are all 40 columns wide, one for each core, and all are on the same scale, so relative height indicates relative execution time. They have lines in red, orange, and green, which represent application-code constructs. Red is creation of a virtual processor, green is the many-to-one \texttt{send\_of\_type\_to}, and orange is the singleton construct. For better visibility, only constraints that cross cores are shown. -After functional debugging, the first tuning run produces the consequence graph seen in Figure \ref{fig:story:a}. The first thing to notice, is that it is slimmer than expected: of the 40 available cores, only 13 are being used. As the application places work on cores explicitly, this must be a bug in the dividing code. A cursory inspection reveals that a closing curly brace in the distribution loop had been misplaced. This may be a very simple bug, but it went unnoticed despite using this application as test program for development of the language runtime, including performance, for several months. +After functional debugging, the first tuning run produces the consequence graph seen in Figure \ref{fig:story:a}. The first thing to notice is that it is slimmer than expected: of the 40 available cores, only 13 are being used. As the application places work on cores explicitly, this must be a bug in the dividing code. A cursory inspection reveals that a closing curly brace in the distribution loop had been misplaced. This may be a very simple bug, but it went unnoticed despite using this application as test program for development of the language runtime, including performance, for several months. \subsubsection{Second Run} After fixing this, the next run (Fig \ref{story:b}) corresponds much more to the expected execution behaviour. However, there remains a noticeable section at the beginning where only 3 cores have work and the other 37 remain idle.