Auto-Parallelizing Compiler for Massive Parallel Computers

在1996年期间，我们有四个研究课题：1）并行编译器的可视化，2）估计并行执行循环与循环携带依赖，3）并行编译器的分布存储器并行计算机，和4）面向性能的并行编译器。1.我们开发了奈良视图，这是一个三维可视化系统，以支持并行编程和并行编译器。奈良View从程序流、并行性和循环嵌套的角度提供了并行程序结构的三维视图，并通过直观地显示循环迭代和共享数据的内存分配，提供了数据依赖的表示。2.提出了一种估计循环携带依赖的并行执行时间的方法，并通过大量实验进行了验证。该方法的主要优点是估计的计算代价与循环承载依赖循环的迭代次数无关。3.我们开发了一个工具，可以将共享内存并行计算机的并行程序转换为分布式系统的其他并行形式。这意味着将并行化编译器Parafrase-2和我们的工具相结合，构建了一个并行分布式编译器。现在我们正在研究它的优化，例如数据分布。4.我们开发了一个分析模型，称为半马尔可夫内存和缓存一致性干扰模型（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.