Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 142 lines (123 sloc) 7.461 kb
7feb07b @fintler Added initial papers.
authored
1 Space filling curves as interconnection topology
4184c50 @fintler Added name and date.
authored
2 By Jon Bringhurst
3 March 3rd, 2011
7feb07b @fintler Added initial papers.
authored
4
5 I haven't been able to find much information on how space filling curves, like
6 Hilbert curves, are used in network interconnection topology in supercomputers.
7 So, this paper is my attempt at putting the information in one place. We'll
8 start off with an introduction to gray encoding and how it relates to Hilbert
9 curves.
10
11 So, gray codes are the concept of the day here. Gray codes are just another
12 binary representation of integer counting (1, 2, 3, 4, 5, …). They were used
13 back in the day for mechanical counting because of a key property -- only one
14 bit changes for every value that a gray code is incremented or decremented.
15 This made it simple for a sensor to tell when the value had changed because
16 only one bit would be flipped every time. This is in contrast to normal binary
17 counting where it's common for multiple bits to be flipped for every time the
18 value is incremented or decremented which makes it difficult to tell if the
19 bits have all completely flipped into their final state.
20
21 Gray codes also have another special property. Some people like to call gray
22 codes "reflected binary codes". This property makes the generation of gray
23 codes feel very similar to the generation of a fractal. For example, start off
24 with the one bit gray codes -- you have 0 and 1. Now, to get two bit gray
25 codes, you write it forwards and backwards (0, 1, 1, 0). Then, prepend 0s to
26 the first half of the numbers and 1s to the second half of the numbers (00, 01,
27 11, 10) and you end up with the two bit gray codes. To get the n-bit gray
28 codes, you repeat the process n times from the base case.
29
30 Now the cool stuff. Gray codes have yet another story to tell. You can use gray
31 codes to reference a coordinate in a space filling curve known as a
32 "Hilbert Curve". Ignore the word "curve" for now -- it's just going to confuse
33 you. If you're like most people, you're going to think of a curve as a smooth
34 turn on a roller coaster or the shape of a hot air balloon. You'll think of
35 Hilbert curves like that eventually, but not now. Right now, you can safely
36 think of Hilbert curves in appearance as looking similar to the maze puzzles
37 on a paper placemat from a roadside greasy spoon that you solved with a wax
38 crayon as a child.
39
40 So, how do you use gray codes to reference locations in Hilbert curves? Lets
41 start off with the two bit gray codes. Just use each value like an x-y
42 coordinate. So, we have the coordinates of (0, 0), (0, 1), (1, 1), (1, 0) as
43 our first order Hilbert curve.
44
45
46 (0, 1) *---------* (1, 1)
47 | |
48 | |
49 | |
50 | |
51 (0, 0) * * (1, 0)
52
53 Now, lets try to do the second order Hilbert curve using the four bit gray
54 codes. To do this, we need to utilize the fractal properties of the Hilbert
55 curve. Each coordinate in the first order Hilbert curve needs to be replaced
56 by a new sub-curve that is the same shape as the first order curve. This new
57 sub-curve will be translated and rotated to fit in with the design of the
58 first order Hilbert curve. Once each of the coordinates has been replaced, we
59 end up with a second order Hilbert curve.
60
61 *-------* *-------*
62 | | | |
63 | | | |
64 | | | |
65 * *-------* *
66 | |
67 | |
68 | |
69 *-------* *-------*
70 | |
71 | |
72 | |
73 *-------* *-------*
74
75 To address each of the coordinates in the second order Hilbert curve with gray
76 codes, we need to reference the original location of the coordinate that was
77 replaced by the sub-curve. So, for example, the lower-right corner in the
78 second order Hilbert curve has a gray code with bits that start with "10...".
79 We can then get the rest of the gray code by again picturing the single order
80 Hilbert curve and rotating the visualization and then referencing that same
81 point after rotations in the lower order. So, the remaining part of the code is
82 "00" -- which makes the code for the lower-right corner "1000". Using the same
83 concept, you can use a gray code to find the location in a Hilbert curve.
84
85 Now, how does the conversion from gray codes to Hilbert graphs and back
86 actually help us when it comes to network topology? Lets look at a third order
87 Hilbert curve for some perspective.
88
89 *---* *---* *---* *---*
90 | | | | | | | |
91 * *---* * * *---* *
92 | | | |
93 *---* *---* *---* *---*
94 | | | |
95 *---* *---*---*---* *---*
96 | |
97 * *---*---* *---*---* *
98 | | | | | |
99 *---* *---* *---* *---*
100 (3) | (7) |
101 (2) *---* *---* *---* *---*
102 | | | | | |
103 (1) * *---*---* *---*---* *
104 (4) (5) (6)
105
106 Start from the lower left corner of the curve and start ordering each
107 coordinate as you go along. As you pass each coordinate, calculate a rough
108 estimate of the physical difference in distance between each coordinate.
109 You'll find that as you go, coordinates that are close to each other tend to
110 also be close to each other in their ordering. The number of each coordinate as
111 you go along and give each a value is known as the "Hilbert integer".
112
113 Now that we have a bit of a base, we can try to relate this to interconnection
114 topology. First things first, we need to have a picture of a 3 dimensional
115 Hilbert curve. So, instead of filling up a 2 dimensional space through each
116 order of the curve, we fill up a 3 dimensional space by adding a rotation into
117 the third dimension to each translate and rotation in 2 dimensional space.
118
119 *
120 * |
121 |\ |
122 | \ |
123 | * | *
124 | | | |
125 *-----* |
126 | |
127 | |
128 *-----*
129
130 Now that we have a topology that closely resembles the node structure in a 3D
131 torus network structure, we can start thinking about how nodes are allocated.
132
133 Remember the concept of a Hilbert integer? That's going to be the node ID of
134 every node in the supercomputer. When the Hilbert integers of each node are
135 generated, they're stored by the central resource manager and stored for the
136 duration of the resource manager's lifecycle. After being sorted into a one
137 dimensional array, the node IDs can then be effectively used by a scheduler to
138 provide resources to jobs at a level of abstraction where the scheduler doesn't
139 need to worry about the actual node topology.
140
141 EOF
Something went wrong with that request. Please try again.