Back to search

University of Crete (UOC)

Techniques for enhancing parallelism in mechanisms that automatically execute sequential code in concurrent environments

Abstract

dc:description

Two well-known mechanisms for automatically executing sequential code segments in aconcurrent environment are universal constructions and software transactional memory.They both have the same goal of simplifying the task of parallel programming. A universalconstruction is a mechanism which takes as input the sequential code and executes itin a concurrent environment. Software transactional memory (STM) employs transactionsto avoid conflicting accesses to common data (known as data items or transactional variables).A transaction may either commit, in which case it appears as if it has been executedat a single point in time, or abort, in which case it appears as if it is never executed. Noticethat if a transaction commits, then its updates to data items become visible, otherwise, if itaborts, all its changes are discarded.In this thesis, we study how to achieve increased concurrency while designing suchmechanisms, without sacrificing correctness and progress. One well-studied technique forenhancing concurrency is ensuring a property called disjoint-access parallelism. Roughlyspeaking, disjoint-access parallelism guarantees that processes operating on different partsof an implemented object do not interfere with each other. Thus, disjoint-access parallelimplementations allow for increased parallelism.Wait-freedom is a well-known progress property which ensures that each process completesits execution, even when other processes run at arbitrary speeds or crash. Waitfreedomis highly desirable because implementations ensuring this property are highly faulttolerantand usually ensure bounds on the number of steps executed before an implementedoperation responds.In this thesis, we prove that it is not possible for a universal construction to achieveboth disjoint-access parallelism and wait-freedom; this impossibility result holds for STMas well. Specifically, we identify a natural property of universal constructions and provethat there is no universal construction (with this property) that ensures both disjoint-access parallelism and wait-freedom. Our impossibility proof is obtained by considering a dynamicdata structure that can grow arbitrarily large during an execution. This impossibility resultcan be beaten if we focus on data structures that have a bound on the number of piecesof data accessed by each operation they support. For this setting, we present a universalconstruction that ensures both wait-freedom and disjoint-access parallelism.We further introduce and study weaker versions of disjoint-access parallelism, whichstill however allow for increased parallelism. Motivated be the way current STM algorithmwork, we introduce timestamp-ignoring disjoint-access parallelism, which allows operationsoperating on different parts of an implemented data structure to proceed in parallel,except for accesses to a timestamp object. A timestamp object allows a process to know the“time” at which it accesses the object, relative to accesses by other processes (on the sametimestamp object); specifically, a process is able to determine whether it accessed the objectbefore or after some other process accessed it. We present a universal construction that ensures wait-freedom and timestamp-ignoring disjoint-access parallelism, for certain classesof data structures.We next concentrate on important issues in achieving enhanced parallelism in STMcomputing. Most STM algorithms employ an optimistic approach, where transactions areexecuted speculatively, as if they will never read inconsistent data. When a conflict occurs,STM algorithms usually abort one of the transactions to ensure correctness; two concurrenttransactions conflict if they both access the same data item and at least one of themattempts to modify it. The work performed by a transaction that aborts is discarded and itis later re-executed as a new transaction; this incurs a performance penalty. Moreover, forread-intensive workloads, it is really important to ensure that transactions that never updatea data item (which are called read-only transactions) never abort and are wait-free; i.e. theyalways commit within a finite number of steps. For these reasons, the literature also contains pessimistic STM algorithms, which never abort transactions and support wait-freedom for read-only transactions. However, most of them achieve this by “pessimistically” requiring transactions that update data items (called update transactions) to be executed sequentially. This significantly restricts parallelism in many cases and therefore it also leads to performance degradation.As a first step towards achieving enhanced parallelism, we introduce WFR-TM, an STMalgorithm which attempts to combine some of the advantages of pessimistic and optimisticSTM. In WFR-TM, as in pessimistic STMs, read-only transactions never abort and are wait-free. WFR-TM additionally ensures that read-only transactions never execute expensivesynchronization instructions. In contrast to pessimistic STMs, these properties areachieved without sacrificing all parallelism between update transactions. More specifically,update transactions use a pessimistic approach to synchronize with concurrently executedread-only transactions: they wait for read-only transactions to complete. However, they usean optimistic approach to synchronize with each other: they are executed concurrently ina speculative way, and they commit if they have not encountered any conflict with otherupdate transactions during their execution. Thus, WFR-TM achieves more parallelism thanpessimistic STMs.Finally, we introduce SemanticTM, an STM algorithm in which parallelism is achievedat the level of transactional instructions; i.e. not only the transactions themselves but alsothe instructions of each transaction may be executed concurrently. With compiler support,SemanticTM guarantees that simple transactions are wait-free, by ensuring that no transactions conflict. We remark that STM algorithms that never abort transactions are highly desirable since they additionally support transactions that perform irrevocable operations, e.g. I/O operations.

Degree

thesis:*
Grantor dc:publisher
University of Crete (UOC)
Year dc:date
2014

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Kosmas, Eleftherios
  • Κοσμάς, Ελευθέριος

Subjects

dc:subject × 32

Rights

dc:rights
Statement dc:rights
  • BY_NC_SA
Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/35510

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Kosmas, Eleftherios; Κοσμάς, Ελευθέριος. Techniques for enhancing parallelism in mechanisms that automatically execute sequential code in concurrent environments. University of Crete (UOC), 2014. http://hdl.handle.net/10442/hedi/35510