\input texinfo  @c -*-texinfo-*-

@c see README for how to edit this file
@c DO NOT EDIT gxpman.tex, but gxpman_src.tex
@c
@c (texinfo-insert-node-lines) will add @node to section/chapter
@c C-c C-u C-e will complete their names.
@c 
@c C-c C-u C-e  (texinfo-every-node-update) 
@c    ---> complete node names and links
@c C-c C-u C-a  (texinfo-all-menus-update)  
@c    ---> update menu
@c C-c C-u m    (texinfo-master-menu) 
@c    ---> make master menu

@setfilename massivethreads.info
@settitle MassiveThreads User's Guide
@iftex
@setchapternewpage on
@end iftex
@comment %**end of header


@noindent Copyright 2010-2014 Jun Nakashima (Read COPYRIGHT for detailed information.)

@noindent Copyright 2010-2014 Kenjiro Taura (Read COPYRIGHT for detailed information.)

@titlepage
@title MassiveThreads User's Guide
@subtitle September 2014
@author Kenjiro Taura
@author University of Tokyo
@author 7-3-1 Hongo Bunkyo-ku Tokyo, 113-0033 Japan
@page
@vskip 0pt plus 1filll
Copyright @copyright{} 2010-2014 Jun Nakashima
Copyright @copyright{} 2010-2014 Kenjiro Taura
@end titlepage

@contents

@node Top, MassiveThreads Library, (dir), (dir)

@chapter Getting Started

@menu
* MassiveThreads Library::
* Higher-Level Interfaces::
* DAG Recorder::

@detailmenu
 --- The Detailed Node Listing ---

Higher-Level Interfaces

* Higher Level Interfaces Overview::
* TBB-Compatible Interface::
* Task Parallel Switcher::

TBB-Compatible Interface

* TBB-Compatible Interface Overview::
* Installing TBB-Compatible Interface::
* Writing Programs Using TBB-Compatible Interface::
* Choosing Schedulers Beneath the TBB-Compatible Interface::

DAG Recorder

* DAG Recorder Overview ::
* Installing DAG Recorder::
* Writing Programs That Use DAG Recorder::
* Running Your Programs with DAG Recorder::
* dag2any DAG to any data converter::
* Viewing Recorded Data::
* Querying Recorded Data::

Writing Programs That Use DAG Recorder

* Common Basics::
* Using DAG Recorder with TBB-Compatible Interface::
* Using DAG Recorder with OpenMP::
* Using DAG Recorder with Cilk and CilkPlus::
* Using DAG Recorder with tpswitch.h::

Running Your Programs with DAG Recorder

* Basics of Running Your Programs with DAG Recorder::
* Controlling the Behavior of DAG Recorder::

Viewing Recorded Data

* Viewing Parallelism Profile with gnuplot ::
* Visualizing the DAG via graphviz::
* Understanding Stat File::
* Viewing DAG file with drview::

@end detailmenu
@end menu

@node MassiveThreads Library, Higher-Level Interfaces, Top, Top
@chapter MassiveThreads Library

TODO: write about the library API itself.

@node Higher-Level Interfaces, DAG Recorder, MassiveThreads Library, Top
@chapter Higher-Level Interfaces

@menu
* Higher Level Interfaces Overview::
* TBB-Compatible Interface::
* Task Parallel Switcher::
@end menu

@node Higher Level Interfaces Overview, TBB-Compatible Interface, Higher-Level Interfaces, Higher-Level Interfaces
@section Higher Level Interfaces Overview

MassiveThreads API described so far is still low level and bit
burdensome as a parallel programming interface.  MassiveThreads also
provides higher level APIs, easier and more convenient APIs for
programmers.

One is what we call @i{TBB-compatible interface}, that provides a subset
of functions of Intel Threading Building Block.  It does not only
provide TBB-compatible interface, but also allows you to switch between
various lightweight thread libraries under the same TBB-compatible
interface.  Currently supported libraries include MassiveThreads,
Qthreads, Nanos++, and what we call a dummy scheduler.  The last one
elides task parallel primitives.

The other interface is what we call a @i{task parallel switcher}, with
which you can write a single program running on top of even wider set of
task parallel systems including OpenMP, Cilk, and TBB.

Besides providing a uniform API on various runtime systems, they serve
another important purpose, which is to allow you to trace your task
parallel programs with DAG Recorder, a tracing tool described later in
this manual. @xref{DAG Recorder}. By programming in these APIs, rather
than in the native API of the respective runtime system, your are free
from the burden of manually instrumenting your programs for tracing.  To
this end, we also provide headers to facilitate instrumentation of
OpenMP and Cilk.  They do not serve any purpose of making OpenMP and
Cilk more convenient nor more uniform; they simply make instrumenting
OpenMP and Cilk easier.

Here is the summary of choices of APIs and runtime systems.

@multitable @columnfractions .25 .2 .25 .30
@headitem API            @tab Runtime System  @tab Header file      @tab flags
@item     TBB-compatible @tab None (dummy)   @tab @code{mtbb/task_group.h} @tab @code{-DTO_SERIAL}
@item     TBB-compatible @tab Intel TBB      @tab @code{mtbb/task_group.h} @tab @code{-DTO_TBB -ltbb}
@item     TBB-compatible @tab MassiveThreads @tab @code{mtbb/task_group.h} @tab @code{-lmyth-native}
@item     TBB-compatible @tab Qthreads       @tab @code{mtbb/task_group.h} @tab @code{-DTO_QTHREAD -lqthread}
@item     TBB-compatible @tab Nanos++        @tab @code{mtbb/task_group.h} @tab @code{-DTO_NANOX -lnanox-c}
@item     OpenMP-like    @tab OpenMP @tab @code{tpswitch/omp_dr.h}          @tab
@item     Cilk-like      @tab Cilk   @tab @code{tpswitch/cilk_dr.h}         @tab
@item     Cilkplus-like  @tab Cilkplus   @tab @code{tpswitch/cilk_dr.h}         @tab
@item     Task Parallel Switcher @tab None (dummy) @tab @code{tpswitch/tpswitch.h} @tab @code{-DTO_SERIAL}
@item     Task Parallel Switcher @tab Intel TBB @tab @code{tpswitch/tpswitch.h} @tab @code{ -DTO_TBB -ltbb}
@item     Task Parallel Switcher @tab MassiveThreads @tab @code{tpswitch/tpswitch.h} @tab @code{-DTO_MTHREAD_NATIVE -lmyth-native}
@item     Task Parallel Switcher @tab Qthreads @tab @code{tpswitch/tpswitch.h} @tab @code{-DTO_QTHREAD -lqthread}
@item     Task Parallel Switcher @tab Nanos++ @tab @code{tpswitch/tpswitch.h} @tab @code{-DTO_NANOX -lnanox-c}
@item     Task Parallel Switcher @tab OpenMP @tab @code{tpswitch/tpswitch.h} @tab @code{-DTO_OMP}
@item     Task Parallel Switcher @tab Cilk @tab @code{tpswitch/tpswitch.h} @tab @code{-DTO_CILK}
@item     Task Parallel Switcher @tab Cilkplus @tab @code{tpswitch/tpswitch.h} @tab @code{-DTO_CILKPLUS}
@end multitable

@node TBB-Compatible Interface, Task Parallel Switcher, Higher Level Interfaces Overview, Higher-Level Interfaces
@section TBB-Compatible Interface
@menu
* TBB-Compatible Interface Overview::
* Installing TBB-Compatible Interface::
* Writing Programs Using TBB-Compatible Interface::
* Choosing Schedulers Beneath the TBB-Compatible Interface::
@end menu

@node TBB-Compatible Interface Overview, Installing TBB-Compatible Interface, TBB-Compatible Interface, TBB-Compatible Interface
@subsection TBB-Compatible Interface Overview

As of writing, it supports @file{task_group} class, @file{parallel_for}
template function, and @file{parallel_reduce} template function.  See
respective sections of the TBB reference manual for these classes.
We will see examples using @file{task_group} class below.

@node Installing TBB-Compatible Interface, Writing Programs Using TBB-Compatible Interface, TBB-Compatible Interface Overview, TBB-Compatible Interface
@subsection Installing TBB-Compatible Interface

TBB-compatible interface is distributed as a part of MassiveThreads, so
you do not do anything particular to install it besides the installation
procedure of MassiveThreads.

After installation, the files constituting the API are installed as:
@itemize
@item @i{PREFIX}@file{/include/mtbb/task_group.h}
@item @i{PREFIX}@file{/include/mtbb/parallel_for.h}
@item @i{PREFIX}@file{/include/mtbb/parallel_reduce.h}
@end itemize
Note that they are under @file{mtbb} directory, instead of @file{tbb}
directory as in the original TBB.

@node Writing Programs Using TBB-Compatible Interface, Choosing Schedulers Beneath the TBB-Compatible Interface, Installing TBB-Compatible Interface, TBB-Compatible Interface
@subsection Writing Programs Using TBB-Compatible Interface

Using TBB-Compatible interface is a lot like using the regular TBB.  You
include @file{mtbb/@{task_group,parallel_for,parallel_reduce@}.h}
instead of @file{tbb/@{task_group,parallel_for,parallel_reduce@}.h}, and
use namespace @file{mtbb} instead of namespace @file{tbb}.

Here is a simple example (@file{bin_mtbb.cc}).
@example
@verbatiminclude examples/bin_mtbb.cc
@end example

I hope you agree that changes are minimal.  The original TBB version
would look like this (only differences are the file name of the include
file and namespace prefix of the @file{task_group} class).

@example
@verbatiminclude examples/bin_tbb.cc
@end example

Without DAG Recorder, you would compile @file{bin_mtbb.cc} as follows.
@example
@verbatim
$ g++ --std=c++0x bin_mtbb.cc -lmyth-native
@end verbatim
@end example

Remark 1: @file{--std=c++0x} is given to use C++ lambda expression at
line 8, proposed in C++0x and standardized in C++11.  GCC supports it
since 4.5, when one of the following command line options
@file{--std=c++0x, --std=gnu0x, --std=c++11}, or @file{--std=gnu11} is
supplied.  If your GCC does not support it, you could pass any callable
object (any object supporting @file{operator()}).  We use lambda
expressions for brevity in this manual.

Remark 2: Depending on your configuration, you might need to add
@file{-I, -L,} and @file{-Wl,-R} options to the command line.  For
example, if you install MassiveThreads under @file{/home/you/local} (i.e.,
gave @file{/home/you/local} to @file{--prefix} of the @file{configure}
command), the command line will be:
@example
@verbatim
$ g++ --std=c++0x -I/home/you/local/include -L/home/you/local/lib -Wl,-R/home/you/local/lib bin_mtbb.cc -lmyth-native
@end verbatim
@end example

@node Choosing Schedulers Beneath the TBB-Compatible Interface,  , Writing Programs Using TBB-Compatible Interface, TBB-Compatible Interface
@subsection Choosing Schedulers Beneath the TBB-Compatible Interface

With the above command, you get a program that uses TBB-compatible API
with MassiveThreads as the underlying scheduler.  Roughly speaking,
task_group's @file{run} method will create a thread of MassiveThreads
library via @file{myth_create} and wait method will wait for all threads
associated with the task group object to finish via @file{myth_join}.

The @file{mtbb/task_group.h} file allows you to use threading libraries other than MassiveThreads, by defining a compile time flag @file{TO_XXX}.  Currently, you can choose from the original Intel TBB, MassiveThreads, Qthreads, Nanos++, or None.  Flags you should give to them are listed below.

@multitable @columnfractions .5 .5
@headitem Runtime system @tab Flag 
@item Intel TBB      @tab @file{-DTO_TBB}
@item MassiveThreads @tab @file{-DTO_MTHREAD_NATIVE} (or nothing)
@item Qthreads       @tab @file{-DTO_QTHREAD}
@item Nanos++        @tab @file{-DTO_NANOX}
@item None           @tab @file{-DTO_SERIAL}
@end multitable

The last one, None, elides all tasking primitives; @file{run(@i{c})} executes @file{@i{c}()} serially and @file{wait()} is a noop.  

In order to use @file{mtbb/task_group.h} with the scheduler you chose, you of course need to install the respective scheduler and link your program with it.  

@node Task Parallel Switcher,  , TBB-Compatible Interface, Higher-Level Interfaces
@section  Task Parallel Switcher

TBB-compatible interface unifies various schedulers under the same,
TBB-compatible interface.  Task parallel switcher goes one step further 
by defining an API that can be mapped onto OpenMP and Cilk as well.

OpenMP, Cilk, and TBB's task_group interfaces are all conceptually very
similar; they all define ways to create tasks and wait for outstanding
tasks to finish, after all.

Yet there are idiosyncrasies that make defining truly uniform APIs
difficult.  

TODO: detail the following

@itemize @bullet
@item mk_task_group
@item create_taskc
@item create_task0
@item create_task1
@item create_task2
@item create_taskA
@item call_task
@item call_taskc
@item create_task_and_wait
@item wait_tasks
@end itemize

@node DAG Recorder,  , Higher-Level Interfaces, Top
@chapter DAG Recorder

@menu
* DAG Recorder Overview ::
* Installing DAG Recorder::
* Writing Programs That Use DAG Recorder::
* Running Your Programs with DAG Recorder::
* dag2any DAG to any data converter::
* Viewing Recorded Data::
* Querying Recorded Data::
@end menu

@node DAG Recorder Overview , Installing DAG Recorder, DAG Recorder, DAG Recorder
@section DAG Recorder Overview 

DAG Recorder is a tracing tool to analyze execution of task parallel
programs.  It records all relevant events in an execution of the
program, such as task start, task creation, and task synchronization and
stores them in a manner that is able to reconstruct the computational
DAG of the execution.

@node Installing DAG Recorder, Writing Programs That Use DAG Recorder, DAG Recorder Overview , DAG Recorder
@section Installing DAG Recorder

DAG Recorder is distributed as a part of MassiveThreads, so installing
MassiveThreads automatically installs DAG Recorder too.  DAG Recorder
does not internally depend on MassiveThreads in any way, however; you
can, for example, use DAG Recorder to analyze TBB or OpenMP programs.  

After installation, files directly visible to the user are the following.
@itemize @bullet
@item @i{PREFIX}@file{/lib/libdr.so} --- library
@item @i{PREFIX}@file{/include/dag_recorder.h} --- include file
@end itemize
where PREFIX is the path you specified with @file{--prefix} at
@file{configure} command line.  

In most cases, you do not have to directly include
@file{dag_recorder.h}.  TBB-compatible interface or aforementioned
wrappers (@file{omp_dr.h} and @file{cilk_dr.h}) will automatically
include it.

@node Writing Programs That Use DAG Recorder, Running Your Programs with DAG Recorder, Installing DAG Recorder, DAG Recorder
@section Writing Programs That Use DAG Recorder
@menu
* Common Basics::
* Using DAG Recorder with TBB-Compatible Interface::
* Using DAG Recorder with OpenMP::
* Using DAG Recorder with Cilk and CilkPlus::
* Using DAG Recorder with tpswitch.h::
@end menu

@node Common Basics, Using DAG Recorder with TBB-Compatible Interface, Writing Programs That Use DAG Recorder, Writing Programs That Use DAG Recorder
@subsection Common Basics

Currently, DAG Recorder supports the following task parallel APIs.

@itemize @bullet
@item TBB or the TBB-compatible interface @xref{Writing Programs Using TBB-Compatible Interface}.
@item OpenMP. #pragma task and #pragma taskwait
@item Cilk and Cilkplus. spawn and sync
@end itemize

Making your programs ready for DAG Recorder involves replacing original
task parallel primitives with equivalent, instrumented versions.  You
also need to specify where to start/stop instrumentation and dump the
result.  We provide header files to make the instrumentation nearly
automatic or at least quite mechanical.  What you exactly need to do
depends on the programming model you chose and are detailed in the
following subsections.

@node Using DAG Recorder with TBB-Compatible Interface, Using DAG Recorder with OpenMP, Common Basics, Writing Programs That Use DAG Recorder
@subsection Using DAG Recorder with TBB-Compatible Interface

If you are using TBB-Compatible Interface (@pxref{Writing Programs Using TBB-Compatible Interface}), the instrumentation is most straightforward and least intrusive.  Let's say you have a program including @file{mtbb/task_group.h} such as this.
@example
@verbatiminclude examples/bin_mtbb.cc
@end example

Instrumentation is turned on simply by giving @code{-DDAG_RECORDER=2} at the command line.  What else you need to do is to insert calls to @code{dr_start, dr_stop,} and @code{dr_dump} at appropriate places like this  (@file{bin_mtbb_dr.cc}).
@example
@verbatiminclude examples/bin_mtbb_dr.cc
@end example

As you will see already, you should insert:
@itemize @bullet
@item @code{dr_start(0)} at the point you want to start recording,
@item @code{dr_stop()} at the point you want to stop recording, and
@item @code{dr_dump()} at the point you want to dump the result.
@end itemize

@code{dr_start} takes a pointer, which may be zero, to @code{dr_options} data structure as the argument.  
@ref{Controlling the Behavior of DAG Recorder} for options you can specify.

Here are the command lines to compile this program, with and without DAG Recorder
@itemize @bullet
@item with DAG Recorder:
@example
@verbatim
g++ --std=c++0x bin_mtbb_dr.cc -DDAG_RECORDER=2 -ldr -lmyth-native 
@end verbatim
@end example
@item without DAG Recorder:
@example
@verbatim
g++ --std=c++0x bin_mtbb_dr.cc -lmyth-native
@end verbatim
@end example
@end itemize

The reason why you set DAG_RECORDER to ``2'' is historical.  There was a version one, which have become obsolete by now.

You could switch to other schedulers in the way described already. @xref{Choosing Schedulers Beneath the TBB-Compatible Interface}.  For example, you will get the original TBB scheduler with the following command line.
@example
@verbatim
g++ --std=c++0x bin_mtbb_dr.cc -DTO_TBB -DDAG_RECORDER=2 -ldr -ltbb 
@end verbatim
@end example

@node Using DAG Recorder with OpenMP, Using DAG Recorder with Cilk and CilkPlus, Using DAG Recorder with TBB-Compatible Interface, Writing Programs That Use DAG Recorder
@subsection Using DAG Recorder with OpenMP

OpenMP uses directives (@code{pragma omp task} and @code{pragma omp
taskwait}) to express task parallel programs.  It almost always uses
@code{pragma omp parallel} and @code{pragma omp single} (or @code{pragma
omp master}) to enter a task parallel section.  Here is an equivalent
program to our example, written in the regular OpenMP.

@example
@verbatiminclude examples/bin_omp.cc
@end example

We need to instrument these pragmas, for which we defined equivalent
@i{macros} (not pragmas) in a header file @file{tpswitch/omp_dr.h}.
This is not as straightforward as we hope, but we do not know any good
mechanism to introduce a new pragma or redefine existing pragmas.

@file{tpswitch/omp_dr.h} defines the following macros.

@itemize @bullet
@item @code{pragma_omp_task(@i{clauses, statement})}
@item @code{pragma_omp_taskwait}
@item @code{pragma_omp_parallel_single(@i{clauses, statement})}
@end itemize

Without DAG Recorder, they are expanded into equivalent OpenMP pragmas
in an obvious manner:

@itemize @bullet
@item pragma_omp_task(@i{clauses}, @i{statement}) =
@example
#pragma omp task @i{clauses}
  @i{statement}
@end example
@item pragma_omp_taskwait 
@example
#pragma omp taskwait
@end example
@item pragma_omp_parallel_single(@i{clauses}, @i{statement})
@example
#pragma omp parallel @i{clauses}
#pragma omp single
@{
  @i{statement}
@}
@end example
@end itemize

So, here is DAG Recorder-ready version of the above program.

@example
@verbatiminclude examples/bin_omp_dr.cc
@end example

This source code can be compiled with and without DAG Recorder.

@itemize @bullet
@item Without DAG Recorder:
@example
g++ -fopenmp bin_omp_dr.cc 
@end example

@item With DAG Recorder:
@example
g++ -fopenmp -DDAG_RECORDER=2 bin_omp_dr.cc -ldr
@end example
@end itemize

@node Using DAG Recorder with Cilk and CilkPlus, Using DAG Recorder with tpswitch.h, Using DAG Recorder with OpenMP, Writing Programs That Use DAG Recorder
@subsection Using DAG Recorder with Cilk and CilkPlus

There are two versions of Cilk; the original MIT Cilk and CilkPlus.
The former is implemented as a source to source translator (cilkc) and it is a strictly C extension (C++ not supported).
The latter is natively supported by Intel C++ Compiler and GCC version $\geq$ 4.9.  
It supports both C and C++ for writing serial parts.
DAG Recorder supports both Cilk and CilkPlus.
Hereafter, when we say Cilk, it means the original MIT Cilk version.

CilkPlus uses directives @code{_Cilk_spawn} and @code{_Cilk_sync} statements.
Here is our example in CilkPlus.

@example
@verbatiminclude examples/bin_cilkplus_raw.c
@end example

Alternatively you can include @code{<cilk/cilk.h>} and use more human friendly @code{cilk_spawn} and @code{cilk_sync} keywords.

@example
@verbatiminclude examples/bin_cilkplus.c
@end example

Cilk uses directives @code{spawn} and @code{sync} statements to create and synchronize tasks.
Here is our example in Cilk.

@example
@verbatiminclude examples/bin_cilk.cilk
@end example

There is a subtle but important difference between Cilk and CilkPlus.
In Cilk, a function that spawns a task needs to be explicitly marked as
a @i{cilk procedure} by the @code{cilk} keyword at function declaration;
and, once a procedure is marked as a cilk procedure, it cannot be called
by a regular function call syntax; @i{it must always be spawned.}  That is,
in our example, the following is prohibited.
@example
int x = bin(n);
@end example

It must instead be written as
@example
int x;
x = spawn bin(n);
sync;
@end example
As a result, the enclosing function must also be marked as a cilk procedure.


Whether you use Cilk or CilkPlus, modifications necessary to make these
programs ready are summarized as follows.

@enumerate
@item include @file{tpswitch/cilk_dr.cilkh} (Cilk) or @file{tpswitch/cilkplus_dr.h} (CilkPlus)
@item enclose all @code{spawn, cilk_spawn,} and @code{_Cilk_spawn} statements with @code{spawn_(...)} macro.  e.g.,
@example
y = cilk_spawn f(x);
@end example
should be rewritten to:
@example
spawn_(y = cilk_spawn f(x));
@end example
@item replace all @code{sync} and @code{cilk_sync} statements with @code{sync_} and @code{cilk_sync_}, respectively.

@item any function that spawns a task needs to begin with @code{cilk_begin}.  This is to indicate the beginning of a task.  If you forget this, a compilation error should result, complaining ``no such variable __cilk_begin__'';

@item replace return statements with either @code{cilk_return(@i{val})} or @code{cilk_void_return}, depending on whether the return statement returns a value.  This is to indicate the end of a task.  

      (TODO : wish to fix this) If you forget this, a compilation
      succeeds, but DAG Recorder fails.

@item (TODO : get rid of this restriction) As of writing, if you insert @code{cilk_begin}
      into a function, that function always needs to be spawned. That is,
      such a function cannot be called by a normal function call syntax.  
      This is prohibited in MIT Cilk
      anyways and flagged as a compilation error.  It is on you when
      you use CilkPlus, which allows task-spawning functions to be
      called serially without spawn keywords.  If you forget this, there
      are no compilation errors and DAG Recorder will be confused.
@end enumerate

Here is the modified CilkPlus program.

@example
@verbatiminclude examples/bin_cilkplus_dr.c
@end example

And here is Cilk version.

@example
@verbatiminclude examples/bin_cilkplus.c
@end example

This source code can be compiled with and without DAG Recorder.

@itemize @bullet
@item CilkPlus, without DAG Recorder:
@example
g++ -fcilkplus bin_cilkplus_dr.c
@end example

@item CilkPlus, with DAG Recorder:
@example
g++ -fcilkplus -DDAG_RECORDER=2 bin_cilkplus_dr.c -ldr
@end example

@item Cilk, without DAG Recorder:
@example
cilkc bin_cilk_dr.cilk
@end example

@item Cilk, with DAG Recorder:
@example
cilkc -DDAG_RECORDER=2 bin_cilk_dr.cilk -ldr
@end example
@end itemize

Instrumeting Cilk or CilkPlus programs is admittedly more burdensome
than instrumenting OpenMP or TBB.  The main reason for this is that
Cilk's @code{spawn} statement and CilkPlus's @code{cilk_spawn} 
statement create a task
that executes @i{the body of a procedure}, rather than an entire
procedure call statement, so we need to mark the beginning of the called
procedure as the beginning of the task.  That's why you need to insert
@code{cilk_begin}.  The difference between the two is subtle, but
consider the following example.

@example
spawn f(g(x));
@end example

In this Cilk code, evaluation of @code{g(x)} is @i{not} performed by the
spawned task, so there is no way to mark the beginning of the task by
tweaking macros that receive the entire procedure call statement.

In contrast, a similar TBB code:
@example
@verbatim
tg.run([=] { f(g(x)); });
@end verbatim
@end example
spawns a task that performs @code{f(g(x))} entirely.  
To make matters even simpler, the task spawning primitive
is just another method rather than a builtin syntax, 
which we can transparently instrument by having another 
class that implements @code{run} method.



@node Using DAG Recorder with tpswitch.h,  , Using DAG Recorder with Cilk and CilkPlus, Writing Programs That Use DAG Recorder
@subsection Using DAG Recorder with tpswitch.h

Just give @file{-DDAG_RECORDER=2} 
and respective linker options (e.g., -lmyth-native -ldr -lpthread)
to the command line.

TODO: more detailed and reader-friendly description.

@node Running Your Programs with DAG Recorder, dag2any DAG to any data converter, Writing Programs That Use DAG Recorder, DAG Recorder
@section Running Your Programs with DAG Recorder

@menu
* Basics of Running Your Programs with DAG Recorder::
* Controlling the Behavior of DAG Recorder::
@end menu

@node Basics of Running Your Programs with DAG Recorder, Controlling the Behavior of DAG Recorder, Running Your Programs with DAG Recorder, Running Your Programs with DAG Recorder
@subsection Basics of Running Your Programs with DAG Recorder

Once you obtained an executable compiled and linked with DAG Recorder, you can run it just normally.  

@example 
@verbatim
$ ./bin_mtbb_dr 20
bin(20) = 1048576
@end verbatim
@end example

You will find the following three files generated under the current directory.
@itemize @bullet
@item @file{00dr.dag} --- The DAG file. This is the primary file generated by DAG Recorder, from which other files are derived
@item @file{00dr.gpl} --- The parallelism file.  This is a file showing the actual and available parallelism, in a gnuplot format. 
@item @file{00dr.stat} --- The summary stat file.  This is a text file showing, among others, the number of tasks, total work time (time spent in the application code), critical path, the number of steals, etc.  The contents of this file will be explained later.
@end itemize

Run this program with setting environment variable @code{DR=0}, and you
can run the program with DAG Recorder turned off.

@example 
@verbatim
$ DR=0 ./bin_mtbb_dr 20
bin(20) = 1048576
@end verbatim
@end example

It still imposes a small overhead (essentially, looking up a global
variable + branch) for each tasking primitive.  We believe this overhead
is rarely an issue, but if you want to completely eliminate this
overhead, compile the program without @code{DAG_RECORDER=2}.

@node Controlling the Behavior of DAG Recorder,  , Basics of Running Your Programs with DAG Recorder, Running Your Programs with DAG Recorder
@subsection Controlling the Behavior of DAG Recorder

The behavior of DAG Recorder can be controlled either from within the
program or by environment variables; you can pass a pointer to
@code{dr_options} structure to @code{dr_start}, which has been 0 in the
examples we have shown so far.  If the argument to @code{dr_start} is
null (zero), options can be set via environment variables.  We will
illustrate how they work.

First about environment variables.  Run the program with setting the
environment variable @code{DR_VERBOSE} to @code{1}, and you will see the
list of environment variables and their values printed by
@code{dr_start}.  You will also see messages about files generated by
@code{dr_dump}.

@example 
@verbatim
$ DR_VERBOSE=1 ./bin_mtbb_dr 10
DAG Recorder Options:
dag_file_prefix (DAG_RECORDER_DAG_FILE_PREFIX,DR_PREFIX) : 00dr
dag_file_yes (DAG_RECORDER_DAG_FILE,DR_DAG) : 1
stat_file_yes (DAG_RECORDER_STAT_FILE,DR_STAT) : 1
gpl_file_yes (DAG_RECORDER_GPL_FILE,DR_GPL) : 1
dot_file_yes (DAG_RECORDER_DOT_FILE,DR_DOT) : 0
text_file_yes (DAG_RECORDER_TEXT_FILE,DR_TEXT) : 0
gpl_sz (DAG_RECORDER_GPL_SIZE,DR_GPL_SZ) : 4000
text_file_sep (DAG_RECORDER_TEXT_FILE_SEP,DR_TEXT_SEP) : |
dbg_level (DAG_RECORDER_DBG_LEVEL,DR_DBG) : 0
verbose_level (DAG_RECORDER_VERBOSE_LEVEL,DR_VERBOSE) : 1
chk_level (DAG_RECORDER_CHK_LEVEL,DR_CHK) : 0
uncollapse_min (DAG_RECORDER_UNCOLLAPSE_MIN,DR_UNCOLLAPSE_MIN) : 0
collapse_max (DAG_RECORDER_COLLAPSE_MAX,DR_COLLAPSE_MAX) : 1152921504606846976
node_count_target (DAG_RECORDER_NODE_COUNT,DR_NC) : 0
prune_threshold (DAG_RECORDER_PRUNE_THRESHOLD,DR_PRUNE) : 100000
alloc_unit_mb (DAG_RECORDER_ALLOC_UNIT_MB,DR_ALLOC_UNIT_MB) : 1
pre_alloc_per_worker (DAG_RECORDER_PRE_ALLOC_PER_WORKER,DR_PRE_ALLOC_PER_WORKER) : 0
pre_alloc (DAG_RECORDER_PRE_ALLOC,DR_PRE_ALLOC) : 0
dag_recorder: writing dag to 00dr.dag
dr_pi_dag_dump: 28648 bytes
dag recorder: writing stat to 00dr.stat
dag recorder: writing parallelism to 00dr.gpl
bin(10) = 1024
@end verbatim
@end example

Uppercase names within parentheses are environment variables you might want to
set.  They start with a prefix @code{DAG_RECORDER_} and many of them
have a shorter version that begin with @code{DR_}.  The list will change
as our experiences accumulate.  Below is the list of frequently used
variables (consider other variables are still experimental).

@multitable @columnfractions .15 .15 .7
@headitem variable @tab default @tab description
@item @code{DR_DAG_PREFIX} @tab @file{00dr}  @tab Prefix of all files below
@item @code{DR_DAG}  @tab 1 @tab 1 if generate a DAG file (to @code{DR_DAG_PREFIX}.dag)
@item @code{DR_STAT} @tab 1 @tab 1 if generate a summary stat file (to @code{DR_DAG_PREFIX}.stat)
@item @code{DR_GPL}  @tab 1 @tab 1 if generate a parallelism profile file (to @code{DR_DAG_PREFIX}.gpl)
@item @code{DR_DOT}  @tab 0 @tab 1 if generate a DAG file in a graphviz format (to @code{DR_DAG_PREFIX}.dot), which can be converted into viewable images by the @file{dot} command.  You need to have graphviz package installed in yours system 
@item @code{DR_TEXT} @tab 0 @tab 1 if generate a human-readable text-formatted DAG file (to @code{DR_DAG_PREFIX}.txt).  Specify this when you want to inspect raw data 
@item @code{DR_TEXT_SEP} @tab @code{|} @tab The field delimiter used in the text-formatted DAG file 
@item @code{DR_VERBOSE}  @tab 0  @tab Set verbosity 
@item @code{DR_COLLAPSE_MAX} @tab a huge value @tab Determine how aggressively the DAG Recorder collapses subgraphs.  Specifically, the value determines an upper bound of time (in clock cycles) any single node resulted from collapsing a subgraph can span.  In other words, any single node in the DAG represents either a true single node (i.e., performed no tasking primitives) or a subgraph that took shorter than this number of clocks.  The default is a huge value, which means the system can collapse subgraphs as much as it can.  Set it to a small value to guarantee a minimum resolution.
@end multitable

Let us move on to the second method, which is to control the behavior
from your program.  As briefly noted above, this is done by passing a
pointer to @code{dr_options} structure to @code{dr_start}.  See
@i{PREFIX}@file{/include/dag_recorder.h} for the list of fields.  Note
that field names were also displayed with @code{DR_VERBOSE=1} option
above.  For example, the line:
@example
dag_file_prefix (DAG_RECORDER_DAG_FILE_PREFIX,DR_PREFIX) : 00dr
@end example
tells you @code{dag_file_prefix} is the field name you want to set to change
the prefix of generated files.

When you change some of these fields, you will want to leave other
fields to their default values.  @code{dr_options_default(opts)}
is the function that fills the structure pointed to by @code{opts}
with default and environmentally-set values.  So, the typical sequence you want to use will be:
@example
dr_options opts[1];
dr_options_default(opts);
opts->dag_file = ...;
opts->@i{whatever_you_want_to_change} = ...;
   ...
dr_start(opts);
@end example

@node dag2any DAG to any data converter, Viewing Recorded Data, Running Your Programs with DAG Recorder, DAG Recorder
@section dag2any DAG to any data converter

about dag2any

@node Viewing Recorded Data, Querying Recorded Data, dag2any DAG to any data converter, DAG Recorder
@section Viewing Recorded Data

Tools to view DAG Recorder data are still ad-hoc; ideally there should
be a single tool to view the same data from many angles.  As of writing,
there instead is an interactive tool to show parallelism profile and a
set of files derived from the DAG data, viewable by standard tools such as
gnuplot.  We will continue to work on developing tools to analyze DAG
data from many angles and unify their user interfaces.

@menu
* Viewing Parallelism Profile with gnuplot ::
* Visualizing the DAG via graphviz::
* Understanding Stat File::
* Viewing DAG file with drview::
@end menu

@node Viewing Parallelism Profile with gnuplot , Visualizing the DAG via graphviz, Viewing Recorded Data, Viewing Recorded Data
@subsection Viewing Parallelism Profile with gnuplot 

By default, programs traced by DAG Recorder generates a parallelism profile as a gnuplot file.  You can simply view it by gnuplot.  A parallelism profile looks like this.

@image{gpl/tbb,300pt}

@iftex


@end iftex

The horizontal axis represents time (in clock cycles) and the vertical
axis the number of tasks of various conditions, indicated by colors.

@itemize @bullet

@item ``running'' means the number of actually running tasks.
The number of running tasks should never exceed the number of workers used
by the execution.  In the graph above, it is constant around 64.  As you
will have guessed already, it was an execution with 64 cores.

@item all other colors mean the number of ``available'' or 
``runnable'' but not running tasks; a task is available when all its
predecessors in the DAG have finished.  Available tasks are classified
by the type of event that made them runnable.  

@itemize @bullet

@item ``end'' means the task became available as its awaiting task finished.

@item ``create'' means the task became available as its parent created it.

@item ``create cont'' means the task became available as it created a task and continues.

@item ``wait cont'' means the task became available as it reached synchronization point (i.e., issued tg.wait() in TBB, sync in Cilk, pragma task wait in OpenMP, etc.) and child tasks have already finished by that point.

@item ``other cont'' means the task became available as it performed any operation that might enter the runtime system.  In practice, you will never see this event.

@end itemize
@end itemize

For example, consider the following program:
@example
@verbatim
#include <mtbb/task_gorup.h>
int main() {
  mtbb::task_group tg;
  a();
  tg.run([=] b());
  c();
  tg.wait();
  d();
}
@end verbatim
@end example
and the DAG resulting from executing this program.

@image{svg/dag,300pt}

The label of an edge indicates how the node it points to is classified
when its source node has finished.  For example, the node @i{q} is
counted as @i{create}, from the time when @i{p} finished (i.e., the task
entered @code{tg.run([=] @{ b(); @})}) to the time when @i{q} started.

@i{p''} becomes available when @i{both} @i{q} and @i{p'} finished, so
how it is classified depends on which of them finished last.  If @i{q}
finished later than @i{p'}, it is classified as @i{end}; otherwise as
@i{wait cont}.

In most cases, your primary interest will be in ``running.''  If this
stays constant around the number of workers used, it means the same
number of cores are maximally utilized (as long as the operating system
runs each worker on a distinct core).  If it is not the case, that is,
there are intervals in which the number of running tasks is lower than
the number of workers used, you should check if there are enough
@i{available} tasks.

If there are no or little available tasks in an interval, it means your
program did not have enough tasks in that interval, so you might have to
consider increasing the parallelism in that interval.  In some cases you
have simply left some section of your code left not parallelized at all,
which is easily visible in the parallelism profile.  A tool drview will
help you spot source code locations when this happens.  
@pxref{Viewing DAG file with drview}.

If, on the other hand, available tasks are abundant, it means the
runtime system, for whatever reasons, was not able to fully exploit
available parallelism.  There are several possible reasons for this.

@itemize

@item Your tasks are too fine grained, so you observe the overhead
of task creation or task stealing.  For example, let's say a runtime
system takes 10000 cycles from the point a task is created until the
point it actually gets started, it is not counted as running during that
interval of 10000 cycles.  If average task granularity is only, say,
5000 cycles, then on average only 33% (5000/15000) of CPU time will be
spent on actually running tasks.  With a 64 workers execution, you will
observe about 20 running tasks.  The more overhead the runtime system
imposes, the less number of running tasks you will observe.

@item The runtime system somehow imposes constraints on workers that can run 
certain tasks, so some available tasks are left unexecuted when workers
meeting the condition are busy on other tasks.  A typical example is
OpenMP tied tasks and TBB (where all tasks are tied); tied tasks cannot
migrate once started by a certain worker.

@end itemize

@node Visualizing the DAG via graphviz, Understanding Stat File, Viewing Parallelism Profile with gnuplot , Viewing Recorded Data
@subsection Visualizing the DAG via graphviz

You can generate the DAG captured by DAG Recorder, by setting
environment variable @code{DAG_RECORDER_DAG_FILE} 
(or @code{DR_DAG}) to the filename
you want to have it in.  The file is a text file of a graphviz dot
format, which can then be transformed into various graphics format by
graphviz tool dot.

Since a program easily generates a DAG of millions or more nodes, this
feature will be useful only for short runs.  

For example, you can see the DAG by any SVG viewer by the following
procedure.
@example
$ DR_DAG=00dr.dot ./a.out
$ dot -Tsvg -o 00dr.svg 00dr.dot 
$ @i{any-svg-viewer} 00dr.svg
@end example

See graphviz package and dot manual for further information about the
dot tool.

When you use this feature to visualize the true topology of the DAG your
program generated, you might want to turn off the subgraph contraction
algorithm DAG Recorder implements to save space.  To this end, you can
set @code{DR_COLLAPSE_MAX} environment variable to zero.

@example
$ DR_COLLAPSE_MAX=0 DR_DAG=00dr.dot ./a.out
$ dot -Tsvg -o 00dr.svg 00dr.dot 
$ @i{any-svg-viewer} 00dr.svg
@end example

@node Understanding Stat File, Viewing DAG file with drview, Visualizing the DAG via graphviz, Viewing Recorded Data
@subsection Understanding Stat File

By default, programs traced by DAG Recorder generates a small text file that summarizes various pieces of information of the execution.  You can view it by any text editor.  Here is an example.

@example
@verbatiminclude examples/00dr.stat
@end example

@itemize @bullet
@item The first three items show the number of events:
@multitable @columnfractions .1 .9
@item @code{create_task} @tab The number of times tasks are created, not including the main task.
@item @code{wait_tasks} @tab The number of times wait operations are issued. Each wait may wait for multiple tasks, so this number may not match create_task
@item @code{end_task} @tab The number of times tasks are ended. This should be @code{create_task} + 1.  +1 is because the former does not include the main task, but @code{end_task} does.
@end multitable

@item Then there are three numbers showing the breakdown of the total 
time spent by the execution.
@multitable @columnfractions .1 .9
@item @code{work (T1)} @tab The cumulative time (clock cycles) spent
in executing the application code.  Total across all cores.  This does
not include time spent in the runtime system (e.g., task creation
overhead).  If the application perfectly scales, this number should be
constant no matter how many cores you used for execution.  This is the
area of the ``running'' region in the parallelism profile graph.

@item @code{delay} @tab The cumulative time available tasks are not
executed despite there are ``spare'' cores not executing any task.  This
is the area of ``available'' region below the horizontal line at the
number of cores in the parallelism profile graph.  This value would be
zero under a hypothetical ``genuinely greedy'' scheduler, a scheduler
which immediately dispatches any available task to if any available
core, without any delay or whatsoever.

@item @code{no_work} @tab The cumulative time cores spent without available
tasks.  This is the area not filled by running or available tasks below
the horizontal line at the number of cores in the parallelism profile
graph.
@end multitable

The following is a conceptual model to understand what each of them is.
Imagine we stop all workers at each processor cycle and count the number
of tasks running (@i{= R}), as well as the number of tasks available but
not running (@i{= A}).

Let @i{W =} the number of workers.  In this setting,
@itemize @bullet
@item @code{T1} is the total of @i{R} over all cycles
@item @code{delay} is the total of min(@i{A, W - R}) over all cycles
@item @code{no_work} is the total of min(0, @i{W - R - A}) over all cycles
@end itemize

Observe that at any point, the sum of the three terms is always @i{W}.
Therefore, it always holds that 

@display
@code{T1} + @code{delay} + @code{no_work} = @i{W} x elapsed time
@end display

In other words, @code{T1, delay}, and @code{no_work} give a
@i{breakdown} of the whole execution time.  Perfectly scalable
executions have @code{T1} approximately the same as that of serial
execution and have both @code{delay} and @code{no_work} nearly zero.
They in general give you a quantitative information on why your
application does not ideally scale.

Applications that do not have enough parallelism will have large
@code{no_work}, those that have enough parallelism that cannot
be utilized by the runtime system will show a large @code{delay} value,
and those that have their work time increased (presumably due to
cache misses due to inter-core communication, false sharing, or 
capacity overflows on shared caches) will show a @code{T1} value
significantly larger than that of serial execution.

@item Nine metrics that follow give you a better idea about the
speedup.

@multitable @columnfractions .15 .85
@item @code{critical_path (T_inf)} @tab Critical path of the DAG.  This
is the longest time spent in a path in the DAG.  The time does not
include time spent in the runtime system.

@item @code{n_workers (P)} @tab
The number of workers that participated in the execution.  This is
the value DAG Recorder observed during execution and, in rare occasions,
may not match the number of cores you asked the runtime system to use.
If, for example, the program was so short lived or created so few tasks
that some cores were not used at all, you may observe a number smaller than
the number you specified.

@item @code{elapsed} @tab
Elapsed time (clock cycles) of the application.
As we stated above, @code{elapsed} x @code{P} should match the sum
of @code{T1, delay,} and @code{no_work}.

@item @code{T1/P} @tab 
This is simply @code{T1} divided by @code{P}. 
This gives an obvious lower bound on achievable elapsed time.

@item @code{T1/P+T_inf} @tab
This is simply @code{T1} divided by @code{P}. 
This gives an upper bound of elapsed time by a hypothetical greedy
scheduler.  If the scheduler is ``greedy enough'' (available tasks
will be executed quickly enough as long as there is an available core),
the elapsed time you observed should be close to this value.

@item @code{T1/T_inf} @tab
This is simply @code{T1} divided by @code{T_inf}, 
or the ``average parallelism'' of the execution.  In general, if you
hope your application to scale, this value should be much larger than
the number of cores you hope to utilize.

@item @code{greedy speedup} @tab 
The speedup that should be achieved
by a hypothetical greedy scheduler.  It is, @code{T1} divided
by @code{T1/P+T_inf}.

@item @code{observed speedup} @tab 
The actual speed up observed,
which is @code{T1} divided by @code{elapsed time}.

@item @code{observed/greedy} @tab 
The ratio of the above two terms.
It indicates how greedy the scheduler was.
@end multitable

@item The following two terms give you an idea about granularity

@multitable @columnfractions .15 .85
@item task granularity @tab 
This is the average number of cycles
between to task creations.  That is, @code{T1} divided by
the number of tasks.

@item interval granularity @tab
This is the average number of cycles spent in a single DAG node,
or cycles between any two consecutive
task parallel operations (e.g., a task creation followed by a sync).
@end multitable

@item Three terms that follow give you the number of DAG nodes
and the effectiveness of the DAG contraction algorithm.

@multitable @columnfractions .15 .85
@item dag nodes @tab 
The number of DAG nodes if there would be no 
contraction.

@item materialized nodes @tab 
The number of nodes after DAG contraction.
If @code{DR_COLLAPSE_MAX=0} (DAG contraction turned off), this should
equal to dag nodes.  If this value is large (default) and you use
only a single core, this is always one!

@item compression ratio @tab
The ratio between the two.  DAG contraction
is more effective (thus the value is small) when many large subgraphs
are executed in a single core, and thus are contracted.
@end multitable

@item Finally, there are five matrices that describe the number of edges
in the DAG connecting two nodes executed by a pair of workers.
Specifically, each matrix is @i{P} x @i{P} matrix (where @i{P} is the
number of workers) whose @i{P[i,j]} element (@i{i} : row number, @i{j} :
column number) is the number of edges of a respective type connecting
from a node executed by worker @i{i} to a node executed by worker @i{j}.
Five matrices are:

@multitable @columnfractions .15 .85
@item end-parent edges @tab
This matrix counts edges
from the last node of a task to the node that follows a wait
operation that synchronized with the task.

@item create-child edges @tab 
This matrix counts edges
from a task creation node to the first node of the created task.

@item create-cont edges @tab 
This matrix counts edges from
a task creation node to its continuation in the same task.

@item wait-cont edges @tab 
This matrix counts edges from
a synchronization node (a node that ends by issuing OpenMP 
@code{taskwait},
TBB @code{task_group::wait()} method, 
Cilk @code{sync} statement, etc.) to its continuation in 
the same task.

@item other-cont edges @tab
This matrix counts edges from
a node that ends by entering the runtime system for any reason other
than task creation or synchronization to the node that starts after the
operation.
@end multitable

@end itemize

@node Viewing DAG file with drview,  , Understanding Stat File, Viewing Recorded Data
@subsection Viewing DAG file with drview

@code{drview} is a tool that shows parallelism profile of an execution
and allows you to zoom into an interval in it.  This way it helps you
pinpoint tasks executing when parallelism was low.

Prerequisites:  @code{drview} is a python script that 
relies on the following libraries.
@itemize @bullet
@item matplotlib (Debian package name: python-matplotlib)
@item gtk (Debian package name: python-gtk2 and perhaps python-gtk2-dev)
@end itemize
Please make sure you should be able to import respective python modules
(@code{matplotlib} and @code{gtk}).

To use @code{drview}, you first need to convert the .dag file 
generated by DAG Recorder into
SQLite3 format using @code{dag2any} tool described above.  
Then you pass the resulting
SQLite3 file to @code{drview}.

TODO: We are planning to improve this crude interface, so you can
directly give a @code{.dag} file to drview.

@example
$ dag2any 00dr.dag 
writing sqlite3 to 00dr.sqlite
basics:  ........................................
nodes:   ........................................
edges:   ........................................
strings: ........................................
committing
$ drview 00dr.sqlite
@end example
This will bring up the user interface window.

BUG: The initial configuration of panes is far from satisfactory.
Please adjust their sizes manually by grabbing borders between panes.  I
am still trying to figure out how to configure their sizes.

After manually adjusting pane sizes, you will obtain something like this.

@image{img/drview_screenshot_resized}

On the leftmost pane, you see the parallelism profile, the same
information you can see by the gnuplot-formatted parallelism profile.
@pxref{Viewing Parallelism Profile with gnuplot}. 

On the center pane is the list of DAG nodes executed.  Each row
represents a group of nodes that share the same start and end positions.
They are ordered by the total number of cycles spent in the group of
tasks.  If you double-click on a row, the right pane shows the source
code of the corresponding location.  By clicking somewhere in the
``start'' or ``end'' column, the source code pane will display the
group's start or end position, respectively.

The most useful feature of this tool is that you can zoom into an
interval of your interest in the parallelism pane.  Hold the left button
of the mouse pushed and specify a rectangular region in the parallelism
pane, and you will see the parallelism and the task panes redrawn to
reflect the tasks executed in the selected interval.  This way, you can
easily know the source locations of low parallelism.

@node Querying Recorded Data,  , Viewing Recorded Data, DAG Recorder
@section Querying Recorded Data


@bye