Bob Metcalfe rides off into the sunset

I joined my first computer crusade as a systems programming student at the Massachusetts Institute of Technology in 1965. There have been many crusades since then.

In this final episode from the Ether, I'll return to a crusade for which we are now only stacking our lances: Anticiparallelism.

In the 1960s, punched-card batch-processing mainframes were defended by IBM and the BUNCH (Burroughs, Univac, NCR, Control Data, and Honeywell). I joined the encircling crusaders: Digital Equipment, Data General, and Scientific Data Systems. Our siege machines were interactive time-shared minicomputers.

In the 1970s, with teletypes on the rise, I defected to the personal computing crusades at Xerox, later Apple and Sun, and eventually IBM, Intel, and Microsoft.

In the 1980s, I led the Ethernet crusade. 3Com and Novell took up LANs against stand-alone PCs and their defenders - including Microsoft - for whom sneakernet and RS-232C were then quite enough.

And then in 1986 or so, Senator Al Gore "took the initiative in creating the Internet", our current crusade - led since by Vint Cerf, Sun, and Cisco.

Internet crusade Actually, the Internet has been its own series of crusades since 1969: remote login, file transfer, e-mail, news groups, client/server, instant messaging, Web publishing, push, Web commerce, streaming media, mobile, peer-to-peer, and soon broadcasting Web entertainment.

Among my favourite current crusades is the all-optical Internet; with fibres extending to the curb, to the home, and not soon enough, to the wall. Fibre crusaders are thwarted for now by the powerful copper monopolies.

Another favourite is the Pay-As-We-Go Internet. Too many still think they'll get for free, or for some low flat fee, all they desire in Internet access, transport, services, and content.

And then there's the crusade for a secure Internet. Today's Internet is anonymous to the bone. But anonymity must be the exception. And as soon as we dethrone the encryption-controlling Clinton-Gores, communications on the Internet should be strongly encrypted all the time.

Not to tilt at windmills, there's also Anticiparallelism, a crusade of mine you probably don't recall from 1998. But I've just met someone actually working on Anticiparallelism - at Microsoft, no less.

Anticiparallelism is, in short, using idle resources to preprocess anticipated computing tasks in parallel with current tasks. It's doing this automatically, using pervasive, fine-grained, decision analysis in new applications, user interfaces, programming languages, OSes, and hardware.

Here are some nitty-gritty examples of problems that Anticiparallelism might solve.

Start: What is your computer doing those first minutes after you start it up? It has been idle for hours. It will be idle for much of the time thereafter. So why doesn't it handle its duties before or after starting up?

Next: Why does linking to Web pages, especially the obvious next page, take your computer so completely by surprise?

Back: When you hit your browser's back button, why doesn't your computer have your previous page cached?

Reply: Why must your computer format and send your reply to the current message before fetching and rendering your next in-box message? Why aren't sending your last reply and fetching your next message done in parallel with displaying your current message?

Disk: Why do we waste so much time waiting for disks to be backed up and defragmented? With a little Antici-parallelism, both could be done in the background as soon as a file is updated.

These are several of the most obvious problems that could be solved with Anticiparallelism, but generally aren't. Today's computers squander parallelism. Their software sequentialises computations, failing to anticipate tasks that might be accelerated with precomputed partial results put in inventory - cached - using idle resources.

When I first wrote about Anticiparallelism, readers had issues.

One was that allowing a defragger to run in the background slows response. Another was that background tasks too often crash PCs. True, Antici-parallelism requires fine-grained pre-emption and five nines (not nine fives) of reliability.

Others complained that prefetching Web pages is immoral - tragedy of the Commons and all that. It's clever to invest our own idle resources on potentially moot precomputations, but it's antisocial to do so with freely shared community resources. Amen.

When I risked talking about Anticiparallelism recently before the Defense Advance Research Projects Agency, a funny thing happened. A member of the prestigious Information Science and Technology (ISAT) Study Group came forward to say that he is already working on it.

Eric Horvitz calls it Continual Computation. He leads a group at Microsoft Research and was excited that someone shares his passion.

What do Horvitz and I have in common that would lead us to this crusade? Decision theory. We both rejoice in techniques for making better decisions under uncertainty.

Horvitz and I know, for example, that after you choose one of three doors behind which are hidden two goats and a car, and after Monty Hall shows you a goat behind one of the two unchosen doors, the strategy that doubles your chances of winning the car is to switch from taking what's behind the door you first chose to taking what's behind the unopened door.

Horvitz proves theorems about precomputation policies that maximise the "flux" of computation. He deals with uncertainties about which computing "challenges" will arise. He considers when it's right to employ idle but also shared resources to advance one's own Continual Computing.

Sequential structures

We talked about control structures in programming languages and operating systems that might enable Continual Anticiparallelism. The normal sequential structures such as "Do this, then this, then this, then end" allow for very little parallelism.

Programmers can pursue parallelism by hand. Horvitz points to Microsoft Outlook, which does some precomputing already. Another example is SQL Server 2000, which uses an analysis of database workload to precompute partial answers to queries.

But Horvitz and I, as do most crusaders, have high ideals.

Case dispatches such as "Do this, or do this, or do this, depending on what the user types" are seldom used to guide parallel precomputation among the cases while users make up their minds. But they could be.

As a first step, programmer-assigned priorities could guide the contingent precomputation. Variations on an "agenda" control structure could let programmers say, "When you get a chance, do this and this and this, in parallel with these priorities."

But Horvitz and I are crusading for even more continually anticiparallelistic computing systems, which will pursue optimisation opportunities automatically. We are crusading for self-aware computing that monitors how often this follows that, that zeroes in on precomputations with high values and probabilities, that prioritises them using optimisations from decision theory, and that makes the most of Continual Anticiparallelism. For more on Horvitz's crusade, see www.re-search.microsoft.com/users/horvitz.

And until we meet again, stay enthusiastic.

* Bob promises we have not heard the last of him. Farewells to metcalfe@info-world.com

Join the newsletter!

Error: Please check your email address.

More about 3Com AustraliaData GeneralHoneywellIBM AustraliaIntelMassachusetts Institute of TechnologyMetcalfeMicrosoftNCR AustraliaNovellXerox

Show Comments

Market Place