danl@cbnewsc.ATT.COM (daniel.r.levy) (04/25/89)
I've enrolled in a class in advanced (parallel) computer architecture, and one
of the intriguing topics that has come up is the de Bruijn ("broin") graph.
The class instructor, Dr. M. Samatham of Northwestern, has done quite a bit of
research on this critter. The intriguing thing about de Bruijn graphs (or
specifically, the binary de Bruijn graph) is that, while it has a fixed
degree of 4, many different useful computational topologies map right into
the binary de Bruijn graph, including linear arrays, rings, trees (single and
back-to-back a la Tree Machine), the perfect shuffle, and the shuffle exchange.
The graph is built by numbering 2**k nodes from 0 to (2**k)-1, and then
connecting each node to the other nodes whose number is the following
operation upon the binary number of the original node: a one-bit left
circular shift (SEA); a one-bit right circular shift (SEA-1); a one-bit left
circular shift while complementing the bit that was circulated (SEAC),
and a one-bit right circular shift while complementing the bit that was
circulated (SEAC-1). Some of the nodes will end up with more than one
connection to the same neighbor, and others will loop two of their connections
into each other, of course.
I'm interested if there are people out there building de Bruijn machines, and
in what they are doing with them. It appears to be a rather versatile
parallel architecture.
--
Dan'l Levy UNIX(R) mail: att!ttbcad!levy, att!cbnewsc!danl
AT&T Bell Laboratories
5555 West Touhy Avenue Any opinions expressed in the message above are
Skokie, Illinois 60077 mine, and not necessarily AT&T's.