Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Dates: Last 2 Years

You searched for subject:(Concurrent Data Structures). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters

1. Aksenov, Vitalii. Synchronization costs in parallel programs and concurrent data structures : Coûts de synchronization dans les programmes parallèlles et les structures de données simultanées.

Degree: Docteur es, Informatique. Programmation simultanée, 2018, Sorbonne Paris Cité; ITMO University

Pour utiliser la puissance de calcul des ordinateurs modernes, nous devons écrire des programmes concurrents. L’écriture de programme concurrent efficace est notoirement difficile, principalement en raison de la nécessité de gérer les coûts de synchronisation. Dans cette thèse, nous nous concentrons sur les coûts de synchronisation dans les programmes parallèles et les structures de données concurrentes.D’abord, nous présentons une nouvelle technique de contrôle de la granularité pour les programmes parallèles conçus pour un environnement de multi-threading dynamique. Ensuite, dans le contexte des structures de données concurrentes, nous considérons la notion d’optimalité de concurrence (concurrency-optimality) et proposons la première implémentation concurrence-optimal d’un arbre binaire de recherche qui, intuitivement, accepte un ordonnancement concurrent si et seulement si l’ordonnancement est correct. Nous proposons aussi la combinaison parallèle (parallel combining), une technique qui permet l’implémentation efficace des structures de données concurrences à partir de leur version parallèle par lots. Nous validons les techniques proposées par une évaluation expérimentale, qui montre des performances supérieures ou comparables à celles des algorithmes de l’état de l’art.Dans une perspective plus formelle, nous considérons le phénomène d’assistance (helping) dans des structures de données concurrentes. On observe un phénomène d’assistance quand l’ordre d’une opération d’un processus dans une trace linéarisée est fixée par une étape d’un autre processus. Nous montrons qu’aucune implémentation sans attente (wait-free) linéarisable d’une pile utilisant les primitives read, write, compare&swap et fetch&add ne peut être “sans assistance” (help-free), corrigeant une erreur dans une preuve antérieure de Censor-Hillel et al. Finalement, nous proposons une façon simple de prédire analytiquement le débit (throughput) des structures de données basées sur des verrous à gros grains.

To use the computational power of modern computing machines, we have to deal with concurrent programs. Writing efficient concurrent programs is notoriously difficult, primarily due to the need of harnessing synchronization costs. In this thesis, we focus on synchronization costs in parallel programs and concurrent data structures.First, we present a novel granularity control technique for parallel programs designed for the dynamic multithreading environment. Then in the context of concurrent data structures, we consider the notion of concurrency-optimality and propose the first implementation of a concurrency-optimal binary search tree that, intuitively, accepts a concurrent schedule if and only if the schedule is correct. Also, we propose parallel combining, a technique that enables efficient implementations of concurrent data structures from their parallel batched counterparts. We validate the proposed techniques via experimental evaluations showing superior or comparable performance with respect to state-of-the-art algorithms.From a more…

Advisors/Committee Members: Gallet-Delporte, Carole (thesis director), Shalyto, Anatoly (thesis director), Kuznetsov, Petr (thesis director).

Subjects/Keywords: Structures de données simultanées; Contrôle de la granularité; Programme concurrent; Concurrent data structures; Granularity control; Concurrent programs

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Aksenov, V. (2018). Synchronization costs in parallel programs and concurrent data structures : Coûts de synchronization dans les programmes parallèlles et les structures de données simultanées. (Doctoral Dissertation). Sorbonne Paris Cité; ITMO University. Retrieved from http://www.theses.fr/2018USPCC025

Chicago Manual of Style (16th Edition):

Aksenov, Vitalii. “Synchronization costs in parallel programs and concurrent data structures : Coûts de synchronization dans les programmes parallèlles et les structures de données simultanées.” 2018. Doctoral Dissertation, Sorbonne Paris Cité; ITMO University. Accessed January 17, 2020. http://www.theses.fr/2018USPCC025.

MLA Handbook (7th Edition):

Aksenov, Vitalii. “Synchronization costs in parallel programs and concurrent data structures : Coûts de synchronization dans les programmes parallèlles et les structures de données simultanées.” 2018. Web. 17 Jan 2020.

Vancouver:

Aksenov V. Synchronization costs in parallel programs and concurrent data structures : Coûts de synchronization dans les programmes parallèlles et les structures de données simultanées. [Internet] [Doctoral dissertation]. Sorbonne Paris Cité; ITMO University; 2018. [cited 2020 Jan 17]. Available from: http://www.theses.fr/2018USPCC025.

Council of Science Editors:

Aksenov V. Synchronization costs in parallel programs and concurrent data structures : Coûts de synchronization dans les programmes parallèlles et les structures de données simultanées. [Doctoral Dissertation]. Sorbonne Paris Cité; ITMO University; 2018. Available from: http://www.theses.fr/2018USPCC025

.