Why is parallel programming difficult?

Why is parallel programming so hard? At least it’s supposed to be hard — that’s the myth. Of course there’s also a myth (among non-programmers) that all programming is hard, for everyone except 12 year-olds in movies.

One reason parallel programming is hard is we don’t get any practice. Programmers aren’t used to thinking parallel. Introductory programming is linear programming, and most real-world bread-and-butter programming tasks are don’t require a parallel approach. And frankly, it’s easier to understand and express a linear program, and it’s certainly easier to debug.

And besides, parallel hardware has always been exotic, at least up until now. So there hasn’t been much demand for parallelism, and the tools reflect that. Programming languages are (mostly) linear, described as linear text that becomes a linear token stream. Years of parser and compiler research has focused on grammars to translate that linear token stream into linear machine code.

Programs were linear even before text files. Fortran programs used to be stored on stacks of punch cards.

So our tools and habits encourage linear thinking. We introduce unnecessary constraints and dependencies that break parallelism without even thinking about it.

And that’s one reason parallel programming is hard. A big reason.

March 26, 2009 | Filed Under Programming, multi-thread, parallel processing

2 Comments 

Infinite sums, integer sequences

Yesterday my son told me “You know Dad, when you add 1/10 + 4/100 + 9/1000 + 16/10000 forever you end up with 110/729.”

This was part of a discussion we started a year ago when I was teaching him about repeating decimals. We started easy with 1/10 + 1/100 + 1/1000 forever is 1/9, moved on to stuff like 1/9 + 1/81 + 1/729 etc is 1/8. He particularly likes 1/49, which has a 42 digit repeat and is 0.0204081633..etc or the sum of (2^n)/(100^n) where n is 1..infinity.

He also likes how 1/4 is related to 1/49 and 1/499. 1/4 is sum((2^n)/(10^n)) (n <- 1..infinity), 1/49 is sum((2^n)/(100^n)), and 1/499 is sum((2^n)/(1000^n)).

Anyway, since 1/4 is sum((2^n)/(10^n)), we briefly wondered what sum((n^2)/(10^n)) was. I didn’t know, and I forgot about it.

But my son remembered and somehow calculated it to be 110/729. Then he told me sum((n^2)/(100^n)) is 10100/(99^3). So I suggested maybe sum((n^2)/(X^n)) (n <- 1..infinity) is (X*(X+1))/((X-1)^3).

That’s kind of cool. It’s related to the fact that 1/2 + 1/4 + 1/8 + ..etc.. is 1, and 1/3 + 1/9 + 1/27 + ..etc.. is 1/2, and in general sum(1/(B^n)) is 1/(B-1) (summing over n <- 1..infinity). And also 1/2 + 2/4 + 3/8 + ..etc.. is 2, and 1/3 + 2/9 + 3/27 + ..etc.. is 3/4, and in general sum(n/(B^n)) is B/((B-1)^2). So if my guess above is right maybe we’ve caught a pattern. Take a look:

Summing over n <- 1..infinity:
  sum((n^0)/(B^n))  is  (1      /((B-1)^1))
  sum((n^1)/(B^n))  is  (B      /((B-1)^2))
  sum((n^2)/(B^n))  is  (B(B+1))/((B-1)^3)

That’s interesting. And the denominator follows the obvious pattern as we go forward. For sum((n^3)/(B^n)) it’s (B-1)^4, for sum((n^4)/(B^n)) it’s (B-1)^5, etc. As for the numerator, you’d think B(B+1)(B+2) might be next.

But it’s not. The numerator is a lot weirder than that.

Let’s look at this again:

Summing over n <- 1..infinity:
  sum((n^0)/(B^n))  is  v0/((B-1)^1) where v0 is 1
  sum((n^1)/(B^n))  is  v1/((B-1)^2) where v1 is B
  sum((n^2)/(B^n))  is  v2/((B-1)^3) where v2 is B(B+1)
  sum((n^3)/(B^n))  is  v3/((B-1)^4) where v3 is ?
  ...
  sum((n^A)/(B^n))  is  vA/((B-1)^(A+1))

Is there an easy way to describe the numerators v3, v4, v5, etc? To find out I wrote some code. You can see it here (in series.erl). Here’s what the function sum_na_over_bn_numerator (and list_close_sum_na_over_bn_numerator_for_b) told me:

For A Numerator when B is 2 Numerator when B is 3 Numerator when B is 4 Numerator when B is 5
0 1 1 1 1
1 2 3 4 5
2 6 12 20 30
3 26 66 132 230
4 150 480 1140 2280
5 1082 4368 12324 28280
6 9366 47712 160020 421680
7 94586 608016 2424132 7336880
8 1091670 8855040 41967540 145879680
9 14174522 145083648 817374564 3263031680

The first three rows are 1, B, and B(B+1) as I stated above. But the rows after that are harder to figure. If the next numerator were B(B+1)(B+2), the 4th row (where A is 3) would be 24, 60, 120, 210 instead of 26, 66, 132, 230. I don’t know of a simple expression to generate this sequence.

The column where B is 2 is the sequence [1, 2, 6, 26, 150, 1082, 9366, 94586, 1091670, 14174522, 204495126, etc]. This series is described as the Number of necklaces of sets of labeled beads (A000629) in the Encyclopedia of Integer Sequences (att.com). It is also mentioned in Stirling Number of the Second Kind (wolfram.com).

The column where B is 3 is the sequence [1, 3, 12, 66, 480, 4368, 47712, 608016, 8855040, 145083648, 2641216512, etc]. This series is also (sort of) described in the Encyclopedia of Integer Sequences (att.com) where it is called the Expansion of ln(1+sinh(x)/exp(x)) (A009362). But A009362 is not exactly the same sequence since it starts with 0 and has alternating positive and negative integers, like this: [0, 1, -3, 12, -66, 480, -4368, 47712, -608016, etc].

We can turn this table on its side with the function list_close_sum_na_over_bn_numerator_for_a and look at other integer sequences.

For B Numerator when A is 0 Numerator when A is 1 Numerator when A is 2 Numerator when A is 3 Numerator when A is 4
2 1 2 6 26 150
3 1 3 12 66 480
4 1 4 20 132 1140
5 1 5 30 230 2280
6 1 6 42 366 4074
7 1 7 56 546 6720
8 1 8 72 776 10440
9 1 9 90 1062 15480
10 1 10 110 1410 22110
11 1 11 132 1826 30624

And of course the 2nd column (where A=0) is always 1, the 3rd column is the same as B, and the fourth column is B(B+1).

The fourth column values (B(B+1)) are also known as the Pronic Numbers. In the Encyclopedia they are called the Oblong (or pronic, or heteromecic) numbers: n(n+1) (A002378).

I don’t have names for any of the other integer sequences in the tables above. I’ll list a few of them here in case someone ever googles them. (I don’t think google is very good at recognizing number sequences in table columns.)

The following lists are just google bait. Read above to find out where they came from.

Sequences from list_close_sum_na_over_bn_numerator_for_a( N ):

Sequences from list_close_sum_na_over_bn_numerator_for_b( N ):

March 19, 2009 | Filed Under analysis, erlang, math, sample code

4 Comments 

Home Depot’s decline?

Is it just me, or is Home Depot going downhill?

I remember a few years ago how Home Depot was a really fun store. The shelves were well stocked and organized, the selection was great, the staff could point you to anything, the displays were fresh and fun to look at, the garden plants were healthy, and the seasonal stuff was always exciting. But now the place seems grubby and disorganized.

For example, yesterday I was looking for a socket to fix a lamp. It’s not hard to find the sockets, in the aisle with electrical switches, plugs, and other doo-dads. But the little boxes under the display switches are a mess — all jumbled together with random stuff from other parts of the store mixed in. I finally found the socket I needed, about 4 boxes away from where it belonged.

There were only a few switches to choose from, all from the same manufacturer, and all somewhat overpriced at about $3.50. A couple years ago (when I last fixed a lamp) there were twice as many choices. Even Lowe’s has more selection. And better prices.

This is just one little thing of course. But over the past year I’ve been noticing more and more a feeling of grubby disorganization in the store. I used used to find inspiration at Home Depot, but nowadays it’s just depressing.

Two weeks ago a friend of mine was telling me about another friend who was laid off from Home Depot. He said they got rid of all the most experienced people because they were the highest paid.

Yikes. I know there’s always at least two sides to a story like that — I’ve been through layoffs, and they’re awful for the employees, but they’re also awful for the managers who have to fire people. These decisions are very hard.

Still, this story jibes with my anecdotal impression. Somebody on the sales floor has to really care about all the little details. Someone has to make sure the dust is dusted, the bins are straightened, and the obscure items are stocked. That someone has to be on the floor noticing details every day. Not working the register. Not stuck in an office writing performance reviews.

March 16, 2009 | Filed Under Society

Leave a Comment 

← Previous Page — Next Page →