Stride - Stream Identification During Execution
-----------------------------------------------

Stride is a tool to dynamically instrument load/stores in binary to
obtain information about memory usage patterns in the data reference
stream of an application. The tool uses Dyninst to instrument load/stores
and function entry/exits with trace calls. Once the application is executed
the tool attaches to the binary (using Unix IPC) and dynamically analyzes
the trace. It employs an online algorithm to detect linear memory access
patterns. Instrumentation can be selectively applied and disabled during 
execution. At the conclusion of the run, detailed function-level stream
statistics are calculated.

Stride should work without modification on parallel codes written using
MPI, but no aggregation of statistics is performed across tasks. The tool
should work with multithreaded codes in a seamless manner once a MT-safe
release of Dyninst becomes available. In addition to Dyninst, Stride uses
PAPI to instrument the binary with portable hardware performance 
monitoring calls.  

Installation:
  1) Obtain and install PAPI (2.0+) and Dyninst (3.0).
     PAPI can be obtained from: http://icl.cs.utk.edu/projects/papi/
     Dyninst can be obtained from: http://www.dyninst.org
  2) Obtain the Stride source from http://www.cs.utah.edu/~tushar/stride/stride_2_0.tar.gz
  3) Untar the source
  4) cd stride 
  5) Define the environment variables: DYNINST, DYNINST_RT_LIB, PAPI_INC and PAPI_LIB
  6) make 
  7) make install

  This will install binaries in 'bin' and an instrumentation shared library in 'lib'.
In addition, some useful tools, such as a binary probe, are installed in 'bin'.

Running the tool:
  Two modules are executed in tandem to make Stride obtain stream information:
  dsd -- This is started in the background, and will connect to the application
         once it (the application) starts execution.
  mutator -- This instruments functions chosen by the user in the applicaition.
             It also loads in a shared library -- libins.a -- in the application's
             address space.

Examples:
--------

1. To probe and find out the modules in a binary
   %  binprobe gzip
List of modules found in binary:
crt0main.s  __threads_init.c  gzip.c  zip.c  deflate.c  trees.c  unpack.c  bits.c  unzip.c  inflate.c  util.c  lzw.c  unlzw.c  unlzh.c  getopt.c  libgcc2.c  strcat.s  strcpy.s  strcmp.s  strncpy.s  moveeq.s  Global_Linkage  libcrypt.a  libc.a  libC.a  libC.a  libC.a  libC.a  libdyninstAPI_RT.so.1


2. To obtain a list of functions in the module
     % binprobe gzip unlzw.c
     Function list (obtained from image, after removing forbidden functions): unlzw

3. To obtain regularity information for all functions in a module 'unlzw.c', where
   libins.a lies in ~/lib:
     % dsd &
     % mutator -p './gzip datafile' -mod unlzw.c -dso ~/lib/libins.a

4. To instrument all the functions in all the modules
     % dsd &
     % mutator -p './gzip datafile' -dso ~/lib/libins.a

5. To instrument a function 'deflate':
     % dsd &
     % mutator -p './gzip datafile' -f deflate -dso ~/lib/libins.a

6. To limit sampling to two samples of a function 'fill_window', when all
   the functions in module deflate.c are instrumented:
   % dsd -n_samp 3 -reqd fill_window &
   % mutator -p './gzip datafile' -mod deflate.c -dso ~/lib/libins.a   

7. To sample two functions fill_window and deflate unti their results converge
   to a less than 2% change between successive iterations:
   % dsd -stable 0.02 &
   % mutator -p './gzip datafile' -f fill_window deflate -dso ~/lib/libins.a

8. To peridically sample peridically (ON for 5 sec. and OFF for 45 sec)
   all the functions in the modules deflate.c util.c
   % dsd -t_samp 5 45 &
   % mutator -p './gzip datafile' -mod deflate.c util.c -dso ~/lib/libins.a

9. To run the mutator for performance instrumentation profiling:
   % setenv PAPI_EVENT_0 0x80000000
   % setenv PAPI_EVENT_1 0x80000022
   % dsd &
   % mutator -p './gzip datafile' -noldst -dso ~/lib/libins.a

   To find out the PAPI event numbers, use the 'avail' command in the
   PAPI distribution.


For command line options:
 dsd --h
 mutator --h


Acknowledgements:
----------------
Bronis de Supinski (bronis@llnl.gov) and Sally A. McKee (sam@csl.cornell.edu) 
have taken a huge interest in the development of StrIDE and my thesis :).
Thanks are also due to the Dyninst team (Bryan Buck, bbuck@cs.umd.edu) 
for their help with instrumentation issues.

Bugs and information:
--------------------
Tushar Mohan: tushar@cs.utah.edu

The code is available for any use and modification, with no claims
on usability and fitness. Use at your own risk.



Last Update: 04/24/2003