Spreadsheets are special
Friday, 15 October 2010
Article Index
Spreadsheets are special
Spreadsheet as cellular automaton


The CA way to parallel programming

The use of a range reference and a function to get rid of the for loop is just the start. An adventurous spreadsheet user can write formulas that refer to formulae stored in other cells. This raises the level of sophistication to the point were it reaches the forefront of computer science research. The problem is that if you have formulae in different cells and one cell depends on the result of another then the result will depend on the order that you evaluate them in.

In other words a set of self-referencing formulas produces a race hazard and even the possibility of circular dependency. At first spreadsheet implementers solved this problem by simply imposing some rules that gave a known order of evaluation - usually top to bottom and left to right. Spreadsheet users quickly learned to think in terms of "everything above and to the left is evaluated and safe to use".

This may seem like avoiding the issue but even this simple approach could cope with circular references that needed an iterative approach to evaluate. The spreadsheet would simply recalculate itself repeatedly in the same order until it was either stopped or until the calculation converged to a solution.

Later spreadsheets took a more reasonable and efficient approach to re-computation and created a dependency graph that allowed the expressions to be evaluated in a natural order. This didn't eliminate the need to iterate to evaluate circular references but it did mean that you could write formulas that depended on other results anywhere in the spreadsheet and expect the system to work out everything in a sensible order.

What is less obvious is that the spreadsheet brings with it a natural approach to parallel programming. Each formula entered into a cell is to be evaluated in place and display its current result in that cell. This is an inherently parallel algorithm. If you could build the hardware equivalent of a spreadsheet with one processor per cell then all you would have to do is ensure that each processor evaluated just the formula in its cell and display the result. In this case the order of evaluation doesn't matter as long as the processors always re-compute until the results settle to a stable state. While this would not be a good way to implement a software emulation of the spreadsheet concept it is a very reasonable way for real hardware to be used - the settling time would be very short.

This whole approach to parallel processing is of course nothing more than a cellular automaton (CA). The CA is possibly the most important computational architecture we have yet to explore. It has been suggested that a CA can give us the theory of everything we have been looking for. If you don't believe that CAs are capable of great complexity then just take a look at the Game of Life - a 2D CA with amazingly simple rules that generates very complex behaviour. The idea is that something like the simple rules for Life are at the heart of the universe which simply gets on computing those rules and on the way generates all there is.

The spreadsheet is a CA and it is an advanced computational model that turns out to be surprisingly easy to use. Whatever you think of the spreadsheet don't dismiss it as trivial.




Last Updated ( Friday, 15 October 2010 )

RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.