duminică, 9 ianuarie 2011

C# implementation of the parallel sieve of Erathostenes

Update: all the source code for this article can be downloaded from here

This is my implementation of a parallel sieve of Erathostenes in C#.
I got the algorithm from here.
I know I could have used some of the existing C# functionality to manage threads rather than doing it all myself but I found this more convenient at the time.
Anyone is welcomed to bring any corrections.





using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace ParalelErathostenes
{
    /// 
    /// Finds prime numbers starting from 2 and up to a given value
    /// 
    class Program
    {

        /*         
        1. Create a list of natural numbers 2, 3, 4, 5, ….., n.  None of which is marked. Each process 
        creates its share of lists. 
        2. Set k to 2, the first unmarked number on the list. Each process does this. 
        3. Repeat: Each process marks its share of list 
        a. Mark all multiples of k between k² and n. 
        b. Find the smallest number greater than k that is unmarked. Set  k to this new 
        value 
        c. Process 0 broadcasts k to rest of processes. 
        Until k² > n. 
        4. The unmarked numbers are primes. 
        5. Reduction to determine number of primes
        */

        /// 
        /// possible status of each thread used by this program
        /// 
        enum ThreadStatus
        {
            DoingStuff = 0,
            Waiting = 1,
            Dead = 2
        };

        /// 
        /// Statuses for all the threads started
        /// 
        static ThreadStatus[] ThreadStatuses;

        /// 
        /// array that stores wether a number is prime or not true = prime, false = not prime
        /// this array should be as long as the maximum number up to which you want to find primes
        /// 
        static bool[] nums;

        /// 
        /// k from the algorithm above
        /// 
        static int k;

        /// 
        /// n from the algorithm above
        /// 
        static int n;

        /// 
        /// nr of threads that compute primes - this is actually the number of worker threads because one 
        /// extra thread will handle just finding the smallest remainig prime and broadcasting it to all the 
        /// other threads
        /// 
        static int nrThreads;

        /// 
        /// changes status of all worker threads to "DoingStuff"
        /// 
        static void MakeWorkerThreadsDoStuff()
        {
            for (int i = 1; i < nrThreads + 1; i++)
            {
                ThreadStatuses[i] = ThreadStatus.DoingStuff;
            }
        }

        /// 
        /// changes status of all worker threads to "Waiting"
        /// 
        static void MakeWorkerThreadsWait()
        {
            for (int i = 1; i < nrThreads + 1; i++)
            {
                ThreadStatuses[i] = ThreadStatus.Waiting;
            }
        }

        /// 
        /// changes status of all worker threads to "Dead"
        /// 
        static void KillWorkerThreads()
        {
            for (int i = 1; i < nrThreads + 1; i++)
            {
                ThreadStatuses[i] = ThreadStatus.Dead;
            }
        }

        /// 
        /// checks wether at least one of the worker threads is still doning something
        /// 
        /// 
        static bool WorkerThreadsDoingStuff()
        {
            for (int i = 1; i < nrThreads + 1; i++)
            {
                if (ThreadStatuses[i] == ThreadStatus.DoingStuff)
                    return true;
            }
            return false;
        }

        /// 
        /// checks wether at least one of the worker threads is waiting(on stand by)
        /// 
        /// 
        static bool WorkerThreadsWaiting()
        {
            for (int i = 1; i < nrThreads + 1; i++)
            {
                if (ThreadStatuses[i] == ThreadStatus.Waiting)
                    return true;
            }
            return false;
        }

        /// 
        /// checks wether the main thread is in wairing mode
        /// 
        /// 
        static bool MainThreadWaiting()
        {
            return (ThreadStatuses[0] == ThreadStatus.Waiting);
        }

        /// 
        /// checks if all threads are done working and waiting
        /// 
        /// 
        static bool AllThreadsDead()
        {
            foreach (var threadStatus in ThreadStatuses)
            {
                if (threadStatus != ThreadStatus.Dead)
                    return false;
            }

            return true;
        }

        /// 
        /// each thread runs this function it marks non prime numbers within it's given range
        /// between start and stop
        /// 
        /// 

        static void MarkNonPrimes(int ThreadNr)
        {

            while (ThreadStatuses[ThreadNr] == ThreadStatus.Waiting)
            {
                Thread.Sleep(1);
            }

            if (ThreadStatuses[ThreadNr] == ThreadStatus.Dead)
                return;
            //stores how many numbers we have to decide are primes or non primes
            int nrOfNumbers = n - k * k;
            //divide that by the number of threads to get the interval within which each thread should 
            //look for primes
            int interval = nrOfNumbers / nrThreads;

            //for this thread and this value of k start at this value
            int startNumber = k * k + interval * (ThreadNr - 1);
            //and end at this value
            int stopNumber = (ThreadNr == nrThreads) ? n : startNumber + interval;

            lock (nums)
            {
                for (int j = startNumber; j < stopNumber; j++)
                {
                    //Mark all multiples of k between k² and n. 
                    if (j % k == 0)
                        nums[j] = false;
                }
            }

            //nothig to do now but wait
            ThreadStatuses[ThreadNr] = ThreadStatus.Waiting;

            MarkNonPrimes(ThreadNr);
        }

        /// 
        /// this is the main thread's function it manages the worker therads and finds the smallest prime
        /// when the worker threads finish marking non primes
        /// 
        static void FindSmallestPrimeAndBroadcast()
        {
            while (WorkerThreadsDoingStuff())
            {
                Thread.Sleep(1);
            }

            //c. Process 0 broadcasts k to rest of processes. 
            for (int i = k + 1; i < n; i++)
            {
                if (nums[i])
                {

                    k = i;

                    break;
                }
            }
            //Until k² > n. 
            if (k * k > n)
            {
                //kill worker threads
                KillWorkerThreads();
                //commit suicide
                ThreadStatuses[0] = ThreadStatus.Dead;
                return;
            }
            //all worker threads can now read the correct new value of k so they can all get to work
            MakeWorkerThreadsDoStuff();

            FindSmallestPrimeAndBroadcast();
        }

        static void Main(string[] args)
        {

            n = 100;
            nrThreads = 10;

            //add one because one main thread is needed to manage all the others
            ThreadStatuses = new ThreadStatus[nrThreads + 1];

            //1. Create a list of natural numbers 2, 3, 4, 5, ….., n.  None of which is marked.
            nums = new bool[n];
            //suppose all these are primes, we will then start marking them as non primes
            for (int i = 2; i < n; i++)
                nums[i] = true;

            //initialize k with 1, start looking for primes bigger than 1, 1 is not a prime
            k = 1;

            //make sure all threads are waiting so they don't run out and find primes on their 
            //own without the main thread regulating them
            MakeWorkerThreadsWait();

            //this is the main thread
            var _mainThread = new System.Threading.Thread(() => FindSmallestPrimeAndBroadcast());
            _mainThread.IsBackground = true;
            _mainThread.Start();

            //worker threads
            for (int i = 1; i < nrThreads + 1; i++)
            {
                //need to declare this as a locol variable so that the value passed to the thread
                //won't be changed causing chaos
                var localI = i;
                var _workerThread = new System.Threading.Thread(() => MarkNonPrimes(localI));

                _workerThread.IsBackground = true;
                _workerThread.Start();
            }

            //wait for all threads to end
            while (!AllThreadsDead())
            //commenting the line above and decommenting the one below really help with debugging
            //because you don't constantly get sidetracked to AllThreadsDead() when pressing F5
            //while (true)
            {
                Thread.Sleep(1);
            }

            //print the primes you found
            for (int i = 0; i < n; i++)
                if (nums[i])
                    Console.WriteLine(i);
        }
    }
}

Niciun comentariu:

Trimiteţi un comentariu