Q2 project README

s307995 Robert Schwartz, s308685 Giovanni Gaddi, s317998 Alessandro Bianco

2023/4 Winter Exam Session

Compatibility:

All programs can be compiled on Ubuntu 22.04.3 LTS with g++ 11.4.0. Alternatively, all programs with the exception of the external METIS comparison implementation can be compiled on Windows 10 with g++ 13.2.0 (MSYS2 project). The implementation relies solely on standard libraries, without using Boost. For faster execution output can always be piped to /dev/null. Note that the ./bin directory may have to be created.

Compile and Run our METIS Implementation:

Compile:

g++ -o ./bin/mtmetis.exe ./src/mtmetis.cpp

Run:

./bin/mtmetis.exe nThreads nPartitions maxDeviation inputFile outputFile cutoffSize partitioningAlg
- nThreads: number of threads for partitioning
- nPartitions: the final number of partitions desired
- maxDeviation: tolerance for partition weights
- inputFile: address of the input file
- outputFile: address to save the result
- cutoffSize: size below which partitioning can occur
- partitioningAlg: -g for greedy or -kl for KL

Examples:

.\bin\mtmetis.exe 4 7 1.20 resources\metismodels\x1000y2000m20q20.metis outputmetis.kl 50 -kl
4 Threads, 7 Partitions, 1.20 max deviation, Use of 1000 nodes and 2000 edges metis model graph, 50 cutoff size using KL for cutting
.\bin\mtmetis.exe 5 2 1.05 resources\metismodels\x400y800m20q20.metis outputmetis.g 20 -g
5 Threads, 2 Partitions, 1.05 max deviation, Use of 400 nodes and 800 edges metis model graph, 20 cutoff size using greedy algorithm for cutting

Compile and Run our KL Implementation:

Compile:

g++ -o ./bin/KL.exe ./src/KL.cpp

Run:

./bin/KL.exe nThreads nPartitions input_filename output_filename mode
- nThreads: number of threads (affecting only reading in KL sequential mode)
- nPartitions: the final number of partitions desired
- input_filename: address of the input file
- output_filename: address to save the result
- mode: -rr for round robin or -b for blob

Examples:

.\bin\KL.exe 7 7 resources\metismodels\x400y800m20q20.metis outputkl.rr -rr
7 Threads, 7 Partitions, Use of 400 nodes and 800 edges metis model graph in mode round robin
.\bin\KL.exe 2 3 resources\metismodels\x200y400m20q20.metis outputkl.b -b
2 Threads, 3 Partitions, Use of 200 nodes and 400 edges metis model graph in mode blob

METIS Models and Testing:

./resources/metismodels contains various Metis-type model input files, generated using our custom script genmetis.py (provided in ./resources). Each file structure is xaaaaybbbbmccqdd.metis:

- xaaaaybbbb: number of nodes and edges
- mcc: maximum value of node weights
- qdd: maximum value of edge weights

CutSize and Cut Quality Calculation:

Use CutSizeCalc.cpp to calculate cutsize and cut quality (deviation from ideal cut).

Compile:

g++ -o ./bin/CutSizeCalc.exe ./src/CutSizeCalc.cpp

Run:

./bin/CutSizeCalc.exe input_filename output_filename nThreads
- input_filename: address of the input file
- output_filename: address to save the result
- nThreads: number of threads for the file reader

Examples:

.\bin\CutSizeCalc.exe resources\metismodels\x400y800m20q20.metis outputmetis.kl 7
Using 7 threads for reading, original graph on metis model 400 nodes and 800 edges
output file with partitions generated by metis using kl
Output is printed in line

Installing and Running MT-METIS (State of the art comparison option):

Run the following commands in bash (note that the comparison output file does not match our output file type):

curl https://dlasalle.github.io/mt-metis/releases/mt-metis-0.7.2.tar.gz | tar -xz
cd mt-metis-0.7.2; ./configure; make; make install
apt-get install sysstat
sudo apt install zsh -y
g++ ./q2/src/mtmetis.cpp -o ./q2/bin/mtmetis.exe; chmod +x ./q2/bin/mtmetis.exe
./mt-metis-0.7.2/build/Linux-x86_64/bin/mtmetis -T 4 ./resources/metismodels/x10000y20000m20q20.metis 10 test.part