Previous | Next --- Slide 24 of 50
Back to Lecture Thumbnails
kprewitt

One thing that I think could be interesting from this is that adding an edge from any core to the bitwise negation of its representation would only require another link for every two cores, but should decrease the diameter by half.

If it were 6-dimensional, then the original diameter would be 6, but by adding this link, we would be able to get from 000000 to any node in at most 3 hops, as if a node has at most 3 1's in its representation, we can go directly, and if it has more, we can jump to 111111 and make it to the core in at most 2 hops.

The only issue I can see with this is some of the links are likely to be notably longer than others, but with the hypercube implementation for higher dimensions, we might already have this issue to some degree.

mchoquet

The hypercube design seems really cool in theory, but I think they mentioned in class that very few computers actually use this format. What you said about nonuniform link lengths is probably a drawback; I can think of a couple others:

  1. For higher dimensions, each router has a high number of wires going into it, which might increase routing complexity.

  2. For anything higher than 3-D, projecting this design onto a 2-D circuit in a space-efficient way is probably extremely hard.

jinghuan

What are properties of hypercube? Direct/indirect? blocking/non-blocking? What is the cost? What does it mean radix and number of links?

retterermoore

Let's see if I can take a stab at these:

I think it's direct, as there weren't separate router nodes and non-router nodes drawn.

It's blocking, as you can't get from 0,0 to 1,1 and 0,1 to 1,0 simultaneously on the 2D hypercube.

Cost is the number of links, O(n log n)

Radix is the number of links out of each node, which is O(log n) since each of the log n bits of an n-bit binary number node can be flipped to give you a neighbor of that node.