Search

Your search keyword '"Shared memory model"' showing total 14 results
Start Over Descriptor "Shared memory model" Language english
14 results on '"Shared memory model"'

1. Randomized renaming in shared memory systems.

Author

Berenbrink, Petra, Brinkmann, André, Elsässer, Robert, Friedetzky, Tom, and Nagel, Lars

Subjects
*DISTRIBUTED algorithms, *DISTRIBUTED computing, *MEMORY
Abstract

Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m. The problem is called tight if m = n , and loose if m > n. In recent years renaming came to the fore again and new algorithms were developed. For tight renaming in asynchronous shared memory systems, Alistarh et al. describe a construction based on the AKS network that assigns all names within O (log n) steps per process. They also show that, depending on the size of the name space, loose renaming can be done considerably faster. For m = (1 + ϵ) ⋅ n and constant ϵ , they achieve a step complexity of O (log log n). In this paper we consider tight as well as loose renaming and introduce randomized algorithms that achieve their tasks with high probability. The model assumed is the asynchronous shared-memory model against an adaptive adversary. Our algorithm for loose renaming maps n processes to a name space of size m = (1 + 2 ∕ (log n) ℓ) ⋅ n = (1 + o (1)) ⋅ n performing O (ℓ ⋅ (log log n) 2) test-and-set operations. In the case of tight renaming, we present a protocol that assigns n processes to n names with step complexity O (log n) , but without the overhead and impracticality of the AKS network. This algorithm utilizes modern hardware features in form of a counting device which is also described in the paper. This device may have the potential to speed up other distributed algorithms as well. • Tight and loose renaming in the shared-memory model. • Loose renaming with (1+o(1)) * n names in poly-double-logarithmic number of steps. • Tight renaming algorithm simpler and more practical than existing one. • Tight renaming relies on new HW register with potential benefits in other areas. [ABSTRACT FROM AUTHOR]

Published
2021
Full Text
View/download PDF

2. Convergence analysis of asynchronous stochastic recursive gradient algorithms.

Author

Wang, Pengfei and Zheng, Nenggan

Subjects
*STOCHASTIC analysis, *ALGORITHMS, *LEARNING problems, *MACHINE learning, *MATHEMATICAL optimization
Abstract

Asynchronous stochastic algorithms with variance reduction techniques have been empirically shown to be useful for many large-scale machine learning problems. By making a parallel optimization algorithm asynchronous, one can reduce the synchronization cost and improve the practical efficiency. Recently, the stochastic recursive gradient algorithm has shown superior theoretical performance; however, it is not scalable enough in the current big data era. To make it more practical, we propose a class of asynchronous stochastic recursive gradient methods and analyze them in the shared memory model. The analysis results show that our asynchronous algorithms can linearly converge to the solution in the strongly convex case and complete the iteration faster. In addition, we analyze the "price of asynchrony" and give the sufficient conditions required for linear speedup. To the best of our knowledge, our speedup conditions match the optimal bounds of asynchronous stochastic algorithms known thus far. Finally, we demonstrate our theoretical analyses from a practical implementation on a multicore machine. [ABSTRACT FROM AUTHOR]

Published
2022
Full Text
View/download PDF

3. “Slow is Fast” for wireless sensor networks in the presence of message losses.

Author

Hajisheykhi, Reza, Zhu, Ling, Arumugam, Mahesh, Demirbas, Murat, and Kulkarni, Sandeep

Subjects
*WIRELESS sensor networks, *MESSAGE passing (Computer science), *PROBABILITY theory, *INFORMATION sharing, *SELF-stabilization (Computer science)
Abstract

