K-Model: a new computational model for stream processors (Contributo in atti di convegno)

Type
Label
  • K-Model: a new computational model for stream processors (Contributo in atti di convegno) (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
    in 12th IEEE International Conference on High Performance Computing and Communications, Melbourne, Australia, 1-3 September 2010
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Capannini G.; Silvestri F.; Baraglia R. (literal)
Pagina inizio
  • 239 (literal)
Pagina fine
  • 246 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#url
  • http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5581343 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note
  • In: HPCC 2010 - 12th IEEE International Conference on High Performance Computing and Communications (Melbourne, Australia, 1-3 September 2010). Proceedings, pp. 239 - 246. IEEE, 2010. (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#pagineTotali
  • 8 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#descrizioneSinteticaDelProdotto
  • 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 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • CNR-ISTI, Pisa (literal)
Titolo
  • K-Model: a new computational model for stream processors (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#isbn
  • 978-0-7695-4214-0 (literal)
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. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


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