Istituto di Scienza e Tecnologie dell'Informazione     
Auletta V., Das S., De Vivo A., Pinotti M. C., Scarano V. Toward a universal mapping algorithm for accessing trees in parallel memory systems. In: First merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing. Proceedings (Orlando, USA,1998), 447-454. ACM-IEEE, 1998. 1998.
We 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 will be referred to as elementary templates. In this paper, we 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. We also propose another mapping algorithm for a composite template, say V (as versatile), such that its size is not fixed and an instance of V is composed of any combination of c instances of elementary templates. The number of conflicts for accessing an S-node instance of template V is 0 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.
Subject Parallel Memory Systems
C.3 special purpose and application based systems
E.1 Data Structures

Icona documento 1) 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