Change search
Link to record
Permanent link

Direct link
BETA
Gidenstam, Anders
Publications (10 of 11) Show all publications
Johansson, U., Löfström, T., Sundell, H., Linnusson, H., Gidenstam, A. & Boström, H. (2018). Venn predictors for well-calibrated probability estimation trees. In: Alex J. Gammerman and Vladimir Vovk and Zhiyuan Luo and Evgueni N. Smirnov and Ralf L. M. Peeter (Ed.), 7th Symposium on Conformal and Probabilistic Prediction and Applications: COPA 2018, 11-13 June 2018, Maastricht, The Netherlands. Paper presented at 7th Symposium on Conformal and Probabilistic Prediction and Applications, London, June 11th - 13th, 2018 (pp. 3-14).
Open this publication in new window or tab >>Venn predictors for well-calibrated probability estimation trees
Show others...
2018 (English)In: 7th Symposium on Conformal and Probabilistic Prediction and Applications: COPA 2018, 11-13 June 2018, Maastricht, The Netherlands / [ed] Alex J. Gammerman and Vladimir Vovk and Zhiyuan Luo and Evgueni N. Smirnov and Ralf L. M. Peeter, 2018, p. 3-14Conference paper, Published paper (Refereed)
Abstract [en]

Successful use of probabilistic classification requires well-calibrated probability estimates, i.e., the predicted class probabilities must correspond to the true probabilities. The standard solution is to employ an additional step, transforming the outputs from a classifier into probability estimates. In this paper, Venn predictors are compared to Platt scaling and isotonic regression, for the purpose of producing well-calibrated probabilistic predictions from decision trees. The empirical investigation, using 22 publicly available datasets, showed that the probability estimates from the Venn predictor were extremely well-calibrated. In fact, in a direct comparison using the accepted reliability metric, the Venn predictor estimates were the most exact on every data set.

Series
Proceedings of Machine Learning Research
Keywords
Venn predictors, Calibration, Decision trees, Reliability
National Category
Computer Sciences
Research subject
Business and IT
Identifiers
urn:nbn:se:hb:diva-15061 (URN)
Conference
7th Symposium on Conformal and Probabilistic Prediction and Applications, London, June 11th - 13th, 2018
Funder
Knowledge Foundation
Available from: 2018-09-04 Created: 2018-09-04 Last updated: 2018-09-06Bibliographically approved
Atalar, A., Gidenstam, A., Renaud-Goud, P. & Tsigas, P. (2015). Modeling Energy Consumption of Lock-Free Queue Implementations. In: 2015 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015, Hyderabad, India, May 25-29, 2015: . Paper presented at IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015 (pp. 229-238). IEEE Computer Society
Open this publication in new window or tab >>Modeling Energy Consumption of Lock-Free Queue Implementations
2015 (English)In: 2015 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015, Hyderabad, India, May 25-29, 2015, IEEE Computer Society, 2015, p. 229-238Conference paper, Published 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.

Place, publisher, year, edition, pages
IEEE Computer Society, 2015
Keywords
data structures, energy consumption, parallel processing, power aware computing, queueing theory
National Category
Computer Sciences
Identifiers
urn:nbn:se:hb:diva-5410 (URN)10.1109/IPDPS.2015.31 (DOI)
Conference
IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015
Projects
Execution Models For Energy-Efficient Computing Systems - EXCESS (European Union Seventh Framework Programme (FP7/2013-2016) under grant agreement 611183)
Funder
EU, FP7, Seventh Framework Programme, 611183
Available from: 2015-12-17 Created: 2015-12-17 Last updated: 2018-01-10Bibliographically approved
Nikolakopoulos, Y., Gidenstam, A., Papatriantafilou, M. & Tsigas, P. (2015). Of Concurrent Data Structures and Iterations. In: Christos D. Zaroliagis and Grammati E. Pantziou and Spyros C. Kontogiannis (Ed.), Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday (pp. 358-369). Springer Berlin/Heidelberg, 9295
Open this publication in new window or tab >>Of Concurrent Data Structures and Iterations
2015 (English)In: 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.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2015
Series
Lecture Notes in Computer Science ; 9295
Keywords
Iteration, Consistency, Lock-free Concurrent data structures, In-memory computation, Range-queries
National Category
Computer Sciences
Identifiers
urn:nbn:se:hb:diva-5409 (URN)10.1007/978-3-319-24024-4_20 (DOI)2-s2.0-84951869962 (Scopus ID)
Projects
Execution Models for Energy-Efficient Computing Systems - EXCESS (European Union Seventh Framework Programme (FP7/2013-2016) under grant agreement 611183)
Funder
EU, FP7, Seventh Framework Programme, 611183
Available from: 2015-12-17 Created: 2015-12-17 Last updated: 2018-01-10Bibliographically approved
Nikolakopoulos, Y., Gidenstam, A., Papatriantafilou, M. & Tsigas, P. (2014). Enhancing Concurrent Data Structures with Concurrent Iteration Operations: Consistency Framework and Trade-offs. In: : . Paper presented at MCC14: Seventh Swedish Workshop on Multicore Computing, Lund, Sweden, 27-28 November, 2014. Lunds Tekniska Högskola
Open this publication in new window or tab >>Enhancing Concurrent Data Structures with Concurrent Iteration Operations: Consistency Framework and Trade-offs
2014 (English)Conference paper, Published 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.

Place, publisher, year, edition, pages
Lunds Tekniska Högskola, 2014
Keywords
Datavetenskap
National Category
Computer Sciences
Identifiers
urn:nbn:se:hb:diva-7244 (URN)2320/14383 (Local ID)2320/14383 (Archive number)2320/14383 (OAI)
Conference
MCC14: Seventh Swedish Workshop on Multicore Computing, Lund, Sweden, 27-28 November, 2014
Available from: 2015-12-22 Created: 2015-12-22 Last updated: 2018-01-10Bibliographically approved
Gidenstam, A., Koldehofe, B., Papatriantafilou, M. & Tsigas, P. (2013). Scalable group communication supporting configurable levels of consistency. Concurrency and Computation, 25(5), 649-671
Open this publication in new window or tab >>Scalable group communication supporting configurable levels of consistency
2013 (English)In: Concurrency and Computation, ISSN 1532-0626, Vol. 25, no 5, p. 649-671Article in journal (Refereed) Published
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.

Place, publisher, year, edition, pages
John Wiley & Sons, Ltd., 2013
Keywords
Gossiping, Group communication, Optimistic causal order, Datavetenskap
National Category
Computer Sciences
Identifiers
urn:nbn:se:hb:diva-1580 (URN)10.1002/cpe.1801 (DOI)000316231200004 ()2320/12365 (Local ID)2320/12365 (Archive number)2320/12365 (OAI)
Note

Sponsorship:

Contract/grant sponsor: Publishing Arts Research Council; contract/grant number: 98–1846389

Available from: 2015-11-13 Created: 2015-11-13 Last updated: 2018-01-10Bibliographically approved
Sundell, H., Gidenstam, A., Papatriantafilou, M. & Tsigas, P. (2011). A Lock-Free Algorithm for Concurrent Bags. In: : . Paper presented at The 23rd Annual Symposium on Parallelism in Algorithms and Architectures, San Jose, June 4-6, 2011. ACM
Open this publication in new window or tab >>A Lock-Free Algorithm for Concurrent Bags
2011 (English)Conference paper, Published 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.

Place, publisher, year, edition, pages
ACM, 2011
Keywords
concurrent, data structure, non-blocking, shared memory, Parallel Programming
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:hb:diva-6575 (URN)10.1145/1989493.1989550 (DOI)2320/8255 (Local ID)978-1-4503-0743-7 (ISBN)2320/8255 (Archive number)2320/8255 (OAI)
Conference
The 23rd Annual Symposium on Parallelism in Algorithms and Architectures, San Jose, June 4-6, 2011
Available from: 2015-12-22 Created: 2015-12-22 Last updated: 2018-01-10Bibliographically approved
Gidenstam, A., Sundell, H. & Tsigas, P. (2010). Cache-Aware Lock-Free Queues for Multiple Producers/Consumers and Weak Memory Consistency. In: Chenyang Lu, Toshimitsu Masuzawa, Mohamed Mosbah (Ed.), Proceedings of the 14th International Conference on Principles of Distributed Systems (OPODIS) 2010: . Paper presented at International Conference on Principles of Distributed Systems (OPODIS) 2010 (pp. 302-317). Springer
Open this publication in new window or tab >>Cache-Aware Lock-Free Queues for Multiple Producers/Consumers and Weak Memory Consistency
2010 (English)In: 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, Published 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.

Place, publisher, year, edition, pages
Springer, 2010
Keywords
lock-free, data structure, synchronization, shared memory, queue, concurrent queue, fifo queue, Parallel Programming
National Category
Computer Sciences Computer and Information Sciences
Identifiers
urn:nbn:se:hb:diva-6460 (URN)10.1007/978-3-642-17653-1_23 (DOI)2320/7291 (Local ID)978-3-642-17652-4 (ISBN)3-642-17652-6 (ISBN)2320/7291 (Archive number)2320/7291 (OAI)
Conference
International Conference on Principles of Distributed Systems (OPODIS) 2010
Funder
Swedish Research Council for Environment, Agricultural Sciences and Spatial Planning, 37252706EU, FP7, Seventh Framework Programme, 248481
Note

Sponsorship:

This work was partially supported by the EU as part of FP7 Project PEPPHER (www.peppher.eu) under grant 248481 and the Swedish Research Council under grant number 37252706 and 13671-60582-29.

Available from: 2015-12-22 Created: 2015-12-22 Last updated: 2018-01-10Bibliographically approved
Gidenstam, A., Papatriantafilou, M. & Tsigas, P. (2010). NBmalloc: Allocating Memory in a Lock-Free Manner. Algorithmica, 58(2), 304-338
Open this publication in new window or tab >>NBmalloc: Allocating Memory in a Lock-Free Manner
2010 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 58, no 2, p. 304-338Article in journal (Refereed) 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.

Place, publisher, year, edition, pages
Springer New York LLC, 2010
Keywords
memory allocation, lock-free synchronisation, non-blocking synchronisation, multithreaded applications, Parallel Programming
National Category
Computer Sciences Computer and Information Sciences
Identifiers
urn:nbn:se:hb:diva-2741 (URN)10.1007/s00453-008-9268-x (DOI)2320/5970 (Local ID)2320/5970 (Archive number)2320/5970 (OAI)
Funder
National Supercomputer Centre (NSC), Sweden
Note

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).

Available from: 2015-11-13 Created: 2015-11-13 Last updated: 2018-01-10Bibliographically approved
Gidenstam, A., Papatriantafilou, M., Sundell, H. & Tsigas, P. (2009). Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting. IEEE Transactions on Parallel and Distributed Systems, 20(8), 1173-1187
Open this publication in new window or tab >>Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting
2009 (English)In: IEEE Transactions on Parallel and Distributed Systems, ISSN 1045-9219, E-ISSN 1558-2183, Vol. 20, no 8, p. 1173-1187Article in journal (Refereed) Published
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.

Place, publisher, year, edition, pages
IEEE, 2009
Keywords
memory management, memory reclamation, semiautomatic, garbage collection, data structure, lock-free, shared memory, Parallel Programming
National Category
Computer and Information Sciences Computer and Information Sciences
Identifiers
urn:nbn:se:hb:diva-2720 (URN)10.1109/TPDS.2008.167 (DOI)2320/5913 (Local ID)2320/5913 (Archive number)2320/5913 (OAI)
Available from: 2015-11-13 Created: 2015-11-13 Last updated: 2018-01-10Bibliographically approved
Larsson, A., Gidenstam, A., Ha, P. H., Papatriantafilou, M. & Tsigas, P. (2009). Multiword atomic read/write registers on multiprocessor systems. ACM Journal of Experimental Algorithmics, 13(1), 1.7-1.30
Open this publication in new window or tab >>Multiword atomic read/write registers on multiprocessor systems
Show others...
2009 (English)In: ACM Journal of Experimental Algorithmics, ISSN 1084-6654, E-ISSN 1084-6654, Vol. 13, no 1, p. 1.7-1.30Article in journal (Refereed) Published
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.

Place, publisher, year, edition, pages
Association for Computing Machinery, Inc., 2009
Keywords
atomic register, wait-free, synchronization, Parallel Programming
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:hb:diva-2722 (URN)10.1145/1412228.1455262 (DOI)2320/5920 (Local ID)2320/5920 (Archive number)2320/5920 (OAI)
Funder
National Supercomputer Centre (NSC), Sweden
Note

Sponsorship:

This work was supported by computational resources provided by the Swedish National Supercomputer

Centre (NSC).

Available from: 2015-11-13 Created: 2015-11-13 Last updated: 2018-01-10Bibliographically approved
Organisations

Search in DiVA

Show all publications