A Review of Parallelization Tools and Introduction to Easypar
---
paper_title: Semi-automatic extraction and exploitation of hierarchical pipeline parallelism using profiling information

paper_content:

In recent years multi-core computer systems have left the realm of high-performance computing and virtually all of today's desktop computers and embedded computing systems are equipped with several processing cores. Still, no single parallel programming model has found widespread support and parallel programming remains an art for the majority of application programmers. In addition, there exists a plethora of sequential legacy applications for which automatic parallelization is the only hope to benefit from the increased processing power of modern multi-core systems. In the past automatic parallelization largely focused on data parallelism. In this paper we present a novel approach to extracting and exploiting pipeline parallelism from sequential applications. We use profiling to overcome the limitations of static data and control flow analysis enabling more aggressive parallelization. Our approach is orthogonal to existing automatic parallelization approaches and additional data parallelism may be exploited in the individual pipeline stages. The key contribution of this paper is a whole-program representation that supports profiling, parallelism extraction and exploitation. We demonstrate how this enhances conventional pipeline parallelization by incorporating support for multi-level loops and pipeline stage replication in a uniform and automatic way. We have evaluated our methodology on a set of multimedia and stream processing benchmarks and demonstrate speedups of up to 4.7 on a eight-core Intel Xeon machine.
---
paper_title: Automatic extraction of functional parallelism from ordinary programs

paper_content:

Presents the hierarchical task graph (HTG) as an intermediate parallel program representation which encapsulates minimal data and control dependences, and which can be used for the extraction and exploitation of functional, or task-level parallelism. The hierarchical nature of the HTG facilitates efficient task-granularity control during code generation, and thus applicability to a variety of parallel architectures. The construction of the HTG at a given hierarchy level, the derivation of the execution conditions of tasks which maximizes task-level parallelism, and the optimization of these conditions which results in reducing synchronization overhead imposed by data and control dependences are emphasized. Algorithms for the formation of tasks and their execution conditions based on data and control dependence constraints are presented. The issue of optimization of such conditions is discussed, and optimization algorithms are proposed. The HTG is used as the intermediate representation of parallel Fortran and C programs for generating parallel source as well as parallel machine code. >
---
paper_title: Automatic parallelization of divide and conquer algorithms

paper_content:

Divide and conquer algorithms are a good match for modern parallel machines: they tend to have large amounts of inherent parallelism and they work well with caches and deep memory hierarchies. But these algorithms pose challenging problems for parallelizing compilers. They are usually coded as recursive procedures and often use pointers into dynamically allocated memory blocks and pointer arithmetic. All of these features are incompatible with the analysis algorithms in traditional parallelizing compilers.This paper presents the design and implementation of a compiler that is designed to parallelize divide and conquer algorithms whose subproblems access disjoint regions of dynamically allocated arrays. The foundation of the compiler is a flow-sensitive, context-sensitive, and interprocedural pointer analysis algorithm. A range of symbolic analysis algorithms build on the pointer analysis information to extract symbolic bounds for the memory regions accessed by (potentially recursive) procedures that use pointers and pointer arithmetic. The symbolic bounds information allows the compiler to find procedure calls that can execute in parallel without violating the data dependences. The compiler generates code that executes these calls in parallel. We have used the compiler to parallelize several programs that use divide and conquer algorithms. Our results show that the programs perform well and exhibit good speedup.
---
paper_title: A practical automatic polyhedral parallelizer and locality optimizer

paper_content:

We present the design and implementation of an automatic polyhedral source-to-source transformation framework that can optimize regular programs (sequences of possibly imperfectly nested loops) for parallelism and locality simultaneously. Through this work, we show the practicality of analytical model-driven automatic transformation in the polyhedral model -- far beyond what is possible by current production compilers. Unlike previous works, our approach is an end-to-end fully automatic one driven by an integer linear optimization framework that takes an explicit view of finding good ways of tiling for parallelism and locality using affine transformations. The framework has been implemented into a tool to automatically generate OpenMP parallel code from C program sections. Experimental results from the tool show very high speedups for local and parallel execution on multi-cores over state-of-the-art compiler frameworks from the research community as well as the best native production compilers. The system also enables the easy use of powerful empirical/iterative optimization for general arbitrarily nested loop sequences.
---
paper_title: Automatic parallelization of recursive procedures

paper_content:

Parallelizing compilers have traditionally focussed mainly on parallelizing loops. This paper presents a new framework for automatically parallelizing recursive procedures that typically appear in divide-and-conquer algorithms. We present compile-time analysis to detect the independence of multiple recursive calls in a procedure. This allows exploitation of a scalable form of nested parallelism, where each parallel task can further spawn off parallel work in subsequent recursive calls.We describe a run-time system which efficiently supports this kind of nested parallelism without unnecessarily blocking tasks. We have implemented this framework in a parallelizing compiler, which is able to automatically parallelize programs like quicksort and mergesort, written in C.For cases where even the advanced symbolic analysis and array section analysis we describe are not able to prove the independence of procedure calls, we propose novel techniques for speculative run-time parallelization, which are more efficient and powerful in this context than analogous techniques proposed previously for speculatively parallelizing loops. Our experimental results on an IBM G30 SMP machine show good speedups obtained by following our approach.
---
paper_title: Semi-automatic extraction and exploitation of hierarchical pipeline parallelism using profiling information

paper_content:

In recent years multi-core computer systems have left the realm of high-performance computing and virtually all of today's desktop computers and embedded computing systems are equipped with several processing cores. Still, no single parallel programming model has found widespread support and parallel programming remains an art for the majority of application programmers. In addition, there exists a plethora of sequential legacy applications for which automatic parallelization is the only hope to benefit from the increased processing power of modern multi-core systems. In the past automatic parallelization largely focused on data parallelism. In this paper we present a novel approach to extracting and exploiting pipeline parallelism from sequential applications. We use profiling to overcome the limitations of static data and control flow analysis enabling more aggressive parallelization. Our approach is orthogonal to existing automatic parallelization approaches and additional data parallelism may be exploited in the individual pipeline stages. The key contribution of this paper is a whole-program representation that supports profiling, parallelism extraction and exploitation. We demonstrate how this enhances conventional pipeline parallelization by incorporating support for multi-level loops and pipeline stage replication in a uniform and automatic way. We have evaluated our methodology on a set of multimedia and stream processing benchmarks and demonstrate speedups of up to 4.7 on a eight-core Intel Xeon machine.
---
paper_title: A framework for automatic parallelization of sequential programs

paper_content:

With the dropping prices of multiprocessor desktop computers and high-performance clusters these systems are more and more available to the average user. Thus there is a growing need for applications that take advantage of multiprocessor systems. Automatic parallelization allows preexisting sequential programs to utilize multiple processors. Automatic parallelization requires thorough analysis of the sequential program. In this paper multiprocessor systems, and challenges of automatic parallelization are briefly covered. Also, a framework for developing and running automatic parallelization algorithms is introduced.
---
paper_title: Maximizing Multiprocessor Performance with the SUIF Compiler

paper_content:

This article describes automatic parallelization techniques in the SUIF (Stanford University Intermediate Format) compiler that result in good multiprocessor performance for array-based numerical programs. Parallelizing compilers for multiprocessors face many hurdles. However, SUIF's robust analysis and memory optimization techniques enabled speedups on three fourths of the NAS and SPECfp95 benchmark programs.
---
paper_title: An efficient data dependence analysis for parallelizing compilers

paper_content:

A novel algorithm, called the lambda test, is presented for an efficient and accurate data dependence analysis of multidimensional array references. It extends the numerical methods to allow all dimensions of array references to be tested simultaneously. Hence, it combines the efficiency and the accuracy of both approaches. This algorithm has been implemented in Parafrase, a Fortran program parallelization restructurer developed at the University of Illinois at Urbana-Champaign. Some experimental results are presented to show its effectiveness. >
---
paper_title: Parallel programming with Polaris

paper_content:

Parallel programming tools are limited, making effective parallel programming difficult and cumbersome. Compilers that translate conventional sequential programs into parallel form would liberate programmers from the complexities of explicit, machine oriented parallel programming. The paper discusses parallel programming with Polaris, an experimental translator of conventional Fortran programs that target machines such as the Cray T3D.
---
paper_title: Experiences of using a dependence profiler to assist parallelization for multi-cores

paper_content:

We show how to use a data-dependence profiling tool called DProf, which can be utilized to assist parallelization for multi-core systems. DProf is based on an optimizing compiler and uses reference runs to emit information on runtime dependences between various memory accesses within a loop. The profiler not only marks the dependent statements and the accesses but also emits details regarding the percentage of time the dependences are encountered - the percentage being taken over the loop iteration size. Though DProf has been primarily built to capture opportunities for speculative thread-level parallelism, it has been found that the report generated by the DProf can be utilized very effectively in detecting and parallelizing complex code. To demonstrate this, we have taken two complex benchmarks - 435.gromacs and 437.leslie3d from the SPECfp CPU2006 suite and show how they can be parallelized effectively using DProf as an assist. To the best of our knowledge none of the existing parallelizing compilers can detect and parallelize all the instances reported in this work. We find that by using DProf we are able to parallelize these benchmarks very effectively for IBM P5+ and P6 multi-core systems. We have parallelized the benchmarks using OpenMP leading to speedups up to 2.6x. Also, due to the detailed reporting by DProf, we could cut down on our parallelization development effort significantly by concentrating on portions of the code that require attention. DProf can also be used to identify applications, where applying parallelization may lead to regression in performance. This allows the developers to discard applications or parts of it quickly, which may not lead to performance improvements when deployed on multi-cores. Thus, a data dependence profiler like DProf can act as an excellent assist mechanism to move applications to multi-cores in an effective way.
---
paper_title: Extracting coarse-grain parallelism in general-purpose programs

