News Column

Patent Issued for Compiler Support for Optimizing Decomposed Software Transactional Memory Operations

August 21, 2014

By a News Reporter-Staff News Editor at Computer Weekly News -- A patent by the inventors Tarditi, Jr., David Read (Kirkland, WA); Harris, Timothy Lawrence (Cambridge, GB); Plesko, Mark Ronald (Kirkland, WA); Shinnar, Avraham E. (New Rochelle, NY), filed on March 23, 2006, was published online on August 5, 2014, according to news reporting originating from Alexandria, Virginia, by VerticalNews correspondents.

Patent number 8799882 is assigned to Microsoft Corporation (Redmond, WA).

The following quote was obtained by the news editors from the background information supplied by the inventors: "It is common for multiple threads of a multi-thread process to share common memory locations during concurrent execution. Consequently, two different threads of a multi-threaded process may read and update the same memory location accessible by the program. However, care must be taken to ensure that one thread does not modify a value of the shared memory location while the other thread is in the middle of a sequence of operations that depend on the value.

"For example, suppose that a program is accessing the contents of two different software objects, wherein each object represents an amount of money in a different bank account. Initially, the amount of the first account is $10, stored at memory address A1, while the amount of the second account is $200, stored at memory address A2. A first thread of a banking program is coded to transfer $100 from A2 to A1 and a second thread is coded to calculate the total amount of funds in both accounts. The first thread may start by adding $100 to the contents of A1, updating it to $110, and then proceed to subtract $100 from the contents of A2, updating it to $100. However, if the second thread executes between these two operations, then the second thread may compute an incorrect total of $310 for both accounts, rather than the correct total of $210.

"A software transactional memory ('STM') provides a programming abstraction through which a thread can safely perform a series of shared memory accesses, allowing the thread to complete its transaction without interference from another thread. Accordingly, transactional memories can be employed in software to ensure that the transaction including the exemplary addition and subtraction operations of the first thread is 'atomic' as to the memory locations A1 and A2, and therefore the second thread will compute the correct total amount in both accounts.

"However, existing approaches for implementing transactional memory in software suffer from performance problems. For example, in one existing approach, when a thread accesses a sequence of memory locations within a transaction, the thread maintains a separate list of the memory locations and values it wishes to read and update (i.e., write to) during the transaction and then, at the end of the transaction, the thread updates all of these values at the actual shared memory locations. If, during the transaction, the thread wants to re-read or re-write to any memory location in its list, the thread must search for the memory location's entry in the list to access the entry, which is a slow proposition programmatically. Accordingly, this indirect method of implementing a transactional memory in software suffers from poor performance.

"Additionally, existing approaches to implementing transactional memory in software introduce substantial overhead, including unnecessary calls to transactional memory and record-keeping instructions, causing execution of programs to suffer, especially if these instructions perform in an inefficient manner. Additionally, record-keeping activities inherent in some transactional memory schemes do not effectively limit the creation and maintenance of the records they create, which can waste memory, as well as disk space and other system resources."

In addition to the background information obtained for this patent, VerticalNews journalists also obtained the inventors' summary information for this patent: "A software transactional memory system is described. The system and techniques described herein utilize decomposed software transactional memory instructions as well as runtime optimizations to achieve efficient performance. A compiler is described which utilized knowledge of decomposed instruction semantics to perform optimizations which would be unavailable on traditional word-based software transactional memory systems. The compiler additionally performs high-level optimizations on STM code. Some of these optimizations are performed in order to take advantage of lower-level optimizations. These high-level optimizations include removal of unnecessary read-to-update upgrades, movement of STM operations around procedure calls, and removal of unnecessary operations on newly-allocated objects. Additionally, STM code is optimized to provide strong atomicity for memory accesses written outside of transactions. Multi-use header words for objects during runtime are extended to provide software transactional memory words which allow for per-object housekeeping, as well as fast snapshots which illustrate changes to objects. At runtime unnecessary growth of software transactional memory logs is avoided by filtering entries to the logs using an associative table during execution. Finally, at runtime, a garbage collector performs compaction of STM logs in addition to other garbage collection processes.

"In one example, a method of compiling a program which includes software transactional memory blocks is described. The method comprises optimizing the program to create an optimized program containing software transactional memory instructions and compiling the optimized program.

"In another example, a compiler system for compiling a program containing software transactional memory blocks is described. The system comprises an optimization module configured to optimize an intermediate representation for the source code, the intermediate representation comprising, at least in part, decomposed software transactional memory instructions. The representations of decomposed software transactional memory instructions are optimized at least in part according to software transactional memory optimization rules.

"In yet another example, computer-readable media are described which contain instructions which, when executed by a computer, cause the computer to perform a method for optimizing a program comprising software transactional memory instructions. The method comprises receiving an intermediate representation of the program which includes representations of the software transactional memory instructions and applying optimization rules specific to software transactional memory instructions in order to optimize the representations of the software transactional memory instructions.

"This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter.

"Additional features and advantages will be made apparent from the following detailed description of embodiments that proceeds with reference to the accompanying drawings."

URL and more information on this patent, see: Tarditi, Jr., David Read; Harris, Timothy Lawrence; Plesko, Mark Ronald; Shinnar, Avraham E.. Compiler Support for Optimizing Decomposed Software Transactional Memory Operations. U.S. Patent Number 8799882, filed March 23, 2006, and published online on August 5, 2014. Patent URL:

Keywords for this news article include: Software, Microsoft Corporation.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC

For more stories covering the world of technology, please see HispanicBusiness' Tech Channel

Source: Computer Weekly News

Story Tools Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters