OpenMP_Mergesort

C++ OpenMP MergeSort

Merge sorting integers using the OpenMP library for paralleization. Pthreads nor C/C++ atomics are used to manage/synchronize threads. This program sorts a (specified) .txt file of unique integers and outputs the sorted list to a different (specified) .txt file. The input .txt file will be an unsorted data structure [Standard Template Library (STL) vector].

Sorting Algorithms:

1. Mergesort - divides into two halfs, then merges sorted halfs

MergeSort using OpenMP

Utilizing OpenMP with MergeSort has proven to be easier to implement, though skeptical in a sense of what's really going on outside of the documentation. There was also no documentation for utilizing a while loop in a parallel manner, so ended up using a single thread to accomplish those. Overall, though it was easier to implement OpenMP than pthreads, it's was worth the extra time before to see how everything was being setup within the code itself.

Testing:

• Compare OpenMP MergeSort against a sorted array (using sort()) to ensure array was properly sorted.
• Comparing execution time on OpenMP MergeSort against the traditional MergeSort (single threaded).

---

🗄️ Code Organization

📁 Files

1. main.cpp - primary C++ file for program execution
2. Makefile - create executable objects; C++14
3. arg_parser.h - error handling and parsing for program's input options
4. README.pdf - write-up for project

💾 Additional file

1. randomNumberGen.cpp- creates a text file with a specified number of random numbers from [ 1 - number size ]. Default number is 10,000 unless specified when ran (as second argument).
2. pthread_add.h - threading if compiling on macOS (will still run as normal for linux systems)

Compiling

Note: If zipped, first unzip file before proceeding.

1. From root directory, run make from the terminal. This will generate a program called mysort
2. Additionally, if wanting to create a text file (source.txt) of randomly generated numbers (repeatable), run make numGen from the terminal. Then, ./numGen <amount of numbers to generate>. If a second argument isn't passed in (./numGen), the program will generate a 10,000 random numbers (between 1 and 30,000) by default.
3. Next, follow execution syntax below for parallel algoritm sorting.
4. Make clean will remove all file generated by make, to include make numGen.

Execution

Program option/input parameters

mysort [--name] OR mysort [source.txt] [-o out.txt]

1. mysort --name: prints name to console.
2. source.txt: unsorted txt file of numbers, with each number on a new line
3. -o out.txt: sorted txt file of numebrs, in which the program outputs/writes to

• Additional outputs: time of execution in nanoseconds and seconds

🐜 Surviving Bugs

• None noted

Resources

1. pragma directives
2. OpenMP from bowdoin.edu