QTreeInpla

Quadtree-based sparse linear algebra implementation in Inpla.

How to run golden tests

Ensure dotnet is installed.

1. Clone patched Inpla repository at Lamagraph/inpla
2. make to compile Inpla executable
3. Make sure you are in the project directory (Inpla's use directives are relative to current working directory)
4. dotnet fsi test.fsx -- $PATH_TO_INPLA_EXECUTABLE or simply ./test.fsx $PATH_TO_INPLA_EXECUTABLE

Experiments

How to run

• Make threaded patched Inpla from experiments or memory branch:

git clone https://github.com/Lamagraph/inpla.git -b experiments

make -C inpla thread

• Use ulimit -s unlimited for unlimited stack

• Run ./scripts/run_experiments.sh $PATH_TO_INPLA $MAX_THREADS $NUMBER_OF_RUNS $(bfs|tc|sssp) to run all experiments in ./experiments_$(bfs|tc|sssp)/ directory and collect the results OR run the experiments yourself: ./inpla/inpla -f ./experiments_bfs/bcspwr10.in -t 4 -Xms 22 -Xmt 0 > ./my_4threaded_result.txt

• ./scripts/run_experiments_bybyte.sh may be used in combination with Lamagraph/inpla's memory branch to use equal amounts of memory for each matrix and number of threads specified. You will have to calculate memory required for running on a single thread ahead of time (see lines 35-40 in ./scripts/run_experiment_bybyte.sh)

• In experiments Lamagraph/inpla, use -Xmt 0 to disable geometric memory consumption. Use -Xms 22 or greater to use more memory from the start. Note, that increasing the number of threads will multiply the amount of memory used, make sure to modify launching arguments accordingly

• After ./scripts/run_experiments.sh you can ./scripts/results_to_data.fsx $(bfs|tc|sssp) to extract data on algorithm time and conversion time ready to be plotted

• Download mtx matrices from SuiteSparse matrix collection and convert them to experiments using ./scripts/mtx_to_experiment.fsx $PATH_TO_MTX_MATRIX $(bfs|tc|sssp)

How to preprocess graphs

Reordering may help in cases, when the graph doesn't have a sparsity pattern.

You can use ./scripts/simple_mtx_reordering.py to reorder matrices stored in mtx files.

python reorder_mtx.py input.mtx output.mtx --method rcm

For visual control of reordering you can use ./scripts/draw_mtx_sparsity.py

python spy_mtx.py original.mtx original_spy.png --title "Original Matrix"

Examples of reordering

Original	Reordered
webbase-1M.mtx
coAuthorsCiteseer.mtx
arc130.mtx