Istituto di Scienza e Tecnologie dell'Informazione     
Capannini G., Silvestri F., Baraglia R. K-Model: a new computational model for stream processors. 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.
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.
URL: http://ieeexplore.ieee.org/search/searchresult.jsp?newsearch=true&queryText=K-Model%3A+a+new+computational+model+for+stream+processors&filter=&x=33&y=11
DOI: 10.1109/HPCC.2010.22
Subject Computational model
Stream programming
C.0 Computer Systems Organization. GENERAL Modeling of computer architecture

Icona documento 1) Download Document PDF
Icona documento 2) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional