Search

Most scientific applications rely on parallel multiprocessor computing to enhance performance. However, the irregular loops within these applications obstruct the parallelism analysis at compile-time. Rauchwerger et al. presented a run-time method to extract the hidden parallelism in a program using dependence chains. The relative overhead degrades this approach's performance due to the mass storage requirement and huge array reference processing. In this study, a new predecessor/successor approach is developed in which high-level predecessor/successor information is recorded and processed efficiently. A predecessor/successor table is constructed first in the inspector phase so that only the successor iterations in the current wavefront need to be examined, instead of the entire loop iterations during wavefront scheduling. Usually, the performance of dependence chain approach degrades dramatically for a hot-spot access pattern, but our scheme works very efficiently in this case. The experimental results using synthetic code and real programs are presented to prove the superiority of the proposed approach.

Generating the local memory access sequence is an important issue while compiling a data-parallel language into an SPMD code. There are many researches dealing with this issue for cyclic(k) distribution in simple subscripts. But the problem becomes highly complicated when the array references are with complex subscripts. One of the complex array reference functions is array subscript containing multiple induction variables (MIV subscripts). MIV is an affine combination of two or more nested loop indices in a single dimension. In this paper, we develop a general method in O(k) time to evaluate the start element for a given global start element. We compute the course distance first, and then traverse the FSM until the start element is found. In our method, the FSM table constructed in the one-level algorithm [J. Parallel Distr. Comput. 26(1) (1995) 72] can be used directly, but in the method of Ramanujam et al. [Languages and Compilers for Parallel Computing, vol. 1366. Springer-Verlag, 1998, p. 49] the l , r vectors of the processor must be evaluated for each global start element and the time-expensive operations like division and mod are required to check the space boundary of processors. Experimental results have revealed our method is more efficient than theirs.

Processor-in-memory (PIM) architectures have recently been proposed, with the objective of reducing the performance gap between processor and memory. An earlier study of Huang and Chu [Proceedings of 2nd Workshop on Intelligent Memory Systems, Cambridge, MA, 2000] designed a statement-based parallelizing system, SAGE, to exploit the potential benefits of PIM. This study extends this system to achieve better performance. Several comprehensive optimization approaches, including self-patch weight evaluation, loop splitting for PIM, intelligent memory operation (IMOP) recognition, and tiling for PIM, are devised to produce execution schedules with improved load balance. Experimental results confirm the effectiveness of the proposed method.

How to generate local memory access sequence and communication sets efficiently is an important issue in compiling a data-parallel language into a single program multiple data (SPMD) code for distributed-memory machines. Many methods have been developed for generating local memory access sequence. In this paper, we focus on the problem of communication sets generation. The local block distance between two active elements with the same offset and destination (source) in a processor will be investigated. We develop an algorithm for the sending phase and receive-execute phase, respectively. Our algorithms do not need to compute send and receive patterns and lose no communication sets while there exist incomplete blocks that cannot constitute a send or receive pattern. Experimental results showed that our method outperforms other previous work.

Generating the local memory access sequences is an integral part of compiling a data-parallel program into an SPMD code. Most previous research into local memory access sequences have focused on one-dimensional arrays distributed with CYCLIC(k) distribution. The local memory access sequences for multidimensional arrays with independent subscripts are produced by repeatedly applying the method for one-dimensional arrays. However, the task becomes highly complex when subscripts are coupled such that the subscripts in different dimensions depend on the same loop induction variables. This paper presents an efficient approach to computing the iterations executed on each processor by exploiting repetitive patterns in memory accesses. Smaller iteration tables than those of Ramanujam [Code generation for complex subscripts in data-parallel programs, in: Z. Li et al. (Eds.), Languages and Compilers for Parallel Computing, Lecture Notes in Computer Science, vol. 1366, Springer-Verlag, Berlin, 1998, pp. 49-63] are used, the iteration gap table is not required. The method has been implemented on an IBM SP2. Experimental results demonstrate the efficiency of the proposed method.

Generating local memory access sequence is a critical issue in distributed-memory implementations of data-parallel languages. In this paper, for arrays distributed block-cyclically on multiple processors, we introduce a novel approach to the local memory access sequence generation using the theory of permutation. By compressing the active elements in a block into an integer, called compress number, and exploiting the fact that there is a repeating pattern in the access sequence, we obtain the global block cycle. Then, we show that the local block cycle can be efficiently enumerated as closed forms using the permutation of global block cycle. After decompressing the compress number in the local block cycle, the local block patterns are restored and the local memory access sequence can be quickly generated. Unlike other works, our approach incurs no run-time overhead.

Data dependence analysis is the most essential process while parallelizing a sequential program. Most current data dependence tests cannot handle array subscripts that are non-linear expressions. In this paper, we present a new parallelization algorithm, called non-linear array subscripts (NLA) test, to deal with non-linear or complex array subscripts. In this scheme, the iterations subject to loop-carried dependence are scheduled into different wavefronts, while the iterations with no loop-carried dependence are assigned into the same wavefront. Based on the wavefront information, the original loop is then transformed into parallel code. Our experimental results on shared-memory parallel machines HP SPP2000 and ALR Quad6 prove the high effectiveness of the NLA test.

In order to exploit potential parallelism of loops, in which the array access patterns cannot be analyzed at compile-time, parallelizing compilers must rely on the run-time dependence analysis techniques. The LRPD test is noted in this field for its applicability. It assumes full parallelism and executes speculatively, then examines the correctness of parallel execution after loop termination. We extended the concept and developed a practical run-time technique, called the speculative parallelization with new technology (SPNT) test, to further exploit loop-level parallelism. Two main characteristics make the SPNT test distinguished. The first is improving the success rate of speculative parallelization by eliminating all cross-iteration data dependences except the cross-processor flow dependences. The second is reducing the failure penalty by aborting the speculative parallel execution immediately once a cross-processor flow dependence is detected during the execution. Our experimental results on shared-memory parallel machines HP SPP2000 and ALR QUAD6 prove the high effectiveness of the SPNT test.

Loop interchange is a transformation that exchanges two level of a nested loop for getting maximum performance in a target parallel computer. Loop interchange also is a powerful tool which can be used in a variety of ways to support parallelism. This paper proposed an improved loop interchange algorithm that can determine whether two arbitrary level of loops can be interchanged each other without invalid the data dependence. Conventional loop interchange considered by direction vector, they are constrained only on adjacent loop which lack of efficiency and accuracy. The algorithm is modified by a convinient direction vector that extends the loop interchange to arbitrary level, it has more efficiency and accuracy than previous approaches. We also derived an inequality with which to perform loop interchange by checking their bonds. Finally, interchange of imperfectly nested loop is also discussed, while most of loop interchange studies constrained only on perfectly loop that doesn't meet all conditions in coding program, and some previous approaches that used loop distribution and regular loop interchange to solve imperfect loop, they are still lack of accuracy and efficiency, we have an algorithm to address these problems.

In this paper the fault-tolerant characteristics of the generalized Boolean n-cube network are studied. For processor failures the network is shown to be n+1 (one step) diagnosable. Two efficient algorithms which can diagnose up to n+1 processor failures are presented and their computational complexity are studied.

High performance computing capability is crucial for the advanced calculations of scientific applications. A parallelizing compiler can take a sequential program as input and automatically translate it into a parallel form. But for loops with arrays of irregular (i.e., indirectly indexed), nonlinear or dynamic access patterns, no state-of-the-art compilers can determine their parallelism at compile-time. In this paper, we propose an efficient run-time scheme to compute a high parallelism execution schedule for those loops. This new scheme first constructs a predecessor iteration table in inspector phase, and then schedules the whole loop iterations into wavefronts for parallel execution. For non-uniform access patterns, the performance of the inspector/executor methods usually degrades dramatically, but it is not valid for our scheme. Furthermore, this scheme is especially suitable for multiprocessor systems because of the features of high scalability and low overhead.

Loop interchange is a powerful restructuring technique for supporting vectorization and parallelization. We propose an improved technique to determine whether loops can be interchanged between two non adjacent loops. We also present a method for determining whether we can directly make loop interchange on an imperfectly nested loop. Some experimental results are also presented to show the effectiveness of the method.

We propose an efficient run-time technique to find an optimal parallel execution schedule for partially parallel loops in which synchronizations between iterations are needed to ensure correct program semantics. For efficiency, we combine conventional mark phase and scheduler phase into a single parallel scheduler. The scheduler divides the loop iterations into several chunks then executes the iterations in one chunk in parallel. Our scheme not only runs fast but also achieves an optimal schedule. In addition, an atomic bit-vector operation is introduced to avoid global synchronization overhead and ensure the larger wavefront number is kept when the wavefront number of an iteration will be concurrently updated during scheduling.

Pipeline technique is the major method to increase the performance of single processor, but when processing branch instructions, we must wait the result of branch to decide the next instruction; we call the waiting time "Branch Penalty", which will influence the performance of pipeline processor. Branch target buffer is an important method to resolve the branch penalty, but branch penalty occurs when the prediction incorrect. In this paper, we propose a method to reduce the branch penalty when the prediction falls into an error on branch target buffer. >

Generating local memory access sequences and communication sets efficiently is an important issue while compiling a data-parallel language into a SPMD (Single Program Multiple Data) code. Recently, several approaches have been presented; they are based on the case in which array references are distributed across arbitrary number of processors with arbitrary block sizes using block-cyclic distribution. Typically, in order to generate explicit communication sets, each node program has to scan over the local memory access sequences. In this paper, we focus on two cases. First, array references are aligned to a common template and this template is distributed across processors using block-cyclic distribution. Second, array references are distributed across the same number of processors with same block size. The first case is further classified into one-level and two-level mappings. We construct a block state graph to generate communication sets by scanning only a portion of local memory access sequence. In one-level mappings and the second case, we only need to scan the active elements among the first s local active blocks; while in two-level mappings, only need to scan the active elements among the first /spl alpha/*s local active blocks, where s is the stride of regular section and a is the stride of alignment function. As a result, the efficiency can be greatly improved.