hyPACK-2013 Mode 1 : Performance Visualization Tools : Multi-Core Processors

In writing efficient message-passing programs, one must take into consideration a number of factors. Many times, these factors are at odds with each other, and a careful balance needs to be derived. Key to successful message-passing programming (as well as ordinary sequential programming) is the selection of the appropriate parallel algorithm. Various scientific problems exhibit the same type or different amount of concurrency in parallel algorithm. Concurrency (or parallelism as it is most frequently referred to) is of paramount importance in parallel programming, and its detection and specification is one of the two key steps in the design of parallel algorithms (data and task distribution is the other). Message-passing programs need to effectively distribute the various data-structures that are manipulated during the execution of the algorithm as well as the computation among the processors. By properly distributing the data-structures and the computation, a program can reduce the communication overhead and increase the utilization of the parallel computer.

Thus, in order to be suitable for programming using message-passing, parallel algorithms must also specify data and/or task distribution. In the rest of this section, we discuss the various properties that a parallel algorithm must have so that a message-passing program implementing this algorithm will be able to attain high performance on a wide range of clusters. Also, the tool can provide good insight for such kind of parallel programs to know the performance issues. These properties can be used both as a guide in evaluating the potential performance of competing parallel algorithms as well as a framework to be used in developing effective message-passing parallel algorithms. The tools can assist the user in giving accurate information on performance and scalability issues of the programs.


Concurrency     Decomposition     Load Balance     Overheads          

Maximize Concurrency     Equal Workload       Maximize Data Locality      

Minimize Frequency of Data Transfers

Concurrency: In general, given a single task, it is possible to decompose and map it to processors in many different ways. Some of these yield better performance than others. Furthermore, different decompositions and mappings may yield good performance on different computers for a given problem. It is therefore crucial for programmers to understand the relationship between the underlying machine model (SIMD / MIMD) and the parallel program to develop efficient programs. The decomposition methods that help us discover tasks that can be done concurrently, methods for mapping these tasks to processors so that the processors are efficiently utilized, and methods for handling and reducing interactions among tasks so that the processors are all doing useful work most of the time. The type of parallelism that is result of identical operations being applied concurrently on different data items is called data parallelism. Besides the data parallelism, there are task parallelism and stream parallelism. Combinations of tasks and Data parallelism often allow us to utilize the coarse granularity inherent in task parallelism with the granularity in data parallelism with the fine granularity in data parallelism to effectively utilize a large number of processors.

Decomposition : For many problems, the underlying task graph naturally contains sufficient degree of concurrency. Given such a graph, tasks can be scheduled on multiple processors to solve the problem in parallel. Unfortunately, there are many problems for which the task graph consists of only one task, or multiple tasks that need to be executed sequentially. For such problems, we need to split the overall computations into tasks that can be performed concurrently. The process of splitting the computations in a problem into a set of concurrent tasks is referred to as decomposition. A good decomposition should have the following steps.

Decomposing a problem effectively is of paramount importance in parallel computing. Without a good decomposition, we may not be able to achieve to a high degree of concurrency, making it impossible to really exploit parallelism and reduce the amount of time required in solving a problem. These techniques are broadly classified as recursive decomposition, data decomposition, exploratory decomposition, and speculative decomposition. Data decomposition is a powerful method for deriving concurrency in algorithms that operate on large data structures. In the first step, the data (or the domain) on which the computations are performed is partitioned, and in the second step, this data partitioning is used to induce a partitioning of the computational into tasks. These tasks generally perform similar operations on different data elements. Hence, data decomposition often leads to data level parallelism. The partitioning of data can be performed in three ways: Partitioning Output Data, Partitioning Intermediate Data, and Partitioning Input data.

Load-balance : Given a set of tasks and a set of processors there are many ways of performing this mapping. In deciding which mapping is better we must focus on which one better achieves the following two objectives.

• The amount of computation assigned to each processor is balanced so that some processor does not idle when others are executing tasks
• The interactions among the different processors is minimized, so that the processors spend most of the time in doing work that is essential for solving the problem even on serial computers.

Load balancing algorithms can be classified into two categories. Static and dynamic load balancing. Static load balancing techniques distributes the work among processors prior to execution of the algorithm. Dynamic load balancing techniques distribute the work among processors during the execution of the algorithm. Algorithms that can be load-balanced statically are in general easier to design and program. On the other hand algorithms that require dynamic load balancing are somewhat more complicated. However, there are problems in which we cannot statically partition the work among the processors. There are three general classes of problems that fall into this category. The first class consists of problems in which all the tasks are available at the beginning of the computation, but the amount of time required by each task is different and cannot be determined easily. The second class consists of problems in which tasks are available at the beginning but as the computation progresses, the amount of time required by each task changes. The third class consists of problems in which tasks are generated dynamically. In these class of problems, a static work partitioning is either impossible (e.g. first class) or can potentially lead to serious load imbalance problems (e.g. second and third classes). The only way to develop efficient parallel programs for these classes of problems is if we allow dynamic load balancing. That is during execution of the program, work is dynamically transferred among the processors that have a little work or no work.

Overheads : (Idling Overheads & Data sharing Overheads) Given a set of tasks and a set of processors there are many ways of mapping onto the performance on parallel computer. One must focus on the mapping, which gives good results in a parallel algorithm that yields the highest performance. Ideally, user will like to develop a parallel program that is able to achieve linear speedups. The time that is required by the parallel algorithm but is not essential to the serial algorithm is referred to as overhead due to parallelization. Minimizing these overheads is critical in developing efficient parallel algorithms. Parallel algorithms can potentially incur three types of overheads. The first is due to idling, the second is due to data sharing and synchronization, and the third is due to extraneous computations. We describe some of these overheads in detail.

Idling Overheads : Processors can become idle for three main reasons. The first reason is due to load imbalances, the second is due to computational dependencies, and the third is due to interprocessor information exchange and synchronization. Computations in which the work is equally distributed among the processors are called load balanced. If the work is not load balanced, then the processors with less work will finish first and stay idle while waiting for the processors with more work to finish with their computations.

For some problems, we can easily develop parallel algorithms that are load-balanced; however, for other problems designing load-balanced algorithms significantly challenging. In simplest case, the amount of work performed by each task is the same. However, there are some problems in which the amount of computation per task is significantly different and it is not known prior. Also, for many problems, distributing the computations equally among the processors is not sufficient ensure that idling is eliminated. This is particularly true for computations in which there are dependencies between tasks.

In fact, the loads before and after synchronization may be different which results in significant overheads. Minimizing idling among the processors is critical, since every time a processor becomes idle, it does absolutely nothing towards the solution of the problem.

Data Sharing Overheads : The sharing of data often leads to additional overheads that are inherent to the parallel algorithms, They must be minimised as they directly affect the performance achieved by this algorithm. Depending on the underlying architecture, data sharing can take different forms. On distributed memory machines, data is initially partitioned among the processors. Explicitly sending and receiving messages achieve data sharing. In this framework, the cost of data sharing is rather explicit, and minimizing the data sharing overheads directly translates to reducing the communication overhead.

On shared address-space machines, data sharing is often performed implicitly. Data is initially partitioned among the processors. In this type of architectures, the data is stored in the shared memory and every processor can read and write to them. Even though the data is accessible by all processors but data sharing overheads still exists. Data sharing overheads become worse when shared data needs to modify the data at a time and possibly no processor is reading the data while the modification is taking place. Developing algorithms that minimize data sharing overheads often involves intelligent task decomposition, task distribution, initial data distribution and proper scheduling of the data sharing operations, all of which play an important role for performance of a parallel program.

Parallel algorithm can potentially perform two types of extraneous computations. The first type consists of non-essential computations that are performed by the parallel algorithm but the serial program does not require them. In a parallel algorithm, non-essential computations often arise either because of speculative execution or because of exploratory execution between the processors. In some applications, the processors may end up in doing redundant work. In general, performing frequent processor interactions to check whether or not similar work has been already generated can eliminate redundant computations.

Maximize Concurrency : Concurrency provides an abstraction to simple concurrent for implementations software algorithms or applications that are naturally parallel. when multiple software threads of execution are running in parallel, it means that the active threads are running simultaneously on different hardware resources or processors of computing system. Parallel algorithms, irrespective of the programming language used to implement them, should be able to utilize effectively a large number of processors. Many times the algorithm used can limit the amount of parallelism that can be exploited. Often, simply having more processors performing the computations previously performed by a single processor can increase concurrency. Concurrency in Multi-threaded programs depends upon both hardware and software. Designing optimized way of managing the shared resources used at a given time is important. In other words, efficient resource utilization is the key to maximize the performance of computer resources.

Equal Workload : Parallel algorithms should effectively utilize the hardware resources to be able to solve the given problem in the least amount of time. This directly implies that each processor must perform an equal amount of work. In parallel computing terminology this is referred to as the computation being load-balanced. Computation is load-balanced when each processor performs the same amount of computation, the same amount of communication, requires the same amount of memory, and spends minimal amount of time idling while it is waiting for messages. If different processors do different amount of work, then all processors have to wait until the processor with the most work finishes.

Maximize Data Locality : Research in parallel algorithm design has developed a variety of techniques that can be often used to reduce the communication and increase the data-locality. One commonly used technique is to replicate data that is frequently accessed but not changed on all the processors. Data replication is very powerful and can significantly reduce the amount of communication. However, care must be taken to ensure that data-replication does not significantly increase the aggregate memory requirements of the algorithm. Another technique that often decreases the amount of time spent in communication is to increase the amount of work performed by each processor by using fewer processors. This approach essentially builds data locality by simply assigning more data elements to each processor. Note that this approach is in direct conflict with the objective of using a large number of processors and exploit as much concurrency as possible. Parallel algorithms and programs should be developed so that they can effectively operate on a wide range of processors.

Minimize data Transfer : Selecting a parallel algorithm that minimizes the frequency of data transfers is preferable, even if it does not reduce the overall volume of data being transferred. This is usually achieved by first gathering the data that needs to be of time required to transfer the data. Transfer of data is also highly desired in sequential algorithm, which is similar to minimizing communication. On a serial computer, every time a word not residing in the cache is accessed, a predetermined number of words equal to the size of the cache-line are transferred from the main memory to the cache memory. Effective sequential algorithms must use most of these words otherwise significant bandwidth is wasted.

Debugging Multi-Threaded Applications - Overview: Multi-threaded applications are inherently more complicated than single-threaded applications. The bugs may or may not surface when running under the debugger. Multi-threaded bugs are very sensitive to the timings of events in an application.

Commercial multi-threaded tools such as Intel Thread Checker, Intel Vtune Performance analyzer, Sun Studio and Etnus - total View Debugger and Open Source Tools such as MPI Performance Analyzer may provides quite lot of clue to application developer to find the reasons for failure of the program as well as enhance the performance of the program on Multi-core processors. The common debugging tools and thread checker may assist the user to know abnormal behavior of multi-threaded program. Also, obtaining correct results for multi-threaded program is difficult due to common errors in multi-threaded program such as data race conditions and synchronization issues.

Debugging : The common coding errors that cause the multi-threaded program to fail should be investigated. Two categories of bugs founding multi-threaded applications are synchronized bugs and performance bugs. Synchronization bugs include race conditions and deadlocks that cause unexpected and incorrect behavior. Performance bugs arise from unnecessary thread overhead due to thread creation or context switch overhead, and memory access patterns that are suboptimal for a given processor's memory hierarchy. There are debugging synchronization bugs that cause application to fail and information such as accessing the shared resources at the time of failure and at the time of access to shared resources.

In most of the multi-threaded applications, the sequence of events that lead to a race condition or deadlock situation is critical in determining the root cause of multi-threaded bug. Using trace buffer, which is a mechanism for logging events that the developer is interested in monitoring, may help to identify the reasons of failure of the code. Tracepoints are used, as part of debugger and a tracepoint is similar with the concept of a breakpoint. A tracepoint is similar to a breakpoint except the instead of stopping program execution when the applications program counter reaches that point, the debugger takes some other action. This action can be printing a message or running other function. For POSIX threads, debugging can be accomplished by using the GNU Project Debugger (GDB). The GDB provides a number of capabilities for debugging threads as given below. Thread specific breakpoints, Listing of all threads in the system, the ability to switch between threads, the ability to apply commands to a group of threads, the ability to apply commands to a group of threads and automatic notification when new threads are created