paper_content:

While the chip multiprocessor (CMP) has quickly become the predominant processor architecture, its continuing success largely depends on the parallelizability of complex programs. In the early 1990s great successes were obtained to extract parallelism from the inner loops of scientific computations. In this paper we show that significant amounts of coarse-grain parallelism exists in the outer program loops, even in general-purpose programs. This coarse-grain parallelism can be exploited efficiently on CMPs without additional hardware support.
---
paper_title: Hybrid Approach for Parallelization of Sequential Code with Function Level and Block Level Parallelization

paper_content:

Automatic parallelization of a sequential code is about finding parallel segments in the code and executing these segments parallely by sending them to different computers in a grid. Basically, parallel segments in the code can be found by doing block level analysis, instruction level analysis or function level analysis. Block is any continuous part of the code that performs a particular task. This paper talks about a hybrid approach that combines the block level analysis with functional level analysis for parallelization of sequential code and its illustrates its advantages over block level parallelization and function level parallelization performed independently. In this approach, segments of code are identified as basic blocks. These blocks are analyzed to identify them as parallelizable or dependent. Loops which are also identified as blocks are parallelized using existing loop parallelization techniques [1]. This information would be used for automatic parallel processing of the set of independent blocks on different nodes in the grid using Message Passing Interface(MPI). The system will annotate the MPI library functions to the program at appropriate positions in the source code to proceed with the automatic parallelization and execution of the program.
---
paper_title: Semi-automatic extraction and exploitation of hierarchical pipeline parallelism using profiling information

paper_content:

In recent years multi-core computer systems have left the realm of high-performance computing and virtually all of today's desktop computers and embedded computing systems are equipped with several processing cores. Still, no single parallel programming model has found widespread support and parallel programming remains an art for the majority of application programmers. In addition, there exists a plethora of sequential legacy applications for which automatic parallelization is the only hope to benefit from the increased processing power of modern multi-core systems. In the past automatic parallelization largely focused on data parallelism. In this paper we present a novel approach to extracting and exploiting pipeline parallelism from sequential applications. We use profiling to overcome the limitations of static data and control flow analysis enabling more aggressive parallelization. Our approach is orthogonal to existing automatic parallelization approaches and additional data parallelism may be exploited in the individual pipeline stages. The key contribution of this paper is a whole-program representation that supports profiling, parallelism extraction and exploitation. We demonstrate how this enhances conventional pipeline parallelization by incorporating support for multi-level loops and pipeline stage replication in a uniform and automatic way. We have evaluated our methodology on a set of multimedia and stream processing benchmarks and demonstrate speedups of up to 4.7 on a eight-core Intel Xeon machine.
---
paper_title: Automatic Sequential to Parallel Code Conversion The S2P Tool and Performance Analysis

paper_content:

The way software programs are being written has been redefined since the introduction of multicore processors. Software developers have started writing parallel programs that are robust and scalable. This would ensure use of processor power being made available in the form of multiple cores. Though this trend is increasing, there are legacy applications that have been developed over the past few decades. Most of these applications are inherently sequential making no use of multithreading or parallel programming. If such applications are ported to execute on the multicore hardware as they are then optimal usage of all cores is not guaranteed. Such applications would ideally utilize only one core and the other cores would remain idle, unless the operating system supports some parallelism while scheduling. Hence there is a need to convert such legacy sequential codes to their parallel versions so that multicore hardware is exploited to the fullest. In this paper we present a tool that we have developed to automatically convert a sequential C code to parallel code. This Sequential to Parallel (S2P) tool is still in the development phase. We also discuss other parallelization tools available today, compare such tools with S2P tool and present our performance analysis results on different kind of multicore hardware.
---
paper_title: How much parallelism is there in irregular applications?

paper_content:

Irregular programs are programs organized around pointer-based data structures such as trees and graphs. Recent investigations by the Galois project have shown that many irregular programs have a generalized form of data-parallelism called amorphous data-parallelism. However, in many programs, amorphous data-parallelism cannot be uncovered using static techniques, and its exploitation requires runtime strategies such as optimistic parallel execution. This raises a natural question: how much amorphous data-parallelism actually exists in irregular programs? In this paper, we describe the design and implementation of a tool called ParaMeter that produces parallelism profiles for irregular programs. Parallelism profiles are an abstract measure of the amount of amorphous data-parallelism at different points in the execution of an algorithm, independent of implementation-dependent details such as the number of cores, cache sizes, load-balancing, etc. ParaMeter can also generate constrained parallelism profiles for a fixed number of cores. We show parallelism profiles for seven irregular applications, and explain how these profiles provide insight into the behavior of these applications.
---
paper_title: The application visualization system: a computational environment for scientific visualization

paper_content:

A software system for developing interactive scientific visualization applications quickly, with a minimum of programming effort, is described. This application visualization system (AVS) is an application framework targeted at scientists and engineers. The goal of the system is to make applications that combine interactive graphics and high computational requirements easier to develop for both programmers and nonprogrammers. AVS is designed around the concept of software building blocks, or modules, which can be interconnected to form visualization applications. AVS allows flow networks of existing modules to be constructed using a direct-manipulation user interface, and it automatically generates a simple user interface to each module. >
---
paper_title: Experiences of using a dependence profiler to assist parallelization for multi-cores

paper_content:

We show how to use a data-dependence profiling tool called DProf, which can be utilized to assist parallelization for multi-core systems. DProf is based on an optimizing compiler and uses reference runs to emit information on runtime dependences between various memory accesses within a loop. The profiler not only marks the dependent statements and the accesses but also emits details regarding the percentage of time the dependences are encountered - the percentage being taken over the loop iteration size. Though DProf has been primarily built to capture opportunities for speculative thread-level parallelism, it has been found that the report generated by the DProf can be utilized very effectively in detecting and parallelizing complex code. To demonstrate this, we have taken two complex benchmarks - 435.gromacs and 437.leslie3d from the SPECfp CPU2006 suite and show how they can be parallelized effectively using DProf as an assist. To the best of our knowledge none of the existing parallelizing compilers can detect and parallelize all the instances reported in this work. We find that by using DProf we are able to parallelize these benchmarks very effectively for IBM P5+ and P6 multi-core systems. We have parallelized the benchmarks using OpenMP leading to speedups up to 2.6x. Also, due to the detailed reporting by DProf, we could cut down on our parallelization development effort significantly by concentrating on portions of the code that require attention. DProf can also be used to identify applications, where applying parallelization may lead to regression in performance. This allows the developers to discard applications or parts of it quickly, which may not lead to performance improvements when deployed on multi-cores. Thus, a data dependence profiler like DProf can act as an excellent assist mechanism to move applications to multi-cores in an effective way.
---
paper_title: Jade: a high-level, machine-independent language for parallel programming

paper_content:

Jade, a high-level parallel programming language for managing coarse-grained parallelism, is discussed. Jade simplifies programming by providing sequential-execution and shared-address-space abstractions. It is also platform-independent; the same Jade program runs on uniprocessors, multiprocessors, and heterogeneous networks of machines. An example that illustrates how Jade programmers express irregular, dynamically determined concurrency and how the implementation exploits this source of concurrency is presented. A digital video imaging program that runs on a high-resolution video system and several other examples of Jade applications are described. >
---
paper_title: Language support for lightweight transactions

paper_content:

Concurrent programming is notoriously difficult. Current abstractions are intricate and make it hard to design computer systems that are reliable and scalable. We argue that these problems can be addressed by moving to a declarative style of concurrency control in which programmers directly indicate the safety properties that they require. In our scheme the programmer demarks sections of code which execute within lightweight software-based transactions that commit atomically and exactly once. These transactions can update shared data, instantiate objects, invoke library features and so on. They can also block, waiting for arbitrary boolean conditions to become true. Transactions which do not access the same shared memory locations can commit concurrently. Furthermore, in general, no performance penalty is incurred for memory accesses outside transactions.We present a detailed design of this proposal along with an implementation and evaluation. We argue that the resulting system (i) is easier for mainstream programmers to use, (ii) prevents lock-based priority-inversion and deadlock problems and (iii) can offer performance advantages.
---
paper_title: On the Use of Data Flow Analysis in Static Profiling

paper_content:

Static profiling is a technique that produces estimates of execution likelihoods or frequencies based on source code analysis only. It is frequently used in determining cost/benefit ratios for certain compiler optimizations. In previous work,we introduced a simple algorithm to compute execution likelihoods,based on a control flow graph and heuristic branch prediction. In this paper we examine the benefits of using more involved analysis techniques in such a static profiler. In particular, we explore the use of value range propagation to improve the accuracy of the estimates, and we investigate the differences in estimating execution likelihoods and frequencies.
---
paper_title: Semi-automatic extraction and exploitation of hierarchical pipeline parallelism using profiling information

paper_content:

