The Boston Diaries

The ongoing saga of a programmer who doesn't live in Boston, nor does he even like Boston, but yet named his weblog/journal “The Boston Diaries.”

Go figure.

Thursday, May 24, 2007

Small forays into multiprocessing programming II

So, my attempt at parallelizing the Pythagoran Triples program. I rewrote it as a function to make it easier to parallelize:

```struct params
{
double start;
double end;
int    count;
}

int pythagorean_triple(void *data)
{
struct params *p = data;
double         a;
double         b;
double         c;

for (p->count = 0 , c = p->start ; c <= p->end ; c++)
{
for (b = 1 ; b < c ; b++)
{
a = sqrt(c * c - b * b);
if (trunc(a) == a)
p->count++;
}
}
return(0);
}
```

That way, I could then do:

```/*--------------------------------------
; the reason for these structures
; is that threads created with clone()
; only get a single pointer parameter.
; This way, I can pass in more data
; using that one pointer.
;
; And yes, I'm using C.  Nyah.
;-------------------------------------*/

struct param t1;
struct param t2;

t1.start = 2;
t1.end   = 16383;
t2.start = 16384;
t2.end   = 32768;

```

And I was surprised that it only took one second less when the processing was split using this method than when it ran not split at all.

I ran it several times, and yes, both threads were being created, but one was finishing way sooner than I expected. It was then that I realized the reason—it takes less time to count to a thousand than it does to thirty thousand.

D'uh!

Obvious in hindsight.

```for (c = 2 ; c <= 16383 ; c++)
for (b = 1 ; b < c ; b++)
... ;
```

```for (c = 16384 ; c <= 32768 ; c++)
for (b = 1 ; b < c ; b++)
... ;
```

Now … how to split the load evenly between two (or more) processors? Obviously splitting the range in half wasn't cutting it, but is that the only way to split the workload? What if I were to have one processor do even numbers, and the other one odd numbers? Something like:

```for (c = 2 ; c <= 32768 ; c += 2)
for (b = 1 ; b < c ; b++)
... ;

for (c = 3 ; c <= 32768 ; c += 2)
for (b = 1 ; b < c ; b++)
... ;
```

Yeah, that might work.

And it did—the workload was evenly distributed across the processors. The code slightly changed though:

```struct params
{
double start;
double end;
double delta;
int    count;
}

int pythagorean_triple(void *data)
{
struct params *p = data;
double         a;
double         b;
double         c;

for (
p->count = 0 , c = p->start ;
c <= p->end ;
c += p->delta
)
{
for (b = 1 ; b < c ; b++)
{
a = sqrt(c * c - b * b);
if (trunc(a) == a)
p->count++;
}
}
return(0);
}

{
struct params t1;
struct params t2;

t1.end   = t2.end   = 32768;
t1.delta = t2.delta = 2;
t1.start = 2;
t2.start = 3;

}
```

This concurrent programming certainly requires a different way of thinking about things. And obvious ways of splitting up workloads don't always work out as expected.

Obligatory Miscellaneous

You have my permission to link freely to any entry here. Go ahead, I won't bite. I promise.

The dates are the permanent links to that day's entries (or entry, if there is only one entry). The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site: https://boston.conman.org/, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

https://boston.conman.org/2000/08/01

You can also specify the entire month by leaving off the day portion. You can even select an arbitrary portion of time.

You may also note subtle shading of the links and that's intentional: the “closer” the link is (relative to the page) the “brighter” it appears. It's an experiment in using color shading to denote the distance a link is from here. If you don't notice it, don't worry; it's not all that important.

It is assumed that every brand name, slogan, corporate name, symbol, design element, et cetera mentioned in these pages is a protected and/or trademarked entity, the sole property of its owner(s), and acknowledgement of this status is implied.