K-Model: a new computational model for stream processors

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.