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
///
///
/// checks wether at least one of the worker threads is waiting(on stand by)
///
///
/// checks wether the main thread is in wairing mode
///
///
/// checks if all threads are done working and waiting
///
///
/// 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