Domain maps creation

[preejackie]

Hi all
I'm new to chapel programming language, I trying to learn it by doing. But I find it difficult to understand the domain type in chapel, I'm wondering how the domains can increase the performance ? It's a index set (contains a set of elements which are used to index the members of other set) - as I know so far.
In c++
we can declare a array like this

  type name[size].

here the index is spanned simply between 0 to size - 1. And the elements are accessed by using this index.
In chapel
we can domain like

  var Dom : domain(1) = {1..n};
  var array : [Dom] int

How this vary from the c-style array declaration ? And what is use of this type ?
I'm completely lost when I reading the docs. I didn't able to understand correctly. Please don't point me to docs.
Next is domain maps
As far as I know domain maps maps the indexes to target localities using distributions like blockdist, cyclicdist etc
I have doubt regarding that ..
That is

  const space = {1..8, 1..8};
  const BlockSpace = Space dmapped Block(boundingBox=Space);
  var  array : [BlockSpace] int ; 

As far as I know it declares a space of 2d 8*8
And distributes it with respect to block distribution and declares an array over that domain. I want to clear one thing that is " whether it creates the array & distributes it " or "It creates a distributed array"?
Please explain me these things (domains & domain maps). I'm facing lot a mistakes when I'm coding these things.
Thank you all

[bradcray]

Hi @Praveenv98 :

The first part of my reply is to note that there's no need to use (named) domains in Chapel if you don't find value in them. That is, if you're accustomed to writing C++ like:

int array[n];

You're welcome to declare your Chapel arrays similarly as:

var array: [0..#n] int;

The main differences between the two being (a) syntax and (b) Chapel supports arbitrary lower and upper bounds on arrays and therefore requires you to specify both. In such cases, you are actually still creating a domain, it's simply anonymous (un-named).

I'm wondering how the domains can increase the performance?

For a simple case like the above, domains shouldn't be expected to increase performance. In such cases, think of them as being a language feature that may or may not provide software engineering conveniences in your code. For instance, in the C code, to iterate over the array and index into it, you'd need to write something like:

for (int i=0; i<n; i++) {
  array[i] = i;
}

whereas by having domains in the language, Chapel supports loops like:

for i in array.domain do
  a[i] = i;

or, if you've named the domain as in your first example above, you could write:

for i in Dom do
  a[i] = i;

Essentially, in this context, domains can be thought of as providing greater ability to reason about or compute on the size, shape, and indices of an array than in C/C++. Domains can also be useful in this context by supporting operators that create new domains from other domains (you said not to point you to documentation, but for users who don't know our documentation as well as you do, here's a pointer to such operations).

How this vary from the c-style array declaration ? And what is use of this type ?

Hopefully I've addressed these questions above.

As far as I know domain maps maps the indexes to target localities using distributions like blockdist, cyclicdist etc

More generally, domain maps specify how to implement a domain, the operations computed on it, any arrays declared in terms of that domain, and operations on such arrays. One common use of domain maps is to distribute domain indices (and array elements) to target locales, but they can also be used to specify how a domain's indices and/or array's elements should be stored and operated upon even within a single memory / target locale. This is perhaps most interesting when using associative or sparse domains where, though even dense rectangular domains can support multiple memory layouts by changing domain maps.

Walking through your example line-by-line:

  const space = {1..8, 1..8};

This first line creates an 8 x 8 domain. Because no domain map is specified, it uses the default domain map which will cause its indices to be stored locally to the current locale. If any arrays were declared over this domain, they would also be local to the current locale.

For your second line, let's take it expression by expression:

  ...dmapped Block(boundingBox=Space);

This expression creates an instance of the Block domain map (or "distribution"). In the current implementation, the Block distribution takes an argument (boundingBox) specifying which indices within the n-dimensional plane should be blocked between the locales as evenly as possible. Since you're giving Space as the argument, it will divide its index set ({1..8, 1..8}) between the locales as evenly as possible. For instance, if you were to run this program using 4 locales, locale 0 would own {1..4, 1..4} from the bounding box, locale 1 would own {1..4, 5..8}, locale 2 would own {5..8, 1..4} and locale 3 would own {5..8, 5..8}. But because distributions are designed to partition the entire n-dimensional plane (2-dimensional in this case since boundingBox was given a 2D domain), locale 0 would actually own {-infinity..4, -infinity..4}, locale 1 would own {-infinity..4, 5..infinity} and so forth. This partitioning will govern the implementation of any domains declared using this domain map. Like the one you declared:

  const BlockSpace = Space dmapped Block(boundingBox=Space);

Here, you're declaring a new domain BlockSpace whose index set will be defined by Space and therefore have the indices {1..8, 1..8}. Yet, because of the dmapped clause, BlockSpace will not be implemented using the default domain map, but rather the block domain map. As a result, its indices will get partitioned according to where they fall on the 2D plane relative to the ownership described just above. And since Space was used to define both BlockSpaces index set and the bounding box for this instance of Block, it'll be partitioned as you'd expect: Locale 0 will own {1..4, 1..4}, locale 1 will own {1..4, 5..8} and so forth. For a contrasting example, if we had written:

  const row0 = {0..0, 1..8} dmapped Block(boundingBox=Space);

then locale 0 would own {0..0, 1..4}, locale 1 would own {0..0, 5..8} and locales 2 and 3 would own nothing since the index set lies completely outside of the portion of the 2D plane that they own.

You can query the ownership of a given domain by writing code like the following:

forall i in BlockSpace do
  writeln(here.id, " owns index ", i);

when running this on 4 locales, you should see output corresponding to the ownership I described above.

OK, so now that you have a distributed domain, you can declare a distributed array over it:

  var  array : [BlockSpace] int ; 

Here, array will be distributed according to BlockSpace's domain map. Thus, when running on 4 locales, each locale will own a 4x4 block of data corresponding to the same index distribution we've been describing above. And this ownership can be queried by doing:

forall a in array do
  writeln(here.id, " owns ", a);

or:

forall (a,i) in zip(array,BlockSpace) do
  writeln(here.id, " owns a[", i, "] whose value is ", a);

Back to your questions:

want to clear one thing that is " whether it creates the array & distributes it " or "It creates a distributed array"?

I would say that it creates a distributed array. Specifically, it does not create an 8x8 array on one locale prior to distributing it to multiple locales. Rather, it creates the per-locale 4x4 blocks of data (when run on 4 locales) from the outset.

Of course, to see the domain and array being distributed, you must compile and run with multiple locales. If compiling and running with a single locale, that locale will naturally own all of the indices and array elements of all of the domains and arrays above.

Back to your earlier question:

I'm wondering how the domains can increase the performance?

In the distributed setting, the use of domains can increase performance as follows:

var A, B, C: [BlockSpace] real;
forall (a, b, c) in zip(A, B, C) do
  a = b + c;

Since, at compile time or execution time, the implementation can see that A, B, and C all share the same domain, it can know that the three arrays are implemented similarly and therefore that no communication between locales is necessary to implement each iteration of the loop in question. In our current implementation, we (sometimes) make use of such information at execution time to accelerate the implementation. In a better implementation of Chapel, the compiler could make use of such knowledge to eliminate any runtime overheads or checks to determine that the arrays are aligned (similarly distributed). In our previous work on the ZPL language, we made great use of such static information for cases like this, and we designed Chapel to be able to perform such optimizations as well, though it remains future work for our project.

[preejackie]

It's wonderful answer @bradcray,
Thank you for reply. Now i got a new visualization and understanding of domains & domain maps. This is more detailed than the documentation, Please add this link somewhere, so people new to chapel will be happy. I forwarding to look into implementation of domains and it's associate "array". Could you give me some tips where to look for that in the source code .
Thank you so much
@bradcray

[bradcray]

Please add this link somewhere, so people new to chapel will be happy.

I'm curious what documentation on domains and arrays you read prior to posting this, as I feel fairly certain that I haven't said anything here which isn't already documented elsewhere. So knowing what you read (and didn't read) would be useful to understand where you got stuck and how to help others who might feel similarly stuck.

