Profiling tools for Java

Universidade do Minho Escola de Engenharia Departamento de Informática Vítor Domingos Araújo Gomes Profiling Tools for Java December 2021 Universidade do Minho Escola de Engenharia Departamento de Informática Vítor Domingos Araújo Gomes Profiling Tools for Java Master dissertation Integrated Master’s in Informatics Engineering Dissertation supervised by João Luís Ferreira Sobral December 2021 COPYRIGHT AND TERMS OF USE FOR THIRD PARTY WORK This dissertation reports on academic work that can be used by third parties as long as the internationally accepted standards and good practices are respected concerning copyright and related rights. This work can thereafter be used under the terms established in the license below. Readers needing authorisation conditions not provided for in the indicated licensing should contact the author through the RepositóriUM of the University of Minho. LICENSE GRANTED TO USERS OF THIS WORK: CC BY https://creativecommons.org/licenses/by/4.0/ STATEMENT OF INTEGRITY I hereby declare having conducted this academic work with integrity. I confirm that I have not used plagiarism or any form of undue use of information or falsification of results along the process leading to its elaboration. I further declare that I have fully acknowledged the Code of Ethical Conduct of the University of Minho. a RESUMO Atualmente, Java é uma das linguagens de programação mais populares. Esta popularidade é parcialmente devida à sua portabilidade que advém do facto do código Java ser compilado para bytecode que poderá ser executado por uma máquina virtual Java (JVM) compatível em qualquer sistema. A JVM pode depois interpretar diretamente ou compilar para código máquina a aplicação Java. No entanto, esta execução sobre uma máquina virtual cria alguns obstáculos à obtenção do perfil de execução de aplicações. Perfis de execução são valiosos para quem procura compreender o comportamento de uma aplicação pela recolha de métricas sobre a sua execução. A obtenção de perfis corretos é importante, mas a sua obtenção e análise pode ser desafiante, particularmente para aplicações paralelas. Esta dissertação sugere um fluxo de trabalho de otimização a aplicar na procura de aumentos na escalabilidade de aplicações Java paralelas. Este fluxo sugerido foi concebido para facilitar a descoberta dos problemas de desempenho que afetam uma dada aplicação paralela e sugerir ações a tomar para os investigar a fundo. O fluxo de trabalho utiliza a noção de possible speedups para quantificar o impacto de problemas de desempenho diferentes. A ideia de possible speedups passa por estimar o speedup que uma aplicação poderia atingir se um problema de desempenho específico fosse completamente removido. Esta estimativa é calculada utilizando as métricas recolhidas durante uma análise ao perfil de uma aplicação paralela e de uma versão sequencial da mesma aplicação. O conjunto de problemas de desempenho considerados incluem o desequilíbrio da carga de trabalho, sobrecarga de paralelismo devido ao aumento no número de instruções executadas, sobrecarga de sincronização, gargalos de desempenho no acesso à memória e a fração de trabalho sequencial. Estes problemas foram considerados as causas mais comuns de limitações à escalabilidade de aplicações paralelas. Para investigar mais a fundo o efeito destes problemas numa aplicação paralela, são sugeridos alguns modos de visualização do perfil de execução de uma aplicação dependendo do problema que mais limita a sua escalabilidade. As visualizações sugeridas consistem maioritariamente de diferentes tipos de flame graphs do perfil de uma aplicação. Duas ferramentas foram desenvolvidas para ajudar a aplicar este fluxo de trabalho na otimização de aplicações Java paralelas. Uma destas ferramentas utiliza o async-profiler para recolher perfis de execução de uma dada aplicação Java. A outra ferramenta utiliza os perfis recolhidos pela primeira ferramenta para estimar possible speedups e produzir todas as visualizações mencionadas no fluxo de trabalho sugerido. Por fim, o fluxo de trabalho foi validado com alguns casos de estudo. O caso de estudo principal consistiu na otimização iterativa de um algoritmo K-means, partindo de uma implementação sequencial e resultando no aumento gradual da escalabilidade da aplicação. Casos de estudo adicionais também foram apresentados para ilustrar possibilidades não abordadas no caso de estudo principal. PA L AV R A S -C H AV E escalabilidade, Java, paralelo, perfil de execução b ABSTRACT Java is currently one of the most popular programming languages. This popularity is, in part, due to the portability it offers which comes from the fact that Java source code is compiled into bytecode which can be executed by a compatible Java Virtual Machine (JVM) in a different system. The JVM can then directly interpret or compile into machine code the Java application. However, this execution on top of a virtual machine creates some obstacles to developers looking to profile their applications. Profilers are precious tools for developers who seek to understand an application’s behaviour by collecting metrics about its execution. Obtaining accurate profiles of an application is important, but they can also be challenging to obtain and to analyse, particularly for parallel applications. This dissertation suggests an optimisation workflow to employ in the pursuit of reducing scalability bottlenecks of parallel Java applications. The workflow is designed to simplify the discovery of the performance problems affecting a given parallel application and suggest possible actions to investigate them further. The suggested workflow relies on possible speedups to quantify the impact of different performance problems. The idea of possible speedups is to estimate the speedup an application could achieve if a specific performance problem were to completely disappear. This estimation is performed using metrics collected during the profile of the parallel application and its sequential version. The set of performance problems considered include workload imbalance, parallelism overhead due to an increase in the number of instructions, synchronisation overhead, memory bottlenecks and the fraction of sequential workloads. These were deemed to be the most common causes for scalability issues in parallel applications. To further investigate the effect of these problems on a parallel application, some visualisations of the application’s behaviour are suggested depending on which problem limits scalability the most. The suggested visualisations mostly consist of different flame graphs of the application’s profile. Two tools were also developed to help in the application of this optimisation workflow for parallel Java applications. One of these tools relies on async-profiler to collect profiles of a given Java application. The other tool uses the profiles collected by the first tool to estimate possible speedups and also produce all visualisations mentioned in the suggested workflow. Finally, the workflow was validated on multiple case studies. The main case study was the iterative optimisation of a K-means algorithm, starting from a sequential implementation and resulting in the gradual increase of the application’s scalability. Additional case studies were also presented in order to highlight additional paths not covered in the main case study. K E Y W O R D S Java, parallel, profiling, scalability. c CONTENTS Contents iii I INTRODUCTORY MATERIAL 3 1INTRODUCTION 4 2S TAT E O F T H E A R T 6 2.1 Performance Evaluation 6 2.2 Common Performance Problems 7 2.2.1 Amdahl’s Law 7 2.2.2 Memory Wall 8 2.2.3 Parallelism Overhead 8 2.2.4 Resource Contention 8 2.2.5 Workload Imbalance 9 2.3 Profiling 9 2.3.1 Instrumentation 10 2.3.2 Sampling 10 2.3.3 Profile Visualisations 10 2.4 Profiling Java 13 2.4.1 Profiling with GetAllStackTraces 13 2.4.2 Profiling with AsyncGetCallTrace 14 2.4.3 Profiling with perf event open 15 2.5 Java Profiling Tools 15 2.5.1 VisualVM 15 2.5.2 Perf 17 2.5.3 Async-profiler 18 2.5.4 Summary 20 II C O R E O F T H E D I S S E R TAT I O N 23 3DEVELOPMENT 24 3.1 Performance Limitations 25 3.2 Workflow 26 3.3 Metrics 30 iii Contents iv 3.3.1 Evaluating the impact of efficiencies 34 3.4 Case Studies 35 3.4.1 K-means 35 3.4.2 Other case studies 41 3.5 Tools Implementation 45 3.6 Limitations of the Work Developed 46 3.6.1 Possible Speedups 46 3.6.2 Profiling Inaccuracies and Overheads 47 3.6.3 Fixed Frequency 48 3.6.4 Spinning 48 3.6.5 Load Imbalance 48 3.6.6 Multiple Parallel Sections 49 4CONCLUSIONS AND FUTURE WORK 50 4.1 Conclusions 50 4.2 Prospect for future work 51 III APPENDICES 54 A T O O L S 55 LIST OF FIGURES Figure 1 Example of a speedup graph 7 Figure 2 Example of an efficiency graph 7 Figure 3 Effect of Amdahl’s law on parallel applications 8 Figure 4 Effect of load imbalance on parallel applications 9 Figure 5 Resulting flame graph generated from a small profile 12 Figure 6 Resulting flame graph generated from a larger profile 13 Figure 7 Resulting call tree obtained with VisualVM by sampling a sequential version of radix sort 16 Figure 8 Resulting call tree obtained with VisualVM by sampling a sequential version of radix sort, expanded on aux sort 16 Figure 9 Resulting flat profile from sampling a sequential version of radix sort with VisualVM 16 Figure 10 Result of profiling, by instrumentation, a sequential version of radix sort with VisualVM 17 Figure 11 Flame graph output out of profiling the sequential radix sort with Perf 17 Figure 12 Flame graph output out of profiling the sequential radix sort with Perf 18 Figure 13 Resulting tree view of profiling the sequential radix sort with Async-profiler 19 Figure 14 Resulting flat profile of the sequential radix sort with Async-profiler 19 Figure 15 Resulting flame graph of profiling the sequential radix sort with Async-profiler 20 Figure 16 Resulting flame graph obtained with perf 21 Figure 17 Resulting flame graph obtained with async-profiler 22 Figure 18 Resulting call tree obtained with VisualVM 22 Figure 20 Clock cycles flame graph of a sequential application 26 Figure 19 General application workflow 27 Figure 21 Comparison of possible speedups 28 Figure 22 Flat profile of the busiest thread 29 Figure 23 In this application, the number of clock cycles of innermost methods is well distributed between different methods, as seen in 23a. Looking at 23b, however, we can see that most clock cycles originate from methods called inside m2, making this method a prime candidate for optimisation. 29 Figure 24 Clock cycles flame graph of the initial k-means implementation 35 Figure 25 Possible speedup of the first optimisation to the k-means algorithm 36 Figure 26 Flat profile of the busiest thread of the first optimisation to the k-means algorithm 36 v 2.2. Common Performance Problems 7 Figure 1.: Example of a speedup graph Figure 2.: Example of an efficiency graph graphs, ideal scalability would see speedup always equal to the number of threads, while for efficiency graphs it would see the efficiency always equal to 1. 2.2 COMMON PERFORMANCE PROBLEMS Many parallel applications cannot achieve an efficiency close to 1. In general, the efficiency of these applications decreases as the number of processing elements increases. The reason for this lack of efficiency is due to the existence of limited resources and intrinsic limitations of the algorithms used [8]. For example, the application may need to share resources between the threads which limits their availability or the algorithm may contain computational work that cannot be distributed evenly between the threads or be made parallel at all. This section classifies and describes common problems found in parallel applications into 5 categories. 2.2.1 Amdahl’s Law A parallel application’s workload can be split into 2 fractions, the sequential fraction and the parallel, or enhanced, fraction. A common performance problem in applications arises from Amdahl’s law which states that the speedup of an application is limited by the fraction of the application that is not enhanced. For parallel applications, this means the sequential fraction of the application will be a constraint on its scalability. Since all of the available processing elements can only be used during the parallel fraction of the application, we can only expect increased performance during this fraction and thus the sequential fraction limits the scalability of the whole application. Figure 3illustrates this problem, where the sequential fraction goes from being the cause of a small portion of application time when running on 1 thread, to being the cause of half of its execution time when running on 4 2.2. Common Performance Problems 8 threads. This performance problem becomes more noticeable as the time spent processing parallel workloads is reduced and for larger sequential fractions. Figure 3.: Effect of Amdahl’s law on parallel applications 2.2.2 Memory Wall The scalability of an application can also be greatly impacted by the memory accesses of the application. If a sequential version of the application already spent a large chunk of its time with memory accesses, the fact that memory accesses are now made concurrently in the parallel application could affect scalability if the memory bandwidth isn’t big enough to concurrently satisfy all memory accesses. Additionally, the parallelisation of an application may sometimes destroy the cache locality that was present in the sequential version or introduce false sharing. This will impact scalability by increasing the miss rate on cache accesses leading to an increase in the number of memory accesses and, consequentially, by increasing the strain on memory bandwidth. This increase would raise the time spent accessing the memory, ultimately increasing the application’s execution time. 2.2.3 Parallelism Overhead Another common performance problem of parallel applications comes from parallelism overhead. This problem emerges from the additional workload required to introduce parallelism to the application such as the creation of execution threads or redundant computations. Since this additional workload needs to be processed, the execution time of the application will not decrease as much as expected. This overhead increases as the number of parallel tasks increases, so the creation of parallel workloads as coarse as possible reduces the impact of parallelism overhead. 2.2.4 Resource Contention To ensure correctness of the parallel implementation, it may be necessary to guarantee exclusive access to some resources. This could result in processing elements having to wait for the release of a resource held by another processing element. When this happens, it creates resource contention overhead, essentially serialising what 2.3. Profiling 9 should be parallel work. This leads to inefficient use of the processing elements available which translates into a lack of scalability. 2.2.5 Workload Imbalance Parallelisation requires the distribution of the parallel workload among the available processing elements. Ideally, this distribution results in an equal workload for all processing elements. However, this is often not the case, especially in coarse-grained parallelism where the parallel tasks are large and few and it becomes harder to split them evenly resulting in load imbalance. This leads to inactive processing elements whilst some parallel workloads are yet to be processed. This could mean the parallel workloads should be more fine-grained to reduce workload imbalance, even though this could increase parallelism overhead. Figure 4illustrates the effects of load imbalance delaying the end of parallel fraction execution. Figure 4.: Effect of load imbalance on parallel applications 2.3 PROFILING Profiling is a form of analysing a program by recording information about its use of the system’s resources. Profiling can be performed while the program is running in the PE’s or not, and during all of its lifetime or any fraction of it. The recorded information can be related to various performance metrics, for example, a profile can show where a program spends time when executing in a PE or where it performs more memory allocations. Profiling is a useful technique for developers to find performance bottlenecks in their applications and support them during program optimisation. When profiling an application, there are several things to keep in mind. Profiling will change a program’s behaviour and we should seek to minimise its impact. The profile obtained may not be representative of an application’s real profile, so it is important to be aware of the obtained profile’s quality to avoid being misled. Profiling can also generate a lot of data which can be problematic when profiling applications running for a long time. Sections 2.3.1 and 2.3.2 discuss the two main methods of obtaining a program’s profile, instrumentation and sampling. Section 2.3.3 introduces techniques for displaying profiles. 2.3. Profiling 10 2.3.1 Instrumentation Instrumentation-based profilers measure occurrences or time inside functions within some instrumented section of the code. To accomplish this, instructions need to be added to the code to identify when functions are called and exited. This method of profiling can be very detailed as it is capable of counting the exact number of function calls and the time spent in these. However, this can cause a big overhead due to the added instructions, which is most noticeable when calling small functions at a high frequency. Additionally, the introduced code may influence optimisation decisions done by compilers which can fundamentally change the profile of an application. Because of these main drawbacks, instrumentation-based profiling may produce very inaccurate profiles of an application, however, it can still be very useful and report information other methods cannot (e.g. sampling). 2.3.2 Sampling Sampling-based profiling operates by collecting the profile information (for example, a call stack) of the inspected program at a given frequency or period, halting the program in this process. This results in a collection of locations the inspected program has been spotted at, from which can be deduced a general profile of the application. This means that we can only obtain an approximation to the real profile of the application. However, sampling-based profiling allows the target program to run with little overhead introduced by the profiler and since the profiler is not as intrusive as in an instrumentation based method, the generated profile may even be more accurate. For this strategy to be reliable, the profiler must collect a significant number of samples to portray an accurate representation of a program’s profile. The number of collected samples can be controlled by the duration of time the profiler inspects the application or the frequency the profiler collects samples of the execution, keeping in mind that higher frequencies incur in higher overhead. In addition, we should also make sure to avoid any bias that may arise from the sampling strategy causing a misrepresentation of the program’s profile. Biases may appear for many different reasons, for example, the frequency of sampling may line up with some periodic process or the method used to collect samples may be biased itself. Some common issues found with sampling-based profiling are the stack reconstruction and identification of inlined methods. Stack reconstruction can be problematic when execution is halted from outside the application and without knowledge of how to walk the stack. If the conventional method of using the base pointer register to identify the boundaries of different functions in the stack is not used by the application, this may result in broken stack traces. These issues will be more detailed for the case of Java applications in section 2.4. 2.3.3 Profile Visualisations The profile of the execution of a program can contain a large amount of information. For it to be of any use, it is important to filter this information and present it in an easy to read format. 2.3. Profiling 11 The following profile of an application will serve as an example of the information contained in a profile which will be used to demonstrate the different visualisations of a profile. The explanation for the different visualisation options treat this profile as if it was obtained via sampling, but they also serve for profiles obtained via instrumentation. This profile contains: • 2 occurrences of function A called inside the main function • 2 occurrences of function B called inside function A called inside the main function • 3 occurrences of function C called inside function A called inside the main function • 1 occurrence of function E called inside function A called inside the main function • 2 occurrences of function B called inside function D called inside the main function Flat Profile View Flat views only take into account the innermost functions of a call stack, essentially ignoring the context of where these functions were called from, by not taking the rest of the call stack into consideration. This means that if, for example, the profile contains a sample with a call stack composed of function B called inside function A called inside the main function, that sample will only account for an occurrence of the function B, regardless of where this function was called from. This visualisation loses some information contained in the profile, such as the prevalence of outer functions during the execution of the application, but it can highlight the presence of functions being used inside multiple other functions. A flat view of the example profile would only give us the following information: • 4 occurrences of function B • 3 occurrences of function C • 2 occurrences of function A • 1 occurrence of function E This view summarised the profile to the innermost functions of each stack. This visualisation option can be especially useful for finding functions with a big number of samples spread between deep and different call stacks. However, it cannot exhibit the impact of outer functions. In the previous example, the flat profile shows that 40% of the samples were found in function B, so optimising this function has the potential of providing the greatest performance improvements, but it fails to show that, for example, function A is found in the call stack of 80% of the samples, so there is no clue as to what performance improvements may be achieved if function A is optimised by reducing its calls to other functions. 2.3. Profiling 12 Call Tree As opposed to the flat profile, a call tree displays the full information of the call stacks in the profile. This type of visualisation can be interpreted as, basically, a tree where a path from the root to the leaves represents a call stack. This visualisation can bring light to the impact that outer functions may have in the application’s execution. On the other hand, it can represent too much information which can easily overwhelm when profiles become too large and diverse. The profile used as an example previously can be presented in the format of a call tree as follows: main function - Total samples: 10(100%); Self samples: 0(0%) function A - Total samples: 8(80%); Self samples: 2(20%) function B - Total samples: 2(20%); Self samples: 2(20%) function C - Total samples: 3(30%); Self samples: 3(30%) function E - Total samples: 1(10%); Self samples: 1(10%) function D - Total samples: 2(20%); Self samples: 0(0%) function B - Total samples: 2(20%); Self samples: 2(20%) This presentation aggregates call stacks with common outer functions. The number of self samples of a function is the number of samples in which such function was the innermost function of the call stack. The number of total samples includes the number of times the function was present in any level of the call stack. In this presentation, it can now be clearly seen the presence of function A in the profile as it is present in 80% of the call stacks. Flame Graph Flame graphs [7] are a specific visualisation method for observing call trees. They represent a call stack as a pile of boxes on top of each other, where each box represents a function. The width of these boxes is proportional to the number of occurrences of its function, which gives emphasis to functions with a higher number of occurrences. These graphs are interactive, so that less prominent methods can still be seen by zooming into them and their number of occurrences be obtained by mousing over them, making these graphs capable of relaying all the information of a call tree. Figure 5displays the flame graph of the example profile presented previously. The call stacks are represented here from the base to the top. This type of visualisation does not offer many advantages when displaying smaller profiles. Figure 6shows the flame graph for a larger profile in which the advantages of using flame graphs are more clear, the most prominent call stacks stand out from the rest and are quickly identified. Figure 5.: Resulting flame graph generated from a small profile 2.4. Profiling Java 13 Figure 6.: Resulting flame graph generated from a larger profile 2.4 P R O F I L I N G JAVA The Java programming language is currently one of the most popular programming languages. This popularity is partly due to the security and portability it offers. To achieve this portability, the programs developed in this language are compiled into bytecode, which is then interpreted or compiled and optimised on top of a Java Virtual Machine (JVM). However, the introduction of this middle step introduces some issues in the process of analysing and optimising Java applications. In the case of a Java application, the profiling process gets tricky due to its execution on top of a JVM. This process gets even more complex when we intend to profile applications with various threads, where the performance problems are usually connected to the hardware properties. In addition to the problems generally found in sampling-based profiling such as stack reconstruction and inlining, some common issues with sampling-based profiling Java applications are the bias caused by safepoint restrictions, tracking native, JVM and kernel calls, identifying interpreted methods and identifying symbols for compiled methods. This section will present the most common techniques for profiling Java applications along with their main advantages and drawbacks. 2.4.1 Profiling with GetAllStackTraces To profile a Java application we can make use of the class Thread offered by the package java.lang containing the function GetAllStackTraces which returns a map of the java stack traces for all live threads. A better option may be the native function GetAllStackTraces offered by the JVM Tool Interface (JVMTI) to collect these stack traces. Both of these functions allow us to easily generate a profile for the execution of a Java application. One of the main advantages of using this technique is the guaranteed support from any JVM. However, there are a few drawbacks to this approach. The function GetAllStackTraces can only operate when all the Java threads are at a safepoint. When the JVM requires the system to be at a safepoint for a VM operation, all threads must stop at the next safepoint 2.4. Profiling Java 14 in its execution and can only resume execution after the VM operation has been performed [5]. When a safepoint is requested, a thread may be in a few different states [4]. These are the ways a thread can reach a safepoint depending on their state for the HotSpot JVM [12]: • When running interpreted code, the thread can reach a safepoint when executing branching/returning byte codes. • When running in native code, the thread does not need to stop its execution and must only stop when returning from the native code if a safepoint state is still required. • When running compiled code, the thread stops when it finds itself in a safepoint poll. These are usually located in method exits and uncounted loops. • When blocked, the thread will not be allowed to return from the block condition until the safepoint operation is complete. This requirement of bringing the threads to a safepoint means we can only sample the threads at specific points in its execution, which may lead to inaccurate samples. For example, when a thread is running compiled code, if the thread is inside an inlined method, the safepoint poll when exiting this method would cease to exist and the thread would stop its execution already outside of this method. Another problem safepoints introduce is the added overhead of bringing the system to a safepoint. Every time the system wants to reach a safepoint, it will take as long as the slowest thread to reach a safepoint. This overhead will be more significant as the number of live threads increases. In conclusion, this method of profiling will collect samples from all threads, whether they’re currently running in the PEs or not. However, this type of sampling may be inaccurate due to the safepoints introducing additional overhead and bias to the profile. This sampling method is also unable to profile kernel, native and JVM code. 2.4.2 Profiling with AsyncGetCallTrace The JVM call AsyncGetCallTrace was initially implemented on OpenJDK JVMs and may not be available in other JVMs. With this call, it’s possible to collect stack traces of Java applications outside of safepoints avoiding the issues present in the GetAllStackTraces method. With this method, a collection of samples can be obtained by sending Linux signals (for example, SIGPROF on a regular interval) to the Java process being profiled with a signal handler registered. This signal would then be caught and handled by a random thread running our Java application on the PEs. While handling the received signal, a call to AsyncGetCallTrace can be safely made to record stack traces. It’s advisable to set the flag -XX:+DebugNonSafepoints to generate extra debugging info for nonsafepoints since, by default, JVMs usually only generate debug information for safepoints. Using this function, we are no longer restricted to collecting samples from safepoints and as a result, we’re able to generate a more accurate profile. On the downside, this function is not part of the JVM specification and is unsupported and undocumented. Using AsyncGetCallTrace we can only profile threads running, 2.5. Java Profiling Tools 15 meaning the time a thread spends waiting for a contended resource cannot be seen as in when using the previous method. As in the previous method, this method is also unable to profile native and JVM code. 2.4.3 Profiling with perf_event_open The system call perf_event_open is a Linux method for collecting stack traces which can also be used to obtain Java stack traces asynchronously. This method allows the capture of native and kernel functions along with the java functions. This function also allows sampling according to various hardware performance event counters, allowing us to obtain profiles displaying various metrics. Hardware performance counters can record information such as instructions retired, the number of clock cycles elapsed, cache misses, etc.. In order to traverse the stack to collect stack traces, this method uses the frame pointer to find the chain of functions forming a call stack. However, by default, JVMs use the frame pointer as a general purpose register as an optimisation. This means that this method will create samples of broken stack traces. To fix this, it’s necessary to include the flag -XX:+PreserveFramePointer when running a Java application. This flag overrides this optimisation, allowing for stack traces to be built. Using this method, we’re collecting stack traces from outside the JVM, and as a result, we cannot differentiate between the different interpreted methods or find the method names of the JIT compiled code. Overall, using perf_event_open can give us a wider scope of what our application is doing, by allowing us to profile JVM, native and kernel functions. On the other hand, this method has some limitations in profiling interpreted Java code and JIT compiled code. 2.5 J AVA P R O F I L I N G TO O L S In this section, a set of profilers usable with Java applications is presented along with the strategies used by these to profile Java applications, their main features, drawbacks and some visualisation options. To display the profilers in action, a sequential implementation of an array sorting algorithm, radix sort, was chosen to be inspected by the presented profilers. 2.5.1 VisualVM VisualVM[1] is one of the most popular Java profilers. This profiler allows for memory and CPU profiling via two methods, sampling based profiling and instrumentation based profiling. Sampling The sampling option of VisualVM uses the method GetAllStackTraces from JVM Tool Interface. For this reason, this method suffers from the safepoint bias problem and it is also unable to profile native or kernel code. The output of this tool can be visualised in a call stack tree format as shown in figure 7. 2.5. Java Profiling Tools 16 Figure 7.: Resulting call tree obtained with VisualVM by sampling a sequential version of radix sort Figure 8.: Resulting call tree obtained with VisualVM by sampling a sequential version of radix sort, expanded on aux_sort In figure 8, we can see that this implementation of radix sort contains the methods named count_digits and place_keys. What we cannot see in this profile, however, is that these two methods call the method digitAt. This method tends to get inlined by the JIT compiler, and for this reason, it cannot be seen inside the calling methods in figure 8because the safepoint polls when exiting this method are lost after inlining. In figure 9we see a flat profile obtained with VisualVM. This visualisation is displaying the 5 hottest methods, the methods with the most total self time, during the program execution. While this visualisation option is simpler, especially when the call is tree extremely deep or complex, it does not provide any context of where the methods were called. So optimising these methods would result in increased performance, but optimising the methods calling these may be a more viable strategy. Figure 9.: Resulting flat profile from sampling a sequential version of radix sort with VisualVM Instrumentation The Profiler option of VisualVM works by instrumentation. By providing the classes we wish to profile, the profiler will count the number of invocations of each method along with their duration. While this method of profiling returns a more detailed profile, the overhead introduced by the instrumentation may skew the obtained results. In figure 10, the output of profiling our sequential implementation of radix sort is shown. With this profiling method, the method digitAt would be visible even if inlined. However, profiling this method would incur in a a huge overhead due to the large number of times this method is invoked. Part II CORE OF THE DISSERTATION 3 DEVELOPMENT Parallel applications often do not achieve ideal speedup due to multiple common limitations that can affect their scalability. The objective of the work developed in this dissertation is to guide programmers in the optimisation of parallel applications, specifically Java applications. This is achieved through the conception of an optimisation workflow and supplementary tools that aid them in quantifying the impact of the limitations affecting a parallel application’s scalability and directing their optimisation efforts accordingly, in order to maximise performance gains. To accomplish this, some performance limitations, deemed to be the most commonly observed performance limitations for parallel applications, are defined in section 3.1. The workflow suggested in section 3.2 is based around the impact of these limitations to identify which one imposes the biggest bottleneck on performance. The workflow consists of a decision tree of actions to perform according to the performance problem that is deemed to be the biggest constraint on the scalability of the application. Depending on which limitation is identified as the biggest bottleneck, it suggests different actions in order to investigate the problem further. The usage of this workflow requires the collection of metrics from the execution profile of the parallel application as well as its sequential counterpart. The impact of the performance limitations on scalability can be estimated using metrics collected by profiling parallel applications and their sequential versions. Their impact is measured using the formulas presented in section 3.3. While the values given by the performance metrics collected may not be fully accurate due to multiple factors, they can still be useful in identifying performance limitations by comparison of their estimated impact. Section 3.4 exemplifies and validates the usage of the suggested workflow in the iterative optimisation process of a given case study. Some extra case studies are also presented in order to highlight additional paths not covered in the main case study. The suggested workflow is supplemented by the tools detailed in 3.5. These tools aid in the collection of the metrics required to follow the workflow for Java applications and offer the visualisation options mentioned in the workflow. Section 3.6 describes some of the existing limitations of the workflow and tools suggested and highlights some scenarios in which these may be inaccurate or unreliable. 24 3.1. Performance Limitations 25 3.1 PERFORMANCE LIMITATIONS Parallel applications seek to use the multiple processing elements available to them in order to increase their performance. An application with good scalability can use its available processing elements to increase its performance, ideally increasing it by a factor equal to the number of processing elements. However, applications might not have ideal scalability due to common performance problems found in parallel applications. There are 5 groups of performance limitations addressed in this work: 1. Sequential fraction 2. Parallelism overhead 3. Memory bottleneck 4. Load imbalance 5. Lock contention The sequential fraction limitation consists of the limitation imposed by Amdahl’s law, this is, the limitation caused by the fraction of the application that is not enhanced, the sequential fraction. This fraction will represent a larger part of the application time as the parallel fraction gets more optimised meaning that further optimisations to the parallel fraction will result in lower performance gains. The parallelism overhead limitation consists of the increase in the number of instructions executed when running the parallel application when compared to the sequential application. This increase in the number of instructions is due to the additional logic necessary to create parallelism and it may appear in the sequential or parallel fractions of the application. The increase in the number of instructions translates into an increase in execution time which will affect the scalability of the application. The memory bottleneck limitation is the limitation caused by an increase in total time waiting for the memory. This increase can be caused by multiple factors. For example, an increase in memory accesses due to lack of cache locality in the parallel application or an increase in concurrent memory accesses resulting in a limitation by the memory bandwidth. The increase in time spent waiting for the memory results in an increase of application time, affecting the scalability of the application. The limitation caused by load imbalance is the limitation imposed by the distribution of an uneven workload to the different processing elements. Since the parallel fraction of an application is only finished when all processing elements finish executing it, a balanced workload will maximise performance gains by lowering the time it takes for the last processor to finish their execution. On the other hand, an unbalanced workload will increase the execution time of the parallel fraction and limit the scalability of the application The lock contention limitation is caused by locks introduced in a parallel application. These locks may be added to force serialised execution of some portion of the parallel fraction. This serialised execution delays the execution of the parallel fraction on some processing elements, resulting in an increase of the execution time of application and affecting its scalability. 3.2. Workflow 26 3.2 W O R K F L OW As mentioned before, parallel applications may suffer poor scalability due to various limitations. To fix scalability issues, it is helpful to have an idea of which limitations are ruining scalability so they can be looked into and mitigated. Identifying these limitations could be achieved by analysing the application’s source code or profiling data which could be a daunting task. The suggested workflow tries to simplify this task by implementing guidelines for optimising parallel applications. The presented workflow helps in identifying application’s major performance problems and suggests an action in accordance to locate the specific problem causing the bottleneck. The suggested workflow is presented in figure 19 and starts with the profiling of an initial sequential application with the objective of identifying its hottest methods and optimise them in order to obtain the largest performance gains. There are multiple ways of displaying the profile of an application, but the flame graph view is suggested because of its readability, giving a larger visibility to the hottest call stacks, the ones we seek to optimise. Figure 20 displays the clock cycles flame graph of a sequential application where the number of clock cycles spent inside the method m1 represents about 85% of the total number of clock cycles of the whole application. The fraction of clock cycles spent on a call stack has a direct correlation to the fraction of time spent on it, so the number of clock cycles is a good metric for finding the hottest methods of an application. Figure 20.: Clock cycles flame graph of a sequential application After identifying the application’s hot spots, we should look into how these can be optimised. In the case of figure 20, method m1 should be one of the methods looked into for optimisations since it represents a large chunk of the application, and so, the optimisation of this method has the possibility of returning the greatest performance increase. If we choose to optimise the application without resorting to parallelisation, we can then profile the optimised application to look for its hot spots and repeat this process again. However, if we decide to turn to parallelisation to improve the application’s performance, we can then profile this new parallel application and compare it to the old sequential application to obtain information about the scalability of the parallelisation. The scalability of a parallel application may be affected by different problems, and to mitigate the impact of these problems, different actions can be taken. Figure 21 exemplifies the comparison among speedup lines of different groups. This comparison is used to quickly identify the biggest limitations to an application’s speedup over a different number of threads. In this case, the speedup of the application can reach the highest values if the sequential fraction of the application is reduced (speedup with no sequential fraction line in the figure). The current speedup line shows the speedup obtained with the current parallelisation and is obtained by comparing the parallel application with its sequential version. 3.2. Workflow 27 Sequential application Flame graph Parallel application Speedup graph Busiest thread flat profile Lock contention flame graph Instructions flame graph Clock cycles flame graph Cache misses flame graph Optimised parallel application Profile app Optimisation without parallelisation Parallelisation of hottest method Profile app Speedup with no lock contention is the highest Identify most contended locks and decrease their use Speedup with no parallelism overhead is the highest Identify and decrease overhead Speedup with no sequential fraction is the highest Identify and optimise hottest method Speedup with no load imbalance is the highest Identify most unbalanced methods and balance them Speedup with no memory bottleneck is the highest Identify increases in cache misses and seek to lower their occurrence Profile application Figure 19.: General application workflow 3.2. Workflow 28 Since the remaining speedup lines mostly overlap the current speedup line, solving any remaining performance limitation won’t improve the application’s speedup as much. Figure 21.: Comparison of possible speedups If the speedup graph implies that the sequential fraction is the most limiting factor of the application’s global speedup, as in figure 21, then it means the sequential portion of the application started to take a bigger chunk of the application’s time as the parallelised portion’s execution time shrunk. In this case, the workflow suggests we should look at the busiest thread flat profile (figure 22). This graph allows us to have a better understanding of the impact of the sequential fraction of the application by comparing the number of clock cycles spent on innermost methods of the sequential fraction of the application and the parallel fraction of the busiest thread over the execution of the application for different numbers of threads. This graph essentially displays the innermost methods with the highest number of clock cycles, suggesting that these should be the ones to be optimised. In the example of figure 22, the number of cycles spent on the method m1 in the busiest thread gets reduced to the point that further optimisations to it will have little impact in the performance of the whole application as the number of threads increases. In this case, m2 becomes the most attractive method to optimise given its higher number of clock cycles when running the application on more than 10 threads. In the case that the innermost methods don’t reveal much, as in the case of figure 23a, a clock cycles flame graph of the sequential fraction of the application can be used to have a better idea of the hottest methods stack. Figure 23b allows us to see that optimising m2 could provide a good performance improvement, while the flat profile can’t show us this detail. 3.2. Workflow 29 Figure 22.: Flat profile of the busiest thread (a) Flat profile of the busiest thread (b) Clock cycles flame graph of the sequential portion of an application Figure 23.: In this application, the number of clock cycles of innermost methods is well distributed between different methods, as seen in 23a. Looking at 23b, however, we can see that most clock cycles originate from methods called inside m2, making this method a prime candidate for optimisation. After optimising this parallelisation by decreasing the sequential fraction of the application, we can look into the speedup graph of the new application to discover its biggest performance limitations and seek to optimise accordingly. 3.3. Metrics 30 To address other performance limitations, flame graphs are also suggested to look deeper into each limitation, changing only the metrics presented in the flame graph. For applications where load imbalance is the bottleneck, there should be a visible difference in the number of clock cycles of the unbalanced methods between the different threads in a clock cycles flame graph. Comparing cache misses flame graphs for different levels of parallelism, displaying in which call stacks memory accesses increase, helps in identifying where memory access limitations may occur from. To identify the sources of parallelism overhead, a comparison between instructions flame graphs is necessary to pin down increases in instruction count of different methods. If lock contention is the culprit of bad scalability, a lock contention flame graph displays the time spent waiting on different locks by each thread, revealing where contention mostly occurs. 3.3 METRICS For each group of performance limitations presented previously, an efficiency metric was developed to allow the estimation of the possible speedup lines used in the workflow. If the efficiency of a group equals 1, that means such group doesn’t create any inefficiency on the application’s performance. However, we cannot simply compare these efficiencies in order to find which group is the most harmful to the overall speedup because some groups may be more impactful than others, regardless of having a higher efficiency. To measure each efficiency group’s impact on the overall speedup of the application, we can estimate the achievable speedups of the application if such group caused no inefficiencies. By comparing these possible speedups without inefficiencies we can determine which group is being the biggest bottleneck on the application’s performance and optimise accordingly to obtain the largest performance increases. In this section we present the implementation of the efficiency groups used in the suggested workflow, how their efficiencies are computed and how their impact on the speedup of an application can be compared. The efficiencies presented in this section require profiling the number of clock cycles, #CC, and instructions executed, #I, of a sequential application and its parallelised version, identified by the subscripts Sand P, respectively. The number of clock cycles and instructions of these profiles must also be divided into the ones ran or to be ran in parallel, identified with the subscript p, and the ones ran sequentially in both applications, identified by the subscript s. For example, #ISp is the number of instructions executed in the sequential application of methods to be made parallel. The profile also must be able to differentiate the number of clock cycles and instructions of different threads. To obtain results regarding lock contention, the profile of the time spent waiting on locks should also be available for the parallel application, since the impact of this limitation could not be accurately estimated with the number of instructions or clock cycles. All metrics used to compute the efficiencies are described in table 2. This section also assumes that both applications, sequential and parallel, run on the same fixed processor clock rate. Another assumption is that the machine running the parallel application has at least one core available for each thread of the parallel application, all threads suffer the same degree of parallelism overhead and lock contention times and that the busiest thread is always the busiest thread whenever any parallel work is distributed. 3.3. Metrics 31 Primitive Metric Description #ISs Number of instructions executed on the sequential fraction of the sequential application #ISp Number of instructions executed on the parallel fraction of the sequential application #IPs Number of instructions executed on the sequential fraction of the parallel application #IPp Sum of instructions executed on the parallel fraction of the parallel application by all threads #CCSp Number of clock cycles spent on the parallel fraction of the sequential application #CCPp Sum of clock cycles spent on the parallel fraction of the parallel application by all threads #CCPpM Number of clock cycles spent on the parallel fraction of the parallel application by the busiest thread TPplock Total time spent waiting on locks by all threads on the parallel fraction of the parallel application TPpexec Total time spent by all threads on the parallel fraction of the parallel application Derived Metric Description #CCSNumber of clock cycles spent on the whole sequential application CPISs Average CPI of the sequential fraction of the sequential application CPIPs Average CPI of the sequential fraction of the parallel application CPISp Average CPI of the parallel fraction of the sequential application CPIPp Average CPI of the parallel fraction of the parallel application Table 2.: Metrics used to compute efficiencies 3.3. Metrics 32 Sequential Fraction - Parallel Fraction Efficiency The parallel fraction efficiency aims to quantify the performance limitation that arises from Amdahl’s law stating that the maximum speedup achievable with parallelisation is limited by the sequential fraction of the application. This efficiency, or enhanced fraction, is the proportion of execution time that the methods to be made parallel occupy on the sequential application. Since we’re assuming these applications are running on a fixed processor frequency, the fraction of execution time will be equal to the fraction of clock cycles. Equation 3evaluates the parallel fraction efficiency (EPF) as the fraction of clock cycles spent executing instructions to be made parallel (#CCSp) out of the clock cycles spent during the execution of the whole sequential application (#CCS). EPF = #CCSp #CCS (3) Parallelism Overhead - Instruction Overhead Efficiency The parallelisation of an application may introduce some noticeable overhead due to added instructions necessary for parallelisation. These additional instructions may appear in the sequential and parallel fractions of the application and depending on where these instructions appear, they’ll have a different impact on the overall speedup of the application due to other factors such as the parallel fraction efficiency and the number of processors used. The instruction overhead efficiency aims to quantify the parallelism overhead by measuring the increase in the total number of instructions. Since the increase in the number of instructions has a different impact on the scalability of an application depending on which fraction of the application this increase occurs, the instruction overhead efficiency is split into two efficiencies, the instruction overhead efficiency on the sequential fraction and on the parallel fraction. The instruction overhead on the sequential fraction efficiency, ESOI, in equation 4is obtained by dividing the number of instructions executed in the sequential fraction of the sequential application, #ISs, by the number of instructions executed in the sequential fraction of the parallel application, #IPs. ESOI= #ISs #IPs (4) The instruction overhead on the parallel fraction, EPOI, shown in equation 5is the ratio between the number of instructions executed in the parallel fraction of the sequential application, #ISp, by the number of instructions executed in the parallel fraction of the parallel application, #IPp. EPOI= #ISp #IPp (5) The efficiency of the instruction overhead on the parallel fraction assumes that the increase in the number of instructions is distributed evenly between all threads. 3.4. Case Studies 39 Figure 30.: Possible speedup of the third optimisation to the k-means algorithm Figure 31.: Comparison between the real and calculated speedups of the third optimisation to the kmeans algorithm Figure 32.: Profiling overheads of the third optimisation to the k-means algorithm Figure 33.: Number of cache misses of the third optimisation to the k-means algorithm 3.4. Case Studies 40 Figure 34.: Possible speedup of the fourth optimisation to the k-means algorithm Figure 35.: Instruction flame graph of the fourth optimisation to the k-means algorithm Figure 36 shows the speedup lines for an improvement on the previous application in which some of the parallelism overhead was reduced by removing some unnecessary management of data structures (removing the need for the Map structure). This results in the sequential fraction being, again, the main limitation on the scalability of the application, meaning we should look, again, into the sequential fraction of the application to improve the scalability of the application. 3.4. Case Studies 41 Figure 36.: Possible speedup of the fifth optimisation to the k-means algorithm 3.4.2 Other case studies This section presents some other case studies with the intention of covering some paths in the decision tree of the workflow not observed in the k-means case study. Figure 37 presents the possible speedups for a molecular dynamics simulation based on an implementation from [15]. This implementation has its scalability limited mostly by the memory bottleneck. This is because the number of cache misses in the parallel application can reach 100 times more misses as the number of threads increases, which could be seen by comparing cache misses counts of the cache misses flame graph of the sequential and parallel applications, but can also be seen with a wider perspective in a graph displaying the total count of cache misses over different levels of parallelism as shown in figure 38. Figure 39 shows the possible speedups for the same application with a modification to the algorithm that causes the uneven distribution of the parallel workload. In this case, the application still suffers a limitation due to memory bottleneck but also due to load imbalance. The load imbalance can be spotted in figure 40, a clock cycles flame graph of the application running with 4 threads, where the busiest thread runs for almost 10 times more clock cycles than the thread with the smallest workload. 3.4. Case Studies 42 Figure 37.: Possible speedup of the MD algorithm Figure 38.: Cache misses of the MD algorithm Figure 39.: Possible speedup of the unbalanced MD algorithm 3.4. Case Studies 43 Figure 41.: Possible speedup of the first ray tracing algorithm Figure 42.: Possible speedup of the second ray tracing algorithm Figure 40.: Clock cycles flame graph of the unbalanced MD algorithm The following two applications implement a ray tracer algorithm also based on the implementation from [15]. The first one implements its own barrier for synchronisation. The second application implements synchronisation by using CyclicBarrier found in Java’s library. The possible speedups for these applications can be found in figures 41 and 42, respectively. These graphs suggest both applications seem to be limited by memory accesses. However, the first implementation seems to also be limited by overhead introduced with the parallelisation, while the second implementation sees load imbalance as the second biggest limitation of scalability. Inspecting a portion of the instructions flame graph of the first application, in figure 43, we see the additional instructions introduced by the barrier. For each thread, there are 2 notable stacks, one corresponds to the ray tracer algorithm and the other to the barrier. The stack related to the barrier creates the instruction overhead due to busy waiting and hide the load imbalance. This flame graph also shows an instruction imbalance, seen by the fact that the stacks of the different threads have different widths, which did not translate into a workload imbalance. 3.4. Case Studies 44 The profile of the second application does not display stack samples referring to the barrier. This makes it so that there is no apparent instruction overhead and reveals the workload imbalance, as seen in its clock cycle flame graph, figure 44. This workload imbalance is not due to an imbalance in the number of instructions of each workload, but due to an imbalance in CPI of the workloads, as it would be seen in a cache misses flame graph. Figure 43.: Fraction of the instructions flame graph of the first ray tracing algorithm 3.5. Tools Implementation 45 Figure 44.: Clock cycles flame graph of the second ray tracing algorithm 3.5 TOOLS IMPLEMENTATION To support the suggested workflow, two tools were built, a profile collector and a profile visualiser. The first consists of a python script making use of async-profiler to collect stack trace samples of sequential and parallel versions of a program. The reason for choosing this profiler was due to its capability of profiling every required metric, easy attachment to the application, identification of Java, JVM, native and kernel functions and the low overhead it introduces. The path for async-profiler should be specified inside the script. This script runs the given sequential and parallel programs multiple times to collect multiple metrics separately. It profiles cycles, instructions, cache-misses, wall time and time spent on locks in different executions for each number of threads and the number of iterations intended (used to create an average profile). The result of this script is a file with the profile of every metric and for every number of threads and iterations. Each profile consists of a list of stack traces accompanied by a number which represents the estimated count of a metric. The usage of the profile collector is shown in appendix A. The profile visualiser can be used to generate visualisations to follow the presented workflow. This tool, also implemented in python, takes as input the output of the profile collector as well as 2 regular expressions to identify the parallel stack samples of the sequential and parallel applications. The definition of these 2 regular expressions is important to classify samples as sequential or parallel and thus be able to perform the possible speedup calculations, which are to be performed using the equations presented previously. The visualiser starts by parsing the given file and storing the profile of each program execution in a tree data structure. This structure was chosen to simplify the drawing of flame graphs and speed up the process of looking up which methods are called inside other methods and how many total samples this equates to. Each node of 3.6. Limitations of the Work Developed 46 the tree identifies the name of a function, its sample count, if it belongs to the parallel fraction of the application and the nodes of functions called inside this function. The sample count is the number of samples collected in which the function is sampled as being the innermost function. After the file is parsed, resulting in multiple profiles of different metrics for different numbers of threads stored in trees, the efficiencies used to measure the impact of the different limitations are calculated using the formulas presented previously, except for the lock contention efficiency. Due to big overheads when profiling the application for locks, sometimes resulting in lock waiting times per thread higher than the total application time when it’s not being profiled, the time spent waiting on locks is multiplied by the ratio between the execution time of the application when it’s being profiled for wall time and lock time. This is an attempt of trying to find what the time spent on locks would be if lock profiling had the same overhead as wall time profiling. This attempt is flawed because the overhead is not consistent throughout the application. But while it may be a flawed solution, it does bring the calculated speedup of the applications closer to their real speedup. After calculating possible speedups, the application provides the options shown in figure 45. General metrics displays a graph showing the evolution of the number of clock cycles, instructions, CPI and cache-misses with the increase in the number of threads. Execution times displays the execution times of the application with and without profiling, allowing the comparison of profiling overheads. Possible speedup gains displays the possible scalability gains by completely removing specific limitations. Flat profile of the busiest thread option displays a graph useful for comparing the fraction of clock cycles spent on the sequential and parallel fractions as the number of threads increases. The flame graphs option can display flame graphs for clock cycles, instructions, cache misses, wall time and time spent on locks for any number of threads. 3.6 LIMITATIONS OF THE WORK DEVELOPED The aim of the work developed during this dissertation was to create a methodology and tools capable of aiding programmers in the process of increasing a parallel application’s scalability. The resulting work aims to accomplish this by pointing the biggest scalability bottlenecks of a given application, and with this information, help the programmer in deciding where to seek optimisations. While the presented work is able to achieve its goals, especially for simpler applications, it tends to fail in some specific scenarios. This section exposes some of the issues that may affect the effectiveness of the solution suggested. 3.6.1 Possible Speedups There is no guarantee that the estimated possible speedup values can be achieved, or even that aiming to reduce the performance problems responsible for the biggest scalability bottlenecks achieves the largest performance gains. For example, an application may suffer performance limitations mostly due to delays in memory access. This limitation is usually impossible to overcome completely. If, in practice, only a small fraction of the possible speedup can realistically be achieved, seeking to make optimisations against this performance limitation may be futile compared to other limitations. 3.6. Limitations of the Work Developed 47 Figure 45.: Profile visualiser’s main menu Another issue is that fixing some performance problems, may exacerbate the impact of others. For example, the sequential fraction of an application could always be considered to be a part of the parallel fraction but with maximum imbalance (only one thread executing all the parallel work). This would result in the total removal of the sequential fraction, but no increase the application’s performance due to the imbalance increase of the parallel fraction of the application. To predict the speedup improvements from removing multiple limitations, multiple efficiencies need to be considered equal to 1. Trying to predict the possible speedup increases from removing multiple limitations by merely looking at the possible speedups obtained from removing single limitations is challenging due to the existent cross impact of the limitations. In a similar work to the possible speedups approach which uses speedup stacks [14], the speedup losses associated with each limitation can be summed. Speedup stacks essentially attribute fractions of the difference between ideal speedup and real speedup to specific problems by measuring specific time overheads. 3.6.2 Profiling Inaccuracies and Overheads This methodology will always be affected by the profiling inaccuracies and overheads introduced by the profiler used. Currently, the biggest impact caused by the profiler used is the overhead introduced by lock profiling which is based on instrumentation to capture Java object monitors and ReentrantLocks. This profile is used to estimate the impact of lock contention, so applications whose scalability is affected noticeably by lock contention 3.6. Limitations of the Work Developed 48 suffer from a bigger inaccuracy in the estimation of possible speedups. This inaccuracy is more pronounced when locks are acquired more frequently in the application since this results in higher profiling overheads. To be aware of the possible inaccuracies in the estimation of possible speedups, it can be helpful to observe overheads introduced by profiling. 3.6.3 Fixed Frequency This work assumes the PEs all run at the same fixed clock frequency throughout the whole application’s execution. If an equal fixed frequency cannot be guaranteed, then the estimated calculated speedup becomes more inaccurate, however the overall methodology can still be applied. This problem affects mostly calculations involving the impact of lock contention because these are estimated using execution times, which are dependent on clock cycle frequency, instead of number of clock cycles or instructions. Variable frequency can also affect the difference between the observed speedup of the application and the estimated speedup which should be equal to the observed speedup. The estimated speedup is the basis from which all possible speedups are calculated, so it is important for it to reflect the real speedup of the application. 3.6.4 Spinning When threads are forced to wait for each other due to resource contention or load imbalances, they can either spin or be scheduled out of execution. Spinning results in the increase of the instruction count of the application and the incorrect attribution of a fraction of the scalability issues to parallelisation overhead. To overcome this issue, it is possible to remove stack samples referring to spin locks from the profile to obtain similar profiles to the applications that schedule their threads out of execution. However, this approach was not used due to the fact that removing these stack samples reduces the profile’s information and also because when there is a significant amount of spinning for a particular application, it can easily be detected by inspecting the instructions flame graph. 3.6.5 Load Imbalance Load imbalance is currently estimated by comparing the number of clock cycles of parallel workloads executed by the busiest thread with the total number of clock cycles of parallel workloads executed by all threads. This method of calculating load imbalance can be inaccurate if parallel work is issued multiple times. If there exists more than one parallel section in an application and the busiest thread is not always the busiest for all parallel sections, then the estimated load imbalance will be lower than its real impact. This happens because the busiest thread is used as a reference to the moments any thread is executing the parallel workload, which is only valid if the busiest thread is also busy whenever any other thread is busy. To overcome this problem, there should be some reliable method of obtaining the number of elapsed clock cycles whenever any thread is executing parallel work. As it stands, the overall busiest thread is used as a A TOOLS Figure 46.: Profile collector’s usage 55