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
102
103
104
105
106
107
108
109
110
111
112
113
|
<!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>The Block Column and Row Distributions</TITLE>
<META NAME="description" CONTENT="The Block Column and Row Distributions">
<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="tex2html3212" HREF="node83.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3210" HREF="node81.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html3204" HREF="node81.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3214" 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="tex2html3215" 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="tex2html3213" HREF="node83.html">The Block Mapping</A>
<B>Up:</B> <A NAME="tex2html3211" HREF="node81.html">In-Core Narrow Band and </A>
<B> Previous:</B> <A NAME="tex2html3205" HREF="node81.html">In-Core Narrow Band and </A>
<BR> <P>
<H2><A NAME="SECTION04441000000000000000">The Block Column and Row Distributions</A></H2>
<A NAME="sec1dbd"> </A>
<A NAME="2682"> </A>
<A NAME="2683"> </A>
<A NAME="2684"> </A>
<A NAME="2685"> </A>
<A NAME="2686"> </A>
<P>
ScaLAPACK assumes a one-dimensional
block distribution for the band and
tridiagonal routines. The <EM>block</EM>
distribution is used when the computational
load is distributed homogeneously
over the global data. This distribution
leads to a highly efficient implementation
of the divide-and-conquer algorithms
used in ScaLAPACK.
<P>
For convenience we will number the
processes from 0 to <I>P</I>-1, and
the matrix rows from 1 to <I>M</I>
and the matrix columns from 1
to <I>N</I>. Figure <A HREF="node82.html#figblock">4.8</A>
shows the two data layouts used in
ScaLAPACK for solving narrow band
linear systems. In all cases,
each submatrix is labeled with
the number of the process that
contains it. Process 0 owns the
shaded submatrices.
<P>
Consider the layout illustrated
on the left of figure <A HREF="node82.html#figblock">4.8</A>,
the <B>one-dimensional block
column distribution</B>. This distribution
<A NAME="2691"> </A><A NAME="2692"> </A>
<P><A NAME="2697"> </A><A NAME="figblock"> </A><IMG WIDTH=447 HEIGHT=158 ALIGN=BOTTOM ALT="figure2693" SRC="img310.gif"><BR>
<STRONG>Figure 4.8:</STRONG> The one-dimensional block-column and block-row distributions<BR>
<P>
assigns a block of <I>NB</I> contiguous
columns of a matrix to successive
processes arranged in a <IMG WIDTH=42 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline15088" SRC="img311.gif">
one-dimensional process grid. Each
process receives at most one block
of columns of the matrix, i.e.,
<IMG WIDTH=102 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline15090" SRC="img312.gif">.
Column <I>k</I> is stored on process
<IMG WIDTH=57 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline15094" SRC="img313.gif">.
The maximum number of columns
stored per process is given by
<IMG WIDTH=46 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline15096" SRC="img314.gif">. In the
figure <I>M</I>=<I>N</I>=16 and <I>P</I>=4.
This distribution assigns
blocks of columns of size
<I>NB</I> to successive processes.
If the value of <I>P</I> evenly
divides the value of
<I>N</I> and <I>NB</I> = <I>N</I> / <I>P</I>, then
each process owns a block of
equal size. However, if this
is not the case, then either
the last process to receive
a portion of the matrix will
receive a smaller block than
other processes, or some
processes may receive an
empty portion of the matrix.
The transpose of this layout,
the <B>one-dimensional
block-row distribution</B>,
<A NAME="2701"> </A><A NAME="2702"> </A>
is shown on the right of
figure <A HREF="node82.html#figblock">4.8</A>.
<P>
The block-column distribution scheme
is the data layout that is used in
the ScaLAPACK library for the
coefficient matrix of the narrow
band and tridiagonal solvers.
<P>
The block-row distribution scheme
is the data layout that is used in
the ScaLAPACK library for the
right-hand-side matrix of the
narrow band and tridiagonal solvers.
<P>
<HR><A NAME="tex2html3212" HREF="node83.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3210" HREF="node81.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html3204" HREF="node81.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3214" 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="tex2html3215" 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="tex2html3213" HREF="node83.html">The Block Mapping</A>
<B>Up:</B> <A NAME="tex2html3211" HREF="node81.html">In-Core Narrow Band and </A>
<B> Previous:</B> <A NAME="tex2html3205" HREF="node81.html">In-Core Narrow Band and </A>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>
|
