Research On Nested Transactional Memory

Concurrency in user applications is on the rise. Modern computers contain multiple threads per core and multiple cores per chip. How to develop efficient and portable parallel program, decrease the complexity has been one of the crucial problems in parallel computing field. Traditional user applications use fine-grained lock to synchronize large multiprogrammed systems. Unfortunately, fine-grained locking is prone to deadlock, non-composability, priority inversion and convoying. Nonblocking algorithms avoid these limitations by ensuring that the delay or failure of a thread never prevents the system as a whole from making forward progress. But it is still difficult to design and implement. Based on the successful experiences of concurrent operations in Database Management System, Transactional memory (TM) promises to do the concurrent read/write operations with high efficiency.The key of transactional systems is the need for conflict validation. This thesis analyzes the current research status about TM, including design pattern of software and hardware TM and conflict detection mechanism. Founded on the research, we introduce a conflict validation model applicable to all cases and apply it in the TM system.Composability is the basic of modern software engineer. Nested Transactional Memory (NTM) represents the composability of TM. After a research on the modern theory of TM, this thesis offers a reference model for nested transactions at the level of memory accesses. The model does not relate to hardware. It defines the semantics for both plain nesting, closed and open nesting, and describes the memory states as seen by each transaction, memory access conflicts, commits and aborts actions. Grounded upon this model, the thesis does a further research on open nesting and offers a priority contention management algorithm. It can effectively improve the execution number of transaction in unit time after applying to the system.Based on the work above, this thesis realizes the NTM system using C++. It has good extensibility and friendly API. It can simplify the process of parallel programming and improve the efficiency of parallel program development.