Can/should the Chapel compiler do loop fusing of whole-array statements / promotions?

[jabraham17]

While comparing some Chapel code with Fortran code, it was observed that many lines of promoted operations was slower than the equivalent code written with a single forall and no promoted operations. The following code snippet is a complete reproducer

use Time;
use Math;

config const n = 50_000;
config const ns = 5000;
config const print = false;
config const explicitForall = false;

var A, B, C, D, E, F: [1..n] real;
var RES1, RES2: [1..n] real;

writeln("Using numTasks = ", here.maxTaskPar);

var t = new stopwatch();
t.start();
if explicitForall {
  doExplicitForall();
} else {
  doPromotion();
}
t.stop();
writeln("Execution time: ", t.elapsed(), " seconds");

if print {
  writeln("RHO: ", RES1);
  writeln("RE: ", RES2);
}

proc doExplicitForall() {
  for 1..ns {
    forall ii in 1..n {
      RES1(ii) = A(ii) * B(ii) + (1.0-A(ii)) * C(ii);
      RES2(ii) = RES1(ii) * D(ii) * E(ii) / F(ii);
    }
  }
}

proc doPromotion() {
  for 1..ns {
    RES1 = A * B + (1.0-A) * C;
    RES2 = RES1 * D * E / F;
  }
}

Running this on a linux64 system with 32 cores, I see the following

> ./example --ns 10000 --n 1_000_000 
Using numTasks = 32
Execution time: 0.820101 seconds

> ./example --ns 10000 --n 1_000_000 --explicitForall
Using numTasks = 32
Execution time: 0.637187 seconds

Essentially, the promoted version is resulting in two parallel loops, so there is some extra overhead and work done. The promoted version could be notionally written as follows

proc doPromotionExplicit() {
  for 1..ns {
    [(r, a, b, c) in zip(RES1, A, B, C)] r = a * b + (1.0-a) * c;
    [(r1, r2, d, e, f) in zip(RES1, RES2, D, E, F)] r2 = r1 * d * e / f;
  }
}

Combining these loops into one results doExplicitForall function in the original code. Note that I have opted to iterate over the domain rather than the zip, but the result should be the same.

Should the Chapel compiler do this automatically, essentially fusing parallel loops together? We could restrict this kind of optimization to "do these arrays all share the same domain", but I would go a step further and say "can we prove these arrays have the same loop trip count". This would allow users to write the much cleaner and concise array operations, but get similar performance as the explicit forall case.

For the full context on the original discussion, see https://chapel.discourse.group/t/chapel-performance-test-on-wsl-ubuntu/42122

[bradcray]

Note that I have opted to iterate over the domain rather than the zip, but the result should be the same.

I'm not certain that's necessarily the case… E.g., in Engin's GPU case, I believe he tried doing a zip-based rewrite and found that the register pressure was much higher. It'd be worth verifying in any case.

A definite tension to this kind of optimization is that it's possible to go too far, fuse too many loops and blow out your cache benefits or register set by having too large of a working set. So the options are essentially (a) do the optimal thing (recognizing that that's very difficult to achieve), (b) do the simple thing and require the user to use explicit loops when it's too slow (this is the status quo), (c) fuse aggressively and require the user to rewrite to use explicit loops when it backfires and is too slow.

One other concept we could consider is to have some sort of:

@fuse
{
    RES1 = A * B + (1.0-A) * C;
    RES2 = RES1 * D * E / F;
}

attribute that would say when to fuse the loops.

but I would go a step further and say "can we prove these arrays have the same loop trip count"

In order to generate good loop nests, I think this would need to be "trip count in each dimension" or rather "same size and shape". That said, for the promotion to be legal, that should probably already be the case?

Also note that all the expressions may not be simple arrays, they could be slices or forall expressions, for example.

[jabraham17]

I'm not certain that's necessarily the case… E.g., in Engin's GPU case, I believe he tried doing a zip-based rewrite and found that the register pressure was much higher. It'd be worth verifying in any case.

I did verify this. Using the following code, it matches the performance of doExplicitForall

proc doFusedPromotion() {
  for 1..ns {
    [(r1, r2, a, b, c, d, e, f) in zip(RES1, RES2, A, B, C, D, E, F)] {
        r1 = a * b + (1.0-a) * c;
        r2 = r1 * d * e / f;
    }
  }
}

(a) do the optimal thing (recognizing that that's very difficult to achieve), (b) do the simple thing and require the user to use explicit loops when it's too slow (this is the status quo), (c) fuse aggressively and require the user to rewrite to use explicit loops when it backfires and is too slow.

I think there is a middle ground. Simplifying somewhat, in this example there are 2 forall loops created by promotion from 2 statements. Say we have a fuse-maximum of 2, in this example we fuse the two loops. If there are are 3 statements, we fuse the first two and leave the third alone. If there are 4 statements, we fuse the first two and the last two. Then, we can expose this fuse-maximum as a compilation knob. Of course there are other factors (like how many things will be zippered), but I think with a conservative fuse that can be dialed up more aggressively we can get a good performance improvement without sacrificing the concise array code. It may not be the most optimal possible, but its better than the status quo.

I prefer this approach to an attribute based approach, as the same thing can be achieved by writing an explicit forall loop.

[bradcray]

@e-kayrakli asserted today that "we should only do this for promoted expressions", which I tend to agree with and considered the point of this issue. Re-reading the title, though, I could see how someone might think otherwise, so I reworded it, hoping that's OK with @jabraham17

[e-kayrakli]

I believe he tried doing a zip-based rewrite and found that the register pressure was much higher. It'd be worth verifying in any case.

Yes. That's a GPU-specific issue captured in #24131.

I came here mostly to express strong interest in writing this optimization. Whether I should just jump in and do that is a different question, though. :) Maybe on a quiet Friday?

[e-kayrakli]

Ignoring the promotion-only aspect of the approach discussed here for a second, there's also a bit of an interesting question in terms of at what level we should be fusing things. In an ideal world, I would propose we implement fusion for coforall and on statements, which I think would result in better coverage for the optimization. It would also have the added benefit of having the optimization fire later in compilation, potentially saving some time. But that feels significantly more challenging than fusing foralls, pretty much right after resolution, or even as we resolve things, if we can decouple the implementation nicely.

[jabraham17]

This issue was definitely motivated by the promotion case, where if you want to fuse two promoted statements today, your only option is to write an explicit forall loop. However, if you are already writing forall/coforall/on loops/blocks, its fully within your control to fuse them manually. While I think it would be nice to one day have that kind of optimization, I think it has significantly more challenges and is arguably less useful/productive

[bradcray]

However, if you are already writing forall/coforall/on loops/blocks, its fully within your control to fuse them manually. While I think it would be nice to one day have that kind of optimization, I think it has significantly more challenges and is arguably less useful/productive

I might go further and say that a downside of doing that sort of fusion is that it removes the user's ability to control where parallelism is introduced in their program by using the more explicit features of the language.

Engin, when you say:

I would propose we implement fusion for coforall and on statements

are you referring to the coforall and on statements that a distributed array might use to implement its prallelism in its leader iterator?

[e-kayrakli]

are you referring to the coforall and on statements that a distributed array might use to implement its prallelism in its leader iterator?

Yes.

I might go further and say that a downside of doing that sort of fusion is that it removes the user's ability to control where parallelism is introduced in their program by using the more explicit features of the language.

I don't intend to belabor the point here as I am not really proposing we work on coforall fusion today. But I think what you are saying here Brad is not really a drawback considering what I meant would result in the same generated code and the behavior in the end.

(A potential benefit of fusing later would be to potentially fuse loops from two inline functions called consecutively)

[bradcray]

I've been thinking more about this issue the last several days, and wanted to capture some thoughts:

• We'd need to be sure that there are no inter-statement dependencies that would prevent the promoted statements from being fused. That said, if our heuristic for fusing were "all have the same domain", I haven't come up with an example that would pose issues. If it were "have the same size and shape" then I think we'd primarily need to be careful around array views and aliases that represent array views. For example:

B[2..<n] = A[1..<n-1] + A[3..n];
A = B;  // A [2..<n] = B[2..<n];

could not be fused.

• If we were to do some work in this general space, I think we should definitely start by getting the performance of multidimensional promotions and zipperings to be acceptable (Multidimensional zippered iteration (or promotion) kills performance #13147) prior to doing this because it's such a performance killer currently. Arguably, if we implemented this first, and were to do it using a forall i … loop with indexing rather than a zippering over all promoted arrays, it could address some of those cases; but since this optimization wouldn't apply in all promoted cases, I think it would create too uneven of a landscape in terms of when things performed well vs. poorly and make matters more confusing than they are today. I also just think Multidimensional zippered iteration (or promotion) kills performance #13147 is way overdue for attention, particularly if we have more Fortran users coming to Chapel and wanting to use whole-array operations (one of the motivations for this issue).

• I also wouldn't prioritize this issue over other current priorities we have, at least at present, and without a good pseudocode or algorithmic sketch of what we're building and agreement on that.

• I think the ideal time to fuse would be at the time we're lowering promoted expressions to loops rather than after the fact. The reasons being that I think it's easier to lower whole-array statements and operations to the forall loop you ultimately want than to fuse forall loops or coforall loops containing forall loops after the fact. As mentioned previously, I also remain skeptical that getting into the business of fusing coforall loops and the forall loops they contain is worth our while, both due to the increased difficulty of determining that the fusing is legal (in terms of both loop structure and dependency analysis) and because my strong suspicion is that if a user's code contains adjacent coforall / forall loops that are compatible for fusing, they probably made them separate loops for a reason. Put another way, as a user, it's easier for me to write a fused loop:

forall (a,i) in (A, D) {
  a = B[i-1] + B[i+1];
  B[i] = a;
}

than a non-fused one:

forall (a,i) in (A, D) {
  a = B[i-1] + B[i+1];
}
forall (a,i) in (A, D) {
  B[i] = a;
}

so, to me, it seems more likely that the lack of fusion is intentional/necessary and less likely that we'd pick up lots of low-hanging performance gains, particularly given that the implementation challenge seems so much greater.