Anticiparallelism

Microsoft Corp. researcher Eric Horvitz says he's trying to figure out "what a computer should worry about when its thumbs are twiddling." Computers spend a huge amount of time twiddling their digital digits, wasting computational resources, he says.

Computers shouldn't be surprised by requests, especially from regular users, says Horvitz. For example, a PC running a network application could, while temporarily idle, prefetch and cache content from the Internet that a user may need later. Horvitz calls this "continual computing," in which computers stay busy by anticipating users' wishes.

Ethernet inventor Bob Metcalfe estimates that more than 99% of the world's computer capacity is wasted. He points out that modern microprocessors, such as Intel Corp.'s Itanium, engage in speculative execution - in which some values are computed or retrieved before they are needed - while doing other work. He says that principle should be moved to higher levels, to the operating system and to application software.

"What's done at the hardware level is really minuscule compared to what could be done," says Metcalfe, a partner at Polaris Venture Partners in Waltham, Mass. "This is a very old, deep idea that needs to be pursued much further than it has." He calls the idea "anticiparallelism."

Metcalfe argues for new control structures in languages that make it easier for programmers to enable anticiparallelism. "We need constructs that would let you say, 'Here's a bunch of things that need doing, and here's an expression of their priority,' " he says.

Some elements of continual computing are embodied in IBM's Autonomic Computing initiative, which aims to make systems self-managing. IBM is developing software that can reconfigure itself while constantly striving to optimize its own performance. "It will monitor its constituent parts and fine-tune workflow to achieve predetermined system goals," according to IBM.

In Horvitz's model, continual computation requires the computer to examine possible actions and execute those with the highest "expected value." Expected value is calculated by multiplying the probability that the user will want to take a path by the value of having it done in advance. The greater the delay avoided, the greater the value.

Many applications could take advantage of continual computation, Horvitz says. "Imagine if [Microsoft] Outlook maintained a set of probabilities based on you as the user - what you tend to do with e-mail messages, how you tend to view them, how you go back to them," he explains. Delays would be minimized because Outlook would perform many tasks before being asked, Horvitz claims.

"And Microsoft Project could sense when you are going to call for an optimization or when you are going to recalculate things in Excel," Horvitz says. "It might be doing this quietly in the background when it had idle time."

A server-based application could build a statistical model of client activity in order to assess the probability that any given piece of information would be requested by a user.

"Instead of waiting for a pull from the client, the system watches for any available bandwidth and then pushes down bits of data," Horvitz says. "The client always looks in local cache first, and it tends to find things that are miraculously there."

Might users complain when the system anticipates incorrectly? No problem, Metcalfe says. "The basic idea with contingent computations is that if [they were] wrong, they would not be noticed, just thrown away," he says.

Unwanted Assistance

But Horvitz can imagine software that's more in-your-face with anticiparallelism. For example, it might offer assistance, change a display or bring up a new application it thinks you need. That could lead to "frustration with a 'smart' system that just may not be smart enough," he says. Microsoft is studying that problem and is developing ways for systems to assess their own fallibility on the fly and seek reactions and guidance from users, Horvitz says.

Horvitz would also like to see operating systems engage in continual computing. An operating system running on a server would have to predict client behavior as well as machine and network resource availability. Microsoft calls its work in this area the Crystal Ball project.

Horvitz says his methods amount to load-balancing, and if all network-based applications did it, demand spikes that sometimes slow Internet servers and routers could be greatly diminished. But, he warns, "if someday everybody does continual computation, those who do it more poorly than others will have slower systems, more latency."

Asked if all Microsoft products will someday continually compute, Horvitz will only say, "You can be sure that applications that use very intensive resources in a networked setting will be using proactive caching techniques, and continual computation is probably the best way to do that."

5 power user tips for Microsoft OneNote
  
Shop Tech Products at Amazon