| 31. |
- Cederman, Daniel, 1981, et al.
(författare)
-
On Sorting and Load-Balancing on GPUs
- 2008
-
Ingår i: ACM SIGARCH Computer Architecture News. ; 36:5
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper we present GPU-Quicksort, an efficientQuicksort algorithm suitable for highly parallel multi-coregraphics processors. Quicksort has previously been consideredas an inefficient sorting solution for graphics processors,but we show that GPU-Quicksort often performs betterthan the fastest known sorting implementations for graphicsprocessors, such as radix and bitonic sort. Quicksortcan thus be seen as a viable alternative for sorting largequantities of data on graphics processors.We also present a comparison of different load balancingschemes. To get maximum performance on the manycoregraphics processors it is important to have an evenbalance of the workload so that all processing units contributeequally to the task at hand. This can be hard toachieve when the cost of a task is not known beforehandand when new sub-tasks are created dynamically during execution.With the recent advent of scatter operations andatomic hardware primitives it is now possible to bring someof the more elaborate dynamic load balancing schemes fromthe conventional SMP systems domain to the graphics processordomain.
|
|
| 32. |
- Cederman, Daniel, 1981, et al.
(författare)
-
Supporting Lock-Free Composition of Concurrent Data Objects
- 2010
-
Ingår i: SIGPLAN Notices (ACM Special Interest Group on Programming Languages). - : Association for Computing Machinery (ACM). - 0730-8566 .- 0362-1340 .- 1558-1160. ; 45:5, s. 339-340
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- Lock-free data objects offer several advantages over their blocking counterparts, such as being immune to deadlocks and convoying and, more importantly, being highly concurrent. But they share a common disadvantage in that the operations they provide are difficult to compose into larger atomic operations while still guaranteeing lock-freedom. We present a lock-free methodology for composing highly concurrent linearizable objects together by unifying their linearization points. This makes it possible to relatively easily introduce atomic lock-free move operations to a wide range of concurrent objects. Experimental evaluation has shown that the operations originally supported by the data objects keep their performance behavior under our methodology.
|
|
| 33. |
- Cederman, Daniel, 1981, et al.
(författare)
-
Supporting Lock-Free Composition of Concurrent Data Objects
- 2010
-
Ingår i: Proceedings of the 7th ACM conference on Computing frontiers. - 9781450300445 ; , s. 53-62
-
Konferensbidrag (refereegranskat)abstract
- Lock-free data objects offer several advantages over their blocking counterparts, such as beingimmune to deadlocks and convoying and, more importantly, being highly concurrent.However, composing the operations they provide into larger atomic operations, while still guaranteeingefficiency and lock-freedom, is a challenging algorithmic task.We present a lock-freemethodology for composing highly concurrent linearizable objects together by unifying their linearization points.This makes it possible to relatively easily introduce atomic lock-free move operations to a wide rangeof concurrent objects. Experimental evaluation has shown that the operations originally supported bythe data objects keep their performance behavior under our methodology.
|
|
| 34. |
- Cederman, Daniel, 1981, et al.
(författare)
-
Supporting Lock-Free Composition of Concurrent Data Objects
- 2009
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Lock-free data objects offer several advantages over their blocking counterparts, such as being immune to deadlocks and convoying and, more importantly, being highly concurrent. But they share a common disadvantage in that the operations they provide are difficult to composeinto larger atomic operations while still guaranteeing lock-freedom. We present a lock-free methodology for composing highly concurrent linearizable objects together by unifying their linearization points. This makes it possible to relatively easily introduce atomic lock-free move operations to a wide range of concurrent objects. Experimental evaluation has shown that the operations originally supported by the data objects keep their performance behavior under our methodology.
|
|
| 35. |
- Cederman, Daniel, 1981, et al.
(författare)
-
Supporting Lock-Free Composition of Concurrent Data Objects
- 2010
-
Ingår i: Proceedings of the 15th ACM SIGPLAN symposium on Principles and practice of parallel programming. - New York, NY, USA : ACM. - 9781605587080 ; , s. 339-340
-
Konferensbidrag (refereegranskat)abstract
- Lock-free data objects offer several advantages over their blocking counterparts, such as being immune to deadlocks and convoying and, more importantly, being highly concurrent. But they share a common disadvantage in that the operations they provide are difficult to compose into larger atomic operations while still guaranteeing lock-freedom. We present a lock-free methodology for composing highly concurrent linearizable objects together by unifying their linearization points. This makes it possible to relatively easily introduce atomic lock-free move operations to a wide range of concurrent objects. Experimental evaluation has shown that the operations originally supported by the data objects keep their performance behavior under our methodology.
|
|
| 36. |
- Cederman, Daniel, 1981, et al.
(författare)
-
Supporting Lock-Free Composition of Concurrent Data Objects
- 2010
-
Ingår i: MCC10 Proceedings.
-
Konferensbidrag (refereegranskat)abstract
- We present a lock-free methodology for composing highly concurrent linearizable objects together by unifying their linearization points. This makes it possible to relatively easily introduce atomic lock-free move operations to a wide range of concurrent objects. Experimental evaluation has shown that the operations originally supported by the data objects keep their performance behavior under our methodology.
|
|
| 37. |
- Cederman, Daniel, 1981, et al.
(författare)
-
Supporting Lock-Free Composition of Concurrent Data Objects: Moving Data Between Containers
- 2013
-
Ingår i: IEEE Transactions on Computers. - 0018-9340. ; 62:9, s. 1866-1878
-
Tidskriftsartikel (refereegranskat)abstract
- Lock-free data objects offer several advantages over their blocking counterparts, such as being immune to deadlocks, priority inversion and convoying. They have also been shown to work well in practice. However, composing the operations they provide into larger atomic operations, while still guaranteeing efficiency and lock-freedom, is a challenging algorithmic task. We present a lock-free methodology for composing a wide variety of concurrent linearizable objects together by unifying their linearization points. This makes it possible to relatively easily introduce atomic lock-free move operations to a wide range of concurrent lock-free containers. This move operation allows data to be transferred from one container to another, in a lock-free way, without blocking any of the operations supported by the original container. For a data object to be suitable for composition using our methodology it needs to fulfil a set of requirements. These requirement are however generic enough to be fulfilled by a large set of objects. To show this we have performed case studies on six commonly used lock-free objects (a stack, a queue, a skip-list, a deque, a doubly linked-list and a hash-table) to demonstrate the general applicability of the methodology. We also show that the operations originally supported by the data objects keep their performance behavior under our methodology.
|
|
| 38. |
- Cederman, Daniel, 1981, et al.
(författare)
-
Towards a Software Transactional Memory for CUDA
- 2009
-
Ingår i: MCC09 Proceedings.
-
Konferensbidrag (refereegranskat)abstract
- The introduction of CUDA, NVIDIA's system for general purpose computing on their many-core graphics processorsystem, and the general shift in the industry towards parallelism, has created a demand for ease of parallelization.Software transactional memory (STM) simplifies development of concurrent code by allowing theprogrammer to mark sections of code to be executed atomically. The STM will then guarantee that otherprocesses will see either none or all of the writes done in in that section. In contrast to using locks,STM:s are easy to compose and does not suffer from deadlocks. An STM can thus be seen as a concurrency control mechanism.In this paper we report on our work towards implementing a simple software transactional memory in CUDA.
|
|
| 39. |
- Cederman, Daniel, 1981, et al.
(författare)
-
Towards a Software Transactional Memory for Graphics Processors
- 2010
-
Ingår i: Proceedings of the Eurographics Symposium on Parallel Graphics and Visualization 2010.
-
Konferensbidrag (refereegranskat)abstract
- The introduction of general purpose computing on many-core graphics processorsystems, and the general shift in the industry towards parallelism, has created a demand for ease of parallelization.Software transactional memory (STM) simplifies development of concurrent code by allowing theprogrammer to mark sections of code to be executed concurrently and atomically in an optimistic manner.In contrast to locks,STMs are easy to compose and do not suffer from deadlocks.We have designed and implemented two STMs for graphics processors, one blocking and one non-blocking.The design issues involved in the designing of these two STMs are described andexplained in the paper together with experimental results comparing the performance of the two STMs.
|
|
| 40. |
- Cederman, Daniel, 1981, et al.
(författare)
-
Understanding the Performance of Concurrent Data Structures on Graphics Processors
- 2012
-
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. - 9783642328190 ; 7484/2012, s. 883-894
-
Konferensbidrag (refereegranskat)abstract
- In this paper we revisit the design of concurrent data structures -- specifically queues -- and examine their performance portabilitywith regard to the move from conventional CPUs to graphics processors. We have looked at both lock-based and lock-free algorithmsand have, for comparison, implemented and optimized the same algorithms on both graphics processors and multi-core CPUs.Particular interest has been paid to study the difference between the old Tesla and the new Fermi and Kepler architecturesin this context.We provide a comprehensive evaluation and analysis of our implementations on all examined platforms.Our results indicate that the queues are in general performance portable, but that platform specific optimizations are possibleto increase performance. The Fermi and Kepler GPUs, with optimized atomic operations, are observed to provide excellent scalabilityfor both lock-based and lock-free queues.
|
|
