A Radical Rethinking of Transactional Memory

By Al Riske

18.Dec.07 - When he was still a doctoral student, Mark Moir took a highly contrarian stance.

"The way I got into what I'm doing now is I saw some of the early ideas and I said, 'It all sounds very nice but there's no way it's ever going to work, and I'm going to be the one to prove it's impossible,'" he recalls.

What he's doing now is making the impossible possible -- developing ways to build systems that are fast, scalable, concurrent, and correct.

All that thanks to a radical rethinking of transactional memory.

Simply put, the aim of transactional memory is to ensure that the right operations take place at the right time, without interference or disruption. Easier said than done. Especially if you want to go fast.

As luck would have it, the things Moir thought were impossible -- the things he and his team in Sun Labs have been working on for the past several years -- are becoming practical just in time to take advantage of the multicore revolution in microprocessors.

In fact, Sun's upcoming "Rock" processor will be the first mainstream processor to hardwire support for transactional memory into its design for increased speed.

The thing to know about Mark Moir is that he hates false dichotomies.

"There are just so many in our industry," he says. "People say, 'You can't use this technique to get that property. It's impossible.' No, it isn't. Just because the first two ideas you tried out didn't work doesn't mean it's impossible. I know how hard it is to prove something is impossible, so when someone says, 'That's impossible,' I say, 'Where's your proof? You don't have one, do you? Uh-huh.'"

It's a lesson he learned from experience, obviously. While he was never lazy about pursuing proofs, the hard work he put in sparked some essential insights.

"When you set out to prove that something is impossible, you've got to somehow abstract all the possible solutions and prove that none of those could work, so it's a very hard problem," Moir says. "Time after time I'd be working on a proof to show you can't solve such and such a problem in such a model, and I'd have it all covered -- doesn't work this way, doesn't work that way -- and I'd be down to this last hard case, banging my head against the wall for a few weeks, and then I'd wake up one morning and realize, 'Oh, I can't prove that this is impossible because ... it's possible.'"

Soon a pattern emerged:

"After this happened a few times, I said 'Okay, forget proving it's impossible. Let me get on the bandwagon and make it possible.'"

So Moir's initial stance was wrong, he's pleased to say, but that didn't stop him and his team from taking a very contrarian approach to the solution.

"If you have some data you want to be shared concurrently by multiple processors or cores, then you've got to synchronize them somehow. If everyone just comes and messes with the data then there's chaos and nothing makes any sense," Moir explains. "The traditional way to synchronize is to use locks to basically say, 'Look, you stay out of here; I'll do my stuff and let you know when I'm done.' But if all of us are doing this, we all have to get in line and that's not a good thing."

He notes Sun's next-generation processor, code-named Rock, is going to support a form of hardware transactional memory -- a hybrid form -- that is essentially non-blocking.

"We had learned this pattern: Don't try to set the bar really high so you can't find a workable solution. Figure out what's an easier thing to do and go incrementally from there," he says. "That insight is a big part of the reason Sun is ahead of the competition in terms of implementing transactional memory."

Many other researchers have tried to have the hardware solve the whole problem, because existing software solutions are painfully slow.

"That's really hard," Moir says. "People would come up with really complicated solutions -- things that are much too risky to put in a product you're betting your company on -- and at the end of their paper they'd say something like, 'We leave certain unresolved system-level issues for future work.' Translation: 'Even with our really complicated solution we haven't figured this out.'"

Which is where Moir's hybrid solution comes into play.

"We came up with the idea of best-effort transactional memory. In other words, the hardware does the best it can and, in software, we hide its limitations," he says.

"Programmers don't have to know that the hardware only solves these cases and not those, but the hardware designers get that much more flexibility because whenever they get into a really tricky situation they can say, 'Okay, I'm just going to abort in this case and the software will take care of it.' That way, the more the hardware can do, the more we can take advantage of it, but it's not all or nothing."

Translation: They turned a very difficult problem into a much easier one.

By using super fast hardware to solve the most common cases and leaving the exceptional cases to slower software programs, the team has been able to produce startling practical results.

Best effort is where we've taken quite a different tack from everyone else," Moir says, "and I think it's going to serve us very well."

The team has developed a simulator that behaves like Rock, so they've been trying out their ideas.

"We came up with about six things of the tops of our heads, and in a three-week period we got five of those things working to some degree of success," Moir says.

One especially encouraging result: Using (simulated) hardware transactional memory behind the scenes made existing Java code faster and more scalable. This despite the fact that the original programmer had never even heard of transactional memory.

What researchers found was that even if the programmer had written in a lock -- the old, "Look, you stay out of here; I'll do my stuff and let you know when I'm done" -- the hardware transactional memory could try to complete tasks in parallel and only resort to a lock if there was an actual conflict.

"With certain kinds of data structures, the lock is really more conservative than it needs to be. It's just that once in a while we might conflict so we'd better understand that and make sure that things happen correctly that once in a while. With hardware transactional memory, every time we don't conflict we'll go in parallel, and the once in a while that we do, then we'll serialize," Moir explains.

"My belief is that the real power of transactional memory will come when people start actually programming explicitly with this programming model in mind. But even if we had completely settled on programming models and had developed robust support for them, which we haven't, it would still take time for people to adopt it. So I'm excited that people can get real benefits from transactional memory even without changing their code."

Impossible? Hardly.