Robin's Blog

Programming << Pointers << Parallel Programming

I remember, fairly early on in my programming career, reading Joel Spolsky’s article about interviewing for programmers. At the time I thought I might want to get a job as a programmer (in fact, I’ve now got a job in academia – albeit in a field that involves a fair amount of programming), so I was interested to know what sort of things he thought interviewers should look for. One of the key things is being able to understand pointers, which he suggests is far harder than most of the rest of programming:

I’ve come to realize that understanding pointers in C is not a skill, it’s an aptitude. In first year computer science classes, there are always about 200 kids at the beginning of the semester, all of whom wrote complex adventure games in BASIC for their PCs when they were 4 years old. They are having a good ol’ time learning C or Pascal in college, until one day the professor introduces pointers, and suddenly,they don’t get it. They just don’t understand anything any more. 90% of the class goes off and becomes Political Science majors, then they tell their friends that there weren’t enough good looking members of the appropriate sex in their CompSci classes, that’s why they switched. For some reason most people seem to be born without the part of the brain that understands pointers. Pointers require a complex form of doubly-indirected thinking that some people just can’t do, and it’s pretty crucial to good programming. A lot of the “script jocks” who started programming by copying JavaScript snippets into their web pages and went on to learn Perl never learned about pointers, and they can never quite produce code of the quality you need.
Joel Spolsky (from The Guerrilla Guide to Interviewing)

At the time, I’d never properly dealt with pointers, so I made it my goal to understand them, which I did – mainly through reading the great K&R book. In his quote above, Joel refers to the type of ‘doubly-indirected thinking’ that is required to understand pointers – realising that what you have isn’t the object itself, it’s just a reference to the object, and that you can manipulate the pointer without necessarily manipulating the object, and so on.

However, I’ve just discovered the next thing along the line from the doubly-indirected thinking that pointers require: it’s the n-indirected thinking that parallel programming requires. That’s what the title refers to – using the mathematical symbolism of >> being ‘significantly greater than’ (yes there may be a unicode character for this, no I didn’t bother to find it). So – why’s all this parallel programming even harder (conceptually, at least)? Well…with pointers you have one thing (the pointer) which points to another thing (a memory location storing something – an integer, or a double or something). In parallel programming, everything has multiple copies, all of which may (or may not) have different values at any one time.

I’ve been doing some programming using MPI – the Message Passing Interface – recently. The way this works is that each core (that is, individual processing unit – whether it is combined on a piece of silicon with other cores or not) is treated as entirely separate from every other core in terms of memory (this is in distinct difference to other methods like OpenMP). Therefore, if cores want to exchange data they have to send an explicit message to another core to get the data. This sounds very restrictive, but by carefully distributing data to begin with, you can minimise the amount of communication you need to do.

One other thing about MPI, and the most relevant for this post, is that each process runs exactly the same code – so the whole code runs on each processor (unless you do things like ‘if (process_id == 0)’). This means that, at any point in code, one variable (for example, num_rows, holding the number of rows of the array this processor is operating on) can actually hold different values in each processor. For example, in the code I was writing, this was the same for most processes (as I tried to split up the array evenly) but with a few processes having more or less than the others. So, one variable has multiple values – ok, doesn’t sound too complicated…

However, when you start sending values from one place to another you realise that you can get in a terrible mental muddle (I find scribbling lots of diagrams helps!) as you’re sending variables from one process to variables in another process that may have different values for all of the other variables. Of course, when you’re dealing with pointers as well you’ve got the confusion of pointers, then the n-indirectedness of dealing with all of the variables. Fun!

(Oh and add to this the realisation that each process can be doing different things at the same time, but that send and receive calls must still match up….and your brain starts to explode!)

Still, all of this parallel programming is worth it – I’ve got really great speedups for some of my code!


Categorised as: Programming


Leave a Reply

Your email address will not be published. Required fields are marked *