Why the Continued Success of High-Tech Rests upon a Different Way of Coding

Story by Al Riske. Photography by Howard Friedenberg.

March 6, 2009 - Maurice Herlihy and Nir Shavit understand the fear that keeps people in the high-tech industry awake at night -- the fear that computers will become like washing machines.

“When you buy a washing machine you keep it until it breaks,” Herlihy says. “You don't trade it in every two years for a better model because next year's washing machine isn't going to be significantly better than this year's model.”

So, are these two Sun researchers -- part-time members of the Scalable Synchronization Research Group in Sun Labs -- saying that Moore's Law has run its course? Are they saying that computers will no longer become twice as fast every year or every year and a half?

Not exactly.

But there has been a seismic shift in how microprocessors are designed and built. Sun led the way with its multicore, multithread “Niagara” processors and now every major chip maker has followed suit.

This new kind of processor -- known for juggling numerous software threads, or tasks, at the same time -- is highly efficient, but will require a new style of programming if it is to reach its full potential.

“One thing that everyone in the industry is worried about is that, if we don't know how to program for multiple cores, then we're not going to be able to deliver increased value every year the way we have in the past,” Herlihy says.

Long-time friend and colleague Nir Shavit notes that the model wherein old software simply runs faster on new machines isn't going to hold up much longer.

“If you're adding more parallelism to the machine, the same code will not run faster; somebody will have to rewrite it,” he says. “The somebody who will have to rewrite it is everybody.”

Which is why Herlihy and Shavit wrote The Art of Multiprocessor Programming and have been teaching courses on the subject at Brown University and Tel-Aviv University, respectively.

They also came to Sun headquarters in Menlo Park, California, recently to teach a five-day version of the course to Sun software engineers.

“There are people who know how to do it,” Shavit says. “Databases and scientific computing are two niche markets, where people have been programming multiprocessors for a long time, but this is not general programming. There are billions of lines of code out there. How many of them have to do with high-end databases or scientific computing? Essentially just governments and very big organizations. The rest have nothing to do with parallel computing, which is why people never really took the time to figure out how to teach an undergraduate course on parallel computing.”

But multicore processors have quickly become commonplace, even on desktop and laptop computers, and soon mobile phones and other handheld devices will come with eight cores, or processing units, say Herlihy and Shavit.

Which means programmers will need to learn new tricks. No doubt about it.

Parallel programming, the authors say, is a bit like coordinating the efforts of painters in your house. Smaller rooms will be finished faster, so instead of having those painters wait idly for the others to finish, you want them to help with the larger rooms -- without tripping over each other and spilling paint on the floor.

“This exact type of coordination is what makes concurrent programming hard. How do you coordinate all the idle computing threads so that they make use of all the available processors?” Shavit says.

“The answer lies in the design of efficient concurrent data structures and coordination protocols, the tools used by programmers to allow threads to communicate effectively.”

Herlihy calls these data structures the ball bearings of a parallel computing machine because, without them, the different parts would grind together.

“Some kinds of applications are easily parallelized because everybody is doing something completely different, like graphics where you can draw this one and that one and you don't really need to coordinate. But often you end up with something where one activity is handing data to another activity, and data structures are used as a way of communicating between different activities. So one will put something into a table or an array and another will come and take it out,” he says. “The data structures are where the activities need to synchronize. This is the hard part. If you do it badly things are very inefficient.”

Shavit adds that he and Herlihy show programmers various tricks they can use in different situations.

“In typical programs people write now, 90 percent of the code is easy to parallelize. If you know the algorithm, it's easy to see how to break it up and put it on different processors. But there are 10 percent that are hard to parallelize. Those 10 percent have to do with the passing of information between the threads by way of shared data structures,” he says.

“If you don't parallelize that part, if you don't open that bottleneck, if you do everything there sequentially, then all of your performance sucks. That's the issue. Understanding how to open those bottlenecks in the data structure is crucial.”

Which is where the somewhat unscientific-sounding term intuition comes into play.

“Intuition is really crucial in this context because a lot of the things are counter-intuitive. When you program sequentially, it's easy to understand what the sequence of things is,” Shavit says. “But if, while you're doing one thing, another person is doing something else, and the things he does can interleave with what you're doing at different places and you have no idea when they will happen ... this kind of thinking is just counter-intuitive. That's what we have to overcome to give people a feel for how they can begin to think about these things.”

So they start with simple examples.

“Sequential computing has this theoretical foundation that goes way back to this guy called Alan Turing, who formulated the notion of a Turing machine. Anything that is computable sequentially is computable on this Turing machine, and it is the model of computation. So what we do in the beginning is we show students what the model of computation is for these new machines. It's not Turing computability. It's what we call shared-memory computability. Having understood this fundamental model, then they go on and tackle the actual problems,” Shavit says.

“Many computing courses go from concrete to abstract,” Herlihy says. “We do this the other way around. We start out with a simple, idealized, abstract model and then we introduce more and more concrete things. It's hard enough in the idealized model to reason about concurrent activities, so we do this in a simplified way. Then when we go over and show them a more complicated, realistic situation, we say, 'See, this is the same as what you saw before, but it's lurking in disguise and it's more complicated and awful.' We think that going from theoretical models to practical works better in this context.”