On Thu, 17 Feb 2005 05:25:09 +0100, Norbert Nemec wrote:

I think your syntax looks very good.
But I think we can learn from the similarities between sql
and vectorisation, the have been done a lot of research in
query optimization for sql and maybe we can use some of it
for vectorisation.

Also if we change focus from array of numbers to array of objects, then we almost have a indexed table.

vectorize a[i,j].name(),a[i,j].address() into file[i] with i=0..10 over
j=0..100;

So, maybe we can expand the vectorization engine to work on those too.

Also have you thought of how to implement aggregated functions, maybe we can learn form databases.


Knud

Norbert Nemec wrote:
> Georg Wrede schrieb:
> 
>> Why not
>>
>>  >> vectorize(int i; minVi; maxVi) {
>>  >> vectorize(int j; minVj; maxVj) {
>>  >> vectorize(int k; minVk; maxVk)
>>  >> {
>>  >>    c[i, k] = a[i,j] * b[j, k];
>>  >> } }}
> 
> 
> Because this means that you can only vectorize statements and not expressions. This again means:
> * you cannot express vectorized returns
> * you cannot mix vectorized operations with other array operations
> * you cannot feed the result of a vectorized operation into a function without storing it into a temporary variable
> 
> Furthermore, this syntax still seems to imply that the 'i' loop is the outermost loop. Especially loop reordering is an important tool for optimization which could be done by an advanced optimizing compiler.

Unerstood.

> (Instead of having a syntax that implies an order and then saying "But the compiler is allowed to change the order", I would strongly prefer a syntax that differs substantially from sequential statements.)

Bear with me, on this area i a total noob...

So, immediately above you say "sequential statements". Does that
include the

    c[i, k] = a[i,j] * b[j, k];

above?

(I like to understand thoroughly before I can think clearly. ;-)

My dream is that we can come up with something that "vector folks"
would love, but that also does not look too scary or intractable
to programmers used to "the C notation family", including D.

> By the way: be aware that I only consider *vectorization*, i.e. command level parallelization. Parallelizing whole blocks of code is a completely different story and should be handled separately. That kind of parallelization needs different strategies in the compiler and aims for a mostly distinct audience.

Georg Wrede schrieb:
>> (Instead of having a syntax that implies an order and then saying "But the compiler is allowed to change the order", I would strongly prefer a syntax that differs substantially from sequential statements.)
> 
> So, immediately above you say "sequential statements". Does that
> include the
> 
>     c[i, k] = a[i,j] * b[j, k];
> 
> above?

In a way, yes. What I mean is: C is a strictly sequential language. The programmer is used to the fact that commands are executed in order. (This is, what "sequential" means)

If we want to extend this by constructions that break that strict sequentiality, the syntax should be sufficiently distinct.

> My dream is that we can come up with something that "vector folks"
> would love, but that also does not look too scary or intractable
> to programmers used to "the C notation family", including D.

True. This is my dream as well. Of course, vectorized expressions will never be the first thing to learn for a D newby. They are an advanced concept and people will be able to use D for years without touching it. Anyhow, it should of course fit in as smooth as possible.

As I see it, people can go forth step by step:

