lundi 27 août 2018

Confusion in Multithreading in C++

I am trying to simulate a probability problem, in which there are n clients and n servers. Each client randomly sends a request to any server, so each server can receive any number of requests, I have to calculate the expected number of maximum requests that any server can receive.

I am trying to simulate this by running 10,000 iterations, where in each iteration each client chooses a random server and a request is sent to it, servers are represented as an integer array of size N.

Client chooses a random number and then the value at that index in server array is incremented. As, for better results the question says N should be about 106.

So to make it a little faster , I used multithreading in which each thread runs 100 iterations and in total there are 10 threads.

But the multithreaded code produces very different results as that from normal code. Below are the code snippets with output for both of them

Normal Version

 #include <iostream>
 #include <random>
 #include <chrono>

 #define N 1000000
 #define iterations 1000

int servers[N];

// This array's i'th index will contain count of in how many
// iterations was i the maximum number of requests received by any  server
int distr[N+1]={0};

int main(int argc, char const *argv[])
{   
   // Initialising
   auto start = std::chrono::high_resolution_clock::now();

   std::srand(time(NULL));

   // Performing iterations
   for(int itr=1; itr<=iterations; itr++)
   {
       for(int i=0;i<N;i++)
       {
           servers[i]=0;
       }

       for(int i=1;i<=N;i++)
       {
           int index = std::rand()%N;
           servers[index]++;
       }

       int maxRes = -1;
       for(int i=0;i<N;i++)
       {
           maxRes = std::max(maxRes, servers[i]);
       }
       distr[maxRes]+=1;
   }

   for(int i=0;i<=15;i++)
   {
      std::cout<<(double)distr[i]<<std::endl;
   }

   auto stop = std::chrono::high_resolution_clock::now();
   auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
   std::cout<<duration.count()<<" milliseconds"<<std::endl;

   return 0;
}

Output

0
0
0
0
0
0
0
359
552
79
10
0
0
0
0
0
1730 milliseconds

Multithreaded Version

#include <iostream>
#include <random>
#include <chrono>
#include <thread>
#include <fstream>

#define N 100000
#define iterations 1000
#define threads 10

// This array's i'th index will contain count of in how many
// iterations was i the maximum number of requests received by any server
std::atomic<int> distr[N] = {};

void execute(int number)
{
    // Performing iterations
    int servers[N]={0};
    for(int itr=1; itr<=number; itr++)
    {

        for(int i=1;i<=N;i++)
        {
            int index = std::rand()%N;
            servers[index]++;
        }

        int maxRes = -1;
        for(int i=0;i<N;i++)
        {
            maxRes = std::max(maxRes, servers[i]);
            servers[i]=0;
        }

        distr[maxRes] += 1;
    }
}

int main(int argc, char const *argv[])
{   
    // Initialising
    auto start = std::chrono::high_resolution_clock::now();

    std::srand(time(NULL));

    std::thread t[threads];
    for(int i=0;i<threads;i++)
    {
        t[i] = std::thread(execute, iterations/threads);
    }   

    for(int i=0;i<threads;i++)
    {
        t[i].join();
    }

    for(int i=0;i<=15;i++)
    {
        double temp = (double)distr[i];
        std::cout<<i<<"\t"<<distr[i]<<std::endl;
    }

    auto stop = std::chrono::high_resolution_clock::now();

    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
    std::cout<<duration.count()<<" milliseconds"<<std::endl;

    return 0;
}

Output

0   0
1   0
2   0
3   0
4   0
5   0
6   0
7   7
8   201
9   421
10  267
11  68
12  2
13  2
14  4
15  0

1385 milliseconds

Whereas I have run the normal code many times and each times the count for maximum = 9 > 500, and there is not so much scattering of data, I mean only maximum = 8,9,10,11 have significant values rest all are zeroes.

Can anyone please explain what am I doing wrong ?

Thanks in advance!




Aucun commentaire:

Enregistrer un commentaire