Versatile Access to Parallel Memory Systems

In this paper, we present a survey of results about the problem of mapping the N items of a data structure on M memory modules so that items can be accessed in parallel by templates i.e. distinct sets of nodes. In particular, we present some results that allow to access several different templates at once, i.e. we focus on versatile mapping algorithms (for a comprehensive survey of other related results see [14] in this volume). In particular, we present some of the algorithms in literature for accessing arrays (by rows, columns, diagonals and subarrays) and trees (accessed by subtrees, root-to-leaf paths, levels and compositions thereof). 1 Introduction In this paper we present a survey of results related to the problem of mapping a data structure to M memory modules when it is known how the access is required i.e. templates of memory access are known. The problem is to minimize the conflicts on the memory modules, i.e. simultaneous access to the same module to retrieve different dat..