Mathematics of arrays

Some weeks ago a group was created on Slack that is discussing the possibilities of “mathematics of arrays” (MoA) within the context of Fortran. The idea of this methodology is to express algorithms in such a way that they are independent of the number of dimensions, which will make it easier for the compiler (both the MoA component and the regular compiler) to optimise the program. As the theory is fairly abstract, the initiator of this group Lenore Mullin, is preparing an introduction to the theory and its applications.

If you are interested, let us know or join the Slack channel, “MoA Global Team”.

To get a bit better acquainted with the idea, here are a few references:
https://docs.google.com/presentation/u/0/d/1g4TQB57NbmueIcl4icnkqIlVU5xSnB6Fkr-9IW8MzTA/mobilepresent

9 Likes

Thanks for sharing. On a side note, the google docs link requires explicit access request.

1 Like

Hm, I think I encountered that myself as well, but it has been a while :blush:. There are a few more documents and links shared. It is easiest to scan the discussion.

To help everyone:
If we can define Fortran operations (including intrinsics) in MoA, (perhaps starting with a subset), we could easily optimize the Abstract Syntax Tree independent of the compilation
step. Actually, since MoA defines operations using shapes and the psi indexing function we could easily explore new functionality, e.g. higher dimension arrays, binary transpose, or whatever. I’d love to help Fortran be the ideal array language needed for Exascale, verifying the equivalence of programs, using MoA to “dimension lift” to map to arbitrary architectures. MoA can do this because the theory is all about indexing: the machine is viewed as arrays also. Hoping to meet more of you.

7 Likes

Here is another good read. I am presently extending this work to GPUs.

4 Likes

Welcome, @Lenore!

1 Like

Hello @Lenore Mullin!

Gary Klimovicz (@gak) mentioned your work recently here: FPGA Hardware acceleration - #6 by gak

Upon searching more, I found this introductory article you co-authored quite helpful for understanding why this matters:

I would be interested :slight_smile: . However, I couldn’t join the slack channel (no idea how to join it).

If anyone wants to join the Slack channel, let me know. Please give me your desired email.
Also to help motivate others:
Don’t be overwhelmed by notation etc. Except for a few things, Fortran has most of the semantics to enable MoA optimizations. So Cshift in Fortran is rotate in MoA. MoA has n-dimensional generality and all operations compose (index composition, what I call psi reduction) reduce to a normal form in the mathematical sense. This allows us to prove two or more programs are equivalent because they reduce to the same normal form. We can also prove that any program formulated in MoA terminates, i.e. is decidable. Also, important mathematically. With what I call “dimension lifting” we can continue to use shapes to map to architectural components viewed as array and indexing, e.g. a register is a vector, threads are vectors, registers can be scalars, etc. The purpose of any lectures is to motivate, use, and bring mathematical prowess to Fortran.

Hoping to generate interest and things that came to mind.

There are so many array languages vying to be “the” array language. Fortran has been around
for a while, has grown, and is used by many. I know there is an enhanced subset that is based
on mathematics, and with mathematics there are no debates. Furthermore, much, if not most, can be automated to assist compilation to hardware or software. Hoping Fortran folks attend an intro lecture to discuss these topics.

Would love to attend a lecture. When and how?

I’ll add you to the general group as well as moafortan

May I have your email. You can send to me at Lenore.mullin@gmail.com or arraylady@gmail.com

1 Like

Thanks for the post and welcome @Lenore to the forum!

As you know, I am very interested in exploring this avenue for LFortran. We are making excellent progress, so we will be in good shape to do this work in about a month or two.

So happy to hear this @certik

1 Like

We’ll have the tutorial this Friday. If you haven’t sent me your email to join the channel, we’ll make the tutorial open and will put the link here also.
Looking forward to meeting you.

2 Likes

The first lecture in the series will be held on Google Meet:

Introduction to Mathematics of Arrays
Friday, August 20, 2021
2:30 - 3:30 PM EDT
https://meet.google.com/icm-pfti-drb

If you’re already in the MoA Global Team Slack channel, I’ve sent a Google Calendar invite to each of you. See you tomorrow!

3 Likes

Awesome, thanks @wyphan !

1 Like

Thanks @wyphan . Looking forward to meeting more Fortran folks.

1 Like

Thanks to everyone who attended the first lecture. You can access the slides here:

The next one is scheduled in two weeks, and will cover the building blocks of Mathematics of Arrays.
I’ll post the link closer to the date.

3 Likes