Change search
Refine search result
1 - 10 of 10
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the 'Create feeds' function.
  • 1.
    Atalar, Aras
    et al.
    Chalmers University of Technology.
    Gidenstam, Anders
    University of Borås, Faculty of Librarianship, Information, Education and IT.
    Renaud-Goud, Paul
    Chalmers University of Technology.
    Tsigas, Philippas
    Chalmers University of Technology.
    Modeling Energy Consumption of Lock-Free Queue Implementations2015In: 2015 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015, Hyderabad, India, May 25-29, 2015, IEEE Computer Society, 2015, p. 229-238Conference paper (Refereed)
    Abstract [en]

    This paper considers the problem of modelling the energy behaviour of lock-free concurrent queue data structures. Our main contribution is a way to model the energy behaviour of lock-free queue implementations and parallel applications that use them. Focusing on steady state behaviour we decompose energy behaviour into throughput and power dissipation which can be modeled separately and later recombined into several useful metrics, such as energy per operation. Based on our models, instantiated from synthetic benchmark data, and using only a small amount of additional application specific information, energy and throughput predictions can be made for parallel applications that use the respective data structure implementation. To model throughput we propose a generic model forlock-free queue throughput behaviour, based on combination of the dequeuers' throughput and enqueuers' throughput. To model power dissipation we commonly split the contributions from the various computer components into static, activation and dynamic parts, where only the dynamic part depends on the actual instructions being executed. To instantiate the models a synthetic benchmark explores each queue implementation over the dimensions of processor frequency and number of threads. Finally, we show how to make predictions of application throughput and power dissipation for a parallel application using lock-free queue requiring only a limited amount of information about the application work done between queue operations. Our case study on a Mandelbrot application shows convincing prediction results.

  • 2.
    Gidenstam, Anders
    et al.
    University of Borås, School of Business and IT.
    Koldehofe, Boris
    Papatriantafilou, Marina
    Tsigas, Philippas
    Scalable group communication supporting configurable levels of consistency2013In: Concurrency and Computation, ISSN 1532-0626, Vol. 25, no 5, p. 649-671Article in journal (Refereed)
    Abstract [en]

    Group communication is deployed in many evolving Internet-scale cooperative applications such as multiplayer online games and virtual worlds to efficiently support interaction on information relevant to a potentially very large number of users or objects. Especially peer-to-peer based group communication protocols have evolved as a promising approach to allow intercommunication between many distributed peers. Yet, the delivery semantics of robust and scalable protocols such as gossiping is not sufficient to support consistency semantics beyond eventual consistency because no relationship on the order of events is enforced. On the other hand, traditional consistency models provided by reliable group communication providing causal or even total order are restricted to support only small groups. This article proposes the cluster consistency model which bridges the gap between traditional and current approaches in supporting both scalability and ordered event delivery. We introduce a dynamic and fault tolerant cluster management method that can coordinate concurrent access to resources in a peer-to-peer system and can be used to establish fault-tolerant configurable cluster consistency with predictable reliability, running on top of decentralised probabilistic protocols supporting scalable group communication. This is achieved by a general two-layered architecture that can be applied on top of the standard Internet communication layers and offers a modular, layered set of services to the applications that need them. Further, we present a fault-tolerant method implementing causal cluster consistency with predictable reliability, running on top of decentralised probabilistic protocols supporting group communication. This paper provides analytical and experimental evaluation of the properties regarding the fault tolerance of the approach. Furthermore, our experimental study, conducted by implementing and evaluating the two-layered architecture on top of standard Internet transport services, shows that the approach scales well, imposes an even load on the system, and provides high-probability reliability guarantees.

  • 3.
    Gidenstam, Anders
    et al.
    University of Borås, School of Business and IT.
    Papatriantafilou, Marina
    LFTHREADS: a lock-free thread library2008In: SIGARCH Computer Architecture News, Association for Computing Machinery, Inc. , 2008, Vol. 4878, p. 88-92Conference paper (Refereed)
    Abstract [en]

    This extended abstract presents LFTHREADS, a thread library entirely based on lock-free methods, i.e. no spinlocks or similar synchronization mechanisms are employed in the implementation of the multithreading. Since lockfreedom is highly desirable in multiprocessors/multicores due to its advantages in parallelism, fault-tolerance, convoy-avoidance and more, there is an increased demand in lock-free methods in parallel applications, hence also in multiprocessor/multicore system services. LFTHREADS is the first thread library that provides a lock-free implementation of blocking synchronization primitives for application threads; although the latter may sound like a contradicting goal, such objects have several benefits: e.g. library operations that block and unblock threads on the same synchronization object can make progress in parallel while maintaining the desired thread-level semantics and without having to wait for any "low" operations among them. Besides, as no spin-locks or similar synchronization mechanisms are employed, memory contention can be reduced and processors/cores are able to do useful work. As a consequence, applications, too, can enjoy enhanced parallelism and fault-tolerance. For the synchronization in LFTHREADS we have introduced a new method, which we call responsibility hand-off (RHO), that does not need any special kernel support. The RHO method is also of independent interest, as it can also serve as a tool for lock-free token passing, management of contention and interaction between scheduling and synchronization. This paper gives an outline and the context of LFTHREADS. For more details the reader is refered to [7] and [8].

  • 4.
    Gidenstam, Anders
    et al.
    University of Borås, School of Business and IT.
    Papatriantafilou, Marina
    Sundell, Håkan
    University of Borås, School of Business and IT.
    Tsigas, Philippas
    Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting2009In: IEEE Transactions on Parallel and Distributed Systems, ISSN 1045-9219, E-ISSN 1558-2183, Vol. 20, no 8, p. 1173-1187Article in journal (Refereed)
    Abstract [en]

    We present an efficient and practical lock-free method for semiautomatic (application-guided) memory reclamation based on reference counting, aimed for use with arbitrary lock-free dynamic data structures. The method guarantees the safety of local as well as global references, supports arbitrary memory reuse, uses atomic primitives that are available in modern computer systems, and provides an upper bound on the amount of memory waiting to be reclaimed. To the best of our knowledge, this is the first lock-free method that provides all of these properties. We provide analytical and experimental study of the method. The experiments conducted have shown that the method can also provide significant performance improvements for lock-free algorithms of dynamic data structures that require strong memory management.

  • 5.
    Gidenstam, Anders
    et al.
    University of Borås, School of Business and IT.
    Papatriantafilou, Marina
    Tsigas, Philippas
    NBmalloc: Allocating Memory in a Lock-Free Manner2010In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 58, no 2, p. 304-338Article in journal (Refereed)
    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.

  • 6.
    Gidenstam, Anders
    et al.
    University of Borås, School of Business and IT.
    Sundell, Håkan
    University of Borås, School of Business and IT.
    Tsigas, Philippas
    Cache-Aware Lock-Free Queues for Multiple Producers/Consumers and Weak Memory Consistency2010In: Proceedings of the 14th International Conference on Principles of Distributed Systems (OPODIS) 2010 / [ed] Chenyang Lu, Toshimitsu Masuzawa, Mohamed Mosbah, Springer , 2010, p. 302-317Conference paper (Refereed)
    Abstract [en]

    A lock-free FIFO queue data structure is presented in this paper. The algorithm supports multiple producers and multiple consumers and weak memory models. It has been designed to be cache-aware and work directly on weak memory models. It utilizes the cache behavior in concert with lazy updates of shared data, and a dynamic lock-free memory management scheme to decrease unnecessary synchronization and increase performance. Experiments on an 8-way multi-core platform show significantly better performance for the new algorithm compared to previous fast lock-free algorithms.

  • 7. Larsson, Andreas
    et al.
    Gidenstam, Anders
    University of Borås, School of Business and IT.
    Ha, Phuong H.
    Papatriantafilou, Marina
    Tsigas, Philippas
    Multiword atomic read/write registers on multiprocessor systems2009In: ACM Journal of Experimental Algorithmics, ISSN 1084-6654, E-ISSN 1084-6654, Vol. 13, no 1, p. 1.7-1.30Article in journal (Refereed)
    Abstract [en]

    Modern multiprocessor systems offer advanced synchronization primitives, built in hardware, to support the development of efficient parallel algorithms. In this article, we develop a simple and efficient algorithm, the READERSFIELD algorithm, for atomic registers (variables) of arbitrary length. The simplicity and better complexity of the algorithm is achieved via the utilization of two such common synchronization primitives. In this article, we also experimentally evaluate the performance of our algorithm, together with lock-based approaches and a practical, previously previously known algorithm that is based that is based only on read and write primitives. The experimental evaluation is performed on three well-known parallel architectures. This evaluation clearly shows that both algorithms are practical and that as the size of the register increases the READERSFIELD algorithm performs better, following its analytical evaluation.

  • 8. Nikolakopoulos, Yiannis
    et al.
    Gidenstam, Anders
    University of Borås, School of Business and IT.
    Papatriantafilou, Marina
    Tsigas, Philippas
    Enhancing Concurrent Data Structures with Concurrent Iteration Operations: Consistency Framework and Trade-offs2014Conference paper (Refereed)
    Abstract [en]

    Concurrent data structures provide the means to multi-threaded applications to share data. Data structures come with a set of predefined operations, specified by the semantics of the data structure. In the literature and in several contemporary commonly used programming environments, the notion of iteration has been introduced for collection data structures, as a bulk operation enhancing the native set of operations. Iterations in several of these contexts have been treated as sequential in nature and may provide weak consistency guarantees when running concurrently with the native operations of the data structures. In this work we study iterations in concurrent data structures in the context of concurrency with the native operations and the guarantees that they provide. Besides linearizability, we propose a set of consistency specifications for such bulk operations, including also concurrency-aware properties by building on Lamport’s systematic definitions for registers. Furthermore, by using queues and composite registers as case-studies of underlying objects, we provide a set of constructions of iteration operations, satisfying the properties and showing containment relations. Besides the trade-off between consistency and throughput, we demonstrate the trade-off between the overhead of the bulk operation and possible support (helping) by the native operations of the data structure. We describe a set of algorithms that demonstrate these and study the implications on the efficiency of the implementations.

  • 9.
    Nikolakopoulos, Yiannis
    et al.
    Chalmers University of Technology.
    Gidenstam, Anders
    University of Borås, Faculty of Librarianship, Information, Education and IT.
    Papatriantafilou, Marina
    Chalmers University of Technology.
    Tsigas, Philippas
    Chalmers University of Technology.
    Of Concurrent Data Structures and Iterations2015In: Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday / [ed] Christos D. Zaroliagis and Grammati E. Pantziou and Spyros C. Kontogiannis, Springer Berlin/Heidelberg, 2015, Vol. 9295, p. 358-369Chapter in book (Refereed)
    Abstract [en]

    Bulk operations on data structures are widely used both on user-level but also on programming language level. Iterations are a good example of such bulk operations. In the sequential setting iterations are easy to design on top of an algorithmic construction of a data structure and is not considered as a challenge. In a concurrent environment, such as a multicore system, the situation is completely different and the issue of extending concurrent data structure designs to support iteration operations opens new research challenges in concurrent algorithmic data structure implementations, with respect to consistency and efficiency. In this paper we take a journey through this young and evolving research topic. More precisely we describe recent advances in the area together with an overview of iteration implementations that have appeared in the research literature as well as in widely-used programming environments and we outline a range of application targets and challenging future directions.

  • 10.
    Sundell, Håkan
    et al.
    University of Borås, School of Business and IT.
    Gidenstam, Anders
    University of Borås, School of Business and IT.
    Papatriantafilou, Marina
    Tsigas, Philippas
    A Lock-Free Algorithm for Concurrent Bags2011Conference paper (Refereed)
    Abstract [en]

    A lock-free bag data structure supporting unordered buffering is presented in this paper. The algorithm supports multiple producers and multiple consumers, as well as dynamic collection sizes. To handle concurrency efficiently, the algorithm was designed to thrive for disjoint-access-parallelism for the supported semantics. Therefore, the algorithm exploits a distributed design combined with novel techniques for handling concurrent modifications of linked lists using double marks, detection of total emptiness, and efficient memory management with hazard pointer handover. Experiments on a 24-way multi-core platform show significantly better performance for the new algorithm compared to previous algorithms of relevance.

1 - 10 of 10
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf