Monday, December 28, 2015

Making a Raspberry Pi Cluster's Rack

The frame, fully assembled, with trays

It's hard to play with a Raspberry Pi and not wonder what a bunch of them wired together could do. We're talking about $40 computers with 1GB RAM, a quad-core 900MHz processor, and a GPU, all on a credit card-sized board. They're not too far off, specs-wise, from the ThinkPad X60 I'm typing this post on. All that with a $40 price tag -- how could you not want as many as possible?

It probably wouldn't surprise anyone who knows me to learn that I've been working on doing exactly this: wiring a bunch of Raspberry Pis into a cluster for distributed computing. I've now collected enough of the hardware that the big priority is building a rack to keep it all organized. There are a bunch of cool Pi cluster rack designs out there. One 3D-printed design stands out in particular, both for the idea behind it and the implementation. I considered a few different designs, but none were a perfect match for my goals. In the end, it seemed like the best option was to roll my own rack.

Every design is tuned to the resources available to its designer. Being at my family's house for a week over winter break, I had a seven-day window of access to my dad's wood shop, his CNC machine, and his help. Naturally, I was inclined to take full advantage of all three. First of all, though, came deciding what exactly it was we would make.

Design
A few different design constraints are involved here. I wanted every Pis easy to access or remove. I wanted the finished product to look nice. I wanted to keep the footprint small, because this thing is probably going to live on my desk. It was also important to make sure the design wouldn't restrict airflow, because this cluster will be running some long jobs without any heat sinking. Lastly, budget dictated an eight-board setup.

I decided to power over USB, because my understanding is that the Pi has a protective self-resetting fuse in line with the USB power input. This fuse keeps power supply malfunctions from permanently destroying your board, but powering over GPIO seems to bypass this protection. I didn't put too much time into verifying this info, since I heard it from a trusted source, and in any case powering the boards over USB from a couple externally powered hubs is also nice and simple. If I ever decide to overclock these boards (and, let's be real, that's happening sooner or later), I'll probably enlist some help and make a custom power supply to deal with the increased power demands at that point. Maybe mount some heat sinks, too.

These parameters together with the tools available led me to the design you saw above. It's a vertical rack of five trays: on the bottom, a tray for USB hubs and an 8-port Ethernet switch; above it, four trays, all set up to mount two Pis each. Each Pi mount point also has an elliptical hole to promote airflow. It seemed important not to neglect either side of the boards ventilation-wise, since both sides of the Pi 2 have important chips on them (CPU and GPU on top, RAM on bottom). The Pis are rotated 180 degrees from each other, so that both have their Ethernet port and USB power input exposed.

The final design.

The Pis dictated the dimensions of the trays, which in turn dictated the dimensions of the wooden frame. The frame, assembled from square cuts of 3/4-inch-thick mahogany, ended up with a footprint of just about 7.5x5in (disregarding backstops), and a standing height of 9.5in. After cutting as many square beams as possible from the board, there was a thin strip left; we cut from this two more 9.5in pieces and used these as backstops.

Assembly
It was only in hindsight that I realized how simple this process really is. The vast majority of our time was spent not on woodworking but on trying to troubleshoot the CNC machine toolchain. There don't seem to be nearly enough mature open-source projects in this domain. This is an area where a few dedicated programmers could make a respectable impact. The process of setting up a working toolchain was so painful that I'm not going to say another word about it, except to note for posterity that when we did get things working it was using the proprietary tools provided by the manufacturer (Shapeoko) start-to-finish. One wishes that there could be a better way.

The CNC machine, hard at work cutting a tray. Not pictured: hours and hours of troubleshooting.

Anyway! Enough of that. The tray design ended up being pretty simple -- two pairs of four screw holes lined up to the Raspberry Pi's mount hole dimensions (link is to B+ measurements, but the Pi 2's hole spacing is identical). With those set to mill, it's time to cut some wood! We had this nice, light, 3/4-inch-thick mahogany lying around, so we used that, cutting as much as possible into square rods and cutting these rods down to the various lengths needed (four each at 3.5in, 6in, and 9.5in). This left a thin residual strip from the end of the board, which we later cut into backstops. But before backstops come tray slots, and before tray slots, the frame's sides need to be assembled.

The sides were easy enough to build: just take the relevant cut-to-size pieces (after sanding them reasonably smooth!), measure out whatever ground clearance you might want, glop some wood glue onto the points of contact, press everything together, slap on some clamps, and let it sit for a good long while.

Letting it sit.

Cutting the slots is easy, too, if there's a tablesaw around: just measure & mark the slot locations, lower the blade so it extends from the table by however deep you want the slots to be, and gouge away. I opted to be sort of generous with the cut depth (after all, better too wide than too narrow), but what I've come to realize is that the tolerance used here has a surprisingly big impact on how cleanly the trays slide in. It pays to be as accurate as possible.

Once the slots are cut, it's time to glue up the other four crosspieces and bring the whole frame together. This step was a bit tricky, since all four beams have to be left to set at roughly the same time in order to keep everything nicely aligned, which turns out to be easier said than done. The problem is that once two pieces are in and clamped down, the remaining ones get progressively harder to wedge in without losing most or all of their wood glue. I really don't have any better advice than to use generous amounts of glue (remember that spillover can always be cut/scraped/sanded off) and to have two pairs of hands involved: one person gently pulling the soon-to-be contact points apart, and another person to put the new beam in and get it lined up just right.

Do not disturb.

Once this glue cures, the frame's complete except for backstops. These really could not be easier to attach, especially compared to what came before them.

After that, all that's left to do is sand this puppy damn smooth and slap on some finish. This wood took the finish well, each coat drying pretty quickly. We put on ballpark four or five coats (who counts?), continuing until it looked good, then sanded it down and added a final layer.

A delicate process.

Oh -- there is one more thing left to do, and that's to mount the Pis on their trays. As you can see, we hit a slight gotcha here:

Asymmetry... adds character?

If you think it looks like those boards are missing half their standoffs, you're absolutely right. Here's what happened. We drew up our parts list for screws, standoffs, nuts, and washers, and rolled on down to the local hardware store (Stone Way Hardware, great place). Tracking down the 2.5mm hardware took a while, since just about nobody except computer & electronics hobbyists use this stuff... arguably for good reason. Turns out the stock was pretty sparse. We asked if they might have more "in the back". No such luck. The clerk commented, after hearing the amounts we were looking for, that we wanted as many of these components as they sold in about two years. He didn't seem particularly moved by the chance to get two years ahead of quota, and so we had to make due with half of everything.

Fortunately, it only really takes two screws & standoffs to do a "good enough" job of mounting a Pi if you install them diagonally from each other. It's not pretty, but it works. The boards are mounted and stable now, but I definitely plan to get the rest of the hardware at some point down the road. It'd probably be better for the boards, and it'd just look better besides. Maybe I'll check back in at Stone Way in a couple years.

The rack, with a network switch in its tray and 6 out of 8 Pis mounted

Wednesday, December 9, 2015

Thoughts on some 2015 Putnam Exam Problems

Now that a few days have gone by, I thought I'd write a few notes on things I found interesting while working on this year's Putnam exam.

This year's problems seemed pretty different from last year's. That year, I had trouble making use of all my time; this year, I found myself working into the last five minutes in each session. The A section felt very approachable in particular; B was certainly more arcane, but still didn't feel prohibitively so. There were interesting problems to talk about on both sides.

A PDF with this year's problems can be found attached to the first post here: (link)

A1, B1

Like last year's A1, these were easy problems whose main barrier to solution was that they required some nontrivial background knowledge. Not particularly interesting or exceptional.

For A1, this comes down to the fact that there's a simple geometric property which uniquely defines the point P. This in turn allows simple algebraic expressions for the two small areas under the chords AP and PB, and once you have those it's just a matter of integral-crunching to prove their equality.

For B1, it's a question of how much you know about the relevant facts in analysis. I didn't take the time to work out a full solution; the curious can find a good discussion here. The idea of letting g(x) = f(x)h(x), then working out first three derivatives and looking for interesting properties seems to bear fruit. It is useful to remember that if h has no zeroes, then g's zeroes are exactly f's zeroes.

A2

This was a fun one. The sequence is easy to work out by hand; it's also easy to work out a closed form for arbitrary terms. Doing either of these things can lead to the solution, if they are paired with the right ideas. The important first impression in either case is that since we're talking about odd prime factors, we should be on the lookout for properties concerning divisibility and prime factorization.

The straightforward way to find the closed form is by noting that the sequence can be modeled in terms of vectors and matrices:


allows one to obtain vectors containing consecutive elements of the sequence. It's possible to get the closed form of the sequence from this representation by solving for the matrix's eigenvectors and rewriting the starting vector as a linear combination of them. This makes it easy to get rid of the matrix. The closed form allows us to figure out some properties about certain elements of the sequence dividing others, and that gets us well on our way.