In recent years multi-core computer systems have left the realm of high-performance computing and virtually all of today's desktop computers and embedded computing systems are equipped with several processing cores. Still, no single parallel programming model has found widespread support and parallel programming remains an art for the majority of application programmers. In addition, there exists a plethora of sequential legacy applications for which automatic parallelization is the only hope to benefit from the increased processing power of modern multi-core systems. In the past automatic parallelization largely focused on data parallelism. In this paper we present a novel approach to extracting and exploiting pipeline parallelism from sequential applications. We use profiling to overcome the limitations of static data and control flow analysis enabling more aggressive parallelization. Our approach is orthogonal to existing automatic parallelization approaches and additional data parallelism may be exploited in the individual pipeline stages. The key contribution of this paper is a whole-program representation that supports profiling, parallelism extraction and exploitation. We demonstrate how this enhances conventional pipeline parallelization by incorporating support for multi-level loops and pipeline stage replication in a uniform and automatic way. We have evaluated our methodology on a set of multimedia and stream processing benchmarks and demonstrate speedups of up to 4.7 on a eight-core Intel Xeon machine.
---
paper_title: An efficient data dependence analysis for parallelizing compilers

paper_content:

A novel algorithm, called the lambda test, is presented for an efficient and accurate data dependence analysis of multidimensional array references. It extends the numerical methods to allow all dimensions of array references to be tested simultaneously. Hence, it combines the efficiency and the accuracy of both approaches. This algorithm has been implemented in Parafrase, a Fortran program parallelization restructurer developed at the University of Illinois at Urbana-Champaign. Some experimental results are presented to show its effectiveness. >
---
paper_title: Experiences of using a dependence profiler to assist parallelization for multi-cores

paper_content:

We show how to use a data-dependence profiling tool called DProf, which can be utilized to assist parallelization for multi-core systems. DProf is based on an optimizing compiler and uses reference runs to emit information on runtime dependences between various memory accesses within a loop. The profiler not only marks the dependent statements and the accesses but also emits details regarding the percentage of time the dependences are encountered - the percentage being taken over the loop iteration size. Though DProf has been primarily built to capture opportunities for speculative thread-level parallelism, it has been found that the report generated by the DProf can be utilized very effectively in detecting and parallelizing complex code. To demonstrate this, we have taken two complex benchmarks - 435.gromacs and 437.leslie3d from the SPECfp CPU2006 suite and show how they can be parallelized effectively using DProf as an assist. To the best of our knowledge none of the existing parallelizing compilers can detect and parallelize all the instances reported in this work. We find that by using DProf we are able to parallelize these benchmarks very effectively for IBM P5+ and P6 multi-core systems. We have parallelized the benchmarks using OpenMP leading to speedups up to 2.6x. Also, due to the detailed reporting by DProf, we could cut down on our parallelization development effort significantly by concentrating on portions of the code that require attention. DProf can also be used to identify applications, where applying parallelization may lead to regression in performance. This allows the developers to discard applications or parts of it quickly, which may not lead to performance improvements when deployed on multi-cores. Thus, a data dependence profiler like DProf can act as an excellent assist mechanism to move applications to multi-cores in an effective way.
---
paper_title: ThreadSanitizer: data race detection in practice

paper_content:

Data races are a particularly unpleasant kind of threading bugs. They are hard to find and reproduce -- you may not observe a bug during the entire testing cycle and will only see it in production as rare unexplainable failures. This paper presents ThreadSanitizer -- a dynamic detector of data races. We describe the hybrid algorithm (based on happens-before and locksets) used in the detector. We introduce what we call dynamic annotations -- a sort of race detection API that allows a user to inform the detector about any tricky synchronization in the user program. Various practical aspects of using ThreadSanitizer for testing multithreaded C++ code at Google are also discussed.
---
paper_title: Effective performance measurement and analysis of multithreaded applications

paper_content:

Understanding why the performance of a multithreaded program does not improve linearly with the number of cores in a shared-memory node populated with one or more multicore processors is a problem of growing practical importance. This paper makes three contributions to performance analysis of multithreaded programs. First, we describe how to measure and attribute parallel idleness, namely, where threads are stalled and unable to work. This technique applies broadly to programming models ranging from explicit threading (e.g., Pthreads) to higher-level models such as Cilk and OpenMP. Second, we describe how to measure and attribute parallel overhead -- when a thread is performing miscellaneous work other than executing the user's computation. By employing a combination of compiler support and post-mortem analysis, we incur no measurement cost beyond normal profiling to glean this information. Using idleness and overhead metrics enables one to pinpoint areas of an application where concurrency should be increased (to reduce idleness), decreased (to reduce overhead), or where the present parallelization is hopeless (where idleness and overhead are both high). Third, we describe how to measure and attribute arbitrary performance metrics for high-level multithreaded programming models, such as Cilk. This requires bridging the gap between the expression of logical concurrency in programs and its realization at run-time as it is adaptively partitioned and scheduled onto a pool of threads. We have prototyped these ideas in the context of Rice University's HPCToolkit performance tools. We describe our approach, implementation, and experiences applying this approach to measure and attribute work, idleness, and overhead in executions of Cilk programs.
---
paper_title: The Cilkview scalability analyzer

paper_content:

The Cilkview scalability analyzer is a software tool for profiling, estimating scalability, and benchmarking multithreaded Cilk++ applications. Cilkview monitors logical parallelism during an instrumented execution of the Cilk++ application on a single processing core. As Cilkview executes, it analyzes logical dependencies within the computation to determine its work and span (critical-path length). These metrics allow Cilkview to estimate parallelism and predict how the application will scale with the number of processing cores. In addition, Cilkview analyzes cheduling overhead using the concept of a "burdened dag," which allows it to diagnose performance problems in the application due to an insufficient grain size of parallel subcomputations. Cilkview employs the Pin dynamic-instrumentation framework to collect metrics during a serial execution of the application code. It operates directly on the optimized code rather than on a debug version. Metadata embedded by the Cilk++ compiler in the binary executable identifies the parallel control constructs in the executing application. This approach introduces little or no overhead to the program binary in normal runs. Cilkview can perform real-time scalability benchmarking automatically, producing gnuplot-compatible output that allows developers to compare an application's performance with the tool's predictions. If the program performs beneath the range of expectation, the programmer can be confident in seeking a cause such as insufficient memory bandwidth, false sharing, or contention rather than inadequate parallelism or insufficient grain size.
---
paper_title: Semi-automatic extraction and exploitation of hierarchical pipeline parallelism using profiling information

paper_content:

In recent years multi-core computer systems have left the realm of high-performance computing and virtually all of today's desktop computers and embedded computing systems are equipped with several processing cores. Still, no single parallel programming model has found widespread support and parallel programming remains an art for the majority of application programmers. In addition, there exists a plethora of sequential legacy applications for which automatic parallelization is the only hope to benefit from the increased processing power of modern multi-core systems. In the past automatic parallelization largely focused on data parallelism. In this paper we present a novel approach to extracting and exploiting pipeline parallelism from sequential applications. We use profiling to overcome the limitations of static data and control flow analysis enabling more aggressive parallelization. Our approach is orthogonal to existing automatic parallelization approaches and additional data parallelism may be exploited in the individual pipeline stages. The key contribution of this paper is a whole-program representation that supports profiling, parallelism extraction and exploitation. We demonstrate how this enhances conventional pipeline parallelization by incorporating support for multi-level loops and pipeline stage replication in a uniform and automatic way. We have evaluated our methodology on a set of multimedia and stream processing benchmarks and demonstrate speedups of up to 4.7 on a eight-core Intel Xeon machine.
---
paper_title: CTrigger: exposing atomicity violation bugs from their hiding places

paper_content:

Multicore hardware is making concurrent programs pervasive. Unfortunately, concurrent programs are prone to bugs. Among different types of concurrency bugs, atomicity violation bugs are common and important. Existing techniques to detect atomicity violation bugs suffer from one limitation: requiring bugs to manifest during monitored runs, which is an open problem in concurrent program testing. This paper makes two contributions. First, it studies the interleaving characteristics of the common practice in concurrent program testing (i.e., running a program over and over) to understand why atomicity violation bugs are hard to expose. Second, it proposes CTrigger to effectively and efficiently expose atomicity violation bugs in large programs. CTrigger focuses on a special type of interleavings (i.e., unserializable interleavings) that are inherently correlated to atomicity violation bugs, and uses trace analysis to systematically identify (likely) feasible unserializable interleavings with low occurrence-probability. CTrigger then uses minimum execution perturbation to exercise low-probability interleavings and expose difficult-to-catch atomicity violation. We evaluate CTrigger with real-world atomicity violation bugs from four sever/desktop applications (Apache, MySQL, Mozilla, and PBZIP2) and three SPLASH2 applications on 8-core machines. CTrigger efficiently exposes the tested bugs within 1--235 seconds, two to four orders of magnitude faster than stress testing. Without CTrigger, some of these bugs do not manifest even after 7 full days of stress testing. In addition, without deterministic replay support, once a bug is exposed, CTrigger can help programmers reliably reproduce it for diagnosis. Our tested bugs are reproduced by CTrigger mostly within 5 seconds, 300 to over 60000 times faster than stress testing.
---
paper_title: Automatic Sequential to Parallel Code Conversion The S2P Tool and Performance Analysis

paper_content:

The way software programs are being written has been redefined since the introduction of multicore processors. Software developers have started writing parallel programs that are robust and scalable. This would ensure use of processor power being made available in the form of multiple cores. Though this trend is increasing, there are legacy applications that have been developed over the past few decades. Most of these applications are inherently sequential making no use of multithreading or parallel programming. If such applications are ported to execute on the multicore hardware as they are then optimal usage of all cores is not guaranteed. Such applications would ideally utilize only one core and the other cores would remain idle, unless the operating system supports some parallelism while scheduling. Hence there is a need to convert such legacy sequential codes to their parallel versions so that multicore hardware is exploited to the fullest. In this paper we present a tool that we have developed to automatically convert a sequential C code to parallel code. This Sequential to Parallel (S2P) tool is still in the development phase. We also discuss other parallelization tools available today, compare such tools with S2P tool and present our performance analysis results on different kind of multicore hardware.
---
paper_title: RaceTrack: efficient detection of data race conditions via adaptive tracking

paper_content:

Bugs due to data races in multithreaded programs often exhibit non-deterministic symptoms and are notoriously difficult to find. This paper describes RaceTrack, a dynamic race detection tool that tracks the actions of a program and reports a warning whenever a suspicious pattern of activity has been observed. RaceTrack uses a novel hybrid detection algorithm and employs an adaptive approach that automatically directs more effort to areas that are more suspicious, thus providing more accurate warnings for much less over-head. A post-processing step correlates warnings and ranks code segments based on how strongly they are implicated in potential data races. We implemented RaceTrack inside the virtual machine of Microsoft's Common Language Runtime (product version v1.1.4322) and monitored several major, real-world applications directly out-of-the-box,without any modification. Adaptive tracking resulted in a slowdown ratio of about 3x on memory-intensive programs and typically much less than 2x on other programs,and a memory ratio of typically less than 1.2x. Several serious data race bugs were revealed, some previously unknown.
---
paper_title: An object-based parallel programming assistant

paper_content:

Programmers of sequential and parallel computers share the objective of developing fast, reliable programs as efficiently as possible. Already, considerable effort has been made to develop tools and techniques for sequential computers. Several approaches have been devised to meet the parallel programming challenge. Sequential languages have been adapted for parallel computers; new parallel languages designed; and tools developed which aid the programmer in detecting parallel code. A parallel programming assistant can aid the user in several ways: it can carry out tasks that are simple but mundane to the user, it can make comprehension easier for the user by summarizing program information; and it can cooperate with the user in doing a complex task, thus combining its own knowledge with that of the user's. We have developed a parallel programming assistant [1] which supports object-based programming. The main motivation for this work was to explore how an assistant can enhance the programmer's understanding of parallel programming. In particular, we wanted to provide the user with parallel programming methods which would be easily integrated with other parts of the life cycle. Moreover, we wanted the programmer to interact with the assistant while writing parallel programs. The parallel programming assistant interactively aids the user in developing parallel programs. Instead of automatically detecting implicit parallelism in sequential code and subsequently transforming it, the parallel programming assistant analyzes statements as they are entered and immediately gives the user feedback on whether they hinder parallelization. Moreover, the assistant tells the user if the dependencies in the program which hinder parallelization can be removed by transformation. The parallel programming assistant supports object-based development. In the object-based paradigm, the decomposition of a system is based upon the concept of an object [2]. An object is a “thing” that has the capacity to store information, manipulate its own information, carry out some task upon request from an object, and activate an object. Objects are not only things where we store data, such as a line or a collection of records, but are also more powerful things which represent components in a software system such as a user interface. The first mentioned objects are data objects , the last mentioned are processing objects . The expressive power of an object-based language makes it easier for the parallel programming assistant to gather semantics about the program which it then uses to decide how to form parallel language constructs. There are two programming activities within the assistant: 1) specifying and implementing objects, and 2) writing statements that call the methods of these objects. The user does not have to carry out (or complete) activity 1) before 2) and he can freely go from one to the other. In parallel programming these activities involve: P1) partitioning an object in order to enable parallel execution of methods on the object (methods-partitioning); or partitioning an object to enable parallel execution of methods on objects within the object, (object-partitioning) and P2) writing parallel statements (i.e. parallel loops and parallel blocks). An example of a simple parallel block under construction within the parallel programming assistant is: While the block is under construction, the assistant divides it into regions such that statements in a region can be called in parallel. As statements are entered the configuration of the regions changes. When all statements have been entered, and all information is available, the TentativeParallelBlock is changed to zero or more ParallelBlocks. In the example above, the assistant examines whether the two statements are dependent by method-partitioning the object Line, such that the methods setfrom and setto are in separate partitions. Since the object Line is self-contained the assistant only needs to look for dependencies within the object Line. More complex cases arise when the assistant needs to detect dependencies between statements that call methods on separate processing objects which are not self-contained. In this case the object which contains the called objects has to be object-partitioned. The second language construct which the assistant helps the user creating is a parallel loop: As the programmer enters statements to the loop above, the assistant examines whether the objects hinder parallelization of the loop. The assistant first checks whether the structure of the object hinders partitioning of the object. Then, it checks whether the methods hinder parallelization, and finally whether the iterator of the object hinders its partitioning. When homogeneous objects, such as Lines, are partitioned, each partition gets its own set of methods. Each processor then accesses one of these partitions. In a loop, objects are not only partitioned, but also multiplied. An object such as Line is multiplied so that there are P copies, one for each processor. We specified and designed the parallel programming assistant using the object-based paradigm to software development. The experience we gained in object-based software development was helpful in designing the transformations on the objects for the parallel programming assistant. The interactive nature of the parallel programming assistant gives the user the opportunity to intervene when information is missing, that is when the implementation of objects is incomplete. An object-based language allows us to associates attributes to software objects and their methods. This provides more flexibility in the design of the parallel programming assistant, since the attributes can determine the type of transformations. As more types of objects for parallel programming become known, more transformations can be added to the assistant.
---
paper_title: Kismet: parallel speedup estimates for serial programs

paper_content:

Software engineers now face the difficult task of refactoring serial programs for parallel execution on multicore processors. Currently, they are offered little guidance as to how much benefit may come from this task, or how close they are to the best possible parallelization. This paper presents Kismet, a tool that creates parallel speedup estimates for unparallelized serial programs. Kismet differs from previous approaches in that it does not require any manual analysis or modification of the program. This difference allows quick analysis of many programs, avoiding wasted engineering effort on those that are fundamentally limited. To accomplish this task, Kismet builds upon the hierarchical critical path analysis (HCPA) technique, a recently developed dynamic analysis that localizes parallelism to each of the potentially nested regions in the target program. It then uses a parallel execution time model to compute an approximate upper bound for performance, modeling constraints that stem from both hardware parameters and internal program structure. Our evaluation applies Kismet to eight high-parallelism NAS Parallel Benchmarks running on a 32-core AMD multicore system, five low-parallelism SpecInt benchmarks, and six medium-parallelism benchmarks running on the finegrained MIT Raw processor. The results are compelling. Kismet is able to significantly improve the accuracy of parallel speedup estimates relative to prior work based on critical path analysis.
---
paper_title: Quartz: a tool for tuning parallel program performance

paper_content:

Initial implementations of parallel programs typically yield disappointing performance. Tuning to improve performance is thus a significant part of the parallel programming process. The effort required to tune a parallel program, and the level of performance that eventually is achieved, both depend heavily on the quality of the instrumentation that is available to the programmer. This paper describes Quartz, a new tool for tuning parallel program performance on shared memory multiprocessors. The philosophy underlying Quartz was inspired by that of the sequential UNIX tool gprof: to appropriately direct the attention of the programmer by efficiently measuring just those factors that are most responsible for performance and by relating these metrics to one another and to the structure of the program. This philosophy is even more important in the parallel domain than in the sequential domain, because of the dramatically greater number of possible metrics and the dramatically increased complexity of program structures. The principal metric of Quartz is normalized processor time : the total processor time spent in each section of code divided by the number of other processors that are concurrently busy when that section of code is being executed. Tied to the logical structure of the program, this metric provides a “smoking gun” pointing towards those areas of the program most responsible for poor performance. This information can be acquired efficiently by checkpointing to memory the number of busy processors and the state of each processor, and then statistically sampling these using a dedicated processor. In addition to describing the design rationale, functionality, and implementation of Quartz, the paper examines how Quartz would be used to solve a number of performance problems that have been reported as being frequently encountered, and describes a case study in which Quartz was used to significantly improve the performance of a CAD circuit verifier.
---
paper_title: Interfacing Computer Aided Parallelization and Performance Analysis

paper_content:

When porting sequential applications to parallel computer architectures, the program developer will typically go through several cycles of source code optimization and performance analysis. We have started a project to develop an environment where the user can jointly navigate through program structure and performance data information in order to make efficient optimization decisions. In a prototype implementation we have interfaced the CAPO computer aided parallelization tool with the Paraver performance analysis tool. We describe both tools and their interface and give an example for how the interface helps within the program development cycle of a benchmark code.
---
paper_title: Maximizing Multiprocessor Performance with the SUIF Compiler

paper_content:

This article describes automatic parallelization techniques in the SUIF (Stanford University Intermediate Format) compiler that result in good multiprocessor performance for array-based numerical programs. Parallelizing compilers for multiprocessors face many hurdles. However, SUIF's robust analysis and memory optimization techniques enabled speedups on three fourths of the NAS and SPECfp95 benchmark programs.
---
paper_title: An object-based parallel programming assistant

paper_content:

Programmers of sequential and parallel computers share the objective of developing fast, reliable programs as efficiently as possible. Already, considerable effort has been made to develop tools and techniques for sequential computers. Several approaches have been devised to meet the parallel programming challenge. Sequential languages have been adapted for parallel computers; new parallel languages designed; and tools developed which aid the programmer in detecting parallel code. A parallel programming assistant can aid the user in several ways: it can carry out tasks that are simple but mundane to the user, it can make comprehension easier for the user by summarizing program information; and it can cooperate with the user in doing a complex task, thus combining its own knowledge with that of the user's. We have developed a parallel programming assistant [1] which supports object-based programming. The main motivation for this work was to explore how an assistant can enhance the programmer's understanding of parallel programming. In particular, we wanted to provide the user with parallel programming methods which would be easily integrated with other parts of the life cycle. Moreover, we wanted the programmer to interact with the assistant while writing parallel programs. The parallel programming assistant interactively aids the user in developing parallel programs. Instead of automatically detecting implicit parallelism in sequential code and subsequently transforming it, the parallel programming assistant analyzes statements as they are entered and immediately gives the user feedback on whether they hinder parallelization. Moreover, the assistant tells the user if the dependencies in the program which hinder parallelization can be removed by transformation. The parallel programming assistant supports object-based development. In the object-based paradigm, the decomposition of a system is based upon the concept of an object [2]. An object is a “thing” that has the capacity to store information, manipulate its own information, carry out some task upon request from an object, and activate an object. Objects are not only things where we store data, such as a line or a collection of records, but are also more powerful things which represent components in a software system such as a user interface. The first mentioned objects are data objects , the last mentioned are processing objects . The expressive power of an object-based language makes it easier for the parallel programming assistant to gather semantics about the program which it then uses to decide how to form parallel language constructs. There are two programming activities within the assistant: 1) specifying and implementing objects, and 2) writing statements that call the methods of these objects. The user does not have to carry out (or complete) activity 1) before 2) and he can freely go from one to the other. In parallel programming these activities involve: P1) partitioning an object in order to enable parallel execution of methods on the object (methods-partitioning); or partitioning an object to enable parallel execution of methods on objects within the object, (object-partitioning) and P2) writing parallel statements (i.e. parallel loops and parallel blocks). An example of a simple parallel block under construction within the parallel programming assistant is: While the block is under construction, the assistant divides it into regions such that statements in a region can be called in parallel. As statements are entered the configuration of the regions changes. When all statements have been entered, and all information is available, the TentativeParallelBlock is changed to zero or more ParallelBlocks. In the example above, the assistant examines whether the two statements are dependent by method-partitioning the object Line, such that the methods setfrom and setto are in separate partitions. Since the object Line is self-contained the assistant only needs to look for dependencies within the object Line. More complex cases arise when the assistant needs to detect dependencies between statements that call methods on separate processing objects which are not self-contained. In this case the object which contains the called objects has to be object-partitioned. The second language construct which the assistant helps the user creating is a parallel loop: As the programmer enters statements to the loop above, the assistant examines whether the objects hinder parallelization of the loop. The assistant first checks whether the structure of the object hinders partitioning of the object. Then, it checks whether the methods hinder parallelization, and finally whether the iterator of the object hinders its partitioning. When homogeneous objects, such as Lines, are partitioned, each partition gets its own set of methods. Each processor then accesses one of these partitions. In a loop, objects are not only partitioned, but also multiplied. An object such as Line is multiplied so that there are P copies, one for each processor. We specified and designed the parallel programming assistant using the object-based paradigm to software development. The experience we gained in object-based software development was helpful in designing the transformations on the objects for the parallel programming assistant. The interactive nature of the parallel programming assistant gives the user the opportunity to intervene when information is missing, that is when the implementation of objects is incomplete. An object-based language allows us to associates attributes to software objects and their methods. This provides more flexibility in the design of the parallel programming assistant, since the attributes can determine the type of transformations. As more types of objects for parallel programming become known, more transformations can be added to the assistant.
---
paper_title: Semi-automatic extraction and exploitation of hierarchical pipeline parallelism using profiling information

paper_content:

In recent years multi-core computer systems have left the realm of high-performance computing and virtually all of today's desktop computers and embedded computing systems are equipped with several processing cores. Still, no single parallel programming model has found widespread support and parallel programming remains an art for the majority of application programmers. In addition, there exists a plethora of sequential legacy applications for which automatic parallelization is the only hope to benefit from the increased processing power of modern multi-core systems. In the past automatic parallelization largely focused on data parallelism. In this paper we present a novel approach to extracting and exploiting pipeline parallelism from sequential applications. We use profiling to overcome the limitations of static data and control flow analysis enabling more aggressive parallelization. Our approach is orthogonal to existing automatic parallelization approaches and additional data parallelism may be exploited in the individual pipeline stages. The key contribution of this paper is a whole-program representation that supports profiling, parallelism extraction and exploitation. We demonstrate how this enhances conventional pipeline parallelization by incorporating support for multi-level loops and pipeline stage replication in a uniform and automatic way. We have evaluated our methodology on a set of multimedia and stream processing benchmarks and demonstrate speedups of up to 4.7 on a eight-core Intel Xeon machine.
---
paper_title: How much parallelism is there in irregular applications?

paper_content:

Irregular programs are programs organized around pointer-based data structures such as trees and graphs. Recent investigations by the Galois project have shown that many irregular programs have a generalized form of data-parallelism called amorphous data-parallelism. However, in many programs, amorphous data-parallelism cannot be uncovered using static techniques, and its exploitation requires runtime strategies such as optimistic parallel execution. This raises a natural question: how much amorphous data-parallelism actually exists in irregular programs? In this paper, we describe the design and implementation of a tool called ParaMeter that produces parallelism profiles for irregular programs. Parallelism profiles are an abstract measure of the amount of amorphous data-parallelism at different points in the execution of an algorithm, independent of implementation-dependent details such as the number of cores, cache sizes, load-balancing, etc. ParaMeter can also generate constrained parallelism profiles for a fixed number of cores. We show parallelism profiles for seven irregular applications, and explain how these profiles provide insight into the behavior of these applications.
---
paper_title: Convit , a Tool for Learning Concurrent Programming

paper_content:

Concurrent programming is an important and difficult topic for most computer science students. This paper presents a visualization tool called Convit to help students master and understand concurrent programming problems and their solutions. The tool, a Java applet, is basically a debugger or simulator, which runs concurrent programs written in a simple pseudocode. The code is translated into Java run in the applet. The students are supposed to work on their own with the tool exploring the examples and problems created by teachers. The tool also allows modification of the synchronization statements, to a limited degree, so that the student may try out various choices.
---
paper_title: DEEP: a development environment for parallel programs

paper_content:

The use of the DEEP development environment to analyze parallel program performance is described. The full integrated environment contains tools for the creation, analysis and debugging of parallel programs. All information is related back to the original parallel source code. This paper describes the program analysis portion of DEEP, with examples of its use on data parallel programs (HPF and Data Parallel C) and shared memory parallel (SMP) programs.
---
paper_title: Automatic Sequential to Parallel Code Conversion The S2P Tool and Performance Analysis

paper_content:

The way software programs are being written has been redefined since the introduction of multicore processors. Software developers have started writing parallel programs that are robust and scalable. This would ensure use of processor power being made available in the form of multiple cores. Though this trend is increasing, there are legacy applications that have been developed over the past few decades. Most of these applications are inherently sequential making no use of multithreading or parallel programming. If such applications are ported to execute on the multicore hardware as they are then optimal usage of all cores is not guaranteed. Such applications would ideally utilize only one core and the other cores would remain idle, unless the operating system supports some parallelism while scheduling. Hence there is a need to convert such legacy sequential codes to their parallel versions so that multicore hardware is exploited to the fullest. In this paper we present a tool that we have developed to automatically convert a sequential C code to parallel code. This Sequential to Parallel (S2P) tool is still in the development phase. We also discuss other parallelization tools available today, compare such tools with S2P tool and present our performance analysis results on different kind of multicore hardware.
---
paper_title: The GRED graphical editor for the GRADE parallel program development environment

paper_content:

Abstract In this paper, we describe a graphical editor GRED as a part of the integrated programing environment GRADE that is intended to support designing, debugging and performance tuning of message-passing programs running on a heterogeneous network of computers. The GRED editor hides the cumbersome details of the underlying low-level message-passing system (which can be either PVM or MPI) by providing visual abstractions but allows the programer to define local computations of the individual processes in C (or in Fortran in the future) independently from the visually supported process management and inter-process communication activities. Visual representation of the critical (i.e. message-passing related) parts of the code can help the user in grasping the complex structure and run-time behavior of the whole parallel application, even if he or she is not an expert in the field of concurrent programing.
---
paper_title: An object-based parallel programming assistant

paper_content:

Programmers of sequential and parallel computers share the objective of developing fast, reliable programs as efficiently as possible. Already, considerable effort has been made to develop tools and techniques for sequential computers. Several approaches have been devised to meet the parallel programming challenge. Sequential languages have been adapted for parallel computers; new parallel languages designed; and tools developed which aid the programmer in detecting parallel code. A parallel programming assistant can aid the user in several ways: it can carry out tasks that are simple but mundane to the user, it can make comprehension easier for the user by summarizing program information; and it can cooperate with the user in doing a complex task, thus combining its own knowledge with that of the user's. We have developed a parallel programming assistant [1] which supports object-based programming. The main motivation for this work was to explore how an assistant can enhance the programmer's understanding of parallel programming. In particular, we wanted to provide the user with parallel programming methods which would be easily integrated with other parts of the life cycle. Moreover, we wanted the programmer to interact with the assistant while writing parallel programs. The parallel programming assistant interactively aids the user in developing parallel programs. Instead of automatically detecting implicit parallelism in sequential code and subsequently transforming it, the parallel programming assistant analyzes statements as they are entered and immediately gives the user feedback on whether they hinder parallelization. Moreover, the assistant tells the user if the dependencies in the program which hinder parallelization can be removed by transformation. The parallel programming assistant supports object-based development. In the object-based paradigm, the decomposition of a system is based upon the concept of an object [2]. An object is a “thing” that has the capacity to store information, manipulate its own information, carry out some task upon request from an object, and activate an object. Objects are not only things where we store data, such as a line or a collection of records, but are also more powerful things which represent components in a software system such as a user interface. The first mentioned objects are data objects , the last mentioned are processing objects . The expressive power of an object-based language makes it easier for the parallel programming assistant to gather semantics about the program which it then uses to decide how to form parallel language constructs. There are two programming activities within the assistant: 1) specifying and implementing objects, and 2) writing statements that call the methods of these objects. The user does not have to carry out (or complete) activity 1) before 2) and he can freely go from one to the other. In parallel programming these activities involve: P1) partitioning an object in order to enable parallel execution of methods on the object (methods-partitioning); or partitioning an object to enable parallel execution of methods on objects within the object, (object-partitioning) and P2) writing parallel statements (i.e. parallel loops and parallel blocks). An example of a simple parallel block under construction within the parallel programming assistant is: While the block is under construction, the assistant divides it into regions such that statements in a region can be called in parallel. As statements are entered the configuration of the regions changes. When all statements have been entered, and all information is available, the TentativeParallelBlock is changed to zero or more ParallelBlocks. In the example above, the assistant examines whether the two statements are dependent by method-partitioning the object Line, such that the methods setfrom and setto are in separate partitions. Since the object Line is self-contained the assistant only needs to look for dependencies within the object Line. More complex cases arise when the assistant needs to detect dependencies between statements that call methods on separate processing objects which are not self-contained. In this case the object which contains the called objects has to be object-partitioned. The second language construct which the assistant helps the user creating is a parallel loop: As the programmer enters statements to the loop above, the assistant examines whether the objects hinder parallelization of the loop. The assistant first checks whether the structure of the object hinders partitioning of the object. Then, it checks whether the methods hinder parallelization, and finally whether the iterator of the object hinders its partitioning. When homogeneous objects, such as Lines, are partitioned, each partition gets its own set of methods. Each processor then accesses one of these partitions. In a loop, objects are not only partitioned, but also multiplied. An object such as Line is multiplied so that there are P copies, one for each processor. We specified and designed the parallel programming assistant using the object-based paradigm to software development. The experience we gained in object-based software development was helpful in designing the transformations on the objects for the parallel programming assistant. The interactive nature of the parallel programming assistant gives the user the opportunity to intervene when information is missing, that is when the implementation of objects is incomplete. An object-based language allows us to associates attributes to software objects and their methods. This provides more flexibility in the design of the parallel programming assistant, since the attributes can determine the type of transformations. As more types of objects for parallel programming become known, more transformations can be added to the assistant.
---
paper_title: Semi-automatic extraction and exploitation of hierarchical pipeline parallelism using profiling information

paper_content:

In recent years multi-core computer systems have left the realm of high-performance computing and virtually all of today's desktop computers and embedded computing systems are equipped with several processing cores. Still, no single parallel programming model has found widespread support and parallel programming remains an art for the majority of application programmers. In addition, there exists a plethora of sequential legacy applications for which automatic parallelization is the only hope to benefit from the increased processing power of modern multi-core systems. In the past automatic parallelization largely focused on data parallelism. In this paper we present a novel approach to extracting and exploiting pipeline parallelism from sequential applications. We use profiling to overcome the limitations of static data and control flow analysis enabling more aggressive parallelization. Our approach is orthogonal to existing automatic parallelization approaches and additional data parallelism may be exploited in the individual pipeline stages. The key contribution of this paper is a whole-program representation that supports profiling, parallelism extraction and exploitation. We demonstrate how this enhances conventional pipeline parallelization by incorporating support for multi-level loops and pipeline stage replication in a uniform and automatic way. We have evaluated our methodology on a set of multimedia and stream processing benchmarks and demonstrate speedups of up to 4.7 on a eight-core Intel Xeon machine.
---
paper_title: A scalable approach to thread-level speculation

paper_content:

While architects understand how to build cost-effective parallel machines across a wide spectrum of machine sizes (ranging from within a single chip to large-scale servers), the real challenge is how to easily create parallel software to effectively exploit all of this raw performance potential. One promising technique for overcoming this problem is Thread-Level Speculation (TLS), which enables the compiler to optimistically create parallel threads despite uncertainty as to whether those threads are actually independent. In this paper, we propose and evaluate a design for supporting TLS that seamlessly scales to any machine size because it is a straightforward extension of writeback invalidation-based cache coherence (which itself scales both up and down). Our experimental results demonstrate that our scheme performs well on both single-chip multiprocessors and on larger-scale machines where communication latencies are twenty times larger.
---
paper_title: Automatic Sequential to Parallel Code Conversion The S2P Tool and Performance Analysis

paper_content:

The way software programs are being written has been redefined since the introduction of multicore processors. Software developers have started writing parallel programs that are robust and scalable. This would ensure use of processor power being made available in the form of multiple cores. Though this trend is increasing, there are legacy applications that have been developed over the past few decades. Most of these applications are inherently sequential making no use of multithreading or parallel programming. If such applications are ported to execute on the multicore hardware as they are then optimal usage of all cores is not guaranteed. Such applications would ideally utilize only one core and the other cores would remain idle, unless the operating system supports some parallelism while scheduling. Hence there is a need to convert such legacy sequential codes to their parallel versions so that multicore hardware is exploited to the fullest. In this paper we present a tool that we have developed to automatically convert a sequential C code to parallel code. This Sequential to Parallel (S2P) tool is still in the development phase. We also discuss other parallelization tools available today, compare such tools with S2P tool and present our performance analysis results on different kind of multicore hardware.
---
paper_title: Extracting coarse-grain parallelism in general-purpose programs

paper_content:

While the chip multiprocessor (CMP) has quickly become the predominant processor architecture, its continuing success largely depends on the parallelizability of complex programs. In the early 1990s great successes were obtained to extract parallelism from the inner loops of scientific computations. In this paper we show that significant amounts of coarse-grain parallelism exists in the outer program loops, even in general-purpose programs. This coarse-grain parallelism can be exploited efficiently on CMPs without additional hardware support.
---
paper_title: Interprocedural Analysis for Parallelization

paper_content:

This paper presents an extensive empirical evaluation of an interprocedural parallelizing compiler, developed as part of the Stanford SUIF compiler system. The system incorporates a comprehensive and integrated collection of analyses, including privatization and reduction recognition for both array and scalar variables, and symbolic analysis of array subscripts. The interprocedural analysis framework is designed to provide analysis results nearly as precise as full inlining but without its associated costs. Experimentation with this system on programs from standard benchmark suites demonstrate that an integrated combination of interprocedural analyses can substantially advance the capability of automatic parallelization technology.
---
paper_title: Identifying potential parallelism via loop-centric profiling

paper_content:

The transition to multithreaded, multi-core designs places a greater responsibility on programmers and software for improving performance; thread-level parallelism (TLP) will be increasingly relied upon in addition to instruction-level parallelism (ILP) and increased clock frequency. Deciding where to try to parallelize code is difficult, especially for large, complex applications or those where the original developers have moved on. Outer loops are relatively easy targets for parallelization, but traditional profilers focus primarily on functions and hot inner loops. To aid in programmers' parallelization efforts, we introduce the concept of loop-centric profiling to provide a hierarchical view of how much time is spent in a loop and the loops nested within it.This paper introduces two techniques for loop profiling. First, we describe an instrumentation-based approach that gathers highly detailed and accurate information about loop behavior. Second, we present a sampling approach that achieves similar results with negligible overhead. The paper concludes with a case study evaluating the tool on several SPEC 2000 benchmarks.
---
paper_title: Measuring Parallelism in Computation-Intensive Scientific/Engineering Applications

paper_content:

Describes COMET, (concurrency measurement tool), a software tool for measuring parallelism in large scientific/engineering applications. The proposed tool measures the total parallelism present in programs, filtering out the effects of communication/synchronization delays, finite storage, limited number of processors, the policies for management of processors and storage, etc. Although an ideal machine that can exploit the total parallelism is not realizable, such measures would aid the calibration and design of various architectures/compilers. The proposed software tool accepts ordinary Fortran programs as input. Therefore, parallelism can be measured easily on many fairly big programs. Some measurements for parallelism obtained with the help of this tool are also reported. It is observed that the average parallelism in the chosen programs is in the range of 500-3500 Fortran statements executing concurrently in each clock cycle in an idealized environment. >
---
paper_title: Kismet: parallel speedup estimates for serial programs

paper_content:

