Toward a universal mapping algorithm for accessing trees in parallel memory systems
Vincenzo Auletta, Sajal Kumar Das, Amelia De Vivo, Cristina Maria Pinotti, Vittorio Scarano · 2002
The authors study the problem of mapping the N nodes of a complete t-ary tree on M memory modules so that they can be accessed in parallel by templates, i.e. distinct sets of nodes. Typical templates for accessing trees are subtrees, root-to-leaf paths, or levels which are referred to as elementary templates. They first propose a new mapping algorithm for accessing both paths and subtrees of size M with an optimal number of conflicts (i.e., only one conflict) when the number of memory modules is limited to M. They also propose another mapping algorithm for a composite template, say /spl Vscr/ (as versatile), such that its size is not fixed and an instance of /spl Vscr/ is composed of any combination of c instances of elementary templates. The number of conflicts for accessing an S-node instance of template /spl Vscr/ is O(S//spl radic/M log M+c) and the memory load is 1+o(1) where load is defined as the ratio between the maximum and minimum number of data items mapped onto each memory module.