Program analysis can be fast and fun!

The ParaMeter tool was developed to help locate and extract parallelism from sequential applications.  The ParaMeter tool can also perform analysis on applications that already multi-threaded, as long as the application can be dynamically traced.


What is ParaMeter For?
How does ParaMeter Work?
The BDD Trace Format
Does this thing actually work?

What is ParaMeter For?
ParaMeter helps programmers find parallel threads that already exist within their sequential applications.  There can be any number of reasons why a programmer would want to add parallel threads to an existing sequential application.  Most notably is performance.

While computing performance for most sequential applications has made slight gains in the last decade, the gains are...well...slight.  Single core systems have gone from a flood of performance gains from 1970 to 1990 to more of a trickle.  However, CPU manufacturers are adding more and more cores to a single compute system.  This sounds great, but in the increase in performance is no longer invisible to the software architect; if a programmer wants a faster application, he/she now has to work for it.

This sounds very lame.  I am not going to lie to you - it can be.  Writing parallel applications can be a pain.  Even expert code ninjas can easily produce a crazy, non-deterministic, race condition in a multi-threaded application.  The approach ParaMeter takes is simple: first, get the sequential program correct, then add parallel threads when and where they are needed.

How Does ParaMeter Work?
ParaMeter contains analysis features that were once very time consuming to perform with large dynamic traces.  First, it can render DINxRDY time plots fast enough for full interactivity.  It can also perform program data dependence slicing and rapidly correlate DINs to source code.  

What is the secret ingredient?  How can ParaMeter can rapidly analyze large trace data sets?  Traces are first converted into reduced, ordered, binary decision diagrams (BDDs).  BDDs can allow for both rapid global analysis as well as good compression.

The BDD Trace Format
ParaMeter uses a special BDD variable order and analysis algorithms to enable rapid visualization and good compression of trace data.

sample DINxRDY plot

The DIN in the DINxRDY plot is the Dynamic Instruction Number.  This is simply a unique number assigned to each instruction that your program executes at run time.  Since the DIN of the first instruction is one, the second instruction is two, and so on, the DIN also identifies the location of the instruction in the trace.

The RDY in the DINxRDY plot is the Ready time of the instruction.  This is the earliest time that an instruction can be scheduled to execute given pretty close to optimal constraints.  These constraints include infinite execution width, perfect branch prediction, no stack register dependencies, etc.  This allows the DINxRDY plot to show as few false dependencies as possible.

Does ParaMeter Work?
You bet!  Check out the case study done with the 175.vpr benchmark here.

Home - ParaMeter - 175.vpr Case Study - ParaFAQ