Software engineers now face the difficult task of refactoring serial programs for parallel execution on multicore processors. Currently, they are offered little guidance as to how much benefit may come from this task, or how close they are to the best possible parallelization. This paper presents Kismet, a tool that creates parallel speedup estimates for unparallelized serial programs. Kismet differs from previous approaches in that it does not require any manual analysis or modification of the program. This difference allows quick analysis of many programs, avoiding wasted engineering effort on those that are fundamentally limited. To accomplish this task, Kismet builds upon the hierarchical critical path analysis (HCPA) technique, a recently developed dynamic analysis that localizes parallelism to each of the potentially nested regions in the target program. It then uses a parallel execution time model to compute an approximate upper bound for performance, modeling constraints that stem from both hardware parameters and internal program structure. Our evaluation applies Kismet to eight high-parallelism NAS Parallel Benchmarks running on a 32-core AMD multicore system, five low-parallelism SpecInt benchmarks, and six medium-parallelism benchmarks running on the finegrained MIT Raw processor. The results are compelling. Kismet is able to significantly improve the accuracy of parallel speedup estimates relative to prior work based on critical path analysis.
---
paper_title: The Cilkview scalability analyzer

paper_content:

The Cilkview scalability analyzer is a software tool for profiling, estimating scalability, and benchmarking multithreaded Cilk++ applications. Cilkview monitors logical parallelism during an instrumented execution of the Cilk++ application on a single processing core. As Cilkview executes, it analyzes logical dependencies within the computation to determine its work and span (critical-path length). These metrics allow Cilkview to estimate parallelism and predict how the application will scale with the number of processing cores. In addition, Cilkview analyzes cheduling overhead using the concept of a "burdened dag," which allows it to diagnose performance problems in the application due to an insufficient grain size of parallel subcomputations. Cilkview employs the Pin dynamic-instrumentation framework to collect metrics during a serial execution of the application code. It operates directly on the optimized code rather than on a debug version. Metadata embedded by the Cilk++ compiler in the binary executable identifies the parallel control constructs in the executing application. This approach introduces little or no overhead to the program binary in normal runs. Cilkview can perform real-time scalability benchmarking automatically, producing gnuplot-compatible output that allows developers to compare an application's performance with the tool's predictions. If the program performs beneath the range of expectation, the programmer can be confident in seeking a cause such as insufficient memory bandwidth, false sharing, or contention rather than inadequate parallelism or insufficient grain size.
---
paper_title: Towards a holistic approach to auto-parallelization: integrating profile-driven parallelism detection and machine-learning based mapping

paper_content:

Compiler-based auto-parallelization is a much studied area, yet has still not found wide-spread application. This is largely due to the poor exploitation of application parallelism, subsequently resulting in performance levels far below those which a skilled expert programmer could achieve. We have identified two weaknesses in traditional parallelizing compilers and propose a novel, integrated approach, resulting in significant performance improvements of the generated parallel code. Using profile-driven parallelism detection we overcome the limitations of static analysis, enabling us to identify more application parallelism and only rely on the user for final approval. In addition, we replace the traditional target-specific and inflexible mapping heuristics with a machine-learning based prediction mechanism, resulting in better mapping decisions while providing more scope for adaptation to different target architectures. We have evaluated our parallelization strategy against the NAS and SPEC OMP benchmarks and two different multi-core platforms (dual quad-core Intel Xeon SMP and dual-socket QS20 Cell blade). We demonstrate that our approach not only yields significant improvements when compared with state-of-the-art parallelizing compilers, but comes close to and sometimes exceeds the performance of manually parallelized codes. On average, our methodology achieves 96% of the performance of the hand-tuned OpenMP NAS and SPEC parallel benchmarks on the Intel Xeon platform and gains a significant speedup for the IBM Cell platform, demonstrating the potential of profile-guided and machine-learning based parallelization for complex multi-core platforms.
---
paper_title: A practical automatic polyhedral parallelizer and locality optimizer

paper_content:

We present the design and implementation of an automatic polyhedral source-to-source transformation framework that can optimize regular programs (sequences of possibly imperfectly nested loops) for parallelism and locality simultaneously. Through this work, we show the practicality of analytical model-driven automatic transformation in the polyhedral model -- far beyond what is possible by current production compilers. Unlike previous works, our approach is an end-to-end fully automatic one driven by an integer linear optimization framework that takes an explicit view of finding good ways of tiling for parallelism and locality using affine transformations. The framework has been implemented into a tool to automatically generate OpenMP parallel code from C program sections. Experimental results from the tool show very high speedups for local and parallel execution on multi-cores over state-of-the-art compiler frameworks from the research community as well as the best native production compilers. The system also enables the easy use of powerful empirical/iterative optimization for general arbitrarily nested loop sequences.
---
paper_title: Cetus: A Source-to-Source Compiler Infrastructure for Multicores

paper_content:

The Cetus tool provides an infrastructure for research on multicore compiler optimizations that emphasizes automatic parallelization. The compiler infrastructure, which targets C programs, supports source-to-source transformations, is user-oriented and easy to handle, and provides the most important parallelization passes as well as the underlying enabling techniques.
---
paper_title: Automatic Sequential to Parallel Code Conversion The S2P Tool and Performance Analysis

paper_content:

The way software programs are being written has been redefined since the introduction of multicore processors. Software developers have started writing parallel programs that are robust and scalable. This would ensure use of processor power being made available in the form of multiple cores. Though this trend is increasing, there are legacy applications that have been developed over the past few decades. Most of these applications are inherently sequential making no use of multithreading or parallel programming. If such applications are ported to execute on the multicore hardware as they are then optimal usage of all cores is not guaranteed. Such applications would ideally utilize only one core and the other cores would remain idle, unless the operating system supports some parallelism while scheduling. Hence there is a need to convert such legacy sequential codes to their parallel versions so that multicore hardware is exploited to the fullest. In this paper we present a tool that we have developed to automatically convert a sequential C code to parallel code. This Sequential to Parallel (S2P) tool is still in the development phase. We also discuss other parallelization tools available today, compare such tools with S2P tool and present our performance analysis results on different kind of multicore hardware.
---
paper_title: The application visualization system: a computational environment for scientific visualization

paper_content:

A software system for developing interactive scientific visualization applications quickly, with a minimum of programming effort, is described. This application visualization system (AVS) is an application framework targeted at scientists and engineers. The goal of the system is to make applications that combine interactive graphics and high computational requirements easier to develop for both programmers and nonprogrammers. AVS is designed around the concept of software building blocks, or modules, which can be interconnected to form visualization applications. AVS allows flow networks of existing modules to be constructed using a direct-manipulation user interface, and it automatically generates a simple user interface to each module. >
---
paper_title: An object-based parallel programming assistant

paper_content:

Programmers of sequential and parallel computers share the objective of developing fast, reliable programs as efficiently as possible. Already, considerable effort has been made to develop tools and techniques for sequential computers. Several approaches have been devised to meet the parallel programming challenge. Sequential languages have been adapted for parallel computers; new parallel languages designed; and tools developed which aid the programmer in detecting parallel code. A parallel programming assistant can aid the user in several ways: it can carry out tasks that are simple but mundane to the user, it can make comprehension easier for the user by summarizing program information; and it can cooperate with the user in doing a complex task, thus combining its own knowledge with that of the user's. We have developed a parallel programming assistant [1] which supports object-based programming. The main motivation for this work was to explore how an assistant can enhance the programmer's understanding of parallel programming. In particular, we wanted to provide the user with parallel programming methods which would be easily integrated with other parts of the life cycle. Moreover, we wanted the programmer to interact with the assistant while writing parallel programs. The parallel programming assistant interactively aids the user in developing parallel programs. Instead of automatically detecting implicit parallelism in sequential code and subsequently transforming it, the parallel programming assistant analyzes statements as they are entered and immediately gives the user feedback on whether they hinder parallelization. Moreover, the assistant tells the user if the dependencies in the program which hinder parallelization can be removed by transformation. The parallel programming assistant supports object-based development. In the object-based paradigm, the decomposition of a system is based upon the concept of an object [2]. An object is a “thing” that has the capacity to store information, manipulate its own information, carry out some task upon request from an object, and activate an object. Objects are not only things where we store data, such as a line or a collection of records, but are also more powerful things which represent components in a software system such as a user interface. The first mentioned objects are data objects , the last mentioned are processing objects . The expressive power of an object-based language makes it easier for the parallel programming assistant to gather semantics about the program which it then uses to decide how to form parallel language constructs. There are two programming activities within the assistant: 1) specifying and implementing objects, and 2) writing statements that call the methods of these objects. The user does not have to carry out (or complete) activity 1) before 2) and he can freely go from one to the other. In parallel programming these activities involve: P1) partitioning an object in order to enable parallel execution of methods on the object (methods-partitioning); or partitioning an object to enable parallel execution of methods on objects within the object, (object-partitioning) and P2) writing parallel statements (i.e. parallel loops and parallel blocks). An example of a simple parallel block under construction within the parallel programming assistant is: While the block is under construction, the assistant divides it into regions such that statements in a region can be called in parallel. As statements are entered the configuration of the regions changes. When all statements have been entered, and all information is available, the TentativeParallelBlock is changed to zero or more ParallelBlocks. In the example above, the assistant examines whether the two statements are dependent by method-partitioning the object Line, such that the methods setfrom and setto are in separate partitions. Since the object Line is self-contained the assistant only needs to look for dependencies within the object Line. More complex cases arise when the assistant needs to detect dependencies between statements that call methods on separate processing objects which are not self-contained. In this case the object which contains the called objects has to be object-partitioned. The second language construct which the assistant helps the user creating is a parallel loop: As the programmer enters statements to the loop above, the assistant examines whether the objects hinder parallelization of the loop. The assistant first checks whether the structure of the object hinders partitioning of the object. Then, it checks whether the methods hinder parallelization, and finally whether the iterator of the object hinders its partitioning. When homogeneous objects, such as Lines, are partitioned, each partition gets its own set of methods. Each processor then accesses one of these partitions. In a loop, objects are not only partitioned, but also multiplied. An object such as Line is multiplied so that there are P copies, one for each processor. We specified and designed the parallel programming assistant using the object-based paradigm to software development. The experience we gained in object-based software development was helpful in designing the transformations on the objects for the parallel programming assistant. The interactive nature of the parallel programming assistant gives the user the opportunity to intervene when information is missing, that is when the implementation of objects is incomplete. An object-based language allows us to associates attributes to software objects and their methods. This provides more flexibility in the design of the parallel programming assistant, since the attributes can determine the type of transformations. As more types of objects for parallel programming become known, more transformations can be added to the assistant.
---
paper_title: The GRED graphical editor for the GRADE parallel program development environment

