Inria automn school "High Performance Numerical Simulation": StarPU Tutorial - Bordeaux, November, 7th 2019

To be able to exercise accelerator support without having real GPUs cards, we will use a simulation version of StarPU, based on top of SimGrid. The following Guix command will put you in a dedicated StarPU SimGrid environment

$ guix environment --pure starpu-simgrid --ad-hoc starpu-simgrid grep coreutils emacs vim less openssh inetutils gv -- /bin/bash --norc

You also need to load the environment from the init.sh shell script from the archive file.

$ . ./init.sh

Then you can see that StarPU detects the simulated platform with

$ starpu_machine_display

This example is at the root of the archive file

In the previous section, we submitted only one task. We here discuss how to partition data so as to submit multiple tasks which can be executed in parallel by the various CPUs and GPUs.

Let's examine mult.c.

• The computation kernel, cpu_mult is a trivial matrix multiplication kernel, which operates on 3 given DSM interfaces. These will actually not be whole matrices, but only small parts of matrices.
• init_problem_data initializes the whole A, B and C matrices.
• partition_mult_data does the actual registration and partitioning. Matrices are first registered completely, then two partitioning filters are declared. The first one, vert, is used to split B and C vertically. The second one, horiz, is used to split A and C horizontally. We thus end up with a grid of pieces of C to be computed from stripes of A and B.
• launch_tasks submits the actual tasks: for each piece of C, take the appropriate piece of A and B to produce the piece of C.
• The access mode is interesting: A and B just need to be read from, and C will only be written to. This means that StarPU will make copies of the pieces of A and B along the machines, where they are needed for tasks, and will give to the tasks some uninitialized buffers for the pieces of C, since they will not be read from.
• The main code initializes StarPU and data, launches tasks, unpartitions data, and unregisters it. Unpartitioning is an interesting step: until then the pieces of C are residing on the various GPUs where they have been computed. Unpartitioning will collect all the pieces of C into the main memory to form the whole C result matrix.

Run the application with the script mult.sh, enabling some statistics:

#!/bin/bash
make mult
STARPU_WORKER_STATS=1 ./mult

Figures show how the computation were distributed on the various processing units.

gemm/xgemm.c is a very similar matrix-matrix product example, but which makes use of BLAS kernels for much better performance. The mult_kernel_common functions shows how we call DGEMM (CPUs) or cublasDgemm (GPUs) on the DSM interface.

Let's execute it.

#!/bin/bash
make gemm/sgemm
STARPU_WORKER_STATS=1 ./gemm/sgemm

Take the vector example again, and add partitioning support to it, using the matrix-matrix multiplication as an example. Here we will use the starpu_vector_filter_block() filter function. You can see the list of predefined filters provided by StarPU here. By using the SimGrid version of StarPU, you may when running a partitioned version of vector_scal_task_insert get the following error

[starpu][_starpu_simgrid_submit_job][assert failure] Codelet vector_scal does not have a perfmodel, \
or is not calibrated enough, please re-run in non-simgrid mode until it is calibrated

this is because the performance model we are providing for this tutorial is only calibrated for vectors with 2048 elements, to avoid the issue, you can just multiply the number of elements (NX) by the number of sub-data you defined in struct starpu_data_filter, and so each sub-data will be a vector of 2048 elements. We provide a solution for the exercice here.

To let StarPU reorder tasks, submit data transfers in advance, etc., task submission should be asynchronous whenever possible. Ideally, the application should behave like that: submit the whole graph of tasks, and wait for termination.

Performance prediction is essential for proper scheduling decisions, the performance models thus have to be calibrated. This is done automatically by StarPU when a codelet is executed for the first time. Once this is done, the result is saved to a file in $STARPU_PERF_MODEL_DIR for later re-use. The starpu_perfmodel_display tool can be used to check the resulting performance model.

STARPU_PERF_MODEL_DIR specifies the main directory in which StarPU stores its performance model files. The default is $STARPU_HOME/.starpu/sampling.

STARPU_HOME specifies the main directory in which StarPU stores its configuration files. The default is $HOME on Unix environments, and $USERPROFILE on Windows environments.

In this tutorial which is using the Simgrid version of StarPU, we are setting STARPU_PERF_MODEL_DIR to a specific directory perfmodels available in the archive.

$ starpu_perfmodel_display -l
file: <vector_scal.conan>
file: <mult_perf_model.conan>
file: <starpu_dgemm_gemm.conan>
file: <starpu_sgemm_gemm.conan>
$ starpu_perfmodel_display -s vector_scal
# performance model for cuda0_impl0 (Comb0)
# performance model for cuda0_impl0 (Comb0)
	Regression : #sample = 132
	Linear: y = alpha size ^ beta
		alpha = 7.040874e-01
		beta = 3.326125e-01
	Non-Linear: y = a size ^b + c
		a = 6.207150e-05
		b = 9.503886e-01
		c = 1.887639e+01
# hash		size		flops		mean (us)	stddev (us)		n
a3d3725e	4096           	0.000000e+00   	1.902150e+01   	1.639952e+00   	10
870a30aa	8192           	0.000000e+00   	1.971540e+01   	1.115123e+00   	10
48e988e9	16384          	0.000000e+00   	1.934910e+01   	8.406537e-01   	10
...
09be3ca9	1048576        	0.000000e+00   	5.483990e+01   	7.629412e-01   	10
...
# performance model for cuda1_impl0 (Comb1)
...
09be3ca9	1048576        	0.000000e+00   	5.389290e+01   	8.083156e-01   	10
...
# performance model for cuda2_impl0 (Comb2)
...
09be3ca9	1048576        	0.000000e+00   	5.431150e+01   	4.599005e-01   	10
...
# performance model for cpu0_impl0 (Comb3)
...
a3d3725e	4096           	0.000000e+00   	5.149621e+00   	7.096558e-02   	66
...
09be3ca9	1048576        	0.000000e+00   	1.218595e+03   	4.823102e+00   	66
...

This shows that for the vector_scal kernel with a 4KB size, the average execution time on CPUs was about 5.1µs, with a 0.07µs standard deviation, over 66 samples, while it took about 19µs on CUDA GPUs, with a 1.6µs standard deviation. With a 1MB size, execution time on CPUs is 1.2ms, while it is only 54µs on the CUDA GPU. It is a good idea to check the variation before doing actual performance measurements. If the kernel has varying performance, it may be a good idea to force StarPU to continue calibrating the performance model, by using export STARPU_CALIBRATE=1

The performance model can also be drawn by using starpu_perfmodel_plot, which will emit a gnuplot file in the current directory:

$ starpu_perfmodel_plot -s vector_scal
...
[starpu][main] Gnuplot file <starpu_vector_scal.gp> generated
$ gnuplot starpu_vector_scal.gp
$ gv starpu_vector_scal.eps

The gv command will not work if you have not specified -X when you ran ssh.

If the code of a computation kernel is modified, the performance changes, the performance model thus has to be recalibrated from start. To do so, use export STARPU_CALIBRATE=2

By default, StarPU uses the lws simple greedy scheduler. This is because it provides correct load balance even if the application codelets do not have performance models: it uses a single central queue, from which workers draw tasks to work on. This however does not permit to prefetch data, since the scheduling decision is taken late.

If the application codelets have performance models, the scheduler should be changed to take benefit from that. StarPU will then really take scheduling decision in advance according to performance models, and issue data prefetch requests, to overlap data transfers and computations.

For instance, compare the lws (default) and dmda scheduling policies:

$ STARPU_BUS_STATS=1 STARPU_WORKER_STATS=1 gemm/sgemm -xy $((256*4)) -nblocks 4

with:

$ STARPU_BUS_STATS=1 STARPU_WORKER_STATS=1 STARPU_SCHED=dmda gemm/sgemm -xy $((256*4)) -nblocks 4

You can see most (all?) the computation have been done on GPUs, leading to better performances.

Try other schedulers, use STARPU_SCHED=help to get the list.

Also try with various sizes (keeping a 256 tile size, i.e. increase both occurrences of 4 above) and draw curves.

You can also try the double version, dgemm, and notice that GPUs get less great performance.

Basically, StarPU provides equivalents of MPI_* functions, but which operate on DSM handles instead of void* buffers. The difference is that the source data may be residing on a GPU where it just got computed. StarPU will automatically handle copying it back to main memory before submitting it to MPI.

In the mpi/ subdirectory, ring_async_implicit.c shows an example of mixing MPI communications and task submission. It is a classical ring MPI ping-pong, but the token which is being passed on from neighbour to neighbour is incremented by a starpu task at each step.

This is written very naturally by simply submitting all MPI communication requests and task submission asynchronously in a sequential-looking loop, and eventually waiting for all the tasks to complete.

$ cd mpi
$ make ring_async_implicit
$ mpirun -np 2 $PWD/ring_async_implicit

A stencil application shows a basic MPI task model application. The data distribution over MPI nodes is decided by the my_distrib function, and can thus be changed trivially. It also shows how data can be migrated to a new distribution.

$ make stencil5
$ mpirun -np 2 $PWD/stencil5 -display

The Klang-Omp OpenMP compiler converts C/C++ source codes annotated with OpenMP 4 directives into StarPU enabled codes. Klang-Omp is source-to-source compiler based on the LLVM/CLang compiler framework.

The following shell sequence shows an example of an OpenMP version of the Cholesky decomposition compiled into StarPU code.

cd
source /gpfslocal/pub/training/runtime_june2016/openmp/environment
cp -r /gpfslocal/pub/training/runtime_june2016/openmp/Cholesky .
cd Cholesky
make
./cholesky_omp4.starpu

Homepage of the Klang-Omp OpenMP compiler: Klang-Omp

In addition to online profiling, StarPU provides offline profiling tools, based on recording a trace of events during execution, and analyzing it afterwards.

A Guix StarPU-FxT package is available. You need to call the following Guix command to use it.

$ guix environment --pure starpu-fxt --ad-hoc starpu-fxt grep coreutils emacs vim less gv \
     --with-commit=starpu-fxt=3cc33c3cc85eae5dbc0f4b0ddc9291e3409287b2 -- /bin/bash --norc

The Guix package starpu-fxt is currently based on the version 1.3.3 of StarPU which has a bug which leads to the creation of huge trace files. This has been fixed but not released yet, we hence use the Guix parameter --with-commit to indicate a specific commit for StarPU. This will no longer be needed after the next StarPU release and the upgrade of the Guix package.

The trace file is stored in /tmp by default. To tell StarPU to store output traces in the home directory, one can set:

$ export STARPU_FXT_PREFIX=$HOME/

The application should be run again, for instance:

$ make clean
$ make mult
$ ./mult

This time a prof_file_XX_YY trace file will be generated in your home directory. This can be converted to several formats by using:

$ starpu_fxt_tool -i ~/prof_file_*

This will create

• a paje.trace file, which can be opened by using the ViTE tool. This shows a Gant diagram of the tasks which executed, and thus the activity and idleness of tasks, as well as dependencies, data transfers, etc. You may have to zoom in to actually focus on the computation part, and not the lengthy CUDA initialization.
• a dag.dot file, which contains the graph of all the tasks submitted by the application. It can be opened by using Graphviz.
• an activity.data file, which records the activity of all processing units over time.