DocumentCode :
3415803
Title :
Multiple templates access of trees in parallel memory systems
Author :
Auletta, Vincenzo ; Vivo, Amelia De ; Scarano, Vittorio
Author_Institution :
Dipartimento di Inf. ed Applicazioni, Salerno Univ., Italy
fYear :
1997
fDate :
1-5 Apr 1997
Firstpage :
694
Lastpage :
701
Abstract :
Studies the problem of mapping the N nodes of a data structure onto M memory modules so that they can be accessed in parallel by templates, i.e. distinct sets of nodes. In the literature, several algorithms are available for arrays (accessed by rows, columns, diagonals and subarrays) and trees (accessed by subtrees, root-to-leaf paths, etc.). Although some mapping algorithms for arrays allow conflict-free access to several templates at once (e.g. rows and columns), no mapping algorithm is known for efficiently accessing both subtree and root-to-leaf path templates in complete binary trees. We prove that any mapping algorithm that is conflict-free for one of these two templates has Ω(M/log M) conflicts on the other. Therefore, no mapping algorithm can be found that is conflict-free on both templates. We give an algorithm for mapping complete binary trees with N=2M -1 nodes on M memory modules in such a way that: (a) the number of conflicts for accessing a subtree template or a root-to-leaf path template is O[√(M/logM)], (b) the load (i.e. the ratio between the maximum and minimum number of data items mapped on each module) is 1+o(1), and (c) the time complexity for retrieving the module where a given data item is stored is O(1) if a preprocessing phase of space and time complexity O(log N) is executed, or O(log log N) if no preprocessing is allowed
Keywords :
computational complexity; memory architecture; parallel algorithms; shared memory systems; tree data structures; complete binary trees; conflict-free access; data structure; load; memory modules; multiple template access; node mapping algorithms; parallel access; parallel memory systems; preprocessing phase; root-to-leaf path templates; subtree templates; time complexity; Binary trees; Data structures; Delay; Information retrieval; Parallel algorithms; Read-write memory; Vegetation mapping;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Processing Symposium, 1997. Proceedings., 11th International
Conference_Location :
Genva
ISSN :
1063-7133
Print_ISBN :
0-8186-7793-7
Type :
conf
DOI :
10.1109/IPPS.1997.580980
Filename :
580980
Link To Document :
بازگشت