Home Github hello@fazalkhan.net

Parallel binary search using Open MPI

Explanation

Binary search is a search algorithm that can search through sorted data in O(log n) time complexity.

I wanted to implement a parallelised search algorithm utilising binary search, mainly to remind myself of how MPI works.

Below is code that does the following:

Code

#include <mpi.h>

#include <stdexcept>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>

/* binary search algorithm that searches for an number in a list */
bool binarySearch(int target, const std::vector<int> &list)
{
int low = 0;
int high = list.size() - 1;
int mid = (low + high) / 2;

while (low <= high)
{
int candidate = list[mid];

if (candidate == target)
return true;

if (target < candidate)
high = mid - 1;

if (target > candidate)
low = mid + 1;

mid = (low + high) / 2;
}

return false;
}

int main(int argc, char *argv[])
{
MPI_Init(&argc, &argv);
int rank;
int number_of_processors;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &number_of_processors);

/* length of the random number list we will create */
int length = 1000;
int target;

std::vector<int> send_counts;
std::vector<int> displacements;
std::vector<int> list;

/* processor 0 does all the work in creating the list and allocating the number list to all processors */
if (rank == 0)
{
/* Create a random array of numbers, between 0 and 100000 */
for (int i = 0; i < length; i++)
list.push_back(rand() % 100000);

srand(time(NULL));

/* Randomly pick the index for a value we are searching for. Otherwise pick a value that cannot be found */
int selectBit = rand() % 2;
int index;

if (selectBit)
{
index = rand() % (length - 1);
target = list.at(index);
}
else
{
target = 200000;
}

/* number of elements to send to each process */
int load = list.size() / number_of_processors;
int allocated = 0;

/* this loop basically allocates work to each processor */
for (int i = 0; i < number_of_processors; i++)
{
send_counts.push_back(load);
displacements.push_back(allocated);

/* send the load size to other processes so they can create appropriately sized buffer to receive the data */
MPI_Send(&load, 1, MPI_INT, i, 0, MPI_COMM_WORLD);

if (number_of_processors == send_counts.size())
break;

allocated += load;

/* split remaining total load evenly */
load = (list.size() - allocated) / (number_of_processors - send_counts.size());
}
}

int size_of_receive_buffer;

MPI_Recv(&size_of_receive_buffer, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

std::vector<int> rec_buf(size_of_receive_buffer);

/* scatter the list of random numbers to each processor, based on the load they are calculated to receive */
MPI_Scatterv(&list[0], &send_counts[0], &displacements[0], MPI_INT, &rec_buf[0], size_of_receive_buffer, MPI_INT, 0, MPI_COMM_WORLD);

/* Each array sorts the received data, ready to run binary search */
std::sort(rec_buf.begin(), rec_buf.end());

/* run binary search on the vector of data */
bool result = binarySearch(target, rec_buf);

/* This will be used to aggregate the results */
bool *final_result = nullptr;

/* gather all the search results to process 0 */
MPI_Gather(&result, 1, MPI_CXX_BOOL, &final_result, 1, MPI_CXX_BOOL, 0, MPI_COMM_WORLD);

if (rank == 0)
{
final_result = new bool[number_of_processors];

bool found = false;

/* loop through and check which processors had the matching value */
for (int i = 0; i < number_of_processors; i++)
{
if (final_result[i])
{
std::cout << "processor " << i << " has found the target value of " << target << std::endl;
found = true;
}
}

if (!found)
std::cout << "the target value of " << target << " cannot be found!" << std::endl;

delete[] final_result;
}

/* Do necessary clean up*/
MPI_Finalize();
return 0;
}