Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Augmenting Transactional Memory with the Future Abstraction
KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Programvaruteknik och datorsystem, SCS.ORCID-id: 0000-0002-4944-4492
2020 (engelsk)Doktoravhandling, monografi (Annet vitenskapelig)
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.

sted, utgiver, år, opplag, sider
Stockholm: KTH Royal Institute of Technology, 2020. , s. 139
Serie
TRITA-EECS-AVL ; 2020:50
Emneord [en]
Software Transactional Memory, Parallel Programming, Futures, Synchronization, Concurrency Control, Self-tuning, Sequential Model-based Bayesian Optimization
Emneord [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
Emneord [sv]
Mjukvarubaserat transaktionellt minne, parallell programmering, futures, synkronisering, parallell exekvering, självjustering, sekventiell modellbaserad Bayesian-optimering
HSV kategori
Forskningsprogram
Datalogi
Identifikatorer
URN: urn:nbn:se:kth:diva-282844ISBN: 978-91-7873-654-6 (tryckt)OAI: oai:DiVA.org:kth-282844DiVA, id: diva2:1472160
Disputas
2020-10-22, Ka-Sal C (Sven-Olof Öhrvik), Kistagången 16, Electrum 1, våningsplan 2, KTH Kista, Stockholm, 09:00 (engelsk)
Opponent
Veileder
Prosjekter
Erasmus Mundus Joint Doctorate in Distributed Computing
Forskningsfinansiär
Swedish Foundation for Strategic Research
Merknad

QC 20201001

Tilgjengelig fra: 2020-10-01 Laget: 2020-09-30 Sist oppdatert: 2023-03-06bibliografisk kontrollert

Open Access i DiVA

fulltext(2144 kB)435 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 2144 kBChecksum SHA-512
8698c3da7ea96245822909f0d83447f5968025ebe7090e3cd1087618628e70363cc73832ecb4a15ba4f214148f15433330cfc59e90d67e02b533954174398258
Type fulltextMimetype application/pdf

Andre lenker

zoom link for online defence

Søk i DiVA

Av forfatter/redaktør
Zeng, Jingna
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 435 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

isbn
urn-nbn

Altmetric

isbn
urn-nbn
Totalt: 977 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf