Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Optimal mappings of q-ary and binomial trees into parallel memory modules for fast and conflict-free access to path and subtree templates
Autore:
Das, SK; Pinotti, MC;
Indirizzi:
Univ Texas, Dept Comp Sci & Engn, Arlington, TX 76019 USA Univ Texas Arlington TX USA 76019 omp Sci & Engn, Arlington, TX 76019 USA CNR, Ist Elaboraz Informaz, I-56100 Pisa, Italy CNR Pisa Italy I-56100CNR, Ist Elaboraz Informaz, I-56100 Pisa, Italy
Titolo Testata:
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
fascicolo: 8, volume: 60, anno: 2000,
pagine: 998 - 1027
SICI:
0743-7315(200008)60:8<998:OMOQAB>2.0.ZU;2-1
Fonte:
ISI
Lingua:
ENG
Soggetto:
PRIORITY-QUEUES;
Keywords:
binomial tree; complete q-ary tree; conflict-free access; optimal mapping scheme; parallel memory system; path template; subtree template;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
19
Recensione:
Indirizzi per estratti:
Indirizzo: Das, SK Univ Texas, Dept Comp Sci & Engn, Arlington, TX 76019 USA Univ Texas Arlington TX USA 76019 & Engn, Arlington, TX 76019 USA
Citazione:
S.K. Das e M.C. Pinotti, "Optimal mappings of q-ary and binomial trees into parallel memory modules for fast and conflict-free access to path and subtree templates", J PAR DISTR, 60(8), 2000, pp. 998-1027

Abstract

The main memory access latency can significantly slow down the overall performance of a computer system due to the fact that average cycle time of the main memory is typically a factor of 5-10 times higher than that of a processor. To cope with this problem, in addition to the use of caches, the main memory of a multiprocessor architecture is usually organized into multiple modules or banks. Although such organization enhances memory bandwidth, the amount of data that the multiprocessor can retrieve in the same memory cycle, conflicts due to simultaneous attempts to access the same memory module may reduce the effective bandwidth. Therefore, efficient mapping schemes are required to distribute data in such a way that regular patterns, called templates, of various structures can be retrieved in parallel without memory conflicts. Prior work on data mappings mostly dealt with conflict-freeaccess to templates such as rows, columns, or diagonals of(multidimensional) arrays, and only limited attention has been paid to access templates of nonnumeric structures such as trees. In this paper, we study optimal and balanced mappings for accessing path and subtree templates of trees, where a mapping will be called optimal if it allows conflict-free access to templates with as few memory banks as possible. An optimal mapping will also be called balanced if it distributes as evenly as possible the nodes of the entire tree among the memory banks available. In particular, based on Latin squares, we propose an optimal and balanced mapping for leaf-to-root paths of q-ary trees. Another (recursive) mapping for leaf-to-root paths of binary trees raises interesting combinatorial problems. We also derive an optimal and balanced mapping to access complete t-ary subtrees of complete q-ary trees, where 2 less than or equal to t less than or equal to q, and an optimalmapping for subtrees of binomial trees. (C) 2000 Academic Press.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 13/07/20 alle ore 07:56:38