ParaMeter
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.
Contents
What is ParaMeter For?
How does ParaMeter Work?
The BDD Trace Format
DINxRDY Plots
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.
DINxRDY Plots
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
