Search

Efficacy of automatic parallelization techniques that rely on source code analysis alone is often limited due to lack of information about runtime characteristics of target applications. In order to exploit runtime application behavior for its parallelization, we need: (1) tools/techniques for dynamic instrumentation and profiling; and (2) a methodology to identify areas of application that are amenable for explicit and speculative parallelization. In this paper, we present an infrastructure that provides above-mentioned facilities to analyze ELF binaries in an emulated runtime environment. The infrastructure, which is implemented as an extension to quick emulator (QEMU), includes a profiling mechanism to capture runtime behavior of an application and an inter-function dependence metric for quantitatively measure the potential for function level parallelism. The dependence metric is an extension of data dependence densities effort [7]. We ran sequential versions of NAS benchmarks through this infrastructure to determine their function level parallelization potential. Resulting data can be consumed for manual parallelization efforts as well as for automated parallelization through compiler feedback during build process. [ABSTRACT FROM PUBLISHER]

Based on three OpenMP program models, the technology of parallel region reconstruction is mainly discussed to implement the improved loop level OpenMP program. Parallel region reconstruction is to expand and merge parallel regions. When reconstructing parallel regions, there are two things should be noted, that is to keep data attribute and data dependence before and after optimization. Experimental results of PPOPP show that after parallel region reconstruction, the improvement of lu1k is maximally up to 28.1%, and the improvement of erle64 is the lowest about 1.87%. The reason of lu1k's highest improvement is that a parallel region is expanded outside a loop of 1024 iterations, which reduce 1023 times of the parallel region creation. The experimental results indicate the technology of parallel region reconstruction reduces the creation of parallel region, and improves the performance of the OpenMP program. [ABSTRACT FROM PUBLISHER]

In this paper, we propose an improved parallelizing algorithm for serial programs without reducing the relevancy to the previous algorithm called PDMA. We add eliminating false dependences to PDMA for higher parallelism, as well as giving the description of the improved algorithm. Finally, this paper shows that the improved algorithm achieves better parallelism than PDMA through example comparison. [ABSTRACT FROM AUTHOR]

Several compile time transformations of loops with simple dependencies have been developed in order to expose possible parallelism in these loops. However, once an irregular data dependence is detected, no attempt is usually made to extract any parallel thread from the loop. In this paper, we present the parallel region execution, a new compile time approach for improving the execution of loops with complex dependencies. It consists of dividing the iteration space of the loop into parallel regions and serial regions, where all the iterations in the parallel regions can be fully executed in parallel. Our parallel region execution technique has been tested on the MasPar machine for various examples and generally resulted in a large speedup. [ABSTRACT FROM PUBLISHER]

Dependence analysis on an Extended Finite State Machine (EFSM) representation of the requirements of a system under test has been used in requirements-based regression testing for regression test suite (RTS) reduction (reducing the size of a given test suite by eliminating redundancies), for RTS prioritization (ordering test cases in a given test suite for early fault detection) or for RTS selection (selecting a subset of a test suite covering the identified dependencies). These particular uses of dependence analysis are based on definitions of various types of control and data dependencies (between transitions in an EFSM) caused by a given set of modifications on the requirements. This abstract considers the definitions of data dependencies, gives examples of incompleteness of existing definitions, and presents insights on completing these definitions. [ABSTRACT FROM PUBLISHER]