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-the-art 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. © 2010 IEEE.

K-model: A new computational model for stream processors / Capannini, G.; Silvestri, F.; Baraglia, R.. - (2010), pp. 239-246. ((Intervento presentato al convegno 2010 12th IEEE International Conference on High Performance Computing and Communications, HPCC 2010 tenutosi a Melbourne, VIC, aus [10.1109/HPCC.2010.22].

K-model: A new computational model for stream processors

Silvestri F.;
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-the-art 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. © 2010 IEEE.
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1572875
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact