Efficient Generation of Local Index Sets for Distributed Arrays

Deborah K. Weisser

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-96-895
January 1996

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1996/CSD-96-895.pdf

An important component of parallel programs with distributed data structures is local address generation for various index patterns. In this paper we present a general approach as well as two specific algorithms for common problems to perform this task quickly on distributed arrays. Our algorithms usually run in O(| output|) time, which is optimal. We have implemented our algorithms. When the problem size is small, they perform as well as or better than naive algorithms. When the problem size is large, they outperform naive algorithms by several orders of magnitude.


BibTeX citation:

@techreport{Weisser:CSD-96-895,
    Author = {Weisser, Deborah K.},
    Title = {Efficient Generation of Local Index Sets for Distributed Arrays},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1996},
    Month = {Jan},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1996/6012.html},
    Number = {UCB/CSD-96-895},
    Abstract = {An important component of parallel programs with distributed data structures is local address generation for various index patterns. In this paper we present a general approach as well as two specific algorithms for common problems to perform this task quickly on distributed arrays. Our algorithms usually run in <i>O</i>(|<i>output</i>|) time, which is optimal. We have implemented our algorithms. When the problem size is small, they perform as well as or better than naive algorithms. When the problem size is large, they outperform naive algorithms by several orders of magnitude.}
}

EndNote citation:

%0 Report
%A Weisser, Deborah K.
%T Efficient Generation of Local Index Sets for Distributed Arrays
%I EECS Department, University of California, Berkeley
%D 1996
%@ UCB/CSD-96-895
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1996/6012.html
%F Weisser:CSD-96-895