Istituto di Scienza e Tecnologie dell'Informazione     
Bertossi A. A., Pinotti M. C. Mappings for conflict-free access of paths in elementary data structures. In: 6th Annual International Computing and Combinatorics Conference (Sydney, 26 - 28 July 2000). Proceedings, pp. 351 - 361. (Lecture Notes in Computer Science, vol. 1858). Springer, 2000.
Since the divergence between the processor speed and the memory access rate is progressively increasing, an ecient partition of the main memory into multibanks is useful to improve the overall sys-tem performance. The e ectiveness of the multibank partition can be de-graded by memory conflicts, that occur when there are many references to the same memory bank while accessing the same memory pattern. Therefore, mapping schemes are needed to distribute data in such a way that data can be retrieved via regular patterns without conflicts. In this paper, the problem of conflict-free access of arbitrary paths in bidimen-sional arrays, circular lists and complete trees is considered for the rst time and reduced to variants of graph-coloring problems. Balanced and fast mappings are proposed which require an optimal number of colors (i.e., memory banks). The solution for bidimensional arrays is based on a combinatorial object similar to a Latin Square. The functions that map an array node or a circular list node to a memory bank can be calculated in constant time. As for complete trees, the mapping of a tree node to a memory bank takes time that grows logarithmically with the number of nodes of the tree.
Subject Mappings
E.2 Data storage representation

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional