Within the last decade multi-core processors have become increasingly commonplace with thepower and performance demands of modern real-world programs acting to accelerate this trend. Therapid advancements in designing and adoption of such architectures mean that there is a serious needfor programming models that allow the development of correct parallel programs that executeefficiently on these processors. A principle problem in this regard is that of efficiently synchronizingconcurrent accesses to shared memory. Traditional solutions to this problem are either inefficient butprovide programmability (coarse-grained locks) or are efficient but are not composable and very hardto program and verify (fine-grained locks). Optimistic Transactional Memory systems provide many ofthe composability and programmabillity advantages of coarse-grained locks and good theoreticalscaling but several studies have found that their performance in practice for many programs remainsquite poor primarily because of the high overheads of providing safe optimism. Moreover currenttransactional memory models remain rigid - they are not suited for expressing some of the complexthread interactions that are prevalent in modern parallel programs. Moreover, the synchronizationachieved by these transactional memory systems is at the physical or memory level.This thesis advocates a position that memory synchronization problem for threads should bemodeled and solved in terms of synchronization of underlying program values which have semanticsassociated with them. It presents optimistic synchronization techniques that address the semanticsynchronization requirements of a parallel program instead.These techniques include methods to 1) enable optimistic transactions to recover fromexpensive sharing conflicts without discarding all the work made possible by the optimism 2) enable ahybrid pessimistic-optimistic form of concurrency control that lowers overheads 3) makesynchronization value-aware and semantics-aware 4) enable finer grained consistency rules (thanallowed by traditional optimistic TM models) therefore avoiding conflicts that do not enforce anysemantic property required by the program. In addition to improving the expressibility of specificsynchronization idioms all these techniques are also effective in improving parallel performance. Thisthesis formulates these techniques in terms of their purpose, the extensions to the language, thecompiler as well as to the concurrency control runtime necessary to implement them. It also brieflypresents an experimental evaluation of each of them on a variety of modern parallel workloads. Theseexperiments show that these techniques significantly improve parallel performance and scalability overprograms using state-of-the-art optimistic synchronization methods.
PDF
download
878987797
028-85220240
