Comments (8)
Hi @damianmoz β
Given that, can the following
+ reduce foreach ....be made to be a vectorized reduction
This is the hope and intention, yes. Historically, this has not happened because we didn't support foreach
expressions (#19336), which meant the loop couldn't appear in that position, syntactically. But @DanilaFe has recently been working on adding these in #19336, so we're getting closer. Meanwhile, @stonea has been working on adding support for with
-clauses to foreach
loops, which may be required to have a reduce
+ foreach
expression do the right thingβI'm not certain though I suspect it is.
from chapel.
Just noting that @jeremiah-corrado was helping users who ran into this flavor of issue today. Tagging @stonea as I think this is starting to become one of the performance gotchas that stands out more and more for me as being problematic.
from chapel.
A difference between array initialization and reductions it that the reduction could be:
var sum = + reduce [i in 0..<here.maxTaskPar] veryExpensiveProcedure(i);
where the trip count may be modest (4β128, say) suggesting serialization, but the body of the loop suggests parallelizing.
Setting up a heuristic for the common "just reduce an array" case:
var sum = + reduce A;
is easy and more similar to array initialization, but then is very brittle to modest changes like:
var sum = + reduce (A != 0);
var sum = + reduce [a in A] (a != 0);
var sum = + reduce [i in A.domain] (A[i] != 0);
etc.
So it seems to me like we'd need to do some sort of evaluation of the "weight" of the expression being reduced, which feels new and more complex (and like something that we could/might want to apply to parallel loops in general and not just those involved in reductions).
But I'd be very happy if you were to point out that I'm missing something. :)
from chapel.
I did not realize that
+ reduce for ....
is a serial reduction. Given that, can the following
+ reduce foreach ....
be made to be a vectorized reduction. That would be explicit. I could live with that, even if it is not as succinct as I would like.
I am not a fan of the vaguer approach.
I still think a keyword like reducev or something similar would be more succinct. Even the keyword serial qualifying reduce would work for me if that can be made to work syntactically.
from chapel.
implement heuristics that would serialize reductions for sufficiently small/serial cases
Some other ideas here:
- we could use on-line autotuning or similar adaptive techniques that respond to the amount of time each iteration takes
- we could use profile-guided optimization techniques; e.g. if we simply were to log where tasks were created and where they ended and their duration, the compiler/runtime could use this information to decide to skip creating certain tasks for performance reasons
from chapel.
For future reference, for this, #24196 and #14000. here is a serial max reduction of the absolute values of a 1D array with unit stride (as would be 99% of the arrays that one would see in linear algebra applications). Any suggested improvements are most welcome.
inline proc maxofabs(const v : [?D] real(?w))
{
inline proc tmax(x : real(w), y : real(w)) // version of what is in AutoMath
{
return if x > y || x != x then x else y;
}
param zero = 0:real(w);
const n = D.size;
const k = D.low;
var v0 = zero, v1 : real(w), v2 : real(w), v3 : real(w);
select(n & 3) // use a head+body split (i.e. do not use body+tail)
{
when 0 do (v1, v2, v3) = (zero, zero, zero);
when 1 do (v1, v2, v3) = (zero, zero, abs(v[k]));
when 2 do (v1, v2, v3) = (zero, abs(v[k]), abs(v[k + 1]));
when 3 do (v1, v2, v3) = (abs(v[k]), abs(v[k + 1]), abs(v[k + 2]));
}
if n > 7 then foreach j in k + (n & 3) .. D.high by 4 do // use a loop when n>8
{
v0 = tmax(v0, abs(v[j]));
v1 = tmax(v1, abs(v[j + 1]));
v2 = tmax(v2, abs(v[j + 2]));
v3 = tmax(v3, abs(v[j + 3]));
}
else if n > 3 then // avoid loop overhead when 4 <= n < 7
{
const j = k + (n & 3);
v0 = abs(v[j]);
v1 = tmax(v1, abs(v[j + 1]));
v2 = tmax(v2, abs(v[j + 2]));
v3 = tmax(v3, abs(v[j + 3]));
}
return tmax(tmax(v0, v2), tmax(v1, v3));
}
from chapel.
implement heuristics that would serialize reductions for sufficiently small/serial cases
Re hard/vagueness of this bit: it is not worrisome to me. We already use such heuristics for array initialization and parallel bulk copy between arrays. I do agree that it is hard to find the perfect threshold, but I am optimistic that there's a number that can make the current painful cases go faster. We can always pick a conservative serialization threshold by default and make it tunable by the user.
from chapel.
But I'd be very happy if you were to point out that I'm missing something.
Nope. I don't think you are.
But I may be more (naively?) optimistic than you that we can make common cases significantly faster by potentially sacrificing some less common cases' performance and that it could be a achievable net win in the near term.
from chapel.
Related Issues (20)
- chpl__init_ModuleName(int64_t _ln, int32_t _fn) has mystery parameters HOT 1
- should identifier matches against the enclosing module name be considered if there are other matches? HOT 6
- Performance delta between Chapel and CUDA for `tanh` HOT 2
- `make test-cls` fails in quickstart config on M1 mac
- [Documentation]: Improve GPU Setup Documentation for CHPL_LOCALE_MODEL=gpu HOT 1
- Standalone Arkouda `ContrivedConstructor` caused compiler to throw unreasonable promotion/parameness error HOT 1
- [Feature Request]: Chapel OS packages with GPU support
- Add chpl-language-server documentation for vim and emacs HOT 6
- [Bug]: problems in LLVM or C codegen
- [Documentation]: Should we move the documentation on syntax highlighting into the online documentation? HOT 1
- [Feature Request]: Add support for DuckDB HOT 1
- Compiler LLVM fatal errors aren't very helpful without CHPL_DEVELOPER right now HOT 1
- [Feature Request]: support autocompletion for fish HOT 1
- Dyno: named declarations should report their indentation separately from their name locations
- Remove/Retire 'numa' locale model
- [Feature Request]: Lint rule for extra parentheses HOT 3
- [Feature Request]: Lint rule for line length HOT 1
- Compiling a `--library` with GPU support (or C++) should use C linkage in the generated header
- Moving tasks to sublocales doesn't work in the library mode
- [Bug]: `chpl-shim` produces empty json if run twice on mason
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
π Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. πππ
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google β€οΈ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from chapel.