Classic software engineering and the mighty pigeon

A diligent member of my army of stringers, researchers, fact-checkers and miscellaneous hangers-on forwarded me a BBC article on a contest between South Africa's broadband carrier and a carrier pigeon. The pigeon carried a 4GB memory stick 60 miles in 2 hours. In the same amount of time, the broadband connection had transmitted 2% of the data. Pigeon 1, broadband nil.

Is this really news? First, how fast was the broadband connection? 2% of 4GB is 80MB. 80MB/7200s = 11KB/s. OK, that's pretty slow. For comparison, I just ran a speed test against a server about 60 miles away. The download speed was about 14Mb/s, or about 2MB/s. That would bring me my 4GB in about 40 minutes. Pigeon 1, broadband 1.

But wait. I can only download as fast as the other end can upload. If the other end has my broadband connection, it can upload at about 360Kb/s or about 45KB/s. You read that right. My upload speed would appear to be about a fortieth of my download speed. That's about four times the speed of the South African connection, meaning I couldn't even get 10% of the data transmitted by wire before the pigeon reached its destination. Pigeon 2, broadband 1.

Hmm ... my ability to send large quantities of data -- movies, for example -- to the world at large is severely limited, but my ability to access said data from whoever can make it available quickly isn't. And my internet connection is provided by a Cable TV/old-school media company ... but I digress.

When I got the link about the South African pigeon, I immediately thought of Jon Bentley's classic Programming Pearls and More Programming Pearls. If you're interested in software engineering you could do worse than to stop reading this right now, go hunt down copies of these books and inhale them. The code samples are variously given in C, C++ and a procedural pseudocode reminiscent of Old High Algol, but just as Chaucer is worth the trouble of reading in the original, so too Bentley.

If you don't want to hunt down paper copies, check out the web site [The web site doesn't carry the entire book, but it's still well worth visiting. The book itself has been extensively updated in the recent second edition. There's even a little Java here and there, but only a little. The Labs is still the Labs, after all].

I assume you're back now and along the way noticed problem 11 in column 1 of Pearls:

11. In the early 1980's Lockheed engineers transmitted daily a dozen drawings from a Computer Aided Design (CAD) system in their Sunnyvale, California, plant to a test station in Santa Cruz. Although the facilities were just 25 miles apart, an automobile courier service took over an hour (due to traffic jams and mountain roads) [Ah, Highway 17. Good times, good times.] and cost a hundred dollars per day. Propose alternative data transmission schemes and estimate their cost.

The solution Lockheed came up with?

The computers at the two facilities were linked by microwave, but printing the drawings at the test base would have required a printer that was very expensive at the time. The team therefore drew the pictures at the main plant, photographed them, and sent 35mm film to the test station by carrier pigeon, where it was enlarged and printed photographically. The pigeon's 45-minute flight took half the time of the car, and cost only a few dollars per day. During the 16 months of the project the pigeons transmitted several hundred rolls of film, and only two were lost (hawks inhabit the area; no classified data was carried). Because of the low price of modern printers, a current solution to the problem would probably use the microwave link.

Pigeon 3, broadband 1.

For several obvious reasons I doubt that pigeons are going to be the optimum solution for most high-volume data transmission problems, but it certainly gives one pause to note that a generation after the Lockheed story, in the face of Moore's law and all that, pigeon power is still a plausible solution. At least compared to what passes for broadband here in the States.

Why should this be? Moore's law cuts both ways. In fact, it currently favors the pigeon. The South African test was done with a 4GB memory stick. Sticks of 16GB are now available. Leaving aside the question of whether a pigeon (or two) could carry more than one stick, even a single pigeon with a single 16GB stick could beat my download speed over a 60 mile course.

Memory sticks are getting bigger much faster than broadband is getting faster, if only because switching to a larger stick is much, much easier than switching broadband technologies.

This is all reminding me of my early posts on Jim Gray.

The game is changing

When I'm beating my "not-so-disruptive technology" drum, I'm not trying to say that technological change has no effect. Rather, technological change is more gradual than we might sometimes think. Over time, it can have significant effects. The rule of thumb I've heard is that predictions overestimate the short term and underestimate the long term.

For example, over my lifetime Moore's law has tracked orders of magnitude worth of steady improvement in hardware. This progress has been accompanied by a steady stream of discoveries and algorithmic improvements on the software side (and a counterbalancing accumulation of layers between the code and the hardware, but that's a separate story).

In the early days of AI, there was much breathless talk (not necessarily by those actually doing the research) about the "electronic brain" being able to match and surpass the human brain. Only later did it become clear that this vastly underestimated the sheer computational power of a human brain -- or a gerbil brain, for that matter.

A classic AI program, say SHRDLU, ran on a PDP-6 and processed small chunks of text to maintain a set of assertions about a toy "block world". It was definitely a neat hack, and it looked pretty impressive since, as everyone knew, language processing is one of the highest levels of thought and therefore one of the most difficult [Re-reading, that's not quite right. Language processing really is hard in its full glory. However SHRDLU, like everything else at the time, did fairly rudimentary language processing. The "gee-whiz" part was that it could keep track of spatial relations between blocks in its block world. My point was that this is actually much, much simpler than, say, walking. So for "language processing" read "reasoning about spatial relations".].

In fact, "high-level" abstract thought is going to be about the easiest type of thought for a computer to mimic -- the computer itself is the product of exactly that sort of thought, so a certain structural suitability is to be expected. This is probably clearer in hindsight than at the time.

An oversimplified view of what happened next is that we began to understand and appreciate a few key facts:

• Biological minds are much more complex than a PDP-6. There are hundreds of billions of neurons in the brain, versus (somewhere around) hundreds of thousands of components in a PDP-6, most of which would have been core memory (by which I mean actual magnetic cores).
• Biological minds are distributed and work in parallel. For example, the eye is not a simple camera. The retina and optic nerve do significant processing before the image even reaches the brain.
• Biological computation is not based on abstract reasoning. Rather, the other way around. Biological computation has a much more statistical, approximate flavor than traditional symbol-bashing.

and so, again oversimplifying, the AI bubble burst. Everyone now knew that AI was a pipe dream. Best to go back to real work.

"Real work" meant a lot of things, but it included:

• Figuring out how to handle much larger amounts of data than, say, dozens or hundreds or even thousands of assertions about blocks in a toy world, and how to make use of hardware that (currently) throws around prefixes like giga- and tera-.
• Figuring out how to build distributed systems that work in parallel.
• Figuring out how to handle messy, approximate real-world problems.

Hmm ... three bullet points up there ... three bullet points down here ... almost like they were meant to be compared and contrasted ...


The jumping-off point for all this was observation in the previous post that our internal data network appears to have capacity comparable to fairly fast off-the-shelf digital networks. This rough parity is a fairly recent development.

Necessary, but not sufficient

While I've just argued that bigger, faster and better-connected computers do not automatically give rise to qualities like intelligence or consciousness, and that some aspects of intelligence require very little computing power, that doesn't mean that every aspect of intelligence is trivial.

A demo like the Big Dog is possible not only because many people have worked very hard at understanding how animals move and how to explain that to a computer, but also because we now have absolutely sick amounts of computing power available compared to a few decades ago when the serious speculation started.

For example, the first computer chess program could just barely follow all the rules (or could it do even that?), but before long the main elements of computer chess as we know it today were in place. Deep Blue beat Kasparov partly due to constant incremental improvements in the underlying software, but mostly because the hardware came to be able to crunch out so many positions that it could see farther ahead and make "positional" moves out of sheer calculation.

Image processing has come a long way, to the point that cameras can more or less recognize faces (i.e., that these pixels are probably a face, not that it's your face). Some of this is due to better understanding and better algorithms, but even the best algorithm is not going to run in reasonable time without a high-octane pixel-smasher working behind it.

In short, progress is coming from painstaking research aimed at understanding the problems to be solved and getting the code to run, and it's coming from continual advances in hardware performance. Both are necessary. Neither is sufficient alone.

Sixty-year-old computer slower than modern emulator. Film at a 11.

I suppose that's not really a fair summary of this BBC article on a commemoration of the cracking of Nazi codes by Colossus, one of the first modern computers (depending on one's definition of "computer"). Still, it hardly seems surprising that an emulator running on a laptop would be faster than the 1940's original.

Re-assembling Colossus and getting it running, though -- that's a neat hack. Especially since the original machines were cut into pieces after the war.

We'll be with you after a brief delay ...

One of Deutsch's distributed computing fallacies is that latency is zero -- messages arrive the moment you send them. In practice, it takes a bit of time for your message to get through your firewall to your ISP's router, onto the backbone, to your recipient's ISP, through their firewall and to their host.

Much of the time, this won't matter. If your mail client is polling every five minutes, who cares if the packets containing your email took some fraction of a second to get to your mail server? On the other hand, if you're trying to do something on the net that requires precise synchronization, things can get hairy.

The Network Time Protocol keeps good time (to within about 1/100 of a second over the internet), but NTP relies on propagating accurate timing out from a small set of central servers. It doesn't try to keep everyone in sync with each other directly.

Depending on the circumstances, people can notice delays as low as 20-40 milliseconds. For example, a lag of 40 milliseconds between hitting a key and hearing a sound is enough for a musician to notice. Echoes become perceptible around 100ms and extremely distracting not long after.

Latency on a local network can be quite low, often just a few milliseconds. The round-trip time for pinging a major service can be in the teens and twenties. This is partly because the major providers replicate their servers so that you're generally talking to a server close to you.

For example, I pinged www.google.com.au (Google Australia) and got a round-trip time of about 15ms. That's pretty impressive, given that I'm about 15,000km from the nearest point in Australia and light travels at 300,000km/s. That would give an absolute minimum time of 100ms for the 30,000km round-trip. However, the name www.google.com.au resolves (where I'm sitting) to a server in Mountain View, CA. That's fair game, as long as the Mountain View server looks enough like the "real" one Down Under.

However, if I try to ping the Australian Broadcasting Company (which probably has little reason to put a duplicate server in my neighborhood), I get a more believable time of 200ms or so. Depending on circumstances, that much delay can cause problems. For example, a badly placed speaker phone in a conference call between Oz and the US can render conversation nearly impossible.

As it turns out, most of the populated world has water directly opposite on the globe, but there are a few extreme cases, such as Hamilton, New Zealand and Córdoba, Spain. There are also plenty of less extreme cases, whether Europe/Australia, California/India or what-have-you, where even the best case may introduce noticeable delays.

The high-order bit here is that some level of humanly perceptible latency is likely to be with us, in particular situations, no matter how fast the hardware gets. Moore's law can make the pipes bigger and the processors faster, but it will do nothing to increase the speed of light.

What killed parallel computing?

When I was an undergrad, parallel computing was the Next Big Thing. By "parallel computing" I mean a large number of CPUs that either share memory or a have relatively little local memory but pass (generally small) messages on a very fast local message bus. This is as opposed to distributed computing, where CPUs have lots of local memory and communicate in larger chunks over relatively slow networks.

So what happened? Multiple choice:

• What do you mean "what killed it?" Supercomputers today are all massively parallel. Next time you do a Google search, thank a cluster.
  
• Distributed computing killed it. If you want to really crunch a lot of data, get a bunch of people on the net to do it with their spare cycles, a la SETI@home and GIMPs.
• Moore's law killed it. Most people don't need more than one or two processors because they're so darn fast. Sure you can use parallel techniques if you really need to, but most people don't need to.

Personally, I'd go with "all of the above" (but then, I wrote the quiz).

Another worthwhile question is "What's the difference between parallel and distributed anyway?" The definitions I gave above are more than a bit weasely. What's "relatively small"? What's the difference between a few dozen computers running GIMPs on the web and a few-dozen-node Beowulf? At any given time, the Beowulf ought to be faster, due to higher bandwidth and lower latency, but today's virtual Beowulf ought to be as fast as a real one from N years ago.

A distinction I didn't mention above is that classic parallel algorithms have all the nodes running basically the same code, while nodes in distributed systems specialize (client-server being the most popular case). From that point of view the architecture of the code is more important than the hardware running it. And that's probably about right.

A few more "Rules of Thumb" highlights

More tidbits from Rules of Thumb in Data Engineering:

• In ten years RAM will cost what disk does today.
• A (full-time) person can administer a million dollars worth of disk storage (if I got the math right, that's about 3PB these days -- it was 30TB in 1999)
• In 1999, a CPU could keep 40-50 disks busy (and for some applications it should be doing just that). The number is probably not changing very quickly.
  
• At the time the article was written, two ratios appeared to be dropping rapidly. If the predictions held true (I haven't checked yet), the impact could be significant:
• The CPU cost of network access vs. disk access, measured both per message and per byte.
• The dollar cost per byte transferred of WAN vs. LAN
  
• You should pretty much always cache a web page.
  

Jim Gray et. al. on disks and scan times

Here are a couple of highlights Jim Gray and Prashant Shenoy's 1999 paper "Rules of Thumb in Data Engineering", with approximate updates for 2007.

Two key parameters for disk storage are

• Price: 1994: $42K/TB. Predicted for 2004: $1K/TB. Seagate currently offers a 500GB drive which can be had for $180, or $0.36K/TB. This isn't the bleeding edge. Seagate is announcing a 1TB drive, and I haven't done anything like a thorough search across all manufacturers.
• Scan time (time required to read every byte on a disk or other medium): Disks have been getting faster, but they've been getting bigger faster than they've been getting faster. In 1999 a typical 70GB drive with a transfer rate of 25MB/s would scan in about 45 minutes. The paper predicts 500GB, 75MB/s and 2 hours for 2004. The Seagate 500GB drive can sustain 72MB/s.
  

The price trend is just Moore's law. The main lesson, as with most hardware, is don't buy any more than you have to. It'll be cheaper tomorrow.

Increasing scan time has more subtle but crucial effects. We're used to thinking of disks as random-access devices (at least in comparison to, say, tapes). That's why we use them for virtual memory. But they're actually becoming more like tapes and less like RAM. Random access on a disk takes seek time and rotation time. Sequential access just takes transfer time. Seek time and rotation time are becoming more and more expensive relative to transfer.

This has a whole host of implications. Some that Gray and Shenoy mention:

• Mirroring makes more sense for RAID performance than parity. With mirrors you can spread read accesses out across multiple copies, clawing back some of the lost random access performance.
• Mirroring also makes more sense for backup. Gray and Shenoy look at tape backup and conclude that tape storage will soon (i.e., now) be purely archival. It just takes too long to scan through all the data on tape. They don't look at CD/DVD, but 500GB of disk is about 60 dual layer DVDs (neglecting compression). Better just to keep multiple copies online.
• Log-structured file systems will make more and more sense for general use (and were already prevalent in high-performance database systems in 1999). This dovetails with the "change by adding" viewpoint of wikis, version control systems and such.

These effects are more visible behind the scenes than on the web at large. When we factor in CPU and network performance, the results are more directly visible. I'll get to that ...

Jim Gray and real computing

I used to have a bookmark of Jim Gray's piece "Rules of Thumb in Data Engineering". I have no idea which old profile the bookmark is hidden under, but googling "'sequential access' 'disk' 'rules of thumb'" brought it up as the first hit. Another win for Google over bookmarks (though I was a bit lucky to remember the phrase "rules of thumb").

The piece examines the changing ratios among CPU, disk capacity, network speed and other basic parameters and reaches some interesting conclusions about databases and caching. It also makes the larger point is that with Moore's law and its cousins in effect, the basic assumptions behind our engineering trade-offs change faster than we think. The article itself was written in 1999. The trends it outlines look to be holding up well and the main point even more so.

As you may know, Jim Gray was lost at sea last January. Gray's body of work is classic engineering -- developing a firm, objective grasp of the basic facts in order to put all this wonderful machinery to good use. Even a quick look at his home page shows what a loss this is for our profession, to say nothing of those close to him.