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
, 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 <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.
BibTeX citation:
@techreport{Weisser:CSD-96-895, Author= {Weisser, Deborah K.}, Title= {Efficient Generation of Local Index Sets for Distributed Arrays}, 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