Introduction

Xgrid is an amazing resource built in to recent versions of Mac OS X that allows you to harness the power of spare processing power on other Macs to speed up the solving of difficult problems - known as Distributed Processing.

Xgrid can be used by anyone with a Mac, but most of the existing documentation assumes you're in a University research environment. I therefore thought it would be useful to document my experiences of using it to solve a recreational computing problem.

The problem

The problem I was trying to solve illustrates the type of problem that is amenable to distributed processing. I am trying to find a 5 x 5 word square in which the 5 horizontal words, 5 vertical words, and two diagonals (reading left to right) are all valid English words. I had already found a 4 x 4 word square by trial and error:

 b  u  m  p
 a  r  e  a
 r  e  a  r
 s  a  l  t

and I wrote a program in Lisp to search for all such squares. I then extended the program to find 5 x 5 squares, using a list of 4500 English 5-letter words. Even after optimising the program as much as I could, it took the program an hour to test the first word, "abase". So it seemed likely that the program would take 4500 hours to search all the words, or 187 days, over half a year!

I calculated that if I could distribute the problem across 16 processors the time would be reduced to just over 10 days, which sounds more acceptable. I could set 16 different tasks running, dividing the list of 4500 starting words between them. Xgrid makes all this possible.

Note that Xgrid can run a separate job on each processor core, so if you have a Dual 2-Core Mac Pro, Xgrid will be able to run 4 separate jobs on it simultaneously.

What is Xgrid?

Xgrid is built in to all versions of Mac OS X since Tiger. It allows you to farm out programs, called Jobs, to run on the spare processing power of other Macs, accessible over the Internet.

Xgrid consists of four components:

The Agents are Macs with spare processing power, that will be used to run the Jobs sent to them. This all happens invisibly to them, and you can specify that the Jobs only run when the Agent is idle.

The Controller runs on one Mac, and manages the separate programs, called Jobs. The Controller can run on any Mac running Mac OS 10.4 or later, or Mac OS Server 10.4 or later. It needs to be able to access the Agents over the network, so if the Agents aren't on the same local network as the Controller, the Controller needs to be accessible to the Internet.

The Clients are programs that connect to the Controller, and give it the Jobs to farm out to the Agents. A Client can be any Mac with access to the Controller. The simplest approach, and the one I took, is to use the Terminal to submit jobs to the Controller and collect the output. Alternatively, you could write a program to submit the Jobs and collect the output automatically.

The Grids are ways to group together jobs. In this example I've just used one grid, the default grid called Xgrid.

Problems you can Solve with Xgrid

Xgrid is ideal for problems that can easily be divided into smaller self-contained tasks, and some classic examples include:

  • Factorizing large numbers into primes.
  • Solving chess "mate in n moves" problems.
  • Solving word problems, such as word squares.
  • Plotting Mandelbrot maps.
  • Rendering 3D images.

Programming for Xgrid

You can run any program on Xgrid that can be run from the Mac OS X Terminal. In this Wiki I give examples of running programs written in:


blog comments powered by Disqus