kth.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat 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 (Engelska)Doktorsavhandling, monografi (Övrigt vetenskapligt)
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.

Ort, förlag, år, upplaga, sidor
Stockholm: KTH Royal Institute of Technology, 2020. , s. 139
Serie
TRITA-EECS-AVL ; 2020:50
Nyckelord [en]
Software Transactional Memory, Parallel Programming, Futures, Synchronization, Concurrency Control, Self-tuning, Sequential Model-based Bayesian Optimization
Nyckelord [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
Nyckelord [sv]
Mjukvarubaserat transaktionellt minne, parallell programmering, futures, synkronisering, parallell exekvering, självjustering, sekventiell modellbaserad Bayesian-optimering
Nationell ämneskategori
Datavetenskap (datalogi) Datorteknik
Forskningsämne
Datalogi
Identifikatorer
URN: urn:nbn:se:kth:diva-282844ISBN: 978-91-7873-654-6 (tryckt)OAI: oai:DiVA.org:kth-282844DiVA, id: diva2:1472160
Disputation
2020-10-22, Ka-Sal C (Sven-Olof Öhrvik), Kistagången 16, Electrum 1, våningsplan 2, KTH Kista, Stockholm, 09:00 (Engelska)
Opponent
Handledare
Projekt
Erasmus Mundus Joint Doctorate in Distributed Computing
Forskningsfinansiär
Stiftelsen för strategisk forskning (SSF)
Anmärkning

QC 20201001

Tillgänglig från: 2020-10-01 Skapad: 2020-09-30 Senast uppdaterad: 2023-03-06Bibliografiskt granskad

Open Access i DiVA

fulltext(2144 kB)438 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 2144 kBChecksumma SHA-512
8698c3da7ea96245822909f0d83447f5968025ebe7090e3cd1087618628e70363cc73832ecb4a15ba4f214148f15433330cfc59e90d67e02b533954174398258
Typ fulltextMimetyp application/pdf

Övriga länkar

zoom link for online defence

Sök vidare i DiVA

Av författaren/redaktören
Zeng, Jingna
Av organisationen
Programvaruteknik och datorsystem, SCS
Datavetenskap (datalogi)Datorteknik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 438 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 981 träffar
RefereraExporteraLänk till posten
Permanent länk

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