Optimal tree access by elementary and composite templates in parallel memory systems (Articolo in rivista)

Type
Label
  • Optimal tree access by elementary and composite templates in parallel memory systems (Articolo in rivista) (literal)
Anno
  • 2002-01-01T00:00:00+01:00 (literal)
Alternative label
  • Auletta V., Das S.K., De Vivo A., Pinotti M.C., Scarano V. (2002)
    Optimal tree access by elementary and composite templates in parallel memory systems
    in IEEE transactions on parallel and distributed systems (Print)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Auletta V., Das S.K., De Vivo A., Pinotti M.C., Scarano V. (literal)
Pagina inizio
  • 399 (literal)
Pagina fine
  • 411 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 13 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note
  • IEEE, 2002 (Pubblicazione A0-27) (literal)
Note
  • ISI Web of Science (WOS) (literal)
Titolo
  • Optimal tree access by elementary and composite templates in parallel memory systems (literal)
Abstract
  • In this paper, we study efficient strategies for mapping onto parallel memory systems complete trees that are accessed by fixed templates (like complete subtrees, paths, or any combinations their of). These mappings are evaluated with respect to the following criteria: (1) the largest number of data items that can be accessed in parallel without memory conflicts; (2) the number of memory conflicts that can occur when accessing templates of size equal to the number of available memory modules, thereby exploiting the full parallelism of the system; (3) the complexity of the memory addressing scheme, i.e., the cost of retrieving the module where a given data item is mapped. We show that there exist trade-offs between these three criteria and the performance of different mapping strategies depends on the emphasis given on each of these criteria. More specifically, we describe an algorithm for mapping complete binary trees of height H onto M memory modules and prove that it achieves the following performance results: (1) conflict-free access to complete subtrees of size K and paths of size N such that N + K - [log K] ⩽ M; (2) at most 1 conflict in accessing complete subtrees and paths of size M; (3) O(K/M + c) conflicts when accessing a composite template of K nodes consisting of c disjoint subsets, each subset being a complete subtree, or a path or a set of consecutive nodes in a level of the tree (literal)
Prodotto di
Autore CNR

Incoming links:


Prodotto
Autore CNR di
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
data.CNR.it