Working the sequence out by hand also can be surprisingly useful. In fact, the first thing I did was work out the first eight terms or so by hand and find the prime factorization of each one. This greatly helped to inform the rest of my strategy.

Note that a simple pigeonhole argument shows that the sequence is eventually periodic under any modulus. This means that if we work out the sequence mod p until we've found where its periodicity starts and how long the period is, then we can predict all indices n such that p divides a_n.

That strategy, while guaranteed to eventually work, will kind of take a while. The astute problem-solver can probably expect that no small primes bear fruit under this approach -- that would be too easy! So, while we could work out all the sequences up to say p=17 and cross our fingers that one of them turns out to have a zero at index 2015, there's probably a better use for that time. If we're committed to this strategy, though, then what other primes can we use? Well, a_5 = 2*181, which is a pretty big prime that shows up in a pretty weird place -- that might be worth checking out, right?

Right, indeed. If you do the arithmetic right, you find that 181 turns out to divide a_2015. Sometimes it pays to trust your intuition!

As an aside, there exists an interesting sort of symmetry between the zero terms of the sequence. Here, for example, is the start of the the sequence mod 181:

1, 2, 7, 26, 97, 0, 84, 155, 174, 179, 180, 179, 174, 155, 84, 0, 97, 26, 7, 2, 1, 2, 7, 26, 97, 0, 84, 155, 174, 179, 180, 179, 174, 155, 84, 0, ...

See the symmetry? Where's that coming from?

A3

Still kicking myself for this one. The insufficiently careful might think, as I in the haze of 10-minutes-left-in-the-session adrenaline did, that the exponent can be rewritten as,
which would sure make things a bunch easier! Sadly, the last step of this simplification fails to account for complex roots of unity -- something which, a few minutes into the break, I was absolutely kicking myself for. Even in the moment, it felt too easy. The actual solution methods turn out not to actually be that difficult -- more on that from the usual scary-smart folks here.

B2

This problem was so cool. Seriously. If you haven't tried it yet, you probably should. The patterns are really interesting and formulating rigorous arguments around them is a surprisingly tricky exercise. I don't want to say too much, because I don't want to spoil the fun of it -- the comments below will start out general and get gradually more specific. One word of warning: be cautious of conjectures concerning periodicity until you see a good proof for them.

It's possible to prove constraints on the least significant digits of terms in the sequence, and it's possible to put some useful constraints on their density. Once you have those tools, it's a short jump to finding large sums guaranteed to be in the sequence. If you find general forms for these sums, you can set them equal to 2015 mod 10,000. Then, if you know the extended Euclidean algorithm, you can invert any multiplications in these expressions and end up with some very strong hints about conditions sum terms would have to satisfy, if they exist at all.

Carefully following this line of thought, I was able to show that 4668+4669+4670 is in the sequence, which in turn implies that 14004+14005+14006 is. This is all we need, since 14004+14005+14006 = 42015 blaze it

I found it really helpful, in formulating these steps, to write out the first 60 positive integers in a 10x6 grid and work out the start of the sequence on this grid, crossing out summands and circling sums, doing my best to place sums > 60 roughly where they would appear if the grid extended far enough to include them.

B3

Interesting problem. It can be done through casework if you have the linear algebra chops. There turn out to be two main categories of matrices satisfying the condition. I definitely would've worked on this one if I'd had more time, but making sure my B2 argument was rigorous took way too long. Lesson learned: practicing formally writing up unusual arguments can be a productive use of one's time.

B4

There is a technique known as Ravi substitution which I had never heard of before reading about this problem, but which turns out to be well-known at the higher levels of competitive problem solving. It allows one to simplify the sides-of-a-triangle constraint. As far as I can tell, there seem to be two different forms of Ravi substitution: one for when the sides are reals, and one for when they are integers.

If the sides a, b, c are reals, it turns out that the sides-of-a-triangle condition is equivalent to specifying that there exist some positive reals x, y, z, such that a = x + y, b = x + z, and c = y + z.

If the sides a, b, c are integers (as in this problem) then that substitution is not possible, but several others are. For instance, we can define x, y, z as x = a + b - c, y = a + c - b, z = b + c - a. We can use the triangle inequality to trivially prove that x, y, z are all positive, and some mucking about with parity lets us set up a nice bijective property between triples a, b, c, and triples x, y, z. Once we have that, we can make substitutions and crunch out algebra. BIGTRO's comment in this thread works this line of thought out to the end; I wish I'd had the time to try and find all this.

B6

This is a really interesting problem, but I think that whoever came up with it may have been criminally insane. That's all I have to say here.