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

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • harvard-cite-them-right
  • 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
NBmalloc: Allocating Memory in a Lock-Free Manner
Högskolan i Borås, Institutionen Handels- och IT-högskolan. (CSL@BS)
2010 (Engelska)Ingår i: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 58, nr 2, s. 304-338Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Efficient, scalable memory allocation for multithreaded applications on multiprocessors is a significant goal of recent research. In the distributed computing literature it has been emphasized that lock-based synchronization and concurrency-control may limit the parallelism in multiprocessor systems. Thus, system services that employ such methods can hinder reaching the full potential of these systems. A natural research question is the pertinence and the impact of lock-free concurrency control in key services for multiprocessors, such as in the memory allocation service, which is the theme of this work. We show the design and implementation of NBmalloc, a lock-free memory allocator designed to enhance the parallelism in the system. The architecture of NBmalloc is inspired by Hoard, a well-known concurrent memory allocator, with modular design that preserves scalability and helps avoiding false-sharing and heap-blowup. Within our effort to design appropriate lock-free algorithms for NBmalloc, we propose and show a lock-free implementation of a new data structure, flat-set, supporting conventional “internal” set operations as well as “inter-object” operations, for moving items between flat-sets. The design of NBmalloc also involved a series of other algorithmic problems, which are discussed in the paper. Further, we present the implementation of NBmalloc and a study of its behaviour in a set of multiprocessor systems. The results show that the good properties of Hoard w.r.t. false-sharing and heap-blowup are preserved.

Ort, förlag, år, upplaga, sidor
Springer New York LLC , 2010. Vol. 58, nr 2, s. 304-338
Nyckelord [en]
memory allocation, lock-free synchronisation, non-blocking synchronisation, multithreaded applications, Parallel Programming
Nationell ämneskategori
Datavetenskap (datalogi) Data- och informationsvetenskap
Identifikatorer
URN: urn:nbn:se:hb:diva-2741DOI: 10.1007/s00453-008-9268-xLokalt ID: 2320/5970OAI: oai:DiVA.org:hb-2741DiVA, id: diva2:870835
Forskningsfinansiär
National Supercomputer Centre (NSC), Sweden
Anmärkning

Publicerad i Algorithmica Online First. Väntar på att publiceras i ett nummer av Algorithmica.

Sponsorship:

This work was supported by computational resources provided by the Swedish National Supercomputer Centre (NSC).

Tillgänglig från: 2015-11-13 Skapad: 2015-11-13 Senast uppdaterad: 2018-01-10Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Gidenstam, Anders

Sök vidare i DiVA

Av författaren/redaktören
Gidenstam, Anders
Av organisationen
Institutionen Handels- och IT-högskolan
I samma tidskrift
Algorithmica
Datavetenskap (datalogi)Data- och informationsvetenskap

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 197 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • harvard-cite-them-right
  • 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