We present a new shared memory model, SF shared memory model. In this model, the actions of each node are partitioned into slow actions and fast actions. By contrast, the traditional shared memory model only includes fast actions. Intuitively, slow actions can utilize slightly stale state information to execute successfully. However, fast actions require that the state information they use is most recent. We show that the use of slow actions can substantially benefit in improving performance of programs from the shared memory model to WAC model that has been designed for sensor networks. To illustrate this, we use three protocols concerning problems that need to be solved in sensor networks. We show that under various message loss probabilities, densities, etc., slow actions can improve the performance substantially, since slow actions reduce the performance penalty of fast actions under heavy message loss environments. Moreover, the effectiveness of the slow action increases when there is a higher probability of message loss. [ABSTRACT FROM AUTHOR]

Published
2015
Full Text
View/download PDF

4. Upper and Lower Bounds for Deterministic Approximate Objects

Author

Adnane Khattabi, Corentin Travers, Alessia Milani, Danny Hendler, Khattabi, Adnane, Ben-Gurion University of the Negev (BGU), Laboratoire Bordelais de Recherche en Informatique (LaBRI), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)

Subjects
FOS: Computer and information sciences, Discrete mathematics, distributed algorithms, Shared memory model, Computer science, Multiplicative function, Approximation algorithm, Value (computer science), [INFO] Computer Science [cs], Upper and lower bounds, Distributed computing, shared memory, Computer Science - Distributed, Parallel, and Cluster Computing, relaxed specifications, concurrent data structures, [INFO]Computer Science [cs], Distributed, Parallel, and Cluster Computing (cs.DC), fault tolerance
Abstract

Relaxing the sequential specification of shared objects has been proposed as a promising approach to obtain implementations with better complexity. In this paper, we study the step complexity of relaxed variants of two common shared objects: max registers and counters. In particular, we consider the $k$ -multiplicative-accurate max register and the k-multiplicative-accurate counter, where read operations are allowed to err by a multiplicative factor of $k$ (for some $k\in \mathbb{N}$ ). More accurately, reads are allowed to return an approximate value $x$ of the maximum value $v$ previously written to the max register, or of the number $v$ of increments previously applied to the counter, respectively, such that $v/k\leq x\leq v. k$ . We provide upper and lower bounds on the complexity of implementing these objects in a wait-free manner in the shared memory model.

Published
2021

5. Journal of Parallel and Distributed Computing / Randomized renaming in shared memory systems

Author

Berenbrink, Petra, Brinkmann, André, Elsässer, Robert, Friedetzky, Tom, and Nagel, Lars

Subjects
Randomized algorithm, Tight renaming, Shared memory model, Distributed algorithm, Loose renaming
Abstract

Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m. The problem is called tight if m=n, and loose if m>n. In recent years renaming came to the fore again and new algorithms were developed. For tight renaming in asynchronous shared memory systems, Alistarh et al. describe a construction based on the AKS network that assigns all names within O(logn) steps per process. They also show that, depending on the size of the name space, loose renaming can be done considerably faster. For m=(1+ϵ)⋅n and constant ϵ, they achieve a step complexity of O(loglogn). In this paper we consider tight as well as loose renaming and introduce randomized algorithms that achieve their tasks with high probability. The model assumed is the asynchronous shared-memory model against an adaptive adversary. Our algorithm for loose renaming maps n processes to a name space of size m=(1+2∕(logn)ℓ)⋅n=(1+o(1))⋅n performing O(ℓ⋅(loglogn)2) test-and-set operations. In the case of tight renaming, we present a protocol that assigns n processes to n names with step complexity O(logn), but without the overhead and impracticality of the AKS network. This algorithm utilizes modern hardware features in form of a counting device which is also described in the paper. This device may have the potential to speed up other distributed algorithms as well.

Published
2021

6. Parallelization Methods for Edge Extraction Applied to Chip Multiprocessor Clusters.

Author

Cheng, Guo, Chen, Luo, Wu, Qiuyun, and Jing, Ning

Abstract

As the parallel computing technologies become mature, many computationally intensive and/or data intensive algorithms could be improved with parallelization methods. In this paper, we improve the performance of the edge extraction algorithmic program by parallelizing the sequential algorithm. We altogether propose three parallelization methods based on chip multiprocessor (CMP) clusters. The OpenMP-based method is investigated for the shared memory model and thus it is applied to single CMP node, while the three MPI-based methods are investigated for the message passing model and thus they are applied to CMP-clusters. Massive experiments verify that the parallelization methods proposed in this paper are all effective and efficient. [ABSTRACT FROM PUBLISHER]

