CODEWITHSUNDEEP
c++multithreadingparallel-processing
Caladin00
Caladin00

Reputation: 356

Can someone help me parallelize this C++ Code?

So I've been tasked with finding a way to parallelize this simple C++ problem. The problem is... I'm really... REALLY struggling with parallel programming concepts and have no idea what to do. The steps to be taken are below:

1) take a positive integer N as an argument
2) create an integer array of size N
3) populate the integers from range [1,1000]
4) Find the largest integer and the sum of the array in parallel
5) print the largest integer and the sum of the array.

It was easy enough until I got to step 4. I have no idea how to parallelize this code. I've heard of concepts like threading and multi-threading but I have next to zero idea how to implement them in C++ and could really use some assistance + detailed explanation with this. I have yet to find a concrete example of a C++ program that has been parallelized that makes sense to me.

#include  <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(){

cout << "Enter the Size of the Array (N):  \n ";
int N;
cin >> N;

int array[N];
int largest_number = 0;
int sum = 0;

srand(time(0));
cout << "Populating Array...\n";

//  Filling up the Array  with values
    for(int i =0; i < N; i++)
    {

    array[i] =  (rand() % 1000) + 1;

    }


// Finding the largest value and calculating sum of the array
    for( int j  = 0; j < N; j++)
    {

    sum += array[j];

    if( array[j] > largest_number)
    {largest_number = array[j];}

    }

cout << "Output: \n";
cout << "Maximum:  " <<  largest_number << ";" <<  "Sum: " <<  sum;
cout << "\n";

 }

As it stands right now, the code works fine. I just need it to show instances of parallel programming.

As far as expectations go, I could implement a timer on the code to check how much faster parallelization will be on this code but I want to make sure it works first. Thanks

Upvotes: 6

Views: 15209

Answers (2)

Jarod42
Jarod42

Reputation: 217245

With C++17 std::reduce:

std::vector<int> array(N);
// ...
const auto sum = std::reduce(std::execution::par, arr.begin(), arr.end(), 0);

Upvotes: 2

Richard
Richard

Reputation: 61289

For many simple parallel problems, OpenMP is going to be your best choice.

It's already included in all C++ compilers, it's a mature industry standard, it offers capabilities to offload to GPUs, and it's minimally invasive to existing code, allowing you to drop back to a serial formulation easily.

Below, I've rewritten your code to leverage OpenMP. I've also made several other changes.

I've dropped the using namespace std line. This line's potentially dangerous because the standard library is big and this pulls all of it into the global namespace where it can potentially conflict with other libraries you might be using.

I've also dropped int array[N]. This code was dangerous to begin with because arrays like this can only really only be defined if N is a compile-time constant. What you really needed was a dynamic allocation. In C++ the best way to do that is with std::vector (see below).

Finally, we get to the for-loop. OpenMP works best for scenarios in which each iteration of the loop is independent. This means that if you'll have difficulty using it with code like a[i]=3*a[i-1]. However, your loop can be made to fit the pattern.

The call to OpenMP:

#pragma omp parallel for reduction(+:sum) reduction(max:largest_number)

tells the computer

Start as many threads as there are cores and divide the loop evenly between these threads. Give each thread its own private copy of the variables sum and largest_number. Once each thread has finished its work, combine the private sum variables into a global sum variable using the + operator. Also, combine all the private largest_number variables into a global largest_number variable using the max operator.

As you can see, this single line is a very succinct representation of what needs to be done. Even if you're planning on using a more complicated framework, such as Intel's Thread Building Blocks or rolling your own with std::thread, OpenMP can be a good way of prototyping a solution. It also plays nicely with TBB and std::thread.

//Compile with g++ main.cpp -fopenmp
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>

int main(){
  std::cout << "Enter the Size of the Array (N): ";
  int N;
  std::cin >> N;

  std::vector<int> array(N);

  //WARNING: This is a poor way of choosing a seed
  srand(time(0));

  std::cout << "Populating Array...\n";
  for(int i =0; i < N; i++)
    array[i] =  (rand() % 1000) + 1; //WARNING: This is a poor way to choose random numbers

  int largest_number = 0;
  int sum = 0;

  // Finding the largest value and calculating sum of the array
  #pragma omp parallel for reduction(+:sum) reduction(max:largest_number)
  for( int j  = 0; j < N; j++){
    sum += array[j];

    if(array[j] > largest_number)
      largest_number = array[j];
  }

  std::cout << "Output: \n";
  std::cout << "Maximum:  " <<  largest_number << ";" <<  "Sum: " <<  sum;
  std::cout << "\n";
}

Upvotes: 15

Related Questions