Array redistribution is required very often in programs on distributed memory parallel computers. It is essential to use efficient algorithms for redistribution, otherwise the performance of the programs may degrade considerably. We focus on automatic generation of communication routines for multi dimensional redistribution. The principal advantage of this work is to gain the ability to handle redistribution between arbitrary source and destination processor sets and between arbitrary source and destination distribution schemes. We have implemented these algorithms using Parallelware communication library. Some optimization techniques for our algorithms are also proposed. Experimental results show the efficiency and flexibility of our techniques compared to other redistribution works.

Array redistribution is required often in programs on distributed memory parallel computers. It is essential to use efficient algorithms for redistribution, otherwise the performance of the programs may degrade considerably. The redistribution overheads consist of two parts: index computation and interprocessor communication. If there is no communication scheduling in a redistribution algorithm, the communication contention may occur, which increases the communication waiting time. In order to solve this problem, we propose a technique to schedule the communication so that it becomes contention-free. Our approach initially generates a communication table to represent the communication relations among sending nodes and receiving nodes. According to the communication table, we then generate another table named communication scheduling table. Each column of the communication scheduling table is a permutation of receiving node numbers in each communication step. Thus the communications in our redistribution algorithm are contention-free. Our approach can deal with multi-dimensional shape changing redistribution.

Abstract We herein describe a compiler generator, Rie, which is based on a one‐pass‐type attribute grammar. LR‐attributed grammars are one class of attribute grammars in which attribute evaluation can be performed in one pass during LR parsing without creating a parse tree. Rie was developed based on a variant of an LR‐attributed grammar called ECLR‐attributed grammar (equivalence class LR‐attributed grammar), in which equivalence relations are introduced into the LR‐attributed grammar. Rie generates a one‐pass compiler from a compiler description given in attribute grammar form. Many language processors have been developed using Rie. The generated compiler is only about 1.8 times slower than a handwritten compiler, which is fairly efficient for a compiler generated from formal descriptions.

In this paper, we present a new scalar architecture for high-speed vector processing. Without using cache memory, the proposed architecture tolerates main memory access latency by introducing slide-windowed floating-point registers with data preloading feature and pipelined memory. The architecture can hold upward compatibility with existing scalar architectures. In the new architecture, software can control the window structure. This is the advantage compared with our previous work of register-windows. Because of this advantage, registers are utilized more flexibly and computational efficiency is largely enhanced. Furthermore, this flexibility helps the compiler to generate efficient object codes easily.

A description is given of features which were added to a conventional programming language that will manipulate streams of values. A stream is a sequence of values of a certain fixed type. The number of elements of a stream may be determined at execution time, and evaluation of each element can be postponed until its value is actually needed. Many programs can be expressed naturally and clearly as networks of processes communicating by means of streams. The network is called a composite function and consists of several component functions. Since component functions are connected solely by streams, they greatly increase the flexibility of combinations and the reusability of programs. Loop statements can be considered as iterative statements over streams. One general problem in these networks is the mechanism of terminating each process of the network. A practical solution for this problem is presented. Comparisons to other programming styles, such as coroutines, Lisp, functional programming, and dataflow languages, are described. Three modes of execution are considered for the implementation of composite functions: parallel mode, coroutine mode, and inline mode. In the inline mode, a composite function is expanded and transformed into a single function, realizing maximum run-time efficiency. Algorithms for this expansion are given.>