----------------------------------------
RECORD FRAMEWORK CONTENTS
----------------------------------------
1. Overview

2. Project layout
   A. Wrapper generator
   B. Trace instrumentation
   C. Tests

3. Record source
   A. Task-level compression
   B. Interoperability
   C. Cross-node compression
   D. File descriptions
   E. Histogram based trace recording

4. Building

5. Instrumenting applications

****************************************
1. Overview
****************************************
The record framework's purpose is to capture and record 
a compressed trace of all MPI communication performed by an 
MPI application for lossless replay.  For lossless replay 
to be possible, we must note for each task: (1) What MPI call
is used and (2) the call's function arguments.  Compression 
of traces is used due to HPC's trend towards massivly parallel 
environments.  Without compression techniques, trace files and 
memory usage during a run would be unscalable for large jobs.

Capture of MPI calls is done w/ a stripped version of 
Umpire's wrapper generator.  The wrapper generator provides
hooks into every MPI call regardless of MPI implementation.
Using these hooks, we are able to record call and argument 
information.  The information is kept appended to the tail of 
a queue datastructure to maintain the order of operations.
A simple compression algorithm is run over the queue each time
a new operation is added to perform on-the-fly compression for 
each task's operation queue.  Upon application termination, 
the record framework merges all task-level traces into a 
comprehensive trace (referred to as cross-node merging).

****************************************
2. Project layout
****************************************
##################
Wrapper generator:
##################
Umpire is a tool from Lawrence Livermore National Laboratory 
(LLNL) that instruments MPI applications with communication 
debugging code.  It can be used to instrument any application 
based on the MPI 1.2 specification (i.e. it is implementation
independent).  The wrapper generator was of great interest to 
us to make our framework implementation independent as well.
(Although it has currently been used with MPICH and openMPI only)

The wrapper generator uses the header files of an MPI 
implementation to create a code generating binary.  The 
code generator creates wrappers for MPI functions based
on the PMPI profiling layer.  A specification file is 
used to instruct the code generator on which functions
to instrument.  All other Umpire functionality has 
been striped out.

The dirctory, 'wrapper-engine', contains the code 
generator.  Minor edits are occasionally required for
bugs in the wrapper-engine so knowledge of its basic
layout is not a bad idea.  The engine is based on 
yacc & lex.  It reads in an MPI header file and 
extracts function prototypes to create wrappers.
The only file I've really had to work with was 
mpi_wrappers.c.  This file is where most of the 
code generation takes place.

######################
Trace instrumentation:
######################
Our record framework is implemented in the directory, 
'libsrc'.  In the file 'mpi-spec.umpi.extract', we 
specify how each MPI function should be instrumented.
Within the file, you can specify pre/post instrumentation 
in C.  The binary 'wrapper-engine.exe' (see discussion above) 
uses this input file to generate code which when compiled 
creates 'lib[glob|node|dump].a' in the 'lib' directory.  The library
performs all MPI functions as well as trace file generation.
The various libraries are compiled with different compression levels.
libdump.a just dumps flat traces per node. libnode.a only compresses
on node and outputs a trace file per node. libglob.a has inter-node
compression enabled and outputs a single trace file per run.

######
Tests:
######
There are a slew of tests that came w/ Umpire that are also
built in the 'tests' directory.  We didn't really use any 
of these for actual testing, but since they cover most 
MPI functions, they were useful in debugging potential
linking errors.

****************************************
3. Record source
****************************************
#######################
Task-level compression:
#######################
Each task initially collects its own unique operation queue.
Upon each communication call, MPI call and arguments are 
stored in a 'replay_op' datatype.  The 'replay_op' constitutes
the core data kept for each operation in the operation queue.

The operation queue itself, 'rsd_queue' is comprised of many 
'rsd_node' data structures.  Each 'rsd_node' has a 'replay_op', 
a stack trace signature, looping information, and pointers.
The stack trace signatures provide distinction between 
similiar MPI calls and aid in cross-node compression.  
Compression at the task level is achieved through loop 
detection and concise representation.  Lastly, the operation 
queue allows traversal in both directions, so this data type 
contains next and prev pointers.

Compression at the task level relies on representing 
MPI operations called in a loop concisely.  Each 
'rsd_node' has looping information stored in a 
data structure, 'prsd_stack'.  Each 'prsd_node' in the 
stack represents a loop (i.e. a stack of length 3 has 
information about a triply nested loop).  Nodes in the 
stack contain the number of loop iterations as well as
loop member identification.  Loop member identification 
is accomplished by noting which 'rsd_node' is the last
operation in the loop and noting how many loop 
members there are.

As each MPI operation gets called, an 'rsd_node' is 
created in 'mpi-spec.umpi.extract'.  The operation is
added to the tail of the operation queue (a 'rsd_queue').
Compression is attempted after each operation is appended
to the tail of the queue using 'compress_rsd'.  This 
function searches for consecutivly matching sequences of 
operations.  The search begins at the tail of the operation
queue and attempts to match two equivalent sequences.  
Upon a match, loop information ('prsd_stack') is encoded
into the first operation in the loop and the duplicate
sequence is elminated.

#################
Interoperability:
#################
The goal of the task-level framework is to create 
compressed operation queues of all MPI communication.
We can actually achieve far better compression at the 
task-level using bzip (or other structureless compression 
algorithms).  This results in an unscalable solution with 
job size so we use cross-node compression (which 
requires structured task-level compression).  In addition
to structural task-level compression, we needed to perform
additional measures to help the task-level framework
create compressed traces amiable to the cross-node 
framework's compression scheme.  These measures include
parameter lists and request offsets.

Parameter lists target stencil codes using point to point 
communication.  Since stencil codes generally perform 
point to point communication based on their rank, we noted
that the targets varied across tasks.  The commonality between
between the targets across tasks actually lay in the offset from
the task rank.  Parameter lists, 'params_queue', are 
encoded into the 'rsd_node' data structure.  During compression,
if 'compress_rsd' detects stencil communication, it is more concisely 
represented using a parameter list.  For example, given a 5-point
stencil in a 2D space, a task would perform 4 communication 
operations to their left, right, top, and bottom neighbors.
Rather than representing this string of operations in 4 
seperate 'rsd_node' data structures, we opted to maintain a 
list of offsets attached to a single 'rsd_node' data structure.

Request offsets are a special data structure used to deal with
the undeterministic nature of MPI_Request handles.  On an 
asynchronous call, an integer is generated to be used as an 
MPI_Request handle.  The generated integer does not necessarily 
coincide with a MPI_Request handle on another task although 
the stack signatures may match.  A global, static array of 
requests is kept to combat this problem.  Whenever an 
asynchronous call is made, its resultant MPI_Request handle 
is stored in the global array.  Upon lookup (MPI_Wait, MPI_Test,
etc.), the request handle's offset from the current position in 
the global array is recorded in place of the MPI_Request handle.
So rather than potentially differing integers for a parameter, 
we use offsets that will always match across tasks if the tasks
are performing the same communication functionality.

#######################
Cross-node compression:
#######################
Upon an application's termination (as signified by a call to 
MPI_Finalize), all the task-level operation queues are 
merged into a single comprehensive trace file.  Since many 
tasks perform the same operations, we are able to label
sets of operations with task ranks and remove duplicates.

The specification file, 'mpi-spec.umpi.extract' contains most
of the merging code in the instrumentation of MPI_Finalize.
Merges are performed on two operation queues at a time.  A balenced 
binary tree overlay controls the entire merging process.  Each 
task gets an operation queue from its left child, merges
the queue, then repeats the action for the right child.  With the 
operations queues of each child, a task may send its operation 
queue to its parent.  Because operation queues are comprised of linked 
lists, a set of transfer functions are used to flatten data structures 
in preparation.  Once the root of the tree is reached, the resultant 
operation queue is written to file.

##################
File descriptions:
##################
mpi-spec.umpi.extract:  Defines how 'wrapper-engine.exe' 
will instrument each function call.  All functions which
perform communication or change the MPI state machine are
instrumented.  Additionally, MPI_Init performs initialization
functionality and MPI_Finalize performs clean up and 
operation queue merger functionality.

opstruct.[h,c]:  Defines 'replay_op' data structure.  This
structure contains the core information about which MPI call
was made, function arguments, and meta data about function 
arguyments which are arrays.  Additionally, many of the 
macros to access arguments are defined here as well.

rsd_node.[h,c]:  Defines 'rsd_node' and 'rsd_queue' data 
structures.  The 'rsd_queue' is what contains a list of 
all operations performed during an applications run.  This
data structure is used to capture information at the 
task-level as well as in the cross-node framework.  The
queue is made up of 'rsd_node' data structures.  These 
contain MPI data and compression information.  The 
implementation of these contains many standard queue and 
linked list operations.  It also contains the compression 
algorithm 'compress_rsd' which performs task-level 
compression.  This function must be called every time 
a new operation is added to the queue.

stack_sig.[h,c]:  Stack signatures are concatenated strings 
seperated by the '_' character.  The strings are collected
by performing a stack walk.  In the record framework, 
signatures are collected upon each MPI call.  They are used 
to identify similar operations (for loop idenification).  A 
simple comparison of 'replay_op' data is not suffiecient for 
determining that two 'rsd_node' structures match.  The call 
and argument information may match but the call sites in the 
code may differ.  Since task-level compression is based on 
maintaining loop structure, stack signature differentiation
is necessary.

prsd_node.[h,c]:  Defines 'prsd_node' and 'prsd_stack' data
structures.  The 'prsd_stack' contains the loop information 
for an 'rsd_node'.  Each stack member, a 'prsd_node', represents
a loop level.  The 'prsd_node' data structure contains the 
number of iterations the loop is performed and loop 
member identification.  Identiciation of loop members uses 
a stack signature of the last operation in the loop and 
the total number of loop members.  The implementation 
contains many standard stack and linked list operations.

params_queue.[h,c]:  Defines 'params_node' and 'params_queue' data
structures.  The 'params_queue' contains a list of offsets stored in 
'params_node' structures.  A 'rsd_node' uses a 'params_queue' to 
represent point-to-point stencil communication.  Used in conjunction 
with 'prsd_stack', a parameter list denotes that a communication operation 
is performed on multiple targets.  Each target is determined by 
the task's MPI rank + the offset in the parameter list.  The implementation
contains many standard queue and linked list operations.  It also 
contains comparison functions to identify matching parameter lists.

req_handler.[h,c]:  Defines a set of functions which maintain 
the global array of request offsets.  When asynchronous communication
is performed, the associated MPI_Request handle is stored in the 
global array using 'add_offset_entry'.  Whenever an MPI_Request 
handle is queiried (MPI_Wait, MPI_Test, etc.), rather than storing
the undeterministic handle, 'lookup_offset' or 'lookup_offsetlist' 
(for multiple offset lookup) are used as the stored parameter.

radix_tree.[h,c]:  Defines a set of functions which determine 
a task's left and right children, and parent.  The functions 
perform bit manipulation of a task's MPI rank to find targets.
The resultant tree is a balenced binary tree.

params.[h,c]:  Defines a function which is used during the 
cross-node merger.  The function determines if all the parameters
of two operations match.

transfer.[h,c]:  Defines a set of functions which are used to 
marshall data for transfer during the cross-node merger.  All 
data structures use pointers to represent an operation queue.
In order to transfer an operation queue, all data is flattened
into a contigous address space.  Upon receipt of a flattened
operation queue, the transfer functions also enable a queue to 
be unmarshalled.

rank_recursive.[h,c]:  Defines a set of functions to manipulate 
an integer array.  The integer array represents a list of tasks
which participate in an operation referred to as a task participant
list.  During the cross-node merger, as operations are identified as 
matching, the task participant lists of the operations are merged and 
the duplicate operation is discarded.  This implementation uses
a recursive definition for task participant lists.

###############################
Histogram based trace recording
###############################

Trace recording can also be done using histograms for events
that do not compress properly. This can be used to achieve 
higher compression rate by losing small amount of accuracy. Users
can use the switch USE_HISTO_COMPRESS in libsrc/Makefile.libsrc
file to enable compression using histograms. Event compression will
be successful even if the function parameters do not match exactly.
These non-matching parameters will be recorded in histograms, which
provides more details than the crude averaging method. Even PRSD loop
information will be collected in histogram bins. Users can provide
an error percentage in the file common/inc/ScalarParam.h. If two 
non-matching values fall within the error percentage only then histogram
collection is done. Else compression will fail for that particular event.
This feature can be used solely on user's discretion to lose some 
accuracy and get very high compression benefits.

****************************************
4. Building
****************************************
See BUILD for instructions. Also see Makefile and libsrc/Makefile.libsrc
for additional options.

****************************************
5. Instrumenting applications
****************************************
To instrument an application, you must relink it so that 
libglob (or libnode/dump) appears before your MPI library.
Some runtime options can be set via environment variables.
  Additionally, 
you must place an input file 'record.in' in the directory of
your application.  The file must specify 4 lines: (1) output 
format, (2) compression window, (3) request offset buffer
size, and (4) trace file output.  The output format should 
always be rsd, ascii, or binary.  We only support replay of
the rsd traces.  The compression window specifies how far
back the task-level compression algorithm will search the queue.
Use -1 if there should be no window.  The request offset buffer
size specifies the size of the global array.  If the array is too
small, an error is displayed.  The trace file output specifies where
to write the trace.
