Login
Computer Science @ Rochester
Wednesday, April 30, 2003
11:00 AM
CSB 209
Ph.D. Thesis Proposal
William Scherer III
University of Rochester
Compiler and Runtime Support to Improve the Performance of Concurrent Data Structures
Non-blocking synchronization (NBS) offers many tangible benefits when compared to locks, such as fault, preemption, and page-fault tolerance, and potential parallel access to data structures. Further, lock-specific problems of priority inversion and deadlock do not occur in NBS. Offsetting these advantages, NBS has some serious disadvantages. Implementing non-blocking synchronization for arbitrary data structures is extremely difficult due to subtle race conditions and relaxed memory consistency issues. Although universal constructions that transform any sequential code into NBS data structures exist, the performance of resulting data structures has historically been inferior to that from lock-based implementations.

Java Transactional Memory (JTM) is a new universal construction that features much lower overhead for synchronization than previous universal constructions. It thus has the potential to be the first general-purpose yet high-performance framework for implementing NBS data structures. Another novel feature of the JTM is my design for a plug-in architecture that allows arbitrary management of conflict (contention) between threads that access common resources.

I propose to search out schemes for contention management and compare the performance of the JTM using these schemes to each other and to locks. In so doing I will characterize the performance of the JTM system as a whole and thus determine the extent to which it can compete with lock-based synchronization.

I propose to apply this performance data by automating the process of transactionalizing data structures. To accomplish this, I propose to embed the JTM in a Java Virtual Machine and add transactional support to a Java compiler. This will allow automated creation of high-performance NBS versions of a user's concurrent classes, with no special effort needed on the user's part. Finally, I propose to adaptively maximize performance by incorporating runtime information in order to dynamically switch between concurrency implementations.