StarPU Handbook

Offline Performance Tools

To get an idea of what is happening, a lot of performance feedback is available, detailed in this chapter. The various informations should be checked for.

- What does the Gantt diagram look like? (see Creating a Gantt Diagram)
  - If it's mostly green (tasks running in the initial context) or context specific color prevailing, then the machine is properly utilized, and perhaps the codelets are just slow. Check their performance, see Performance Of Codelets.
  - If it's mostly purple (FetchingInput), tasks keep waiting for data transfers, do you perhaps have far more communication than computation? Did you properly use CUDA streams to make sure communication can be overlapped? Did you use data-locality aware schedulers to avoid transfers as much as possible?
  - If it's mostly red (Blocked), tasks keep waiting for dependencies, do you have enough parallelism? It might be a good idea to check what the DAG looks like (see Creating a DAG With Graphviz).
  - If only some workers are completely red (Blocked), for some reason the scheduler didn't assign tasks to them. Perhaps the performance model is bogus, check it (see Performance Of Codelets). Do all your codelets have a performance model? When some of them don't, the schedulers switches to a greedy algorithm which thus performs badly.

You can also use the Temanejo task debugger (see Using The Temanejo Task Debugger) to visualize the task graph more easily.

# Off-line Performance Feedback

## Generating Traces With FxT

StarPU can use the FxT library (see https://savannah.nongnu.org/projects/fkt/) to generate traces with a limited runtime overhead.

You can get a tarball from http://download.savannah.gnu.org/releases/fkt/?C=M

Compiling and installing the FxT library in the `$FXTDIR` path is done following the standard procedure:

    $ ./configure --prefix=$FXTDIR
    $ make
    $ make install

In order to have StarPU to generate traces, StarPU should be configured with the option --with-fxt :

    $ ./configure --with-fxt=$FXTDIR

Or you can simply point the `PKG_CONFIG_PATH` to `$FXTDIR/lib/pkgconfig` and pass --with-fxt to `configure`

When FxT is enabled, a trace is generated when StarPU is terminated by calling starpu_shutdown(). The trace is a binary file whose name has the form `prof_file_XXX_YYY` where `XXX` is the user name, and `YYY` is the MPI id of the process that used StarPU (or 0 when running a sequential program). One can change the name of the file by setting the environnement variable STARPU_FXT_SUFFIX, its contents will be used instead of `prof_file_XXX`. This file is saved in the `/tmp/` directory by default, or by the directory specified by the environment variable STARPU_FXT_PREFIX.

The additional `configure` option --enable-fxt-lock can be used to generate trace events which describes the locks behaviour during the execution. It is however very heavy and should not be used unless debugging StarPU's internal locking.

The environment variable STARPU_FXT_TRACE can be set to 0 to disable the generation of the `prof_file_XXX_YYY` file.

When the FxT trace file `prof_file_something` has been generated, it is possible to generate different trace formats by calling:

    $ starpu_fxt_tool -i /tmp/prof_file_something

Or alternatively, setting the environment variable STARPU_GENERATE_TRACE to `1` before application execution will make StarPU do it automatically at application shutdown.

One can also set the environment variable STARPU_GENERATE_TRACE_OPTIONS to specify options, see `starpu_fxt_tool –help`, for example:

    $ export STARPU_GENERATE_TRACE=1
    $ export STARPU_GENERATE_TRACE_OPTIONS="-no-acquire"

When running a MPI application, STARPU_GENERATE_TRACE will not work as expected (each node will try to generate trace files, thus mixing outputs...), you have to collect the trace files from the MPI nodes, and specify them all on the command `starpu_fxt_tool`, for instance:

    $ starpu_fxt_tool -i /tmp/prof_file_something*

By default, the generated trace contains all informations. To reduce the trace size, various `-no-foo` options can be passed to `starpu_fxt_tool`, see `starpu_fxt_tool –help` .

### Creating a Gantt Diagram

One of the generated files is a trace in the Paje format. The file, located in the current directory, is named `paje.trace`. It can be viewed with ViTE (http://vite.gforge.inria.fr/) a trace visualizing open-source tool. To open the file `paje.trace` with ViTE, use the following command:

    $ vite paje.trace

Tasks can be assigned a name (instead of the default `unknown`) by filling the optional starpu_codelet::name, or assigning them a performance model. The name can also be set with the field starpu_task::name or by using STARPU_NAME when calling starpu_task_insert().

Tasks are assigned default colors based on the worker which executed them (green for CPUs, yellow/orange/red for CUDAs, blue for OpenCLs, red for MICs, ...). To use a different color for every type of task, one can specify the option `-c` to `starpu_fxt_tool` or in STARPU_GENERATE_TRACE_OPTIONS. Tasks can also be given a specific color by setting the field starpu_codelet::color or the starpu_task::color. Colors are expressed with the following format `0xRRGGBB` (e.g `0xFF0000` for red). See `basic_examples/task_insert_color` for examples on how to assign colors.

To get statistics on the time spend in runtime overhead, one can use the statistics plugin of ViTE. In Preferences, select Plugins. In "States Type", select "Worker State". Then click on "Reload" to update the histogram. The red "Idle" percentages are due to lack of parallelism, while the brown "Overhead" and "Scheduling" percentages are due to the overhead of the runtime and of the scheduler.

To identify tasks precisely, the application can also set the field starpu_task::tag_id or setting STARPU_TAG_ONLY when calling starpu_task_insert(). The value of the tag will then show up in the trace.

One can also introduce user-defined events in the diagram thanks to the starpu_fxt_trace_user_event_string() function.

One can also set the iteration number, by just calling starpu_iteration_push() at the beginning of submission loops and starpu_iteration_pop() at the end of submission loops. These iteration numbers will show up in traces for all tasks submitted from there.

Coordinates can also be given to data with the starpu_data_set_coordinates() or starpu_data_set_coordinates_array() function. In the trace, tasks will then be assigned the coordinates of the first data they write to.

Traces can also be inspected by hand by using the tool `fxt_print`, for instance:

    $ fxt_print -o -f /tmp/prof_file_something

Timings are in nanoseconds (while timings as seen in ViTE are in milliseconds).

### Creating a DAG With Graphviz

Another generated trace file is a task graph described using the DOT language. The file, created in the current directory, is named `dag.dot` file in the current directory. It is possible to get a graphical output of the graph by using the `graphviz` library:

    $ dot -Tpdf dag.dot -o output.pdf

### Getting Task Details

Another generated trace file gives details on the executed tasks. The file, created in the current directory, is named `tasks.rec`. This file is in the recutils format, i.e. `Field: value` lines, and empty lines to separate each task. This can be used as a convenient input for various ad-hoc analysis tools. By default it only contains information about the actual execution. Performance models can be obtained by running `starpu_tasks_rec_complete` on it:

    $ starpu_tasks_rec_complete tasks.rec tasks2.rec

which will add `EstimatedTime` lines which contain the performance model-estimated time (in µs) for each worker starting from 0. Since it needs the performance models, it needs to be run the same way as the application execution, or at least with `STARPU_HOSTNAME` set to the hostname of the machine used for execution, to get the performance models of that machine.

Another possibility is to obtain the performance models as an auxiliary `perfmodel.rec` file, by using the `starpu_perfmodel_recdump` utility:

    $ starpu_perfmodel_recdump tasks.rec -o perfmodel.rec

### Monitoring Activity

Another generated trace file is an activity trace. The file, created in the current directory, is named `activity.data`. A profile of the application showing the activity of StarPU during the execution of the program can be generated:

    $ starpu_workers_activity activity.data

This will create a file named `activity.eps` in the current directory. This picture is composed of two parts. The first part shows the activity of the different workers. The green sections indicate which proportion of the time was spent executed kernels on the processing unit. The red sections indicate the proportion of time spent in StartPU: an important overhead may indicate that the granularity may be too low, and that bigger tasks may be appropriate to use the processing unit more efficiently. The black sections indicate that the processing unit was blocked because there was no task to process: this may indicate a lack of parallelism which may be alleviated by creating more tasks when it is possible.

The second part of the picture `activity.eps` is a graph showing the evolution of the number of tasks available in the system during the execution. Ready tasks are shown in black, and tasks that are submitted but not schedulable yet are shown in grey.

### Getting Modular Schedular Animation

When using modular schedulers (i.e. schedulers which use a modular architecture, and whose name start with "modular-"), the call to `starpu_fxt_tool` will also produce a `trace.html` file which can be viewed in a javascript-enabled web browser. It shows the flow of tasks between the components of the modular scheduler.

## Limiting The Scope Of The Trace

For computing statistics, it is useful to limit the trace to a given portion of the time of the whole execution. This can be achieved by calling

starpu_fxt_autostart_profiling(0)
starpu_fxt_autostart_profiling
void starpu_fxt_autostart_profiling(int autostart)

before calling starpu_init(), to prevent tracing from starting immediately. Then

starpu_fxt_start_profiling();
starpu_fxt_start_profiling
void starpu_fxt_start_profiling(void)

and

starpu_fxt_stop_profiling();
starpu_fxt_stop_profiling
void starpu_fxt_stop_profiling(void)

can be used around the portion of code to be traced. This will show up as marks in the trace, and states of workers will only show up for that portion.

# Performance Of Codelets

The performance model of codelets (see Performance Model Example) can be examined by using the tool `starpu_perfmodel_display`:

    $ starpu_perfmodel_display -l
    file: <malloc_pinned.hannibal>
    file: <starpu_slu_lu_model_21.hannibal>
    file: <starpu_slu_lu_model_11.hannibal>
    file: <starpu_slu_lu_model_22.hannibal>
    file: <starpu_slu_lu_model_12.hannibal>

Here, the codelets of the example `lu` are available. We can examine the performance of the kernel `22` (in micro-seconds), which is history-based:

    $ starpu_perfmodel_display -s starpu_slu_lu_model_22
    performance model for cpu
    # hash      size       mean          dev           n
    57618ab0    19660800   2.851069e+05  1.829369e+04  109
    performance model for cuda_0
    # hash      size       mean          dev           n
    57618ab0    19660800   1.164144e+04  1.556094e+01  315
    performance model for cuda_1
    # hash      size       mean          dev           n
    57618ab0    19660800   1.164271e+04  1.330628e+01  360
    performance model for cuda_2
    # hash      size       mean          dev           n
    57618ab0    19660800   1.166730e+04  3.390395e+02  456

We can see that for the given size, over a sample of a few hundreds of execution, the GPUs are about 20 times faster than the CPUs (numbers are in us). The standard deviation is extremely low for the GPUs, and less than 10% for CPUs.

This tool can also be used for regression-based performance models. It will then display the regression formula, and in the case of non-linear regression, the same performance log as for history-based performance models:

    $ starpu_perfmodel_display -s non_linear_memset_regression_based
    performance model for cpu_impl_0
    	Regression : #sample = 1400
    	Linear: y = alpha size ^ beta
    		alpha = 1.335973e-03
    		beta = 8.024020e-01
    	Non-Linear: y = a size ^b + c
    		a = 5.429195e-04
    		b = 8.654899e-01
    		c = 9.009313e-01
    # hash		size		mean		stddev		n
    a3d3725e	4096           	4.763200e+00   	7.650928e-01   	100
    870a30aa	8192           	1.827970e+00   	2.037181e-01   	100
    48e988e9	16384          	2.652800e+00   	1.876459e-01   	100
    961e65d2	32768          	4.255530e+00   	3.518025e-01   	100
    ...

The same can also be achieved by using StarPU's library API, see Performance Model and notably the function starpu_perfmodel_load_symbol(). The source code of the tool `starpu_perfmodel_display` can be a useful example.

An XML output can also be printed by using the `-x` option:

    tools/starpu_perfmodel_display -x -s non_linear_memset_regression_based
    <?xml version="1.0" encoding="UTF-8"?>
    <!DOCTYPE StarPUPerfmodel SYSTEM "starpu-perfmodel.dtd">
    <!-- symbol non_linear_memset_regression_based -->
    <!-- All times in us -->
    <perfmodel version="45">
      <combination>
        <device type="CPU" id="0" ncores="1"/>
        <implementation id="0">
          <!-- cpu0_impl0 (Comb0) -->
          <!-- time = a size ^b + c -->
          <nl_regression a="5.429195e-04" b="8.654899e-01" c="9.009313e-01"/>
          <entry footprint="a3d3725e" size="4096" flops="0.000000e+00" mean="4.763200e+00" deviation="7.650928e-01" nsample="100"/>
          <entry footprint="870a30aa" size="8192" flops="0.000000e+00" mean="1.827970e+00" deviation="2.037181e-01" nsample="100"/>
          <entry footprint="48e988e9" size="16384" flops="0.000000e+00" mean="2.652800e+00" deviation="1.876459e-01" nsample="100"/>
          <entry footprint="961e65d2" size="32768" flops="0.000000e+00" mean="4.255530e+00" deviation="3.518025e-01" nsample="100"/>
        </implementation>
      </combination>
    </perfmodel>

The tool `starpu_perfmodel_plot` can be used to draw performance models. It writes a `.gp` file in the current directory, to be run with the tool `gnuplot`, which shows the corresponding curve.

When the field starpu_task::flops is set (or STARPU_FLOPS is passed to starpu_task_insert()), `starpu_perfmodel_plot` can directly draw a GFlops/s curve, by simply adding the `-f` option:

    $ starpu_perfmodel_plot -f -s chol_model_11

This will however disable displaying the regression model, for which we can not compute GFlops/s.

When the FxT trace file `prof_file_something` has been generated, it is possible to get a profiling of each codelet by calling:

    $ starpu_fxt_tool -i /tmp/prof_file_something
    $ starpu_codelet_profile distrib.data codelet_name

This will create profiling data files, and a `distrib.data.gp` file in the current directory, which draws the distribution of codelet time over the application execution, according to data input size.

This is also available in the tool `starpu_perfmodel_plot`, by passing it the fxt trace:

    $ starpu_perfmodel_plot -s non_linear_memset_regression_based -i /tmp/prof_file_foo_0

It will produce a `.gp` file which contains both the performance model curves, and the profiling measurements.

If you have the statistical tool `R` installed, you can additionally use

    $ starpu_codelet_histo_profile distrib.data

Which will create one `.pdf` file per codelet and per input size, showing a histogram of the codelet execution time distribution.

# Data trace and tasks length

It is possible to get statistics about tasks length and data size by using :

    $ starpu_fxt_data_trace filename [codelet1 codelet2 ... codeletn]

Where filename is the FxT trace file and codeletX the names of the codelets you want to profile (if no names are specified, `starpu_fxt_data_trace` will profile them all). This will create a file, `data_trace.gp` which can be executed to get a `.eps` image of these results. On the image, each point represents a task, and each color corresponds to a codelet.

# Trace Statistics

More than just codelet performance, it is interesting to get statistics over all kinds of StarPU states (allocations, data transfers, etc.). This is particularly useful to check what may have gone wrong in the accurracy of the SimGrid simulation.

This requires the `R` statistical tool, with the `plyr`, `ggplot2` and `data.table` packages. If your system distribution does not have packages for these, one can fetch them from `CRAN`:

    $ R
    > install.packages("plyr")
    > install.packages("ggplot2")
    > install.packages("data.table")
    > install.packages("knitr")

The `pj_dump` tool from `pajeng` is also needed (see https://github.com/schnorr/pajeng)

One can then get textual or `.csv` statistics over the trace states:

    $ starpu_paje_state_stats -v native.trace simgrid.trace
    "Value"         "Events_native.csv" "Duration_native.csv" "Events_simgrid.csv" "Duration_simgrid.csv"
    "Callback"      220                 0.075978              220                  0
    "chol_model_11" 10                  565.176               10                   572.8695
    "chol_model_21" 45                  9184.828              45                   9170.719
    "chol_model_22" 165                 64712.07              165                  64299.203
    $ starpu_paje_state_stats native.trace simgrid.trace

An other way to get statistics of StarPU states (without installing `R` and `pj_dump`) is to use the `starpu_trace_state_stats.py` script which parses the generated `trace.rec` file instead of the `paje.trace` file. The output is similar to the previous script but it doesn't need any dependencies.

The different prefixes used in `trace.rec` are:

    E: Event type
    N: Event name
    C: Event category
    W: Worker ID
    T: Thread ID
    S: Start time

Here's an example on how to use it:

    $ starpu_trace_state_stats.py trace.rec | column -t -s ","
    "Name"		"Count" "Type"	"Duration"
    "Callback"       220	Runtime	0.075978
    "chol_model_11"  10	Task	565.176
    "chol_model_21"  45	Task	9184.828
    "chol_model_22"  165	Task	64712.07

`starpu_trace_state_stats.py` can also be used to compute the different efficiencies. Refer to the usage description to show some examples.

And one can plot histograms of execution times, of several states for instance:

    $ starpu_paje_draw_histogram -n chol_model_11,chol_model_21,chol_model_22 native.trace simgrid.trace

and see the resulting pdf file:

A quick statistical report can be generated by using:

    $ starpu_paje_summary native.trace simgrid.trace

it includes gantt charts, execution summaries, as well as state duration charts and time distribution histograms.

Other external Paje analysis tools can be used on these traces, one just needs to sort the traces by timestamp order (which not guaranteed to make recording more efficient):

    $ starpu_paje_sort paje.trace

# Theoretical Lower Bound On Execution Time

StarPU can record a trace of what tasks are needed to complete the application, and then, by using a linear system, provide a theoretical lower bound of the execution time (i.e. with an ideal scheduling).

The computed bound is not really correct when not taking into account dependencies, but for an application which have enough parallelism, it is very near to the bound computed with dependencies enabled (which takes a huge lot more time to compute), and thus provides a good-enough estimation of the ideal execution time.

Theoretical Lower Bound On Execution Time Example provides an example on how to use this.

# Theoretical Lower Bound On Execution Time Example

For kernels with history-based performance models (and provided that they are completely calibrated), StarPU can very easily provide a theoretical lower bound for the execution time of a whole set of tasks. See for instance `examples/lu/lu_example.c`: before submitting tasks, call the function starpu_bound_start(), and after complete execution, call starpu_bound_stop(). starpu_bound_print_lp() or starpu_bound_print_mps() can then be used to output a Linear Programming problem corresponding to the schedule of your tasks. Run it through `lp_solve` or any other linear programming solver, and that will give you a lower bound for the total execution time of your tasks. If StarPU was compiled with the library `glpk` installed, starpu_bound_compute() can be used to solve it immediately and get the optimized minimum, in ms. Its parameter `integer` allows to decide whether integer resolution should be computed and returned

The `deps` parameter tells StarPU whether to take tasks, implicit data, and tag dependencies into account. Tags released in a callback or similar are not taken into account, only tags associated with a task are. It must be understood that the linear programming problem size is quadratic with the number of tasks and thus the time to solve it will be very long, it could be minutes for just a few dozen tasks. You should probably use `lp_solve -timeout 1 test.pl -wmps test.mps` to convert the problem to MPS format and then use a better solver, `glpsol` might be better than `lp_solve` for instance (the `–pcost` option may be useful), but sometimes doesn't manage to converge. `cbc` might look slower, but it is parallel. For `lp_solve`, be sure to try at least all the `-B` options. For instance, we often just use `lp_solve -cc -B1 -Bb -Bg -Bp -Bf -Br -BG -Bd -Bs -BB -Bo -Bc -Bi` , and the `-gr` option can also be quite useful. The resulting schedule can be observed by using the tool `starpu_lp2paje`, which converts it into the Paje format.

Data transfer time can only be taken into account when `deps` is set. Only data transfers inferred from implicit data dependencies between tasks are taken into account. Other data transfers are assumed to be completely overlapped.

Setting `deps` to 0 will only take into account the actual computations on processing units. It however still properly takes into account the varying performances of kernels and processing units, which is quite more accurate than just comparing StarPU performances with the fastest of the kernels being used.

The `prio` parameter tells StarPU whether to simulate taking into account the priorities as the StarPU scheduler would, i.e. schedule prioritized tasks before less prioritized tasks, to check to which extend this results to a less optimal solution. This increases even more computation time.

# Trace visualization with StarVZ

Creating views with StarVZ (see: https://github.com/schnorr/starvz) is made up of two steps. The initial stage consists of a pre-processing of the traces generated by the application, while the second one consists of the analysis itself and is carried out with R packages' aid. StarVZ is available at CRAN (https://cran.r-project.org/package=starvz) and depends on pj_dump (from pajeng) and rec2csv (from recutils).

To download and install StarVZ, it is necessary to have R, pajeng, and recutils:

    # For pj_dump and rec2csv
    apt install -y pajeng recutils

    # For R
    apt install -y r-base libxml2-dev libssl-dev libcurl4-openssl-dev libgit2-dev libboost-dev

To install the StarVZ, the following command can be used:

    echo "install.packages('starvz', repos = 'https://cloud.r-project.org')" | R --vanilla

To generate traces from an application, it is necessary to set STARPU_GENERATE_TRACE and build StarPU with FxT. Then, StarVZ can be used on a folder with StarPU FxT traces to produce a default view:

    export PATH=$(Rscript -e 'cat(system.file("tools/", package = "starvz"), sep="\n")'):$PATH

    starvz /foo/path-to-fxt-files

An example of default view:

One can also use existing trace files (paje.trace, tasks.rec, data.rec, papi.rec and dag.dot) skipping the StarVZ internal call to starpu_fxt_tool with:

    starvz --use-paje-trace /foo/path-to-trace-files

Alternatively, each StarVZ step can be executed separately. Step 1 can be used on a folder with:

    starvz -1 /foo/path-to-fxt-files

Then the second step can be executed directly in R. StarVZ enables a set of different plots that can be configured on a .yaml file. A default file is provided (`default.yaml`); also, the options can be changed directly in R.

    library(starvz)
    library(dplyr)

    dtrace <- starvz_read("./", selective = FALSE)

    # show idleness ratio
    dtrace$config$st$idleness = TRUE

    # show ABE bound
    dtrace$config$st$abe$active = TRUE

    # find the last task with dplyr
    dtrace$config$st$tasks$list = dtrace$Application %>% filter(End == max(End)) %>% .$JobId
    # show last task dependencies
    dtrace$config$st$tasks$active = TRUE
    dtrace$config$st$tasks$levels = 50

    plot <- starvz_plot(dtrace)

An example of visualization follows:

# Memory Feedback

It is possible to enable memory statistics. To do so, you need to pass the option --enable-memory-stats when running `configure`. It is then possible to call the function starpu_data_display_memory_stats() to display statistics about the current data handles registered within StarPU.

Moreover, statistics will be displayed at the end of the execution on data handles which have not been cleared out. This can be disabled by setting the environment variable STARPU_MEMORY_STATS to `0`.

For example, if you do not unregister data at the end of the complex example, you will get something similar to:

    $ STARPU_MEMORY_STATS=0 ./examples/interface/complex
    Complex[0] = 45.00 + 12.00 i
    Complex[0] = 78.00 + 78.00 i
    Complex[0] = 45.00 + 12.00 i
    Complex[0] = 45.00 + 12.00 i

    $ STARPU_MEMORY_STATS=1 ./examples/interface/complex
    Complex[0] = 45.00 + 12.00 i
    Complex[0] = 78.00 + 78.00 i
    Complex[0] = 45.00 + 12.00 i
    Complex[0] = 45.00 + 12.00 i

    #---------------------
    Memory stats:
    #-------
    Data on Node #3
    #-----
    Data : 0x553ff40
    Size : 16

    #--
    Data access stats
    /!\ Work Underway
    Node #0
    	Direct access : 4
    	Loaded (Owner) : 0
    	Loaded (Shared) : 0
    	Invalidated (was Owner) : 0

    Node #3
    	Direct access : 0
    	Loaded (Owner) : 0
    	Loaded (Shared) : 1
    	Invalidated (was Owner) : 0

    #-----
    Data : 0x5544710
    Size : 16

    #--
    Data access stats
    /!\ Work Underway
    Node #0
    	Direct access : 2
    	Loaded (Owner) : 0
    	Loaded (Shared) : 1
    	Invalidated (was Owner) : 1

    Node #3
    	Direct access : 0
    	Loaded (Owner) : 1
    	Loaded (Shared) : 0
    	Invalidated (was Owner) : 0

# Data Statistics

Different data statistics can be displayed at the end of the execution of the application. To enable them, you need to define the environment variable STARPU_ENABLE_STATS. When calling starpu_shutdown() various statistics will be displayed, execution, MSI cache statistics, allocation cache statistics, and data transfer statistics. The display can be disabled by setting the environment variable STARPU_STATS to `0`.

    $ ./examples/cholesky/cholesky_tag
    Computation took (in ms)
    518.16
    Synthetic GFlops : 44.21
    #---------------------
    MSI cache stats :
    TOTAL MSI stats	hit 1622 (66.23 %)	miss 827 (33.77 %)
    ...

    $ STARPU_STATS=0 ./examples/cholesky/cholesky_tag
    Computation took (in ms)
    518.16
    Synthetic GFlop/s : 44.21