uu.seUppsala universitets publikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • 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
Precise and sound automatic fence insertion procedure under PSO
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.ORCID-id: 0000-0003-4993-0092
2015 (engelsk)Inngår i: Networked Systems: NETYS 2015, Springer, 2015, s. 32-47Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

We give a sound and complete procedure for fence insertion for concurrent finite-state programs running under the PSO memory model. This model allows ''write to read'' and ''write-to-write'' relaxations corresponding to the addition of an unbounded store buffers between processors and the main memory. We introduce a novel machine model, called the Hierarchical Single-Buffer (HSB) semantics, and show that the reachability problem for a program under PSO can be reduced to the reachability problem under HSB. We present a simple and effective backward reachability analysis algorithm for the latter, and propose a counter-example guided fence insertion procedure. The procedure infers automatically a minimal set of fences that ensure correctness of the program. We have implemented a prototype and run it successfully on all standard benchmarks, together with several challenging examples.

sted, utgiver, år, opplag, sider
Springer, 2015. s. 32-47
Serie
Lecture Notes in Computer Science ; 9466
Emneord [en]
PSO, weak memory model, well-quasi order, well-structured transition system, concurrent program, verification
HSV kategori
Identifikatorer
URN: urn:nbn:se:uu:diva-253647DOI: 10.1007/978-3-319-26850-7_3ISBN: 978-3-319-26849-1 (tryckt)OAI: oai:DiVA.org:uu-253647DiVA, id: diva2:815352
Konferanse
NETYS 2015, May 13–15, Agadir, Morocco
Prosjekter
UPMARCTilgjengelig fra: 2016-03-23 Laget: 2015-05-29 Sist oppdatert: 2018-11-20

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Personposter BETA

Abdulla, Parosh AzizAtig, Mohamed FaouziNgo, Tuan Phong

Søk i DiVA

Av forfatter/redaktør
Abdulla, Parosh AzizAtig, Mohamed FaouziNgo, Tuan Phong
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

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

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • 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