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>Glossary</TITLE>
<META NAME="description" CONTENT="Glossary">
<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="tex2html4522" HREF="node187.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html4520" HREF="node7.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html4516" HREF="node185.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html4524" 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="tex2html4525" 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="tex2html4523" HREF="node187.html">Specifications of Routines</A>
<B>Up:</B> <A NAME="tex2html4521" HREF="node7.html">Guide</A>
<B> Previous:</B> <A NAME="tex2html4517" HREF="node185.html">Quick Reference Guide to </A>
<BR> <P>
<H1><A NAME="SECTION041200000000000000000">Glossary</A></H1>
<A NAME="7174"> </A>
<P>
The following is a glossary of terms and notation used throughout this users
guide and the leading comments of the source code.
The first time notation from this glossary appears in the text, it will
be <EM>italicized</EM>.
<P>
<UL>
<LI>
<B>Array descriptor</B>: Contains the information required to establish
the mapping between a global matrix entry and its corresponding process
and memory location<A NAME="7183"> </A><A NAME="7184"> </A>.
<P>
The notations x_ used in the entries of the array descriptor denote
the attributes of a global matrix. For example, M_ denotes the
number of rows, and M_A specifically denotes the number of rows in
global matrix A. See sections <A HREF="node73.html#secdescriptors">4.2</A>,
<A HREF="node77.html#secdesc1">4.3.3</A>, <A HREF="node86.html#secdesc501">4.4.5</A>, <A HREF="node87.html#secdesc502">4.4.6</A>,
and <A HREF="node91.html#secdesc601">4.5.1</A> for complete details.
<LI>
<B>BLACS</B><A NAME="7191"> </A>: Basic Linear Algebra Communication
Subprograms, a message-passing library designed for linear algebra.
They provide a portability layer for communication between ScaLAPACK
and message-passing systems such as MPI and PVM, as well as native
message-passing libraries such as NX and MPL. See section <A HREF="node15.html#secBLACS">1.3.4</A>.
<LI>
<B>BLAS</B><A NAME="7194"> </A>: Basic Linear Algebra
Subprograms [<A HREF="node189.html#blas3">57</A>, <A HREF="node189.html#blas2">59</A>, <A HREF="node189.html#blas1">93</A>], a standard for subroutines for common
linear algebra computations such as dot-products, matrix-vector
multiplication, and matrix-matrix multiplication. They provide
a portability layer for computation. See section <A HREF="node13.html#secBLAS">1.3.2</A>.
<LI>
<B>Block size</B>: The number of contiguous rows or columns of a global
matrix to be distributed consecutively to each of the processes in the
process grid. The block size is quantified by the notation <IMG WIDTH=83 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline14817" SRC="img286.gif">, where <I>MB</I> is the row block size and <I>NB</I> is the column block size.
<P>
The distribution block size can be square, <I>MB</I>=<I>NB</I>, or rectangular,
<IMG WIDTH=85 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline20032" SRC="img768.gif">.
<B>Block size</B><A NAME="7199"> </A> is also referred to as the
<B>partitioning unit</B><A NAME="7201"> </A>
or <B>blocking factor</B><A NAME="7203"> </A>.
<LI>
<B>Distributed memory computer</B>: A term used in two senses:
<UL>
<LI> A computer marketed as a distributed memory computer
(such as the Cray T3 computers, the IBM SP computers, or the Intel
Paragon), including one or more message-passing libraries.
<LI> A distributed shared-memory computer (e.g., the Origin 2000)
or network of workstations (e.g., the Berkeley NOW) with
message passing.
</UL>
ScaLAPACK delivers high performance on these computers provided that
they include certain key features such as an efficient message-passing
system, a one-to-one mapping of processes to processors,
a gang scheduler and a well-connected communication network.
<LI>
<B>Distribution</B><A NAME="7208"> </A>: Method by which the entries of a global
matrix are allocated among the processes, also commonly referred to as
<B>decomposition</B><A NAME="7210"> </A><A NAME="7211"> </A> or <B>data layout</B><A NAME="7213"> </A>. Examples
of distributions
used by ScaLAPACK include block and block-cyclic distributions and these
will be illustrated and explained in detail later.
<P>
Data distribution in ScaLAPACK is controlled primarily by the
process grid and the block size.
<LI>
<B>Global</B>: A term ``global''<A NAME="7215"> </A><A NAME="7216"> </A> used in two ways:
<UL>
<LI> To define the mathematical matrix<A NAME="7218"> </A>, e.g. the global matrix <I>A</I>.
<LI> To identify arguments that must have the same value on all
processes<A NAME="7219"> </A>.
</UL>
<LI>
<B><IMG WIDTH=44 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12124" SRC="img19.gif">(K_)<A NAME="8187"> </A></B>:
Number of columns that a process receives if <IMG WIDTH=23 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline12126" SRC="img20.gif"> columns of
a matrix are distributed over <I>c</I> columns of its process row.
<P>
To be consistent in notation, we have used a ``modifying
character'' subscript on <I>LOC</I> to denote the dimension of the process grid
to which we are referring. The subscript ``r'' indicates
``row'' whenever it is appended to <I>LOC</I>; likewise, the subscript
``c'' indicates ``column'' when it is appended to <I>LOC</I>.
<P>
The value of <IMG WIDTH=44 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12124" SRC="img19.gif">() may
differ from process to process within the process grid.
For example, in figure <A HREF="node78.html#figmat9">4.6</A> (section <A HREF="node78.html#sec2dbsdexample">4.3.4</A>), we
can see that for process (0,0) <IMG WIDTH=44 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12124" SRC="img19.gif">(N_)= 4; however, for process (0,1)
<IMG WIDTH=44 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12124" SRC="img19.gif">(N_) = 3.
<LI>
<B><IMG WIDTH=44 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12132" SRC="img21.gif">(K_)</B><A NAME="8189"> </A>:
Number of rows that a process would receive if <IMG WIDTH=23 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline12126" SRC="img20.gif"> rows of a matrix
are distributed over <I>r</I> rows of its process column.
<P>
To be consistent in notation, we have used a ``modifying
character'' subscript on <I>LOC</I> to denote the dimension of the process grid
to which we are referring. The subscript ``r'' indicates
``row'' whenever it is appended to <I>LOC</I>; likewise, the subscript
``c'' indicates ``column'' when it is appended to <I>LOC</I>.
<P>
The value of <IMG WIDTH=44 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12132" SRC="img21.gif">() may differ from process
to process within the process grid.
For example, in figure <A HREF="node78.html#figmat9">4.6</A> (section <A HREF="node78.html#sec2dbsdexample">4.3.4</A>), we
can see that for process (0,0) <IMG WIDTH=44 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12132" SRC="img21.gif">(M_)= 5; however, for process (1,0)
<IMG WIDTH=44 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12132" SRC="img21.gif">(M_) = 4.
<LI>
<B>Local</B>: A term <A NAME="7236"> </A><A NAME="7237"> </A> used in two ways:
<UL>
<LI> To express the array elements or blocks stored on each
process, e.g., the local part of the global matrix <I>A</I>, also referred
to as the <B>local array</B><A NAME="7240"> </A>. The size of the local array may differ
from process to process.
See section <A HREF="node28.html#example1">2.3</A> for further details.
<LI> To identify arguments that may have different values on
different processes.<A NAME="7242"> </A>
<P>
</UL>
<LI>
<B>Local leading dimension</B><A NAME="7245"> </A><A NAME="7246"> </A>
of a local array: Specification of entry size for local array. When a global array
is distributed among the processes in the process grid, locally the
entries are stored in a two-dimensional array, the size of which may
vary from process to process. Thus, a leading dimension needs to be
specified for each local array.
For example, in Figure <A HREF="node28.html#figgrida9">2.2</A> in
section <A HREF="node28.html#example1">2.3</A>, we can see that for process (0,0) the local
leading dimension of the local array <I>A</I> (denoted <IMG WIDTH=58 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline12116" SRC="img17.gif">) is 5, whereas
for process (1,0) the local leading dimension of local array <I>A</I>
is 4.
<LI>
<B><I>MYCOL</I><A NAME="7249"> </A></B>: The calling process's column coordinate in the
process grid. Each process within the process grid is uniquely
identified by its process coordinates (<I>MYROW</I>, <I>MYCOL</I>).
<LI>
<B><I>MYROW</I><A NAME="7250"> </A></B>: The calling process's row coordinate in the
process grid. Each process within the process grid is uniquely
identified by its process coordinates (<I>MYROW</I>, <I>MYCOL</I>).
<LI>
<B><I>P</I><A NAME="7251"> </A></B>: The total number of processes in the process grid,
i.e., <IMG WIDTH=94 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline17184" SRC="img427.gif">.
<P>
In terms of notation for process grids, we have used a ``modifying
character'' subscript on <I>P</I> to denote the dimension of the process grid
to which we are referring. The subscript ``r'' indicates
``row'' whenever it is appended to <I>P</I>, and thus <IMG WIDTH=17 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12172" SRC="img24.gif"> is the number
of process rows in the process grid. Likewise, the subscript ``c'' indicates
``column'' when it is appended to <I>P</I>, and thus <IMG WIDTH=17 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12162" SRC="img23.gif"> is the number
of process columns in the process grid.
<LI>
<B><IMG WIDTH=17 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12162" SRC="img23.gif"><A NAME="8193"> </A></B>: The number of process columns in the process
grid (i.e., the second dimension of the two-dimensional process grid).
<LI>
<B><IMG WIDTH=17 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12172" SRC="img24.gif"><A NAME="8194"> </A></B>: The number of process rows in the process
grid (i.e., the first dimension of the two-dimensional process grid).
<LI>
<B>PBLAS</B><A NAME="7261"> </A>: A distributed-memory version of the BLAS (Basic
Linear Algebra Subprograms), also referred to as the <B>Parallel BLAS</B>
or <B>Parallel Basic Linear Algebra Subprograms</B>. Refer to section <A HREF="node14.html#secPBLAS">1.3.3</A> for further details.
<LI>
<B>Process</B>: Basic unit or thread of
execution<A NAME="7266"> </A>
that minimally includes
a stack, registers, and memory. Multiple processes may share a physical
processor. The term processor<A NAME="7267"> </A> refers to the actual hardware.
<P>
In ScaLAPACK, each process is treated as if it were
a processor: the process must exist for the
lifetime of the ScaLAPACK run, and its execution should affect other
processes' execution only through the use of message-passing calls.
With this in mind, we use the term process in all sections of this
users guide except those dealing with timings. When discussing timings,
we specify processors as our unit of execution, since speedup will
be determined largely by actual hardware resources.
<P>
In ScaLAPACK, algorithms are presented in terms of <I>processes,</I>
rather than physical processors. In general there may be several
processes on a processor, in which case we assume that the runtime
system handles the scheduling of processes. In the absence of such
a runtime system, ScaLAPACK assumes one process per processor.
<LI>
<B>Process column</B><A NAME="7270"> </A>: A specific
column of processes within the two-dimensional process grid. For
further details, consult the definition of <B>process grid</B>.
<LI>
<B>Process grid</B><A NAME="7273"> </A><A NAME="7274"> </A>: The way we logically view a parallel machine
as a one- or two-dimensional rectangular grid of processes.
<P>
For two-dimensional process grids, the variable
<IMG WIDTH=17 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12172" SRC="img24.gif"><A NAME="8195"> </A> is used
to indicate the number of rows in the process grid
(i.e., the first dimension of the two-dimensional process grid).
The variable <IMG WIDTH=17 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12162" SRC="img23.gif"><A NAME="8196"> </A> is
used to indicate the number of columns in the process
grid (i.e., the second dimension of the two-dimensional process grid).
The collection of processes need not physically be connected in the
two-dimensional process grid.
<P>
For example, the following figure shows six processes mapped
to a <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline14922" SRC="img304.gif"> grid, where <IMG WIDTH=50 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12422" SRC="img43.gif"> and <IMG WIDTH=49 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline12424" SRC="img44.gif">.
<P>
<P><IMG WIDTH=185 HEIGHT=133 ALIGN=BOTTOM ALT="figure7281" SRC="img769.gif"><P>
<P>
A user may perform an operation within a <B>process row</B> or
<B>process column</B> of the process grid. A <B>process row</B>
refers to a specific row of processes within the process grid, and
a <B>process column</B> refers to a specific column of
processes with the process grid. In the example,
<B>process row 0</B> contains the processes with
natural ordering <B>0, 1,</B> and <B>2</B>, and <B>process column 0</B> contains
the processes with natural ordering <B>0</B> and <B>3</B>.
<P>
For further details, please refer to section <A HREF="node70.html#secgrid">4.1.1</A>.
<LI>
<B>Process row</B><A NAME="7316"> </A>: A specific
row of processes within the two-dimensional process grid. For
further details, consult the definition of <B>process grid</B>.
<LI>
<B>Scope</B><A NAME="7319"> </A>: A term used in two ways:
<UL>
<LI> The portion of the process grid within which an operation
is defined. For example, in the Level 1 PBLAS, the resultant output array
or scalar will be global or local within a process column or row of
the process grid, and undefined elsewhere<A NAME="7321"> </A>.<BR>
<P>
Equivalently, in Appendix <A HREF="node185.html#chapqrefblacs">D.3</A>, scope indicates the processes
that participate in the broadcast or global combine operations. Scope
can equal ``all'', ``row'', or ``column''<A NAME="7323"> </A>.
<LI> The portion of the parallel program within which the
definition of an argument remains unchanged. When the scope of an
argument is defined as global<A NAME="7324"> </A>, the argument must have the same value
on all processes. When the scope of an argument is defined as local<A NAME="7325"> </A>,
the argument may have different values on different processes<A NAME="7326"> </A>.
</UL>
Refer to section <A HREF="node72.html#secscope">4.1.3</A> for further details.
<P>
</UL>
<P>
<HR><A NAME="tex2html4522" HREF="node187.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html4520" HREF="node7.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html4516" HREF="node185.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html4524" 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="tex2html4525" 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="tex2html4523" HREF="node187.html">Specifications of Routines</A>
<B>Up:</B> <A NAME="tex2html4521" HREF="node7.html">Guide</A>
<B> Previous:</B> <A NAME="tex2html4517" HREF="node185.html">Quick Reference Guide to </A>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>
|
