Sunday, August 26, 2012

Multi-multi-threading - Oops, you missed a spot!

Multi-threading involves having multiple threads in a single process. This means running several tasks in parallel. This is (and has been) the future of computing - at least, since Intel demonstrated that a single processing core can act as two by executing two sets of instructions at once. My old Pentium 4 520 is still kicking, its hyper-threaded core running tests for PrimeGrid.

IsItPrime version 1.6.0, which I just released, uses not one but two separate threads to test its candidate number. It's identical to 1.5.6 (which has not been released yet), meaning they share the same basic code. However, it is quite different on the testing side of things.

IsItPrime 1.6.0 uses three threads to run - one is the "worker thread," responsible for drawing, rendering, and displaying the client window and its controls. The other two are "testing threads," which are only created when the TEST button is pressed.

In the case of brute-force trial division testing, multi-threading really shines because each thread can test a different range of numbers. This has its pros and cons for sure, but at this point I think the benefits seriously outweigh the drawbacks.

The first thing that's apparent is that neither thread is going to find the same exact factors. This is good. They run faster and, since they both calculate quotients, the aggregate factor/quotient display remains the same.

Thread One begins testing at 2, while Thread Two begins testing at 3. They both operate within a loop that exits once one of two conditions is satisfied (I'll get to that). This loop has them increase their trial division number by 3 each time. So, the first few instances of the loop will look like this:

Thread One: 2
Thread Two: 3
Thread One: 5
Thread Two: 6
Thread One: 8
Thread Two: 9

and so on.

The major flaw here becomes evident rather quickly, no? That's right - numbers are skipped.

The solution to this would be to start a third thread and have it test 4, 7, 10, 13, 16, and so on.

This is not a big enough deal to merit a complete re-work of the program...or maybe it is. I wanted to get IsItPrime out there first before re-doing its inner workings entirely!

The loop it uses to test, however, is fine. It takes the candidate number and adds two, creating variables iip and iip+2. When it begins testing, each thread creates an array called factorarray[], and as it finds factors (if any), they are inserted into the array. They also create and initialize a variable called bread (because I used the first thing that came to mind), which is set to the quotient of iip divided by factorarray[0].

The loop will exit upon satisfying one (but never both) of these conditions:
  • the trial number exceeds iip and/or equals iip+2
  • the trial number equals or exceeds bread
The latter option is more likely. That means that the test has reached the beginning and found all possible factors in that range.

On redesigning the interface (again):

The interface already looks like this:

I tout it as "user-friendly." Well, isn't it? It's just a bunch of boxes, a few easily-understood buttons, and two progress bars (one per thread).

Now, imagine there was a third thread. That will ultimately have to happen, yes, but would require these major interface changes:
  • A third big factor display box on the bottom
  • A third progress bar
  • A third message box
  • A third slot in the status bar, which is already strapped for space
Not to mention the several hundred more lines of code that would need to be written. Have you ever designed a window completely from scratch using only Win32 API code? It's not particularly difficult, but it's not exactly simple either, and it's kind of time-consuming to boot.

Creating something in a window (let's say a button) is a 12-argument function; four of those arguments are X, Y, width, and height. Never mind that the client area is not exactly what you tell it to be - this is annoying! To put another box in at the top, for instance, I'd have to move everything down!

That and it's just easier to divide something in half than into thirds.

So - the next version of IsItPrime will be released very soon. It will have three testing threads and will not skip any numbers. 

No comments:

Post a Comment