We study conflict-free data distribution schemes in parallel memories in multiprocessor system architectures. Given a host graph G, the problem is to map the nodes of G into memory modules such that any instance of a template type T in G can be accessed without memory conflicts. A conflict occurs if two or more nodes of T are mapped to the same memory module. The mapping algorithm should: (i) be fast in terms of data access (possibly mapping each node in constant time); (ii) minimize the required number of memory modules for accessing any instance in G of the given template type; and (iii) guarantee load balancing on the modules. In this paper, we consider conflict-free access to star templates. i.e., to any node of G along with all of its neighbors. Such a template type arises in many classical algorithms like breadth-first search in a graph, message broadcasting in networks, and nearest neighbor based approximation in numerical computation. We consider the star-template access problem on two specific host graphs-tori and hypercubes-that are also popular interconnection network topologies. The proposed conflict-free mappings on these graphs are fast, use an optimal or provably good number of memory modules, and guarantee load balancing. (C) 2006 Elsevier Inc. All rights reserved.
Conflict-free star-access in parallel memory systems / Sajal K., Das; Finocchi, Irene; Petreschi, Rossella. - In: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. - ISSN 0743-7315. - 66:11(2006), pp. 1431-1441. [10.1016/j.jpdc.2006.06.004]
|Titolo:||Conflict-free star-access in parallel memory systems|
|Data di pubblicazione:||2006|
|Citazione:||Conflict-free star-access in parallel memory systems / Sajal K., Das; Finocchi, Irene; Petreschi, Rossella. - In: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. - ISSN 0743-7315. - 66:11(2006), pp. 1431-1441. [10.1016/j.jpdc.2006.06.004]|
|Appare nelle tipologie:||01.1 - Articolo su rivista (Article)|