Transactional Memory

It's a solution to a large and growing problem for developers. It's a key to exploiting advances in multiprocessing technology. And it's an area of intense focus-and breakthrough innovation-at Sun Labs.

August 13, 2007 -Transactional memory is not a technology or a term most mainstream developers are familiar with today. That is likely to change-and soon.

Transactional memory appears to be the key to unlocking the full potential of next-generation chip multiprocessing (CMP) technologies and accelerating both their performance and their adoption. It could also be a core enabling technology for the massively powerful terascale and petascale computing systems now on the drawing boards of advanced research labs and government agencies. Why? Because transactional memory can solve a very serious problem in software engineering-a problem that is severely constraining application performance and draining countless productive hours from skilled programmers.

Programming in the Age of Concurrency

The problem, in a word, is concurrency. In the emerging world of multi-processor systems, multi-core chips, multi-threaded applications, and massive parallelism, it becomes more and more difficult to synchronize concurrent access to shared memory by multiple threads. This makes it more difficult to ensure that the right operations are taking place at the right time, without interference or disruption, at high performance. For many organizations, the net result is that applications written for multi- processing workloads are currently achieving only 5-10% of the theoretical peak performance of the system.

And right now, much of the burden for delivering higher application performance on multi-processor, multi-threaded systems is falling on programmers, not processor manufacturers. Chip makers have been facing diminishing returns as they try to make processors run faster. While Moore's Law continues to deliver its promised increase in transistor density per chip, clock speed cannot be increased past certain limits without overheating the processor. That has fueled the rapid transition to the CMP era, where multiple cores are running on each processor. As a result, software engineers can no longer count on ever-faster hardware to hide software bloat.

The problem is only going to get worse for developers. Beyond the dual- or quad-core processor systems already on the market today, manufacturers are building many-core chips; for example the UltraSPARC T2 processor (code-named Niagara 2) has 8 cores and can support 64 threads.

While customers can achieve higher throughput while consuming less power and producing less heat by consolidating multiple applications onto a multi-core server, programmers who want to exploit advances in multi-core technology to improve the performance of individual applications will need to master multi-core programming. This takes a lot of time and effort today. There are a number of software engineering issues that make life more difficult than it should be, and solving these problems requires experienced experts whose talents could be better used in other ways than dealing with low-level concurrency issues. What's needed is an efficient, reliable concurrency control mechanism, implemented in a practical way that's easy to use. And as it turns out, delivering such a mechanism is no small task.

Researchers at Sun Labs have been working on the concurrency problem for many years, with a growing focus on shared memory synchronization over the last decade. The team has introduced a number of breakthroughs in transactional memory that show considerable promise for programmers in today's Age of Concurrency.

The Sun Labs team includes some of the best-known and most highly regarded researchers in the transactional memory field. Maurice Herlihy (Visiting Professor) was one of the original inventors of Hardware Transactional Memory and also proposed a hardware implementation; Nir Shavit was one of the inventors of Software Transactional Memory; and Mark Moir invented Hybrid Transactional Memory. The team also includes seasoned engineers Dave Dice and Dan Nussbaum, and Victor Luchangco, an expert in languages and formal methods. In addition, a number of bright, creative and industrious interns have made significant contributions, including Alexandra Fedorova, Yossi Lev, Ori Shalev, Bill Scherer, Simon Doherty, and Virendra Marathe.

The Sun Labs team has also worked closely with Sun Microelectronics, whose engineers have more than 10 patents relating to transactional memory. As a result of the collaboration between Sun Labs and Sun Microelectronics, support for transactional memory is imminent for commercial Sun products—beginning with Sun's "Rock" processor. More about that in a moment. First a bit of perspective. The next sections elaborate on a few areas of recent focus for the team and provide context for Sun's plans to implement transactional memory support in forthcoming products.

Transactional Programming: Software-based, Hardware-based, or Hybrid
Transactional programming has emerged as a very promising alternative to lock-based synchronization techniques for concurrency control. With the lock-based model, still predominant today, programmers rely on a combination of locks and conditions, such as monitors, to prevent concurrent access by threads to the same shared data. But lock-based synchronization has well-known pitfalls. Coarse-grained locking is easy to program but does not scale well, while more sophisticated fine-grained locking is difficult to program and, if not used very carefully, can introduce data races or "deadlocks" (when locks become dependent on each other, such that each thread is holding a lock the other thread needs—or when a thread dies holding a lock that blocks other dependent thread).

Transactional programming can help developers avoid the pitfalls of locks, bringing proven concurrency-control concepts used for decades by the database community to mainstream parallel programming. Transactional programming models can be supported in software using software-based transactional memory (STM), in hardware using hardware- based transactional memory (HTM), or in a combination of the two (Hybrid TM, or HyTM).

STM: Transactional Programming without Hardware Dependency
STM can allow sequences of concurrent operations to be combined into atomic transactions (a transaction is a piece of code that executes a series of reads and writes to shared memory), thereby reducing the complexity of both programming and verification.

But STM has its own limitations and vulnerabilities as well. For example, a number of STMs allow user code in transactions to observe a state that could never have existed. Even though such "zombie" transactions will not commit successfully, they could do something unexpected in the meantime, including infinite loops, illegal memory access, and other runtime problems. In some contexts, particularly in managed runtime systems such as Java, it is possible to mask such bad behavior. But in others, such as general C and C++ code, arbitrary behavior is possible, so zombie transactions must be prevented. Sun Labs researchers are working on transactional memory implementations and transactional programming models for a variety of such contexts.

Another problem is that many previous STMs cause unexpected behavior if a transaction removes an object from a data structure and frees it, or accesses it directly without using transactions. There are tricky tradeoffs involving efficiency, scalability, and even software engineering in addressing issues like this "privatization problem" as well as zombie transactions. Sun Labs engineers are pioneering innovative techniques for addressing these problems. For example, the "TL2" algorithm introduces a novel global version clock mechanism that substantially reduces the cost of avoiding zombie transactions for small to medium numbers of threads. Other research groups are following suit to get similar performance improvements. But the TL2 mechanism can suffer scalability issues in larger systems, where different techniques are preferable.

In addition to devising innovative mechanisms for addressing different workload scenarios and systems, Sun Labs researchers are also working on ways to seamlessly adapt between them, with the goal of building single systems that are competitive with the best for each context.

(For details about the TL2 algorithm, download a copy of "Transactional Locking II," a white paper by Dave Dice, Ori Shalev, and Nir Shavit. Code is available from the group's web page: http://research.sun.com/scalable.)

DSTM2: A Flexible Framework for Implementing STM
One of the key goals of the Sun Labs team has been to make it easier for other researchers to use and add value to its own innovations. "We try to publish our ideas and release as much of our code as we can to the research community, as early as possible," said Dr. Moir. "We want to make it simpler for researchers to experiment, reproduce our results, compare findings, and share new results with colleagues."

To that end, the team last year released code for DSTM2, a Java-based software library that provides a flexible framework for implementing STM. DSTM2 significantly improves the programming interface of its predecessor DSTM, and since the code is provided in Java libraries any Java programmer can use it easily. Essentially, it allows researchers to plug in their STM implementations and directly compare them with others (the resulting system has the same interface so the same benchmarks can be used).

Hybrid Transactional Memory: Extending the Free Lunch
For developers who think the "free lunch" of ever-faster processors hiding software bloat has come to an end, Sun Labs offers new hope in the form of hybrid transactional memory, or HyTM.

While STM has made it possible to start developing, testing, and running transactional programs without slowing down to the sluggish speeds offered by simulators for hardware support, in recent years there has been increasing momentum behind the use of hardware support for transactional memory. A key advantage of an HTM system is that it requires no read or write barriers within the transacion code. The hardware manages data versions and tracks conflicts transparently as the software performs ordinary read and write accesses.

Yet Sun Labs researchers believe that proposed HTM systems also have significant drawbacks. For example, while "bounded" and "best-effort" HTM systems (such as the original one described by Herlihy and Moss) should be sufficient for all but a tiny fraction of transactions given a modest amount of on-chip resources, programmers would need to be aware of—and avoid—the architecture-specific limitations of HTM. This would largely eliminate the software engineering benefits that transactional memory offers. More recent proposals for "unbounded" HTM aim to overcome these disadvantages, but Sun Labs researchers came to the conclusion that the proposals were sufficiently complex and risky that they were unlikely to be adopted in mainstream commercial processor designs in the near future.

The Sun Labs team has introduced what it calls a Hybrid Transactional Memory (HyTM) approach. HyTM exploits HTM support if it is available to achieve higher performance for transactions that do not exceed the HTM's limitations, and transparently executes transactions that do in software. Thus HyTM can use best-effort HTM to boost performance but does not depend on HTM. Programmers can therefore develop and test transactional programs in existing systems today and enjoy the benefits of HTM support as it becomes available.

(For details about HyTM, download a copy of "Hybrid Transactional Memory," a white paper by Peter Damron, Alexandra Fedorova, Yossi Lev, Victor Luchangco, Mark Moir, and Daniel Nussbaum, Sun Microsystems Laboratories, available from the group's web page: http://research.sun.com/scalable .)

Support for Transactional Memory in Sun Products: Imminent

The innovations described above are still in the research domain, but the Sun Labs team is actively working with engineers from other groups within Sun to implement the core technologies and capabilities within Sun products, and the fruits of this collaboration are forthcoming.

Of particular importance, teamwork between Sun Labs and Sun Microelectronics has resulted in the first implementation of Hardware Transactional Memory for a general-purpose processor (Rock). The implementation will be a form of best-effort HTM, which is simpler than the alternative unbounded HTM. HyTM enables this simplicity by hiding the limitations of best-effort HTM from programmers.