Introduction to Special Issue
on Compilers and Languages for Parallel and Distributed Computers
                 IEEE Trans. on Parallel and Distributed Systems
                      Vol. 10, No. 2, February 1999


It has been several years since the last special issue 
of TPDS on Parallel Languages and Compilers in July 1991.
Compared to several years ago, parallel computers have become
much more accessible to users and for a wider range of applications.
It has also presented great opportunities for the researchers
to test the effectiveness of many ideas proposed in the past. 
While many ideas survived the tests, others have shown severe limitations,
either because they are less important than expected, 
or they turn out to be difficult to implement.
Today, researchers in this field have placed more emphasis 
on testing new ideas through practical experiments. 
People are generally not satisfied with paper examples, or
simplified experimentation based only on synthetic workloads.

This emphasis on experimentation with real workloads 
has contributed to many important findings in the
last several years. For example,
it has now been widely recognized that the compilers cannot
analyze individual program constructs and single performance
objectives in isolation, and hope to achieve a good overall performance.
But rather, it has to analyze many related program constructs,
often the entire program, in order to exploit both parallelism and
data locality, to deploy efficient communication, and to reduce
task scheduling and synchronization overheads.  Several 
compiler techniques for such "wide-scope" analyses have been 
proposed, implemented in prototype compilers,
and tested with real programs. 
They have shown very good results.

Today, the number of parallel computers in use have 
increased substantially compared to only a few years ago,
thanks to the popularity of small-scale multiprocessor workstations
and servers. Parallel and distributed processing has also been extended
significantly toward both finer granularity at the instruction-level,
and coarser granularity at the process-level in distributed systems.
Consider the prospect of one-billion transistors on a single
chip and that of numerous computers connected via superfast networks, 
one important question to ask is how the research of compilers and languages
can contribute to the effective use of such extensive resources 
on such wide range of platforms. The challenge is extremely difficult, 
but it is also very exciting. Numerous opportunities exist
for our research community to explore.

It is in this context that we proposed a special issue on
Compilers and Languages for Parallel and Distributed Computers
to capture a snapshot of the current research in this area,
and to motivate effort in exploring new opportunities.
We received thirty-three submissions whose topics range from
instruction-level parallelism to distributed concurrent tasks,
and from HPF (High Performance Fortran) to parallel C.
We are grateful to the authors and the reviewers for their
contribution to this special issue.
Based on the reviews, we have selected five papers in this special issue.
Each paper has been reviewed by at least three referees. 
The papers are selected based on their novelty, technical soundness 
and presentation clarity.

Yingchun Zhu and Laurie Hendren's paper, ``Locality Analysis for
Parallel C Programs,'' presents a compiler algorithm to
improve data locality in programs written in a parallel dialect
of C called EARTH-C. The algorithm determines
when an indirect reference via a pointer can be safely
assumed to be a local access. It also automatically specializes 
functions in order to take advantage of the locality specific to 
the particular calling contexts.
This algorithm is implemented in the EARTH-C compiler for
the EARTH-MANNA multithreaded architecture which consists of
Intel i860 XP CPUs.

In ``A Linear Algebra Framework for Automatic Determination
of Optimal Data Layouts,'' M. Kandemir, A. Choudhary,
N. Shenoy, P. Banerjee and J. Ramanujam describe a compiler
technique, based on hyperplanes in linear algebra,
which automatically determines suitable memory layouts
for sequential and parallel programs to improve spatial locality.
They tested their algorithm with eight programs on two
distributed-shared-memory multiprocessors, the Convex Exemplar
SPP-2000 and the SGI Origin 2000.

The paper by Yu-Kwong Kwok and Ishfaq Ahmad, ``FASTEST:
A Practical Low-Complexity Algorithm for Compile-Time
Assignment of Parallel Programs to Multiprocessors,''
presents an efficient task scheduling algorithm,
and evaluates it with both synthetic programs and a few real
applications. The algorithm combines
list scheduling with neighborhood search and its
time complexity is linearly proportional
to the number of precedence edges.

In the paper ``The LRPD Test: Speculative Run-Time Parallelization
of Loops with Privatization and Reduction Parallelization,''
Lawrence Rauchwerger and David Padua go beyond static analysis
for loop parallelization by performing run-time tests
on data dependences and privatizable arrays during speculative
parallel execution of loop iterations. This approach provides
new opportunities for medium-grained parallel execution. Experimental
results are reported for a number of PERFECT benchmarks.

Eric Tseng and Jean-Luc Gaudiot's paper,
``Communication Generation for Aligned and Cyclic(K) Distributions
Using Integer Lattice,'' addresses the issue of optimizing
communication in SPMD codes on distributed-memory machines.
They propose an approach to reduce inspector-like code which
often incurs a high cost. They model the problem after an integer
lattice and present a new algebraic solution.

In closing, we would like to express our gratitude to
Dr. Duncan Lawrie, former Editor in Chief of TPDS,
and Dr. Jack Stankovic, the present Editor in Chief,
for their support of this special issue. We would also 
like to express our sincere thanks to all referees 
for their prompt and thorough reviews.

Zhiyuan Li, Guest Editor
Department of Computer Sciences,
Purdue University,
West Lafayette, IN 47907

Pen-Chung Yew, Guest Editor
Department of Computer Science and Engineering,
University of Minnesota,
200 Union Street,
Minneapolis, MN 55455