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#.

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