Published
2012
Full Text
View/download PDF

7. The expressive power of snap-stabilization

Author

Vincent Villain, Franck Petit, Alain Cournier, Stéphane Devismes, Ajoy K. Datta, Modélisation, Information et Systèmes - UR UPJV 4290 (MIS), Université de Picardie Jules Verne (UPJV), Department of Computer Science [Las Vegas], University of Nevada [Las Vegas] (WGU Nevada), VERIMAG (VERIMAG - IMAG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Large-Scale Distributed Systems and Applications (Regal), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
Leader election, Theoretical computer science, Shared memory model, reset, General Computer Science, Computer science, Distributed computing, leader election, snapshot, Self-stabilization, Fault tolerance, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Expressive power, Theoretical Computer Science, Fault-tolerance, self-stabilization, 010201 computation theory & mathematics, propagation of information with feedback, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], Daemon, snap-stabilization
Abstract

International audience; A snap-stabilizing algorithm, regardless of the initial configuration of the system, guarantees that it always behaves according to its specification. We consider here the locally shared memory model. In this model, we propose the first snap-stabilizing Propagation of Information with Feedback (PIF) algorithm for rooted networks of arbitrary connected topology which is proven assuming the distributed unfair daemon. Then, we use the proposed PIF algorithm as a key module in designing snap-stabilizing solutions for some fundamental problems in distributed systems, such as Leader Election, Reset, Snapshot, and Termination Detection. Finally, we show that in the locally shared memory model, snap-stabilization is as expressive as self-stabilization by designing a universal transformer to provide a snap-stabilizing version of any algorithm that can be self-stabilized with the transformer of Katz and Perry (Distributed Computing, 1993). Since by definition a snap-stabilizing algorithm is also self-stabilizing, self-and snap-stabilization have the same expressiveness in the locally shared memory model.

Published
2016

8. A Message-Passing and Adaptive Implementation of the Randomized Test-and-Set Object

Author