I forwarding to look into implementation of domains and it's associate "array". Could you give me some tips where to look for that in the source code .

The code that implements domains and arrays is not particularly friendly or accessible and is long overdue for some massive clean-up and refactoring. All domains and arrays are implemented using records in this $CHPL_HOME/modules/internal/ChapelArray.chpl.

Specifically, each domain is implemented with an instance of a _domain record and each array with an _array record. But for the most part, these records are just wrappers around the core classes that implement domains and arrays which are defined by the domain maps themselves. The instance of the class defines the behavior is referred to from these wrappers by the pseudo-field _value.

For instance, rectangular domains and arrays implemented using the default domain map are defined in this $CHPL_HOME/modules/internal/DefaultRectangular.chpl

Specifically by the DefaultRectangularDom and DefaultRectangularArr classes. Other domain maps can be found in $CHPL_HOME/modules/internal/Default*.chpl, $CHPL_HOME/modules/layouts/.chpl and $CHPL_HOME/modules/dists/.chpl. Typically these classes inherit from base classes defined in $CHPL_HOME/modules/internal/ChapelDistribution.chpl

[preejackie]

@bradcray
I have read the primers in documentation. Your way explaining is good. Sometimes hearing from people will help to understand better!
Thank you for the links

[bradcray]

The primers are meant to just give a taste of language features, not to be a definitive explanation. For more complete coverage of domains and arrays, I'd recommend (1) the language specification, and (2) the online domain and array documentation. The former is a reasonably complete introduction to the concepts while the latter focuses on their capabilities from a library interface perspective.

For more on domain maps, I'd suggest the two publications (and/or their slides) located on the Chapel publications page, entitled "Authoring User-Defined Domain Maps in Chapel" and "User-Defined Distributions and Layouts in Chapel: Philosophy and Framework."

I'd also generally recommend not requesting "don't point me to documentation" without being clearer about what documentation you have or haven't read. When existing documents can answer questions for you, it'd save all of us time if you'd let people point you to them.

[mppf]

I havn't read all of this discussion and don't know anything about the context for it. However, it seems to me that this kind of how-do-I-use-Chapel question fits better on Stack Overflow than here as a GitHub issue.

[preejackie]

Sorry @mppf
I don't know whether there is a chapel page in stack-overflow. So I post an issue.
Thank you