Advanced Namespace Tools blog
30 December 2018
N-cubic routing on the Spawngrid
During an irc discussion of the many Plan 9 related offshoot projects that have existed in the past few decades, qrstuv mentioned a name I hadn’t heard before - nCUBE Transit. That turned into one of the deepest rabbit holes I’ve fallen into in many years of chasing Glenda. This is going to be a wild ride, taking us from reliable rotary switches all the way to 4-dimensional and higher spaces, supercomputing history, and unsolved questions in graph theory. Let’s start with a preview of the end point which you are not expected to understand yet - a grid of Plan 9 systems with hypercubic routing connections and four cities on earth mapped to four faces of the hypercube.
A namespace of spatial names
Excerpt from the namespace of a cube.rc process running on the spawngrid:
bind /n/0011/in /n/cube/0
bind /n/1111/in /n/cube/1
bind /n/1001/in /n/cube/2
bind /n/1010/in /n/cube/3
Each of 16 cube.rc processes has a unique namespace, generated by a call to the hyper.c routing tool, where $mynum is the binary id of the cpu making the call:
cd /n/cube
for(i in `{ls}){
bindtarg = `{hyper -id $i -f $mynum}
bind /n/$bindtarg/in $i
}
This maps the connections of the hypercube to the namespace of the process. The namespace of the process is a map of where that cpu’s name is located - a particular corner of the hypercube.
nCUBE Transit
nCUBE Transit was a Plan 9 based operating system used in the hypercubic nCUBE 3 supercomputer, and the nCUBE Mediacube 4 video streaming server. I can find almost nothing about the details of its operation or how it interfaced with and controlled the hypercubic routing. There is information on the earlier Axis/Vertex system, and I am curious if the Plan 9 implementation was similar. If you have any experience with the Transit OS or the history of nCUBE and especially how Plan 9 was used, I would be interested to hear from you at mycroftiv AT sphericalharmony.com.
What is a binary hypercube?
A binary (or boolean) hypercube is a mathematical structure in which a cubical graph of arbitrary dimensions is labeled with binary IDs such that the label of each vertex differs from the vertexes it is connected to in only one bit, and which bit differs corresponds to the direction of travel of the connection. Now that we said it, let’s see what it means. Take a square:
00---01
| |
10---11
The point to notice is that if we start at 00, we can reach 01 and 10 directly (rewriting a single bit in the ID) but it takes an intermediate hop to reach node 11. This square is a binary hypercube of dimension 2. Now imagine extending this pattern to three dimensions. We can do this by making a copy of the square and adding an existing bit to every ID so we now have IDs ranging from 000 to 111, and we put the new copy ‘above’ the original and connect the nodes in the obvious manner. We now have 8 nodes connected in a cube, and again each node differs from its neighbors by only a single bit. Copy the cube, add a fourth bit, connect the corners - now we have a 4d binary hypercube with 16 nodes. Obviously, we never have to stop so there are binary N-cubes for every natural number.
Let’s take a moment to think about some of the basic properties of a binary hypercubic graph. The most notable property in a Plan 9 context is that the ncube maps a literal “space of names” - an ncube of a given dimension contains every possible binary name of the corresponding bit length. Every possible 6-digit binary number appears as a vertex label of a 6-dimensional binary hypercube. The hypercubic geometry shows all the paths by which any string can be transformed into any other string - and the shortest path corresponds to the “Hamming distance” between the names of the nodes. It make take a bit of thought to visualize this. If you are given a string sych as “1001” and you want to transform it to the string “0100” you can do so by following a path in the hypercubic lattice. We will use a program, “hyper”, to verbosely trace the four dimensional path from 1001 to 0100 for us:
term% hyper -v -d 4 -f 1001 -t 0100
routing in 4 dimensions from 1001 to 0100
At: 1001 moving backward via dimension 0
At: 0001 moving forward via dimension 1
At: 0101 moving backward via dimension 3
arrive at 0100
So lets review the hypercube basics: a hypercube of dimension N will contain 2N nodes with all possible binary strings of length N as its node names. Each node(vertex) will connect to N other nodes with each other node name differing by one bit. The bit position which is different corresponds to which geometric dimension connects the nodes. The distance between nodes corresponds to how different the node names are - their “Hamming distance”. There are many other important mathematical properties, but this is the basic structure.
Origins in Gray code
Frank Gray, a Bell Labs researcher, was working on how to prevent errors when converting analog signals to digital. There were problems with potential intermediate states when binary was embodied with physical switches. Consider a set of two mechanical switches representing a pair of binary bits. When counting upward, there is a change of one bit from 00 to 01, but a change of two bits from 01 to 10. If equipment is receiving signals from these switches, there is a risk that the process of flipping two switches to change from 01 to 10 will produce a read of an inaccurate intermediate state, either 11 or 00 depending which of the two bits is flipped first. Gray realized you can construct a code in which only one bit changes at a time. Here is the 3 bit cyclical Gray code sequence compared with standard binary:
dec bin Gray
0 000 000
1 001 001
2 010 011
3 011 010
4 100 110
5 101 111
6 110 101
7 111 100
The Gray code is widely used in a variety of electromechanical controls and signalling systems. His system was published in the Bell Systems technical journal in 1947. About ten years later, another Bell Labs researcher, E.N. Gilbert, probably partly inspired by Hamming’s 1950 work on edit distance, developed the binary hypercube as a way to enumerate Gray codes. The reason for this is that the binary hypercube connections follow the same rule as Gray code - change one bit at a time. If you follow a path from node to node in a hypercube, the sequence of node IDs is a Gray code sequence. If you follow a path that visits every node once at ends at a node adjacent to your starting node, you have enumerated a cyclical Gray code by following a “Hamiltonian cycle” on the hypercubic graph. Gilbert realized that you could use the hypercubic graph to generate and categorize all the possible Gray codes for a given bit length.
History in Supercomputing
Over the next several decades, hypercubic graphs were studied both as pure mathematical objects, and as possible frameworks for communication and computation engineering applications. A 1977 paper by Marshall Pease proposed a hypercubic array of CPUs as a useful real-world topology. He showed that radix-2 FFT maps precisely to the structure of an indirect binary routing system, and that the hypercubic topology is of sufficient generality that other useful topologies can be expressed within it. During the 1980s, hypercubic processor arrays were a topic of active research, and the Caltech/MIT “Cosmic Cube” was a real world 64-cpu system with 6-cube interconnect topology. The nCube corporation was founded in 1983, and their first computer was released in 1985, with succeeding models in 1989 and 1995. The Plan 9 based Transit OS wasn’t used until the 1995 nCube 3. From about 1985-1990, massively parallel hypercubic supercomputers were a popular research topic and many papers were published along with commercial systems reaching the market. In addition to nCUBE, there was the Intel iPSC series and the Connection Machines. In 1988, Gustafson Montry and Benner used a 1024-processor nCUBE/10 to show that it was possible to achieve near linear scaling in efficiency with the number of processors for certain problems. As the 1990s progressed, the foundational work done by the “hypercubic pioneers” began to be applied to other topologies such as toruses. Modern supercomputers are built on concepts, algorithms, and techniques developed in the “hypercubic era” although the physical wiring no longer usually follows the full hypercubic topology.
Hyper.c routing tool
If we want to actually do some hypercubic routing, we want a tool to help calculate a few things for us. The most obvious is a function to calculate and output a route betweem two given IDs:
char src[32], dest[32], curr[32];
void route(int dim){
int i = 0;
while (i < (dim + 1)){
if(curr[i] != dest[i]){
if(verbose){
print("At: %s ", curr);
if(dest[i] == '1')
print("moving forward via dimension %d\n", i);
if(dest[i] == '0')
print("moving backward via dimension %d\n", i);
}
curr[i] = dest[i];
if(showports)
print("%d\n",i);
if(showids)
print("%s\n", curr);
if(onehop)
exits(nil);
}
i++;
}
if(verbose)
print("arrive at %s\n", curr);
}
The core logic for hypercubic routing is captured by the following expression, which simply marches through the bits from left to right and brings them into conformance with the target one by one:
while (i < (dim + 1)){ if(curr[i] != dest[i]){curr[i] = dest[i];} i++;)
The rest of the logic is concerned with various options for printing the output port at each transition, verbose output for demonstration purposes, and exiting after printing only the next hop rather than entire routing sequence. We want a few other things from our hypercubic routing tool. One is the ability to get a list of neighbors to a given ID:
void adjacent(){
int i;
for(i=0; i < dim; i++){
strncpy(dest, src, dim);
if(src[i]=='0'){
dest[i]='1';
} else {
dest[i]='0';
}
print("%s\n",dest);
}
}
Our remaining needed utility is finding the name of the node that is connected to a given output port of a given node ID:
void idquery(int port){
if(src[port] == '0'){
src[port] = '1';
print("%s\n",src);
exits(nil);
}
src[port] = '0';
print("%s\n",src);
}
Hubs and scripts on the spawngrid
What we need now is a system for actually creating the hypercubic communications topology and letting message sending and receiving agents communicate. The hubfs program is useful for creating general purpose network pipes that are mountable via 9p and we will attach scripts to hubfiles to act as message passing agents. The ‘spawngrid’ infrastructure enables us to create a base system image containing all the hypercubic tools, and then spawn a copy of this image in four different cities. Each city will be mapped to a different face of a hypercube, so we will have 4 nodes in each of Paris, New York, Chicago, and San Francisco. A node could be a fully independent cpu or namespace environment, but for simplicity for this proof of concept test, we will simply place 4 differently named hubs within each city spawned environment. We build the connections between cities using rimport of the neighboring machine’s /srv. This will enable the hubfses for the individual nodes to be accessed uniformly through /srv. Then we start 4 shells on each node within that constructed namespace, and assign the $mynum environment variable to all of the 16 possibilites, with the SF shells taking 0000 through 0011, Chicago 0100-0111, NY 1000-1011, Paris 1100-1111. Each of these shells then runs the routehub.rc script:
hubfs -t -s $mynum
mount -c /srv/$mynum /n/$mynum
touch /n/$mynum/in
Now that all 16 numbered hubs are present, they can all be mounted into the appropriate places in the namespace of each shell. routestart.rc finds the neighbors of the node and mounts their hubs, binds those hubs to the correct output port, and then starts cube.rc to pass messages:
fn findneigh {
neighs=`{hyper -a -f $mynum}
echo $neighs
}
dimension=`{echo -n $mynum |wc -c}
bind /tmp/cube /n/cube
neighbors=`{findneigh $mynum}
for(i in $neighbors)
mount /srv/$i /n/$i
cd /n/cube
for(i in `{ls}){
bindtarg = `{hyper -id $i -f $mynum}
bind /n/$bindtarg/in $i
}
cube.rc </n/$mynum/in
The cube.rc script simply reads messages in a loop. If the message matches its ID, it treats the body of the message as a command to be executed and logged, otherwise it calculates the correct ‘next hop’ via the basic hypercubic routing algorithm and sends that message to the cpu bound to the correct output port in the namespace.
while(msg=`{read}){
dest=$msg(1)
if(~ $dest $mynum){
echo $dest >>/tmp/cubelog
echo $msg(2-) |rc >>/tmp/cubelog
}
if not{
route=`{hyper -pno -d $dimension -f $mynum -t $dest}
echo $msg >>/n/cube/$route
}
}
Summary and development ideas
So, the story is that a series of Bell Labs engineers - Frank Gray, Richard Hamming, and E.N Gilbert - created a geometrical framework for spatializing systems of names and the relationships between them. A few decades later, the nCUBE company made physical computers embodying this structure, and created the Plan 9 from Bell Labs based Transit OS to run their 3rd and 4th generation hardware. Now two decades after that, the Plan 9 Advanced Namespace Tools spawngrid is running a hypercubic array which maps four cities to the faces of a hypercube and creates the spatial structure of the names of hypercube nodes using the namespace of Plan 9 processes.
Screenshot of fortunes being sent around the planet hypercubically
The next step is to create a system to take the Hamming distance of an arbitrary set of names, sort the list in that order, and then encode the sequence with Gray code to map any set of names to a minimal corresponding hypercubic structure. Additionally, a set of Gray codes could be provided to act as an embedded subnetwork within a hypercube. The goal is to enable a kind of ‘semantic namespace processing’ where a meaningful set of names can be assigned to processing nodes and the routing can correspond to semantically associated operations. It has long been a goal of ANTS to make the namespace structure do as much work as possible in organizing the behavior of the system. The fact that binary hypercubes offer a way to connect a fully arbitrary set of names in a meaningful and functional way to the namespace of Plan 9 processes in the manner summarized in this post offers numerous possibilites for further exploration. The fact that routing algorithms on binary hypercubes can be seen as functions from the Cantor set to the natural numbers also tantalizes.
An already existing possibility is of conceptual interest: ANTS allows the namespace of processes to be altered via the /proc filesystem. The location of a process within the hypercube is determined by the namespace of binds of that process and the processes mounting its hubfs. By rewriting the namespace of these processes, the location of a process within the hypercubic abstract space can be moved.
Code and questions
All code in this blog post can be found in the “extra/hypercubic” subdirectory of the main ANTS repo although it is likely to have evolved beyond what is present in this blog post, which corresponds to hg r304. I am planning to update this blog post with additional research and I would appreciate any corrections or suggestions. I am interested in correspondence on these matters at mycroftiv AT sphericalharmony.com.
References
“Gray codes and paths on the n-cube” Gilbert 1957 https://archive.org/details/bstj37-3-815 (The original binary ncube construction)
“The indirect binary n-Cube microprocessor array” Pease 1977 https://www.computer.org/csdl/trans/tc/1977/05/01674863.pdf (How to lay out 2d wiring/routing for hypercubic arrays, and applications)
“Hypercube algorithms and implementations” - Mcbryan & van de Velde 1985 https://www.archive.org/stream/hypercubealgorit00mcbr/hypercubealgorit00mcbr_djvu.txt
“Parallel computing on a hypercube: overview of the architecture and some applications” - Ostrouchov 1987 https://www.researchgate.net/profile/George_Ostrouchov?enrichId=rgreq-fe39ffac81e5bff885a16690b38ea061-XXX&enrichSource=Y292ZXJQYWdlOzIzMzQwOTMyNztBUzo5OTMyNjUyOTM3NjI3N0AxNDAwNjkyNjk5MTQ0&el=1_x_5&_esc=publicationCoverPdf
“A Survey of the theory of hypercube graphs” Harary & Hayes & Wu 1988 https://ac.els-cdn.com/0898122188902131/1-s2.0-0898122188902131-main.pdf?_tid=01b12d69-a6d8-41d2-a902-f7fb35d35a35&acdnat=1546308866_238bc5300af27a01df8d86e493b48222
Cosmic Cube and nCUBE
“The Cosmic Cube” https://web.mit.edu/6.173/www/currentsemester/readings/R01-cosmic-cube-seitz-1985.pdf
“A Microprocessor-based Hypercube Supercomputer” Hayes Mudge Stout Colley Palmer 1986 http://web.eecs.umich.edu/~qstout/pap/IEEEM86.pdf
“Development of parallel methods for a 1024-processor hypercube” http://www.johngustafson.net/pubs/pub16/1024.pdf
Patent - “Hypercube processor network” nCUBE 1993 https://patentimages.storage.googleapis.com/3c/e2/99/ddbd7c8f899c57/US5367636.pdf
“An overview of the nCUBE 3 supercomputer” https://www.computer.org/csdl/proceedings/fmpc/1992/2772/00/00234880.pdf
Recent papers
“Properties of the Binary Hypercube and Middle-Level Graphs” Ammerlaan & Vassilev 2013 http://article.sapub.org/10.5923.j.am.20130301.03.html (graph theory research on unsolved questions)
“Interconnection Networks with Hypercubic Skeletons” Xiao & Chen & Parhami 2015 https://cloudfront.escholarship.org/dist/prd/content/qt7sh8223k/qt7sh8223k.pdf?t=o0hzj3 (takes other network data and applies hypercubic paradigm)
“Hypercube-based Multi-path Social FeatureRouting in Human Contact Networks” Wu & Wang 2014 http://paws.kettering.edu/~ywang/file/TC%2012.pdf (focused on mobile applications and grouping nodes by feature analysis)
Misc web info
“Number of (directed) Hamiltonian paths (or Gray codes) on the N-cube” http://oeis.org/A091299
“Hypercubes and hypercubic networks” course notes, Gerbessiotis 2004 https://web.njit.edu/~alexg/courses/cis786/solutions/sub4.pdf
“Permutation routing in hypercubic networks” course notes, Tvrdik 1998 http://pages.cs.wisc.edu/~tvrdik/10/html/Section10.html
“Hypercubic networks” course slides, Leiserson 2003 https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-895-theory-of-parallel-systems-sma-5509-fall-2003/lecture-notes/lecture18_slide.pdf
“Hypercube graph” http://mathworld.wolfram.com/HypercubeGraph.html
https://en.wikipedia.org/wiki/Gray_codes
https://en.wikipedia.org/wiki/Hypercube_graph
https://en.wikipedia.org/wiki/Hypercube_internetwork_topology
Notes
Hartman and Winkler prove that we can always find a homeomorphic or squashed-cube embedding from K n+1 into Q n Hence there are homeomorphic and squashed-cube embeddings from any connected graph of order n + 1 into Q n.