(2D) Array Storage schemes

Users
1

)Currently chapel supports row-major (by default) and column-major (by explicit usage).

Chapel also now has support for Sparse storage although I have no experience with it and I believe that this is defined as being in the early prototype stage. I will need to install 1.29 to get experience with this because it seems quite new.

One can also implement other schemes that one can implement oneself such as the use Illiffe vectors, packed, banded, or skyline. What should one consider if doing this to ensure that self-implemented schemes parallelize well in a forall.

I am particularly interested in what I need to consider in the layout along anti-diagonal bands or waves, i.,e. where say the 16 elements of a 4*4 2D 1-offset array would be stored in order of

 1  3  6 10 15 21
 2  5  9 14 20 26
 4  8 13 19 25 30
 7 12 18 24 29 33
11 17 23 28 32 35
16 22 27 31 34 36

The name of this ordering, I do not know. I will use it in a Jacobi SVD algorithm shortly and it can be used to help parallelize an SOR algorithm and anything else which demands that the reduction of the (i,j)'th elements demands that (i-1,j) and (i,j-1) are already reduced.

Thanks - Damian

2

Hi Damian,

I can see trying out a wavefront parallelization where the loop computes the SOR values using anti-diagonal waves, but my intuition is that the overhead of putting the data into that organization wouldn’t be worth it. Do you have some preliminary results that seem to indicate changing the storage to anti-diagonals would improve the performance? Does/Would it better enable using vector loads?

Thanks,

Michelle

PS – I played around with these kinds of wavefront computations a lot in the past (http://dl.acm.org/authorize?N10511) and some more recently, http://cgi.cs.arizona.edu/~mstrout/Papers/Papers19/IJHPCN-paper-Using_the_loop_chain_abstraction_to_schedule_across_loops_in_existing_code.pdf.

3

I do not have any preliminary results.

What I saw with row-major storage was that a 36-core job ran slower than a 24 core job so I assumed I was getting lots of cache misses.

Hence I was reaching out for suggestions and your work suggests I may be wasting my time. I will read them in more detail over the break. Loop chain abstraction. Got to wrap my head around that one.

Thanks - Damian

P.S. A 52-core job takes even longer.

P.P.S. Thanks for those references. I read both. The second was seriously heavy. My brain hurts.
I will revisit them later and see if the more details manage to permeate the little grey cells in my head.

4

Hi Damian: I did not know that Chapel allowed column-major: could you post how to specify this for an array, or point me to where it is in the documentation ? (I could not find it)

Thanks

Nelson

5

@nelsonluisdias see the documentation on LayoutCS . In a nutshell:

use LayoutCS;
var D = {0..#n, 0..#m};  // a default-distributed domain
var CSC_Domain : sparse subdomain(D) dmapped CS(compressRows=false);
var CSC_Array: [CSC_Domain] real;
6

Vass, I think Nelson just wants a column-major layout for a dense matrix.

Nelson, I cannot find the reference or specification. It is mentioned in some tutorials but never really spelt out. See

https://courses.cs.washington.edu/courses/csep524/13wi/SC12-6-DomainMaps.pdf

I find Chapel's current documentation pretty well frustrating impossible to search so I am not much use. Maybe Vass or Brad can point you at it. It is related to Domain Maps and Index Sets - I think.

7

Thanks!

8

Following up on Damian, yes I was wondering about some simple syntax like

var D = column_major {1..M,1..N} ;
var A: [D] real;

but I am definitely not suggesting it! Again, thanks for the replies :slight_smile:

9

@nelsonluisdias sorry we have not implemented column-major layout for dense matrices. I can think of some workarounds, however it depends on your application.

@damianmoz I agree, much of our documentation leaves much to be desired. Thank you for working to contribute improvements for documentation of C types.

10

Domain Maps already provide the syntax. You do not need to invent something new.. I apologize that U cannot find the example which was supposed to show how to do column-major ordering. But, I am really bad at being able to search the current documentation. Give me a PDF document any day.

I was also amazed but I could not even really find where it is stipulated that the Chapel default is row-major. Hmmm.

Somebody far more knowledgable than me needs to reply here.

11

@vass, it was curiousity, not necessity. I am perfectly happy to use row-major order, which in my opinion is actually more natural. I do not think that Chapel needs to have both ways.

cheers

Nelson

12

@nelsonluisdias thanks for clarifying.

Our LAPACK module has enum lapack_memory_order which allows us to communicate column- or row-majority to the underlying LAPACK implementation.

https://chapel-lang.org/docs/main/modules/packages/LAPACK.html#LAPACK.lapack_memory_order

13

I use row-major order exclusively.

That LAPACK documentation might have confused me that Chapel supported column major ordering. Or maybe I was reading too much into that Domain Map presentation which dates back to 2014.

  • Enjoy the Festive Season and the New Year celebrations. Drive safely
1 Like