Back to Search
Start Over
K-Model: a new computational model for stream processors
- Source :
- 12th IEEE International Conference on High Performance Computing and Communications, pp. 239–246, Melbourne, Australia, 1-3 September 2010, info:cnr-pdr/source/autori:Capannini G.; Silvestri F.; Baraglia R./congresso_nome:12th IEEE International Conference on High Performance Computing and Communications/congresso_luogo:Melbourne, Australia/congresso_data:1-3 September 2010/anno:2010/pagina_da:239/pagina_a:246/intervallo_pagine:239–246, ISTI Technical reports, 2010, HPCC
- Publication Year :
- 2010
- Publisher :
- IEEE, New York, USA, 2010.
-
Abstract
- We introduce K-model, a computational model to evaluate the algorithms designed for graphic processors, and other architectures adhering to the stream programming model. We address the lack of a formal complexity model that properly accounts for memory contention, address coalescing in memory accesses, or the serial control of instruction flows. We study the impact of K-model rules on algorithm design. We devise a coalesced and low contention data access technique for Batcher's networks, and we evaluate the effectiveness of this technique within our K-model. To evaluate the benefits in using K-model in evaluating solutions for streaming architectures, we compare the complexity of a sorting network built using our technique, and quicksort. Although in theory quicksort is more efficient than bitonic sort, empirically, our bitonic sorting network has been shown to be faster than the state-of-theart implementation of quicksort on graphics processing units (GPUs). We use our K-model to prove that this observation should generally hold. As a side result, our technique to perform a Batcher's network on GPUs improves the performance of one the fastest comparison-based solution for integers sorting.
- Subjects :
- Bitonic sorter
Selection sort
Sorting algorithm
Computer science
Parallel algorithms
Computational model
Parallel algorithm
Sorting
Modeling
GPU
Parallel computing
Parallel processing
Bitonic sorting
Adaptive sort
Computer Systems Organization. GENERAL Modeling of computer architecture
Integer
Modeling of computer architecture
Stream programming
Sorting network
sort
Algorithm design
Timsort
Merge sort
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- 12th IEEE International Conference on High Performance Computing and Communications, pp. 239–246, Melbourne, Australia, 1-3 September 2010, info:cnr-pdr/source/autori:Capannini G.; Silvestri F.; Baraglia R./congresso_nome:12th IEEE International Conference on High Performance Computing and Communications/congresso_luogo:Melbourne, Australia/congresso_data:1-3 September 2010/anno:2010/pagina_da:239/pagina_a:246/intervallo_pagine:239–246, ISTI Technical reports, 2010, HPCC
- Accession number :
- edsair.doi.dedup.....ffada43c1d64efcdd83ea548ffc002f6