-
Notifications
You must be signed in to change notification settings - Fork 414
/
distributions.chpl
347 lines (281 loc) · 13.1 KB
/
distributions.chpl
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
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
// Distributions
/*
This primer introduces Chapel's features for distributed domains and
arrays, illustrating them using a few of Chapel's standard
distributions.
Local vs. Distributed Domains and Arrays
----------------------------------------
In Chapel, *distributions* are recipes for implementing arrays and
their index sets (*domains*). Each distribution indicates how a
domain's indices should be mapped to locales. It also specifies how
arrays declared over such distributed domains should be stored in
each locale's memory, accessed, iterated over, etc. This primer
will assume you already have some familiarity with Chapel's concepts
of :ref:`arrays <primers-arrays>`, :ref:`domains <primers-domains>`,
and :ref:`locales <primers-locales>`; if not, refer to their
respective primers for more information.
By default, when a domain is declared, all of its indices are owned
by the locale on which the current task is running. Similarly, an
array declared over such a domain will store all of its elements in
the current locale's memory. For this reason, we say that Chapel
domains and arrays are *local* by default, since they only use a
single locale's resources for their implementation. However, as
this primer will demonstrate, domains and arrays can also be
declared in terms of a distribution as a means of leveraging
multiple locales, their memory, and processors.
Crucially, the operations supported by domains and arrays in Chapel
are independent of whether they are stored on a single locale or
distributed across multiple. The only difference is how and where
the operations are implemented, which can have impacts on
performance and scalability—positive or negative. This property
makes it easy to implement and debug an algorithm on a single node,
and then deploy it on a large-scale supercomputer. It also permits
you to change the distributions used by a program to alter its
implementation.
Properties of Typical Distributions
-----------------------------------
Distributions for rectangular arrays can be thought of as
distributing a *d*-dimensional space of possible indices over a
*d*-dimensional array of locales. Most distribution types are
characterized by this *rank*, *d*, as well as the index type
(*idxType*) used to represent indices in each dimension. For
example, a 3D distribution might map ``(int, int, int)`` indices to
a 3D array of locales, defining which one owns any given index ``(i,
j, k)``. It would also specify how the array elements corresponding
a locale's local indices are stored in memory.
Typical Chapel distributions use an "owner computes" model in which
each locale owns a subset of a domain's indices as well as the array
elements corresponding to those indices. When ``forall`` loops or
other data-parallel operations are executed across such distributed
domains and arrays, each locale executes the iterations
corresponding to its indices and array elements in parallel, using
its locally available processor cores.
Multiple domains may share a single distribution, even if their
index sets are different. For typical distributions, this ensures
that a given index ``(i, j, k)`` is owned by the same locale for all
of the domains, implying that computations on matching indices will
not require communication. Domains with this property are said to
be *aligned*. When multiple arrays are declared in terms of a
single distributed domain, they are guaranteed to be aligned, since
they all share the same distribution.
Getting Started with Block and Cyclic Distributions
---------------------------------------------------
In this primer, we'll introduce two common distributions: the first
maps indices to locales using contiguous rectilinear blocks; the
other deals indices out to locales in a round-robin fashion. To use
these distributions in a Chapel program, their respective modules
must be used or imported:
*/
use BlockDist, CyclicDist;
//
// A third and somewhat atypical distribution, ``replicatedDist``, is
// covered in :ref:`its own primer <primers-replicated>`. It does not
// adhere to some of the characterizations described as "typical"
// above.
//
// For each distribution in this primer, we'll create a distributed
// domain and array using that distribution. Then we'll initialize
// the array using the IDs of the locales owning the elements to
// illustrate how indices are mapped to locales. Running this example
// on 6 locales does a nice job of illustrating the distribution's
// characteristics.
//
// By default, these distributions will target the entire array of
// ``Locales`` on which the program is running, heuristically
// reshaping them into a *d*-dimensional grid whenever *d* is greater
// than 1. When a user wants to exert more control over how the
// locales are targeted—for example to specify the number of locales
// in each dimension, or to target just a subset of the locales—they
// may create their own array of locales and pass that in as an
// argument, as we'll see below.
//
//
// First, we'll declare the problem size to use for our 2D domains
// and arrays, configurable from the command-line:
//
config const n = 8;
//
// Next, we'll declare a 2-dimensional domain ``Space``, which will
// form the basis of our distributed domains.
//
const Space = {1..n, 1..n};
// The Block Distribution
// ----------------------
//
// The ``blockDist`` distribution partitions a *d*-dimensional
// bounding box across the *d*-dimensional target locale array. The
// bounding box is divided into roughly equal-size block sections,
// where each locale owns one of them.
//
// In this example, we declare a 2-dimensional block distribution
// whose bounding box is defined by ``Space``. We then use that
// distribution instance to create a distributed domain and an array
// over the domain:
//
const BlkDist = new blockDist(boundingBox=Space);
const BlockSpace = BlkDist.createDomain(Space);
var BA: [BlockSpace] int;
/*
Since the code above only uses a single domain and array, it could
also be written in one of the following ways for convenience:
.. code-block:: chapel
// create the domain using an anonymous distribution
const BlockSpace = blockDist.createDomain({1..n, 1..n});
const BA: [BlockSpace] int;
or:
.. code-block:: chapel
// create the array using an anonymous distribution and domain
const BA = blockDist.createArray({1..n, 1..n}, int);
Or, in both versions, `Space` could be substituted for the domain
literal, if preferred.
One motivation for declaring explicit distribution and domain
variables as we've done here is to support the creation of aligned
domains and arrays. Another is to amortize the overheads incurred
by such types, since creating any distributed object requires
communication and memory.
*/
// Reasoning About Ownership
// -------------------------
//
// To illustrate how our block-distributed domain and array are mapped
// to locales, let's use a forall loop that assigns each array element
// the locale ID that stores that index/element/iteration.
//
forall ba in BA do
ba = here.id;
// This loop relies on Chapel's owner-computes model by querying the
// locale on which a given iteration is running using ``here.id``. As
// mentioned above, the forall loop will be executed such that each
// locale will use its local processor cores to execute the iterations
// that were mapped to it. As a result, each value of ``BA`` will end
// up storing the ID of the locale that owns it. We can see this
// ownership map by printing the array out:
writeln("Block Array Ownership Map");
writeln(BA);
writeln();
// We can also determine which indices a given locale owns using the
// ``.localSubdomain()`` query. This method returns a non-distributed
// domain representing the indices that are local to the current
// locale. As an example, the following line prints the indices that
// locale 0 owns, since that is where the current task is running:
writeln("Locale 0 owns the following indices of BA: ", BA.localSubdomain());
writeln();
// As another example, the following code iterates over all the
// locales, querying the local indices and checking that the
// corresponding array elements have the expected value:
coforall L in Locales {
on L {
const myIndices = BA.localSubdomain();
for i in myIndices {
if BA[i] != L.id then
halt("Error: incorrect locale id");
}
}
}
// Creating an Aligned Domain
// --------------------------
// Domains declared in terms of a ``blockDist`` distribution can also
// include indices outside of the bounding box. That is, the bounding
// box is only used to compute a partitioning of the complete
// *d*-dimensional space of indices and does not impose a constraint
// on legal domain indices. Any indices located outside the bounding
// box will be mapped to the locale that owns the nearest index within
// it. For example, we can declare a larger domain than
// ``BlockSpace`` as follows:
const BigBlockSpace = BlkDist.createDomain({0..n+1, 0..n+1});
// In this case, the rows and columns numbered ``0`` and ``n+1`` fall
// outside of the bounding box. As a result, indices like ``(0, i)``
// will be owned by the same locale that owns ``(1, i)`` within the
// box. Similarly, index ``(n+1, 0)`` will be owned by the locale
// that owns ``(n, 1)``. Because ``BigBlockSpace`` shares its
// distribution with ``BlockSpace``, we know that any indices common to
// both domains will be owned by the same locale, and that the domains
// are *aligned*.
// Specifying Target Locales
// -------------------------
//
// As mentioned above, most Chapel distributions support an optional
// ``targetLocales`` argument that permits you to specify your own
// array of locales to be targeted. In general, the *targetLocales*
// argument will match the rank of the distribution. For example, to
// block-distribute a domain such that each locale owns a block of
// rows but all of the columns, we can create a ``numLocales x 1``
// view of the locale set as follows:
//
// We start by creating our own ``MyLocales`` array of locale values.
// Here, we use the standard array ``reshape()`` procedure for
// convenience. More generally, this array can be declared and
// created like any other.
//
var MyLocales = reshape(Locales, {0..<numLocales, 0..0});
//
// Then we declare a new distribution, domain, and array that makes
// use of this arrangement of the locales:
//
const BlkDist2 = new blockDist(boundingBox=Space, targetLocales=MyLocales);
const BlockSpace2 = BlkDist2.createDomain(Space);
var BA2: [BlockSpace2] int;
//
// Now we can do a similar computation as before to see where each
// domain index/array element ended up:
//
forall ba2 in BA2 do
ba2 = here.id;
writeln("Block Array Ownership Map");
writeln(BA2);
writeln();
//
// We can also use the ``targetLocales()`` on any array to query the
// locales array to which it's mapped:
//
forall (l, ml) in zip(BA2.targetLocales(), MyLocales) do
if l != ml then
halt("Error: BA2.targetLocales() should equal MyLocales");
// The Cyclic Distribution
// -----------------------
//
// Next, we'll run through a similar example for the ``cyclicDist``
// distribution. This distribution also maps indices of
// *d*-dimensional space out to a set of target locales arranged in a
// conceptual *d*-dimensional grid. However, where ``blockDist``
// distributes contiguous blocks of indices, ``cyclicDist`` deals
// indices to locales in a round-robin fashion. A designated
// ``startIdx`` is given to the initial locale, and others are dealt
// out cyclically in each dimension from there.
const CycDist = new cyclicDist(startIdx=Space.low);
const CyclicSpace = CycDist.createDomain(Space);
var CA: [CyclicSpace] int;
/*
As with ``blockDist``, these declarations could be shortened to one of
the following expressions for convenience:
.. code-block:: chapel
const CyclicSpace = cyclicDist.createDomain({1..n, 1..n});
const CA: [CyclicSpace] int;
or:
.. code-block:: chapel
const CA = cyclicDist.createArray({1..n, 1..n}, int);
*/
// We can then compute which locale owns each index as before:
forall ca in CA do
ca = here.id;
writeln("Cyclic Array Ownership Map");
writeln(CA);
writeln();
//
// And query the indices owned by a given locale. Note that when
// using the ``localSubdomain()`` query with ``cyclicDist``, the
// result will be a strided set of indices for any dimension that has
// more than one target locale due to the round-robin nature. For
// example, locale 0's ownership of CA is:
//
writeln("Locale 0 owns the following indices of CA: ", CA.localSubdomain());
// However, despite the fact that the logical indices owned by a
// locale are strided, the array elements will still be stored
// compactly in a dense block of memory.
// Conclusion
// ----------
// That wraps up this brief introduction to distributions in Chapel
// and their use in declaring distributed domains and arrays. Keep in
// mind that while we demonstrated only very trivial computations in
// this example, all of Chapel's rich set of domain and array
// operations are available whether they are local or distributed.