Accomodating for everyday parallel computing

A bit more than a year ago, Herb Sutter published "The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software" in Doctor Dobb's Journal (which is incidentally the only printed computer magazine I buy). If you don't know this article yet, go and read it, I'll wait right here.

In case you're hasty and decided to skip it in spite of better advice, here's the summary: the trend over the years was that you could afford yourself to keep writing ever less efficient code and have it be compensated by increase in hardware processing power. That trend is over. The reason: CPUs today aren't made faster by increasing their linear processing speed anymore. CPU manufacturers are encountering big technical difficulties on that route lately. Rather, the CPU processing power is increased by adding multiple cores. The bad news is that your sequential, single-threaded algorithm won't automatically benefit from this, as it did from clock speed bumps in the past years.

So, what's to do? Ignore the problem is one solution, but computers with multicore CPUs are today quite widely available on market. I'm typing this on an Intel Core Duo system myself. Running a test program with an infinite loop won't max the CPU utilization on this gear. It'll push it up to 50%. I need to run another instance of the program to push the CPU all the way to 100%. If you ignore the system, you'll produce software that can only utilize 50% of the CPU resources. People will inevitably find it slow over time and use your competitor's software who chose to not ignore the problem.

Another possibility is manual parallelization. Identify hotspots in your code. Rewrite them to be multithreaded. Use mutexes, locks, the whole shebang of multithreaded programming. If you have an array of 1 million elements (a big sound sample, maybe, or a picture), chunk it up and feed each chunk to a different thread. Even better, than chunking it into 2 equal parts on a 2 CPU system, code a producer-consumer pattern to chunk it into many small pieces and feed to threads adaptively. Of course, your code increases in complexity considerably. Of course, your program might have a runtime overhead for spawning new threads. And then there's the fact that concurrent programming on "low level" - using threads and locks explicitly is hard. It is easy to get it wrong and create race conditions and deadlocks at runtime. So, is this solution ideal? Far from it.

An ideal solution would be a programming paradigm that does yield readable source code, and still allows the compiler or the runtime system to identify paralellizable operations and paralell them, either statically (compiler) or dynamically (a runtime JIT compiler after it decides that the up-front cost of setting the paralellization is less than the gain from paralellization of an operation).

Just as today we have runtime environments with implicit memory management and languages designed for writing programs that run in such an environment, we could soon have environments that have implicit parallelization.

As a typical example, a transformation applied to all elements of a collection independently is a good candicate - provided your programming language lets you express it in such a way. I believe that functional languages are better prepared for this kind of implicit parallelization. There are already some academic-level efforts underway, witness Parallel Haskell.

One very interesting notion some people are vocal about is that stack-based computational models inherently stem from the sequential approach to programming, and that as we strive to embrace programming approaches that naturally lend themselves to paralellization, we'll gradually embrace computation models that aren't stack based. Like the just mentioned functional programming where you don't really express your program in terms of subroutine calls. Or how Excel 12 will also feature parallel computations. BTW, the previously linked blog entry also contains links to some interesting research going on in this general area of single-machine parallel computing.

Is it a say hello again to state machines? Maybe, maybe not. One thing I can more readily imagine is that a today's widespread architectural model for enterprise systems - asynchronous messaging - will somehow get adapted for single-machine single-process development that is meant to run on multiple CPUs.

New Gear

I bought a MacBook Pro. It's a first-gen 15.4" 1.83GHz Intel Core Duo piece - it was the only one that the dealership could ship quickly, so I sacrificed 170 MHz per CPU core rather than having to wait one month for the machine to ship. I ordered a +1GB RAM stick and a bigger HDD, but they managed to screw up the order, so these will arrive next week. Sheesh.

The reason I bought a MBP: I need mobility. I realized that while my iMac G5 is an absolutely satisfying machine for all my work, it falls short if I need to do work, but kids insist that I take them down to a playground. Or we want to spend the weekend in our hobby garden out of town, and I want to have a computer with me for evenings. Also, lugging the 11kg 20" iMac is possible - I proved this to myself taking it with me from Szeged, Hungary to Reading, UK and back - but by no means a pleasant experience. (There were no problems with airport security, mind you - Heathrow has a policy that you must take your laptop out of the bag and have the bag and the laptop screened separately. I argued that my computer is not a laptop, and they let me not have to unpack it from its iLugger, thank God. The screening lady cheerfully said "Look, this guy carries a big computer screen with him!" to a passing colleague, so that I can feel like a complete dork.)

Anyway, I'm typing this on the MBP now, after a rather painless transition - all my files, applications, and settings were transferred automatically from the iMac. I had a strange incident though - when the setup got to setting up wireless, I forgot that my router is locked down and will only accept connections from predefined MAC addresses. After two unsuccessful attempts (I thought I forgot the password), the setup froze, and I had to reboot it. It was rather painless afterward though, but since the second time I opted to not transfer data from another machine (would take another three hours), I had to create a local account that I later deleted.

Also a hopefully minor problem - I have to reinstall Fink, so it's bootstrapping in the background as I'm writing this, fingers crossed it'll all work. The nice thing is, the Fink binaries transferred from the iMac actually worked after the migration, as the Rosetta (Mac OS X's built-in PowerPC CPU emulator) picks them up, but various update processes quickly notice that the CPU architecture suddenly changed to x86, and get mightily confused, so it looks like the best idea is to recompile everything from scratch. It does make me a bit anxious though. Fingers crossed, as I said.

War booty

My Dad and me were chatting about motorcycles - the conversation was sparked by a Kawasaki parked near the designated smoking area of a medical diagnostic center where I took him to an MRI scan one evening early this week. (A plate on the wall next to center's entrance boasts the British-American Tobacco Company logo. I can just guess this means they partially funded it. Trying to relieve a guilty conscience, I guess, for all those lung cancers.)

Anyway, I digress.

My Dad owned a 1957 BMW R25 motorcycle back in his young days. (Here's a site with photos if you're curious how does one look like.) He and my Mom used to travel a lot with it all around the country when they were a young couple. As it happens, I was eventually born, and the bike was less and less used - as convenient a vehicle it was for a man and his woman, it was not really usable at all for transporting a family with a kid (and later, two kids). I remember the bike from its years when it was gathering dust in our shed where I sometime retreated to play with Dad's tools. Rarely, Dad would take it out and drive it for half an hour around the countryside. Then its battery died, and he didn't get to replace it. One day, Mom sat down with Dad, and told him that, in her opinion, they should sell it. Dad opposed the idea. He was too attached to the bike emotionally even if he didn't use it much anymore. In a strange twist of fate, the very next day a man from our village knocked on the door. After Dad invited him in and seated him down, he said that he came to ask whether the bike would be for sale. Dad agreed to sell the bike, although with a heavy heart. The new owner took good care of the BMW. He repainted it and repolished it, replaced all that needed replacing. When I saw it few months later, I could hardly recognize it - it looked gorgeous, as good as new. Now (about 20 years later) Dad told me that his heart sank every time he saw it in the village. I told him that that's silly - the BMW definitely had a better place with its new owner.

I asked my Dad whether the new owner still has it. He told me that he met the new owner's wife few years ago, and asked her the same. She told him that when we were invaded by serbian forces back in 1991, they fled with their car and left the bike behind. After the territory was liberated in 1996 and they went back, they were not too surprised to not find it - the chetniks took it. She told him that during the war, these thugs could drive any vehicle they laid their hands on over to their serbian homeland, and the authorities would happily register it to their name if they claimed it was a war booty.

I told to my father: "see, now this is something to make your heart sink."