1) use D just like C
2) start using arrays
3) start using array expressions (simple to understand, but neither fully flexible nor extendable)
4) start using vectorized expressions (more advanced, fully mixable with array expressions.

To illustrate the last point, it should be clear that array expressions
	int[] a,b,c;
	[...]
	c = a+b;
can always be replaced by their equivalent vectorized expressions
	int[] a,b,c;
	[...]
	assert(a.length == b.length)
	c = [i in 0..a.length](a[i]+b[i]);

Norbert Nemec wrote:
> Georg Wrede schrieb:
> 
>> My dream is that we can come up with something that "vector folks"
>> would love, but that also does not look too scary or intractable
>> to programmers used to "the C notation family", including D.
....
> To illustrate the last point, it should be clear that array expressions
>     int[] a,b,c;
>     [...]
>     c = a+b;
> can always be replaced by their equivalent vectorized expressions
>     int[] a,b,c;
>     [...]
>     assert(a.length == b.length)
>     c = [i in 0..a.length](a[i]+b[i]);

That looks quite nice!

Does that work the same with complicated expressions,
with many indices? Does it still look as nice?

Georg Wrede schrieb:
> Norbert Nemec wrote:
> 
>> Georg Wrede schrieb:
>>
>>> My dream is that we can come up with something that "vector folks"
>>> would love, but that also does not look too scary or intractable
>>> to programmers used to "the C notation family", including D.
> 
> ....
> 
>> To illustrate the last point, it should be clear that array expressions
>>     int[] a,b,c;
>>     [...]
>>     c = a+b;
>> can always be replaced by their equivalent vectorized expressions
>>     int[] a,b,c;
>>     [...]
>>     assert(a.length == b.length)
>>     c = [i in 0..a.length](a[i]+b[i]);
> 
> 
> That looks quite nice!
> 
> Does that work the same with complicated expressions,
> with many indices? Does it still look as nice?

I think, the syntax should scale up rather directly. Of course, complicated expressions will never loop simple, but the syntax also should not get into the way. To restate the example I gave before - matrix multiplication:

	double[,] a,b,c;
	[...initialization of a and b...]
	assert(a.length[1] == b.length[0])
	c = [i in 0..a.length[0],
	     k in 0..b.length[1]]
	    (sum(
	        [j in 0..a.length[1]] (a[i,j]*b[j,k])
	    ));

Be aware, that vectorized expressions give rather lengthy code. Everything has to be given explicitely. Of course, one could think of thousand ways of shorthand notations that do stuff implicitely. However, anything that happens implicitely is bound to get in the way some day when you want to do something unusual. As a short-hand solution, there are (index-free) array expressions. Vectorized expressions on the other hand are meant only for cases where you need full flexibility.

Hi

I have been play a little with the vectorization notation here is some examples.

Adding a scalar to a vector.
[i in 0..l](a[i]+=0.5)

Finding size of a vector.
size=sqrt(sum([i in 0..l](a[i]*a[i])));

Finding dot-product; dot=sum([i in 0..l](a[i]*b[i]));

Matrix vector multiplication.
[i in 0..l](r[i]=sum([j in 0..m](a[i,j]*v[j])));

Calculating the trace of a matrix
res=sum([i in 0..l](a[i,i]));

Taylor expansion on every element in a vector
[i in 0..l](r[i]=sum([j in 0..m](a[j]*pow(v[i],j))));

Calculating Fourier series.
f=sum([j in 0..m](a[j]*cos(j*pi*x/2)+b[j]*sin(j*pi*x/2)))+c;

Calculating (A+I)*v using the Kronecker delta-tensor : delta(i,j)={i=j ? 1 : 0}
[i in 0..l](r[i]=sum([j in 0..m]((a[i,j]+delta(i,j))*v[j])));

Calculating cross product of two 3d vectors using the
antisymmetric tensor/Permutation Tensor/Levi-Civita tensor
[i in 0..3](r[i]=sum([j in 0..3,k in 0..3](anti(i,j,k)*a[i]*b[k])));

Calculating determinant of a 4x4 matrix using the antisymmetric tensor
det=sum([i in 0..4,j in 0..4,k in 0..4,l in 0..4]
    (anti(i,j,k,l)*a[0,i]*a[1,j]*a[2,k]*a[3,l]));

I think we need some way to tell the vectorization engine about special tensors like delta() and anti() !

The vectorization engine should be able to exploit that this tensor is zero many times to optimize the calculations.

In sql one would say "where i!=k and i!=j and j!=k"
in the example with anti(i,j,k).

In this notation we need a way to encapsulate the where statements
into specials tensors so that the vectorization engine
know how to use them in optimization.

Nice work, Knud! Examples always are the best way to test a design idea...



Knud Sørensen schrieb:
> Matrix vector multiplication.
> [i in 0..l](r[i]=sum([j in 0..m](a[i,j]*v[j])));

alternatively:
r[0..l] = [i in 0..l](sum([j in 0..m](a[i,j]*v[j])));

It is interesting to see how the syntax allows different ways to express the same thing.


> Calculating (A+I)*v using the Kronecker delta-tensor : delta(i,j)={i=j ? 1 : 0}
> [i in 0..l](r[i]=sum([j in 0..m]((a[i,j]+delta(i,j))*v[j])));
> 
> Calculating cross product of two 3d vectors using the antisymmetric tensor/Permutation Tensor/Levi-Civita tensor
> [i in 0..3](r[i]=sum([j in 0..3,k in 0..3](anti(i,j,k)*a[i]*b[k])));
> 
> Calculating determinant of a 4x4 matrix using the antisymmetric tensor
> det=sum([i in 0..4,j in 0..4,k in 0..4,l in 0..4]
>     (anti(i,j,k,l)*a[0,i]*a[1,j]*a[2,k]*a[3,l]));
> 
> I think we need some way to tell the vectorization engine about special tensors like delta() and anti() !
> 
> The vectorization engine should be able to exploit that this tensor is zero many times to optimize the calculations.

I think this needs a lot of investigation. Optimization is only possible, if they are inside a sum. It should be considered, but I have no clear concept for it, yet.

> In sql one would say "where i!=k and i!=j and j!=k"
> in the example with anti(i,j,k).

Of course, something like "where" does not really make much sense for vectorized expressions: It would mean that the number and position of the elements in the result depends on their content at runtime, which completely breaks vectorization.

> In this notation we need a way to encapsulate the where statements into specials tensors so that the vectorization engine
> know how to use them in optimization.

Well - as I said, the real power of anti and delta, as you call them (I'm not yet fully convinced of the naming) only shows up when they are used inside a sum. Up to now, I had considered 'sum' a rather stupid function that just takes an arbitrary array and sums it up. If you want the compiler to handle anti and delta, I think most of the intelligence has to go into the 'sum' handling in the compiler.

Anyhow: I think these are rather futuristic considerations. It is interesting to think ahead, of course...

Norbert Nemec wrote:
> Georg Wrede schrieb:
> 
>> Norbert Nemec wrote:
>>
>>> Georg Wrede schrieb:
>>>
>>>> My dream is that we can come up with something that "vector folks"
>>>> would love, but that also does not look too scary or intractable
>>>> to programmers used to "the C notation family", including D.
>>
>>
>> ....
>>
>>> To illustrate the last point, it should be clear that array expressions
>>>     int[] a,b,c;
>>>     [...]
>>>     c = a+b;
>>> can always be replaced by their equivalent vectorized expressions
>>>     int[] a,b,c;
>>>     [...]
>>>     assert(a.length == b.length)
>>>     c = [i in 0..a.length](a[i]+b[i]);
>>
>>
>>
>> That looks quite nice!
>>
>> Does that work the same with complicated expressions,
>> with many indices? Does it still look as nice?
> 
> 
> I think, the syntax should scale up rather directly. Of course, complicated expressions will never loop simple, but the syntax also should not get into the way. To restate the example I gave before - matrix multiplication:
> 
>     double[,] a,b,c;
>     [...initialization of a and b...]
>     assert(a.length[1] == b.length[0])
>     c = [i in 0..a.length[0],
>          k in 0..b.length[1]]
>         (sum(
>             [j in 0..a.length[1]] (a[i,j]*b[j,k])
>         ));

Excellent. This looks quite readable, and doesn't seem to
demand "vectorizing knowledge" from the casual reader. This
is important in projects where only some people are "vector
people".

> Be aware, that vectorized expressions give rather lengthy code. Everything has to be given explicitely. 

I see no problem with that. In a "C family" language it is not
unusual at all to find quite explicit passages in source code.

> Of course, one could think of thousand ways of shorthand notations that do stuff implicitely. However, anything that happens implicitely is bound to get in the way some day when you want to do something unusual. 

True! And the uninitiated would have a hard time understanding
the code.

Knud Sørensen wrote:
> Hi 
> 
> I have been play a little with the vectorization notation
> here is some examples.
> 
> Adding a scalar to a vector.
> [i in 0..l](a[i]+=0.5)
> 
> Finding size of a vector.
> size=sqrt(sum([i in 0..l](a[i]*a[i])));
> 
> Finding dot-product; dot=sum([i in 0..l](a[i]*b[i]));
> 
> Matrix vector multiplication.
> [i in 0..l](r[i]=sum([j in 0..m](a[i,j]*v[j])));
> 
> Calculating the trace of a matrix
> res=sum([i in 0..l](a[i,i]));
> 
> Taylor expansion on every element in a vector
> [i in 0..l](r[i]=sum([j in 0..m](a[j]*pow(v[i],j))));
> 
> Calculating Fourier series.
> f=sum([j in 0..m](a[j]*cos(j*pi*x/2)+b[j]*sin(j*pi*x/2)))+c;
> 
> Calculating (A+I)*v using the Kronecker delta-tensor : delta(i,j)={i=j ? 1 : 0}
> [i in 0..l](r[i]=sum([j in 0..m]((a[i,j]+delta(i,j))*v[j])));
> 
> Calculating cross product of two 3d vectors using the antisymmetric tensor/Permutation Tensor/Levi-Civita tensor
> [i in 0..3](r[i]=sum([j in 0..3,k in 0..3](anti(i,j,k)*a[i]*b[k])));
> 
> Calculating determinant of a 4x4 matrix using the antisymmetric tensor
> det=sum([i in 0..4,j in 0..4,k in 0..4,l in 0..4]
>     (anti(i,j,k,l)*a[0,i]*a[1,j]*a[2,k]*a[3,l]));

In spite of some hairy names above, the code itself looks clear,
and readable! The reader can figure out what's going on without
ever having heard of Fourier.  :-)

In my experience, many times when a specialist programmer gets
stuck, and explains the code to the next cubicle guy, often
the latter can point out the obvious bugs, that are too trivial
for the specialist to notice.

Norbert Nemec wrote:
> Nice work, Knud! Examples always are the best way to test a design idea...
....
>> I think we need some way to tell the vectorization engine about special tensors like delta() and anti() !

Are there some special problems to be expected with that?
(I'm no vector guy.) As in, do delta(), anti() and such
demand something very special from the compiler/language,
or are they just functions that could be written in D
right now? And still work with vectorization?