Thread Checker: It is necessary to use proper compiler flags to produce threaded-safe code and ensure that the results are sequentially correct before use the thread checker. Most of the commonly used thread checkers identify the following.

• The thread checker usually collect the data and analyze the various common errors of multi-threaded program. The results of the analysis main focus on errors observed, warning messages based on trace data. It also provides a suggestion of possible causes for the threading errors, and suggested solutions with one-click diagnostic help.
• The thread checker is used with the compile support on the target system. Some thread checkers can do analysis of applications that rely on dynamically linked libraries (DLLs) for which the source code is often unavailable.
• When the thread checker is linked to the threaded program, it relies on instrumentation and usually runs slower than it does without instrumentation.
• Thread checker gives an even better understanding about the specific variables on each line, functions, and context.
• Identify the commonly errors in Multi-threaded programming environment such as Data races, and deadlocks that may be due to synchronization issues.
• Identify the stalled threads and critical section - abonded locks.
• Verification of results to compare the non-threaded and threaded results in the debugging environment of Multi-threaded programs.
• Creates diagnostic messages for places in a program where its behavior in a multi-threaded environment is potentially nondeterministic.
• Identify the threaded bugs to the source code line where the bug occurs.

Upshot (Public Domain Tool )  

Upshot is a parallel program performance analysis tool that comes bundled with the public domain mpich implementation of MPI. Upshot is a trace analysis and visualization package. By linking our source code with appropriate libraries we can obtain information on the time spent by our program in each MPI function. i.e trace events can be generated automatically by using MPE library -mpilog which comes with the freely available MPICH implementation and provides a number of useful facilities, including debugging, logging, graphics, and some common utility routines to create logfiles SLOG/ALOG/CLOG. Alternatively, the programmer can insert event-logging calls manually. Upshot is used to display logfiles ALOG (event based logging format).

Features of Upshot:

• Provides a unified view of the profiling data generated by each process
• Modifies the time stamps of events on different processes so that all the processes start and end at the same time.
• Provides a convenient form for visualizing the profiling data in a Gantt chart.
• Upshot's display tools shows all the state data derived from logged events.
• A state is defined by a starting and ending event of a processor in a single timeline.
• A histogram facility allows the use of histograms to summarize information about state duration.

Jumpshot  (Public Domain Tool )

Jumpshot is a Java-based visualization tool for doing postmortem performance analysis. Using Java instead of Tcl/Tk (that was used in some of the older visualization tools) improves the portability, maintainability and functionalities of the tools. There are several iterations of the tool. It uses MPE (Multi-Processing Environment) library is distributed with the freely available MPICH implementation and provides a number of useful facilities, including debugging, logging, graphics, and some common utility routines to create logfiles SLOG/ALOG/CLOG. Jumpshot is used to display logfiles SLOG (Scalable logfile format) which address data-scalability issue of the logfile for visualization

Alog : An event-based logging format. Its corresponding viewer is either Upshot or Nupshot.The ALOG package is distributed as part of MPE, which is also distributed under MPICH.
Clog : Another event-based logging format. A descendant of ALOG and BLOG, Its corresponding viewer is Jumpshot-2. The CLOG package is distributed as part of MPE, which is also distributed under MPICH

Slog : A scalable logfile format. SLOG addresses the data-scalability issue of the logfile. It is very easy to generate a large CLOG file that renders the performance of Jumphsot-2 slow or even useless. SLOG allows the viewer to read only portion(s) of the logfile for visualization. One of the main goals of SLOG is to help users locate interesting portion(s) of the logfile for analysis.

Features of Jumpshot:

• Provides a Gantt chart display, which represents the various MPI calls and user-defined states for each process and arrows, and messages exchanged between those states.
• Filtering of states is possible so that only those states that are of interested are displayed
• The time-line view can be zoomed and scrolled.
• Clicking on a rectangle or an arrow brings up a box that displays more detailed information about the state or message, respectively.