Effective Data Access Patterns on Massively Parallel Processors

The new generation of microprocessors incorporates a huge number of cores on the same chip. Graphics processing units are an example of this kind of architectures. This chapter discusses the characteristics and the issues of the memory systems of this kind of architectures. It analyzes these architectures from a theoretical point of view using the K-model to estimate the complexity of a given algorithm defined on this computational model. The chapter describes how the K-model can be used to design efficient data access patterns for implementing efficient GPU algorithms. It introduces some preliminary details of many-core architectures, describes the K-model, analyzes the two applications, parallel prefix sum and bitonic sorting networks, by means of the K-model. Finally, the chapter concludes that experiments conducted demonstrates that the K-model could be fruitfully exploited to design efficient algorithms for computational platforms with many cores.