Emmanuelle Anceaume, Achour Mostefaoui, Bruno Sericola, François Castella, Confidentialité, Intégrité, Disponibilité et Répartition (CIDRE), CentraleSupélec-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche Mathématique de Rennes (IRMAR), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), Invariant Preserving SOlvers (IPSO), Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), LINA, Université de Nantes (UN), Dependability Interoperability and perfOrmance aNalYsiS Of networkS (DIONYSOS), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES (IRISA-D2), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), ANR-11-INSE-010, Avresky, DR, Busnel Y., ANR-11-INSE-0010,MARS,Systèmes embarqués fiables et faible consommation à base de Mémoires Magnétiques (MRAM)(2011), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-AGROCAMPUS OUEST, Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Inria Rennes – Bretagne Atlantique, Confidentialité, Intégrité, Disponibilité et Répartition ( CIDRE ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -SYSTÈMES LARGE ÉCHELLE ( IRISA-D1 ), Institut de Recherche en Informatique et Systèmes Aléatoires ( IRISA ), CentraleSupélec-Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -Télécom Bretagne-Institut National des Sciences Appliquées ( INSA ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -École normale supérieure - Rennes ( ENS Rennes ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Bretagne Sud ( UBS ) -CentraleSupélec-Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -Télécom Bretagne-Institut National des Sciences Appliquées ( INSA ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -École normale supérieure - Rennes ( ENS Rennes ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Bretagne Sud ( UBS ) -Institut de Recherche en Informatique et Systèmes Aléatoires ( IRISA ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -Télécom Bretagne-Institut National des Sciences Appliquées ( INSA ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -École normale supérieure - Rennes ( ENS Rennes ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Bretagne Sud ( UBS ) -Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -Télécom Bretagne-Institut National des Sciences Appliquées ( INSA ) -École normale supérieure - Rennes ( ENS Rennes ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Bretagne Sud ( UBS ), Institut de Recherche Mathématique de Rennes ( IRMAR ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ), Invariant Preserving SOlvers ( IPSO ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ) -Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique ( Inria ), Université de Nantes ( UN ), Dependability Interoperability and perfOrmance aNalYsiS Of networkS ( DIONYSOS ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES ( IRISA-D2 ), ANR-11-INSE-010,AMORES, SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Anceaume, Emmanuelle, and ANR-11-LABX-0020,LEBESGUE,Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation(2011)

Subjects
[ INFO ] Computer Science [cs], Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], asynchronous message-passing system, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, [INFO] Computer Science [cs], Test-and-set, 01 natural sciences, randomized algorithm, Set (abstract data type), [ INFO.INFO-DC ] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Synchronization (computer science), [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Shared memory model, crash failures, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], agreement problem, Message passing, 020207 software engineering, Object (computer science), [ INFO.INFO-GT ] Computer Science [cs]/Computer Science and Game Theory [cs.GT], Memory management, 010201 computation theory & mathematics, Asynchronous communication, Test set, [INFO.INFO-GT] Computer Science [cs]/Computer Science and Game Theory [cs.GT], Test&Set, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], synchronization
Abstract

—This paper presents a solution to the well-known Test&Set operation in an asynchronous system prone to process crashes. Test&Set is a synchronization operation that, when invoked by a set of processes, returns yes to a unique process and returns no to all the others. Recently many advances in implementing Test&Set objects have been achieved, however all of them uniquely target the shared memory model. In this paper we propose an implementation of a Test&Set object for a message passing distributed system. This implementation can be invoked by any number p

Published
2015

9. Performance Analysis and Tuning for Parallelization of Ant Colony Optimization by Using OpenMP

Author

Ashraf Gamal Elbialy, Walid Mohamed Aly, Ahmed A. Abouelfarag, Arab Academy for Science, Technology and Maritime Transport [Alexandria] (AASTMT), Khalid Saeed, Władysław Homenda, and TC 8

Subjects
Soft computing, Speedup, Shared memory model, Computer science, Ant colony optimization algorithms, [SHS.INFO]Humanities and Social Sciences/Library and information sciences, MathematicsofComputing_NUMERICALANALYSIS, Parallel computing, Parallel metaheuristic, Travelling salesman problem, Swarm intelligence, ComputingMethodologies_ARTIFICIALINTELLIGENCE, Scheduling (computing), Ant colony optimization, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Openmp, [INFO]Computer Science [cs], Parallel threads, Metaheuristic
Abstract

Part 2: Algorithms; International audience; Ant colony optimization algorithm (ACO) is a soft computing metaheuristic that belongs to swarm intelligence methods. ACO has proven a well performance in solving certain NP-hard problems in polynomial time. This paper proposes the analysis, design and implementation of ACO as a parallel metaheuristics using the OpenMP framework. To improve the efficiency of ACO parallelization, different related aspects are examined, including scheduling of threads, race hazards and efficient tuning of the effective number of threads. A case study of solving the traveling salesman problem (TSP) using different configurations is presented to evaluate the performance of the proposed approach. Experimental results show a significant speedup in execution time for more than 3 times over the sequential implementation.

Published
2015

10. Test-and-Set in Optimal Space

Author

George Giakkoupis, Maryam Helmi, Philipp Woelfel, Lisa Higham, As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Department of Computer Science [Calgary] (CPSC), University of Calgary, Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)

Subjects
Computer science, 020207 software engineering, 0102 computer and information sciences, 02 engineering and technology, Test-and-set, Binary logarithm, Object (computer science), 01 natural sciences, Upper and lower bounds, Combinatorics, Shared memory, Space Complexity, Obstruction-free, 010201 computation theory & mathematics, Asynchronous communication, Test-and-Set Algorithm, Core (graph theory), Synchronization (computer science), 0202 electrical engineering, electronic engineering, information engineering, Shared Memory Model, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

International audience; The test-and-set object is a fundamental synchronization primitive for shared memory systems. This paper addresses the number of registers (supporting atomic reads and writes) required to implement a one-shot test-and-set object in the standard asynchronous shared memory model with n processes. The best lower bound is log n − 1 for obstruction-free and deadlock-free implementations, and recently a deterministic obstruction-free implementation using O(√ n) registers was presented. This paper closes the gap between these existing upper and lower bounds by presenting a deterministic obstruction-free implementation of a one-shot test-and-set object from Θ(log n) registers of size Θ(log n) bits. Combining our obstruction-free algorithm with techniques from previous research, we also obtain a randomized wait-free test-and-set algorithm from Θ(log n) registers, with expected step-complexity Θ(log* n) against the oblivious adversary. The core tool in our algorithm is the implementation of a deterministic obstruction-free sifter object, using only 6 registers. If k processes access a sifter, then when they have terminated, at least one and at most (2k + 1)/3 processes return "win" and all others return "lose" .

Published
2015

11. Optimizing Collective Operations in Hybrid Applications

Author

Patrick Carribault, Marc Pérache, William Jalby, Aurèle Mahéo, Laboratoire d'Informatique Parallélisme Réseaux Algorithmes Distribués (LI-PaRAD), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ), Parallélisme, Réseaux, Systèmes, Modélisation (PRISM), Centre National de la Recherche Scientifique (CNRS)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ), DAM Île-de-France (DAM/DIF), Direction des Applications Militaires (DAM), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), and Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Multi-core processor, Shared memory model, Computer science, Factor (programming language), Context (language use), [INFO]Computer Science [cs], Parallel computing, Software_PROGRAMMINGTECHNIQUES, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], computer, SPMD, ComputingMilieux_MISCELLANEOUS, computer.programming_language
Abstract

The advent of multicore and manycore processors in clusters advocates for combining MPI with a shared memory model like OpenMP in high-performance parallel applications. But exploiting hardware resources with such models can be sub optimal. Thus, one approach is to use the hybrid context to perform MPI communications. In this paper, we address this issue with a concept of hybrid collective communications, which consists in using OpenMP threads to parallelize MPI collectives. We validate our approach on several MPI libraries (IntelMPI and MPC), improving the overall time up to a factor of 5.29×, in a real world application.

Published
2014

12. Design of a shared-memory model for CAPE

Author

Eric Renault, Viet Hai Ha, Département Réseaux et Services Multimédia Mobiles (RS2M), Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP), Services répartis, Architectures, MOdélisation, Validation, Administration des Réseaux (SAMOVAR), Centre National de la Recherche Scientifique (CNRS), Réseaux, Systèmes, Services, Sécurité (R3S-SAMOVAR), and Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP)-Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP)

Subjects
Improved performance, Shared memory model, Programming language, Computer science, Release consistency, Parallel computing, Thread (computing), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], computer.software_genre, computer
Abstract

International audience; Checkpointing Aided Parallel Execution (CAPE) is the paradigm we developed to use checkpointing techniques to automatically run parallel programs on distributed-memory architectures. Two versions of CAPE have been developed and tested. The first one was based on complete checkpoints and has proved the feasibility of the paradigm but did not have good performance [1]. The second one based on incremental checkpoints improved performance a lot and made it comparable with MPI similar programs [2]. However, both versions are applicable only to problems containing parallel regions that verify the Bernstein's conditions. In this case data in parallel regions are processed independently in each parallel thread and result are combined at the end of each region. To overcome this restriction, two main tracks have been investigated: the first one consists in implementing a shared-memory model and the second one in processing all requirements of OpenMP data-sharing clauses and directives. In this paper, we present the design of a shared-memory model based on the Home-based Lazy Release Consistency model and the algorithm to implement it

Published
2012

13. The Multiplicative Power of Consensus Numbers

Author

Damien Imbs, Michel Raynal, As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), and Frey, Davide

Subjects
Reduction (recursion theory), ACM: C.: Computer Systems Organization/C.1: PROCESSOR ARCHITECTURES, Value (computer science), 0102 computer and information sciences, 02 engineering and technology, k-Set agreement, Shared memory system, 01 natural sciences, Upper and lower bounds, Consensus number, Synchronization power, Distributed computability, t-Resilience, System model, 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, Asynchronous processes, Mathematics, Discrete mathematics, Shared memory model, Fault-Tolerance, Multiplicative function, Process (computing), Waitfreedom, Process crash failure, 020207 software engineering, Base (topology), Power (physics), 010201 computation theory & mathematics, [INFO.INFO-OS]Computer Science [cs]/Operating Systems [cs.OS], BG simulation, Algorithm, Reduction algorithm
Abstract

The Borowsky-Gafni (BG) simulation algorithm is a powerful reduction algorithm that shows that t-resilience of decision tasks can be fully characterized in terms of wait-freedom. Said in another way, the BG simulation shows that the crucial parameter is not the number n of processes but the upper bound t on the number of processes that are allowed to crash. The BG algorithm considers colorless decision tasks in the base read/write shared memory model. (Colorless means that if, process decides a value, any other process is allowed to decide the very same value.) This paper considers system models made up of n processes prone to up to t crashes, and where the processes communicate by accessing read/write atomic registers (as assumed by the BG) and (differently from the BG) objects with consensus number x accessible by at most x processes (with x ≤ t n). Let ASM(n,t,x) denote such a system model. While the BG simulation has shown that the models ASM(n,t,1) and ASM(t+1,t,1) are equivalent, this paper focuses the pair (t,x) of parameters of a system model. Its main result is the following: the system models ASM (n1,t1,x1) and ASM (n2,t2,x2) have the same computational power for colorless decision tasks if and only if ⌊t1⁄x1⌋ = ⌊t1⁄x1⌋. As can be seen, this contribution complements and extends the BG simulation. It shows that consensus numbers have a multiplicative power with respect to failures, namely the system models ASM(n,t',x) and ASM(n,t,1) are equivalent for colorless decision tasks iff (t x x) ≤ t' ≤ (t x x)+(x-1).

Published
2010

14. The Disagreement Power of an Adversary

Author

Carole Delporte-Gallet, Andreas Tielmann, Hugues Fauconnier, Rachid Guerraoui, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Ecole Polytechnique Fédérale de Lausanne (EPFL), Distributed Programming Laboratory (LPD), and Tielmann, Andreas

Subjects
Computer Networks and Communications, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Crash, ComputerApplications_COMPUTERSINOTHERSYSTEMS, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, distributed computing, 0202 electrical engineering, electronic engineering, information engineering, Failure detector, Mathematics, Discrete mathematics, Shared memory model, 020206 networking & telecommunications, Adversary, Power (physics), Computational Theory and Mathematics, Hardware and Architecture, 010201 computation theory & mathematics, Asynchronous communication, Theory of computation, 020201 artificial intelligence & image processing, Algorithm, Adversary model, Integer (computer science)
Abstract

At the heart of distributed computing lies the fundamental result that the level of agreement that can be obtained in an asynchronous shared memory model where $t$ processes can crash is exactly $t+1$. In other words, an adversary that can crash any subset of size at most $t$ can prevent the processes from agreeing on $t$ values. But what about the rest ($2^{2^n} -n$) adversaries that might crash certain combination of processes and not others? Given any adversary, what is its disagreement power? i.e., the biggest $k$ for which it can prevent processes from agreeing on $k$ values. This paper answers this question. We present a general characterization of adversaries that enables to directly derive their disagreement power. We use our characterization to also close the question of the weakest failure detector for $k$-set agreement. So far, the result has been obtained for two extreme cases: consensus and $n-1$-set agreement. We answer this question for any $k$ and any adversary.

Published
2009

Catalog

Books, media, physical & digital resources
See catalog results