Large insect populations synchronize globally, but communicate locally. Is there a lesson for parallel computing?
Insects fascinate me. Not because, they have six legs and pretty much dominate the earth, but because they have figured out ways to handle large numbers of themselves. In the past, I have marveled at how large numbers of ants and bees seem to operate as one organism. As core counts and clusters get larger, I always find it instructive to see how the problem of scale is solved by nature. Not that I sit around thinking about insets all day, but recently I watched a show about networks called “Connected: The Power of Six Degrees” on the Science Channel. Fascinating stuff, Kevin Bacon and all. The part that caught my interest however, was the synchronized fireflies.
It turns out that some species of firefly will synchronize their flashes so that the entire population is flashing at the same time. Now that is some trick. After a small bit of googling, I found The Synchronous Fireflies of Elkmont. Before you think I gone totally off the deep end, rest assured I’ll get back to clusters and HPC shortly.
From the article, were it states, “any system will tend toward synchronous behavior if the individuals involved follow some sufficient set of rules.” In the case of fireflies, those rules include:
- Individual fireflies possess an internal timer or oscillator.
- They can sense when their immediate neighbors are flashing.
- They tend to advance their cycle in order to flash before their neighbors flash.
Mathematician Steven Strongman of Cornell University has shown that these conditions are sufficient to lead a whole forest of fireflies to flash in synchrony. No reason for why the rules came about was given, however, similar sets of rules are believed to exist throughout nature. Some other examples of natural synchronization include women’s menstrual cycles, the movement of electrical impulses between nerve cells, the onset of epileptic seizures, and the synchronous movements of flocks of birds and schools of fish.
Before we get back to clusters, let’s switch to ants for a moment. One of the problems with managing large amounts of anything, is communication. For instance an ant colony has a queen, but she does not direct each individual ant. Each ant has a job (dig, forage, defend, etc) and follows a set of rules for that job. Ants communicate using chemicals. For instance they can mark a trail to food or send alarm signals to each other. Communication is local. There is no way to broadcast to every ant.
Cluster with many cores may have a similar problem — central control takes too much time and overhead. Let’s consider a master/worker model used by some programs. As the number of workers gets large, the master can easy become overwhelmed trying to synchronize 10,000 cores. What if a more dynamic approach was used instead of central synchronization. What if like the fireflies, cores could synchronize globally using simple local rules.
Taken further, what if programs were written in a way to self organize to solve a particular problem. That is, a program would consist of thousands of individual programs that would organize in such a way as to solve a particular problem. You might have IO programs, matrix multiplication programs, FFT programs, etc. which, through a set of rules would self organize and provide you with a result. Or, a programs behavior might change depending what its close neighbors are producing or consuming.
At this point, you probably think I have spent too much time with the insects. Perhaps. It should be noted however, that faster clocks have given way to multiple cores. In a similar, way, insects, with their exoskeletons can only get so big, so instead of becoming large, they became many. Like today’s processors instead of scaling up, they scaled out. Now you know why I think about insects.
My twitter following has reached 108, but I have new goal. I want to achieve Best Buy Manager Status. That is, I need 142 more followers. Help me out here. If I can’t qualify for selling TV sets, car stereos, and washing machines, then what am I doing writing about HPC. Oh the shame of it all.
Douglas Eadline is the Senior HPC Editor for Linux Magazine.