麻豆淫院

"It used to be that people used computers for computations where there was a single, hard, logical right answer," says Martin Rinard, a professor of computer science at MIT. "Now, the landscape is changing." When you do a Google search, for instance, the exact order of the first few results may not matter as much as getting an answer quickly. In the Internet age, when Web servers are performing computations for thousands of users at once, and sending the results across thousands of miles of optical fiber, programs that can efficiently find adequate solutions to a problem are often preferable to ones that inefficiently find the perfect solution.

Researchers in Rinard鈥檚 group at the Computer Science and Artificial Intelligence Laboratory have developed a system that automatically looks through computer code for areas where a little bit of accuracy can be traded for significant increases in speed. In one set of tests, the system halved the time that it takes to encode video data for transmission over the Internet, with no noticeable effect on the video quality (see the related video). But the same approach could have advantages for any system that needs to process data in real time, such as stock traders鈥� analytic software, or location-tracking or environmental-monitoring systems that use networks of sensors. It could also pay dividends for systems that need to look for patterns in huge masses of data, such as the recommendation engines at sites like Netflix or Amazon.

The researchers unveiled their system last week, at the International Conference on Software Engineering in South Africa. In a paper they presented there, they concentrated on a version of the system that alerts programmers to sections of their code where accuracy could be traded for speed. But the system could just as readily make that tradeoff automatically, on the fly. For instance, video-chat software running on a laptop could use the standard method of encoding data when the laptop鈥檚 processor was otherwise idle. But if the processor got overburdened trying to handle several applications at once, the video-chat software could switch to the less computationally intensive version of the encoder.

Perforating videos. The top video was created using an algorithm commonly found in videoconferencing software. A new MIT system automatically modified the algorithm so that it took only half as long to produce the bottom video, with little loss of quality.

Cutting corners

The researchers鈥� system exploits a remarkably simple trick. A large computer program will usually feature numerous instances of what鈥檚 called a loop 鈥� a process that鈥檚 repeated over and over again. Suppose that you were writing a program that needed to find the average of a long list of numbers. To begin with, the program would simply step through the list, adding each number to a running total: That鈥檚 the loop. Then it would divide the total by the length of the list.

The CSAIL researchers who developed the new system 鈥� Rinard, research scientist Stelios Sidiroglou-Douskos and graduate students Hank Hoffmann and Sasa Misailovic 鈥� call their new technique 鈥渓oop perforation鈥� because it punches holes in loops: It simply skips every other step in the loop, or every two steps, or whatever it can get away with skipping without sacrificing too much accuracy. In the case of the program for averaging numbers, it might skip the first number on the list but add the second to the running total; skip the third but add the fourth; and so on. Since it鈥檚 adding up only half as many numbers, it takes only half as much time. But if the numbers follow a fairly normal probabilistic distribution, the answer will be close to what it would have been, anyway: The average height of 1,000 randomly selected Americans is probably not that far from the average height of 500 of them.

The researchers鈥� system is itself a loop: it searches through a program, perforating each loop in turn, executing the program and using standard measures to gauge the effect on performance. It then determines which loops鈥� perforation provides the greatest increases in speed with the smallest drop in quality.

Loopy insight

Loop perforation is so simple, and its effects so dramatic, that it may seem odd that it isn鈥檛 already in wide use. But for computer scientists, it鈥檚 very counterintuitive. 鈥淭here鈥檚 a visceral sort of reaction against it,鈥� says Hoffmann, 鈥渂ecause people spend a lot of time thinking, 鈥楾his is the best way to do this.鈥� And what we鈥檙e saying is that you can throw out half of what you thought was the best way to do that, and it still produces a reasonable answer.鈥� Hoffmann recalls, for instance, that one of the applications on which the researchers tested their system was a machine-learning application, which learned to perform a classification task by looking for patterns in sample data. 鈥淪asa knew a lot more than we did about what that app was doing,鈥� Hoffmann says. When the system suggested the perforation of one particular loop, 鈥淪asa was like, 鈥楾his is wrong. You can鈥檛 do that.鈥� But the application seemed to work perfectly well with the perforated loop. 鈥淚t seems like the closer you are to the application, the more reluctant you are to accept these things,鈥� Hoffman says.

鈥淚 like the simplicity of the technique and also the generality of it,鈥� says Cristian Cadar, a lecturer in the Department of Computing at Imperial College London. 鈥淵ou can apply it to a wide variety of programs.鈥� But, Cadar adds, 鈥渢he main impediment to adoption of this technique, at least in the automatic form, is that developers are reluctant to adopt a technique where they don鈥檛 exactly understand what it does to the program.鈥�

To allay developers鈥� fears, Rinard and his group are working to explain the technique鈥檚 success with greater mathematical rigor. And since loop perforation is such uncharted territory, Rinard suggests, its theoretical exploration could have totally unforeseen consequences. 鈥淵ou never know what鈥檚 going to happen when you understand something,鈥� he says. 鈥淭he great aspect of science is these unpredictable, unanticipated breakthroughs that come just because you鈥檙e curious.鈥