Sommario non disponibile.

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.

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

Scarano V
1998

Abstract

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.
1998
Istituto di Scienza e Tecnologie dell'Informazione "Alessandro Faedo" - ISTI
0-8186-8404-6
Sommario non disponibile.
Parallel Memory Systems
Data Structures
Special purpose and application based systems
File in questo prodotto:
File Dimensione Formato  
prod_409147-doc_143759.pdf

solo utenti autorizzati

Descrizione: Toward a universal mapping algorithm for accessing trees in parallel memory systems
Tipologia: Versione Editoriale (PDF)
Dimensione 845.97 kB
Formato Adobe PDF
845.97 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/366732
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 5
social impact