Cellular HPC

Before I spent most of my waking hours in front of computer displays, I used to read books and magazines. One of my favorite magazines was Scientific American. I liked Scientific American because it would introduce new (and old) scientific topics in a very clear an concise way. Plus, it always had nice illustrations which helped me immensely. I used to particularity enjoy Martin Gardner’s “Mathematical Games” column. In the October 1970 issue, he introduced his readers to a game called “Life”. The game was originally developed by mathematician John Conway at Cambridge in the late 1960′s and is often referred to as “Conway’s game of life.” It is also called “Cellular Automata” (CA).

This game of Life was not the board game where you went about trying to move through life, but rather a much more simple game that produced much more complicated outcomes. As I read about the game, I just had to try it because I did not quite believe that it would work the way it did. My skepticism was based on my notion that complex behavior could only come from complex “things.”

So here I was, sitting on the floor with a large poster board on which I had drawn a grid and some square marker pieces. I set up some simple patters, ran the rules and low and behold, it worked! For those that have never played the game, the rules are quite simple. For any arbitrary pattern you place on the grid (with your maker pieces),

• If a space is populated:
  
  
  
  • Any cell with one or zero neighbors dies, (death from loneliness).
    
  • Any cell with four or more neighbors dies. (death from overpopulation).
    
  • Any cell with two or three neighbors survives.
    
  
  
• For a space that is unpopulated (no marker)
  
  
  
  • Any empty cell with three neighbors becomes populated. (birth)
    
  
  

If you want to play with Life on-line you can go to sites like this one and enter patterns to see what happens. One thing to note is that small variations in patterns can cause huge changes in outcomes.

To any certified computer geek, the above is probably old hat. When computers were readily available, Life often became one of the first programs people would write because it was not easy keeping track of all those markers. The extents of your Life game were also increased. You could have all kinds of patterns on a much larger field. In addition, you could run the game for many generations to see what happens. One of the things that always interested me, however, was beyond the game of Life, what else could CA do? It turns out plenty.

A popular and controversial book by Stephen Wolfram called A New Kind of Science was mostly about the properties and possibility of CAs. In general, CA works well when you want to model complex things with lots of little parts. Of course there are other ways to model complex things, but CA has one advantage that it starts out with “simple rules” and generates complex results. There are CA’s for fluid flow, ecosystems, populations, environmental systems, urban growth, and even traffic. There are other areas as well. CA are often used to study “emergent systems” — those systems that start out simple but then self organize.

Why am I talking about CA’s? Aside from being intellectually interesting, they are highly parallel. And, when I see anything that is even slightly parallel I think of clusters and cores. Like, Genetic Algorithms or Monte Carlo methods, CAs are naturally parallel and can take advantage of the cheap and plentiful parallel computing cycles that clusters offer. There are even CA programming languages like CAOS (which stands for Cells, Agents and Observers for Simulation).

There is a certain appeal to using CA as a tool to simulate large systems. Indeed, CA’s can even produce pseudo randomness as part of their behavior. Keep the CA approach in mind when you have some extra cycles and want to play with an new idea. For instance, what if you try to simulate parallel programs running on a cluster. You never know what may happen. The often noted problem with CA’s, which is similar to Genetic Algorithms, is you can find something that works, but you are not sure why. Of course you could say the same thing about real life. Go figure, er ah automate.

Fatal error: Call to undefined function aa_author_bios() in /opt/apache/dms/b2b/linuxdls.com/site/www/htdocs/wp-content/themes/linuxmag/single.php on line 62