K-Model: a new computational model for stream processors (Rapporti tecnici/preprint/working paper)

Type
Label
  • K-Model: a new computational model for stream processors (Rapporti tecnici/preprint/working paper) (literal)
Anno
  • 2010-01-01T00:00:00+01:00 (literal)
Alternative label
  • Capannini G., Silvestri F., Baraglia R. (2010)
    K-Model: a new computational model for stream processors
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Capannini G., Silvestri F., Baraglia R. (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#pagineTotali
  • 14 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#supporto
  • Altro (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • CNR-ISTI, Pisa, Italy; CNR-ISTI, Pisa, Italy; CNR-ISTI, Pisa, Italy; (literal)
Titolo
  • K-Model: a new computational model for stream processors (literal)
Abstract
  • We introduce k-model, a computational model to properly evaluate algorithms designed for graphic processors, and other architectures ad- hering to the stream programming model. We address the lack of one formal complexity model that properly accounts for memory contention, address coalescing in memory accesses, or the serial control of the instruc- tion 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 effi- cient than bitonic sort, empirically, our bitonic sorting network has been shown to be faster than the state-of-the-art implementation of quicksort on graphics processing units (GPUs). Using our k-model we are able to prove the reason why on GPU architectures this is not true anymore. As a side result, our technique to perform a Batcher's network on GPUs improves the performance of the fastest comparison-based solution for integers sorting. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Insieme di parole chiave di
data.CNR.it