Subject: SOLVER Compact Application

From: [email-masked] (David Walker)
Date: Thu, 28 Oct 1993 08:52:59 -0400

Via: uk.ac.edinburgh.castle; Mon, 18 Oct 1993 06:31:49 +0100
Date: Sun, 17 Oct 93 16:28:46 BST
From: S P Booth <[email-masked]>
Subject: Re: ParkBench applications
To: "David W. Walker" <[email-masked]>

Sorry I took so long to reply to this.
If any of this needs any futher clarification don't hesitate to send me
some email.
		spb

-------------------------------------------------------------------------
                  PARKBENCH COMPACT APPLICATIONS SUBMISSION FORM

To submit a compact application to the ParkBench suite you must follow the
following procedure:

1. Complete the submission form below, and email it to David Walker
   at [email-masked]. The data on this form will be reviewed 
   by the ParkBench Compact Applications Subcommittee, and you will
   be notified if the application is to be considered further for
   inclusion in the ParkBench suite.
   
2. If ParkBench Compact Applications Subcommittee decides to consider
   your application further you will be asked to submit the source code
   and input and output files, together with any documentation and papers
   about the application. Source code and input and output files should
   be submitted by email, or ftp, unless the files are very large, in
   which case a tar file on a 1/4 inch cassette tape. Wherever possible 
   email submission is preferred for all documents in man page, Latex 
   and/or Postscript format. These files documents and papers together
   constitute your application package. Your application package should
   be sent to:
David Walker
                Oak Ridge National Laboratory
                Bldg. 6012/MS-6367
                P. O. Box 2008
                Oak Ridge, TN 37831-6367
                (615) 574-7401/0680 (phone/fax)
                [email-masked]

   The street address is "Bethal Valley Road" if Fedex insists on this.
   The subcommittee will then make a final decision on whether to include 
   your application in the ParkBench suite.

3. If your application is approved for inclusion in the ParkBench suite
   you (or some authorized person from your organization) will be asked
   in complete and sign a form giving ParkBench authority to distribute,
   and modify (if necessary), your application package.

-------------------------------------------------------------------------------
Name of Program         : SOLVER
                        : 
-------------------------------------------------------------------------------
Submitter's Name        : Stephen P. Booth
Submitter's Organization: UKQCD collaboration
Submitter's Address     : EPCC
			  The University of Edinburgh
			  James Clerk Maxwell Building
			  The King's Buildings 
			  Mayfield Road
			  Edinburgh EH9 3JZ
		          Scotland
Submitter's Telephone # : +44 (0)31 650 5746
Submitter's Fax #       : +44 (0)31 622 4712
Submitter's Email       : [email-masked]
-------------------------------------------------------------------------------
Cognizant Expert(s)     : Dr S.P.Booth
CE's Organization       : EPCC/UKQCD
CE's Address            : The University of Edinburgh
			  James Clerk Maxwell Building
			  The King's Buildings 
			  Mayfield Road
			  Edinburgh EH9 3JZ
		          Scotland
CE's Telephone #        : +44 (0)31 650 5746
CE's Fax #              : +44 (0)31 622 4712
CE's Email              : [email-masked]

Cognizant Expert(s)     : Dr R.D. Kenway
CE's Organization       : EPCC/UKQCD
CE's Address            : The University of Edinburgh
			  James Clerk Maxwell Building
			  The King's Buildings 
			  Mayfield Road
			  Edinburgh EH9 3JZ
		          Scotland
CE's Telephone #        : +44 (0)31 650 5245
CE's Fax #              : +44 (0)31 622 4712
CE's Email              : [email-masked]

-------------------------------------------------------------------------------
Extent and timeliness with which CE is prepared to respond to questions and
bug reports from ParkBench :

S.Booth is prepared to respond quickly to questions and bug reports.
We have a strong interest in the portability and performance of this code.

