Subject: Paper on Inquiry Intrinsics

From: Rob Schreiber <[email-masked]>
Date: Fri, 17 Jul 92 15:11:56 PDT

I have received (in latex form) a paper on a wide range of
machine-inquiry intrinsics (like number_of_processors()) from
Arnold Krummer and Christoph Ueberhuber
at the Austrian Center for Parallel Computing.   Here, FYI, it is:

%Dear Rob Schreiber,
%
%thank you for your interest. A latex version of our paper
%on system inquiry intrinsics (submitted to Parallel
%Computing) is included in this mail.
%
%
%                           Sincerely 
%
%                                Arnold Krommer
%                                
%----------------------------------------------------------
%Arnold R. Krommer
%Institut for Applied and Numerical Mathematics
%Technical University Vienna
%Wiedner Hauptstr. 8-10/115
%A-1040 WIEN
%
[email-masked]
%
%---------------------------------------------------------
\documentstyle[12pt,fullpage]{article}

\pagestyle{headings}
\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt plus 2pt minus 1pt}
\setcounter{tocdepth}{4}
\setcounter{secnumdepth}{4}
\frenchspacing
\sloppy

\begin{document}
\begin{titlepage}
\title{{\bf Architecture Adaptive Algorithms}}

\author{Arnold R. Krommer\\Christoph W. Ueberhuber\\\\Institute for Applied and
Numerical Mathematics\\Technical University Vienna}

\date{\today}
\end{titlepage}
\maketitle

\begin{abstract}
The architecture adaptive algorithm ({\sc aaa}) methodology introduced in this
paper is an attempt to provide concepts and tools for writing {\em portable\/}
parallel
programs that run {\em efficiently}\/ on a broad range of target machines.
Environment enquiries are defined to
provide
information about the available {\em processors}\/, {\em communication
channels\/},
{\em memory hierarchies}\/, etc. By taking this information into account, a
portable parallel algorithm can adapt its behavior to environment
characteristics and thus increase its {\em efficiency}\/ significantly.

\end{abstract}
\section{Introduction}
On traditional uniprocessor machines, portable programs usually have a good
overall efficiency (due to the power of modern optimizing compilers).
When using vector processors, the programmer must be much more careful to 
utilize fully
the available capacity of all eligible target machines. With parallel systems
the situation is even worse. Portability -- much more difficult to achieve
than on uniprocessor machines -- is by far not enough to ensure a satisfactory
performance over a wide range of parallel computers. Portable programs that
run efficiently on different parallel systems are only possible if they
can adjust themselves to fit the respective computer system they run on. The
essence of such programs are algorithms which are able to 
adapt themselves to different computer architectures:\\ {\sc Architecture 
Adaptive Algorithms}.
 
\subsection{The Idea}
The fundamental idea of the {\sc aaa} methodology has been put into words in
1967 by Peter Naur~\cite{naur67}:
\begin{quote}
{\sl We have to admit a new kind of elements, Environment Enquiries, 
in our common programming languages. These should be designed to place a
carefully chosen set of information about the available equipment at the
disposal of the programmer, for use in directing the control of the process.}
\end{quote}
In context of this quotation (twenty five years ago), 
{\em environment enquiries\/} were supposed to
yield information about machine numbers (radix, minimum and maximum
exponent, etc.) and computer arithmetic. By taking this information into
account,
an algorithm is enabled to adapt itself to machine characteristics and
thus to increase its {\em portability}\/ significantly. After long discussions
{\em arithmetic enquiry functions\/} have been included in the
Fortran\,90~\cite{f90norm} language definition. 

Where multiprocessors are concerned, environment enquiries are to
provide
information about the available {\em processors}\/, {\em communication
channels\/},
{\em memory hierarchies}\/, etc. By taking this information into account, a
portable parallel algorithm can adapt its behavior to environment
characteristics and thus increase its {\em efficiency}\/ significantly.

\subsection{The Necessity}
Programs without explicit parallelism, i.e.\ sequential and implicitly parallel
(functional or logic) programs, cannot be mapped {\em automatically\/} onto
parallel hardware resources if optimum performance is to be achieved.
This is due to the
complexity of the mapping task which is known to be $N\!P$\,complete (Garey,
Johnson~\cite{garey79}).

Programs using explicit parallelism (expressed in shared memory or message
passing languages, {\sc Linda}, etc.) implicitly require certain properties in
the underlying system
to run efficiently (Krommer, Ueberhuber~\cite{krommer92a}, Chapter~3 and 4).
For instance, they require a certain granularity and
topology of the computer, the homogeneity of its processing nodes, the absence of
processor time-sharing, etc. If such a program is ported to a parallel machine
of another type, its efficiency may deteriorate dramatically.

The explicit expression of parallelism is not enough to ensure the efficiency
of portable parallel programs.
Portable programs must {\em adapt}\/
their performance critical sections and features (algorithmic granularity,
communication processes, 
load distribution, etc.) to the architecture of the current parallel computer.

\subsection{The Scope}
The {\sc aaa} approach is intended to provide a methodology for writing programs
that run efficiently on {\em homogeneous}\/ or {\em heterogeneous networks}\/ of
{\em sequential,
vector, SIMD, and MIMD computers}\/.

Computer systems like {\em systolic arrays}\/, {\em dataflow}\/
and {\em reduction machines}\/ -- while attracting considerable interest --
are not dealt with in this report. 
None of these systems is at the moment mature enough to compete as a
cost-effective {\em general purpose\/} computer.
For special applications, such as signal processing, some of
these systems are already applied successfully. However, 
special purpose hardware needs tailor-made software, which keeps 
interest in portable programs low.

\subsection{An Example}
In the following sections, various aspects of the architecture adaptive algorithm
methodology are discussed in some detail.  
Examples are taken from the authors' main area of interest, parallel
quadrature.

Different adaptive quadrature algorithms exploiting coarse grain parallelism
have been discussed so far in literature
(Krommer, Ueberhuber~\cite{krommer91b}). A meta-algorithm comprising a
class of potentially promising algorithms is given by Krommer,
Ueberhuber~\cite{krommer92a}, in Table\,1. This
meta-algorithm has been formulated only for the one-dimensional case
(for functions of one independent variable). A modification for the
multidimensional case can easily be made
(de\,Doncker, Kapenga~\cite{doncker91c}).

The master and all the workers have their own local interval collection which is
processed according to a globally adaptive strategy. The workers
send information about their local integral and error estimates to the master.
Moreover, information concerning workload is exchanged between workers (and
between workers and the master), and
{\em load balancing}\/ is achieved by distributing intervals to be processed 
according to workload information. 

The master process of this meta-algorithm is responsible for
{\em control tasks}\/ like 
initializing,
keeping track of the overall integral and error estimate,
starting new workers, and
terminating the algorithm,
and {\em worker tasks}\/ like
applying a quadrature rule and
load balancing.
The subsumption of control and worker activities under the master process has
been chosen in order to enable
implementations on machines without multitasking facilities.

In the following section, it is shown that the efficiency of a particular
algorithm in this class crucially depends on the underlying computing
environment. Various pieces of information required by an algorithm to
adapt itself to the underlying system will be discussed.  

\section{Required Information} \label{reqinf}
Various kinds of information are required by an architecture
adaptive algorithm:

\begin{description}
\item [{\em Processing Speed}\/:]
Knowledge of the performance of processors is needed for load balancing
purposes. In heterogeneous network-based computing, for example, different
nodes may operate at different speed. Such parallel systems require the
distribution of dissimilar chunks of work adjusted to the individual processor
characteristics. Heterogeneity also occurs in SIMD machines where
a fast control unit contrasts with slow processing elements.
Operations on short arrays should be executed by the control unit of such
machines rather than by the processing elements. Recent investigations (Andrews,
Polychronopoulos~\cite{andrews91}) suggest that heterogeneous environments
may have a better cost/performance ratio than homogeneous systems and therefore
should be included in the range of target machines for parallel software. 

{\footnotesize
{\bf Example:}
The exchange of workload information is part of the load balancing activities
in the
parallel adaptive meta-algorithm in Table\,1. The workload of a worker does not
depend solely
on problem parameters (like error estimates in its local
interval collection), but also on its individual processing speed. A faster
processor should have intervals with larger error estimates in its local
interval collection than a slower one has, as the faster processor is more
powerful
in reducing error estimates (as a result of subdividing intervals).

}

Obtaining an appropriate algorithmic granularity requires knowledge of the
hardware granularity. Thus, for all heterogeneous as well as homogeneous
parallel systems, processor performance information is needed.

{\footnotesize
{\bf Example:}
In the meta-algorithm in Table\,1, load balancing is achieved by transfering
intervals between workers. However, while an interval is being transferred,
neither
the sending nor the receiving worker can process it. Consequently, if
interval processing is fast (with respect to communication speed), it might be
more efficient to process an
interval locally, i.e. to keep a load
{\em imbalance}\/, than to try to balance the load by sending intervals to other
workers.

}

\item [{\em Communication Speed}\/:]
Several performance numbers concerning communication must be known
in order to balance computional load against communication load.  The
{\em communication delay}\/,
i.e. the time required for performing a communication operation, can be divided
into four parts (Bertsekas, Tsitsiklis~\cite{bertsekas89}):
\begin{itemize}
\item {\em Communication Processing Time}\/: the time needed to prepare
information for transmission;
\item {\em Queueing Time}\/: the time spent waiting for the start of transmission;
\item {\em Transmission Time}\/: the time needed to transmit data;
\item {\em Propagation Time}\/: the time between the end of transmission and the end
of reception.
\end{itemize}
Communication delays do not only depend on hardware characteristics, but also
on systems software properties, like communication protocols.

Communication delay is crucial for determining the appropriate
granularity of a parallel algorithm.

{\footnotesize
{\bf Example:}
As can be seen from the previous discussion of the meta-algorithm, load balancing
should be done cautiously if communication delays are not to be
neglected in comparison with processing time.

}

For a specific hardware and system software environment, communication delays
depend primarily on the following factors:
\begin{description}
\item [{\em Message Length}\/:]
Transmission time is a monotone (linearly) increasing function of the amount
of information 
to be transmitted. The time needed for the other parts of a
communication operation is
usually independent of the message length.

{\footnotesize
{\bf Example:}
The time spent in the different stages of a communication operation can vary
significantly depending on the underlying architecture. If a considerable
part of the
communication delay does not depend on the message length, several intervals
should be transferred together. The {\em blocking}\/ of messages helps to
diminish the communication overhead significantly.

}

\item [{\em Location of Sender and Receiver}\/:]
Communication delays are independent of the location of the sender and the
receiver
only in fully connected topologies, like crossbars or buses.
On other topologies, most
notably sparsely connected communication systems like arrays and rings, 
communication delays
may vary substantially depending on the location of the sender and the receiver.

Communication delays can be used for defining a measure of distance (a
{\em metric}\/) for every ordered pair of processors:
Two processors are close to each other, if the
communication delay for a message transfer is low; they are far away from
each other, if the communication delay is high. This measure of distance does
not necessarily correspond to the spatial (physical) distance between
processors.

{\footnotesize
{\bf Example:}
The load balancing strategy applied in a parallel adaptive quadrature 
algorithm should take
into account the communication distances between workers.
If two workers are very
close to each other, intervals should be exchanged even when there is only a
slight load imbalance. On the other hand, should two workers be far away from
each other, a load
imbalance has to be significant to trigger an interval transfer.

}

\item [{\em Traffic and Throughput}\/:]
Queueing time (and consequently communication delay) may increase due to
{\em interference}, i.e. the interaction of several concurrent transmissions
on a communication resource. Communcation delay is a non-linear, monotone
increasing 
function of {\em traffic} -- the amount of information transmitted per time
unit -- and tends to infinity when traffic is beyond the {\em throughput} --
the maximum amount of information that can be transmitted on a given
communication network. 

{\footnotesize
{\bf Example:}
Communication traffic due to load balancing normally results in increased
communication overhead. A load balancing strategy for a parallel adaptive
algorithm
that neglects this effect may be responsible for a loss of efficiency.

}

\item [{\em Communication Type}\/:]
There are a number of communication patterns frequently occuring in numerical
applications: point-to-point message passing, single-source and
multiple-source broadcasting and reduction, gather and scatter operations,
shifts along several axes of multidimensional arrays, and the emulation of
butterfly networks, etc. (Bertsekas, Tsitsiklis~\cite{bertsekas89}, 
Johnsson~\cite{johnsson91}). 
As special hard- and/or software support for some of these communication primitives
may exist (depending on the respective communication system), their
performance has to be enquired individually, i.e. it cannot be derived from
point-to-point communication delays.
The optimal algorithm for a {\em single node scatter}\/, for instance, has
a time complexity of $O(p)$ ($p$ is the number of processors) on a ring
topology as well as on a mesh topology (Bertsekas, Tsitsiklis~\cite{bertsekas89}).
\end{description}

\item [{\em Communication Topology}\/:]
Knowledge of the topology of a given communication network is an important
prerequisite to its effective usage.

There is a broad variety of topologies in use today:
linear arrays, rings, stars, trees, meshes, hypercubes, completely
interconnected systems, etc. (Bertsekas, Tsitsiklis~\cite{bertsekas89}, 
Almasi, Gottlieb~\cite{almasi89}). An interconnection network may even be
{\em reconfigurable}\/, i.e. its topology can be changed during the execution
of an algorithm (Lee, Smitley~\cite{lee88}). 
Additionally, heterogeneous communication systems
may occur in distributed computing environments. 
Thus, information about topology can be quite complex and its utilization can be
difficult.  However, for many applications, there is only a small number of
reasonable task allocations and corresponding communication structures. In these
cases the programmer is primarily interested in how well the {\em virtual}\/
topologies (which are inherent to algorithms) can be mapped onto the
{\em physical}\/ topology of a specific parallel system.

{\footnotesize
{\bf Example:}
All workers send information about their local integral and error estimates to
the master. This communication pattern corresponds to a virtual star
topology. However, the algorithm cannot presuppose the existence of a
physical star topology. Rather, the processes should be mapped onto physical
processors as well as possible. For instance, the processes could be mapped so
that some norm 
\begin{displaymath}
\Vert d \Vert_{q} = \left\{
      \begin{array}{ll}
            \left( \begin{array}{l}
                 \sum\limits_{i=1}^{w} |d_{i}|^{q}
                   \end{array}
            \right) ^{\frac{1}{q}}, & q \in [1,\infty ) \\
            \max\,\{|d_{1}|,\ldots ,|d_{w}|\}, & q = \infty 
      \end{array}
      \right.
\end{displaymath}
of the vector $d = (d_{1}, \ldots, d_{w})$ of the distances between the workers
and the master is minimal. $\Vert d\Vert_{q}$
can serve as a
measure for how well the virtual topology can be emulated on the physical one.

}

\item [{\em Synchronization}\/:]
Inasmuch as synchronization requires communication, all the above considerations
apply. But synchronization causes additional overhead: if a process is delayed
by {\em busy-waiting}, it becomes a load on its environment
(processor, bus, etc.); if it is {\em blocked}, awakening it causes an
additional delay. Synchronization techniques and their
corresponding overhead have to be taken
into consideration when modeling performance.

{\footnotesize
{\bf Example:}
The work to be done by the master process can be split into a part identical
to a worker job (doing integration and load balancing) and a part responsible
for algorithm
control (updating the overall integral and error estimate, initializing
workers). If multitasking facilities are available, these two jobs can be
done by two different processes running on the same processor, which results
in an easier process logic. However, the
control process will spend most of its time waiting for messages from
worker processes. Consequently, the performance of any worker process on the
control algorithm's processor will deteriorate considerably when synchronization
is done by busy-waiting.

}

\item [{\em Memory Organization}\/:]
Performance is significantly influenced by utilizing available memory
hierarchies. 
The management of complex memory structures is usually
hidden from the programmer. If, however, details of the memory management
strategies should be known, algorithms might take
advantage of such knowledge.

{\footnotesize
{\bf Example:} \label{cac}
Adaptive quadrature algorithms applied to integrands with oscillations,
peaks, and/or singularities often produce very large interval
collections with
thousands of intervals. In such cases, the whole interval collection may not
fit into a given cache memory. Consequently, frequent cache misses will occur
when inserting new intervals into the interval collection, which diminishes the
performance
significantly. Therefore, the data structure of the interval collection should
take into account currently available cache sizes. For instance,
the interval collection could be split into two parts: a sorted part (which 
comprises the
intervals with large error estimates) and an unsorted part. The size of the
sorted part chosen should be small enough to fit into the existing cache memory.
There is a penalty when intervals of the unsorted part are accessed. Such
overhead, however, rarely occurs if the unsorted part contains only intervals
with small error estimates.

}

\item [{\em Process Initialization}\/:]
Starting a new process requires initialization work, which results
in a delay of the execution.

{\footnotesize
{\bf Example:}
If an integrand is smooth,
one single evaluation of a quadrature rule is often sufficient to attain the
given accuracy requirement. The time spent on the corresponding
computational effort may be much smaller than the start up time of a worker
process. Therefore, the master process should {\em not}\/
start worker processes at the very beginning of its execution.

} 

\item [{\em Execution Mode}\/:]
Different processors may run either in a synchronous (SIMD) or in an asynchronous
(MIMD) way. 

{\footnotesize
{\bf Example:}
The time required for one evaluation of the integrand function may depend on
the respective abscissa. On a SIMD machine, different workers apply the
quadrature rule to their respective intervals synchronously, which results in
synchronous function evaluations. The overall evaluation time is
determined by the most time consuming evaluation: All processors have to wait
until the most time consuming evaluation has been finished. In cases of
substantially varying function evaluation times, such algorithms cannot be
expected to utilize a SIMD computer
efficiently.

}

\item [{\em Side Effects}\/:]
When several requests are submitted simultaneously to a resource, the
performance of this resource slows down because of {\em interference\/}.
For example, communication delay usually increases when communication traffic
gets heavier.
However, while the programmer can
be expected to be aware of message passing interference, other sources of
interference are less obvious. 

{\footnotesize
{\bf Example:}
In the parallel adaptive quadrature algorithm in Table\,1, communication is
formulated in a
message passing style. This does {\em not}\/ imply that the algorithm
is meant only
for distributed memory machines. Message passing can be implemented easily on
shared memory machines. In this case messages not only interfere with each
other, but also with memory accesses. Thus, both the effective processing speed
and the effective communication speed may
be reduced, which is a fact that might easily be overlooked.  

}

The following side-effects have to be taken into account by an
architecture adaptive algorithm:
\begin{itemize}
\item interference between communication and storage operations on
shared memory computers;
\item interference between processing and communication operations on
distributed systems without special routing processors;
\item interference between different programs running in a time sharing 
environment.
\end{itemize}

\item [{\em Algorithm Adaption Overhead}\/:]
Acquiring information and making the corresponding decisions cause an additional
overhead in architecture adaptive algorithms.
The decision overhead should be quantifyable
in order to find a reasonable compromise between this {\em decision overhead}\/
and the potential gain in efficiency of a more carefully adapted algorithm.
\end{description}

\section{Abstract Machine Model}
Information about the underlying hardware and system software is
indispensable for architecture adaptive algorithms. Preferably, this information
should be given within the framework of a {\em parameterized abstract machine
model}\/ (Augustyn, Krommer, Ueberhuber~\cite{augustyn91}). Describing systems
without an abstract machine model would limit the
applicability of architecture adaptive algorithms to already existing
machines. 
The parameters of the abstract machine model have to represent
different performance relevant aspects of parallel computing systems
(the number of processors, cache sizes, etc.).

The tremendous diversity of today's computing environments makes
the development of an abstract machine model a most challenging task.
In the design process of machine models decisions have to be made concerning
their accuracy and complexity. Accurate models enable highly efficient
architecture adaptive algorithms. Due to their complexity, however, they are
unwieldy for the algorithm designer. An outline
of a possible machine model (based on the
more general exposition of Augustyn, Krommer and
Ueberhuber~\cite{augustyn91}) is given in this section.

{\footnotesize
{\bf Example:}
A specific computing environment of the Technical University Vienna will serve
illustrative purposes. A local area network interconnects
\begin{itemize}
\item a shared memory computer, a Sequent Balance 21000 with $28$ processors;
\item a distributed memory computer, a 16-node iPSC/860 hypercube; and
\item a homogeneous workstation cluster consisting of nine RS/6000-320H
computers connected by a token ring network.
\end{itemize}

}

\subsection{Structure of Computing Environments} \label{agv}
The model to be developed should be used for computationally intensive
problems. I/O bound tasks are not considered in this paper.
The time needed for accessing files is assumed to be negligible.

The performance of computationally intensive tasks can degradate
significantly due to {\em memory hierarchy delays}\/. Properties of the memory
hierarchy's various levels (cache memory, main memory, swap
space on a hard disc, etc.) should be taken into account in a useful machine
model. 
Instruction caches can be neglected in an abstract machine model.
The knowledge of instruction cache sizes is practically useless to the 
programmer of scientific software.

\begin{figure}
\begin{center}
\setlength{\unitlength}{0.0125in}%
\begin{picture}(156,115)(144,641)
\thicklines
\put(206,728){\line(-1,-6){  7.162}}
\put(199,685){\line( 1,-6){  7.324}}
\multiput(214,656)(8.19048,0.00000){11}{\line( 1, 0){  4.095}}
\multiput(214,699)(8.19048,0.00000){11}{\line( 1, 0){  4.095}}
\multiput(214,714)(8.19048,0.00000){11}{\line( 1, 0){  4.095}}
\put(214,641){\framebox(86,115){}}
\put(214,728){\line( 1, 0){ 86}}
\put(256,717){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\ninrm Level 1}}}
\put(256,702){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\ninrm Level 2}}}
\put(256,688){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\ninrm .}}}
\put(256,677){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\ninrm .}}}
\put(256,667){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\ninrm .}}}
\put(256,645){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\ninrm Level N}}}
\put(167,688){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\ninbf Memory}}}
\put(167,675){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\ninbf Hierarchy}}}
\put(256,738){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\ninbf Processor}}}
\end{picture}\\
\vspace{15 pt}
{\footnotesize {\bf Figure 1:} Processor-memory node}
\end{center} 
\end{figure}

{\em Processor-memory nodes} are the fundamental building blocks of a
general model for computing environments. A
processor-memory node contains one processor and/or a memory
hierarchy\footnote{The presence of both the processor and the memory
hierarchy is optional, i.e. a
processor-memory node may consist of only a processor or of only a memory
hierarchy.} (cf. Figure~1). If both the processor and the memory hierarchy
are present,
the processor is supposed to have {\em direct}\/ access to the memory hierarchy.

\begin{figure}
\begin{center}
\setlength{\unitlength}{0.0125in}%
\begin{picture}(317,358)(83,438)
\thicklines
\put( 83,651){\framebox(83,84){}}
\put( 83,693){\line( 1, 0){ 83}}
\put(125,710){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Processor}}}
\put(125,668){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Cache}}}
\put(125,747){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Sequent Balance}}}
\put(242,747){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm i860}}}
\put(358,747){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm RS 6000/320H}}}
\put(317,693){\line( 1, 0){ 83}}
\put(317,618){\framebox(83,117){}}
\put(200,693){\line( 1, 0){ 83}}
\put(200,643){\framebox(83,92){}}
\multiput(200,668)(6.14815,0.00000){14}{\line( 1, 0){  3.074}}
\multiput(317,668)(6.14815,0.00000){14}{\line( 1, 0){  3.074}}
\multiput(317,643)(6.14815,0.00000){14}{\line( 1, 0){  3.074}}
\put(199,438){\framebox(83,84){}}
\multiput(199,480)(7.90476,0.00000){11}{\line( 1, 0){  3.952}}
\put(358,710){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Processor}}}
\put(358,676){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Cache}}}
\put(358,651){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Main Memory}}}
\put(358,626){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Swap Space}}}
\put(242,710){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Processor}}}
\put(242,676){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Cache}}}
\put(242,651){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Main Memory}}}
\put(241,497){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Main Memory}}}
\put(241,455){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Swap Space}}}
\put(241,534){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Sequent Balance}}}
\put(242,787){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenbf Processor-memory nodes}}}
\put(241,570){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenbf Memory node}}}
\end{picture}\\
\vspace{15 pt}  
{\footnotesize {\bf Figure 2:} Examples of processor-memory nodes}
\end{center} 
\end{figure}

{\footnotesize
{\bf Example:}
Each processor node of the Sequent Balance (NS\,32032 processor) has exclusive
access to an
8\,KByte data cache. The Sequent Balance includes a memory node (without
processor)
consisting of a 24\,MByte main memory, and a swap space on a disc.
On the iPSC/860 hypercube each processor-memory node (i860 processor) has an
8\,KByte data
cache and an 8\,MByte main memory. Each RS/6000-320H workstation
({\sc Power} processor) has a
32\,KByte data cache, a 16\,MByte main memory, and a 128\,MByte swap space on a private 
disc (cf. Figure~2).

}

Parallel or distributed computing environments are built 
by connecting processor-memory nodes via an {\em interconnection
network\/} (cf. Figure~3). 

\begin{figure}
\begin{center}
\setlength{\unitlength}{0.0125in}%
\begin{picture}(318,151)(82,640)
\thicklines
\put( 82,690){\framebox(84,84){}}
\put( 82,732){\line( 1, 0){ 84}}
\put(124,749){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Processor}}}
\put(124,707){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Memory}}}
\put(216,690){\framebox(84,84){}}
\put(216,732){\line( 1, 0){ 84}}
\put(258,749){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Processor}}}
\put(258,707){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Memory}}}
\put(316,690){\framebox(84,84){}}
\put(316,732){\line( 1, 0){ 84}}
\put(358,749){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Processor}}}
\put(358,707){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Memory}}}
\put(124,690){\line( 0,-1){ 16}}
\put(258,690){\line( 0,-1){ 16}}
\put(358,690){\line( 0,-1){ 16}}
\put( 82,640){\framebox(318,34){}}
\put(124,782){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenbf Node 1}}}
\put(258,782){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenbf Node p-1}}}
\put(358,782){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenbf Node p}}}
\put(241,653){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Communication network}}}
\put(191,732){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenbf .  .  .}}}
\end{picture}\\
\vspace{15 pt}  
{\footnotesize {\bf Figure 3:} General structure of a parallel machine}
\end{center} 
\end{figure}

\begin{figure}
\begin{center}
\setlength{\unitlength}{0.0125in}%
\begin{picture}(320,134)(80,660)
\thicklines
\put( 80,710){\framebox(84,84){}}
\put( 80,752){\line( 1, 0){ 84}}
\put(122,769){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Processor}}}
\put(122,727){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Cache}}}
\put(316,710){\framebox(84,84){}}
\multiput(316,752)(8.00000,0.00000){11}{\line( 1, 0){  4.000}}
\put(358,769){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Main Memory}}}
\put(358,727){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Swap Space}}}
\put(215,710){\framebox(84,84){}}
\put(215,752){\line( 1, 0){ 84}}
\put(257,769){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Processor}}}
\put(257,727){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Cache}}}
\put( 80,660){\framebox(320,33){}}
\put(240,673){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Bus}}}
\put(122,710){\line( 0,-1){ 17}}
\put(257,710){\line( 0,-1){ 17}}
\put(358,710){\line( 0,-1){ 17}}
\put(189,752){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenbf .  .  .}}}
\end{picture}\\
\vspace{15 pt}  
{\footnotesize {\bf Figure 4:} Shared memory machine (Sequent Balance)}
\end{center} 
\end{figure}
\begin{figure}
\begin{center}
\setlength{\unitlength}{0.0125in}%
\begin{picture}(315,150)(85,640)
\thicklines
\put( 85,749){\line( 1, 0){ 83}}
\put( 85,698){\framebox(83,92){}}
\multiput( 85,723)(6.14815,0.00000){14}{\line( 1, 0){  3.074}}
\put(126,765){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Processor}}}
\put(126,732){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Cache}}}
\put(126,707){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Main Memory}}}
\put(317,749){\line( 1, 0){ 83}}
\put(317,698){\framebox(83,92){}}
\multiput(317,723)(6.14815,0.00000){14}{\line( 1, 0){  3.074}}
\put(359,765){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Processor}}}
\put(359,732){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Cache}}}
\put(359,707){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Main Memory}}}
\put(126,674){\line( 0, 1){ 24}}
\put(359,674){\line( 0, 1){ 24}}
\put( 85,640){\framebox(315,34){}}
\put(242,652){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Hypercube Network}}}
\put(242,749){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenbf .     .     .}}}
\end{picture}\\
\vspace{15 pt}  
{\footnotesize {\bf Figure 5:} Distributed memory machine (iPSC/860)}
\end{center} 
\end{figure}
\begin{figure}
\begin{center}
\setlength{\unitlength}{0.0125in}%
\begin{picture}(315,173)(85,602)
\thicklines
\put( 85,733){\line( 1, 0){ 82}}
\multiput( 85,709)(6.07407,0.00000){14}{\line( 1, 0){  3.037}}
\multiput( 85,684)(6.07407,0.00000){14}{\line( 1, 0){  3.037}}
\put( 85,659){\framebox(82,116){}}
\put(127,750){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Processor}}}
\put(127,718){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Cache}}}
\put(127,693){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Main Memory}}}
\put(127,667){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Swap Space}}}
\put(318,733){\line( 1, 0){ 82}}
\multiput(318,709)(6.07407,0.00000){14}{\line( 1, 0){  3.037}}
\multiput(318,684)(6.07407,0.00000){14}{\line( 1, 0){  3.037}}
\put(318,659){\framebox(82,116){}}
\put(358,750){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Processor}}}
\put(358,718){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Cache}}}
\put(358,693){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Main Memory}}}
\put(358,667){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Swap Space}}}
\put(127,634){\line( 0, 1){ 25}}
\put(358,634){\line( 0, 1){ 25}}
\put( 85,602){\framebox(315,32){}}
\put(243,614){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Token Ring Network}}}
\put(240,730){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenbf .     .     .}}}
\end{picture}\\
\vspace{15 pt}  
{\footnotesize {\bf Figure 6:} Workstation cluster (RS/6000-320H)}
\end{center} 
\end{figure}

{\footnotesize
{\bf Example:}
The Sequent Balance is set up by interconnecting $28$ 
processor-memory nodes and one (shared) memory node by 
a 26.6\,MByte/s high-speed bus (cf. Figure~4).
The processor-memory nodes of the iPSC/860 are interconnected by a
communication system that forms a
four-dimensional hypercube (cf. Figure~5). The overall bandwidth of the
hypercube is 2.8\,MByte/s, the node-to-node latency is 60\,$\mu$s.
The RS/6000-320H workstations are
interconnected by a token ring network (cf. Figure~6) that provides a throuput
of 16\,MBit/s. The latency is about 10\,ms.

}

\begin{itemize}
\item If a memory node is present, it is assumed that {\em each\/} processor has
access to its memory hierarchy (via the interconnection network), i.e.\ such
a node is assumed to be a {\em shared memory\/}. Internode
communication takes place via the shared memory.
\item If {\em all\/} nodes include a processor, it is assumed that
processors communicate by passing messages over the interconnection network.
It is assumed that no {\em explicit\/} routing has to be carried
out to establish the communication between two nodes that are not directly
linked to
each other, i.e.\ a system software layer provides the user with a {\em
virtually fully
connected}\/ interconnection network.
\end{itemize}

{\footnotesize
{\bf Example:}
The existence of a memory node in the diagram of the Sequent Balance indicates
that this is a
shared memory computer. The hypercube topology of the iPSC/860 is completely
hidden by the operating system's message passing routines. Any two
processor-memory nodes can directly communicate with each other. This is also
true for the ring topology
of the RS/6000-320H cluster when using programming tools like {\sc PVM}
(Sunderam~\cite{sunderam90}).

}
 
Several parallel or distributed computing environments in addition to some
processor-memory nodes can be combined by a higher level interconnection
network to form an even more complex distributed computing environment. 

\begin{figure}
\begin{center}
\setlength{\unitlength}{0.0125in}%
\begin{picture}(316,100)(84,700)
\put(284,764){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Cluster}}}
\put(284,779){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm RS 6000}}}
\thicklines
\put( 84,750){\framebox(67,50){}}
\put(117,750){\line( 0,-1){ 17}}
\put(167,750){\framebox(67,50){}}
\put(200,733){\line( 0, 1){ 17}}
\put(250,750){\framebox(67,50){}}
\put(284,733){\line( 0, 1){ 17}}
\put(333,750){\framebox(67,50){}}
\put(367,733){\line( 0, 1){ 17}}
\put( 84,700){\framebox(316,33){}}
\put(117,771){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm iPSC/860}}}
\put(200,779){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Sequent}}}
\put(200,764){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Balance}}}
\put(367,779){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm DECstation}}}
\put(367,764){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm 3100}}}
\put(242,712){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Ethernet}}}
\end{picture}\\
\vspace{15 pt}  
{\footnotesize {\bf Figure 7:} Distributed computing environment}
\end{center} 
\end{figure}

{\footnotesize
{\bf Example:}
The Sequent Balance, the iPSC/860 hypercube host, the RS/6000-320H
workstation cluster, and the author's workstation are connected by an
Ethernet network (cf. Figure~7) that provides a bandwidth of 10\,MBit/s.

}

An important question is whether or not this immanently hierarchical structure
of computing environments should be flattened. Instead of using different levels
of interconnection networks, it is possible -- in a virtual or
logical sense -- to model a complex distributed computing environment by using a
simple structure like that of Figure~3.

{\footnotesize
{\bf Example:}
By using programming environments like {\sc PVM}, each Sequent Balance node can
communicate directly (without explicit routing) with each RS/6000-320H node
via {\sc PVM} message passing routines.

}

Combining different communication networks (and network layers) into a single
network simplifies the model structure, but vastly increases the heterogeneity
of the network. Consequently, algorithm control (for instance, the choice
of an appropriate algorithmic granularity) becomes a formidable task.

{\footnotesize
{\bf Example:}
Communication delays between any two Sequent Balance nodes do not depend on
the location of the sender and the receiver.
This is also approximately true for the communication delays between any two
RS/6000-320H workstations in the cluster. (This is true when using {\sc PVM}.)
In
a virtual network
including both the Sequent Balance and the workstation cluster, communication 
delays between two nodes differ by several orders of magnitude.
Besides, it is not clear how the Sequent Balance's shared memory resources
(its memory node) can be included in the combined machine model.

The iPSC/860 can be controlled only via a host computer. 
It is not possible to allocate i860 processors from outside. Thus, a direct
global algorithm control is not feasible.   

}

In many cases it is better to adopt the hierarchical structure of a
computing environment in the abstract machine model and to achieve algorithmic
control in a hierarchical manner.

{\footnotesize
{\bf Example:}
If a parallel algorithm is supposed to use the Sequent Balance,
the workstation cluster, and the hypercube simultaneously, it is not reasonable
to have just
one centralized control process. If, for instance, control is exercised from 
a workstation node, communication between the controlling process and the
Sequent Balance processes will be slow. All Sequent Balance worker
processes should be controlled by a specific control process running on a
Sequent Balance node. 
In the same way the workstation cluster and the hypercube
should be managed by their own local control processes. These local control
processes in turn are subordinated to a global control process (that may be 
residing in any of the three subenvironments). 

}

The structure of a distributed environment may be composed of several
subhierarchies and hierarchical levels.

\begin{figure}
\begin{center}
\setlength{\unitlength}{0.0125in}%
\begin{picture}(312,115)(88,680)
\put(203,768){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm University}}}
\put(203,753){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Vienna}}}
\put(121,774){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Technical}}}
\put(121,760){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm University}}}
\put(121,745){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Vienna}}}
\thicklines
\put(170,729){\framebox(66,66){}}
\put(203,729){\line( 0,-1){ 16}}
\put(252,729){\framebox(66,66){}}
\put(285,729){\line( 0,-1){ 16}}
\put( 88,729){\framebox(66,66){}}
\put(121,729){\line( 0,-1){ 16}}
\put( 88,680){\framebox(312,33){}}
\put(244,692){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Internet}}}
\put(285,774){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Kepler}}}
\put(285,760){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm University}}}
\put(285,745){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Linz}}}
\put(359,762){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenbf .     .     .}}}
\end{picture}\\
\vspace{15 pt}  
{\footnotesize {\bf Figure 8:} Distributed computing environment}
\end{center} 
\end{figure}

{\footnotesize
{\bf Example:}
The computing environment of the Technical University Vienna is connected
through Internet to other computing sites (cf. Figure~8). These computing sites
are all structured in a hierarchical manner. Computing
resources available in other sites can be combined into a distributed computing
environment. Such an environment makes only sense for applications with an
extremely high demand for computing power and an algorithmic granularity that
is sufficiently coarse.

}
 
\subsection{Characterization of Available Resources}
It is necessary to know which computing environments and which components are
indeed available, before enquiring the properties of
the various components of distributed computing environments. 

A distributed computing environment can consist of several 
subenvironments. (A processor may have access to several subenvironments.)
If the computational demands of an algorithm are high, the computation might
be spread over several subenvironments. 

{\footnotesize
{\bf Example:}
A Sequent Balance node is not only part of one particular 
Sequent Balance shared memory computer, but has also access (via the Ethernet
and Internet networks) to processor-memory nodes of other machines.
A parallel quadrature algorithm starting its execution on a Sequent Balance node
might first exploit the resources of the Sequent Balance. If the integration
turns out to be computationally intensive, the RS/6000-320H cluster and the
iPSC/860 hypercube might also be exploited.
 
}

An enquiry function that returns the accessible (sub)environments (networks) is
required.

{\footnotesize
{\bf Example:}
The enquiry procedure {\tt environment} yields the number {\sl env\_nr} of
networks accessible to the calling process. A list of these
environments is contained in {\sl env\_list}. 
\begin{tabbing}
aaaa\=\kill
\> {\tt environment(} {\sl env\_nr} {\tt ,} {\sl env\_list} {\tt )}
\end{tabbing}
The array elements in {\sl env\_list} are data objects identifying the
respective environments.

}

As soon as all accessible networks are known, the next step is to enquire their
components (processor-memory nodes, distributed computing environments, etc.).

{\footnotesize
{\bf Example:} The enquiry procedure {\tt components} yields the number
{\sl comp\_nr} of
components connected to the environment {\sl env\_id}. A list of these
components is returned in {\sl comp\_list}.
\begin{tabbing}
aaaa\=\kill
\> {\tt components(} {\sl env\_id} {\tt ,} {\sl comp\_nr} {\tt ,}
{\sl comp\_list} {\tt )}
\end{tabbing}
To keep the environment description
as simple as possible, only different (not replicated) components are 
listed in {\sl comp\_list}. The replication factor of a component is included
in the component's description.

The Sequent Balance, for instance, has only two different components: a
processor-memory
node and a memory node (main memory and hard disc).
There are $28$ replicates of the
processor-memory node, but there is only one memory node.

Components are described by data objects containg the following information:
\begin{itemize}
\item replication factor,
\item type (processor-memory node, memory node, or distributed environment),
\item a component identifier ({\sl node\_id} or {\sl env\_id}).
\end{itemize}

}

\subsubsection{Fault-Tolerance}
Although the {\sc aaa} approach is primarily concerned with the performance
aspect of parallel and distributed computing, the {\em reliability\/}
({\em fault-tolerance\/}) issue is also important. This is particularly the case
for heterogeneous computing environments where nodes may become unavailable
to the executing program. For example, this can happen when one of the
participating workstations is physically switched off.

{\footnotesize
{\bf Example:} The procedure {\tt on\_failure} enables a failure handler
{\sl fail\_handler}.
\begin{tabbing}
aaaa\= {\tt near\_proc(} \=\kill
\> {\tt on\_failure(} {\sl fail\_handler} {\tt ,} {\sl num\_proc} {\tt ,}
{\sl proc\_vector} {\tt )}
\end{tabbing}
If one of the {\sl num\_proc} processor-memory nodes contained in
{\sl proc\_vector} fails, i.e.\ is no longer available to the process that
has called {\tt on\_failure},
the following happens:
\begin{itemize}
\item The process that called {\tt on\_failure} is interrupted.
\item The current process context is saved.
\item {\sl fail\_handler} is invoked. 
\item The process resumes execution in
the pre-failure context if {\sl fail\_handler} returns normally. 
\item Newly occuring failures are blocked during the execution of a failure
handler. They can only be served after the currently executing failure handler
has returned.
\end{itemize}
If no failure handler has been set up for a specific processor-memory node, failures of
this node are ignored. Different failure handlers can be assigned to failures
of different nodes. If a node failure is covered by several handlers,
one handler is chosen randomly and invoked.

A failure handler routine has to be declared as follows:
\begin{tabbing}
aaaa\= {\tt near\_proc(} \=\kill
\> {\sl fail\_handler} {\tt (} {\sl node\_id} {\tt )}.
\end{tabbing}
The failed processor {\sl node\_id} is passed to {\sl fail\_handler}.

}

\subsection{Characterization of Computing Environments} \label{cce}
The general model of distributed computing environments is made up of
{\em processors}\/, {\em memory hierarchies}\/, and
{\em interconnection networks\/} (cf. Figure~3).
In order to provide a {\em parameterized}\/ abstract machine model,
all components have to be parameterized.

\subsubsection{Parameterization of Processors}
{\sl Processor Speed}

The task of a processor is the manipulation of data. Processor 
performance should be characterized by the speed of the respective operations.
Since the instruction sets of modern processors vary significantly, only
operations provided in {\em portable}\/ high-level languages (like
Fortran or C) should be taken into account. The set of operations
will further be limited to {\em arithmetic} operations, as the abstract
machine model is to be used in the context of computationally intensive tasks
(scientific software, etc.).
Nevertheless, the following considerations can be easily transferred to other
kinds of operations (integer or character operations, etc.).

First of all, the arithmetic operators {\tt +}, {\tt -}, 
{\tt *}, {\tt /}, {\tt **} have to be considered. In all scientific 
programming languages, a broad range of mathematical {\em intrinsic functions}\/
is available. The (hardware or software) implementation of these functions may
vary substantially on different computers. 
As a result, their performance {\em cannot\/} be accurately derived
from the speed of the arithmetic operations. If the evaluation of intrinsic
functions takes a significant part of the overall execution time, accurate
performance data on the intrinsic functions should be available.

A certain degree of low-level parallelism is available in many of today's
microprocessors. For instance, arithmetic operation units can be
{\em pipelined}\/,
and/or {\em independent} (concurrently operating) arithmetic operation units
can be available. Unfortunately, the execution time of a {\em sequence}\/ of
operations can {\em not}\/ be inferred from the execution times of 
single operations. 

Hockney and Jesshope~\cite{hockney88} have suggested a model for the execution
time of vector instructions that depends on the length $n$ of the vectors
involved:
\begin{equation}\label{hoc}
t = \frac{n + n_{1/2}}{r_{\infty }}.
\end{equation}
$r_{\infty }$ denotes the {\em maximum (asymptotic)
performance}\/, i.e.\ the Mflop/s rate for infinite vectors.
$n_{1/2}$ -- the {\em half-performance length} -- is the vector length
for which half of the maximum performance is achieved.
This linear model is not just a first order fit to experimental data, but can
be derived from hardware properties (Hennessy, Patterson~\cite{hennessy90}).
The model~(\ref{hoc}), though simple, is sufficiently accurate for
many applications. It can be used, for instance, to describe the performance
of {\em (pipelined) scalar processors}\/.

Due to the existence of concurrently operating, pipelined arithmetic
units in modern processors, execution times for compound vector operations
cannot be inferred from single vector operations without detailed knowledge
of the processor architecture. Therefore, $(r_{\infty },n_{1/2})$
models should also be provided for commonly used compound vector operations,
like the BLAS-1 subroutines and intrinsic vector functions.

In most applications only a small subset of the overall processor performance
characteristics is relevant to a performance prediction.
Linear algebra routines, for instance, predominantly use {\em rational}\/
operations.
Simple generic enquiry functions might provide the framework for
acquiring all necessary information. 

{\footnotesize
{\bf Example:}
Two generic enquiry functions providing processor performance parameters
might be defined as follows:
\begin{tabbing}
aaaa\= $n_{1/2}$ = {\tt n\_half(} \=\kill
\> $n_{1/2}$ = {\tt n\_half(} {\sl node\_id} {\tt ,}
   {\sl operation\_id} {\tt )}\\[1mm]
\> $r_{\infty }$ = {\tt r\_infty(} {\sl node\_id} {\tt ,}
   {\sl operation\_id} {\tt )}
\end{tabbing}
The variable {\sl node\_id} specifies the processor and the character
string {\sl operation\_id} the (possibly compound) operation
to be evaluated. The string {\tt '+'}, for instance, denotes a vector addition,
{\tt 'SIN'} the intrinisic sine function, and {\tt 'SAXPY'} the respective
BLAS-1 subroutine.

}

Different hardware may be used for scalar and vector operations. Furthermore,
vectorizing loops incurs some overhead. For short vector length,
scalar mode is faster than vector mode. The parameter
$n_{v}$ (Hennessy, Patterson~\cite{hennessy90}) gives the vector length
needed to make vector mode faster than scalar mode. For scalar processors
without additional vector units, $n_{v} = 1$; while for scalar processors
with additional vector units or vector processors, $n_{v} > 1$ holds.
$n_{v}$ can also be used to derive scalar performance characteristics. 

{\footnotesize
{\bf Example:} The enquiry function {\tt n\_v} returns the parameter $n_{v}$.
\begin{tabbing} 
aaaa\= $n_{v}$ = {\tt n\_v(} \=\kill
\> $n_{v}$ = {\tt n\_v(} {\sl node\_id} {\tt ,}
   {\sl operation\_id} {\tt )}
\end{tabbing}
For example, given the values $r_{\infty }$, $n_{1/2}$, $n_{v}$ for
multiplication, scalar performance for multiplications is obtained by
\[ r_{\infty }^{scalar} = \frac{n_{v} \cdot r_{\infty}}{n_{v} + n_{1/2}}. \]

}

Performance parameters should characterize the processor performance
for situations where data is stored in the highest level of the memory
hierarchy. 
Performance degradation due to delays caused by accessing data in
lower memory levels can be modeled by using the memory hierarchy
parameters from the following section.
 
~\\
{\sl Available Processor Time}

In a time sharing environment, processors are shared between different
processes. The number of CPU cycles available to one of those processes
can be a highly dynamic entity. An enquiry function should
be provided to yield the percentage of CPU time currently available to the
process making the enquiry.
An additional enquiry function could
indicate cases where a processor is private to an executing process.

{\footnotesize
{\bf Example:} Two enquiry functions are as follows:
\begin{tabbing}
aaaa\= \kill
\> {\sl current\_percentage} = {\tt free\_cpu(} {\sl node\_id} {\tt )}\\[1mm]
\> {\sl current\_mode} = {\tt cpu\_sharing(} {\sl node\_id} {\tt )}
\end{tabbing}
The function {\tt free\_cpu} returns the {\em percentage}\/
of cycles of the processor {\sl node\_id}
currently available. The enquiry function {\tt cpu\_sharing} indicates the mode
in which the processor {\sl node\_id} runs (time sharing, etc.).

}

~\\
{\sl Initialization Delay}

The time required to initialize a process on processor
depends on the processor and the workload of the whole system.

{\footnotesize
{\bf Example:} The enquiry function {\tt init\_delay} returns the time
{\sl current\_init\_delay} {\em currently}\/ required to start a new process
on the processor {\sl node\_id}.
\begin{tabbing}
aaaa\= \kill
\> {\sl current\_init\_delay} = {\tt init\_delay(} {\sl node\_id} {\tt )}
\end{tabbing}

}

{\sl Synchronization Mode}

On SIMD machines, processor execution is controlled and synchronized by the
instruction stream issued by a control unit. Thus, processors should be able
to enquire whether or not they can act as control units of SIMD machines.

{\footnotesize
{\bf Example:} The enquiry procedure {\tt sync\_control} returns the vector
{\sl proc\_vector} of length {\sl num\_proc} that contains the numbers of those
processors that
can be controlled in a synchronized manner by the processor that calls
{\tt sync\_control}. 
\begin{tabbing}
aaaa\= {\tt near\_proc(} \=\kill
\> {\tt call sync\_control(} {\sl num\_proc} {\tt ,} {\sl proc\_vector} {\tt )}
\end{tabbing}
If the calling processor is not a control unit of a SIMD machine, the length
{\sl num\_proc} of the return vector is 0.

}

\subsubsection{Parameterization of Memory Hierarchies}
A memory hierarchy is usually transparent to the
programmer. The question arises, what general assumptions can be made
about the mapping of data onto the memory hierarchy.

Memory hierarchies are organized into several levels -- each
smaller and faster than the level below.
The levels of the hierarchy usually subset one another; all the data in one level
is also
found in the level below. When accessed, data is stored in the highest level.
Data is kept in a level of the memory hierarchy
as long as the level's capacity is not exceeded\footnote{Not fully associative
caches are an exception to this rule.}. Other memory management strategies,
concerning, for instance, block replacement and memory writes, vary
significantly (Hennessy, Patterson~\cite{hennessy90}).

Numerous parameters concerning memory hierarchy may influence performance.
Important properties of caches are characterized by physical parameters --
like
cache size, line size, set associativity (So, Zecca~\cite{so88}) -- as well as
cache management strategies -- like the write-through vs. write-back
(Vaughan-Nichols~\cite{vaughan91}) or write-allocate vs. no-write-allocate
(Hennessy, Patterson~\cite{hennessy90}) options. 

Parameters made available to the programmer must fulfill
the following conditions:
\begin{itemize}
\item The parameter must enable the programmer to write more efficient
programs.
\item The parameter must enable the programmer to estimate the
performance of a processor-memory node more realistically (by including memory
delays).
\end{itemize}

According to these principles, the levels of a memory hierarchy could
be characterized by the following parameters:
\begin{description}
\item [{\em Size}\/:]
An algorithm can often choose data reference locality according to known
storage capacities (see the example on page~\pageref{cac}), which results
in lower miss rates for the faster memory levels.

The memory requirements
of a program may sometimes exceed the capacity of the memory hierarchy.
In such a case the program cannot be run in a specific environment or it 
has to be reorganized.

{\footnotesize
{\bf Example:} The enquiry function {\tt size} returns the size of the memory
level {\sl level} in the memory hierarchy {\sl node\_id} (in unit of bytes). 
\begin{tabbing}
aaaa\= {\tt size(} \=\kill
\> {\sl memory\_size} = {\tt size(} {\sl node\_id} {\tt ,} {\sl level}
{\tt )}
\end{tabbing}
The variable {\sl level} is of type {\tt integer}. ${\sl level} = 1$ designates
the fastest level, ${\sl level} = 2$ designates the second fastest level and
so forth.

}

\item [{\em Number of Banks, Interleaving Factor}\/:]
To increase bandwidth, memory is often divided into a relatively small number of
independent banks, each of which may service simultaneously a different
memory request. Performance degradation occurs in the case of {\em memory-bank
conflicts\/}, that are the result of requests to a memory bank that is still
busy servicing
a previous request (Calahan, Bailey~\cite{calahan88}).
Memory banks can be interleaved at different levels (byte, word, double-word,
etc.). By taking the number of banks and the interleaving level into account,
an algorithm may restructure its array reference patterns to avoid,
as far as possible, memory-bank conflicts.

{\footnotesize
{\bf Example:} The enquiry function {\tt units} returns the number of banks
in the memory level {\sl level} in the memory hierarchy {\sl node\_id}.
The corresponding interleaving level is returned by the enquiry function
{\tt interleave\_level}.
  
\begin{tabbing}
aaaa\= {\tt size(} \=\kill
\> {\sl bank\_number} = {\tt units(} {\sl node\_id} {\tt ,} {\sl level}
{\tt )}\\[1mm]
\> {\sl interleave\_factor} = {\tt interleave\_level(} {\sl node\_id} {\tt ,}
{\sl level} {\tt )}
\end{tabbing}
The interleaving level is given in units of bytes. For instance,
${\sl interleave\_factor} = 4$ means interleaving takes place at the word level.

The following example shows how interleaving information can be used to analyze
the memory access patterns of a program.  
Let us asssume that
\begin{itemize}
\item real numbers are stored as words, and
\item the main memory is interleaved at the word level and is split into
$b$ banks.
\end{itemize}
Successive elements of any column of a real $n \times n$ matrix $A$ can be
accessed at maximum speed. In contrast, accessing successive elements of a
row
might cause memory conflicts, if $n$ is {\em not}\/ relative prime to
$b$. Therefore, if the matrix $A$ is frequently accessed by rows, it should
be stored as an $m \times m$ matrix, $m \geq n$, so that $m$ and $b$ are
relative prime.
 
}

\item [{\em Access and Transfer Time}\/:]
Performance degradation due to {\em memory access delays\/} can be modeled by
assuming
that the access to a vector of length $n$ obeys the timing relation
\begin{equation}\label{coh}
t = \frac{n + n_{1/2}^{m}}{r_{\infty }^{m}}
\end{equation}
(Hockney, Jesshope~\cite{hockney88}). By taking into account
\begin{enumerate}
\item the processor parameters $r_{\infty }$, $n_{1/2}$;
\item the memory parameters $r_{\infty }^{m}$, $n_{1/2}^{m}$; as well as
\item the algorithm parameter $f$ (the {\em computational intensity}\/,
i.e.\ the number of floating-point operations per memory reference),
\end{enumerate}
the processor performance including memory delays can be
estimated (Hockney, Jesshope~\cite{hockney88}).
The parameters $r_{\infty }^{m}$, $n_{1/2}^{m}$ of the
linear model (\ref{coh})
reflect the {\em access time\/} as well as the {\em transfer rate}\/ of memory
accesses.
They vary tremendously
for different levels of the memory hierarchy. Consequently, 
the parameters $r_{\infty }^{m}$, $n_{1/2}^{m}$ have to be given
individually for every level of a memory hierarchy.

{\footnotesize
{\bf Example:} The enquiry functions {\tt n\_half\_m} and {\tt r\_infty\_m}
return the parameters $n_{1/2}^{m}$ and $r_{\infty }^{m}$ for the memory
level {\sl level} in the memory hierarchy {\sl node\_id}.
\begin{tabbing}
aaaa\= $n_{1/2}$ = {\tt n\_half(} \=\kill
\> $n_{1/2}^{m}$ = {\tt n\_half\_m(} {\sl node\_id} {\tt ,} {\sl level}
{\tt )}\\[1mm]
\> $r_{\infty }^{m}$ = {\tt r\_infty\_m(} {\sl node\_id} {\tt ,} {\sl level}
{\tt )}
\end{tabbing}

}

A memory level may consist of independent banks; memory hierarchies can 
either be directly linked to a processor or connected to an interconnection
network. Thus, the interpretation of the parameters 
$r_{\infty }^{m}$, $n_{1/2}^{m}$ has to be done carefully:
\begin{itemize}
\item For an interleaved memory, the parameters $r_{\infty }^{m}$,
$n_{1/2}^{m}$
are given for a whole memory level (and {\em not}\/ for a single
memory bank). When accessing contiguous memory locations, no memory conflicts
occur. Thus, the parameters reflect {\em conflict free}\/ memory performance.
Degradation due to memory-bank conflicts cannot be modeled using these
parameters. It can be avoided by using interleaving information. 
\item For memory hierarchies directly linked to a processor, the parameters
$r_{\infty }^{m}$,  $n_{1/2}^{m}$
describe how fast data can be transferred to the highest (fastest) memory level.
The parameters not only characterize memory performance, but also
transmission time and memory management overhead.
\item For memory hierarchies linked to processors via an interconnection
network (shared memories), memory access delays may occur due to the 
interference of 
several processors. In the case of interleaved memory, performance
models for memory access delays require the knowledge of the
{\em bank busy time\/}, i.e. the minimum time between two requests to a memory
bank. The bank busy time can also be used to estimate performance degradation
in cases where a processor does not access the memory contiguously.

{\footnotesize
{\bf Example:} Let us suppose that a memory bank is busy for four clock
periods. A processor accessing every fourth bank on successive clock cycles
does not suffer any performance degradation. In contrast, accessing every
eighth bank incurs a delay of two cycles. Thus, only half the maximum
access rate can be attained.

The enquiry function {\tt unit\_busy} returns the bank busy time
for the memory level {\sl level} in the memory hierarchy {\sl node\_id}.
\begin{tabbing}
aaaa\= $n_{1/2}$ = {\tt n\_half(} \=\kill
\> {\sl busy\_delay} = {\tt unit\_busy(} {\sl node\_id} {\tt ,} {\sl level}
{\tt )}
\end{tabbing}
If a level of the memory hierarchy is {\em not\/} interleaved, {\tt unit\_busy}
returns the busy time for a single bank.

}

\end{itemize}

\item [{\em Cache Associativity -- Sets}\/:]
For {\em not\/} fully associative caches, the {\em effective\/} cash size can be
significantly
reduced if memory references are {\em not evenly\/} spread over the existing
sets (Hennessy, Patterson~\cite{hennessy90}). The set associativity 
problem resembles the memory bank problem in the following ways:
\begin{itemize}
\item The respective memory level is subdivided into several equal units (banks
or sets).
\item The unit in which a memory address is stored is computed by
\[ unit~~=~~block~number~~{\rm mod}~~number~of~units\] 
where 
\[ block~number~~=~~\left\lfloor \frac{address}{interleaving~level} \right\rfloor \]
holds. (For cache memories, the interleaving level is equal to the cache line
size.) 
\item The memory level is efficiently used if the memory accesses are evenly
spread over the different units.
\end{itemize}

{\footnotesize
{\bf Example:} Due to the similarity between the set associativity and the memory
bank problem, the enquiry functions {\tt units} and {\tt interleave\_factor} can
be reused for set associativity. Whether or not the enquiry function {\tt units}
returns the number of banks or the number of sets is {\em irrelevant\/} to the
algorithm. 

}

\item [{\em Vector Registers}\/:]
Vector registers form the highest level in the memory hierarchy of a
register-to-register vector computer.
Crucial for performance considerations
are the length and the number of vector registers. This information can be
obtained from enquiry functions already defined.

{\footnotesize
{\bf Example:} For the vector register level, the enquiry function {\tt size}
returns the {\em aggregate size\/} of all vector registers. The enquiry function
{\tt units} yields the number of vector registers. Subsequently, the length of
the vector registers can easily be derived. {\tt interleave\_factor} returns
$0$, which
indicates that the addresses stored in the vector registers do not obey any
constant relation. In this way vector registers can be distinguished from
banked memory and from cache.

}
 
\item [{\em Shared/Private Indicator}\/:]
In a time sharing environment some memory levels (main memory, 
disc space) can be shared spatially between different processes\,\footnote{Caches are exclusively
available to the executing process.}.
Memory sharing
reduces the size of memory available to a process. The size of
available memory is no longer a static, rather a {\em dynamic}\/ entity.

{\footnotesize
{\bf Example:} The previously defined enquiry function {\tt size} should
be implemented to return the {\em currently\/} available memory size on a
certain level of the memory hierarchy.

}

An additional enquiry function could indicate
whether this size depends on time or is a constant (which indicates that a
memory level is private to an executing process).

{\footnotesize
{\bf Example:} The enquiry function {\tt memory\_sharing} indicates the mode
(exclusive or shared) in which the memory level {\sl level} of the memory
hierarchy {\sl node\_id} is used.
\begin{tabbing}
aaaa\= \kill
\> {\sl memory\_mode} = {\tt memory\_sharing(} {\sl node\_id} {\tt ,}
{\sl level} {\tt )}
\end{tabbing}

}
\end{description}

\subsubsection{Parameterization of Interconnection Networks}
Several possible parameterizations of interconnection networks have been
discussed by Augustyn, Krommer and Ueberhuber~\cite{augustyn91}. The
conclusion of this study was that information about network topology is
unwieldy and difficult to exploit in a concise manner. Therefore, in
Subsection~\ref{agv} it has been assumed that the interconnection network
provides a virtually fully connected system. Due to the underlying physical
topology, communication delays between two nodes can vary significantly.
In many applications it is important to perform communication {\em locally}\/,
i.e. communication should primarily take place between processors with a fast
mutual message path. 

{\footnotesize
{\bf Example:}
As pointed out in Subsection~\ref{reqinf}, an efficient dynamic load balancing
algorithm is crucial to the performance of parallel quadrature programs.
A subclass of dynamic load balancing algorithms receiving considerable attention
is based on nearest neighbor task migration (Ahmad et\,al.~\cite{ahmad91},
Schmid, Krommer, Ueberhuber~\cite{schmid92}). A dynamic load balancing
algorithm must be enabled to enquire the nearest neighbors of a processor-memory
node in order to perform nearest neighbor task migration.

}

{\footnotesize
{\bf Example:} An enquiry procedure that enables local communication could be
defined as follows:
\begin{tabbing}
aaaa\= {\tt near\_proc(} \=\kill
\> {\tt call near\_proc(} {\sl message\_size} {\tt ,} {\sl delay\_limit} {\tt ,}
{\sl num\_proc} {\tt ,} {\sl proc\_vector} {\tt )}
\end{tabbing}
The input variables of {\tt near\_proc} are
{\sl message\_size} and {\sl delay\_limit}; the output variables are
{\sl num\_proc}
and {\sl proc\_vector}. {\sl proc\_vector} contains a list of those
{\sl num\_proc} processors to which a message of length {\sl message\_size} can
be transmitted with a communication delay of less than {\sl delay\_limit}.
The processors in {\sl proc\_vector} are ordered with respect to increasing
communication delay, i.e. the processor with the least communication delay
(the {\em nearest\/} neighbor) comes
first. The processor {\em calling\/} {\tt near\_proc} is {\em not}\/ included
in the list. 

As communication delays depend on the network's current traffic, 
the information provided by {\tt near\_proc} is the
system's {\em estimate\/} of the {\em current\/} situation.

}

Some interconnection topologies are especially suitable for certain
communication patterns. Bus systems, for instance, lend themselves to
broadcast operations; ring topologies are most appropriate for shift operations.
Al\-though the interconnection network is {\em virtually}\/ fully connected, the
program
designer should be enabled to take advantage of knowing properties of the
{\em physical}\/ network.

For the interaction between the algorithm and the interconnection
network, a {\em three layer model}\/ seems to be appropriate:
\begin{itemize}
\item {\em Level 1: Mapping Virtual Topologies}
\vspace{3mm}\\
Many algorithms exhibit regular communication patterns. A virtual communication
topology can be associated with a communication pattern in the following
sense: Any two communicating processors are linked directly; and, if two
processors do not communicate, there is no communication link connecting them.
In other words, the associated topology is the {\em minimal\/} topology (minimum
number of links) that can perform the communication pattern without routing. 
Whether or not 
a communication pattern is suitable for a physical topology depends on
how well the associated topology can be {\em embedded\/} into the physical 
topology.

{\footnotesize
{\bf Example:} \label{sor}
Saltz et\,al.~\cite{saltz87} have discussed the implementation of a red-black
SOR method on a hypercube system. The domain is decomposed into $p$ subregions
($p$ is the number of processors) 
and each region is assigned to a processor. Depending on whether the subregions
are chosen as stripes or as rectangles, the resulting communication patterns
are associated either with a linear array or with a two dimensional mesh
topology. 
Both the linear
array and the two dimensional mesh can be mapped onto a hypercube so that
communicating processors are directly connected (Ber\-tse\-kas,
Tsi\-tsi\-klis~\cite{bertsekas89}). Thus, both data distributions
are suitable for the hypercube topology.

}

The mapping of a virtual topology onto a physical topology should be performed
by the system. Information about the physical topology of the interconnection
network should
be hidden from the program designer.

{\footnotesize
{\bf Example:} The subroutine {\tt map\_topology} requires of the system that
it map the
virtual topology {\sl virtual\_topology} onto those physical processor-memory
nodes whose numbers are contained in the {\sl processor\_vector} of
length {\sl num\_proc}. {\tt map\_topology} returns the data object
{\sl map} that describes the mapping suggested by the system.
\begin{tabbing}
aaaa\= \kill
\> {\tt map\_topology} ({\sl virtual\_topology} {\tt ,} {\sl num\_proc} {\tt ,}
{\sl processor\_vector} {\tt ,} {\sl map} {\tt )}
\end{tabbing}
The data object {\sl virtual\_topology} contains the following items:
\begin{itemize}
\item a string determining the type of the virtual topology
({\tt 'RING'} denotes a ring;
 {\tt 'MESH'} denotes a mesh topology;
 {\tt 'MY\_TOPOLOGY'} may denote a user defined, algorithm specific virtual
 topology\,\footnote{For example, a graph can be used to define a virtual
topology (Ber\-tse\-kas, Tsi\-tsi\-klis~\cite{bertsekas89}).}, etc.),
\item an array of integer parameters determining topology dimensions 
(for a ring topology, ({\tt nr}) denotes a ring with {\tt nr} nodes;
for a mesh topology, ({\tt nx},{\tt ny}) denotes an {\tt nx} $\times$ {\tt ny}
mesh, etc.).
\end{itemize}
The enquiry function {\tt mapping} returns the {\sl physical\_node} onto which
a {\sl virtual\_node} is mapped according to {\sl map}.
\begin{tabbing}
aaaa\= \kill
\> {\sl physical\_node} = {\tt mapping(} {\sl map} {\tt ,} {\sl virtual\_node}
{\tt )}
\end{tabbing}
The data object {\sl virtual\_node} is an integer vector that specifies a node
of the virtual topology. For instance, ({\tt IX,IY}) designates a node in
a virtual mesh topology.

}

\item {\em Level 2: Defining Aggregate Communication Operations}
\vspace{3mm}\\
Some aggregate communication operations, like broadcasts,
have a topology independent meaning. Other aggregate commmunication operations
make sense only in connection with specific virtual topologies.

{\footnotesize
{\bf Example:}
Shift communication operations mean something solely in $n$-dimensional mesh
or torus topologies.

}

Aggregate communication operations with a topology independent meaning
can be specified by aggregate physical communication operations.

{\footnotesize
{\bf Example:} Aggregate physical communication operations are referenced by
data objects containing communication information, as described in Table~1.
Each aggregate communication operation consists of single node broadcast
operations, where a message is sent from $node_{j}$
to $node_{j1}$, \dots, $node_{jn_{j}}$. 
Note that $j \neq k$
does not imply $node_{j} \neq node_{k}$, i.e. a node may appear
several times as a sending node. As pointed out by Bertsekas and
Tsitsiklis~\cite{bertsekas89}, all other aggregate communication patterns can
be built up by
using single node broadcasts, or they are dual to such communication patterns 
(when sender and receivers are exchanged).
Point-to-point message passing is included in single node broadcast as a
special case
($n_{j} = 1$). Thus, all communication patterns can be represented as they are
in Table~1.

}
\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
Sending Node & Receiving Nodes \\
\hline
$node_{1}$ & $node_{1i}, i=1(1)n_{1}$ \\
$node_{2}$ & $node_{2i}, i=1(1)n_{2}$ \\
. & . \\
. & . \\
. & . \\
$node_{k}$ & $node_{ki}, i=1(1)n_{k}$ \\
\hline
\end{tabular}
\end{center}
\begin{center}
\vspace{0 pt}
{\bf Table 1:} Aggregate physical communication operation
\end{center}
\end{table}

Aggregate communication operations with a topology dependent meaning
can be specified by aggregate virtual communication operations.

{\footnotesize
{\bf Example:} The function {\tt virtual\_aggregate} takes as input
a virtual topology {\sl virtual\_topology}, a mapping of the
virtual topology onto the physical topology {\sl map}, and an 
aggregate virtual communication operation
{\sl aggregate\_virtual\_communication}.
{\tt virtual\_aggregate} transforms the aggregate virtual communication
operation into a aggregate {\em physical\/} communication operation and returns
{\sl aggregate\_var}, an identifier
for the aggregate physical communication operation.
\begin{tabbing}
aaaa\= {\sl aggregate\_var} = {\tt virtual\_aggregate(} \=\kill
\> {\sl aggregate\_var} = {\tt virtual\_aggregate(} {\sl virtual\_topology}
{\tt ,} {\sl map} {\tt ,}\\
\>\> {\sl aggregate\_virtual\_communication} {\tt )}
\end{tabbing}
The mapping {\tt map} can be the result of a previous
call of {\tt map\_topology}. But {\tt map} may also be a user provided
mapping. Such mappings make the
specification of aggregate virtual communication operations possible when
virtual topologies are not mapped optimally. Virtual topologies that are not
optimally mapped often arise when data distributions are
determined by previous algorithmic phases associated with other virtual
topologies. 

The data object {\tt aggregate\_virtual\_communication} contains the following
items:
\begin{itemize}
\item a string determining the type of the aggregate virtual communication
operation ({\tt 'SHIFT'}, for instance, denotes a shift operation, etc.),
\item an array of integer parameters specifying accurately the aggregate
virtual communication operation (for a shift operation, for instance,
({\tt idimm1},{\tt ishift1},\dots 
{\tt idimmn},{\tt ishiftn}) denotes a shift in dimension {\tt idimm1} with
stepsize {\tt ishift1}, \dots,  in dimension {\tt idimmn} with
stepsize {\tt ishiftn}, etc.).
\end{itemize}

}

\item {\em Level 3: Delays of Aggregate Communication Operations}
\vspace{3mm}\\
{\footnotesize
{\bf Example:}
The enquiry function {\tt delay} returns the delay of an
aggregate communication operation.
\begin{tabbing}
aaaa\= {\sl delay\_vector} = {\tt delay(} \=\kill
\> {\sl delay\_vector} = {\tt delay(} {\sl aggregate\_var} {\tt ,}
{\sl size\_vector} {\tt )}
\end{tabbing}
The variable {\sl aggregate\_var} identifies a physical
aggregate communication operation, as is described above. {\sl size\_vector} is
a vector of length $k$: the component {\sl size\_vector(j)} gives the size
of the $j$-th message sent.
{\sl delay\_vector} is a vector of length
$k$: the component {\sl delay\_vector(j)} gives the delay of the $j$-th
constituent communication operation. 

}

The results of an enquiry function like {\tt delay} may serve various
purposes:
\begin{itemize}
\item If a
processor is sends a message to itself, no actual transmission takes
place and the
corresponding delay reflects the overhead associated with the communication
routines involved. In this way the delays for asynchronous communication can be
estimated\,\footnote{It is tacitly assumed that the special case where sender and
receiver of a message are identical is {\em not\/} recognized and treated as a
special case, i.e. none of the possible optimization measures are taken.}.
\item If a processor appears several times as a sending node, the overall
communication delay is equal to the maximum constituent communication delay.
\item If the whole aggregate communication pattern takes place in synchronized
manner, i.e. all processors have to wait for the end of all communication
before resuming computation, the overall communication delay is
the maximum communication delay of a single processor. 
\end{itemize}
\end{itemize}

This three layer model can be applied in the following way to
decide which virtual topology is most appropriate for a given interconnection
network.
\begin{itemize}
\item {\tt map\_topology} is used for optimally mapping the possible vitual
topologies. 
\item For each virtual topology, the respective aggregate virtual communication
operations for the algorithm are specified  and
transformed into aggregate physical communication operations. 
\item The delays for the resulting aggregate physical communication operations
and for additionally specified message sizes are enquired. By
comparing the respective delays, the suitable virtual topology can be derived.
\end{itemize}

{\footnotesize
{\bf Example:} In the SOR example on page~\pageref{sor}, both a linear array
and a two dimensional mesh topology are mapped. Both virtual topologies require
shifts as aggregate virtual communication patterns. Whether the array or the
mesh topology is more suitable depends on the problem size
(Saltz et\,al.~\cite{saltz87}).

}

\subsection{Characterization of Compiler and Software}
The efficiency of a computing environment in performing a given task depends not
only on the underlying hardware, but also on many kinds of system software
(compiler, libraries, etc.).

{\footnotesize
{\bf Example:}
Highly optimized BLAS routines are available on many systems. Their performance
can deviate significantly from the performance
of standard Fortran BLAS implementations. For a linear algebra
algorithm based
on BLAS routines, the BLAS routines are transparent. Thus, the algorithm's
performance estimation can be severly flawed.

}

Software factors are hardly amenable to a systematic quantitative
analysis, as is hardware performance. Thus, it is suggested to measure external
software and compiler effects by measuring the run-time behavior of the code
(in particular, the CPU time and the elapsed time).

{\footnotesize
{\bf Example:}
The enquiry function {\tt cpu\_clock} returns the
CPU time consumed by the
calling process since the last {\tt init\_clock} call.
{\tt elapsed\_clock} yields the corresponding elapsed time.
\begin{tabbing}
aaaa\=\kill
\> {\tt init\_clock()}\\
\> $\cdots $\\
\> {\sl cpu\_time} = {\tt cpu\_clock()}\\
\> {\sl elapsed\_time} = {\tt elapsed\_clock()}
\end{tabbing}

}

The actual performance of critical software parts
can be measured by using clock functions. This can be done at different times:
\begin{description}
\item [{\em Before a program run}\/] if the time critical parts of the program
are independent of problem data and dynamic phenomena. The measurement can be
part of the software installation procedure. Another possibility is measuring
any program run and using the accumulated timing data for an algorithmic
tuning.

{\footnotesize
{\bf Example:}
For a linear algebra package, the CPU time needed by various BLAS
routines for a chosen set of input data (size of vectors and matrices)
can be measured. A general performance model of the BLAS routines 
can be derived by fitting a mathematical model to the timing data.
This performance model can be used during run-time for algorithmic decision
making.

}

\item [{\em At the program start}\/] if the time critical parts of the program depend 
on current problem data but do not change during program execution.

{\footnotesize
{\bf Example:}
A result found in Saltz et\,al.~\cite{saltz87} is that the optimal
decomposition for a red-black SOR method on a hypercube system depends on 
the problem size, i.e. the number of grid points. One way to determine the 
appropriate decomposition for a given problem size is to perform a
small number of timesteps for both decompositions at the beginning of a program
run. By comparing the respective performance, the optimal distribution can
be found.

}

\item [{\em During the program run}\/] if the time critical parts of the program 
change during its execution.

{\footnotesize
{\bf Example:}
The time required for one evaluation of the integrand function may depend on
the respective abscissa. As quadrature abscissas are chosen dynamically
during the course of computation, the evaluation times should also be
determined dynamically.

}

\end{description}

\section{Programming Architecture Adaptive Algorithms}
As shown in Figure~9, an architecture adaptive algorithm conceptually consists
of two major parts: the {\em problem solving part}\/ and the {\em algorithm
adaption part}\/. The problem solving part contains those code sections required
for carrying out the original task of the algorithm. The algorithm adaption
part's job is to manage the problem solving activities efficiently. The
algorithm adaption part itself can be subdivided into a {\em decision making
part}\/ and an {\em acting part}\/. The decision making part gathers information
-- for instance, by calling appropriate enquiry functions. It also decides
which measures are to be taken -- according to
a logic developed by the algorithm designer. These measures are subsequently
carried out by the acting part. Note,
however, that this algorithm decomposition is only a conceptual one. It does not
imply that the different parts have to be specified or coded separately. As
shown in a related paper by Bihari and Schwan~\cite{bihari91}, a separate
specification {\em is}\/ possible and results in a more structured approach.

\begin{figure}
\begin{center}
\setlength{\unitlength}{0.0125in}%
\begin{picture}(202,134)(147,637)
\thicklines
\multiput(198,738)(0.00000,-8.00000){9}{\line( 0,-1){  4.000}}
\multiput(198,738)(8.16216,0.00000){19}{\line( 1, 0){  4.081}}
\multiput(198,704)(8.16216,0.00000){19}{\line( 1, 0){  4.081}}
\put(147,637){\framebox(202,134){}}
\put(147,670){\line( 1, 0){202}}
\put(248,750){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Algorithm Adaption}}}
\put(274,717){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Decision Making }}}
\put(274,685){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Acting}}}
\put(248,649){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\tenrm Problem Solving}}}
\end{picture}\\
\vspace{15 pt}
{\footnotesize {\bf Figure 9:} Structure of architecture adaptive algorithms}
\end{center}
\end{figure}

\section{Assessment and Outlook} \label{six}
The authors are well aware of possible objections to the {\sc aaa}
concept.

\subsection{Low-Level Approach}
Most of current efforts made to create portable, efficient parallel software
rely on
a high-level approach (functional languages, global name space languages, etc.).
>From this viewpoint
the {\sc aaa} approach appears an anachronism. However, the {\sc aaa} 
approach is {\em not}\/ meant to be used by the average programmer, who
legitimately prefers to deal with a parallel computer system at a very high
level.
Rather, it is meant for people developing scientific software systems which are
extensively reused, like scientific
software libraries. Because of this extensive reuse, porting costs very soon
exceed even high development costs. As a matter of
fact,
the {\sc aaa} approach {\em promotes}\/ the high level approach to parallel
systems by supporting the development of high quality parallel software
packages.
Software libraries which utilize the power of current and future parallel
machines by adapting themselves to different
architectures relieve the average programmer from dealing explicitely with
machine details.

\subsection{Complexity}
The complexity of architecture adaptive algorithms increases
rapidly with the extent and intricacy of its problem solving part and with the
complexity of the
underlying machine model. Machine models will become even more complex
in the future (by including cache hierarchies, SIMD/MIMD switchable
systems, time-sharing and space-sharing systems, etc.). The
algorithm designer will probably not be able to write programs which are
{\em optimal}\/ for all current and future parallel systems. In many cases it
is not necessary to find optimal solutions. Often reasonable solutions are
sufficient.
Relaxing optimality demands can simplify algorithm
adaption significantly. Sophisticated software development tools, like
simulators for parallel software and hardware, could be a great
help in the development process of {\sc aaa} software.

\subsection{Feasibility}
No ``proof'' has been brought forward so far that the {\sc aaa} approach is
indeed
{\em feasible}\/. Specifically, no experimental evidence, such as an
architecture adaptive parallel quadrature algorithm, has been produced yet.
The authors are well aware that this is a severe objection to
the {\sc aaa}
approach. Without such evidence the {\sc aaa} approach is bound to remain
merely theoretical. The authors' future work will concentrate
on furnishing a feasibility study for the {\sc aaa} methodology by developing
prototype software
for parallel quadrature within the {\sc aaa} framework.

\section*{Acknowledgement}
We would like to thank Roman Augustyn and Josef Fritscher for many helpful
discussions.

\begin{thebibliography}{99}
{\small
\bibitem{ahmad91}
   I.\ Ahmad, A.\ Ghafoor, K.\ Mehrotra, {\sl Performance Prediction of
   Distributed Load Balancing on Multicomputer Systems}, 
   Proceedings Supercomputing '91, IEEE Press, Los Alamitos CA, 1991,
   pp.~830--839.
   
\bibitem{almasi89}
   G.\,S.\ Almasi, A.\ Gottlieb, {\sl Highly Parallel Computing},
   Benjamin-Cum\-mings, Redwood City, 1989.

\bibitem{f90norm}
   {\sl American National Standard: Fortran\,90},
   American National Standards Institute Inc. (ANSI X3J3-1990), New\,York, 1991.

\bibitem{andrews91}
    J.\,B.\ Andrews, C.\,D.\ Polychronopoulos, {\sl An Analytical Approach to
    Performance/Cost Modeling of Parallel Computers}, Journal of Parallel and
    Distributed Computing 12 (1991),
    pp.~343--356.

\bibitem{augustyn91}
   R.\ Augustyn, A.\,R.\ Krommer, C.\,W.\ Ueberhuber, {\sl Effizient-portable
   Programmierung von Parallelrechnern}, 
   Report No. 85/91, Institute for Applied and Numerical Mathematics,
   Technical University Vienna, 1991.
      
\bibitem{bertsekas89}
   D.\,P.\ Bertsekas, J.\,N.\ Tsitsiklis, {\sl Parallel and Distributed
   Computation -- Numerical Methods}, Prentice-Hall, Englewood Cliffs, 1989.

\bibitem{bihari91}
   T.\,E.\ Bihari, K.\ Schwan, {\sl Dynamic Adaption of Real-Time Software},
   ACM Transactions on Computer Systems 9 (1991), pp.~143--174.
   
\bibitem{calahan88}
   D.\,A.\ Calahan, D.\,H.\ Bailey, {\sl Measurement and Analysis of Memory
   Conflicts on Vector Multiprocessors}, in ``Performance Evaluation of
   Supercomputers'' (J.\,L.\ Martin, Ed.), North-Holland, Amsterdam, 
   1988, pp.~83--106.
      
\bibitem{ra75}
   P.\,J.\ Davis, P.\ Rabinowitz, {\sl Methods of Numerical Integration},
   Academic Press, New York, 1975.
 
\bibitem{doncker91c}
   E.\ de\,Doncker, J.\,A.\ Kapenga, {\sl Parallel Quadrature on Loosly Coupled
   Systems},
   in ``Numerical integration --- Recent developments,
   software and applications'' (T.O. Espelid, A.C. Genz, Eds.),
   Kluwer Academic Publishers, Dordrecht, 1992, to appear.
   
\bibitem{garey79}
   M.\,R.\ Garey, D.\,S.\ Johnson, {\sl Computers and Intractability: A Guide
   to the Theory of $N\!P$-Completeness}, Freeman, San\,Francisco, 1979.
      
\bibitem{hennessy90}
   J.\,L.\ Hennessy, D.\,A.\ Patterson, {\sl Computer Architecture --
   A Quantitative Approach}, Morgan Kaufmann, San Mateo CA, 1990.
         
\bibitem{hockney88}
   R.\,W.\ Hockney, C.\,R.\ Jesshope, {\sl Parallel Computers 2},
   Adam Hilger, Bristol Philadelphia, 1988.
   
\bibitem{houstis90}
    E.\,N.\ Houstis, J.\,R.\ Rice, N.\,P.\ Chrisochoides, H.\,C.\ Karathanasis,
    P.\,N.\ Papachiou, M.\,K.\ Samartzis, E.\,A.\ Vavalis, K.\,Y.\ Wang,
    S.\ Weerawarana, {\sl // {\sc Ellpack}: A Numerical Simulation Programming
    Environment for Parallel MIMD Machines}, 1990 International Conference on
    Supercomputing, ACM Press, New\,York, 1990, pp.~96--107.

\bibitem{johnsson91}
    S.\,L.\ Johnsson, {\sl Performance Modeling of Distributed Memory
    Architectures}, Journal of Parallel and Distributed Computing 12 (1991),
    pp.~300--312.

\bibitem{krommer91b}
   A.\,R.\ Krommer, C.\,W.\ Ueberhuber, {\sl A Survey of Parallel Quadrature
   Algorithms}, Technical Report, Austrian Center for Parallel Computation,
   Vienna, 1992,
   to appear.

\bibitem{krommer92a}
   A.\,R.\ Krommer, C.\,W.\ Ueberhuber, {\sl Architecture Adaptive Algorithms},
   Technical Report ACPC/TR 92-2,  Austrian Center
   for Parallel Computation, Vienna, 1992.

\bibitem{lee88}
    I.\ Lee, D.\ Smitley, {\sl A Synthesis Algorithm for Reconfigurable
    Interconnection Networks}, IEEE Transactions on Computers 37 (1988),
    pp.~691--699.

\bibitem{naur67}
   P.\ Naur, {\sl Machine Dependent Programming in Common Languages},
   BIT 7 (1967), pp.~123--131.

\bibitem{quadpack}
   R.\ Piessens, E.\ de\,Doncker-Kapenga, C.\,W.\ Ueberhuber, D.\,H.\ Kahaner,
   {\sc Quadpack}\,--- {\sl A Subroutine Package for Automatic Integration},
   Springer-Verlag, Berlin Heidelberg New\,York Tokyo, 1983.

\bibitem{saltz87}
    J.\,H.\ Saltz, V.\,K.\ Naik, D.\,M.\ Nicol, {\sl Reduction of the Effects of
    the Communication Delays in Scientific Algorithms on Message Passing MIMD
    Architectures}, SIAM Journal on Scientific and Statistical Computing 8
    (1987), pp.~118--134.

\bibitem{schmid92}
   C.\ Schmid, A.\,R.\ Krommer, C.\,W.\ Ueberhuber, {\sl Dynamic Load Balancing
   -- An Overview}, 
   Report No. 90/92, Institute for Applied and Numerical Mathematics,
   Technical University Vienna, 1992.

\bibitem{so88}
    K.\ So, V.\ Zecca, {\sl Program Locality of Vectorized Applications Running
    on the IBM 3090 with Vector Facility}, IBM Systems Journal 27 (1988),
    pp.~436--452.

\bibitem{sunderam90}
   V.\ Sunderam, {\sl PVM: A Framework for Parallel Distributed Computing},
   Concurrency: Practice and Experience 2 (1990), pp.~315--339.
      
\bibitem{vaughan91}
   S.\,J.\ Vaughan-Nichols, {\sl Catch as Cache Can}, Byte 16--6 (1991),
   pp.~209--215.
}
\end{thebibliography}
         
\end{document}