Thread: Sieve of eratosthenes in MPI. Internal loop only

  1. #1
    Registered User
    Join Date
    Oct 2020

    Sieve of eratosthenes in MPI. Internal loop only

    Hello everyone,

    I'm trying to parallelize with the mpi library and c++ the internal loop of the following sequential code (sieve of eratosthenes):

    int main()
        int n = 40;
        int root = std::sqrt(n);
        int count = 0;
        bool* range = new bool[n];
        for (int i = 0; i < n; i++)
            range[i] = true;
        for (int i = 2; i <= root; i++)
            if (range[i])
                //Loop to be parallelized
                for (int j = i * i; j < n; j += i)
                    range[j] = false;
        for (int k = 2; k < n; k++)
            if (range[k])
        printf("Primes: %d", count);
    I do not seek to parallelize the external loop, which although it would be a better solution, I must compare both performances.

    In other words, I would like to parallelize the distribution of the elimination of multiples, which occurs when the range [j] takes the value of false

    Thank you in advance.

  2. #2
    Registered User
    Join Date
    Sep 2020
    It doesn't appear that you've asked a specific question but rather have asked for help generally? Could I ask: Are you expecting other people to write your code for you? I suggest that you at least show an attempt to find a solution - problem solving is at the heart of programming and quite frankly, there is no substitute for it.

    I personally would start by refactoring your code so that the inner loop is in a function of its own - I think that on its own would aid with parallelization. I would then suggest you try reading more about MPI because the way you have asked your question would suggest you aren't that familiar with it (honestly, nor am I). After reading your question I spent 10 minutes or so reading this article (MPI Hello World * MPI Tutorial) and understood the basics, I would suggest you do something similar. E.g. Notice how in that example there is only 1 call to printf but 4 lines are printed? (Because of the parallelization). From what I can tell, the 'magic' happens between the MPI_Init and MPI_Finalize calls. If I were you, I would also look at some other examples found here: mpitutorial/tutorials at gh-pages * mpitutorial/mpitutorial * GitHub and try to learn from example code. At least that way you can attempt to solve the problem yourself and you can at least try to ask a more specific question if you are having problems. Sometimes its easier to solve concrete bugs when you've got something that mostly works rather than asking very general questions.. and you've asked a very general question.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sieve of Eratosthenes
    By hoandini in forum C Programming
    Replies: 1
    Last Post: 10-24-2018, 04:02 PM
  2. Sieve of Eratosthenes
    By Hodor in forum C Programming
    Replies: 9
    Last Post: 11-27-2013, 02:16 AM
  3. Sieve of Eratosthenes
    By Eman in forum C++ Programming
    Replies: 26
    Last Post: 01-26-2011, 05:23 AM
  4. Sieve of Eratosthenes
    By darren78 in forum C++ Programming
    Replies: 0
    Last Post: 04-28-2010, 10:52 AM
  5. Sieve of Eratosthenes
    By jack_carver in forum C++ Programming
    Replies: 7
    Last Post: 04-13-2010, 10:33 PM

Tags for this Thread