Toward a universal mapping algorithm for accessing trees in parallel memory systems

被引：5

作者：

Auletta, V ^{[1
]}

Das, SK ^{[1
]}

De Vivo, A ^{[1
]}

Pinotti, MC ^{[1
]}

Scarano, V ^{[1
]}

机构：

[1] Univ Salerno, Dipartimento Informat & Appl RM Capocelli, I-84081 Baronissi, SA, Italy

来源：

FIRST MERGED INTERNATIONAL PARALLEL PROCESSING SYMPOSIUM & SYMPOSIUM ON PARALLEL AND DISTRIBUTED PROCESSING | 1998年

关键词：

D O I：

10.1109/IPPS.1998.669955

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 las 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 O(s/root M log M + c) memory load as 1+ o(1) where load is defined as the ratio between the maximum and minimum number of data items mapped onto each memory module.

引用

页码：447 / 454

页数：8