See, back in the day, maybe fifty years ago, it was traditional to build a deck using a single carpenter. Back then there were very expensive master carpenters who were affordable only to a very large pool of homeowners who needed decks. But even so, there were a lot of advantages to having even a small share of a single master carpenter. They had the benefit of coming with a complete set of detailed deck plans, and were very experienced at following those plans. They had a lot of apprentices who made sure the carpenter never ran out of nails or lumber. The carpenter and his apprentices were a tightly knit group who were used to working together and were pretty efficient at doing so. The deck plans were pretty straight forward to follow because everyone working on the deck knew their place and their role. The carpenter did all the actual deck building, and the apprentices were relegated to fairly minor roles. Guys like Thomas J. Watson built entire companies just on the training of master uni-carpenters, and did pretty well for a long time.
Not everyone could afford a master carpenter, so a single master carpenter was shared among many folks who needed decks. Since there was always some dead time while building a particular deck, due to weather or lack of materials or what not, the master carpenter could go next door and work on that deck for a while. The carpenter could slice his time up amongst several deck projects. Even so, it took longer to get your deck built because even when the weather cleared the carpenter wouldn't be immediately available to continue on your project. And of course the priorities of the other homeowners with whom you shared the master carpenter weren't always your priorities.
In time, maybe forty years ago, journeyman carpenters became available. They were cheaper but still fairly expensive, and not nearly as fast as the master carpenter. Their apprentices weren't as smart either. But a journeyman carpenter, sometimes referred to as a mini-carpenter, was cheap enough that a few neighbors could band together and hire one to share to get some of their rear decks built faster than if they had been sharing a single master carpenter among a larger pool of homeowners, even though the journeyman carpenter wasn't nearly as fast as the master carpenter. This worked pretty well for a long time, and guys like Ken Olsen made a lot of money training journeyman carpenters.
But about thirty years ago, high school shop classes started turning out wood working students. At first, they were pretty bad. They were very slow, they weren't very smart, they bent more nails than they hammered in, they didn't make very efficient use of lumber. But they were dirt cheap. So some individual homeowners started hiring these shop students to do small jobs that the master and journeyman carpenters never seemed to have time to do or care about. That worked pretty well. Shop students, or micro-carpenters, could build a fence, maybe build a small deck, maybe a set of stairs for an existing deck built by a master carpenter.
Around twenty years ago, someone got the bright idea of banding a bunch of shop students together into a large team, in a variation of the "nine woman can have a baby in a month" strategy. This is not as crazy as it sounds. Owners of very large homes, mansions and estates and resorts and such, had been doing just that for some time with master carpenters. They would band as many as eight master carpenters together, with a whole bunch of apprentices, great lots of lumber and nails, to tackle really big carpentry projects. You could think of it as a sort of super-carpenter. Guys like Seymour Cray were very good at creating these kinds of master carpenter teams.
It wasn't easy: in order to make effective use of eight very expensive master carpenters, the usual deck plans wouldn't do. You had to completely rethink the plans and the instructions so that each master carpenter could keep busy without getting in the way of another master carpenter, that each wouldn't run out of materials and have to sit idle (a very expensive proposition since you had to pay them anyway), and make sure that all the individual parts each was working on all fit together.
Designing the deck plans so that all eight master carpenters kept busy was no mean feat, and a lot of very smart people spent a lot of time coming up with those plans. Even so, there was a limit to how much parallelization could be found even in the biggest construction projects. Gene Amdahl, who started out training carpenters for Thomas Watson and went on to found his own carpenter training company, once rather famously observed that the amount by which a carpentry project could be sped up depended not just on the number of carpenters and the speed of each carpenter, but the degree to which the deck building instructions could be written to keep all of the carpenters busy at the same time. It was one of those observations that was both obvious and profound.
Some of those same smart people also designed some very specialized tools for the master carpenters to make better use of their very expensive time. My favorite was the vector hammer. The vector hammer had a single handle, so that it could be wielded by a single master carpenter, but had many heads, perhaps even dozens. A single master carpenter could, if he were careful, and everything lined up just right, drive dozens of nails at a time. So the deck architects spent a lot of time designing deck plans in which the nails all just happened to line up just right so that the vector hammer could be used.
Applying this same team idea to the high school shop students seemed like a winning proposition. But to get the same level of performance out of a group of high school shop students as you would from eight master carpenters, you would need a lot of high school shop students. How many? A lot. A guy named Danny Hillis made an ambitious attempt to harness sixty-four thousand high school shop students to build a single deck as fast as eight master carpenters.
Yeah, you see the problem now don't you? How do you rewrite your deck plans to keep sixty-four thousand high school shop students busy building a single deck? How do you even keep them supplied with lumber and nails? Keep them from stumbling over one another? It's almost impossible.
Oh, for sure, there were some successes. Some carpentry projects, like building a long picket fence, were embarrassingly parallel. If the fence were long enough, you could space the students out along the length of the fence line and have them all start building in parallel towards the next student, making sure to join the end of their fence section to the beginning of the adjacent student's. For a lot of projects, this actually worked pretty well. And you can be sure for the guy trying to get you to hire his sixty-four thousand shop students, those were the projects he used as examples in his sales pitch. But in general, no one knew how to design blueprints and write instructions to make effective use of that many high school shop students. Most of the students sat around idle, drinking energy drinks, while the few that could be kept busy slowly plodded along.
But a funny thing happened. Over time, as they got older and more experienced, the high school shop students individually got better. They started learning from their mistakes, started copying some of the techniques of the master carpenters, starting being more efficient at building decks. But remarkably there was one thing they didn't do: they didn't get more expensive.
Suddenly it became practical to use a single high school shop student to build a deck. Maybe not as fast as those eight master carpenters. But maybe almost as fast (or sometimes faster) than one of them. And the instructions for a single student to build a deck were so simple, even I could write them. As time went by, each high school shop student continued to get better and better. A guy by the name of Gordon Moore recognized that high school shop students would likely continue to get better and faster at a predictable rate for the foreseeable future.
Alas, it turns out that there were still limits to how fast a single high school shop student could build a deck. Students could only move so fast, could only drink so much energy drink (and had to take more frequent bathroom breaks). And no matter what, they didn't have the experience and knowledge of the master carpenters, so that in their haste to build a deck quickly they occasionally made a mistake, but because they were still pretty good at what they did, the mistake was sometimes subtle and hard for even the deck architects to find.
It was inevitable that someone would suggest that, just as the owners of mansions and estates did decades ago with master carpenters, a group of high school shop students be banded together as a team. First it was just a couple of students. Then four. Then eight were banded together in a team in what we might call a multi-carpenter approach. Some folks, like a guy named David Patterson and his friends who think about building decks a lot, have suggested creating teams of dozens or even hundreds of high school shop students, in what they call a many-carpenter approach.
Oh. Yeah, see, now we're back to the problem of decades ago when no one knew how to write instructions and deck plans for lots of carpenters. It's like we forgot what Amdahl said decades ago.
But the problem is even worse than it was way back then. See, using the one cheap but experienced high school shop student worked for so long and so well, that there are lots and lots of instruction books and architectural plans for how to build all sorts of cool things using a single carpenter. How detailed are these plans? One place where I once worked had an instruction book for its carpentry projects that was eight million lines long. That's a book of around 120,000 pages of instructions, all based on the assumption that a single carpenter would be working on them. This instruction book, portions of which dated back twenty years, generated this company as much as a billion dollars in revenue annually.
Where would you start breaking down eight million lines of instructions so that two carpenters, much less eight, or dozens, could all be kept busy building a deck? Oh, for sure, they've tried, but without much luck. After much effort, the carpenters still keep getting in each others way, tripping over each others lumber, accidentally hammering another carpenter's thumb.
And that's just the legacy deck plans. In fact, even if you're designing a brand new deck from scratch, no one really knows how to write deck building instructions to keep a lot of carpenters busy in parallel. Humans don't think that way. There are lots of ideas about abandoning English altogether and writing the deck building manuals in a new language better suited for expressing parallelism in carpentry. But there are an awful lot of carpenters and deck designers that already know English. And that doesn't do anything for all the myriad of English-language plans, blueprints, and instruction books that already exist.
As a homeowner, I think it is an interesting problem.
Acknowledgements
Thanks to Ken Mulvihill, Robert Gallegos, and Ken Howard for the inspiration.
Acknowledgements
Thanks to Ken Mulvihill, Robert Gallegos, and Ken Howard for the inspiration.
Tags
IBM mainframe supercomputer DEC minicomputer microprocessor multiprocessor Amdahl's Law Moore's Law Thinking Machines massively parallel processor MPP multi-core many-core threads multithreaded C C++ Java
IBM mainframe supercomputer DEC minicomputer microprocessor multiprocessor Amdahl's Law Moore's Law Thinking Machines massively parallel processor MPP multi-core many-core threads multithreaded C C++ Java
6 comments:
Cute, but I think the analogy got a little strained halfway down the page.
And I still think there is a better way to write the plans to use the mass of high school shop students.
Ken
No doubt. When I was in graduate school, I was lucky enough to be in a research group that was looking at software architectures and languages that mapped to the massively parallel architectures envisioned by the Japanese Fifth Generation project. But those architectures and language were then, and still are, extremely exotic, exploiting naturally parallelizing features (attribute grammars, single assignment variables, purely functional paradigms) that still have not become mainstream, and more importantly, aren't called C, C++, or Java. The technical and economic problems are harder than you think. How do I know? Because in twenty years they still haven't been solved.
Very interesting. I read your blog while drinking an energy drink by the way – Go Fast! You gotta support the local economy since it’s made right here in Denver, and I think it tastes better than Red Bull. And I can’t stand Rock Star – although I sometimes fantasize about…
But I digress.
I have only dabbled in the science of deck building and various construction plans throughout my career in industry and commerce. Recently, I have decided, even at my advanced age, to further my education on the subject of carpentry. (My friends wonder why I am studying about eunuchs, or the sequel to what?) There is a need, I believe, for people to gather all the various plans and blueprints, sort them, categorize them, and file them away so others can have access to them. Just as everything is relative, so everything should be relational.
As I begin to pry open door to the vast warehouse that is the deck building industry, I understand that I am seeing only a small kernel of the larger picture. And who would have guessed that the “phone company” would be responsible for developing some of the blueprints you discussed. I am also learning about some of the authors of those blueprint languages: Torvalds, Ritchie and Stroustrup, etc. Although they are all in English, I feel like ESL student. By the way, why do most of these guys have such strange names? Once again, I digress.
I can only imagine your dilemma as you try to design and build your deck. Even with your advanced degrees in architecture, your neighbors are building theirs faster, sometimes with fewer sometimes with more carpenters. It must be difficult to know the best way to proceed.
I think I shall go sweep the remaining snow and leaves of my deck so it will last another 20 years and I won’t have to face your problem myself. Good luck with the construction.
And remember: Don’t nail it – screw it!
Ken M
Oh, I cannot resist pointing out your common arrogance.
Most people would agree with your
"if it has not been solved in my (working) lifetime, it can't be solved" view.
How narrow minded.
Human history of problem solving is so much longer than a lifetime that it makes your narrow view laughable.
It just takes the right level of interest and integration of solutions from other areas of endeavor.
Ken H
Chip,
A fun post. I largely agree. The parallel problem is very hard, and many apps (most?) get little benefit.
I think in the embedded world asymmetric multiprocessing is usually a better solution than the SMP being pushed by the semi folks. (There are exceptions, YMMV, etc, of course).
Perhaps we will crack the secret of automatic parallelization of serial problems someday, but till then wise developers will be wary of claims made by the semi vendors. And even if that happens, one must do some serious analysis to make sure the sharing of the memory bus between cores doesn't strangle the CPUs.
Jack Ganssle
My career has transitioned back and forth over more than three decades between the real-time embedded world and the high performance computing world. I thought this was strange until some of the many-core papers that came out of David Patterson et al.'s group at Berkeley observed these domains required similar skill sets. That's been my experience too. So I spend most of my time working in the asymmetric MP world while nostalgically thinking about the symmetric MP world.
I haven't had the math for this since I left graduate school thirty years ago. But my intuition tells me a general automated solution to converting serial applications to parallel ones is if not at least intractable (equiv to the Halting Problem) then at least NP-Complete. We can at least agree that it is very very hard.
Back in the days of the Japanese Fifth Generation, we looked at all sorts of exotic OS and language features to exploit the MPP dataflow architectures that were envisioned. But even if those days are back, that doesn't help the enormous legacy code bases written in C, C++, and even Java. Like I said, it's an interesting problem.
Thanks so much for your comments. I very much enjoyed taking your seminar a few years ago.
Post a Comment