
			     PPerfMark: 
       An MPI Parallel Performance Analysis Tool Validation Suite
                 Kathryn Mohror and Karen Karavanic
                      Portland State University
                              March 2004                

This work is based on Grindstone: A PVM Parallel Performance Analysis 
Tool Validation Suite by Jeff Hollingsworth and Michael Steele, 
University of Maryland, September 1996. The programs were altered to 
support MPI.

The following are the original program descriptions by Jeff 
Hollingsworth and Michael Steele, with a small change in the text for 
ping-pong.c to reflect the change to MPI.


The programs in this directory comprise a validation suite of programs
that demonstrate simple but common problems which parallel programs 
commonly suffer from.  This is the starting point for a standardized
validation suite which authors of performance analysis tools will be
able to use to verify that their oftware gives corrrect prognoses for
common problems.

			COMMUNICATION PROGRAMS

big-message.c
-------------
Big-message passes very large messages (an array of 100,000 integers).  
The intended bottleneck is that the overhead associated with 
setting up and sending a large message should slow the program 
down.  Two processes are spawned:  the parent starts
by sending the large message to the child.  When the child process
receives the message, it sends it back.  This continues for a preset
number of iterations.

intensive-server.c
------------------
The program demonstrates the pitfall of
having a client-server model in which the server is overloaded.  In
the program intensive-server, the parent process (which will be the
server) spawns three child processes (which will become the clients).
The clients initially wait for a message from the server telling them
to start, and then go into a cycle of sending the server a message and
waiting for a response.  Meanwhile, the server is receiving the
messages from clients, but then wastes time before sending out
responses.  This simulates the server having too much work to do in
comparison with the clients.

ping-pong.c
-----------
Ping-pong illustrates an application that is being slowed down by the
round-trip latencies between processes.  This program spawns one worker
process. Like small-messages, it sends a short message from one process
to the other.  However, before the sender continues, it waits for a
response from the other process.  Message packing and unpacking time,
MPI implementation latency, and message time-of-flight all contribute to the
critical path of this program.

random-barrier.c
----------------
The next bottleneck demonstration is similar to the intensive-server
problem, only this time no single process is the bottleneck.  The
parent process starts three children, and then sits and wastes time
again.  The other processes wait at a pvm_barrier call.  When the
parent finishes wasting time, it passes a token to another randomly
selected process (hence, this program is called random-barrier), and
that process wastes a predetermined amount of time.  The process
continues until each process has gone through a predetermined number of
iterations.

small-messages.c
----------------
The fourth program in the test suite demonstrates the problems of
passing too many small messages.  The program small-messages
was designed to show how the overhead associated with message passing
could become a bottleneck.  In this example, the parent process starts
up three children.  Then, all of the children begin sending small messages
(the size of two integers) to the parent in an attempt to swamp the
parent with too many incoming messages.

wrong-way.c
-----------
The final test program highlights the problem of passing messages
``out-of-order.''  This problem could arise if one process is expecting
messages in a certain order, but another process is sending messages
which are not in the expected order.  This could also arise if the two
processes have to communicate over a ``noisy'' network, and message
packets are dropped or have to be resent.  In the wrong-way program, an
extreme case of having messages out-of-order is used.  Two processes
are spawned.  The first process sends messages with messages numbered 1
through n (where n is a predetermined number; I used 1000 for my
tests).  The second process waits to receive the messages, but expects
to receive the messages in the order n through 1.


			COMPUTATION PROGRAMS

hot-procedure.c
---------------
This program demonstrates a bottleneck created by a single procedure
that is consuming the majority of the time.  It is a completely serial
program, and not additional processes are created.  The program
contains 21 procedures that are called 100 times each.  Almost all of
the processor time is due to one procedure bottleneckProcedure.

diffuse-procedure.c
-------------------
This program demonstrates a procedure bottleneck that is distributed
among several processes in an application.  The procedure
bottleneckProcedure is responsible for 50% of the CPU time in the
overall program.  Each of the other procedures consumes approximately
2.5% of the programs CPU time.  The program consists of four "rounds"
where the bottleneckProcedure is active in each of the programs five
processes.  When a process is not executing bottleneckProcedure, is it
runs one of the 20 irrelevantProcedure*.  The only communication or
synchronization in the program is 21 barrier operations per process.

system-time.c
-------------
This program spends most of its time executing code in the operating
system kernel.  The program is completely serial and does not create
any additional processes.  Depending on the operating system, it should
spends about 75% of its time as "system time" and the remaining 25% is
user time. System time is consumed by having the program repetitvely
call the UNIX system call kill to send itself a continue signal.


Copyright Information
---------------------
Copyright (c) 1996 Jeff Hollingsworth and Michael Steele. All rights reserved.

Permission to use, copy, modify, and distribute this software and
its documentation for any non-commercial purpose is hereby granted,
provided that the above copyright notice appear in all copies. No
title to or ownership of the software is hereby transferred.

NOTICE:  This software is provided ``as is'', without any
warranty, including any implied warranty for merchantability or
fitness for a particular purpose.  Under no circumstances shall
the principals or their agents be liable for any use of, misuse
of, or inability to use this software, including incidental and
consequential damages.

Copyright (c) 2004 Kathryn Mohror and Karen Karavanic. All rights reserved.
