On Mon, 3 Aug 2020, Brad Chamberlain wrote:
Sounds like you've largely sorted this out, but just to touch on a few
points:
As:
var y = [1..columns] real = 0:real;
for r in rows do
{
y += x[r] * z[r, ..];
}
where y and x are vectors. It is a direct mapping. What's wrong with that?
Modulo the row- vs. column-major memory issues you eventually arrived at,
Chapel's support for rank-change slicing is currently known to be fairly
heavyweight, so the expression 'z[r, ..]' is, unfortunately, not cheap at
present. I expect that this accounts for a fair amount of the overhead.
Rewriting it to not involve slicing did snot eem to much much difference,
at least in that case. Conversely, in an example where the 2nd dimension
of 'z' spans the range 1..n and 1 <= j < k <= n, I noted that slicing a
1D-array 'p' and that 2D array 'z' into a range
qr = j..k
I found that:
apply(p[qr], z[r, qr])
took longer than
apply(qr, p, z[r, ..])
I found that fascinating. I have yet to come up with guidelines for when
to slice and when not to slice. Slicing at the 2D level is the concept of
a sub-matrix which is very useful to use to encapsulate an idea. Let me
know when you are addressing that overhead load and I will be happy to
test any changes to reduce it.
If you wanted to push this further, it'd be interesting to break the
loop into pure scalar loops (not that we want people to do this forever)
and see whether tucking that repeated read of x[r] into a scalar helps.
That is:
for r in rows {
const xr = x[r];
for c in cols {
y[c] += xr * z[r,c];
}
}
I tried that and it did not seem to buy much in this particular case. I
would expect any programmer to optimize that by (her/him)self.
As we both know, the above needs a partial reduction and I look forward to
hammering this in the new year. See below.
But I am curious how close we can get to Fortran.
Me too. For a recent project, I reworked the application of Givens' planar
rotations, done row-wise in Fortran, to being done column-wise in Chapel
(or even C), in a loop (obviously), Fortran has two memory reads from 2
separate 1D-arrays at the start of the loop and then two memory writes at
the end. The C (or Chapel) code has 3 memory reads from 2 separate
1D-arrays at the start of the loop and one memory write at the end. Both
have 4 multiplications and 2 additions. The C (or Chapel) code takes twice
as long as the Fortran which seemed weird. Both had identical floating
point operations and near identical X86-64 assembler. But, those 3 reads
at the start induce a stall while the CPU was waiting for the data to be
available in the register. Not happy. I took the C assembler and (at the
expense of wrong answers), killed off one of the floating point operations
(to eliminate the stall) and the C code is now only 20% slower. I have
tried to hand-craft the assembler and I am still stuck. It is on my to-do
list but I am not sure it is fixable.
You mention the vectorization as well, and that's something we're
continuing to look into in the context of the LLVM back-end.
Thanks. I am becoming more of the opinion that expecting a compiler to
come up with an optimal vectorization is fruitless. Maybe we really need
to program (at least low-level, critical routines) using a data structure
which encapsulates several uniform numeric data items, and upon which are
defined high-level and truly generic operations which a compiler can map
to the so-called vector intrinsics of the underlying architecture. That
sequence would be more like a blob (or a wodge) because it is not element
addressable so labelling it with the noun 'vector' would be a serious
misnomer. My 2c.
The second is fascinating. I would never have guessed that an O(n) write
to memory would have 20% the impact of O(n^2) floating point operations.
Welcome to the exciting world of modern architectures and cost models! (?)
Thanks! Just what I needed to hear. You are such a comfort.
I will put working partial reductions on my Santa wish-list for 2021 now!
Sounds good.
Maybe Santa should bring it forward 12 months to December 2020! I see that
there is a recently started GSoC student who will need this sort of thing
too.
Stay safe - Damian
Pacific Engineering Systems International, 277-279 Broadway, Glebe NSW 2037
Ph:+61-2-8571-0847 .. Fx:+61-2-9692-9623 | unsolicited email not wanted here
Views & opinions here are mine and not those of any past or present employer
_______________________________________________
Chapel-developers mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/chapel-developers
