|
If the Margolus partitioning scheme may be seen as the result of super-imposing
two planes containing rectangular girds, then the Q*Bert neighbourhood may be
seen as the result of doing this with two hexagonal meshes.
The two stages of the Q*Bert partitioning scheme
Alternation
The operation (and virtues) of the Q*Bert neighbourhood are very similar to those of the Margolus neighbourhood.
Universal computationThe neighbourhood supports universal computation with uniform automata - using a map similar to that of the "Billiard Ball Machine".
This map may be applied in one clock cycle. To get the mapping for the alternate clock cycle, all the above figures may be rotated through 180 degrees.
Size and packingIts advantages over related neighbourhoods are mainy due to its ability to occupy space more effectively.The Q*Bert neighbourhood typically needs three bits per cell, compared with four for the Margolus neighbourhood and six for the Star of David neighbourhood. Three is the smallest number possible while retaining the ability to perform reversible universal computation. Reversible automata with two states per partition are possible, but there are no such automata that can express non-linear boolean functions - and consequently none of them are capable of universal computation. The size of the LUT required to implement a complete programmable Q*Bert neighbourhood is 48 bits (3x(2^3)x2). The one required for a complete programmable Margolus neighbourhood is 128 bits (4x(2^4)x2) - less than half the size. A Star of David neighbourhood automata requires 384 bits (6x(2^6)) for a complete programmable look-up-table. Small size is not everything - Q*Bert-based systems will require more cells for some tasks than the equivalent when expressed in (say) the Margolus neighbourhood. However for the majority of applications which involve performing cmputations, the additional richness provided by a larger LUT seems likely to be wasted much of the time, doing the equivalent of transporting signals from one point to another. We believe the advantage of the smaller cells in terms of their smaller size and higher update frequency will commonly win out. Finally the Q*Bert neighbourhood is essentially hexagonal - and there is a general additional efficiency of hexagonal packing schemes compared to rectangular ones - a matter I will not go into further here. The Q*Bert neighbourhood has a fairly obvious extension into three dimensions.
|
