SIMD (Single Instruction Multiple Data) extensions are acceleration components integrated in general processor, aiming at extracting instruction and data level parallelism of multimedia and scientific calculation programs. Currently, most of the automatic vectorization methods for SIMD architectures are based on innermost loops. Inner loop vectorization is the common approach for auto-vectorization. This method has been used for many years and its efficiency is widely accepted by people. In this paper, we put forward a better method than inner loop vectorization for some loop nests, which is outer loop vectorization. Outer loop vectorization method means vectorizing the outer loop directly. It can extract more data level parallelism and make the most use of the spatial locality to improve the program efficiency than the inner one which is more suitable for some loop nests. This paper presents the realization. In this paper, we first revisit the preliminary analysis of outer loop vectorization based on Open64 complier. And then, data type conversion and code generation is presented in detail. Finally, we propose two optimization methods, capable of boosting the performance of outer loop vectorization to achieve the acceleration of 20% on average, 50% at most.

Compiling for distributed-memory architectures comprise two main phases. The first phase is to determine computation and data composition. In the 1990s, a great deal of work addressed this problem. The second phase is code generation. However, there is still no effective solution to this problem. Existing methods try to generate codes on the basis of computation and data composition. To enhance the performance of generated codes, various communication optimizations are introduced since communication is one of the main factors degrading the performance. These approaches would bring redundant communication data, as they did not optimize communications jointly with code generation. In this paper, we propose a novel code generation technique for distributed-memory architectures. First, we determine the communication sender and receiver by traversing a loop-based tree structure. To support message aggregation, we find the most appropriate point to insert a message. Secondly, we construct the communication set by proposing some code generation rules, and prove their correctness and accuracy. Redundant communication is thus eliminated. Also, we have evaluated some programs ranging from micro-kernels to applications in NAS parallel benchmarks, and have compared the performance with their message passing interface (MPI), High Performance Fortran (HPF) and Unified Parallel C (UPC) versions. Compared with these versions, our compiler can generate fewer communication points. The generated codes of outperform the HPF and UPC versions and the state-of-the-art, and the average performance can reach 70% of the hand-coded MPI programs.

Structure references are commonly-used at the core of applications in a multitude of domains such as image processing, signal processing, especially the scientific and engineering applications. SIMD instruction sets, as SSE, AVX, AltiVec and 3DNow, provide a promising and widely available avenue for enhancing performance on modern processors. However existing memory accessing shackles limit the achieved performance for structure reference on modern SIMD architectures. In this paper, we propose a novel data layout transformation technology that addresses the accessing obstacles, along with a static analysis technique for detecting the legal loops in where this transformation is suitable. And this approach is implemented in the Optimizing Compiler Open64. The experimental results show that the proposed method can translate application with structure access into vectorizable codes, thereby advancing the execution efficiency adequately.

The difference between vector machine and SIMD extension is analyzed at the very start. The multilevel loop vector code generation algorithm termed Codegen put forward by Kennedy and other fellows can't be directly applied to SIMD extension as it is oriented to vector machine. The vectorization algorithm in state-of-the-art compilers can only process one level of nested loop. In order to vectorize the entire nested loop, a vectorization algorithm based on strip mining called simdcodegen is proposed. Firstly, the formation reason of dependence circles is analyzed and the role of strip mining played in elimination of dependence circles is discussed. Then on the basis of codegen, strip mining is applied on each level of the loop recursively to explore the SIMD parallelism in the nested loop. Although strip mining is always legitimate, the executing cost increases after strip mining. To assure that strip mining is beneficial, that is to say, strip mining can break some dependence circles, cycle broken test is applied before implementation of strip mining. Effectiveness of this method is verified by the experimental results.

Nowadays SIMD extensions became ubiquitous for computational platform, being widely used in signal processing, multimedia, and scientific applications. However, compilers still have difficult in vectorizing some applications, such as computations on non-contiguous and especially interleaved data, and loop nest for which inner loops that carry all the dependencies and external loops with strided memory accesses. In order to solve these problems, we adopt Isomorphic Statements Grouping (ISG) after extending group following UD and DU chains, which group isomorphic computation statements that perform the same operation. And correspondingly, we generate vector permutation instructions according to the target ISA SIMD instructions at the SIMD code generation phase. This approach has been implemented in a compiler based on Open64 which translate C source program to C source program with SIMD intrinsic functions. Experiments with this compiler show that ISG Super Level Parallelism(ISG-SLP) can be used to compile a number of real-world kernels, achieving up to 3.11 speedup.

Code generation belongs to the backend of parallelizing compiler, and is for generating efficient computation and communication code for the target parallel computing system. Traditional research resolve array redistribution mainly by generating communication code that each processor sends all data defined in its local memory to all processors, but this will bring large amount of communication redundancy, which increase with the growth of number of processors. Focusing on this problem, this paper presents an accurate code generation algorithm of array redistribution for distributed-memory architecture. The algorithm determines source processor and goals processor of each array element's migration in array redistribution by the transformation of data decompositions, then generate accurate communication code. The experimental results show that algorithm proposed by this paper can effectively reduce communication redundancy with the processor scale growth, and improve the parallel performance of applications.

The prevalence of control flow, recursive data structures, and general pointer accesses in ordinary programs renders the traditional automatic parallelization techniques unsuitable. OpenMP Decoupled Software Pipelining (DSWP) is proposed to exploit pipeline parallelism lurking in ordinary programs, which cannot be dealt with by traditional techniques. While cost model is important in helping evaluate compiler transformations, guiding the compiler in its optimization process and helping achieve load balancing, existing cost models are too simple to be sufficient for the profit evaluation of OpenMP, especially for DSWPed loops. We propose a compile-time cost model for automatic parallelization profit estimate by extending the existing cost model in Open64 loop nest optimizer (LNO) phase in this paper. Moreover, we improve the OpenMP DSWP algorithm based on our cost model, which increases execution efficiency of automatic parallelization. We evaluate our cost model with loops containing complex memory access patterns and control flow structure, which cannot be dealt with by traditional techniques, and NAS Parallel Benchmarks (NPB) 3.3.1. As a result, evident performance improvement for generated DSWPed loops and programs are obtained by using our model.

Automatic decomposition is a compile technique that maps computation and data onto different processors, and array is one of the main targets processed. Certain arrays, whose migration is the most expensive, are termed as dominant arrays. Since every computing node has its own memory on distributed memory parallel computers (DMPCs), decompositions of dominant arrays have directly impact on the performance of parallel program. To avoid remote data accessing, each definition and use of arrays needs to be distributed consistently, so as that there are too many partition constraints to increase decomposition choices of dominant arrays. We propose an automatic computation and data decomposition algorithm of prioritized dominant array in this paper. Our algorithm ranks arrays according to their potential communication costs, and then finds data decomposition for arrays in the decreasing order of rank. We serialize low rank arrays to enhance the decomposition priority of high rank ones. Finally, serial arrays are to be partitioned if maintaining parallel benefits of previous results. The experimental results show that this algorithm can improve the performance of parallel programs.

The speed of processor accessing local memory is much faster than that of accessing remote memory by communication on distributed memory machines. To reduce the cost brought by the communication the parallel recognition compiler must give efficient computation partition and data distribution, and guarantee that the data needed to visit during computation is kept in the local memories. While in the process of parallel recognition, we observed that in many cases there is no global consistency decomposition; and using multiple fashions of data distribution may improve the performance of parallelism. A consistency combination algorithm for dynamic decomposition that allows data reorganization was presented in this paper. The algorithm starts from the solving of decomposition in single loop nest, and then it fuses different decomposition fashions from the sets of decomposition results and using linear transformation for global data distribution consistence. Our algorithm also takes the structure and the control flow of programs into account to direct the priority order in the process of linear transformation. Effectiveness of our algorithm was shown by verification in the end of this paper.

The recovery of parameter and return-value plays an important role in decompilation, reverse engineering, binary translation and software maintenance etc. Furthermore, related approaches are very useful to inter- procedural analyzing and slicing of binary executable. However, the operations on parameters and return- values always appear obscure after the optimizing phases of a compiler, which will make the recovery hard to realize. In this paper, we present a flow-insensitive but context-sensitive algorithm based on data dependence analysis to get back parameters and return- values. In addition, we discuss our experimental results obtained by applying our techniques to a static binary translation framework. Evidence shows that our method performs well in analyzing the parameters and return-values of executables. We use an IA-64 executable for demonstration, but our techniques are not limited to any particular architecture.

Aiming at the limitations of benchmark tools, the paper brings a model, which is beneficial for NP-based application design, and which ought to be obeyed on the four levels of system, function, task and hardware. Then five formulas are given specifically for Intel NPbased application design. In the third part, an study case and it’s testing result are given with these disciplines and formulas applied. Finally the paper points out under which circumstances can these formulas be applied.