Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Disjoint-Access Parallelism Does Not Entail Scalability
 
conference paper

Disjoint-Access Parallelism Does Not Entail Scalability

Guerraoui, Rachid  
•
Letia, Mihai  
2014
Proceedings of the Second International Conference, NETYS
Second International Conference, NETYS

Disjoint Access Parallelism (DAP) stipulates that operations involving disjoint sets of memory words must be able to progress independently, without interfering with each other. In this work we argue towards revising the two decade old wisdom saying that DAP is a binary condition that splits concurrent programs into scalable and non-scalable. We first present situations where DAP algorithms scale poorly, thus showing that not even algorithms that achieve this property provide scalability under all circumstances. Next, we show that algorithms which violate DAP can sometimes achieve the same scalability and performance as their DAP counterparts. We continue to show how by violating DAP and without sacrificing scalability we are able to circumvent three theoretical results showing that DAP is incompatible with other desirable properties of concurrent programs. Finally we introduce a new property called generalized disjoint-access parallelism (GDAP) which estimates how much of an algorithm is DAP. Algorithms having a large DAP part scale similar to DAP algorithms while not being subject to the same impossibility results.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-319-09581-3_4
Author(s)
Guerraoui, Rachid  
Letia, Mihai  
Date Issued

2014

Published in
Proceedings of the Second International Conference, NETYS
ISBN of the book

978-3-319-09581-3

Start page

41

End page

56

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Event nameEvent placeEvent date
Second International Conference, NETYS

Marrakech, Morocco

May 15-17, 2014

Available on Infoscience
May 28, 2015
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/114105
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés