Non-Specultive Data-Driven Parallelizations of Irregular Algorithms for Sparse Matrices Reordering

This project aims the parallelization of some algorithms for the bandwidth and wavefront reduction problems. The related algorithms are:

• Reverse Cuthill McKee - RCM (Bandwidth Reduction)
• Sloan (Wavefront Reduction)

Dependencies

On linux, execute the command to install libraries used by the program:

sudo apt-get install cmake libboost-all-dev gfortran libblas-dev

Running

./reordering-library -m <path of .mtx file> -a <algorithm> -p <number of threads> -b <percent of chunk>
<algorithm>

• 0: Serial RCM
• 1: Serial Sloan
• 2: HSL RCM
• 3: HSL Spectral
• 4: HSL Sloan
• 5: Unordered RCM
• 6: Leveled RCM
• 7: Bucket RCM
• 8: Relaxed Order Sloan
• 9: Boost RCM
• 10: Boost Sloan
• 11: Logical Bag Sloan
• 12: Shrinked RCM

<percent of chunk>

• It is recommended the value of 0.5.

Example:

./reordering-library -m ./Matrices/rail_5177.mtx -a 5 -p 4 -b .5

• In this example, the matrix rail_5177 is processed by the Unordered RCM algorithm. It is executed with 4 threads.

Profiling

valgrind --leak-check=yes myprog arg1 arg2

• For memory check, Valgrind has been used.

valgrind --tool=callgrind program [program_options]

• For performance profiling, Callgrind has been used.

kcachegrind callgrind.out.XXX

• For graphical performance visualization, KCachegrind has been used. The file callgrind.out.XXX is yielded by Callgrind, and XXX is the process identifier.