[FoRK] I'm a Feynman Fanboy

Eugen Leitl <eugen at leitl.org> on Fri Feb 23 00:25:14 PST 2007

On Thu, Feb 22, 2007 at 05:44:46PM -0600, Lorin Rivers wrote:
> I thought this was a cool article about Feynman's contribution to
> Thinking Machines.
> 
> <http://www.kurzweilai.net/articles/art0504.html?printable=1>

I never understood the point for hypercubes. As for wiring and
routing regularity they're not so hot (the connectivity table
is a fractal). When you lay out the nodes on a flat plane or a
3d lattice, and wire them up regularly, you get something else,
an n-grid.

Here's a cut&paste from a dumb writeup I did somewhen in 1994/95:

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

The n-grid/n-cube.

Imagine a standard three-dimensional cube with an edge of length
1, the first node lying at coordinates (0,0,0), the second at
(0,0,1), the third ... (0,1,0), (0,1,1), (1,0,0), (1,0,1),
(1,1,0) and the eighth at (1,1,1) (see picture). It is a member

    Y
    |       Z
    |      /
 011| o--------o 111
    |/|  /    /|
010 o--------o | 110   A 3-cube with binary labeled
    | |/     | |       nodes in a cartesian coordinate
 001| o------|-o 101   system
    |/       |/
    o--------o-------X
  000      100

of the boolean n-cube homologue sequence with total number of
nodes being 2^n. Thus one can label the nodes with a binary
integer 0,..,(2^n)-1. Alternatively, one can say there a space
of IDs for each n-cube. If we consider a single reference node
in a boolean n-cube, it is connected to n nodes _with binary
offsets_ (2^i). The sign of the offset is derived from the
binary count pattern bit sequence. This is a constructive
definition. (Look up connectivity matrix of boolean 5-cube way
down. Note that it contains _four_ 3-cubes).

 This table represents the 3-cube:

 ref. Binary Signs  binary     connected
 ID   Count         Offsets    IDs
 +---+-----+------+-----------+-------+  (alt.:
 | 0 | 000 |  +++ |  +4 +2 +1 | 4 2 1 |   perfect
 | 1 | 001 |  ++- |  +4 +2 -1 | 5 3 0 |   shuffle
 | 2 | 010 |  +-+ |  +4 -2 +1 | 6 0 3 |   stages (1,2,3)
 | 3 | 011 |  +-- |  +4 -2 -1 | 7 1 2 |   of the initial
 | 4 | 100 |  -++ |  -4 +2 +1 | 1 6 5 |   ref. ID)
 | 5 | 101 |  -+- |  -4 +2 -1 | 2 7 4 |
 | 6 | 110 |  --+ |  -4 -2 +1 | 3 4 7 |
 | 7 | 111 |  --- |  -4 -2 -1 | 4 5 6 |
 +---+-----+------+-----------+-------+

This boolean n-cube is a peculiar beast. On the one hand it is a
very orthogonal structure, easily reasoned upon mathematically.
The signs/offsets look after themselves, it is a
recursive/fractal structure (each n-cube consist of 2
interconnected (via (n-1) number of links) (n-1)-type subcubes),
etc. Routing in it resembles binary search: the first step
brings one halfway there, the second halfway again, etc. We
descend the binary cluster hierarchy until we arrive at the
0-cube (single node). The "distance distribution versus
dimensionality" table is the Pascal triangle, by the way. It can
derive its own ID from wiring constraints and the other IDs it
is directly connected to. (This is a crucial point). Etc.
Routing in a perfect n-cube runs roughly: "going from the left,
find the first bit in destination ID differing from source ID.
Move message packet to the according subcube via direct link
(there is only one). Repeat until you reach outer (rightmost)
bit. Bingo." This can be coded in some 10 assembly statements or
implemented via a very primitive logic. If a part of the links
is missing (the n-cube is defective) we have to visit all the
nodes which should have links to the second subcube until we can
prove the task impossible.

The n-grid, on the other hand, can be considered a better n-cube
(is a superset of it). We can derive it from the n-cube by
making link offsets symmetrical. Links which would reach out of
ID space can be either wrapped around (circular space) or
considered void/free (open space/grid region). See connectivity
table below. Routing is again completely trivial. You just
choose the link which distance (arithmetical ID difference) is
smallest and shove the packet through. In a perfect n-grid, this
works every time and is moreover the best possible algorithm.
Especially, if the near-range order (shortest offsets) is highly
preserved, this scheme works also for severely defective n-grids
(there is a lot of space in those higher dimensions). If the
message _blocks_ (its path has a periode/loop) we can circumvent
the blockage either giving the message packet a random kick or
executing a plan, subsequently visiting all the nodes which
should have links in this direction in ever-increasing
distances.

Connectivity Tables of 5-cube and 5-grid (2^5=32 nodes each)

# means a link,
- means there is no link.

Note that the n-cube is contained in the n-grid (as it is a
superset). The n-cube has a fractal/recursive makeup: it
contains two interconnected (n/2 links) (n-1)-cubes. A n-grid
node has (2n-1) links as compared to the n-cube (free links are
not shown). Two (n-1) subgrids are connected by (2n-1) links as
compared by n links in the n-cube. The simple n-grid routing
algorithm does not work for the n-cube (it blocks/loops in most
cases). Moreover, if the _farthest_ link of each node (n-cube)
is cut, the cube collapses into 2 unconnected (n-1) cubes. This
does not happen to the n-grid. Notice that a defective structure
(some links missing) still routes all right because of built-in
redundancy (which is higher in the n-grid).

The n-grid is a superset of the n-cube. Each node has

boolean 5-cube                    5-grid (open-space version.
                                          free links not shown)

-##-#---#-------#---------------  -##-#---#-------#---------------
#--#-#---#-------#--------------  #-##-#---#-------#--------------
#--#--#---#-------#-------------  ##-##-#---#-------#-------------
-##----#---#-------#------------  -##-##-#---#-------#------------
#----##-----#-------#-----------  #-##-##-#---#-------#-----------
-#--#--#-----#-------#----------  -#-##-##-#---#-------#----------
--#-#--#------#-------#---------  --#-##-##-#---#-------#---------
---#-##--------#-------#--------  ---#-##-##-#---#-------#--------
#--------##-#-----------#-------  #---#-##-##-#---#-------#-------
-#------#--#-#-----------#------  -#---#-##-##-#---#-------#------
--#-----#--#--#-----------#-----  --#---#-##-##-#---#-------#-----
---#-----##----#-----------#----  ---#---#-##-##-#---#-------#----
----#---#----##-------------#---  ----#---#-##-##-#---#-------#---
-----#---#--#--#-------------#--  -----#---#-##-##-#---#-------#--
------#---#-#--#--------------#-  ------#---#-##-##-#---#-------#-
-------#---#-##----------------#  -------#---#-##-##-#---#-------#
#----------------##-#---#-------  #-------#---#-##-##-#---#-------
-#--------------#--#-#---#------  -#-------#---#-##-##-#---#------
--#-------------#--#--#---#-----  --#-------#---#-##-##-#---#-----
---#-------------##----#---#----  ---#-------#---#-##-##-#---#----
----#-----------#----##-----#---  ----#-------#---#-##-##-#---#---
-----#-----------#--#--#-----#--  -----#-------#---#-##-##-#---#--
------#-----------#-#--#------#-  ------#-------#---#-##-##-#---#-
-------#-----------#-##--------#  -------#-------#---#-##-##-#---#
--------#-------#--------##-#---  --------#-------#---#-##-##-#---
---------#-------#------#--#-#--  ---------#-------#---#-##-##-#--
----------#-------#-----#--#--#-  ----------#-------#---#-##-##-#-
-----------#-------#-----##----#  -----------#-------#---#-##-##-#
------------#-------#---#----##-  ------------#-------#---#-##-##-
-------------#-------#---#--#--#  -------------#-------#---#-##-##
--------------#-------#---#-#--#  --------------#-------#---#-##-#
---------------#-------#---#-##-  ---------------#-------#---#-##-



-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820            http://www.ativel.com
8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE

More information about the FoRK mailing list