System Bits: April 1

“Lock-free” vs. “wait-free” parallel algorithms
Since computer chips have stopped getting faster, regular performance improvements are now the result of chipmakers’ adding more cores to their chips, rather than increasing their clock speed. And in theory, doubling the number of cores doubles the chip’s efficiency, but splitting up computations so that they run efficiently in parallel isn’t easy. However, it isn’t as hard as has been feared, according to computer scientists from MIT, Israel’s Technion, and Microsoft Research.

“Lock-free” parallel algorithms are frequently used when writing programs for multicore chips, which are relatively easy to generate from standard sequential code – much of which can be done automatically. But lock-free algorithms don’t come with very satisfying theoretical guarantees, the researchers said. All they promise is that at least one core will make progress on its computational task in a fixed span of time. But if they don’t exceed that standard, they squander all the additional computational power that multiple cores provide.

In recent years, theoretical computer scientists have demonstrated ingenious alternatives called “wait-free” algorithms, which guarantee that all cores will make progress in a fixed span of time. Deriving them from sequential code is extremely complicated, and commercial developers have largely neglected them but the researchers have demonstrated a new analytic technique suggesting that, in a wide range of real-world cases, lock-free algorithms actually give wait-free performance.

In practice, programmers program as if everything is wait-free, which is a mystery, the researchers noted. In a recent paper, they expose a little-talked-about intuition that programmers have about how chip schedulers work, that they are actually benevolent.

Reliable, efficient cooling
Equipment and electricity for cooling are a major expense at big computer installations, and Timothy Shedd, an associate professor of mechanical engineering at the University of Wisconsin-Madison, uses a dark, windy room on the top floor of the Engineering Hall to show a system he has invented that can do the job more efficiently.

In Shedd’s system, a pair of translucent plastic tubes enter each computer case. Upon close inspection, a stream of tiny bubbles in the fluid can be seen exiting the case. Those bubbles — a gas phase of the liquid refrigerant that entered the computer — are removing heat from a single computer. For several reasons, the system is, roughly speaking, 10 times more efficient than the air-conditioning that dominates the server field, he asserts.

Timothy Shedd examines a computer equipped with his novel cooling system. Tubes circulate refrigerating fluid through a special heat exchanger (under the X-shaped structure) on the processor that is the biggest heat source in a computer. (Photo source: David Tenenbaum/UW-Madison)

Shedd has spent more than a decade studying and designing computer cooling systems, and he has started a spinoff business called Ebullient to commercialize his invention, which is covered by patents he’s assigned to the Wisconsin Alumni Research Foundation.

The technology has two key components: First, a plastic chamber attached to the processor absorbs heat at the point of creation. Second, a network of tubes and a pump carry the heat to the roof, where it is “dumped” to the atmosphere. Although the system uses air conditioning refrigerant, it omits the compressor, condenser and evaporator — three major parts of the air conditioning used to cool server farms.

A few innovative computer-cooling systems use water to remove heat, and while water does transfer an immense amount of heat, it makes operators nervous. Instead, this system uses a refrigerant that would not damage the computer if it spills.

As server farms become even more numerous, their cooling requirements will only grow. Shedd estimates that his system can cut cooling costs by up to 90 percent, but first he’s got to prove that it’s safe and reliable. As such, this system has a built-in redundancy — instead of one loop of coolant into each server, there are two, and there are duplicate pumps as well.