Title page for ETD etd-06292016-021029


Type of Document Dissertation
Author Assiri, Basem Ibrahim
Author's Email Address bassir1@lsu.edu
URN etd-06292016-021029
Title Fairness and Approximation in Multi-version Transactional Memory.
Degree Doctor of Philosophy (Ph.D.)
Department Computer Science
Advisory Committee
Advisor Name Title
Busch, Konstantin Committee Chair
Karki, Bijaya Committee Member
Mukhopadhyay, Supratik Committee Member
Abu-Farsakh, Murad Dean's Representative
Keywords
  • Fairness
  • Approximation
  • Multi-version
  • Transactional Memory
  • Read-only Transaction
  • Update Transaction
  • Count Object
  • Queue Object
Date of Defense 2016-06-15
Availability unrestricted
Abstract
Shared memory multi-core systems bene t from transactional memory implementations

due to the inherent avoidance of deadlocks and progress guarantees. In

this research, we examine how the system performance is a ected by transaction

fairness in scheduling and by the precision in consistency. We rst explore

the fairness aspect using a Lazy Snapshot (multi-version) Algorithm. The fairness

of transactions scheduling aims to balance the load between read-only and update

transactions. We implement a fairness mechanism based on machine learning

techniques that improve fairness decisions according to the transaction execution

history. Experimental analysis shows that the throughput of the Lazy Snapshot

Algorithm is improved with machine learning support.

We also explore the impacts on performance of consistency relaxation. In transactional

memory, correctness is typically proven with opacity which is a precise

consistency property that requires a legal serialization of an execution such that

transactions do not overlap (atomicity) and read instructions always return the

most recent value (legality). In real systems there are situations where system delays

do not allow precise consistency, such as in large scale applications, due to

network or other time delays. Thus, we introduce here the notion of approximate

consistency in transactional memory. We de ne K-opacity as a relaxed consistency

property where transactions' read operations may return one of K most recent

written values. In multi-version transactional memory, this allows to save a new

object version once every K object updates, which has two bene ts: (i) it reduces

space requirements by a factor of K, and (ii) it reduces the number of aborts, since

there is smaller chance for con

icts. In fact, we apply the concept of K-opacity on

regular read and write, count and queue objects, which are common objects used in typical concurrent programs. We provide formal correctness proofs and we also

demonstrate the performance bene ts of our approach with experimental analysis.

We compare the performance of precise consistent execution (1-opaque) with

di erent consistency values of K using micro benchmarks. The results show that

increased relaxation of opacity gives higher throughput and decreases the aborts

rate signi cantly.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Assiri_Diss.pdf 1.37 Mb 00:06:21 00:03:16 00:02:51 00:01:25 00:00:07

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.