-------------------------------------------------------------------------------
Major Application Field : Lattice gauge theory
Application Subfield(s) : QCD
-------------------------------------------------------------------------------
Application "pedigree" (origin, history, authors, major mods) :

SOLVER is part of an ongoing software development exercise carried out
by UKQCD (The United Kingdom Quantum Chromo-Dynamics  collaboration)
To develop a new generation of simulation codes. The current generation
of codes were highly tuned for a particular machine architecture so a
software development exercise was started to design and develop a set of
portable codes. This code was developed by S.Booth and N.Stanford of
the University of Edinburgh during the course of 1993.
Solver is a benchmark code derived from the codes used to generate quark
propagators. It is designed to benchmark and validate the computational 
sections of this operation. It differs from the production code in that
it self initialises to non-trivial test data rather than performing file
access. This is because there is no accepted standard for parallel file
access.
The benchmark was originally developed as part of a national UK procurement
exercise.

-------------------------------------------------------------------------------
May this code be freely distributed (if not specify restrictions) :

The code may be freely distributed for benchmarking purposes but 
the code remains the property of UKQCD and we ask to be contacted
if anyone wishes to use it as an application code.

-------------------------------------------------------------------------------
Give length in bytes of integers and floating-point numbers that should be
used in this application:

All floating point numbers are defined as macros (either Fpoint or Dpoint)
The majority of the variables are Fpoint. Dpoint is only used for
accumulation values that may require higher precision. This allows the
precision of the program to be changed easily. For small and
intermediate problem sizes 4 byte Fpoints and 8 byte Dpoints should be 
sufficient. For large problems higher precision may be required.
INTEGERS must be large enough to hold the number of sites 
allocated to a processor (4 bytes almost certainly sufficient)
The COMPLEX type is not used.

-------------------------------------------------------------------------------
Documentation describing the implementation of the application (at module
level, or lower) :

Documentation exists for all program routines except some low level
routines local to a single source file.

-------------------------------------------------------------------------------
Research papers describing sequential code and/or algorithms :

-------------------------------------------------------------------------------
Research papers describing parallel code and/or algorithms :

-------------------------------------------------------------------------------
Other relevant research papers:

-------------------------------------------------------------------------------
Application available in the following languages (give message passing system
used, if applicable, and machines application runs on) :

Two version of the application were developed in parallel.
1) A HPF version (both CMF and HPF directives)
2) A message passing version.

The message passing version uses ansi-F77 with the following extensions
a) CPP is used for include files and some simple macros and build-time 
   conditionals.
b) The F77 restrictions of variable names are not adhered to though the
   authors have tools to convert the code to conform.

All of the message passing operations are confined to a small number of
routines. These routines were designed to be implementable in as many
different message passing systems as possible. Current versions are
1) fake - converts the program to a single processor code.
2) PARMACS - original parallel versions
3) PVM - under development.

-------------------------------------------------------------------------------
Total number of lines in source code: 15567
Number of lines excluding comments  : 10679
Size in bytes of source code        : 432398
-------------------------------------------------------------------------------
List input files (filename, number of lines, size in bytes, and if formatted) :

None 

-------------------------------------------------------------------------------
List output files (filename, number of lines, size in bytes, and if formatted) :

standard output: formatted text

-------------------------------------------------------------------------------
Brief, high-level description of what application does:

The application generates quark propagators from a  background gauge
configuration and a fermionic source. This is equivalent to solving 
M psi = source 
where psi is the quark propagator and M (a function operating on psi)
depends on the gauge fields.
The benchmark performs a cut down version of this operation.

-------------------------------------------------------------------------------
Main algorithms used:

Conjugate gradient least norm with red-black pre-conditioning.

-------------------------------------------------------------------------------
Skeleton sketch of application:

The benchmark code initialises the gauge field to a unit gauge
configuration. (The results for a unit gauge can be calculated
analytically allowing a check on the results)
A gauge transformation is then applied to the gauge field. A unit gauge
field only consists of zeros and ones by applying a gauge transformation
non-trivial values are generated. Quantities corresponding to physical
observables should be unchanged by such a transformation. 
In application code the gauge field would have been read in from disk.
The source field is initialised to a point source (a single non-zero
point on one lattice site)
An iterative solver is called to generate the quark propagator.
The solver routine also generates timing information.
In application code this would then be dumped to disk.
In the benchmark we use the quark propagator to generate a physically
significant quantity (the pion propagator). This generates a single real
number for each timeslice of the lattice. These values are printed to
standard out.

This procedure requires a large number of iterations. For benchmarking
we are only interested in the time per-iteration and some check on the
validity of the results. We therefore usually only perform a fixed
number of iterations (say 50) to generate accurate timing information
and verify the results by comparison with other machines.

-------------------------------------------------------------------------------
Brief description of I/O behaviour:

Unless an error occurs a single processor outputs to standard out.

-------------------------------------------------------------------------------
Describe the data distribution (if appropriate) :
A spacial decomposition is used to distribute the 4-D arrays over a 4-D
grid of processors. Each dimension is distributed independently.
The program supports non-regular decomposition,
e.g. a lattice of width 22 will be distributed across a processor-grid
of width 4 as (6, 6, 5, 5)

-------------------------------------------------------------------------------
Give parameters of the data distribution (if appropriate) :
Lattice size:     NX NY NZ NT
processor grid:   NPX NPY NPZ NPT

-------------------------------------------------------------------------------
Brief description of load balance behavior :

Load balancing depends only on the distribution, if the lattice size can
be exactly divided by the processor grid size all processors will have 
the same workload. In practice it is often useful to trade load
balancing for a larger number of processors.

-------------------------------------------------------------------------------
Give parameters that determine the problem size :
Lattice size, NX NY NZ NT
problem size is NX*NY*NZ*NT
-------------------------------------------------------------------------------
Give memory as function of problem size :

In a production environment there are build time parameters that
set the array sizes and problem/machine sizes can be set at runtime. 
When creating a benchmark program it seemed less confusing to set
lattice and processor-grid sizes at build time and derive all other
quantities from them. The appropriate parameters for memory use are
Max_body (maximum number of data-points per/processor)
Max_bound (maximum number of data points on a single boundary between
   two processors)
If LX LY LZ LT are the local lattice sizes obtained by dividing the
lattice size by the processor grid size and rounding up to the nearest integer.
Max_body = (LX*LY*LZ*LT)/2
Max_bound = MAX( LX*LY*LZ/2 ,LY*LZ*LT/2 ,LX*LZ*LT/2 ,LX*LY*LT/2 )

The code contains a number of build-time switches for variations
in the implementation that may be beneficial on some machines. The
memory usage depends on these switches but typical values are:
108 * Max_body + 36 * Max_bound Fpoints
16 * (Max_body + Max_bound) INTEGERS

-------------------------------------------------------------------------------
Give number of floating-point operations as function of problem size :

Each iteration performs 2760 floating point operations per lattice site.
ie. 50 iteration using a 24^3*48 lattice = 9.16e+10 floating point operations.

-------------------------------------------------------------------------------
Give communication overhead as function of problem size and data distribution :

For each iteration every processor sends 24 messages to each of its 8
neighbours each message contains one floating point number for each
lattice point in the common boundary. Two global sum operations are also
performed for each iteration.

-------------------------------------------------------------------------------
Give three problem sizes, small, medium, and large for which the benchmark
should be run (give parameters for problem size, sizes of I/O files,
memory required, and number of floating point operations) :

18^3*36		2.90e+10 fp operations
24^3*48		9.16e+10 fp operations
36^3*72		4.64e+11 fp operations

-------------------------------------------------------------------------------
How did you determine the number of floating-point operations (hardware
monitor, count by hand, etc.) :

count operations in each loop by hand. The code contains a counter to
sum these values.

-------------------------------------------------------------------------------
Other relevant information:

-------------------------------------------------------------------------------