README.md
1# Cholesky sample
2This directory contains an example of several versions of Cholesky Factorization algorithm.
3
4**dpotrf**: An implementation that calls the oneAPI Math Kernel Library (oneMKL) `dpotrf` function to directly perform the factorization. This can be a serial implementation or threaded implementation depending on the version of the oneMKL library that is linked against.
5
6**crout**: A serial implementation that uses the Crout-Cholesky algorithm for factorization. The same approach is parallelized for the other oneAPI Threading Building Blocks (oneTBB) based approaches below.
7
8**depend**: A parallel version of Crout-Cholesky factorization that uses the oneTBB flow graph. This version uses a dependency graph made solely of `continue_node` objects. This an inspector-executor approach, where a loop nest that is similar to the serial implementation is used to create an unrolled version of the computation. Where the oneMKL calls would have been made in the original serial implementation of Crout-Cholesky, graph nodes are created instead and these nodes are linked by edges to the other nodes they are dependent upon. The resulting graph is relatively large, with a node for each instance of each oneMKL call. For example, there are many nodes that call `dtrsm`; one for each invocation of `dtrsm` in the serial implementation. The is very little overhead in message management for this version and so it is often the highest performing.
9
10**join**: A parallel version of Crout-Cholesky factorization that uses the oneTBB flow graph. This version uses a data flow approach. This is a small, compact graph that passes tiles along its edges. There is one node per type of oneMKL call, plus `join_node`s that combine the inputs required for each call. So for example, there is only a single node that applies all calls to `dtrsm`. This node is invoked when the tiles that hold the inputs and outputs for an invocation are matched together in the tag-matching `join_node` that precedes it. The tag represents the iteration values of the `i`, `j`, `k` loops in the serial implementation at that invocation of the call. There is some overhead in message matching and forwarding, so it may not perform as well as the dependency graph implementation.
11
12This sample code requires a oneTBB library and also the oneMKL library.
13
14## Building the example
15```
16cmake <path_to_example>
17cmake --build .
18```
19
20## Running the sample
21### Predefined make targets
22* `make run_cholesky` - executes the example with predefined parameters.
23
24### Application parameters
25Usage:
26```
27cholesky [size=value] [blocksize=value] [num_trials=value] [output_prefix=value] [algorithm=value] [num_tbb_threads=value] [input_file=value] [-x] [-h] [size [blocksize [num_trials [output_prefix [algorithm [num_tbb_threads]]]]]]
28```
29* `-h` - prints the help for command line options.
30* `size` - the row/column size of `NxN` matrix (size <= 46000).
31* `blocksize` - the block size; size must be a multiple of the blocksize.
32* `num_trials` - the number of times to run each algorithm.
33* `output_prefix` - if provided the prefix will be prepended to output files: <output_prefix>_posdef.txt and <output_prefix>_X.txt; where `X` is the algorithm used. If `output_prefix` is not provided, no output will be written.
34* `algorithm` - name of the used algorithm - can be dpotrf, crout, depend or join.
35* `num_tbb_threads` - number of oneTBB threads.
36* `input_file` - input matrix (optional). If omitted, randomly generated values are used.
37* `-x` - skips all validation.
38