Auto-Parallelizing Compiler for Massive Parallel Computers

在1996年间，我们进行了四个研究课题：1)并行编译器的可视化，2)循环携带依赖关系的并行执行估计，3)分布式存储并行计算机的并行化编译器，4)面向性能的并行化编译器。1)我们开发了支持并行编程和并行化编译器的三维可视化系统Nara View。Nara View从程序流程、并行性和循环嵌套的角度提供了并行程序结构的三维视图，并通过同时显示循环迭代和共享数据的内存分配来表示数据依赖。2.提出了一种估计具有循环携带依赖的循环的并行执行时间的方法，并通过大量的实验进行了验证。这种方法的主要优点是估计的计算代价与循环携带依赖的循环的迭代次数无关。我们通过将问题归结为一个整数线性规划问题来实现这个方法。3.我们开发了一个工具，可以将共享内存并行计算机的并行程序翻译成分布式系统的其他并行形式。这意味着并行化编译器Parafrase-2和我们的工具的组合构成了一个并行和分布式的编译器。我们开发了一个分析模型，称为半马尔可夫内存和缓存一致性干扰模型(SMCI模型)，该模型能够以极低的计算代价预测缓存一致性并行机的性能。该模型可以应用于失效和更新基于广播的高速缓存一致性协议。SMCI模型是构造面向性能并行化编译器的关键技术。

During 1996, we had four research topics : 1) Visualization for parallelizing compilers, 2) Estimating Paralled Execution of loops with Loop-carried Dependences, 3) A parallelizing compiler for distributed memory parallel computers, and 4) Performance oriented parallelizing compilers.1.We have developed Nara View, which is a 3D visualization system for the support of parallel programming and parallelizing compilers. Nara View provides 3D views for the structure of parallel programs in the sense of program flow, parallelism and loop nests, and for representation of data dependence by showing loop iteration and memory allocation of shared data simultaneouusly.2.We have proposed a method to estimate parallel execution time of loops with loop-carried dependences, and validated it by enough number of experiment. The main advantage of this method is that the computational cost of the esitimation is independent to the number of iteration of the loops with loop-carried dependences. We have achieved this method by reducing the problem into an integer linear programming problem.3.We have developed a tool which translates parallel programs for shared memory paralle computers into other parallel forms for distributed systems. It means that the combination of a parallelizing compiler, Parafrase-2, and our tool construct a parallel and distributed compiler. Now we are investigating its optimization such as data distribution.4.We have developed an analytic model, called Semi-Markov Memory and Cache Coherence Interference Model (SMCI model), which can predict the performance of cache coherent parallel computers with extremely inexpensive computational cost. The model can be applied to both invalidate and update broadcast based cache coherence protocol. The SMCI model is a key technique to construct a performance oriented parallelizing compiler.