COMPILE TIME PARTITIONING OF NESTED LOOP ITERATION SPACES WITH NON-UNIFORM DEPENDENCES*

In this paper we address the problem of partitioning nested loops with non-uniform (irregular) dependence vectors. Parallelizing and partitioning of nested loops requires efficient inter-iteration dependence analysis. Although many methods exist for nested loop partitioning, most of these perform poorly when parallelizing nested loops with irregular dependences. Unlike the case of nested loops with uniform dependences these will have a complicated dependence pattern which forms a non-uniform dependence vector set. We apply the results of classical convex theory and principles of linear programming to iteration spaces and show the correspondence between minimum dependence distance computation and iteration space tiling. Cross-iteration dependences are analyzed by forming an Integer Dependence Convex Hull (IDCH). Every integer point in this IDCH corresponds to a dependence vector in the iteration space of the nested loops. A simple way to compute minimum dependence distances from the dependence distance vectors of the extreme points of the IDCH is presented. Using these minimum dependence distances the iteration space can be tiled. Iterations within a tile can be executed in parallel and the different tiles can then be executed with proper synchronization. We demonstrate that our technique gives much better speedup and extracts more parallelism than the existing techniques.     

ON THE OPTIMALITY OF ALLEN AND KENNEDY'S ALGORITHM FOR PARALLELISM EXTRACTION IN NESTED LOOPS

We explore the link between dependence abstractions and maximal parallelism extraction in nested loops. Our goal is to find, for each dependence abstraction, the minimal transformations needed for maximal parallelism extraction. The result of this paper is that Allen and Kennedy's algorithm is optimal when dependences are approximated by dependence levels. This means that even the most sophisticated algorithm cannot detect more parallelism than found by Allen and Kennedy's algorithm, as long as dependence level is the only information available. In other words, loop distribution is sufficient for detecting maximal parallelism in dependence graphs with levels.     

EFFECTIVE PARALLELIZATION TECHNIQUES FOR LOOP NESTS WITH NON-UNIFORM DEPENDENCES

The parallelism of loop nests with non-uniform dependences is difficult to extract and ineffectively explored by the existing parallelization schemes. In this paper, we propose new efficient techniques in extracting parallelism of loop nests with non-uniform dependences using their irregularity. By this way, current highly parallel multiprocessor systems such as multithreaded and clustering multiprocessor systems can be fully utilized. These four mechanisms are (a) parallelization part splitting, (b) partial parallelization decomposition, (c) irregular loop interchange and (d) growing pattern detection. They explore parallelisms of special parallel patterns for nested loops with non-uniform dependences. The loop transformations used in uniform loops are also applied in non-uniform dependence loops after legality tests. We apply the results of classical convex theory and detect special parallel patterns of dependence vectors. We also proposed an algorithm that combines above mechanisms to enhance parallelism. We demonstrate that our technique gives much better speedup and extracts more parallelism than the existing techniques. Thus, we are encouraged by these apparent enhancements to pursue further development.     

多重循环的软件流水技术

为了解决多重循环的指令级并行编译问题，本文提出了反刍方法，以一种新的思维方式处理多重循环，将其视为一个程序流整体，有效地开发了多重循环的并行度．另外，本文还给出了实现反刍方法的基本步骤以及相应的硬件支持．最后，通过一些初步实验的结果验证了本算法的有效性，并讨论了其时间和空间效益，分析了其主要特点.     

一个支持多分支循环最优执行的VLIW体系结构

本首先提出一个能够支持多分支循环程序最优执行的ＶＬＩＷ体系结构模型，然后在这个模型的基础上设计了一个新的主要用于数字信号处理及图象处理应用领域的单片体系结构－ＵＲＰＲ－２。在这个体系结构中，属于不同路径和不同循环体的多个分支操作可以在一个节拍内同时被执行，因此可以在更大范围内开发指讼级并行性，同时还提出了一个种叫作流水控制黑板的机制来支持条件分支操作。ＵＲＰＲ－２不仅能够以很高的速度执行只含有基