Subject: Re: kernels

From: Vladimir Getov <[email-masked]>
Date: Wed, 19 May 93 02:41:37 BST

----------
X-Sun-Data-Type: text
X-Sun-Data-Description: text
X-Sun-Data-Name: text
X-Sun-Content-Lines: 21

> 
> Greetings to kernel working group! Apologies for lack
> of much activity but I have not been completely idle.
> I will put up an outline/draft/working document today
> which includes material from NAS Parallel Benchmark
> papers, Genesis papers and input from Roger Hockney
> and David Walker.
> I leave for US on Thursday so there is still time for some
> iterations before the meeting on Monday.
> 
> Tony Hey
>

Hi all,

Please, find below the first draft/working document on kernel 
benchmarks (file kernel1.tex) in LaTeX format.

Vladimir Getov
 
----------
X-Sun-Data-Type: default
X-Sun-Data-Name: kernel1.tex
X-Sun-Content-Lines: 138

%file: kernel1.tex
\chapter{Kernel Benchmarks\protect\footnote
{Some preliminary thoughts from Tony Hey: for discussion
in Knoxville.}}
 
\section{Introduction}

The low-level benchmark codes are designed to measure the basic 
architectural features of parallel machines. Full application codes 
obviously measure the performance of a parallel system on the full 
problem and this is ultimately what the user wants. However, in many 
instances, the full application codes are complex, contain many 100s 
of thousands of lines of Fortran, and are not available in a suitable
parallel version. In order to obtain a guide to the performance of any
given parallel system on a particular application something less 
complex than the full application is useful. A profile of the 
sequential version of the application enables the compute intensive 
portions of the program to be identified. It is these compute-intensive
sections of an application that we wish to model with the introduction 
of parallel kernel benchmarks.

The popular kernel benchmarks that have been used for traditional vector
supercomputers, such as the Livermore Loops ~\cite{?}, the LINPACK
benchmark ~\cite{?} and the original NAS kernels ~\cite{?}, are clearly 
innappropriate for the performance evaluation of highly parallel machines.
First of all, the tuning restrictions of these benchmarks rule out many 
widely used parallel extensions. More importantly, the computation and 
memory requirements of these programs do not do justice to the vastly 
increased capabilities of the new parallel machines, particularly those 
that will be available by the mid 1990's. For these reasons we believe 
that a new, widely accepted set of kernel benchmarks is desirable as a 
step on the way to more sensible and scientific performance reporting of 
parallel systems.

The kernel codes are typically up to a few thousand lines of Fortran
and are sufficiently simple that the performance of a given parallel
machine on this program may be related to the underlying architectural
parameters. It must be acknowledged, however, that the performance on
kernels alone  is insufficient to completely assess the performance
potential of a parallel machine on full scientific applications. The
chief diificulty is that a certain data structure may be very efficient
on a certain system for one of the isolated kernels, and yet this data
structure would be inappropriate if incorporated into a larger 
application.  For example, the performance of a real CFD application on
a parallel system is critically dependent on data motion between 
different computational kernels. In addition, full applications 
typically have initialization phases, I/O and so on, so complete 
reproduction of these features can be of critical importance for a 
realistic guide to performance.

For these reasons we envisage a level of complexity above kernel codes
which we call 'compact applications'. These are full but perhaps 
simplified application codes that contain all the necessary features of
the full problem but are sufficiently simple to run and analyse. These 
are the province of the Compact Application working group.

\section{The Proposed Kernel Benchmarks}

The kernels should span a reasonably wide range of application areas
and include the most frequently encountered computationally intensive
types of problems. We have tentatively grouped them into four sets of
codes. Examples of such benchmark codes are available in some of the
existing parallel benchmark suites (NAS, Genesis, etc). It is important
to avoid duplication and redundancy. For this reason we have attempted
to list some of the attributes of the parallel system tested by each
kernel benchmark.

\subsection{Matrix benchmarks}
\begin{enumerate}
\item Transpose. Matrix transpose is an important benchmark because it
exercises the communications of computer heavily on a realistic problem
where pairs of processors communicate with each other simultaneously.
It is a useful test of the total communications capacity of the
network.
\item Dense matrix multiply. Communication involves broadcast of data
along rows of mesh, and periodic shift along column direction (or vice
versa).
\item Matrix diagonalization.
\item Dense LU factorization with partial pivoting. Searching for a pivot
is basically a reduction operation within one column of the processor 
mesh. Exchange of pivot rows is a point-to-point communication. Update 
phase requires data to be broadcast along rows and columns of the 
processor mesh.
\item Sparse matrix eigenvalue problem by conjugate gradient. This kernel
is typical of unstructured grid computations in that it tests irregular 
long distance communications, employing unstructured matrix-vector 
multiplication.
\item QR Decomposition. In this benchmark parallelization is achieved by
distribution of rows on a ring of processors using block interleaving.
The first phase of the decomposition is to decompose the local
submatrices and involves no communication or decomposition. In the
second phase the processors cooperate to complete the decomposition.
\end{enumerate}
\subsection{Fourier Transform}
\begin{enumerate}
\item 1-D FFT. Popular test with relatively high level of parallelism, but
   low level of vectorization and a hypercube type communication.
\item 3-D FFT. For the multidimensional cases we have the option of two
different approaches. Either distribute the FFT over each dimension, and
apply a parallel FFT in each direction with differing stride. Or, do not
distribute the data over the first direction so FFT's are purely local 
in this direction, then transpose the data so that the FFT's in the 
second direction are purely local, and so on for the other directions. 
All the communication is now in the transpose operation.
\item PDE by 3-D FFT.  Essence of many 'spectral' codes. Rigorous test 
of long distance communication performance.
\end{enumerate}
\subsection{PDEs}
Communication is basically exchange with neighbors. Convergence check is
a reduction. A variety of methods and update stencils may be used:
\begin{enumerate}
\item Jacobi
\item Gauss-Seidel
\item SOR. This benchmark solves the Poisson equation on a 3-dimensional
grid by parallel red-black relaxation. Only nearest neighbour
interactions are required and the number of floating point operations
per grid point is very small when compared to other more complex PDEs.
\item Finite Element
\item Multigrid. This kernel requires highly structured long distance
communication. Tests both short and long distance data exchange.
\end{enumerate}
\subsection{Other}
\begin{enumerate}
\item Embarassingly Parallel. It provides an estimate of the upper
achievable limits for floating point performance, i.e. the performance
without significant interprocessor communication.
\item Large Integer Sort. This kernel performs a sorting operation that
is important in `particle method' codes. It tests both integer
computation speed and communication performance.
\end{enumerate}

\section{Concluding Remarks}

The precise choice of which code should be selected for each benchmark
kernel and which kernels should be selected should be discussed at
the next meeting. Obviously there is a need to keep the suite short
enough to be used while at the same time containing sufficient useful
information.