A trace-scaling agent for parallel application tracing.

A Trace-Scaling Agent for Parallel Application TracingJ Felix Freitag. Jordi Caubet, Jesus Labarta Computer Architecture Department (DAC) European Center for Parallelism of Barcelona (CEPBA) Univer.'Jitat Politecnica de Catalunya (UPC) {felix,jordics,jesus}@ac. upc.es Abstract requirement for trace files. We show that the agent can obtain such an understanding automatically at runtime without programmer intervention or support. The remainder of the paper is structured as follows: In section 2 we describe scalability problems of tracing mechanisms. Section 3 shows the implementation of the trace-scaling agent. Section 4 describes some applications and results of scaled tracing. Section 5 contains further disussion of our approach. In section 6 we conclude the paper. Tracing and performance analysis tools are an important component in the development of high performance applications. Tracing paral'el prqgrams with current tracing tools. however. easily leads to large trace files with hundreds of lUegabytes. The s~orage. visualization, and analysis of such trace files is often difficult. We propose a trace-scaling agent for tracing p~ral'el applications. which learns the application behaVior in runtime and achieves a small. easy to handle trade. The agent dynamically identifies the amount of inforbtation needed to capture the application behavior. This knowledge acquired at runtime allows recording o~ly the non-iterative trace iriformation, which drastical'y rf!duces the size of the tracefile. 2. Scalability of tracing mechanisms 2.1. Problems associated to large traces The perfonnance analysis of parallel programs easily leads to a large number of trace files, since often several executions of the instrumented application are carried out in order to observe the application behavior under slightly changed conditions. Another reason why several traces are needed is to study how the application scales. All these traces for the different configurations of the application and the environment (number of processors, algorithmic changes, hardware counters, ...) require storage space. Visualization packages have difficulties in showing such large traces effectively. Large traces make the navigation (zooming, forward/backward animation) through them very slow and require the machine where the visualization package is run to have a large physical memory. Othern'ise, the response time of the tool increases significantly, strongly affecting the motivation of the programmer to carry out the perfonnance analysis. The high amount of redundant trace infonnation in large trace files hides the relevant details of the application behavior. When visualizing such large traces, zooming down to identify the application structure becomes an inefficient task for the program analyst. Often, the analyst needs to have a certain understanding of the application in order to carry out an efficient perfonnance analysis. I. Introduction Performance analysis tools are an important component of the parallel program development and tuning cyqle. To obtain the raw performance data of an applicati~n, an instromented version of the application is run with probes that take measures of specific events or perfo~ance indicators (i.e. hardware counters, subroutines, parallel loops). The obtained trace data can be summarized on-line by the tracing tool. More often, however, it is stored ili1 trace files for off-line analysis. We focus our interest in 1Iracing packages for parallel programs, where all the ac~uired data is stored in trace files for a detailed analysis at !a later time. Tracing parallel programs with such traci~ tools easily leads to huge trace files with hundr~s of Megabytes, which has several problems conc!erning storage, visualization and analysis of such traces. We propose a trace-scaling agent for tracing tQols of parallel applications. In runtime the agent lea$ the periodic structure in the application behavior exhibi~ed by many scientific programs. The caption of the appljcation behavior allows storing only the non-iterative trace information, which drastically reduces the storage I This work has been supported by the Spanish MinistI)' of Science and Technology under TIC2001 -0995-CO2-01 and by the European Union (FEDER). Proceedings of the 14th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’02) 1082-3409/02 $17.00 © 2002 IEEE Authorized licensed use limited to: IEEE Xplore Customer. Downloaded on October 13, 2008 at 08:54 from IEEE Xplore. Restrictions apply. 2.2. Related work the trace file. The analysis of such a reduced trace allows tuning the main iterative body of the application. 3. Trace-scaling agent 3.1 Recognition of iterative patterns The most frequent approach to restrict the size of the trace in current practice is to insert calls into the source code of the application to start and stop the acing. Systems such as VampirTrace [6], VGV [4 , and OMPItrace [I] provide this mechanism. This a oach requires the modification of the source code, whi h may not always be available to the performance analys .Even if the source code is available, it is necessary to ve a certain understanding of it before being able to p operly insert the tracing control calls. The Paradyn project [5] developed an instrume tation technology (Dyninst) through which it is poss le to dynamically insert and take out probes in a ing program. Although no effort is made to autom tically detect periods, the methodology behind this approa h also relies on the iterative behavior of applications. The automatic periodicity detection idea we present this paper could be useful inside such a dynamic analy is tool to present to the user the actual structure f the application. In IBM UTE [7], an intermediate approach is fo lowed to partially tackle the problem, which large traces ose to the analysis tool. The tracing facility can generat huge traces of events, containing information with a lot o detail down to the level of context switches and global ystem activities. Then, filters are used to extract a tra e that focuses on a specific application, summ izing information in record formats more amena le to visualization and better describing the appl cation behavior. To properly handle the fast access to s ecific regions of a large trace file the SLOG format (s alable logfile format) has been adopted. Using a frame in x the Jmnpshot visualization tool [8] improves the acce s time to trace data. The trace of the application is a data stream containing the values of several parameters. If the application contains loops, then it has segments with periodic patterns. We apply a periodicity detection algorithm to the data stream in order to segment the data stream into periodic patterns. The used algorithm is frame based and requires a finite length of past data values to compute the periodicity. We implement the periodicity detector from [3] in the trace-scaling agent in order to perform the automatic detection of iterative structures in the trace. The stre3ln of parallel function identifiers from the trace is the input. The output of the agent is the indication whether periodicity exists in the data stream and its period length. The algorithm used by the periodicity detector is based on the distance metric given by the equation ,V-I d(m) = sign Ii x(i)- x(i -m)1 1=0 ( 1 ). In equation (I) N is the size of the data window, m is the delay (O<m<M), M<=N, x[i] is the current value of the data stream, and d(m) is the value computed to detect the periodicity. It can be seen that equation (1) compares the data sequence with the data sequence shifted m samples. Equation (1) computes the distance between two vectors of size N by sumJning the magnitudes of the L I -metric distance of N vector elements. The sign function is used to set the values d(m) to 1 if the distance is not zero. The value d(m) becomes zero if the data window contains an identical periodic pattern with periodicity m. If the periodicity m in the data stream is several magnitudes less than the size N of the data window, then the value d(m) may become zero for multiples of m. On the other hand if the periodicity m in the data stream is larger than the data window size N, then the detector cannot capture the periodicity. The periodicity length we found in the used applications was usually small (between 5 -20) and less than 300. For an unknown data stream, the window size N of the periodicity detector can be set initially to a large value, in order to be able to capture potentially large periodicities. Once a satisfying periodicity is detected, the window size can be reduced dynamically. 2.3 Our approach ~Our approach to the scalability problem oftraci is to adapt dynamically the traced time. We propose a tracescaling agent, which learns in runtime the structure of the application. It automatically determines the r levant tracing intervals, which are sufficient to capt e the application behavior. With the trace-scaling age t it is possible to trace only one or several iterations f the dynamically detected repetitive pattern in the appl cation behavior. Our approach does not require limit" 9 the granularity of tracing, nor the number of paramete s read at every tracing point, nor the problem size. Due to the dynamic interception of the calls to runtime librarie in the tracing tool, our implementation does not requi e the source code of the application to achieve the scal trace. In runtime the redundant trace information is ide tified and only the non-iterative application behavior is st red in Proceedings of the 14th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’02) 1082-3409/02 $17.00 © 2002 IEEE Authorized licensed use limited to: IEEE Xplore Customer. Downloaded on October 13, 2008 at 08:54 from IEEE Xplore. Restrictions apply. 3.2. Implementation The new sample overwrites the column containing the oldest values with the new distance. The implementation with circular lists avoids moving the data values. The number of operations at instant i are reduced, which leads to a small overhead of this implementation. 3.3. OpenMP and tracing tool integration The structure of OpenMP based parallel applications usually iterates over several parallel regions. For each parallel directive the master thread invokes a runtime library passing as argument the address of the outlined routine. The tracing mechanism intercepts the call and obtains a stream of parallel function identifiers. This stream contains all executed parallel functions of the application, both in periodic and non-periodic parallel regions. We have implemented the trace-scaling agent in the OMPItrace tracing tool [I]. The tracing tool generates trace tiles, which consist of events (hardware counter values, parallel regions entry/exit, user functions entry/exit) and thread states (computing, idle, fork/join). full trace data stream iterative patterns scaled trace iLorali.o bcha.;or DO lraoc i. wriLIOD 11111111 IIIIIIIIIIIIIIIIII 111111111 ~ t Figure I. Interaction or the agent in the tracing tool. In Figure 1 the interaction between the instrumented application, the tracing tool, and the agent is illustrated. It can be seen that the agent receives a data stream from the tracing tool. The data stre~ contains the values of a traced parameter such as the identifiers of the executed functions in parallel regions. The agent learns the application behavior. Having this indication the tracing tool knows, which is the non-iterative information to write to the trace file. In our implementation of equation ( I ), we store ~ finite number of previous data values of the data Istream including the most recent value in a data vector. ~ n this data vector the algorithm performs periodicity det ction. This data vector can be implemented as a FIFO b ffer of length M+N. This type of implementation uses ~ least amount of memory, but requires a higher number of operations at every instant i than other implementations. Applying equation (I) on the data vector requir,s M x N operations to compute the values of d(m) at the instant i of the data stream. It can be observed, however, that some operations are done with the same data values ~everal times at different instants i. The previously co puted distances between vector elements could be sto d to reduce the number of computations made by the algorithm at instant i. There is a trade-off between the nwnber of computations made at instant i. and the amount of memory needed by the algorithm. In order to reduce the amiunt of computation we implement a FIFO organized ma rix of size MxN where previously computed distanc s are stored. Using this distance matrix we compute ~ each instant i the value of di(m) for all values of m, whd;re x(i) is the value of the data value at the current samplel i, and x(i-m) is the data value obtained m samples beforb. The computed values of d;(m) are written in the 9olumn corresponding to the instant i in the matrix. i In case of using the distance matrix to store preJiously computed distances, then only M instead of j x N operations need to be made at instant i to obtain e new distances di(m). The value of d(m) for all value m is obtained by summing the elements of each raw 1of the distance matrix, i.e. the previously computed di tances and each most recent distance d;(m). This means hat at every instant i new values are written in a columnlof the distance matrix, and d(m) is computed as the sum lof the values in each raw using the previously computed ~alues of the other columns. Using the distance matrix the l ize of the data vector can be reduced to M, since at instant i only the distances between the ne~l data value and the M I past data values need to be computed. It can be s en in equation ( I) that if the data window size N and th delay M is increased, larger iterative structures can be de ected. Then, the number of computations to obtain d( ) also increases. However, when increasing N and M a d the previously computed distances are re-used, th n the increase of operations is only linear. i In order to reduce the number of shifts of thel FIFO operations, the data structures of the periodicity detector conceptually working as FIFO organized matrix and FIFO organized data vector are programmed as circular lilts. At each instant i the pointer to the current list elemen shifts by one such that it points to the oldest values in t e list. Proceedings of the 14th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’02) 1082-3409/02 $17.00 © 2002 IEEE Authorized licensed use limited to: IEEE Xplore Customer. Downloaded on October 13, 2008 at 08:54 from IEEE Xplore. Restrictions apply. 4. Applications of scaled tracing 4.3. Improvement of the ease of visualization 4.1. Experimental setup We trace the applications given in Table 1 i Four applications from the NAS benchmark suite: Et (cl~ss A), I Lu (class A), Cg (class A) and Sp (class A); aI1d five applications of the SPEC95 suite: Swim, Hydro2dj Apsi, Tomcatv, and Turb3d, all with ref data set. ! All experiments are carried out on a Silicon G~aphics Origin 2000. The OpenMP applications are execut~d in a dedicated environment with 8 CPUs. We configqre the trace-scaling agent such that after having detec,ed 10 iterative parallel regions it stops writing trace datal to the file until it observes a new program behavio~. The parameters contained in the trace file are the threaq states and OpenMP events, which include two hatdware counters. Considering the full trace in Figure 4 (see fmal page) a first visual perception of the program behavior can be quite misleading. For example, it seems that there is a lot of for~join activity in the first thread (white color) while this is only an effect of the display precision. The reason is that at the scale that had to be used to display the whole trace, each pixel represents a large time interval (152 ms) within which one thread can perform many changes of activity. In Figure 5 (see final page) we can easily identify that there is a periodic pattern (period boundaries tagged with flags). It can be observed that after a certain number of repetitions this pattern changes and that a new periodic pattern is then repeated. The direct look at the full trace of Figure 4 hardly reveals that there is a special behavior in the middle part. The flags in Figure 5 identify the period. With the scaled trace it is immediate to zoom to an adequate level to see the actual pattern of behavior. In the visualization of the scaled trace, the iterative trace information is not shown (Figure 5 black area), since the tracing mechanism did not write it to the trace file. Table I. Evaluated benchmarks. Benchmarks --- Application NAS Et NAS Cg NAS Lu NAS Sp Apsi Hydro2D Swim Tomcatv Turb3d NAS benchmarks 4.4. Reduction of the trace file size We examine how much the tmce file size reduces when using the trace-scaling agent. Figure 2 shows the size of the trace files for the NAS and SPEC95 benchmarks obtained with and without using the agent. It can be seen that with scalable tracing the trace files are reduced significantly. The NAS Lu trace file, for instance, reduces from I73 Mb to 8 Mb, which is a reduction of 95%. Had we traced less than IO iterations, the trace size would reduce more. SPEC95fp benchmarks 4.2. Application structure identification - .0 ~ - .r. -0) c: ~ Q) u ~ ... The trace-scaling agent allows inserting info$ation about the detected application structure in thei trace records, which indicates the start/end of an it~rative pattern. This infonnation is highly useful for the I/nalyst because one of the first activities when facing a largf trace is to zoom down, trying to identify an area of !a few periods that can be taken as reference for loo~ng at details. The tracing tool writes these events indicating periodic patterns to the trace even if the writing ! of all other trace information is suspended. In Figure 3 (see fmal page) two iterative regionsi of the NAS Et benchmark with their thread states are shown. The boundaries of the iterative regions are represented as flags, which reveal the application structure. The number of periodic patterns and their duration can easJly be comDuted from the Deriodicitv event in the trace filei Proceedings of the 14th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’02) 1082-3409/02 $17.00 © 2002 IEEE Authorized licensed use limited to: IEEE Xplore Customer. Downloaded on October 13, 2008 at 08:54 from IEEE Xplore. Restrictions apply. efficient analysis. We have proposed a trace-scaling agent, which allows storing data for a complete analysis while achieving a small trace file. We have implemented the agent, which learns the application behavior in runtime and allows storing only the non-iterative trace data. We have shown that the size of such a scaled trace file becomes significantly reduced, while in the traced interval the relevant application behavior is captured. We observed that the scaled traces are easy to handle by visualization tools and the scaled trace lets the analyst fuster observe relevant application behavior such as the application structure. Our implementation of the tracescaling agent has a small overhead and it is used in runtime. The scaled trace can substitute the full trace in several performance analysis tasks, since it allows the performance analyst to reach the same conclusions on the application performance as when using the full trace. - ~.Full trace .10lteratio s -- .c ~ .c -C) c ~ Qj ~ .. ... NAS lu Hydro2D Figure 2. Comparison of the trace file size wi~h full and scalable tracing. 5. Discussion 7. References The overhead of an implementation is an important performance factor of real-time tools. In [2] w~ have evaluated the overhead produced by the trace-$caling agent. It was observed that the overhead introdu4ed by tracing is small in terms of the execution timtThe original tracing tool adds 1% -3% to the executio time. With the trace-scaling agent, the overhead is 3% -6 0. In applications with a periodic pattern ",'e ex ect to reach the same concluysions on performance I when analysing a subset of the iterations, i.e. the scaled trhce. In [2] we have compared the performance indices coTputed from the scaled and full traces. Our results show ~rt the same performance conclusions can be obtained I when analysing the scaled trace of the applications. i The agent learns the application behavior frfthe stream of function identifiers. It could be possible t t the agent detects iterative behavior in the executed fun tions, but at the same time the performance of the other i dices (cache misses, TLB misses, ...) could differ signi cantly from one iteration to another. If such a case occur~ in an isolated parallel region, the agent would not dete~t this situation. I Our tool relies on the iterative behavior OfapPli ftions, where loops are executed many times. Many sc. ntific applications have such a structure. The studied N S and SPEC95 benchmarks, which mostly perform n eric computations, exhibit iterative application behav~or. In case of having the trace-scaling agent activate4 with another class of applications, which are non-iterative, simply no periodic behavior would be detected and the whole trace would be written to the file. [1] J. Caubet, J. Gimenez, J. Labarta, L. DeRose, J. Vetter. "A Dynamic Tracing Mechanism for Performance Analysis of OpenMP Applications." In Internationa/ Workshop on Open,\1P App/ications and Too/s (WO,\1PAT 2001), July 2001, pp. 53-67. [2] J. Caubet, F. Freitag, J. Labarta. "Comparison of scaled and full traces of OpenMP applications." Tech. Report UPC-DAC-200 1-31. [3] F. Freitag, J. Corbalan, J. Labarta. "A dynamic periodicity detector: Application to speedup computation." In Intermationa/ Para//e/ and Distributed Processing Symposium (IPDPS2001), Apri12001. [4] J. Hoeflinger, B, Kuhn, W. Nagel, P. Petersen, H. Rajic, S. Shah, J. Vetter, M. Voss, and R. Woo. An Integrated Performance Visualizer for MPl/OpenMP Programs. In Internationa/ Workshop on Open,\1P Applicatiom and Tools (WO,\1PAT2001), July 2001, pp. 40-52. [5] B. P, Miller, M. D. Callaghan. The Paradyn Parallel Performance Measurement Tools. IEEE Computer 28(11): 37-46, November 1995. [6] Pallas: Vampirtrace. Instal/ation and User's Guide, htm:llwww,12allas.de [7] C. E. Wu, A, Bolmarcich, M. Snir, D. Wootton, F. Parpia, A. Chen, E. Lusk and w, Gropp. From Trace Generation to Visualization: A Performance Framework for Distributed Parallel Systems. In Proceedings of SuperComputing (SC 2000), November 2000. [8] 0. Zaki, Eo Lusk, W, Gropp, and D. Swider, Toward scalable performance visualization with Jwnpshot. In Internationa/ Journa/ of High Performance Computing App/icatiom. 13(2): pages 277-288, 1999. 6. Conclusions We have described the some scalability probl~ms of tracing in cun-ent performance analysis tools an~ why these are a problem for storage, visualizatio~, and Proceedings of the 14th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’02) 1082-3409/02 $17.00 © 2002 IEEE Authorized licensed use limited to: IEEE Xplore Customer. Downloaded on October 13, 2008 at 08:54 from IEEE Xplore. Restrictions apply. Figure 3. Visualization of the thread states in the NAS Bt application in 2 iterative parallel regions. Light color=idle, dark color=computing. Figure 4. Visualization of the whole Hydro2D lexecution trace (full trace). Figure 5. Visualization of the Hydro2D execution with scaled tracing (scaled trace). Proceedings of the 14th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’02) 1082-3409/02 $17.00 © 2002 IEEE Authorized licensed use limited to: IEEE Xplore Customer. Downloaded on October 13, 2008 at 08:54 from IEEE Xplore. Restrictions apply.