Advanced Namespace Tools blog

04 January 2019

N-cubic algorithms

This post continues our exploration of hypercubic computing, as used by the nCUBE series of 80s and 90s supercomputers. The previous post explained the basic structure of the binary hypercube, its origins and use in computing, and showed hypercubic routing running on the spawngrid. This post will look more deeply at hypercubic, and show how algorithms for parallel computing can leverage the structure of the n-cube.

Hypercube full exchange template

This is the most generally useful hypercube algorithm template. It accomplishes the task of exchanging information between all nodes of an ncube in n steps. In other words, if we have 16 nodes in a 4cube, it takes 4 processing steps to transmit informatiion such that each node has access to the information present on all nodes. At each stage in the transmission process, a transformation can be performed. The following example simply accumulates the state.

   while(! ~ `{date -n} *0?)sleep .5
   echo $mynum `{date} >/tmp/cout.$mynum
   dim=`{echo -n $mynum |wc -c}
   input=`{cat /tmp/cin.$mynum}
   out=$input
   i=0
   while(! ~ $i $dim){
          echo $out >>/n/cube/$i
          newin=`{read}
          out=($newin $out)
          echo $out >>/tmp/cout.$mynum
          i=`{echo $i + 1 |hoc}
          sleep 1
          while(! ~ `{date -n} *[05])sleep .1
   }

This is a very beautiful algorithm in my opinion. It loops once for each dimension of the cube, and at each step neighbors exchange information along the dimensional axis corresponding to the loop counter. The algorithm begins with a possibly unique chunk of data present at each node, and concludes with each node having an identical copy of the fully processed dataset.

Hypercube logarithmic broadcast

This is the algorithm to fanout data from a given point on the cube, easily specified as the all-0 origin. It takes n steps to distribute data from a single node to all nodes of the cube. The initial boilerplate is identical to the above, with the loop body being:

   while(! ~ $i $dim){
          theirid=`{hyper -id $i -f $mynum}
          theirdec=`{echo 'obase=10; ibase=2; print '$theirid | bc}
          if(test $theirdec -gt $mydec){
                 echo $out >>/n/cube/$i
                 echo $out >>/tmp/cout.$mynum
          }
          if not{
                 msg=`{read}
                 out=($msg)
          }
          i=`{echo $i + 1 |hoc}
          sleep 1
          while(! ~ `{date -n} *[05])sleep .1
   }
   echo $out >>/tmp/cout.$mynum

The idea here is that at each timestep, the neighbors compare their ID numbers to see who has the larger number. That corresponds to being more hops away from the initiating 0 node, so the higher-numbered node receives a message. On each subsequent tick of the clock, a node that has previously received the data will be paired with a node with higher id, so the data is distributed in a powers-of-two fan out.

Hypercube dimensional collapse

I don’t think that name is commonly used, but it sounds cool and describes this algorithm well. It is the mirror image of the fan out algorithm, and is used to coalesce data to a single node, often with processing along the way. To show a simple example of actual hypercubic processing, I will use this algorithm as presented by nCUBE in their 1986 article on their machine. It computes the sum of squares of the elements of a vector of integers distributed among the nodes of the hypercube. This code includes the boilerplate setup section and is commented for clarity.

   #!/bin/rc
   # hypercubic sum of vectors ala nCUBE 1986

   # we need a decimal id for numeric comparisons
   mydec=`{echo 'obase=10; ibase=2; print '$mynum | bc}

   # we are using a very hacky clock-based step sync, we wait for a shared go moment
   while(! ~ `{date -n} *0?)sleep .5

   # initialize output file with id and timestamp
   echo $mynum `{date} >/tmp/cout.$mynum

   # set up dimension-1 as loop counter
   dim=`{echo -n $mynum |wc -c}
   echo $dim

   # get starting list of numbers aka our segment of the vector
   input=`{cat /tmp/cin.$mynum}
   # square the elements and sum them
   out=0
   for(i in $input)
          out=`{echo $out + ($i '*' $i) |hoc}

   # we run this loop for every dimensional connection in sequence
   i=0
   while(! ~ $i $dim){
          echo $i $out
   # find the id of our neighbor on the current port and convert to decimal
          theirid=`{hyper -id $i -f $mynum}
          theirdec=`{echo 'obase=10; ibase=2; print '$theirid | bc}
   # the cube collapses toward 0 origin so nodes with higher id send to lower
          if(test $theirdec -lt $mydec){
                 echo sending $out to $theirid on $i
                 echo $out >>/n/cube/$i
                 echo $out >>/tmp/cout.$mynum
          }
   # if we are a reader node we wait for a message and add it to our running sum
          if not{
                 echo waiting for msg...
                 msg=`{read}
                 out=`{echo $out + $msg |hoc}
                 echo sum is $out after adding $msg
          }
          i=`{echo $i + 1 |hoc}
   # we are using unix epoch second counts ending in 0 and 5 as our timing ticks
          sleep 1
          while(! ~ `{date -n} *[05])sleep .1
   }

   # save final state as output after completing loop
   echo $out >>/tmp/cout.$mynum

I love visualizing the operation of this algorithm in my mind. Imagining the hypercube ‘shutting itself up’ by telescope-closing through successive dimensions is a fun challenge in higher-dimensional visualization.

Code

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. 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