kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Augmenting Transactional Memory with the Future Abstraction
KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Software and Computer systems, SCS.ORCID iD: 0000-0002-4944-4492
2020 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

The advent of multicore systems spurred great interest in Transactional Memory (TM). TM is a parallel programming paradigm that coordinates concurrent threads by incorporating transactions into programming languages. TM shifts the burden of coordinating and synchronizing concurrent threads from programmers to the compiler, run-time environment, or even hardware.

Unfortunately, though, current state-of-the-art TM implementations lack support for a powerful and intuitive abstraction that is widely used in modern parallel programming environments (e.g., C++, Java and JavaScript), namely "futures". The future abstraction is widely used due to its ability to express in a natural way opportunities for parallelism as well as logical dependencies among parallel tasks. Yet, perhaps surprisingly, the problem of how to support the future abstraction in a TM implementation has not been studied in the literature, although futures represent a natural and convenient means to enable intra-transaction parallelism in long-running transactions.

This dissertation aims at filling precisely this relevant gap in the literature by investigating how to reconcile the TM and the future abstractions.

This limitation is tackled by introducing a novel abstraction, called transactional futures,i.e., transactions that execute wrapped within futures and that are spawned and evaluated by other transactions or transactional futures.

The semantics of transactional futures describes the allowed behaviors with regards to properties such as atomicity and isolation. Multiple semantics are defined, and the trade-offs between ease of use and efficiency are explored for each. Based on these semantics, this dissertation presents two novel TM implementations. The efficiency of the proposed transactional futures abstraction is evaluated in a real system using the TM implementations.

Finally, this dissertation addresses the problem of self-tuning the parallelism degree in TM systems that support intra-transaction parallelism. This goal is achieved by presenting an online learning system that combines model-driven (Sequential Based Bayesian Optimization) and local searches techniques, as well as adaptive performance monitoring techniques.

Abstract [sv]

Tillkomsten av flerkärniga datorsystem har väckt stort intresse för Transactional Memory (TM). TM är en paradigm för parallell programmering som samordnar samtidiga trådar genom att integrera transaktioner i programmeringsspråket. TM förskjuter bördan av att koordinera och synkronisera samtidiga trådar från programmeraren till kompilatorn, exekveringsmiljön eller till och med hårdvaran.

En kraftfull och intuitiv abstraktion som kallas futures används i flera moderna parallella programmeringsspråk, så som C++, Java och JavaScript. Denna abstraktion används i stor utsträckning på grund av dess förmåga att på ett naturligt sätt uttrycka möjligheter till parallellism och logiska beroenden mellan parallella uppgifter.Kanske överraskande så har problemet med att stödja future-abstraktionen i TM-implementationer inte studerats i litteraturen, även om den utgör ett naturligt och bekvämt sätt att möjliggöra parallell exekvering i långvariga transaktioner.

Avhandlingen syftar till att fylla just detta relevanta gap i litteraturen genom att undersöka hur man kan förena TM och futures.

Denna förening görs genom att införa en ny abstraktion, kallad transaktionell futures, d.v.s. transaktioner som utförs inslagna inuti futures och som skapas och utvärderas av andra transaktioner eller transaktionella futures.

Semantiken hos en transaktionell future beskriver de tillåtna beteendena med avseende på egenskaper som atomicitet och isolering. Flera semantiker defineras, och balansen mellan användarvänlighet och effektivitet utforskas för semantikerna. Baserat på dessa semantiker så presenterar denna avhandling två nya TM-implementationer. Effektiviteten hos den föreslagna transaktionell future-abstraktionen utvärderas i ett riktigt system som använder dessa TM-implementationer.

Slutligen behandlar denna avhandling problemet med att självjustera graden av parallellism i TM-system som stöder inkapslade parallella transaktioner inom transaktioner. Målet uppnås genom ett online-inlärningssystem som kombinerar modelldrivna (Sequential Based Bayesian Optimization) och lokala söktekniker, såväl som anpassade prestandaövervakningstekniker.

Abstract [pt]

O advento dos sistemas multicore tem despertado grande interesse na Memória Transacional (MT). MT é um paradigma de programação paralela que coordena acessos concorrentes à memória partilhada, incorporando transações em linguagens de programação. A MT transfere a complexidade de coordenação e sincronização de \textit{threads} dos programadores para o compilador, a implementação da MT ou até o hardware.

No entanto, as implementações existentes da MT não são compatíveis com uma abstração poderosa e intuitiva que é amplamente utilizada em ambientes modernos de programação paralela (por exemplo, C++, Java e JavaScript), ou seja, "futuros" (ou promessas). A abstração de futuro é bastante popular devido à sua capacidade de expressar de maneira intuitiva quer oportunidades de paralelismo quer dependências lógicas entre tarefas paralelas. Todavia, talvez surpreendentemente, o problema de como suportar a abstração de futuro numa implementação de MT ainda não tem sido estudado na literatura, embora os futuros representem um meio natural e conveniente para conseguir obter paralelismo intra-transações em transações de longa duração.

Esta dissertação visa preencher precisamente essa importante lacuna da literatura, investigando como reconciliar as abstrações de MT e a de futuros.

Esse problema é abordado introduzindo uma nova abstração, denominada futuro transacional, ou seja, uma transação executadas dentro de um futuro e gerada e avaliada por outras transações ou futuros transacionais. Esta dissertação define um conjunto de semânticas alternativas para as propriedades de atomicidade e isolamento de futuros transacionais, que visam explorar diferentes equilibrios entre facilidade de uso e eficiência.

Com base nessas semânticas, esta dissertação apresenta e avalia duas novas implementações de MT, que permitiram avaliar a eficiência da abstração de futuro transacional em sistemas reais.

Finalmente, esta dissertação aborda o problema de ajustar de forma automática o grau de paralelismo em sistemas de MT que suportam paralelismo intra-transacional. Esse objetivo é alcançado através da introdução de um sistema de aprendizagem automático que combina técnicas de buscas locais e orientadas por modelo (Sequential Based Bayesian Optimization), bem como mecanismos adaptativos de monitorização de desempenho.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2020. , p. 139
Series
TRITA-EECS-AVL ; 2020:50
Keywords [en]
Software Transactional Memory, Parallel Programming, Futures, Synchronization, Concurrency Control, Self-tuning, Sequential Model-based Bayesian Optimization
Keywords [pt]
Memória Transacional em Software, Programação Paralela, Futuros, Sincronização, Controle de Concorrência, Auto-ajuste, Otimização Bayesiana Seqeencial Baseada em Modelos
Keywords [sv]
Mjukvarubaserat transaktionellt minne, parallell programmering, futures, synkronisering, parallell exekvering, självjustering, sekventiell modellbaserad Bayesian-optimering
National Category
Computer Sciences Computer Engineering
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-282844ISBN: 978-91-7873-654-6 (print)OAI: oai:DiVA.org:kth-282844DiVA, id: diva2:1472160
Public defence
2020-10-22, Ka-Sal C (Sven-Olof Öhrvik), Kistagången 16, Electrum 1, våningsplan 2, KTH Kista, Stockholm, 09:00 (English)
Opponent
Supervisors
Projects
Erasmus Mundus Joint Doctorate in Distributed Computing
Funder
Swedish Foundation for Strategic Research
Note

QC 20201001

Available from: 2020-10-01 Created: 2020-09-30 Last updated: 2023-03-06Bibliographically approved

Open Access in DiVA

fulltext(2144 kB)426 downloads
File information
File name FULLTEXT01.pdfFile size 2144 kBChecksum SHA-512
8698c3da7ea96245822909f0d83447f5968025ebe7090e3cd1087618628e70363cc73832ecb4a15ba4f214148f15433330cfc59e90d67e02b533954174398258
Type fulltextMimetype application/pdf

Other links

zoom link for online defence

Search in DiVA

By author/editor
Zeng, Jingna
By organisation
Software and Computer systems, SCS
Computer SciencesComputer Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 426 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 967 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf