| 1. |
- Sundell, Håkan, 1968, et al.
(author)
-
NOBLE: non-blocking programming support via lock-free shared abstract data types
- 2009
-
In: SIGARCH Computer Architecture News. - : ACM, Association for Computing Machinery, Inc.. - 0163-5964 .- 1943-5851. ; 36:5, s. 80-87
-
Journal article (peer-reviewed)abstract
- An essential part of programming for multi-core and multi-processor includes ef cient and reliable means for sharing data. Lock-free data structures are known as very suitable for this purpose, although experienced to be very complex to design. In this paper, we present a software library of non-blocking abstract data types that have been designed to facilitate lock-free programming for non-experts. The system provides: i) ef cient implementations of the most commonly used data types in concurrent and sequential software design, ii) a lock-free memory management system, and iii) a run time-system. The library provides clear semantics that are at least as strong as those of corresponding lock-based implementations of the respective data types. Our software library can be used for facilitating lockfree programming; its design enables the programmer to: i) replace lock-based components of sequential or parallel code easily and ef ciently , ii) use well-tuned concurrent algorithms inside a software or hardware transactional system. In the paper we describe the design and functionality of the system. We also provide experimental results that show that the library can considerably improve the performance of software systems.
|
|
| 2. |
- Elmqvist, Niklas, 1977, et al.
(author)
-
Employing Dynamic Transparency for 3D Occlusion Management: Design Issues and Evaluation
- 2007
-
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - 1611-3349 .- 0302-9743. - 9783540747949 ; 4662, s. 532 - 545
-
Conference paper (peer-reviewed)abstract
- Recent developments in occlusion management for 3D environments often involve the use of dynamic transparency, or virtual “X-ray vision”, to promote target discovery and access in complex 3D worlds. However, there are many different approaches to achieving this effect and their actual utility for the user has yet to be evaluated. Furthermore, the introduction of semi-transparent surfaces adds additional visual complexity that may actually have a negative impact on task performance. In this paper, we report on an empirical user study comparing dynamic transparency to standard viewpoint controls. Our implementation of the technique is an image-space algorithm built using modern programmable shaders to achieve real-time performance and visually pleasing results. Results from the user study indicate that dynamic transparency is superior for perceptual tasks in terms of both efficiency and correctness.
|
|
| 3. |
- Casado, Lander, 1985, et al.
(author)
-
ContikiSec: A Secure Network Layer for Wireless Sensor Networks under the Contiki Operating System
- 2009
-
In: Proceedings of the 14th Nordic Conference on Secure IT Systems (NordSec 2009), Lecture Notes in Computer Science. - 1611-3349. - 9783642047657 ; 5838, s. 133 - 147
-
Conference paper (peer-reviewed)abstract
- In this paper we introduce ContikiSec, a secure network layer forwireless sensor networks, designed for the Contiki Operating System. ContikiSechas a configurable design, providing three security modes starting fromconfidentiality and integrity, and expanding to confidentiality, authentication,and integrity. ContikiSec has been designed to balance low energy consumptionand security while conforming to a small memory footprint. Our design wasbased on performance evaluation of existing security primitives and is part ofthe contribution of this paper. Our evaluation was performed in the ModularSensor Board hardware platform for wireless sensor networks, running Contiki.Contiki is an open source, highly portable operating system for wireless sensornetworks (WSN) that is widely used in WSNs.
|
|
| 4. |
- Ha, Phuong, 1976, et al.
(author)
-
The Synchronization Power of Coalesced Memory Accesses
- 2008
-
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783540877783 ; 5218, s. 320-334
-
Conference paper (peer-reviewed)abstract
- Multicore processor architectures have established themselves as the new generation of processor architectures. As part of the one core to many cores evolution, memory access mechanisms have advanced rapidly. Several new memory access mechanisms have been implemented in many modern commodity multicore processors. Memory access mechanisms, by devising how processing cores access the shared memory, directly influence the synchronization capabilities of the multicore processors. Therefore, it is crucial to investigate the synchronization power of these new memory access mechanisms.This paper investigates the synchronization power of coalesced memory accesses, a family of memory access mechanisms introduced in recent large multicore architectures like the CUDA graphics processors. We first design three memory access models to capture the fundamental features of the new memory access mechanisms. Subsequently, we prove the exact synchronization power of these models in terms of their consensus numbers. These tight results show that the coalesced memory access mechanisms can facilitate strong synchronization between the threads of multicore processors, without the need of synchronization primitives other than reads and writes. In the case of the contemporary CUDA processors, our results imply that the coalesced memory access mechanisms have consensus numbers up to sixteen.
|
|
| 5. |
- Ha, Phuong, 1976, et al.
(author)
-
Wait-free Programming for General Purpose Computations on Graphics Processors
- 2008
-
In: the Proceedings of the 22th International Parallel and Distributed Symposium (IPDPS 2008). - 1530-2075. - 9781424416936 ; , s. 1-12
-
Conference paper (peer-reviewed)abstract
- The fact that graphics processors (GPUs) are today’s most powerful computational hardware for the dollar has motivated researchers to utilize the ubiquitous and powerful GPUs for general-purpose computing. Recent GPUs feature the single-program multiple-data (SPMD) multicore architecture instead of the single-instruction multiple-data (SIMD). However, unlike CPUs, GPUs devote their transistors mainly to data processing rather than data caching and flow control, and consequently most of the powerful GPUs with many cores do not support any synchronization mechanisms between their cores. This prevents GPUs from being deployed more widely for general-purpose computing. This paper aims at bridging the gap between the lack of synchronization mechanisms in recent GPU architectures and the need of synchronization mechanisms in parallel applications. Based on the intrinsic features of recent GPU architectures, we construct strong synchronization objects like wait-free and t-resilient read-modify-write objects for a general model of recent GPU architectures without strong hardware synchronization primitives like test-and-set and compare-and-swap. Accesses to the wait-free objects have time complexity O(N), whether N is the number of processes. Our result demonstrates that it is possible to construct wait-free synchronization mechanisms for GPUs without the need of strong synchronization primitives in hardware and that wait-free programming is possible for GPUs.
|
|
| 6. |
- Elmqvist, Niklas, 1977, et al.
(author)
-
CiteWiz: a tool for the visualization of scientific citation networks
- 2007
-
In: Information Visualization. - 1473-8716 .- 1473-8724. ; 6:3, s. 215-232
-
Journal article (peer-reviewed)abstract
- We present CiteWiz, an extensible framework for visualization of scientific citation networks. The system is based on a taxonomy of citation database usage for researchers, and provides a timeline visualization for overviews and an influence visualization for detailed views. The timeline displays the general chronology and importance of authors and articles in a citation database, whereas the influence visualization is implemented using the Growing Polygons technique, suitably modified to the context of browsing citation data. Using the latter technique, hierarchies of articles with potentially very long citation chains can be graphically represented. The visualization is augmented with mechanisms for parent–child visualization and suitable interaction techniques for interacting with the view hierarchy and the individual articles in the dataset. We also provide an interactive concept map for keywords and co-authorship using a basic force-directed graph layout scheme. A formal user study indicates that CiteWiz is significantly more efficient than traditional database interfaces for high-level analysis tasks relating to influence and overviews, and equally efficient for low-level tasks such as finding a paper and correlating bibliographical data.
|
|
| 7. |
- Elmqvist, Niklas, 1977, et al.
(author)
-
DataMeadow: a visual canvas for analysis of large-scale multivariate data
- 2008
-
In: Information Visualization. - : SAGE Publications. - 1473-8716 .- 1473-8724. ; 7:1, s. 18-33
-
Journal article (peer-reviewed)abstract
- Supporting visual analytics of multiple large-scale multidimensional data sets requires a high degree of interactivity and user control beyond the conventional challenges of visualizing such data sets. We present the DataMeadow, a visual canvas providing rich interaction for constructing visual queries using graphical set representations called DataRoses. A DataRose is essentially a starplot of selected columns in a data set displayed as multivariate visualizations with dynamic query sliders integrated into each axis. The purpose of the DataMeadow is to allow users to create advanced visual queries by iteratively selecting and filtering into the multidimensional data. Furthermore, the canvas provides a clear history of the analysis that can be annotated to facilitate dissemination of analytical results to stakeholders. A powerful direct manipulation interface allows for selection, filtering, and creation of sets, subsets, and data dependencies. We have evaluated our system using a qualitative expert review involving two visualization researchers. Results from this review are favorable for the new method.
|
|
| 8. |
- Rukundo, Adones, 1986, et al.
(author)
-
Monotonically relaxing concurrent data-structure semantics for increasing performance: An efficient 2D design framework
- 2019
-
In: Leibniz International Proceedings in Informatics, LIPIcs. - 1868-8969. ; 146
-
Conference paper (peer-reviewed)abstract
- There has been a significant amount of work in the literature proposing semantic relaxation of concurrent data structures for improving scalability and performance. By relaxing the semantics of a data structure, a bigger design space, that allows weaker synchronization and more useful parallelism, is unveiled. Investigating new data structure designs, capable of trading semantics for achieving better performance in a monotonic way, is a major challenge in the area. We algorithmically address this challenge in this paper. We present an efficient, lock-free, concurrent data structure design framework for out-of-order semantic relaxation. We introduce a new two dimensional algorithmic design, that uses multiple instances of a given data structure. The first dimension of our design is the number of data structure instances operations are spread to, in order to benefit from parallelism through disjoint memory access; the second dimension is the number of consecutive operations that try to use the same data structure instance in order to benefit from data locality. Our design can flexibly explore this two-dimensional space to achieve the property of monotonically relaxing concurrent data structure semantics for better performance within a tight deterministic relaxation bound, as we prove in the paper. We show how our framework can instantiate lock-free out-of-order queues, stacks, counters and dequeues. We provide implementations of these relaxed data structures and evaluate their performance and behaviour on two parallel architectures. Experimental evaluation shows that our two-dimensional design significantly outperforms the respected previous proposed designs with respect to scalability and performance. Moreover, our design increases performance monotonically as relaxation increases.
|
|
| 9. |
- Gidenstam, Anders, et al.
(author)
-
Cache-Aware Lock-Free Queues for Multiple Producers/Consumers and Weak Memory Consistency
- 2010
-
In: Proceedings of the 14th International Conference on Principles of Distributed Systems (OPODIS) 2010. - Berlin, Heidelberg : Springer. - 9783642176524 - 3642176526 ; 6490, s. 302-317
-
Conference paper (peer-reviewed)abstract
- 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.
|
|
| 10. |
- Gidenstam, Anders, 1977, et al.
(author)
-
Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting
- 2009
-
In: IEEE Transactions on Parallel and Distributed Systems. - : IEEE. - 1558-2183 .- 1045-9219. ; 20:8, s. 1173-1187
-
Journal article (peer-reviewed)abstract
- 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.
|
|
