← Back to index

First shot at Multithreading

Todd
#10385
I've watched a couple of the Multithreading HH episodes, but this is my first time actually implementing it. This is in C#, but it's pretty clear what I'm trying to do:

This entire program does several things with prime numbers, but the part I'm going to post is mainly focused with printing out all prime numbers starting at a high number all the way until it reaches 1. This was not originally intended to be a multi-threaded program, but I wanted to check out some large numbers (I actually have an overload that takes a BigInteger type I will eventually use) and I was watching the computer get bogged down whilst only using 20% of the CPU. In comes multithreading.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 public void printAllPrimes(int number)
            {
                Console.WriteLine(
                    isItPrime(number)
                        ? "{0} is prime. Below are all prime numbers between it and 1:\n"
                        : "{0} is not prime but below are all prime numbers between it and 1:\n", number);
    
                int holder = number;
                
                    while (--holder > 1){
                        if (isItPrime(holder))
                            Console.WriteLine("{0} \t Thread {1}", holder, Thread.CurrentThread.ManagedThreadId);
                }
            }


    public bool isItPrime(int number)
            {
                if (number <= 1){ 
                    return false;
                }
                //We don't want to decrement the number because we need it for the comparisons, so we use holder.
                int holder = number;
    
                while (--holder > 1){
                    //Divisible = divide by a number and get no remainder.
                    if (number % holder == 0){
                        return false;
                    }
                    
                }
                return true;
            }


    static void Main(string[] args)
            {
                Program program = new Program();
                Console.WriteLine("Enter an integer and find out whether it is prime, and find primes all the way down to 1!\n");
                int userEntry = 0;
                while (!Int32.TryParse(Console.ReadLine(), out userEntry)){
                    Console.WriteLine("Enter a valid integer!");
                }
    
                int split = userEntry / 6;
                int[] workChunk = new int[6];
                for (int i = 0; i < 6; i++){
                    workChunk[i] = (userEntry - split);
                    userEntry -= split;
                }
                Thread t1 = new Thread(p => program.printAllPrimes(workChunk[0]));
    
                Thread t2 = new Thread(p => program.printAllPrimes(workChunk[1]));
    
                Thread t3 = new Thread(p => program.printAllPrimes(workChunk[2]));
    
                Thread t4 = new Thread(p => program.printAllPrimes(workChunk[3]));
    
                Thread t5 = new Thread(p => program.printAllPrimes(workChunk[4]));
    
                Thread t6 = new Thread(p => program.printAllPrimes(workChunk[5]));
    
                t1.Start();
                t2.Start();
                t3.Start();
                t4.Start();
                t5.Start();
                t6.Start();
                
    
            }

The good news is, I got the CPU up and they are indeed printing output like this sample:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
   883      Thread 7
    881      Thread 7
    877      Thread 7
    863      Thread 7
    859      Thread 7
    857      Thread 7
    853      Thread 7
    839      Thread 7
    829      Thread 7
    827      Thread 7
    823      Thread 7
    3733     Thread 4
    3727     Thread 4
    2731     Thread 5
    2729     Thread 5
    1511     Thread 6
    1499     Thread 6
    1493     Thread 6
    1489     Thread 6
    1487     Thread 6
    3719     Thread 4
    3709     Thread 4
    3701     Thread 4
    3697     Thread 4
    3691     Thread 4


However, there are indeed repeats (e.g. 891 appears twice) so I ended up refactoring to this:

Main snippet:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
        int[] workChunk = new int[6];
        workChunk[0] = userEntry; //e.g. 36
        for (int i = 0; i < 6; i++){
            workChunk[i] -= split; // 36 - 6 = 30

        }
        Thread t1 = new Thread(p => program.printAllPrimes(userEntry,workChunk[0]));

        Thread t2 = new Thread(p => program.printAllPrimes(workChunk[0],workChunk[1]));

        Thread t3 = new Thread(p => program.printAllPrimes(workChunk[1],workChunk[2]));

        Thread t4 = new Thread(p => program.printAllPrimes(workChunk[2],workChunk[3]));

        Thread t5 = new Thread(p => program.printAllPrimes(workChunk[3],workChunk[4]));

        Thread t6 = new Thread(p => program.printAllPrimes(workChunk[4],workChunk[5]));


//Using this new overload on printAllPrimes:

    public void printAllPrimes(int beginwork,int endwork)
            {
                int holder = beginwork;
    
                while (--holder > endwork)
                {
                    if (isItPrime(holder))
                        Console.WriteLine("{0} \t Thread {1}", holder, Thread.CurrentThread.ManagedThreadId);
                }
            }


Now good thing is, nothing gets repeated. However, now the work only ever gets handled by 2 threads max and I'm not sure why, where before all threads were properly firing up, the thread IDs do change. For example, sometimes it's 10 and 11, others 3 and 4, but only 2. The work is also not getting done in a particularly fast way, but I'm sure that's because I'm throwing numbers like 5798238593 in there on purpose (it's quite fast with smaller numbers), and also I'm sure my code could be improved as well.

I'm on an Intel i7 quad core machine with Environment.ProcessorCount = 8 (8 logical cores).

I remember Casey talking a lot about the LockedIncrement, InterLockedCompareExchange, and InterlockedExchange, but my confusion is in that I have fired the same function in 6 different threads with 6 different parameters, so I'm assuming each thread is getting its own "instance" of the function, no? Whereas if I had two threads going thru the exact same function with the exact same local variables, then I would need the locking? Please correct me if I'm wrong and sorry if my code looks bad, I actually did all of this completely from scratch and haven't seen a "proper" implementation of finding primes or anything on multithreading other than HH. Last but not least, is breaking the work up like this even the proper way to go about doing this with multiple threads? Is there some way to use a mutex to have the same effect without doing the divide by 6 part? Thank you.
Edited by Todd on
Mārtiņš Možeiko
#10387
Print out (or look in debugger) at workChunk array.

For second program, assuming userEntry is 36 and split = 6, you have it like this: { 36, -6, -6, -6, -6, ... -6 };
That seems pretty wrong. I assume you want it like this: { 36, 30, 24, 18, 12, 6, 0 };

But doing multithreading this way will not be very efficient. The way you check if number is prime will take much more work for checking numbers from 36 to 30, than to check from 6 to 0. The larger the numbers, the worse it will get. So some threads will take longer time to finish, but other (most of them) will finish fast and then will be idle while you wait for those long threads to finish.

If you want to keep the algorithm as it is currently, then don't create one thread per chunk. Create one thread per core in your CPU. Then have one atomic number shared with all threads that will store number that needs to be checked next (initialize it with userEntry). Each thread should atomically decrement it to get number it needs to check. So first thread will get 36, next thread will get 35, and so on. Once they get to 1 (or 1) they can return from the thread.

For much larger numbers this will be very slow algorithm. You should look into Miller-Rabin or similar probabilistic primality tests.
Edited by Mārtiņš Možeiko on
Todd
#10389
Aha, thank you! Wow what a stupid mistake in the loop; I can't even believe the program still ran and crunched numbers with that haha, that was the reason for the only 2 threads firing and a reminder that even when you're dealing with "more advanced" things, that often the basics are what will screw it all up. I corrected it! Okay so that's where the whole atomic increment part comes it. That makes sense. I was having a hard time relating this work to the work done in HH but the way you just described it helps me put the two together, thanks!
Reply to Thread
← Back to index