paper_content:

Abstract In this paper, we describe a graphical editor GRED as a part of the integrated programing environment GRADE that is intended to support designing, debugging and performance tuning of message-passing programs running on a heterogeneous network of computers. The GRED editor hides the cumbersome details of the underlying low-level message-passing system (which can be either PVM or MPI) by providing visual abstractions but allows the programer to define local computations of the individual processes in C (or in Fortran in the future) independently from the visually supported process management and inter-process communication activities. Visual representation of the critical (i.e. message-passing related) parts of the code can help the user in grasping the complex structure and run-time behavior of the whole parallel application, even if he or she is not an expert in the field of concurrent programing.
---
paper_title: An efficient hybrid algorithm for incremental data flow analysis

paper_content:

Our exhaustive and incremental hybrid data flow analysis algorithms, based on iteration and elimination techniques, are designed for incremental update of a wide variety of monotone data flow problems in response to source program changes. Unlike previous incremental iterative methods, this incremental algorithm efficiently computes precise and correct solutions. We give theoretical results on the imprecision of restarting iteration for incremental update by fixed point iteration which provided motivation for our algorithm design. Described intuitively, the main algorithm idea is to factor the data flow solution on strong connected components of the flow graph into local and external parts, solving for the local parts by iteration and propagating these effects on the condensation of the flow graph to obtain the entire data flow solution. The incremental hybrid algorithm re-performs those algorithm steps affected by the program changes.
---
paper_title: Incremental data-flow analysis algorithms

paper_content:

An incremental update algorithm modifies the solution of a problem that has been changed, rather than re-solving the entire problem. ACINCF and ACINCB are incremental update algorithms for forward and backward data-flow analysis, respectively, based on our equations model of Allen-Cocke interval analysis. In addition, we have studied their performance on a “nontoy” structured programming language L. Given a set of localized program changes in a program written in L, we identify a priori the nodes in its flow graph whose corresponding data-flow equations may be affected by the changes. We characterize these possibly affected nodes by their corresponding program structures and their relation to the original change sites, and do so without actually performing the incremental updates . Our results can be refined to characterize the reduced equations possibly affected if structured loop exit mechanisms are used, either singly or together, thereby relating richness of programming language usage to the ease of incremental updating.
---
paper_title: Incremental Call Graph Construction for the Eclipse IDE

paper_content:

A call graph is defined as a set of directed edges connecting call sites (statements invoking method calls) to corresponding target methods [6]. It is a very powerful tool for program analysis and can be used to: help plan testing strategies, reduce program size (by eliminating sub-routines that are not invoked) and help programmers understand and debug large programs. Often the method invoked due to a specific call is determined at runtime based on the context in which the call is made, hence in a call graph a single call site could have multiple target methods. This is especially evident in object oriented languages where inheritance and polymorphism make method calls highly dependent on the execution context. To get the set of target methods associated with a call site we can either observe one or more executions of the program and note all methods invoked from a call site (dynamic call graph generation) or statically determine the possible methods (static call graph construction). Dynamic call graphs tend to under-estimate the number of target methods for a call site where as static call graphs tend to over-estimate this this number. A theoretically ideal call graph is the union of the dynamic call graphs over all possible executions of the program. Dynamic call graphs are not safe and generating static call graphs is computationally expensive. To ameliorate the overhead we propose an incremental call graph generation approach which will compute graphs for fragments of the program as they are being developed. It will then recursively combine fragments until a graph for the whole program is generated. The graph will be as precise as corresponding traditional algorithms and will present, upon completion, a safe call graph.
---
paper_title: On Using Incremental Profiling for the Performance Analysis of Shared Memory Parallel Applications

paper_content:

Profiling is often the method of choice for performance analysis of parallel applications due to its low overhead and easily comprehensible results. However, a disadvantage of profiling is the loss of temporal information that makes it impossible to causally relate performance phenomena to events that happened prior or later during execution. We investigate techniques to add temporal dimension to profiling data by incrementally capturing profiles during the runtime of the application and discuss the insights that can be gained from this type of performance data. The context in which we explore these ideas is an existing profiling tool for OpenMP applications.
---
paper_title: Identifying potential parallelism via loop-centric profiling

paper_content:

The transition to multithreaded, multi-core designs places a greater responsibility on programmers and software for improving performance; thread-level parallelism (TLP) will be increasingly relied upon in addition to instruction-level parallelism (ILP) and increased clock frequency. Deciding where to try to parallelize code is difficult, especially for large, complex applications or those where the original developers have moved on. Outer loops are relatively easy targets for parallelization, but traditional profilers focus primarily on functions and hot inner loops. To aid in programmers' parallelization efforts, we introduce the concept of loop-centric profiling to provide a hierarchical view of how much time is spent in a loop and the loops nested within it.This paper introduces two techniques for loop profiling. First, we describe an instrumentation-based approach that gathers highly detailed and accurate information about loop behavior. Second, we present a sampling approach that achieves similar results with negligible overhead. The paper concludes with a case study evaluating the tool on several SPEC 2000 benchmarks.
---
paper_title: Software behavior oriented parallelization

paper_content:

Many sequential applications are difficult to parallelize because of unpredictable control flow, indirect data access, and input-dependent parallelism. These difficulties led us to build a software system for behavior oriented parallelization (BOP), which allows a program to be parallelized based on partial information about program behavior, for example, a user reading just part of the source code, or a profiling tool examining merely one or few executions. The basis of BOP is programmable software speculation, where a user or an analysis tool marks possibly parallel regions in the code, and the run-time system executes these regions speculatively. It is imperative to protect the entire address space during speculation. The main goal of the paper is to demonstrate that the general protection can be made cost effective by three novel techniques: programmable speculation, critical-path minimization, and value-based correctness checking. On a recently acquired multi-core, multi-processor PC, the BOP system reduced the end-to-end execution time by integer factors for a Lisp interpreter, a data compressor, a language parser, and a scientific library, with no change to the underlying hardware or operating system.
---

Title: A Review of Parallelization Tools and Introduction to EasyPar

Section 1: INTRODUCTION
Description 1: Provide a background on the history and need for parallel programming, the rise of multicore processors, and the complications introduced by parallelization. Highlight the significance of parallel programming tools.

Section 2: PARALLELIZATION TECHNIQUES
Description 2: Give an overview of various parallelization techniques and compare them based on their effectiveness, learning curve, and code efficiency.

Section 3: Automatic Parallelization
Description 3: Discuss the concept of automatic parallelization and its limitations. Mention specific examples and the inherent challenges related to automatic parallelization tools.

Section 4: Semiautomatic Parallelization
Description 4: Explain the semiautomatic parallelization techniques and how they involve programmer input to achieve better parallelism.

Section 5: Parallel Programming Languages
Description 5: Introduce programming languages specifically designed for parallel coding, their paradigms, and their adoption challenges.

Section 6: Hardware Support
Description 6: Describe hardware support mechanisms like transactional memory and their roles in concurrent programming.

Section 7: Parallel Programming APIs
Description 7: Detail the different parallel programming APIs available, such as MPI, OpenMP, CUDA, and their use cases.

Section 8: CLASSIFICATION OF PARALLELIZATION TOOLS
Description 8: Present the three classifications of parallelization tools based on stages of parallelization, the era of tool development, and graphical assistance capabilities.

Section 9: First Generation Tools (FGT)
Description 9: Describe the first-generation tools developed before the multicore era, focusing on their loop-level parallelization capabilities.

Section 10: Second Generation Tools (SGT)
Description 10: Explain the second-generation tools developed for multicore architectures emphasizing task-level parallelization.

Section 11: Graphical Assistance Tools
Description 11: Discuss tools that provide graphical visualization to aid in parallel program development and reduce the programmer's burden.

Section 12: PARALLEL PROCESSING TOOLS
Description 12: Review existing parallelization tools and techniques, both recent and older, mentioning their features and limitations.

Section 13: EASYPAR
Description 13: Introduce EasyPar, its components, and novel techniques for real-time analysis of code dependencies during development. Highlight the performance improvements and the use of GPUs and database-driven compilers.

Section 14: CONCLUSION
Description 14: Summarize the issues of parallel programming, the necessity for better tools, and the innovative solutions proposed by EasyPar and similar tools.