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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
|
<!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 Mapping</TITLE>
<META NAME="description" CONTENT="The Block Mapping">
<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="tex2html3224" HREF="node84.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3222" 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="tex2html3216" HREF="node82.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3226" 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="tex2html3227" 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="tex2html3225" HREF="node84.html">Local Storage Scheme for </A>
<B>Up:</B> <A NAME="tex2html3223" HREF="node81.html">In-Core Narrow Band and </A>
<B> Previous:</B> <A NAME="tex2html3217" HREF="node82.html">The Block Column and </A>
<BR> <P>
<H2><A NAME="SECTION04442000000000000000">The Block Mapping</A></H2>
<A NAME="secblockmap"> </A>
<P>
The one-dimensional distribution scheme
is a mapping of a set of blocks onto
the processes. The previous section
informally described this mapping as
well as some of its properties. To
be complete, we shall describe
the precise mapping that associates
to a matrix entry identified by its
global indexes the coordinates of
the process that owns it and its
local position within that process's
memory.
<P>
Suppose we have a two dimensional
array <I>A</I> of size <IMG WIDTH=55 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline15127" SRC="img315.gif"> to
be distributed on a <IMG WIDTH=42 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline15088" SRC="img311.gif">
process grid in a block-column
fashion. By convention, the array
columns are numbered 1 through
<I>N</I> and the processes are numbered
0 through <I>P</I>-1. First, the array
is divided into contiguous blocks
of <I>NB</I> columns with <IMG WIDTH=102 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline15090" SRC="img312.gif">. When <I>NB</I> does not
divide <I>N</I> evenly, the last block
of columns will only contain
<IMG WIDTH=98 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline14699" SRC="img271.gif"> columns instead
of <I>NB</I>. By convention, these blocks
are numbered starting from zero and
dealt out to the processes. In other
words, if we assume that the process
0 receives the first block, the
<IMG WIDTH=21 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline15153" SRC="img316.gif"> block is assigned to the
process of coordinate (0,<I>p</I>).
The mapping of a column of the
array globally indexed by <I>J</I> is
defined by the following analytical
equation:
<BR><IMG WIDTH=306 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath15123" SRC="img317.gif"><BR>
where <I>J</I> is a global column index
in the array, <I>p</I> is the column
coordinate of the process owning
that column, and finally <I>x</I> is
the column coordinate within that
block of columns where the global
array column of index <I>J</I> is to be
found. It is then fairly easy to
establish the analytical relationship
between these variables. One obtains:
<BR><A NAME="eqnindexblockmap"> </A><IMG WIDTH=546 HEIGHT=18 ALIGN=BOTTOM ALT="equation2708" SRC="img318.gif"><BR>
These equations allow to determine
the local information, i.e. the
local index <I>x</I> as well as the
process column coordinate <I>p</I>
corresponding to a global column
identified by its global index <I>J</I>
and conversely. Table <A HREF="node83.html#tabblockmap">4.9</A>
illustrates this mapping layout when
<I>P</I>=2 and <I>N</I>=16 and <I>NB</I>=8. At most
one block is assigned to each process.
<P><A NAME="2714"> </A><A NAME="tabblockmap"> </A><IMG WIDTH=544 HEIGHT=68 ALIGN=BOTTOM ALT="table2713" SRC="img319.gif"><BR>
<STRONG>Table 4.9:</STRONG> One-dimensional block-column mapping example for <I>P</I>=2 and <I>N</I>=16<BR>
<P>
<P>
This example of the one-dimensional
block-column distribution mapping
<A NAME="2722"> </A><A NAME="2723"> </A>
can be expressed in HPF<A NAME="2724"> </A>
by using the following statements:
<PRE> REAL :: A( M, N )
!HPF$ PROCESSORS PROC( 1, P )
!HPF$ DISTRIBUTE A( *, BLOCK( NB ) ) ONTO PROC</PRE>
<P>
A similar example of block-row
distribution <A NAME="2725"> </A><A NAME="2726"> </A>
can easily be constructed. For
an <IMG WIDTH=93 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline15189" SRC="img320.gif"> array <I>B</I>,
such an example can be expressed
in HPF<A NAME="2727"> </A> by
using the following statements:
<PRE> REAL :: B( N, NRHS )
!HPF$ PROCESSORS PROC( P, 1 )
!HPF$ DISTRIBUTE B( BLOCK( NB ), * ) ONTO PROC</PRE>
<P>
There is in fact no real
reason to always deal out
the blocks starting with
the process 0. In fact,
it is sometimes useful to
start the data distribution
with the process of arbitrary
coordinate SRC, in which case
Equation <A HREF="node83.html#eqnindexblockmap">4.3</A>
becomes:
<BR><A NAME="eqnindexblockmap1"> </A><IMG WIDTH=500 HEIGHT=48 ALIGN=BOTTOM ALT="equation2729" SRC="img321.gif"><BR>
<P>
Table <A HREF="node83.html#tabbcblockmap0">4.10</A>
illustrates Equation <A HREF="node83.html#eqnindexblockmap1">4.4</A>
for the block-cyclic layout when <IMG WIDTH=56 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline14791" SRC="img281.gif">,
<IMG WIDTH=79 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline14793" SRC="img282.gif">, <IMG WIDTH=73 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline14795" SRC="img283.gif"> and <IMG WIDTH=67 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline14797" SRC="img284.gif">.
<P><A NAME="2739"> </A><A NAME="tabbcblockmap0"> </A><IMG WIDTH=544 HEIGHT=68 ALIGN=BOTTOM ALT="table2738" SRC="img322.gif"><BR>
<STRONG>Table 4.10:</STRONG> One-dimensional block-column mapping for <I>P</I>=2, <I>SRC</I>=1,
<I>N</I>=16 and <I>NB</I>=8<BR>
<P>
This example of the
one-dimensional block-column
<A NAME="2747"> </A><A NAME="2748"> </A>
distribution mapping can be
expressed in HPF<A NAME="2749"> </A>
by using the following statements:
<PRE> REAL :: A( M, N )
!HPF$ PROCESSORS PROC( 1, P )
!HPF$ TEMPLATE T( M, N + P*NB )
!HPF$ DISTRIBUTE T( *, BLOCK( NB ) ) ONTO PROC
!HPF$ ALIGN A( I, J ) WITH T( I, SRC*NB + J )</PRE>
<P>
A similar example of block-row
distribution <A NAME="2750"> </A>
<A NAME="2751"> </A>
can easily be constructed. For
an <IMG WIDTH=93 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline15189" SRC="img320.gif"> array <I>B</I>,
such an example can be expressed
in HPF<A NAME="2752"> </A> by
using the following statements:
<PRE> REAL :: B( N, NRHS )
!HPF$ PROCESSORS PROC( P, 1 )
!HPF$ TEMPLATE T( N + P*NB, NRHS )
!HPF$ DISTRIBUTE T( BLOCK( NB ), * ) ONTO PROC
!HPF$ ALIGN A( I, J ) WITH T( SRC*NB + I, J )</PRE>
<P>
In ScaLAPACK, the local storage
convention of the one-dimensional
block distributed matrix in every
process's memory is assumed to be
Fortran-like, that is, ``column major''<A NAME="2753"> </A>.
<P>
Determining the number of rows or columns
<A NAME="2754"> </A>
<A NAME="2755"> </A>
of a global band matrix that a specific
process receives is an essential task for
the user. The notation LOC<IMG WIDTH=6 HEIGHT=7 ALIGN=MIDDLE ALT="tex2html_wrap_inline12112" SRC="img15.gif">() is
used for block-row distributions and
LOC<IMG WIDTH=6 HEIGHT=7 ALIGN=MIDDLE ALT="tex2html_wrap_inline12114" SRC="img16.gif">() is used for block-column
distributions. These local quantities
occur throughout the leading comments
of the source code, and are reflected
in the sample argument description in
section <A HREF="node88.html#secargdescband">4.4.7</A>.
<P>
For block distribution, a matrix can be
distributed unevenly. More specifically,
one process in the process grid can receive
an array that is smaller than other processes.
It is also possible that some processes
receive no data. For further information
on one-dimensional block-column or
block-row data distribution, please
refer to section <A HREF="node82.html#sec1dbd">4.4.1</A>.
<P>
<B>Block-Column Distribution</B>: LOC<IMG WIDTH=6 HEIGHT=7 ALIGN=MIDDLE ALT="tex2html_wrap_inline12114" SRC="img16.gif">(N_A)
denotes the number of columns that a process would
receive if N_A columns of a matrix is distributed
over <IMG WIDTH=17 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12162" SRC="img23.gif"> columns of its process row.
<P>
For example, let us assume that the coefficient
matrix <I>A</I> is band symmetric of order <I>N</I> and has
been block-column distributed on a <IMG WIDTH=46 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline15233" SRC="img323.gif">
process grid.
<P>
In the ideal case where the matrix is evenly
distributed to all processes in the process
grid, <IMG WIDTH=170 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline15235" SRC="img324.gif"> and <IMG WIDTH=81 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline15237" SRC="img325.gif">.
Thus, each process receives a block of size <IMG WIDTH=49 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline14839" SRC="img291.gif">
of the matrix <I>A</I>. Therefore,
<P>
LOC<IMG WIDTH=6 HEIGHT=7 ALIGN=MIDDLE ALT="tex2html_wrap_inline12114" SRC="img16.gif">(N_A) = NB_A.
<P>
However, if <IMG WIDTH=170 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline15245" SRC="img326.gif">,
at least one of the processes in the
process grid will receive a block of
size smaller than <IMG WIDTH=49 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline14839" SRC="img291.gif">. Thus,
<PRE><TT> if ( <IMG WIDTH=170 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline15245" SRC="img326.gif"> and <IMG WIDTH=118 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline15251" SRC="img327.gif"> ) then
<P>
processes (0,0), ... , (0,<i>K</i>-1) receive
<P>
LOC<IMG WIDTH=6 HEIGHT=7 ALIGN=MIDDLE ALT="tex2html_wrap_inline12114" SRC="img16.gif">(N_A) = NB_A
<P>
and process (0,<I>K</I>) receives
<P>
LOC<IMG WIDTH=6 HEIGHT=7 ALIGN=MIDDLE ALT="tex2html_wrap_inline12114" SRC="img16.gif">(N_A) = N_A - K <IMG WIDTH=7 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline15263" SRC="img329.gif"> NB_A.
<P>
if <IMG WIDTH=56 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline15265" SRC="img330.gif"> then processes <IMG WIDTH=189 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline15267" SRC="img331.gif"> do
not receive any data.
<P>
end if
<P>
</TT></PRE>
<P>
<B>Block-Row Distribution</B>: LOC<IMG WIDTH=6 HEIGHT=7 ALIGN=MIDDLE ALT="tex2html_wrap_inline12112" SRC="img15.gif">(M_B)
denotes the number of rows that a process would
receive if M_B rows of a matrix is distributed
over <IMG WIDTH=17 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12172" SRC="img24.gif"> rows of its process column.
<P>
Let us assume that the N-by-NRHS right-hand-side
matrix <I>B</I> has been block-row distributed on a
<IMG WIDTH=46 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline15275" SRC="img332.gif"> process grid.
<P>
In the ideal case where the matrix is evenly
distributed to all processes in the process grid,
<IMG WIDTH=178 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline15277" SRC="img333.gif"> and <IMG WIDTH=84 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline15279" SRC="img334.gif">.
Thus, each process receives a block of size <IMG WIDTH=52 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline15281" SRC="img335.gif">
of the matrix <I>B</I>. Therefore,
<P>
LOC<IMG WIDTH=6 HEIGHT=7 ALIGN=MIDDLE ALT="tex2html_wrap_inline12112" SRC="img15.gif">(M_B) = MB_B.
<P>
However, if <IMG WIDTH=178 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline15287" SRC="img336.gif">, then at
least one of the processes in the process grid
will receive a block of size smaller than <IMG WIDTH=52 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline15281" SRC="img335.gif">.
Thus,
<PRE><TT> if ( <IMG WIDTH=178 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline15287" SRC="img336.gif"> and <IMG WIDTH=121 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline15293" SRC="img337.gif"> ) then
<P>
processes t<ex2html_image_mark>#tex2html_wrap_inline15295# receive
<P>
LOC<IMG WIDTH=6 HEIGHT=7 ALIGN=MIDDLE ALT="tex2html_wrap_inline12112" SRC="img15.gif">(M_B) = MB_B
<P>
and process (<I>K</I>,0) receives
<P>
LOC<IMG WIDTH=6 HEIGHT=7 ALIGN=MIDDLE ALT="tex2html_wrap_inline12112" SRC="img15.gif">(M_B) = M_B - K <IMG WIDTH=7 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline15263" SRC="img329.gif"> MB_B.
<P>
if <IMG WIDTH=56 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline15307" SRC="img339.gif"> then processes <IMG WIDTH=190 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline15309" SRC="img340.gif"> do
not receive any data.
<P>
end if
<P>
</TT></PRE><HR><A NAME="tex2html3224" HREF="node84.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3222" 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="tex2html3216" HREF="node82.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3226" 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="tex2html3227" 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="tex2html3225" HREF="node84.html">Local Storage Scheme for </A>
<B>Up:</B> <A NAME="tex2html3223" HREF="node81.html">In-Core Narrow Band and </A>
<B> Previous:</B> <A NAME="tex2html3217" HREF="node82.html">The Block Column and </A>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>
|
