TECHNOLOGY FOR CHANGE

Close Is Good Enough in Horseshoes, Hand Grenades and Now Some Computations

Salvatore Salamone | Date: 05-20-10 | Comments

MIT researchers 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 computational speed.

Thanks to MIT researchers, the old saying �Close is only good enough in horseshoes and hand grenades� can be amended to include the running of some computer algorithms.

Researchers in the MIT 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. The group presented its work at the recent International Conference on Software Engineering in South Africa.

The researchers describe their technique as �loop perforation� because it punches holes in the iterative loops executed within a computer program. Essentially, the technique identifies sections of code where every other step (or two) in a loop can be skipped with minimal impact on the outcome.

One simple application of the technique cited by the researchers has to do with speeding programs that calculate averages. The common process is to use a loop in a program where, in each subsequent execution of the code, the value of the next sample is added to a sum and then the total is divided by the number of performed loops.

With the loop perforation technique, every other step (or perhaps every two steps) would be skipped. This speeds up the computational work and in many cases yields similar results. For example, suppose you have a random sample of the heights of 1,000 U.S. men, and you want to calculate their average height. If you use 500 samples to calculate the average, rather than the full 1,000, you would get roughly the same result in half the time. (Note: This works because the measurements, if they are random, follow a normal probability distribution.)

The technique has applications in several areas. For example, the researchers tried the technique on encoding video data for transmission over the Internet. They were able to significantly reduce the time needed to encode and transmit the video stream, with no noticeable effect on video quality (click on image below to see video).

Using the MIT loop perforation technique, the time needed to encode video data for transmission over the Internet was cut in half with no noticeable effect on the video quality. Here, the top video uses normal coding, while the bottom use loop perforation. (Source: MIT Computer Science and Artificial Intelligence Laboratory)

Other areas where this technique could provide benefits include systems that process data in real time, such as stock traders� analytic software, and in many pattern recognition applications.

The current research focuses on identifying parts of an algorithm that can benefit from the technique. This involves searching through a program and perforating each loop while gauging the effect on performance. Once this is done, a determination is made as to which loops� perforation provides the greatest increases in speed with the smallest drop in quality.

However, the system could be used to automatically implement the actions on the fly. For instance, according to Physorg.com, video-chat software running on a laptop could use the standard method of encoding data when the laptop�s processor is relatively idle. But when the processor gets overburdened trying to handle several applications at once, the video-chat software could switch to the less computationally intensive version of the encoder.