Swarm Intelligence

In a previous post on the Honey-bee algorithm for allocating servers, which I found quite fascinating, I had pointed out I had referred to a paper on Swarm Intelligence by Eric Bonabeau and Christopher Meyer published by Harvard Business Review, and finally I got time to go back and read it and I found it quite fascinating! The paper describes case studies where people have used algorithms inspired by nature (ants, bees) which use a decentralized model of computation and optimization.

The paper points out that the main advantages of using algorithms like these are flexibility, robustness and self-organization. The algorithms work in a completely decentralized manner, and work on the principle that the wisdom of all the ants (or the small agents) can be harnessed in such a manner that the whole is far greater than the sum of its parts. Also, the algorithms are invariably robust to failure and adaptive since they don’t make use of a central decision making bodies and there is a lot of experimentation with new sources of food (or results in the case of algorithms).

The paper also points out that there are several cases where these concepts have been used successfully (both in business and academia):

  • Optimally routing telephones calls and Internet data packets seems to be a tough problem because if we use a centralized algorithm, it will neither be robust nor adaptive. Algorithms based on swarm intelligence come to the rescue since they are not based on a central decision making body, but rather work on the principle that the scouts recruit other agents to follow new promising paths.
  • Fleet management and cargo management also suffer from similar problems. The paper points out that Southwest Airlines found out that in some cases, letting cargo go to wrong destinations and recovering is faster and more robust than always making sure that all cargo is handled correctly.
  • Small simple rules that lets people take decisions for themselves usually works best. This has since been shown to work very well for companies such as Google as well.

There are more case studies in the paper, but what’s fascinating is that these techniques become even more popular now-a-days because companies have realized that it is easier to tolerate failure than to eradicate it — more so in the context of the Internet where there is a race to build systems that are self-correcting (such as Map-Reduce, Hadoop and Dryad). Also the new realities of the emerging architectures (multi-core, highly parallel, massive clusters grids) is going to mean that we have more parallel horsepower to run our applications and such self-organizing algorithms are going to become even more popular in the computing community.

However, one concern would be programming models for such computing bedrocks. We still don’t understand how to manage parallel computation very well to ensure that interpreting such algorithms in code is going to remain difficult for the average programmer for quite sometime.

Parallel Programming + Type inference + Scientific notation: A Winner?

I came across this article in Linux Today which describes Project Fortress, an open-source effort from Sun to provide a language based on Fortran to easily write parallel programs. The project seems to be built on top of Java. Some salient features seem to be:

  1. Implicit parallelism: If you want to execute a loop sequentially you have to explicitly write that. The big claim is of course, using this efficiently on multi-core machines.
  2. Support for unicode: As a result, the scientific research community can make use of greek alphabets in their code, and even use things like superscripts, subscripts, and hats and bars! This means that your code is going to look a lot more like your algorithm.
  3. Automated Type inference: The system has extensive type inference (the kind that functional languages and C# 3.0 have) and that means that your code is far more readable.
  4. Extensive library support: In fact, even some parts of the main system are implemented as libraries. They expose the parsed AST to the programmer, and give him extensive control.

These sound quite interesting, and it seems that the scientific computing language of the future is going to look a lot like Fortress, if they are successful with this effort.

Fran Allen and the evolution of HPC

I had the good fortune of being able to listen to Fran Allen (IBM profile and Wikipedia entry) today. Fran pioneered a lot of work in compiler optimization and was awarded the Turing Award for her contribution to Computer Science in 2007. That makes her the first and only (till date) woman to have won the Turing Award, the highest honour in Computer Science.

It was inspiring listening to her talk about her adventures. She almost described the evolution of high performance computing, with the earliest IBM systems starting from Stretch, which was supposed to be 100X faster than the existing machines (but turned out to be only 50X faster) and was delivered to the National Security Agency. She also described some of failures she had been involved in (Stretch, since it was 2X slower than intended, and then the ACS project). What was interesting was that most of the basis of the pioneering work she described had its basis in the work she had done in these failed projects. The fact that failures are the foundations of mammoth successes is one message she clearly drove home with her optimistic outlook. She also described her work during the System 360 and the PowerPC projects.

Her appeal to computer science researchers and students was mainly about the programming models and architecture decisions revolving around multi-core, a buzz word most of us have been left confused and wondering about. This new revolution that promises to change the way we write software and exploit parallelism in our programs, is the biggest opportunity, as Fran put it!

What was also interesting was how we got to the lecture hall wading through mud in a construction site during the rain. Apparently, there are two conference halls at IISc — one called JRD Tata and the other JN Tata. No wonder, we got to the wrong one and found that it as hosting a conference on Power Electronics. Note to self: make sure you always check the location properly before setting forth.

Other than that, have been lately busy with hacking Python for S60 (this is a brilliant idea– having a platform agnostic scripting language!) to work on my phone and a Python based remote administration toolkit. Will post more about them soon!

Technorati Tags: , , , ,
Follow

Get every new post delivered to your Inbox.

Join 1,843 other followers

%d bloggers like this: