1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<!--Converted with LaTeX2HTML 96.1-h (September 30, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds -->
<HTML>
<HEAD>
<TITLE>Two-Dimensional Block Cyclic Data Distribution as a Key
to Load Balancing and Software Reuse</TITLE>
<META NAME="description" CONTENT="Two-Dimensional Block Cyclic Data Distribution as a Key
to Load Balancing and Software Reuse">
<META NAME="keywords" CONTENT="slug">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<LINK REL=STYLESHEET HREF="slug.css">
</HEAD>
<BODY LANG="EN" >
<A NAME="tex2html3590" HREF="node111.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3588" HREF="node108.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html3582" HREF="node109.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3592" HREF="node1.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="http://www.netlib.org/utk/icons/contents_motif.gif"></A> <A NAME="tex2html3593" HREF="node190.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="http://www.netlib.org/utk/icons/index_motif.gif"></A> <BR>
<B> Next:</B> <A NAME="tex2html3591" HREF="node111.html">BLACS as an Efficient</A>
<B>Up:</B> <A NAME="tex2html3589" HREF="node108.html">PerformancePortability and Scalability</A>
<B> Previous:</B> <A NAME="tex2html3583" HREF="node109.html">The BLAS as the </A>
<BR> <P>
<H2><A NAME="SECTION04522000000000000000">Two-Dimensional Block Cyclic Data Distribution as a Key
to Load Balancing and Software Reuse</A></H2>
<A NAME="subsecblockcyclic"> </A>
<P>
The way the data is
distributed over
the memory hierarchy
of a computer is of
fundamental importance
to load balancing and
software reuse. The
block cyclic data
distribution allows a
reduction of the
overhead due to
load imbalance
and data movement.
Block-partitioned
algorithms<A NAME="3623"> </A><A NAME="3624"> </A> are
used to
maximize the
local node
performance.
<P>
Since the data
decomposition
largely determines
the performance
and scalability
of a concurrent
algorithm, a
great deal of
research
[<A HREF="node189.html#lawn55">27</A>, <A HREF="node189.html#fox88ab">65</A>, <A HREF="node189.html#geist88a">69</A>, <A HREF="node189.html#lawn79">78</A>]
has focused on
different data
decompositions
[<A HREF="node189.html#ashcraft90a">10</A>, <A HREF="node189.html#brent92a">20</A>, <A HREF="node189.html#huss94a">85</A>].
In particular, the
two-dimensional block
cyclic distribution
[<A HREF="node189.html#kumar94a">92</A>]<A NAME="3628"> </A> has
been suggested as a
possible general-purpose
basic decomposition
for parallel dense
linear algebra libraries
[<A HREF="node189.html#chu90a">31</A>, <A HREF="node189.html#hendrickson94a">76</A>, <A HREF="node189.html#lichtenstein93a">97</A>, <A HREF="node189.html#BV89">17</A>]
such as ScaLAPACK.
<P>
Block cyclic distribution
is beneficial because of
its scalability [<A HREF="node189.html#lawn43">51</A>]<A NAME="3631"> </A>,
load balance,<A NAME="3632"> </A> and communication
[<A HREF="node189.html#hendrickson94a">76</A>]
properties. The
block-partitioned
computation then
proceeds in
consecutive
order just as
a conventional
serial algorithm does.
This essential
property of the
block cyclic data
distribution explains
why the ScaLAPACK
design has been
able to reuse
the numerical and
software expertise
of the sequential
LAPACK library.
<P>
<BR> <HR>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>
|
