Project 3 Sorting

Author Zhen Tong 120090694@link.cuhk.edu.cn

Projects Home: https://58191554.github.io/project_page.html

Quick Sort with MPI

In the quick sort with multi-process parallel code, the sort is being done in chunks, and the output of the sort function is $P$$P$ number of sorted array. $P$$P$ is the number of process. To fully use all the computing resource, the master is working with slaves, and counted in $P$$P$. In a even divided array, each process is sorting with quick sort algorithm, which is $O(\frac{N}{P}\log \frac{N}{P})$$O(\frac{N}{P}\log\frac{N}{P})$. Then, all the process send the data back to the Master node, which takes $t_{trans}\times N$$t_{trans}\times N$ amount of time. And later, merge $P$$P$ number of sorted array into the output array. The time complexity of merge is $O(N)$$O(N)$, and we use the heap to store the smallest element of $P$$P$ arrays. When the smallest element pops out, we stack the next element of the same array to the heap, which takes $O(\log P)$$O(\log P)$ time. So, the overall merging is $O(N\log P)$$O(N\log P)$, and the overall time complexity of Quick Sort with MPI is

Bucket Sort with MPI

The idea of Bucket Sort is first divide the array into some bucket interval, sorted the bucket, and merge data with $O(1)$$O(1)$. The motivation of this algorithm the merging time is small, however the divide data into bucket can cost $O(N)$$O(N)$. In the MPI code, we first get the range of the data$O(N)$$O(N)$, and then get the each bucket range divided the data range by the bucket number. Then, we allocate the buckets to the processes, and let them do the data division. After that, use insertion sort in each bucket. The master is prepared $M\times N$$M\times N$ space to receive data. $M$$M$ is the number of all buckets, and $N$$N$ is the number of the total array. The MPI_Send() function will send a structure of [#data, data], we need to tell how many data in one bucket, so that the master can move the data into the vector.

Indeed, the number of buckets in a bucket sort algorithm can significantly impact its performance. The choice of the number of buckets affects the balance between the size of each bucket and the number of comparisons and movements required during the sorting process.

Bucket Size:

Having too few buckets may lead to large bucket sizes, which could result in inefficient sorting within each bucket. If a bucket becomes too large, it might be better to use a more efficient sorting algorithm, such as insertion sort, within that bucket. In the experiment, for array size as ${10}^8$$10^8$, bucket size is ${10}^6$$10^6$.

Numerical Analysis

Odd-Even Sort with MPI

The Odd-Even Sort is not a good algorithm in sequential, because it takes $O(N^2)$$O(N^2)$ amount of time. However, because it is not data dependent in each iteration, it is good for parallel. The key point in MPI is the check the edge of the array to see, whether two adjacent process need to exchange data.

There is a trick in this question, we know that the MPI communication can be very expansive, and send the last signal sorted = ture/false can be too trivial to send. Therefore, we can first assume that the with $10$$10$ to $100$$100$ iteration (take $24$$24$ in experiment), we can check sorted for one time. We can do useless multiple iteration in return of saving expensive MPI Communication. For example, if the iteration time itself with out MPI Communication with Master is $t_1$$t_1$, and the total time of communication with master and all slave is $t_2$$t_2$. And we do $n$$n$ times of iteration with one central communication. Then, we are saving amount of time overall.

Merge Sort with OMP(Bonus)

The merge sort is divide into two steps: the independent neighborhood sort, and recursive merge. The Sorting parallel is simple, we set the maximum number n number of thread to sort in n sub-arrays. The most difficult part is the merge parallelism. The way to merge independently and using parallelism first find the position of element $x$$x$ in the right array $Y$$Y$, and the position of $x$$x$ in output array $Z$$Z$ using binary sort. Assume we have $t$$t$ number threads to use in one merge function, we need to fund the position of $x_1,x_2,...,x_{t-1}$$x_1, x_2, ..., x_{t-1}$, then we can let the thread to do sub-merge for $X[i,i+1]$$X[i, {i+1}]$, and $Y[po{s}_Y(x_i),po{s}_Y(x_{i+1})]$$Y[pos_Y(x_i), pos_Y(x_{i+1})]$ , and write the output in the output array $Z[po{s}_Z(x_i),po{s}_Z(x_{i+1})]$$Z[pos_Z(x_i), pos_Z(x_{i+1})]$. The time complexity is $O(t\log N)$$O(t\log N)$ for binary search, plus $O(N/t)$$O(N/t)$ parallel merge.

The binary search mentioned above is not really doing the binary search, but to return the rightmost element of the array.

xxxxxxxxxx
int binarySearch(vi &vec, int val) {
    int low = 0;
    int high = vec.size();

    while (low < high) {
        int mid = low + (high - low) / 2;

        if (vec[mid]<= val) {
            low = mid+1;
        } else {
            high = mid;
        }
    }
    return low; // Returns the rightmost position
}

Although the performance degrade when thread number exceed 16, I try my best to control the thread distribution. The thread thread strategy is like this. Suppose there are $T$$T$ number of threads

• When there are $M$$M$ sorted array being merge, there are $M/2$$M/2$ threads are doing the merging job

• In each merging job, there are $T-M/2$$T-M/2$ threads ideal, therefore I set $k=\frac{T-M/2}{M/2}$$k = \frac{T-M/2}{M/2}$ threads for the parallel merging job for 2 sorted array.

• Therefore, the $k$$k$ threads need to first do $k-1$$k-1$ numbers of binary sequential, and then do $k$$k$ parallel merging between two array.

Performance

My Time Cost

Baseline

• In the speed up, the odd-even algorithm parallel is the most linear-like case, this is because the MPI Communication is evenly distributed into the iteration, and we take a trick that the more slave we need to communicate, the less frequent our loop communicate to check stop.

• The Quick Sort and the Bucket Sort's speedup is not as good as odd-even sort, because the merge of quick sort is sequential, and the heap size of the priority tree is getting bigger in merging state.

• The Bucket Sort's efficiency is better the other 2 sort algorithm, because there is no increase of sequential part.

Profiling Results & Analysis with perf

• Quick Sort

  • Cache Misses and References:

    • The number of cache misses decreases as the number of cores increases, indicating potential improvements in cache utilization.

    • Cache reference percentages show how often cache was successfully referenced. Some variability is observed, possibly due to the nature of the workload or cache behavior.

  • Cache Reference Percentage:

    • Generally, the cache reference percentage increases with the number of cores, suggesting better cache utilization as parallelism increases.

• Bucket Sort

  • Cache Miss:

    • The number of cache misses first increase then decrease, because the increase is because data dependency was destroyed by dividing data into different process. However, the cache misses then decrease because, there are few data to deal with ,and there are also fewer cold cache miss.

• Odd-Even Sort

  • Cache Misses and Cache References:

    • Cache References generally decreases.

    • The cache reference percentage is the percentage of cache references compared to the total number of cache accesses. It indicates the efficiency of cache utilization.

    • The percentage starts relatively low for 1 core and 2 cores, but significantly increases for 4 cores and beyond. This could be due to the parallel nature of the algorithm, where more cores result in a higher rate of cache references.

  • Number of Instructions:

    • The number of instructions executed increases with the number of cores, with the highest value at 16 cores. This increase in instructions may be attributed to the parallelization overhead and the execution of more instructions in parallel across multiple cores.

Recommendations:

• Cache Optimization:

  • Analyze cache miss patterns to identify opportunities for optimization, such as improving cache locality or restructuring data.

• Parallel Efficiency:

  • Evaluate parallel efficiency and scalability by comparing cache references and misses across different core counts.

• Load Balancing:

  • Consider load balancing to ensure an even distribution of work among cores, reducing the potential for cache contention.

How to Run My Code

You can compile the code and run the code with one line.

xxxxxxxxxx
chmod +x run.sh
./run.sh

Or you can manually compile the code, and run the sbatch, the output will be in the log/Project3.txt, and log log/bonus.txt

xxxxxxxxxx
# Compile the src code in build
mkdir build 
cd build
cmake ..
make -j4

# Run
cd ..
sbatch src/sbach.sh
sbatch src/sbach_bonus.sh

Or you can run the tasks separately after compile. The output of perf will be in the log/task*.txt

x
# change permision to +x first
sbatch src/scripts/task1.sh 
sbatch src/scripts/task2.sh 
sbatch src/scripts/task3.sh 

Or you can execute the code with DIY parameter

xxxxxxxxxx
perf_command="perf stat -e cycles,instructions,cache-references,cache-misses"

• xxxxxxxxxx
  srun -n $num_cores --cpus-per-task 1 --mpi=pmi2 $perf_command ${CURRENT_DIR}/../build/src/quicksort/quicksort_mpi ${big_size}
  

• xxxxxxxxxx
  srun -n $num_cores --cpus-per-task 1 --mpi=pmi2 $perf_command ${CURRENT_DIR}/../build/src/bucketsort/bucketsort_mpi ${big_size} ${big_bucket}
  

• xxxxxxxxxx
  srun -n $num_cores --cpus-per-task 1 --mpi=pmi2 $perf_command ${CURRENT_DIR}/../build/src/odd-even-sort/odd-even-sort_mpi ${oddeven_size}
  

perf analysis

using my python code analysis.py it will extract the import data and do statistic for you, using useful regular expression

xxxxxxxxxx
python3 analysis.py 

Appendix

Table of data collected in the perf commend.

Quick Sort with MPI

Bucket Sort with MPI

Odd-Even Sort with MPI