UniQMG's Blog: Spreadsheets

Spreadsheets are awesome.

They’re user friendly tools that allow easy wrangling and visualization of data. Macros can provide an additional power user tool for getting data, but aren’t portable between spreadsheet implementations. (Also they’re CHEATING!)

State

The main challenge with building a CPU in a spreadsheet is one of state: spreadsheets are essentially stateless. Data is a unidirectional flow and recursive references typically aren’t allowed.

Until you enable iterative calculation. With iterative calculation, cells can directly reference themselves and calculate their new state based on their current value. However, there’s a limit to how many calculations are allowed and self-referencing values can be calculated many more times than desired. Additionally, update orders aren’t defined, leading to data races.

Locks

In order to guarantee stable execution, the spreadsheet CPU uses ‘locks’ to control which part of the CPU is allowed to update:

• The input value is only randomized when the ‘Generate’ lock is open.
• The new value is only calculated when the ‘Calculate’ lock is open
• The value is only comitted when the ‘Commit’ lock is open.

In code, this would look something like the following:

for (let i = 0; i < ITERATIVE_CALC_LIMIT; i++) {
  if (generate_lock) random = generate_random()
  if (calculate_lock) new_value = value + random
  if (commit_lock) value = new_value
}

If you open all the locks at once, your value grows very quickly:

Locks allow each step of your computation to be idempotent and are really just as simple as if (LOCK) update() else hold().

The spreadsheet CPU’s locks

The spreadsheet CPU has a global ‘clock cycle’ counter. One instruction is executed every four clock cycles and split into a Fetch, a Decode, an Unused, and a Commit step.

• Fetch: Instructions are loaded according to the current IP (G15:G18).
• Decode: The instructions are converted into internal commands (I3:L8).
• Unused: Unused.
• Commit: The internal commands are applied (J2).

The internal commands are a simplified form of the instructions that are used to directly calculate new state while the Commit lock is open. They are as follows:

• SET register value: Sets a register (F19:G22) to the given value
• MEMSET address value: Sets a value in memory (N2:N32) to the given value

The internal command values are calculated in the instruction decode table, where the relevent new values are calculated via formula. And that’s it, really. Jumps are implemented via SET IP, and you could even mov a value into the IP register. Memory and register reads are direct from instruction decoding.

End notes

This entire implementation is done using only spreadsheet formulas with iterative calculation enabled. No macros are used, except for a utility macro that increases the Run to value on a timer to actually drive the processor. The value can also be incremented by hand, and the processor will run up to the iteration limit number of cycles towards it.