| 1. |
- Liu, Yuanhua, 1971, et al.
(författare)
-
Considering the importance of user profiles in interface design
- 2009
-
Ingår i: User Interfaces. ; , s. 23-
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)abstract
- User profile is a popular term widely employed during product design processes by industrial companies. Such a profile is normally intended to represent real users of a product. The ultimate purpose of a user profile is actually to help designers to recognize or learn about the real user by presenting them with a description of a real user’s attributes, for instance; the user’s gender, age, educational level, attitude, technical needs and skill level. The aim of this chapter is to provide information on the current knowledge and research about user profile issues, as well as to emphasize the importance of considering these issues in interface design. In this chapter, we mainly focus on how users’ difference in expertise affects their performance or activity in various interaction contexts. Considering the complex interaction situations in practice, novice and expert users’ interactions with medical user interfaces of different technical complexity will be analyzed as examples: one focuses on novice and expert users’ difference when interacting with simple medical interfaces, and the other focuses on differences when interacting with complex medical interfaces. Four issues will be analyzed and discussed: (1) how novice and expert users differ in terms of performance during the interaction; (2) how novice and expert users differ in the perspective of cognitive mental models during the interaction; (3) how novice and expert users should be defined in practice; and (4) what are the main differences between novice and expert users’ implications for interface design. Besides describing the effect of users’ expertise difference during the interface design process, we will also pinpoint some potential problems for the research on interface design, as well as some future challenges that academic researchers and industrial engineers should face in practice.
|
|
| 2. |
- Sundell, Håkan, 1968, et al.
(författare)
-
NOBLE: non-blocking programming support via lock-free shared abstract data types
- 2009
-
Ingår i: SIGARCH Computer Architecture News. - : ACM, Association for Computing Machinery, Inc.. - 0163-5964 .- 1943-5851. ; 36:5, s. 80-87
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 3. |
- Casado, Lander, 1985, et al.
(författare)
-
ContikiSec: A Secure Network Layer for Wireless Sensor Networks under the Contiki Operating System
- 2009
-
Ingår i: Proceedings of the 14th Nordic Conference on Secure IT Systems (NordSec 2009), Lecture Notes in Computer Science. - 1611-3349. - 9783642047657 ; 5838, s. 133 - 147
-
Konferensbidrag (refereegranskat)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.
(författare)
-
The Synchronization Power of Coalesced Memory Accesses
- 2008
-
Ingår i: 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
-
Konferensbidrag (refereegranskat)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.
(författare)
-
Wait-free Programming for General Purpose Computations on Graphics Processors
- 2008
-
Ingår i: the Proceedings of the 22th International Parallel and Distributed Symposium (IPDPS 2008). - 1530-2075. - 9781424416936 ; , s. 1-12
-
Konferensbidrag (refereegranskat)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.
(författare)
-
CiteWiz: a tool for the visualization of scientific citation networks
- 2007
-
Ingår i: Information Visualization. - 1473-8716 .- 1473-8724. ; 6:3, s. 215-232
-
Tidskriftsartikel (refereegranskat)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.
(författare)
-
DataMeadow: a visual canvas for analysis of large-scale multivariate data
- 2008
-
Ingår i: Information Visualization. - : SAGE Publications. - 1473-8716 .- 1473-8724. ; 7:1, s. 18-33
-
Tidskriftsartikel (refereegranskat)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. |
- Elmqvist, Niklas, 1977, et al.
(författare)
-
Employing Dynamic Transparency for 3D Occlusion Management: Design Issues and Evaluation
- 2007
-
Ingår i: 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
-
Konferensbidrag (refereegranskat)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.
|
|
| 9. |
- Falkman, Göran, 1968-, et al.
(författare)
-
SOMWeb - Towards an Infrastructure for Knowledge Sharing in Oral Medicine
- 2005
-
Ingår i: Connecting Medical Informatics and Bio-Informatics: Proceedings of MIE2005 - The XIXth International Congress of the European Federation for Medical Informatics. - Amsterdam : IOS Press. - 1586035495 ; 116, s. 527-32, s. 527-532
-
Konferensbidrag (refereegranskat)abstract
- In a net-based society, clinicians can come together for cooperative work and distance learning around a common medical material. This requires suitable techniques for cooperative knowledge management and user interfaces that are adapted to both the group as a whole and to individuals. To support distributed management and sharing of clinical knowledge, we propose the development of an intelligent web community for clinicians within oral medicine. This virtual meeting place will support the ongoing work on developing a digital knowledge base, providing a foundation for a more evidence-based oral medicine. The presented system is founded on the use and development of web services and standards for knowledge modelling and knowledge-based systems. The work is conducted within the frame of a well-established cooperation between oral medicine and computer science.
|
|
| 10. |
- Caporuscio, Mauro, 1975-, et al.
(författare)
-
ubiSOAP : A Service Oriented Middleware for Seamless Networking
- 2008
-
Ingår i: Service-Oriented Computing “ ICSOC 2008. - Berlin, Heidelberg : Springer. - 9783540896470 ; , s. 195-209
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)abstract
- The computing and networking capacities of today’s wireless portable devices allow for pervasive services, which are seamlessly networked. Indeed, wireless handheld devices now embed the necessary resources to act as both service clients and providers. However, the seamless networking of services remains challenged by the inherent mobility and resource constraints of devices, which make services a priori highly volatile. This paper discusses the design, implementation and experimentation of the ubiSOAP service-oriented middleware, which leverages wireless networking capacities to effectively enable the seamless networking of services. ubiSOAP specifically defines a layered communication middleware that underlies standard SOAP-based middleware, hence supporting legacy services while exploiting nowadays pervasive connectivity.
|
|
| 11. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting
- 2009
-
Ingår i: IEEE Transactions on Parallel and Distributed Systems. - : IEEE. - 1558-2183 .- 1045-9219. ; 20:8, s. 1173-1187
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 12. |
- Sundell, Håkan, 1968, et al.
(författare)
-
Brushing the Locks out of the Fur: A Lock-Free Work Stealing Library
- 2009
-
Ingår i: econd Swedish Workshop on Multi-Core Computing, (MCC '09).
-
Konferensbidrag (refereegranskat)abstract
- We present a lock-free version of the light-weight userleveltask management library called Wool, in an aim toshow that even extremely well tuned, in terms of synchronization,applications can benefit from lock-free programming.Explicit multi-threading is an efficient way to exploitthe offered parallelism of multi-core and multi-processorbased systems. However, it can sometimes be hard to expressthe inherited parallelism in programs using a limitednumber of long lived threads. Often it can be more straightforwardto dynamically create a large number of small tasksthat in turn automatically execute on the available threads.Wool is a promising and efficient library and frameworkthat allows the programmer to create user tasks in C witha very low overhead. The library automatically executestasks and balances the load evenly on a given number ofthreads by utilizing work stealing techniques. However, thesynchronization for stealing tasks is based on mutual exclusionwhich is known to limit parallelism and efficiency. Wehave designed and implemented a new lock-free algorithmfor synchronization of stealing tasks in Wool. Experimentsshow similar or significantly improved performance on a setof benchmarks executed on a multi-core platform.
|
|
| 13. |
- Barbosa, Raul, 1981, et al.
(författare)
-
Implementation of a Flexible Membership Protocol on a Real-Time Ethernet Prototype
- 2007
-
Ingår i: Procceding of PRDC 2007 IEEE 13th Pacific Rim International Symposium on Dependable Computing, Dec. 17-19, 2007, Melbourne, Australia. - 0769530540 ; , s. 342-347
-
Konferensbidrag (refereegranskat)abstract
- This paper describes the implementation of a processorgroup membership protocol in an experimental real-time network. The protocol is appropriate for fault-tolerant distributed systems using TDMA for scheduling messages. It allows nodes to maintain a consensus on the operational state of all nodes, in the presence of node failures and restarts, as well as network failures. The protocol is based on the principle that, in a system of n nodes, each node must acknowledge the messages from k other nodes in the membership group, where k can assume values between 2 and n 1. Membership agreement is guaranteed if f k 1 failures occur during n consecutive transmission slots. We have implemented the membership protocol in a time-triggered network based on COTS Ethernet hardware, programmed to schedule messages according to the TDMA method.
|
|
| 14. |
- Bergenhem, Carl, 1975, et al.
(författare)
-
A Process Group Membership Service for Active Safety Systems Using TT/ET Communication Scheduling
- 2007
-
Ingår i: Proceedings of PRDC 2007 IEEE 13th Pacific Rim International Symposium on Dependable Computing, Dec 17-19, 2007, Melbourne, Australia. - 0769530540 ; , s. 282-289
-
Konferensbidrag (refereegranskat)abstract
- This paper describes a process group membership protocol for distributed real-time systems, that use a communication network which supports both timetriggered (TT) and event-triggered (ET) communication. The protocol allows a group of cooperating real-time processes to establish a consistent view of each other's operational status, i.e. working correctly or not. The aim is to provide an application independent membership service in systems where several distributed real-time tasks share processing nodes. We assume that each such task consists of several processes executing on different nodes and that each node can execute processes belonging to different tasks. The protocol is applicable to any application domain, but has been developed for automotive active safety systems. Here, typical distributed real-time tasks include anti-lock braking, stability control and collision mitigation. In such systems, a membership service provides invaluable support for implementing fault-tolerance and graceful degradation.
|
|
| 15. |
- Bergenhem, Carl, 1975, et al.
(författare)
-
A Process Membership Service for Active Safety Systems
- 2007
-
Ingår i: SAE 2007 World Congress & Exhibition, April 16-19, Detroit, Michigan, USA. - 400 Commonwealth Drive, Warrendale, PA, United States : SAE International. - 0768016339 ; 2007
-
Konferensbidrag (refereegranskat)abstract
- This paper describes a process membership protocol for distributed real-time systems that use both time-triggered and event-triggered message passing for communication between its processing nodes (ECUs). TTCAN and FlexRay are examples of communication networks that support such systems. The membership protocol supports redundancy management in architectures where distributed applications such as braking, stability control, and collision mitigation share a common set of processing nodes. We assume that each such application consists of several processes executing on different nodes and that each node executes processes belonging to different applications. The protocol allows a group of cooperating processes to establish a consistent view of each other's operational status, i.e., whether they function correctly or not.
|
|
| 16. |
- Bergenhem, Carl, 1975, et al.
(författare)
-
Implementation Results of a Configurable Membership Protocol for Active Safety Systems
- 2006
-
Ingår i: Proceedings of PRDC 2006 IEEE 12th Pacfic Rim International Symposium on Dependable Computing, Dec 18-20, Riverside, California, USA. - 0769527248 ; , s. 387-388
-
Konferensbidrag (refereegranskat)abstract
- This paper describes a configurable membership protocol for distributed tasks in time-triggered systems that combine static and dynamic messages such as TTCAN or Flexray. The units of membership are processes in nodes that send messages in static communication slots. The objective is to give nodes a consistent view of the status of processes in the system. Process failures are assumed to be manifested as missing messages (fail-silent assumption). Whenever a node detects a change in the membership status of any process, it broadcasts its opinion about the membership status of all processes. This information is broadcast only by nodes that detect a change of local membership status. The protocol is implemented in a distributed embedded system with TTCAN-communication. The response-time of the protocol has been evaluated experimentally by means of fault injection
|
|
| 17. |
- Cederman, Daniel, 1981, et al.
(författare)
-
A Practical Quicksort Algorithm for Graphics Processors
- 2008
-
Ingår i: 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. ; 5193, s. 246-258
-
Konferensbidrag (refereegranskat)abstract
- In this paper we present GPU-Quicksort, an efficient Quicksort algorithm suitable for highly parallel multi-core graphics processors. Quicksort has previously been considered as an inefficient sorting solution for graphics processors, but we show that GPU-Quicksort often performs better than the fastest known sorting implementations for graphics processors, such as radix and bitonic sort. Quicksort can thus be seen as a viable alternative for sorting large quantities of data on graphics processors.
|
|
| 18. |
- Dolev, Shlomi, et al.
(författare)
-
Game Authority for Robust and Scalable Distributed Selfish Computer Systems
- 2007
-
Ingår i: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. - 9781595936165 ; , s. 356 - 357
-
Konferensbidrag (refereegranskat)abstract
- Game theory analyzes social structures of agents that have freedomof choice within a moral code. The society allows freedom andselfishness within the moral code, which social structures enforce,i.e., legislative, executive, and judicial. Social rules encourage individualprofit from which the entire society gains. Distributed computersystems can improve their scalability and robustness by usingexplicit social structures. We propose using a game authority middlewarefor enforcing the moral code on selfish agents.The power of game theory is in predicting the game outcome forspecific assumptions. The prediction holds as long as the playerscannot tamper with the social structure, or change the rules of thegame, i.e., the prisoner cannot escape from prison in the classicalprisoner dilemma. Therefore, we cannot predict the game outcomewithout suitable assumptions on failures and honest selfishness.
|
|
| 19. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
LFthreads: A lock-free thread library
- 2007
-
Ingår i: Proceedings of the 11th International Conference On Principles Of Distributed Systems, Lecture Notes in Computer Science Vol. 4878, Springer Verlag. - 9783540770954 ; , s. 217 - 231
-
Konferensbidrag (refereegranskat)
|
|
| 20. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
LFthreads: a lock-free thread library
- 2008
-
Ingår i: 1st Swedish Workshop on Multi-Core Computing. ; urn:nbn:se:bth-00422, s. 107-116
-
Konferensbidrag (refereegranskat)
|
|
| 21. |
- Ha, Phuong, 1976, et al.
(författare)
-
Brief Announcement: Wait-free Programming for General Purpose Computations on Graphics Processors
- 2008
-
Ingår i: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing. - 9781595939890 ; , s. 452-
-
Konferensbidrag (refereegranskat)abstract
- This paper aims at bridging the gap between the lack of synchronization mechanisms in recent graphics processor (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 new wait-free objects have time complexity O(N), where N is the number of concurrent processes. The wait-free objects have space complexity O(N2), which is optimal. 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.
|
|
| 22. |
- Ha, Phuong, 1976, et al.
(författare)
-
NB-FEB: A Universal Scalable Easy-to-Use Synchronization Primitive for Manycore Architectures
- 2009
-
Ingår i: Proceedings of the 13th International Conference on Principle of Distributed Systems (OPODIS 2009), Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349. - 9783642108761 ; 5923, s. 189-203
-
Konferensbidrag (refereegranskat)abstract
- his paper addresses the problem of universal synchronization primitives that can support scalable thread synchronization for large-scale manycore architectures. The universal synchronization primitives that have been deployed widely in conventional architectures, are the compare-and-swap (CAS) and load-linked/store-conditional (LL/SC) primitives. However, such synchronization primitives are expected to reach their scalability limits in the evolution to manycore architectures with thousands of cores.We introduce a non-blocking full/empty bit primitive, or NB-FEB for short, as a promising synchronization primitive for parallel programming on manycore architectures. We show that the NB-FEB primitive is universal, scalable, feasible and easy to use. NB-FEB, together with registers, can solve the consensus problem for an arbitrary number of processes (universality). NB-FEB is combinable, namely its memory requests to the same memory location can be combined into only one memory request, which consequently makes NB-FEB scalable (scalability). Since NB-FEB is a variant of the original full/empty bit that always returns a value instead of waiting for a conditional flag, it is as feasible as the original full/empty bit, which has been implemented in many computer systems (feasibility). We construct, on top of NB-FEB, a non-blocking software transactional memory system called NBFEB-STM, which can be used as an abstraction to handle concurrent threads easily. NBFEB-STM is space efficient: the space complexity of each object updated by N concurrent threads/transactions is ${\it \Theta}(N)$, which is optimal.
|
|
| 23. |
- Ha, Phuong, 1976, et al.
(författare)
-
NB-FEB: An Easy-to-Use and Scalable Universal Synchronization Primitive for Parallel Programming
- 2008
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- This paper addresses the problem of universal synchronizationprimitives that can support scalable thread synchronizationfor large-scale many-core architectures. The universalsynchronization primitives that have been deployed widelyin conventional architectures, are the compare-and-swap (CAS)and load-linked/store-conditional (LL/SC) primitives. However,such synchronization primitives are expected to reachtheir scalability limits in the evolution to many-core architectureswith thousands of cores.We introduce a non-blocking full/empty bit primitive, orNB-FEB for short, as a promising synchronization primitivefor parallel programming on may-core architectures. We showthat the NB-FEB primitive is universal, scalable, feasible andconvenient to use. NB-FEB, together with registers, can solvethe consensus problem for an arbitrary number of processes(universality). NB-FEB is combinable, namely its memory requeststo the same memory location can be combined intoonly one memory request, which consequently mitigates performancedegradation due to synchronization "hot spots" (scalability).Since NB-FEB is a variant of the original full/emptybit that always returns a value instead of waiting for a conditionalflag, it is as feasible as the original full/empty bit, whichhas been implemented in many computer systems (feasibility).The original full/empty bit is well-known as a special-purposeprimitive for fast producer-consumer synchronization and hasbeen used extensively in the specific domain of applications.In this paper, we show that NB-FEB can be deployed easilyas a general-purpose primitive. Using NB-FEB, we constructa non-blocking software transactional memory systemcalled NBFEB-STM, which can be used to handle concurrentthreads conveniently. NBFEB-STM is space efficient:the space complexity of each object updated by N concurrentthreads/transactions is Θ(N), the optimal.
|
|
| 24. |
- Ha, Phuong, 1976, et al.
(författare)
-
Non-blocking programming on multi-core graphics processors
- 2009
-
Ingår i: SIGARCH Computer Architecture News. - 0163-5964. ; 36:5, s. 19-28
-
Tidskriftsartikel (refereegranskat)abstract
- 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.Moreover, 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), where N is the number of processes. Our result demonstrates that it is possible to construct waitfree synchronization mechanisms for GPUs without the need of strong synchronization primitives in hardware and that wait-free programming is possible for GPUs.
|
|
| 25. |
- Ha, Phuong, 1976, et al.
(författare)
-
Preliminary results on nb-feb, a synchronization primitive for parallel programming
- 2009
-
Ingår i: Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming. - New York, NY, USA : ACM. - 9781605583976 ; , s. 295-296
-
Konferensbidrag (refereegranskat)abstract
- We introduce a non-blocking full/empty bit primitive, or NB-FEB for short, as a promising synchronization primitive for parallel programming on may-core architectures. We show that the NB-FEB primitive is universal, scalable and feasible. NB-FEB, together with registers, can solve the consensus problem for an arbitrary number of processes (universality). NB-FEB is combinable, namely its memory requests to the same memory location can be combined into only one memory request, which consequently mitigates performance degradation due to synchronization "hot spots" (scalability). Since NB-FEB is a variant of the original full/empty bit that always returns a value instead of waiting for a conditional flag, it is as feasible as the original full/empty bit, which has been implemented in many computer systems (feasibility).
|
|
