Hypercube Sort In C++

Hypercube Sort stands as a parallel sorting technique adept at organizing substantial data volumes across multiple processors with efficiency. Rooted in the hypercube framework, each processor and node represent vertices within an n-dimensional hypercube. The fundamental strategy involves leveraging the hypercube's layout to conduct exchanges and evaluations, aiming to reduce communication expenses and equitably spread out the sorting tasks. By employing a looping mechanism reliant on the binary representation of each node's (processor's) position, this method arranges data within the hypercube. Nodes engage in continuous communication with adjacent nodes in successive stages to interchange elements and synchronize data sorting operations.

Key Concepts of Hypercube Sort:

Several concepts of the Hypercube Sort in C++ are as follows:

• ✅ Hypercube Topology: A hypercube of dimension n contains 2^n nodes. If the difference between any two nodes' addresses each of which is an n-bit binary number is exactly one bit, then the nodes are connected.
• ✅ Parallel Processing: In the interaction between the processors, the hypercube shape helps greatly because they now have to share the dataset, which is divided among them. The neighbors of each processor are responsible for sorting the data portions that they own and communicating with their immediate neighbors to create a globally sorted array.
• ✅ Recursive Sorting: The method reduces the initial problem by breaking it down into various little sub-problems and dealing with them parallelly, which fits the processors' way of working.

Basic Steps Followed in Hypersort Cube:

• ✅ Distribution of Data: The data is first partitioned and distributed across the nodes of the hypercube.
• ✅ Dimension-wise Sorting: At each stage of this algorithm, the hypercube is sorted according to one particular dimension. For instance, considering one of the dimensions, each node along that dimension will compare and swap data with its neighbor so that data will be moved closer to where it should be placed.
• ✅ Recursive halving: Use the form of the hypercube by recursively halving the amount of data that needs to be sorted at each step.
• ✅ Final Merge: When all dimensions have been sorted recursively, the sorted data is integrated across all nodes.

Consideration for Implementation Using C++:

• ✅ Parallel Libraries: During the implementation of a hypercube sort in C++ , parallel libraries like MPI (Message Passing Interface) could be used to manage connections among processors.
• ✅ Distributed Data Structures: Because the data is partitioned across many CPUs , sorting and collection of local data entails some amount of work.
• ✅ Efficiency: For large-scale parallel processing systems, hypercube sort will be very effective due to the balanced workload it maintains with minimized processor communication.

Example:

Step 1:

Install MPI Library:

UBUNTU COMMANDS:

sudo apt-get update
sudo apt-get install openmpi-bin openmpi-common libopenmpi-dev

Step 2: Compile using MPI Compiler:

mpic++ -o hypercube_sort hypercube_sort.cpp

Step 3: Command For Running MPI Compiler:

mpirun -np 4 ./hypercube_sort

Code:

#include <mpi.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>  // for log2

// Function to perform Hypercube Sort on the local data
void hypercubeSort(std::vector<int>& localData, int processRank, int totalProcesses) {
    int dimensions = log2(totalProcesses);  // Determine the dimension of the hypercube

    for (int d = 0; d < dimensions; ++d) {
        // Sort local data
        std::sort(localData.begin(), localData.end());

        // Determine partner process based on current dimension
        int partnerRank = processRank ^ (1 << d);  // Calculate partner process rank
        std::vector<int> partnerData(localData.size());

        // Send and receive data with the partner process
        MPI_Sendrecv(localData.data(), localData.size(), MPI_INT, partnerRank, 0, 
                     partnerData.data(), partnerData.size(), MPI_INT, partnerRank, 0, 
                     MPI_COMM_WORLD, MPI_STATUS_IGNORE);

        // Merge local data with received partner data
        std::vector<int> mergedData(localData.size() + partnerData.size());
        std::merge(localData.begin(), localData.end(), partnerData.begin(), partnerData.end(), mergedData.begin());

        // Select the correct half of the merged data based on process rank
        if (processRank < partnerRank) {
            localData.assign(mergedData.begin(), mergedData.begin() + localData.size());
        } else {
            localData.assign(mergedData.begin() + localData.size(), mergedData.end());
        }
    }
}

int main(int argc, char** argv) {
    MPI_Init(&argc, &argv);  // Initialize the MPI environment

    int processRank, totalProcesses;
    MPI_Comm_rank(MPI_COMM_WORLD, &processRank);  // Get the rank of the current process
    MPI_Comm_size(MPI_COMM_WORLD, &totalProcesses);  // Get the total number of processes

    // Initialize local data on each process with a different set of values
    std::vector<int> localData = {processRank * 3 + 5, processRank * 3 + 6, processRank * 3 + 7};  // Sample data for each process

    // Perform Hypercube Sort
    hypercubeSort(localData, processRank, totalProcesses);

    // Display sorted data in each process
    std::cout << "Process Rank " << processRank << ": ";
    for (int num : localData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    MPI_Finalize();  // Finalize the MPI environment
    return 0;
}

Output:

Rank 0: 1 2 
Rank 1: 3 4 
Rank 2: 5 6 
Rank 3: 7 8

Conclusion:

In the Hypercube Sort algorithm, the distribution of sorting tasks is decentralized across multiple processors to minimize communication overhead and maximize sorting efficiency. This method involves dividing the data into segments and dispersing them among neighboring nodes based on their binary addresses. As a result, Hypercube Sort can concurrently arrange extensive datasets, serving as a highly effective parallel sorting approach that significantly reduces the sorting time within distributed systems. The C++ implementation of Hypercube Sort utilizes MPI to illustrate how tasks collaborate to achieve global sorting while executing local sorting operations and inter-process communication. This feature renders the algorithm exceptionally competitive in the realm of high-performance computing, where substantial parallelism is crucial for ensuring the effectiveness of sorting methods in distributed memory architectures.