Re: [xlr-talk] XL2: linear algebra and loop unrolling
Henry Weller
achieve the equivalent of loop-unrolling which can be done in C++ using
expression templates. Clearly this can be done for hard-coded sequences of
linear operators, for example :=, +, - and + _ - :
use xl.array.basic
use xl.ui.console
to assign(out LHS : array; RHS : array) written LHS := RHS is
for i in range(RHS) loop
LHS[i] := RHS[i]
function add (A, B : array) return array written A + B is
for i in range(A) loop
result[i] := A[i] + B[i]
function subtract (A, B : array) return array written A - B is
for i in range(A) loop
result[i] := A[i] - B[i]
function addSubtract (A, B, C : array) return array written A + B - C is
for i in range(A) loop
result[i] := A[i] + B[i] - C[i]
X : array[5] of integer
X[0] := 3
X[1] := 2
X[2] := 6
X[3] := 7
X[4] := 8
Y : array[5] of integer := X
Z : array[5] of integer := X
R : array[5] of integer := X + Y - Z
WriteLn "X + Y = ", R[4]
but is it necessary to write the equivalent of addSubtract for all combinations
of linear operators or can this loop-unrolling be automated somehow?
Thanks
Henry
Christophe de Dinechin
One would be to use XL macros (see xl2/native/TESTS/11.Preprocessor) :
transform
array_function 'fname' ('args') written 'form' is 'opcode'
into
function 'fname' ('args' : array) return array written 'form' is
for i in range(A) loop
result[i] := 'opcode'
Then you can write something like:
array_function addSubtract(A, B, C) written A+B-C is A[i]+B[i]-C[i]
I took some shortcuts here, e.g. I had to use range(A) meaning that one of the arguments has to be called A. It's possible to add another macro to extract the first argument of 'args' instead, not sure it's worth the effort.
Another more sophisticated option is to add a plugin to the compiler to do this kind of expansion, but then I don't know what the notations should look like. Is this something we want to apply to prefix operations as well, e.g. have sin(A) compute the sin of each element in turn?
So what we want is some sort of transform that takes an expression and replaces a select group of symbols with an indexed version?
In short, what notation would you like to use?
Christophe
> --
> You received this message because you are subscribed to the Google Groups "XL programming language and runtime" group.
> To post to this group, send email to xlr-...@googlegroups.com.
> To unsubscribe from this group, send email to xlr-talk+u...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/xlr-talk?hl=en.
>
Henry Weller
> members" part of the code. I see several solutions.
In a sense, but given some definition of the +, -, *, etc. operators one would
wish to be able to write any linear algebra expression in which all of the
arguments are arrays for examples and a single loop to be constructed around the
expression, i.e.
writing A + B - C * D + E
would automatically be transformed into
for i in range(A) loop
result[i] := A[i] + B[i] - C[i] * D[i] + E[i]
without having to first explicitly declare a function for the particular linear
combination of operators.
> One would be to use XL macros (see xl2/native/TESTS/11.Preprocessor) :
> transform
> array_function 'fname' ('args') written 'form' is 'opcode'
> into
> function 'fname' ('args' : array) return array written 'form' is
> for i in range(A) loop
> result[i] := 'opcode'
> Then you can write something like:
> array_function addSubtract(A, B, C) written A+B-C is A[i]+B[i]-C[i]
OK this is an elegant way to create the addSubtract function but I would rather
not have to create the all of the functions for all of the linear combination
of operators which might be needed which might run into the hundreds.
> Another more sophisticated option is to add a plugin to the compiler to do
> this kind of expansion, but then I don't know what the notations should look
> like. Is this something we want to apply to prefix operations as well,
> e.g. have sin(A) compute the sin of each element in turn?
Yes in principle almost any sequence of mathematical operations which might be
applied to integers or reals might be applied to arrays of them.
> So what we want is some sort of transform that takes an expression and
> replaces a select group of symbols with an indexed version?
Yes, and automatically apply the loop.
> In short, what notation would you like to use?
The same as for integers or reals, e.g.
A := B + C - D * sin(E) * e^F
could be applied to reals, arrays of reals, vectors of reals, fields of reals
etc. and for all but the first loops and indexing would need to be applied
automatically. This is possible with C++ using expression templates and
supported be Valarray, Blitz++, Boost etc. but it is a pretty hideous method to
achieve something seemingly so simple.
Thanks
Henry
Henry G. Weller
> this kind of expansion, but then I don't know what the notations should look
> like. Is this something we want to apply to prefix operations as well,
> e.g. have sin(A) compute the sin of each element in turn?
I have been playing with several options and it looks like a plugin parser is
going to be needed to combine the loops. I have found that it has been done in
this way before in a C++ pre-processor and optimiser called codeboost in which
the loops are implemented in map operators and "map fusion" is used to combine
the hierarchy of map operators, see
http://codeboost.org/papers/exam-otto-03.ps
and in more detail
http://codeboost.org/papers/codeboost-thesis-bagge.ps.gz
This or something like this might be an interesting approach to implement as a
plugin in XL2 as it relies on being able to parse and manipulate the AST which
is possible. What do you think?
Henry
Christophe de Dinechin
I took a little time to read the papers. This is really impressive work (doing that on C++ is all but easy), and it's been there a while (2003 at least).
First, a stupid question : doesn't that answer your own needs much better than XL2, since it's based on C++?
Now, this can be done with XL relatively easily. I'm just a little unclear regarding a syntax that would work well and be general. map is really the archetypal functional gizmo, finding syntax/semantics that work well with an imperative language is a bit challenging. What kind of control do you want over the selection of forms?
What about something like:
itemize [Expr] for [Iterator]
Usage would be:
itemize A := B + C * D for I in range D
Another example would be less general, assume it's always the first element in the expression or something like that:
array_itemize (A := B + C * D)
The plugin code once we decide the syntax and what it means is relatively easy...
Thanks
Christophe
Henry Weller
> I took a little time to read the papers. This is really impressive work (doing
> that on C++ is all but easy), and it's been there a while (2003 at least).
Thanks for taking the time to study this work and considering what I would to be
able to do with XL2, I am sure it is some way from your own needs.
> First, a stupid question : doesn't that answer your own needs much better than
> XL2, since it's based on C++?
While the codeboost work is really impressive it looks like it died and was
fundamentally restricted by the difficulty in parsing C++. Perhaps it could be
done again and better with the C++ parser in Clang but it is such an effort to
work with C++ in this way. In the end it is this difficulty in parsing and
extending C++ which is encouraging me to look elsewhere for a more elegant
language with a smaller number of more powerful features in which the DSL I
would like to use for HPC numerics can be created. Basically I want even more
power than expression templates but without the pain. I would also like to have
a pluggable back-end which would generate C or OpenCL or CUDA or UPC or ......
> Now, this can be done with XL relatively easily.
Excellent, I was hoping you would say that :-)
> I'm just a little unclear regarding a syntax that would work well and be
> general. map is really the archetypal functional gizmo, finding
> syntax/semantics that work well with an imperative language is a bit
> challenging. What kind of control do you want over the selection of forms?
> What about something like:
> itemize [Expr] for [Iterator]
> Usage would be:
> itemize A := B + C * D for I in range D
> Another example would be less general, assume it's always the first element in
> the expression or something like that:
> array_itemize (A := B + C * D)
> The plugin code once we decide the syntax and what it means is relatively easy...
I have been playing with the plugin examples and notice that they are "fired" on
an identifier, would it be possible to execute a plugin on the type of an
expression? i.e. while
itemize A := B + C * D for I in range D
is clear explicit syntax if you had lots of such formula in a function for
example to evaluate some complex model it would look rather cluttered. Ideally
I would like to simply write
A := B + C * D
and
itemize A := B + C * D for I in range D
or equivalent to be inferred from the type of A, B, C and D (which in this case
must all be the of same type). Does this make sense?
Thanks
Henry
Christophe de Dinechin
On 22 mars 2011, at 23:35, Henry Weller wrote:
> I have been playing with the plugin examples and notice that they are "fired" on
> an identifier,
The real trigger is a combination of type and shape. For example, consider:
to RunIt(out A : matrix; B, C, D : matrix) written A := B + C * D is
...
In that case, you need the correct types and the correct shape for RunIt to be called.
> would it be possible to execute a plugin on the type of an expression?
I believe that at the moment, it's a bit complicated to trigger based on type alone. You could do it with something like:
translation XLSemantics
when 'X' where DoSomeTypeAnalysisOf(X) then ...
This would have a serious cost at compile time, however, since every single expression would be type-checked through DoSomeTypeAnalysisOf(X). Are you ready to pay that cost? I vaguely remember you told me XLR was slow enough as it is ;-) Even if you restrict this to "linear algebra expressions", you are still activating your code for every single +, -, * or sin in your code...
> i.e. while
>
> itemize A := B + C * D for I in range D
>
> is clear explicit syntax if you had lots of such formula in a function for
> example to evaluate some complex model it would look rather cluttered.
What about having this work on a range of code, something like:
itemize for I in range D
// All the following code is "itemized"
A := B + C * D
C := A - D / 2
if unitemize(det(A) < 3) then
Z := A * B + D * E
// The following code is not
A[0] := B[0] - C[1]
That might help minimize clutter. You could even split the "how to rewrite" from the "what does it apply to", e.g:
itemize_on A
itemize
A := B + C * D
C := A - D / 2
X := max(A, B)
if unitemize(det(A)) < 3 then ...
> Ideally
> I would like to simply write
>
> A := B + C * D
>
> and
>
> itemize A := B + C * D for I in range D
> or equivalent to be inferred from the type of A, B, C and D (which in this case
> must all be the of same type). Does this make sense?
It makes sense. But there are a few things we may want to include in the design:
- Overriding the loop mechanism (e.g. do you want to replace a serial execution with parallel blocks using Apple's GCD)
- Specifying how to access elements (e.g. A[I] or *A or some other mechanism)
- Be able to constrain the range of items we loop on, or to have different ones for A, B, ...
Does that make sense? Is that overkill?
Regards
Christophe
Henry Weller
> to RunIt(out A : matrix; B, C, D : matrix) written A := B + C * D is
> ...
> In that case, you need the correct types and the correct shape for RunIt to be called.
OK, thanks for the clarification
>> would it be possible to execute a plugin on the type of an expression?
> I believe that at the moment, it's a bit complicated to trigger based on type
> alone.
I was getting that feeling. The problem with using the shape is that it isn't
simple for the kinds of expressions I would like to handle, effectively it would
need to be defined in a less explicit fashion e.g. using some kind of regular
expression involving wild cards etc.
> You could do it with something like:
> translation XLSemantics
> when 'X' where DoSomeTypeAnalysisOf(X) then ...
> This would have a serious cost at compile time, however, since every single
> expression would be type-checked through DoSomeTypeAnalysisOf(X). Are you
> ready to pay that cost?
In principle yes if a type-based quick rejection could be applied to limit the
cost.
> I vaguely remember you told me XLR was slow enough as it is ;-)
XL2 does indeed seem rather slow even for quite small codes but you told me that
the algorithm could be speeded-up significantly :-)
> Even if you restrict this to "linear algebra expressions", you are still
> activating your code for every single +, -, * or sin in your code...
How expensive would a type-check be? Note also that using expression templates
in C++ also involves a significant cost at compile-time.
>> i.e. while
>>
>> itemize A := B + C * D for I in range D
>>
>> is clear explicit syntax if you had lots of such formula in a function for
>> example to evaluate some complex model it would look rather cluttered.
> What about having this work on a range of code, something like:
> itemize for I in range D
> // All the following code is "itemized"
> A := B + C * D
> C := A - D / 2
> if unitemize(det(A) < 3) then
> Z := A * B + D * E
> // The following code is not
> A[0] := B[0] - C[1]
I could see this as being OK/good for some purposes but it would get in the way
of the readability of field algebra expressions the looping in which really
needs to be buried as it is a representational detail which might need to be
different depending on the kind of discretisation used. I would like the
top-level code to look like the equations we are solving both for readability
reasons and so that way a change in the numerical methods being used would not
require a change to the whole code.
>> Ideally
>> I would like to simply write
>>
>> A := B + C * D
>>
>> and
>>
>> itemize A := B + C * D for I in range D
>> or equivalent to be inferred from the type of A, B, C and D (which in this case
>> must all be the of same type). Does this make sense?
> It makes sense. But there are a few things we may want to include in the design:
> - Overriding the loop mechanism (e.g. do you want to replace a serial
> - execution with parallel blocks using Apple's GCD)
Indeed, I would like to be able to optimise the code for different architectures
without changing the top-level e.g. have the loops map to UPC loops by the
back-end. This is another reason to bury the details of the loops.
> - Specifying how to access elements (e.g. A[I] or *A or some other mechanism)
> - Be able to constrain the range of items we loop on, or to have different ones for A, B, ...
> Does that make sense? Is that overkill?
These are interesting issues but I see them as back-end issues and need not be
exposed at the top-level.
Best regards,
Henry
Henry G. Weller
matrix and vector types but a large number of related types. For the simplest
of these types a loop would need to be introduced but for the more complex
multiple loops and other operations e.g. dimension checking (in the mass,
length, time ... sense) would need to be applied. Here is a rough list of the
types that I would like to apply optimised linear algebra to:
VectorSpace
Vector
Tensor (several ranks and specializations e.g. symmetric)
Field
Field<Field>
DimensionedField
GeometricBoundaryField
GeometricField
LDUMatrix
FvMatrix
For all but the last two of these the set of operators and functions which would
need to be handled is pretty much the same but for LDUMatrix and FvMatrix the
set is somewhat smaller.
Best regards
Henry
Henry Weller
I have been working on this optimisation problem further and it does look like
that some kind of map with "map fusion" might be the best way to separate the
concepts from the implementation details, i.e. I would rather not assume that
vectors and matrices are stored in contiguous linear arrays which are looped
over from start to finish, other representations might be better on different
architectures. Binary operators could first be mapped to "map" functions which
could have several implementations depending on the implementation details of
the arrays. Then sequences of binary operators would become hierarchies of
"map" functions which could then be "fused" so that loops or whatever form of
array traversals are required could be combined. This is basically what is
going on in CodeBoost and has also been done in Haskell and I haven't worked out
a better approach which fulfils all the constraints (handling binary operators,
n-ary functions, multiple types, type combinations in the same expression etc.
Do you think that XL2 is a suitable framework in which to attempt an
implementation of "map fusion"?
Thanks
Henry
Christophe de Dinechin
On 28 mars 2011, at 00:08, Henry Weller wrote:
> Hi Christophe,
>
> I have been working on this optimisation problem further and it does look like
> that some kind of map with "map fusion" might be the best way to separate the
> concepts from the implementation details,
Since Henry starts a new thread, let me point out for other readers on the list that "map" here refers to the functional-style "map" function, and "map fusion" refers to a process of combining map functions. The general idea is:
1. Describe addition of arrays, e.g. A+B as "map + on A and B"
2. Describe a general process of fusing map f and map g
Read about "CodeBoost" on Google or earlier threads on this group to see this explained in more details.
> i.e. I would rather not assume that
> vectors and matrices are stored in contiguous linear arrays which are looped
> over from start to finish, other representations might be better on different
> architectures.
Yes, that was my point in an earlier post when I noticed I wanted to be able to customize the loops.
> Binary operators could first be mapped to "map" functions which
> could have several implementations depending on the implementation details of
> the arrays.
This isn't too hard, but when I tried writing some pseudo code, it was always either much less flexible or more verbose than the "natural" way of writing things in XL, which is something like:
function MLA(A, B, C : array) return array written A+B*C is
for I in range A loop
result[I] := A[I] + B[I] * C[I]
If I try to describe a "map" function on arrays, I need to specify:
- How to loop (and it's hard to be denser than in the code above)
- How to perform the operation (and again, it's hard to be denser than what's above)
- The precise conditions when this is being used (given by types and written form above)
So I think what I need now is an actual example of what the description of this "map function" should look like. To start with, is it a function of functions (like in functional languages), or is it a generic, or a macro? Or something special like the "rules" in CodeBoost?
> Then sequences of binary operators would become hierarchies of
> "map" functions which could then be "fused" so that loops or whatever form of
> array traversals are required could be combined.
If the objective is to combine loops, shouldn't we start with this, i.e. find a way to describe loop combination for different functions? Maybe that's where I have this mental block right now...
> This is basically what is
> going on in CodeBoost and has also been done in Haskell and I haven't worked out
> a better approach which fulfils all the constraints (handling binary operators,
> n-ary functions, multiple types, type combinations in the same expression etc.
> Do you think that XL2 is a suitable framework in which to attempt an
> implementation of "map fusion"?
At the language level, probably so, but I'm still unclear as to what the description of the various elements of this framework would look like. This "notation" problem is really the first step in concept programming, and I don't have it for your problem right now. The CodeBoost examples I saw didn't help much, because they looked like ad-hoc tags in C++ code, not some general mechanism. I.e. function named "rules" in which you have "commutative" tags. Is that what you want?
For the moment, I can think of two ways of doing things:
1) Put the rules in a compiler plug-in. This is in my opinion the easiest approach and probably the one with the best performance and best results. Basically, you write a plug-in that recognizes a set of operations (which may themselves be declared in the program with some special syntax) and unrolls / combines them. This was the "itemize" keyword I proposed. That way, you have access to all the type information, all symbol lookup functions, ... You generate loops the way you want, and so on.
2) Try to write the rules in the language itself, as you would in C++ or Haskell. While I believe this can be achieved, I'm afraid it will be much more difficult to use in practice. It won't take advantage of XL2's specific strengths, and it increases the chances you'll hit limitations of the compiler, e.g. with respect to the type system.
Hope this helps
Christophe
Henry Weller
> either much less flexible or more verbose than the "natural" way of writing
> things in XL, which is something like:
> function MLA(A, B, C : array) return array written A+B*C is
> for I in range A loop
> result[I] := A[I] + B[I] * C[I]
The problem with this is the particular sequence of operators is hard-coded and
the number of possible combinations is VERY large indeed.
> If I try to describe a "map" function on arrays, I need to specify:
> - How to loop (and it's hard to be denser than in the code above)
Indeed, the map function itself would be very simple, the clever bit would be
the map-fusion. Alternatively the operators could be converted directly into
loops as above but then the optimisation step would be loop-fusion which looks
rather more complicated.
> - How to perform the operation (and again, it's hard to be denser than what's above)
Indeed, each operation would be simple e.g.
function add(A, B : array) return array written A+B is
for I in range A loop
result[I] := A[I] + B[I]
function subtract(A, B : array) return array written A-B is
for I in range A loop
result[I] := A[I] - B[I]
then the expression "A + B - C" would require loop-fusion or
function add(A, B : array) return array written A+B is
map A B +
function subtract(A, B : array) return array written A-B is
map A B -
for which the expression "A + B - C" would require map-fusion to optimise the
resulting hierarchy of the form:
map A (map B C -) +
into something of the form
map A B C - +
> So I think what I need now is an actual example of what the description of
> this "map function" should look like. To start with, is it a function of
> functions (like in functional languages), or is it a generic, or a macro? Or
> something special like the "rules" in CodeBoost?
Good question, and this is where my understanding of XL2 runs out, I don't know
what kind of a thing "map" should be. It need not be overloaded and dispatched
on type, this could be handled directly e.g.:
function add(A, B : array) return array written A+B is
mapArray A B +
but it needs to handle the operator or function argument efficiently,
effectively inlined like a macro would do
function map(A, B : array, operator : ???) return array
for I in range A loop
result[I] := A[I] operator B[I]
this is were I really need some input.
and for the above we would also need
function map(A, B, C : array, operator1, operator2 : ???) return array
for I in range A loop
result[I] := A[I] operator1 B[I] operator2 C[I]
and we would need to create as many of these as the largest number of elements
in the expression as we need or perhaps write an n-ary version.
>> Then sequences of binary operators would become hierarchies of
>> "map" functions which could then be "fused" so that loops or whatever form of
>> array traversals are required could be combined.
> If the objective is to combine loops, shouldn't we start with this, i.e. find
> a way to describe loop combination for different functions? Maybe that's where
> I have this mental block right now...
Maybe, but it seems to me that fusing map functions will be easier than fusing
loops but perhaps in the end we are talking about the same thing but under a
different name: the map is just an abstraction for the loop.
>> This is basically what is
>> going on in CodeBoost and has also been done in Haskell and I haven't worked out
>> a better approach which fulfils all the constraints (handling binary operators,
>> n-ary functions, multiple types, type combinations in the same expression etc.
>> Do you think that XL2 is a suitable framework in which to attempt an
>> implementation of "map fusion"?
> At the language level, probably so, but I'm still unclear as to what the
> description of the various elements of this framework would look like. This
> "notation" problem is really the first step in concept programming, and I
> don't have it for your problem right now.
Does what I have written above make sense? Does it fit into XL2?
> The CodeBoost examples I saw didn't help much, because they looked like ad-hoc
> tags in C++ code, not some general mechanism. I.e. function named "rules" in
> which you have "commutative" tags. Is that what you want?
I didn't like the syntax they came up with for the operator specification, I
would prefer something like:
function add(A, B : array) return array written A+B is
map A B +
> For the moment, I can think of two ways of doing things:
> 1) Put the rules in a compiler plug-in. This is in my opinion the easiest
> approach and probably the one with the best performance and best
> results. Basically, you write a plug-in that recognizes a set of operations
> (which may themselves be declared in the program with some special syntax) and
> unrolls / combines them. This was the "itemize" keyword I proposed. That way,
> you have access to all the type information, all symbol lookup functions,
> ... You generate loops the way you want, and so on.
I would really like to avoid the need for keywords which relate to the
underlying representation, i.e. I would like to be able to write say the
conjugate-gradient algorithm much like it would be in Fortress:
I tried to include an image here but when I do the posting fails. What I wanted
to include is the Fortress code on page 14 of
http://ropas.snu.ac.kr/seminar/20091213c.pdf
which does not presuppose how "Vec" might be represented and looks almost
identical to the original algorithm. I think that Fortress has rather
over-sugared the syntax and an ASCII version would be sufficient but the idea of
being able to do vector algebra in this form (which we can already do in
OpenFOAM) and be as efficient as possible (which currently we can't so we have
to inject loops by hand in the critical parts) is a powerful one.
> 2) Try to write the rules in the language itself, as you would in C++ or
> Haskell. While I believe this can be achieved, I'm afraid it will be much more
> difficult to use in practice. It won't take advantage of XL2's specific
> strengths, and it increases the chances you'll hit limitations of the
> compiler, e.g. with respect to the type system.
Would a language extension be needed to implement map-fusion, e.g. as part of
the optimiser? Or can it be done more naturally within the current framework?
--
Best regards,
Henry
Henry Weller
> either much less flexible or more verbose than the "natural" way of writing
> things in XL, which is something like:
> function MLA(A, B, C : array) return array written A+B*C is
> for I in range A loop
> result[I] := A[I] + B[I] * C[I]
The problem with this is the particular sequence of operators is hard-coded and
the number of possible combinations is VERY large indeed.
> If I try to describe a "map" function on arrays, I need to specify:
> - How to loop (and it's hard to be denser than in the code above)
Indeed, the map function itself would be very simple, the clever bit would be
the map-fusion. Alternatively the operators could be converted directly into
loops as above but then the optimisation step would be loop-fusion which looks
rather more complicated.
> - How to perform the operation (and again, it's hard to be denser than what's above)
Indeed, each operation would be simple e.g.
function add(A, B : array) return array written A+B is
for I in range A loop
result[I] := A[I] + B[I]
function subtract(A, B : array) return array written A-B is
for I in range A loop
result[I] := A[I] - B[I]
then the expression "A + B - C" would require loop-fusion or
function add(A, B : array) return array written A+B is
map A B +
function subtract(A, B : array) return array written A-B is
map A B -
for which the expression "A + B - C" would require map-fusion to optimise the
resulting hierarchy of the form:
map A (map B C -) +
into something of the form
map A B C - +
> So I think what I need now is an actual example of what the description of
> this "map function" should look like. To start with, is it a function of
> functions (like in functional languages), or is it a generic, or a macro? Or
> something special like the "rules" in CodeBoost?
Good question, and this is where my understanding of XL2 runs out, I don't know
what kind of a thing "map" should be. It need not be overloaded and dispatched
on type, this could be handled directly e.g.:
function add(A, B : array) return array written A+B is
mapArray A B +
but it needs to handle the operator or function argument efficiently,
effectively inlined like a macro would do
function map(A, B : array, operator : ???) return array
for I in range A loop
result[I] := A[I] operator B[I]
this is were I really need some input.
and for the above we would also need
function map(A, B, C : array, operator1, operator2 : ???) return array
for I in range A loop
result[I] := A[I] operator1 B[I] operator2 C[I]
and we would need to create as many of these as the largest number of elements
in the expression as we need or perhaps write an n-ary version.
>> Then sequences of binary operators would become hierarchies of
>> "map" functions which could then be "fused" so that loops or whatever form of
>> array traversals are required could be combined.
> If the objective is to combine loops, shouldn't we start with this, i.e. find
> a way to describe loop combination for different functions? Maybe that's where
> I have this mental block right now...
Maybe, but it seems to me that fusing map functions will be easier than fusing
loops but perhaps in the end we are talking about the same thing but under a
different name: the map is just an abstraction for the loop.
>> This is basically what is
>> going on in CodeBoost and has also been done in Haskell and I haven't worked out
>> a better approach which fulfils all the constraints (handling binary operators,
>> n-ary functions, multiple types, type combinations in the same expression etc.
>> Do you think that XL2 is a suitable framework in which to attempt an
>> implementation of "map fusion"?
> At the language level, probably so, but I'm still unclear as to what the
> description of the various elements of this framework would look like. This
> "notation" problem is really the first step in concept programming, and I
> don't have it for your problem right now.
Does what I have written above make sense? Does it fit into XL2?
> The CodeBoost examples I saw didn't help much, because they looked like ad-hoc
> tags in C++ code, not some general mechanism. I.e. function named "rules" in
> which you have "commutative" tags. Is that what you want?
I didn't like the syntax they came up with for the operator specification, I
would prefer something like:
function add(A, B : array) return array written A+B is
map A B +
> For the moment, I can think of two ways of doing things:
> 1) Put the rules in a compiler plug-in. This is in my opinion the easiest
> approach and probably the one with the best performance and best
> results. Basically, you write a plug-in that recognizes a set of operations
> (which may themselves be declared in the program with some special syntax) and
> unrolls / combines them. This was the "itemize" keyword I proposed. That way,
> you have access to all the type information, all symbol lookup functions,
> ... You generate loops the way you want, and so on.
I would really like to avoid the need for keywords which relate to the
Henry Weller
> either much less flexible or more verbose than the "natural" way of writing
> things in XL, which is something like:
> function MLA(A, B, C : array) return array written A+B*C is
> for I in range A loop
> result[I] := A[I] + B[I] * C[I]
The problem with this is the particular sequence of operators is hard-coded and
the number of possible combinations is VERY large indeed.
> If I try to describe a "map" function on arrays, I need to specify:
> - How to loop (and it's hard to be denser than in the code above)
Indeed, the map function itself would be very simple, the clever bit would be
the map-fusion. Alternatively the operators could be converted directly into
loops as above but then the optimisation step would be loop-fusion which looks
rather more complicated.
> - How to perform the operation (and again, it's hard to be denser than what's above)
Indeed, each operation would be simple e.g.
function add(A, B : array) return array written A+B is
for I in range A loop
result[I] := A[I] + B[I]
function subtract(A, B : array) return array written A-B is
for I in range A loop
result[I] := A[I] - B[I]
then the expression "A + B - C" would require loop-fusion or
function add(A, B : array) return array written A+B is
map A B +
function subtract(A, B : array) return array written A-B is
map A B -
for which the expression "A + B - C" would require map-fusion to optimise the
resulting hierarchy of the form:
map A (map B C -) +
into something of the form
map A B C - +
> So I think what I need now is an actual example of what the description of
> this "map function" should look like. To start with, is it a function of
> functions (like in functional languages), or is it a generic, or a macro? Or
> something special like the "rules" in CodeBoost?
Good question, and this is where my understanding of XL2 runs out, I don't know
what kind of a thing "map" should be. It need not be overloaded and dispatched
on type, this could be handled directly e.g.:
function add(A, B : array) return array written A+B is
mapArray A B +
but it needs to handle the operator or function argument efficiently,
effectively inlined like a macro would do
function map(A, B : array, operator : ???) return array
for I in range A loop
result[I] := A[I] operator B[I]
this is were I really need some input.
and for the above we would also need
function map(A, B, C : array, operator1, operator2 : ???) return array
for I in range A loop
result[I] := A[I] operator1 B[I] operator2 C[I]
and we would need to create as many of these as the largest number of elements
in the expression as we need or perhaps write an n-ary version.
>> Then sequences of binary operators would become hierarchies of
>> "map" functions which could then be "fused" so that loops or whatever form of
>> array traversals are required could be combined.
> If the objective is to combine loops, shouldn't we start with this, i.e. find
> a way to describe loop combination for different functions? Maybe that's where
> I have this mental block right now...
Maybe, but it seems to me that fusing map functions will be easier than fusing
loops but perhaps in the end we are talking about the same thing but under a
different name: the map is just an abstraction for the loop.
>> This is basically what is
>> going on in CodeBoost and has also been done in Haskell and I haven't worked out
>> a better approach which fulfils all the constraints (handling binary operators,
>> n-ary functions, multiple types, type combinations in the same expression etc.
>> Do you think that XL2 is a suitable framework in which to attempt an
>> implementation of "map fusion"?
> At the language level, probably so, but I'm still unclear as to what the
> description of the various elements of this framework would look like. This
> "notation" problem is really the first step in concept programming, and I
> don't have it for your problem right now.
Does what I have written above make sense? Does it fit into XL2?
> The CodeBoost examples I saw didn't help much, because they looked like ad-hoc
> tags in C++ code, not some general mechanism. I.e. function named "rules" in
> which you have "commutative" tags. Is that what you want?
I didn't like the syntax they came up with for the operator specification, I
would prefer something like:
function add(A, B : array) return array written A+B is
map A B +
> For the moment, I can think of two ways of doing things:
> 1) Put the rules in a compiler plug-in. This is in my opinion the easiest
> approach and probably the one with the best performance and best
> results. Basically, you write a plug-in that recognizes a set of operations
> (which may themselves be declared in the program with some special syntax) and
> unrolls / combines them. This was the "itemize" keyword I proposed. That way,
> you have access to all the type information, all symbol lookup functions,
> ... You generate loops the way you want, and so on.
I would really like to avoid the need for keywords which relate to the
Marc Coram
learning about XL.
A thought that occurs to me is that XL seems to be placing a lot of
burden on the rewrite system. This is elegant and unifying, but to me
anyway it seems natural to compare it with alternatives like macros
and f-expressions. [I'm going to be very loose and make mistakes,
please forgive me.]
So, for example, suppose we consider an example, in lispish syntax for
the moment like:
(with-vectorize (set! d (sqrt (div (mul (sum a b) c) d)) (range a))
We could suppose that such a thing was parsed from some more human-
readable syntax like:
Vectorize over (range a):
d := sqrt( (a+b)*c/d )
Then we could imagine that with-vectorize is a macro invocation that
(1) checks that its first operand parses to something that belongs to
whatever set of expression with-vectorize is built to handle and (2)
then rewrites the operand into some boring for loop version over the
specified range.
So my general question becomes: are there transformations that can be
readily/efficiently described by a macro but not by a sequence of
(guarded) rewrite equations? Is this an example? And if so what shall
we do? And my larger concerns revolve around questions like: how do we
get expanders like this to play nicely with other expanders. E.g.
suppose I tried to "differentiate" this whole thing (whatever that
would be defined to mean in such a case), then how would the two
expanders interact? To my (rather limited) understanding fexprs (as
e.g. in the Kernel language) should be "more expressive" than the
other idioms, but that there are not established mechanisms for
avoiding associated run-time costs.
All of this needs to be taken with large grains of salt because (for
starters) I haven't done my due diligence to understand XL rewrite
semantics properly yet.
Regards!
> 50KViewDownload
>
>
> which does not presuppose how "Vec" might be represented and looks almost
> identical to the original algorithm. I think that Fortress has rather
> over-sugared the syntax and an ASCII version would be sufficient but the idea of
> being able to do vector algebra in this form (which we can already do in
> OpenFOAM) and be as efficient as possible (which currently we can't so we have
> to inject loops by hand in the critical parts) is a powerful one.
>
> > Haskell. While I believe this can be achieved, I'm afraid it will be much more
> > difficult to use in practice. It won't take advantage of XL2's specific
> > strengths, and it increases the chances you'll hit limitations of the
> > compiler, e.g. with respect to the type system.
>
Marc Coram
about itemize.
Christophe de Dinechin
- Henry wants to use static type information for best performance. The XL2 type system is at the moment better suited for this kind of exploration. However, my concern is that using the type system alone (sans keyword) will work, but will slow-down the compilation too much. That needs to be confirmed with experimentation, which I don't have time to do right now, unfortunately.
- The XLR rewrite system is more extensive (at least as far as its definition is concerned), and covers what is known in Lisp circles as functions (lazy or eager evaluation), macros and f-expressions. It is not fully implemented yet, and it may degrade to a run-time cost which would be inadequate for high-performance computing applications.
I owe both of you a longer reply, but I don't know exactly when I will be able to write it.
Regards
Christophe