loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers
Star-Coloring of Graphs for Conflict-Free Access to Parallel Memory Systems
Santa Fe, New Mexico
April 26-April 30
ISBN: 0-7695-2132-0
Sajal Das, University of Texas at Arlington
Irene Finocchi, University of Rome "Tor Vergata"
Rossella Petreschi, University of Rome "La Sapienza"
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 in G of a template type T can be accessed without memory conflicts. A conflict occurs if two or more nodes of T are mapped to the same module. The mapping algorithm should be fast in terms of data access, minimize the required number of memory modules, and guarantee load balancing on the modules. In this paper, we consider conflict-free access to star templates (i.e., any node of G along with all its neighbors) and we study the star-access problem on two specific host graphs, tori and hypercubes. We propose conflict-free mappings that are fast and load-balanced, using an optimal or provably good number of memory modules.
Citation:
Sajal Das, Irene Finocchi, Rossella Petreschi, "Star-Coloring of Graphs for Conflict-Free Access to Parallel Memory Systems," ipdps, vol. 1, pp.50b, 18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers, 2004
Usage of this product signifies your acceptance of the Terms of Use.