15418 Project: Transactional Memory Analysis

Harry Shao (yizhous)

Yuxiang Zhu (yuxiangz)

SUMMARY

We are going to implement a software transactional memory library with multiple levels of strictness. We will then write programs that perform common workflows using this library, and examine the relationship between performance (time spent, or percentage of failed commits) and the strictness of the library for each workflow.

BACKGROUND

We talked about transactional memory in class, and it appears to be a very unique solution for synchronizing parallel tasks. Compared to traditional methods, transactions are less error-prone than locks, and they make handling complex data structures easier than using primitive atomic operations. However, transactional memory is not as commonly used as these traditional methods, so we decided to implement one with the hope of understanding how it might work under the hood, and also to test out how common workflows (such as manipulating linked-lists, trees, etc.) would be implemented with TM, and how well they will perform.

CHALLENGE

The main challenge of the project lies in implementing the library. We first need to come up with multiple ways to implement transactional memory in software. The different levels of strictness may require very different implementations. Then we need to make sure the library is functionally correct, which may not be easy since its methods will be called by multithreaded programs (and the implementation itself still needs to use traditional methods of synchronization). Finally, but equally important, is the design of the library. What levels of strictness should we have (i.e. what are the behavior of each of them), and how should we set up the public methods and variables so that programs using it are easy to write.

RESOURCES

We will not be needing any special hardware for this project as it will be a generic library that can be run on any machine. Especially for the first part of the project where we implement the library, we will likely be using our own machines. We will be starting from scratch writing the library. The design of the interface will likely follow convention, so we may look up what existing transaction-based systems (not neccesarily transactional memory) look like.

GOALS AND DELIVERABLES

Plans to achieve:

Hope to achieve:

Demo:

The demo will be a presentation of the interface of the library, along with a brief intro of how it's implemented. We will also be showing charts of runtime statistics and our analysis on the performance and failure rate tradeoffs.

What to learn:

In the end, we hope to build a library that is functionally correct, and thus usable in actual real-world programs.

PLATFORM CHOICE

We plan on using C++ for this project because of its flexibility and performance. C++ has a very flexible syntax and allows user-defined types to overload operators. This makes it easy for us to define our own wrapper types for primitive types, and "intersect" its memory accesses to add in our own logic. It also helps that the language is relatively low level, which means we have "raw" access to memory locations and that it will be fast to run (important since we'll be introducing overhead to many simple memory accesses).

SCHEDULE