This project parallelizes the QuickSort and Merge Sort algorithms using OpenMP. Our goal was to practice parallelization and build a useful tool for team Sunergy. Team Sunergy is Appalachian State University's solar vehicle racing team. Data is collected from the battery management system at the race each year. The data contains over thirty variables such as state of charge, highest/lowest cell volt, pack current charge limit, and highest/lowest cell temperature. The battery management system of the car constantly outputs data and the dataset therefore scales quite rapidly. For example, in the period from Wed Jul 21 17:34:07 PDT 2021 to Thu Jul 22 00:27:15 PDT 2021 (Roughly 7 Hours) the BMS generated 78,210 data points. Our program parallelizes the sorting of this data using QuickSort & Merge Sort. The program scans in the comma separated value dataset and populates the data structure. We organized the data into a structure of structures grouping similar variables together. The bmsData structure contains pack, cell, and hiLo data sub structures. The end user can scan in a csv dataset and then choose which variable to sort the data upon.
1. Setup: Clone the repo on a server such as App State's student2 machine.2. Compile: Run the 'make' command found within the makefile.
3. Run: ./sorter -n {X} -t {Y} -- X = 2^# of arrays -- Y = # of threads.
4. Commands: -m runs MergeSort, -q runs QuickSort, ./sorter -h provides information.
- Sequential & Parallelized QuickSort
- Sequential & Parallelized Merge Sort
- Speedup comparison between algorithms
- Created a tool which the solar vehicle team could use and expand upon
- Practiced parallelization
- Learned how to parse & import CSV data
- Learned more about valgrind and gdb
- GPU QuickSort
- Sorting the data on the varibale of choice.
- "Data Collection and Analysis Techniques for Solar Car Telemetry Data"
https://solarcar.mst.edu/wp-content/uploads/sites/14/2019/10/Data-Collection-and-Analysis-Techniques-for-Solar-Car-Telemetry-Data.pdf
- Sample Data Sets: data.world
https://data.world/datasets/solar
- "Parallel Depth First Search, Part 1: Implementation"
https://www.lrde.epita.fr/~bleton/doc/parallel-depth-first-search.pdf
- Section 3.2 of textbook: "Parallel Programming, Concepts and Practice"
By Bertil Schmidt, Jorge Gonazales-Dominguez, Christian Hundt, & Moritz Schlarb
Parallel Programming, Concepts and Practice
- "How can I read and parse CSV files in C++?"
https://stackoverflow.com/questions/1120140/how-can-i-read-and-parse-csv-files-in-c
- "Quicksort: an improved GPU-based implementation of quicksort"
By Emanuele Manca, Andrea Manconi, Alessandro Orro, Giuliano Armano and Luciano Milanes.
Quicksort: an improved GPU-based implementation of quicksort
- "GPU-Quicksort: A Practical Quicksort Algorithm for Graphics Processors"
By Daniel Cederman and Philippas Tsigas
GPU-Quicksort: A Practical Quicksort Algorithm for Graphics Processors
- Advice and Guidance from Dr. Cindy Norris
Professor of Computer Science, Appalachian State University
https://compsci.appstate.edu/faculty-staff/dr-cindy-norris
- Team Sunergy Private Dataset
cellvoltages_2021-07-21-17-34-00
| # Hours | Date / Time | In Class Yes/No | Description | Person |
|---|---|---|---|---|
| 4 (2 x 2) |
6/15/22 2 - 4p |
Y | Picking a topic & starting research | LWR & IMA |
| 1.5 |
6/16/22 11 - 12:30p |
N | Reading about GPU Quicksort | IMA |
| 1 |
6/16/22 1 - 2p |
N | Article Reading | LWR |
| 5 (2.5 x 2) |
6/16/22 2 - 4:30p |
Y | Read QuickSort article, setup codebase, gpuquicksort.cu & makefile | LWR & IMA |
| 2 |
6/17/22 2 - 4p |
N | Debugging makefile, working on Gpuquicksort, organizing codebase | LWR |
| 2.75 |
6/17/22 2:30 - 5:15p |
N | Structuring the build files and layout of the codebase | IMA |
| 1 |
6/17//22 8 - 9p |
N | Reading Quicksort documentation | LWR |
| 5.32 (2.66 x 2) |
6/18/22 8 - 10:40p |
N | Implementing Host logic | LWR & IMA |
| 6 (3 X 2) |
6/20/22 9:30 - 12:30p |
N | CPU Kernel implementation & consulting with Dr. Norris | LWR & IMA |
| 5 (2.5 x 2) |
6/20/22 2 - 4:30p |
Y | Research, consulting with Dr. Norris, GPUQuickSort | LWR & IMA |
| 8 (4 x 2) |
6/20/22 8:30 - 12:30a |
N | BMS Data entry pair programming session | LWR & IMA |
| 2 (1 x 2) |
6/21/22 10 - 12p |
N | Debugging sorter.cu | LWR |
| 3 (1.5 x 2) |
6/21/22 12:30 - 2p |
N | Debugging code | LWR & IMA |
| 5 (2.5 x 2) |
6/21/22 2 - 4:30p |
Y | Code Compiling, Further Debugging | LWR & IMA |
| 0.75 |
6/21/22 4:30 - 5:15p |
N | Debugging | IMA |
| 6 (3 x 2) |
6/21/22 9:45 - 12:45a |
N | Resolved Execution Bugs | LWR & IMA |
| 1.75 |
6/22/22 7 - 8:45a |
N | Optimizing Memory Access | IMA |
| 0.5 |
6/22/22 9 - 9:30a |
N | Further Investigations | IMA |
| 6 (3 x 2) |
6/22/22 10 - 1p |
N | Implementing Algorithm, debugging, documenting code, updating readme, & creating power point presentation. | LWR & IMA |
| 5 (2.5 x 2) |
6/22/22 2 - 4:30p |
Y | Work on presentation, redesign git repo, rework readme, mergesort is now running | LWR & IMA |
| 8 (4 x 2) |
6/22/22 5 - 9p |
N | Creating presentation, polishing readme, debugging sorting algorithms to increase speedup. | LWR & IMA |
| 8 (4 x 2) |
6/23/22 9:30 - 1:30p |
N | Refactored algorithms, fixed speedup issue, created sorted CSV download, polished presentation & readme | LWR & IMA |