In Structured Programming 11 (1990), pp. 157-171.
A preliminary version appeared in Proc. 13th IEEE Computer Software and Applications Conf. (1989), pp. 94-101.

Seymour: A Portable Parallel Programming Language

Russ Miller
Dept of Comp Sci & Eng, State University of New York at Buffalo

Quentin F. Stout
EECS Department, University of Michigan

Abstract: The interconnection scheme among processors (or between processors and memory) of a parallel computer significantly affects the running time of programs. Therefore, efficient parallel algorithms must take the interconnection scheme into account. This in turn entails tradeoffs between efficiency and portability among different architectures. The problem we address in this paper is that of developing algorithms which are portable among fine-, medium-, and coarse-grained parallel architectures such as hypercubes, meshes, and pyramids, while yielding a fairly efficient implementation on each.

This paper introduces Seymour, a high-level data parallel programming language that can be used to design, express, and implement efficient portable parallel algorithms. The foundation of Seymour is based on the emerging approach of designing parallel algorithms based on standardized global operations such as prefix, broadcast, sort, compression, and associative read. Seymour also incorporates fundamental paradigms, such as divide-and-conquer, reduce-and-create-cross-product, and reduce-and-compress, which are derived from theoretical parallel algorithms. Seymour redirects the difficulties of portability and efficiency into similar difficulties for the global operations and paradigms. However, the cost of developing efficient implementations of standardized operations on the various target architectures can be amortized over numerous algorithms.

Keywords: parallel programming paradigms, global data movement operations, portable parallel programs, efficiency, parallel computing, computer science

Russ Miller (