Making a package safe for use by multiple tasks

Making a package safe for use by multiple tasks

[Alexander Boucke]

Hello!

I am just playing with the idea to use multiple tasks in a programm doing
linear algebra. The problem lies in my vector-algebra package, that uses
some global tmp-object to optimize memory use and reuse. To give you the
idea, some not necessarily correct code snippets what this is doing:

in the spec:

type values is array (<>) or real;
type vector is access values;

function "+" (left, right : vector) return vector;

in the body:

tmp_vec : vector;

function "+" (left, right : vector) return vector is
begin
   -- test here, if the tmp_vec is of correct size and allocated
   for i in tmp_vec'range loop
      tmp_vec(i) := left(i) + right(i);
   end loop;
   return tmp_vec;
end "+";

I hope this gives you the idea. In fact it is a little more complicated,
since I do reference counting on the vectors. The thing with the tmp_vec
enables me to reuse this vector several times, e.g. in d := a + b + c it is
not necessary to allocate it new every time, I could just overwrite tmp_vec
here.

This is of course not usable if I use more then one task! And converting the
whole thing in some kind of protected type is certainly not very useful,
since this would it would not allow parallel execution of vector operations
then.

Except of getting rid of these tmp_vec things, does anybody of you have an
idea, how this could be dealt with. The idea is, that every task needs to
have it's own temporary object. But I have no idea how this could be be
achieved in an automatic or semi-automatic way.

Thanks,

Alexander

Re: Making a package safe for use by multiple tasks

[Grein, Christoph]

From: "Alexander Boucke" <alexb@lufmech.rwth-aachen.de>
 
> idea, how this could be dealt with. The idea is, that every task needs to
> have it's own temporary object. But I have no idea how this could be be
> achieved in an automatic or semi-automatic way.

See RM C.7.2 Task Attributes

Re: Making a package safe for use by multiple tasks

[Alexander Boucke]

Thanks, good idea that might help. I did look in the RM, but not annex C...

Regards,
Alexander

Grein, Christoph wrote in message ...
>From: "Alexander Boucke" <alexb@lufmech.rwth-aachen.de>
>
>> idea, how this could be dealt with. The idea is, that every task needs to
>> have it's own temporary object. But I have no idea how this could be be
>> achieved in an automatic or semi-automatic way.
>
>See RM C.7.2 Task Attributes

Re: Making a package safe for use by multiple tasks

[Marc A. Criley]

Alexander Boucke wrote:
> 
> Hello!
> 
> I am just playing with the idea to use multiple tasks in a programm doing
> linear algebra. The problem lies in my vector-algebra package, that uses
> some global tmp-object to optimize memory use and reuse. To give you the
> idea, some not necessarily correct code snippets what this is doing:
> 
  <snip>

> This is of course not usable if I use more then one task! And converting the
> whole thing in some kind of protected type is certainly not very useful,
> since this would it would not allow parallel execution of vector operations
> then.
> 
> Except of getting rid of these tmp_vec things, does anybody of you have an
> idea, how this could be dealt with. The idea is, that every task needs to
> have it's own temporary object. But I have no idea how this could be be
> achieved in an automatic or semi-automatic way.

Just off the top of my head...I don't know if this would be practical
for you or not, but if you just want to try something quick and dirty,
you could try this:

Convert the package into a generic package, i.e., just add "generic" to
the package spec, then instantiate an instance of the package for each
task.

It's an inelegant and wasteful hack, but hey, I warned you that it was
quick and dirty :-) :-)

Marc A. Criley
Consultant
Quadrus Corporation
www.quadruscorp.com

Re: Making a package safe for use by multiple tasks

[Alexander Boucke]

Marc A. Criley wrote in message <3D00956A.E19C904A@earthlink.net>...
>Alexander Boucke wrote:
>>
>
>Just off the top of my head...I don't know if this would be practical
>for you or not, but if you just want to try something quick and dirty,
>you could try this:
>
>Convert the package into a generic package, i.e., just add "generic" to
>the package spec, then instantiate an instance of the package for each
>task.
>
>It's an inelegant and wasteful hack, but hey, I warned you that it was
>quick and dirty :-) :-)
>
>Marc A. Criley
>Consultant
>Quadrus Corporation
>www.quadruscorp.com

A bit too quick and dirty indeed, especially as the vectors from different
instances are then different types... I think the approach that C. Grein
gave me about using Task_Attributes is just right. This seems to be an easy
way to get a single tmp object for each task and still have one vector type
for the whole program.

Alexander

Re: Making a package safe for use by multiple tasks

[Dr. Michael Paus]

Alexander Boucke wrote:

> I am just playing with the idea to use multiple tasks in a programm doing
> linear algebra. The problem lies in my vector-algebra package, that uses
> some global tmp-object to optimize memory use and reuse. To give you the
> idea, some not necessarily correct code snippets what this is doing:

I do not see how the approach you have shown in you example contributes to
your goals to optimize memory use and reuse. What's the problem with the
following modification to your code?

function "+" (left, right : vector) return vector is
   tmp_vec : vector;
begin
    for i in tmp_vec'range loop
       tmp_vec(i) := left(i) + right(i);
    end loop;
    return tmp_vec;
end "+";

Making tmp_vec a local variable has the following advantages:

- You don't have any problems with tasking (of course the stack size must
   be big enough to hold this array).
- You don't have any problems with recursive calls (this is no problem here
   but is a general problem with static variables).
- You do not have to consider special cases, e.g. what actually happens if
   you do this?
     x := a + (b + c);
   The first call to "+" will pass the access values a and b to the function
   which will place its result into the memory where tmp_vec points to.
   In the second call to "+" the left argument will be a and the right one
   will be tmp_vec. Now in this specific example the result will be correct
   but try to figure out what happens if you write a function which computes
   the cross product of the two vectors according to the same scheme. Your code will
   fail! Generally, using access types in linear algebra packages like this
   is VERY dangerous.
- The performance should be the same or even better than in the original
   example (cpu cache).
- Memory usage is actually better here because tmp_vec will be put
   on the stack and so this memory can be used for other things when the
   function has been finished. In the other case the memory for tmp_vec is
   occupied for the whole runtime of the program. Imagine you have 10 packages
   which use the same scheme. The memory for all these temporary variables will
   be occupied the whole time although you may be using only one of the packages
   at the same time.

So all in all I think that your solution is actually counter productive with
respect to the goals you have stated.

Michael

Re: Making a package safe for use by multiple tasks (Correction)

[Dr. Michael Paus]

One little correction to my above posting. I forgot to mention that
you have to substitude

    type values is array (<>) or real;
    type vector is access values;

by

    type vector is array (<>) or real;

in the case of my modified example code.

Re: Making a package safe for use by multiple tasks

[Ted Dennison]

"Alexander Boucke" <alexb@lufmech.rwth-aachen.de> wrote in message news:<adq0le$2np$1@nets3.rz.RWTH-Aachen.DE>...
> I am just playing with the idea to use multiple tasks in a programm doing
> linear algebra. The problem lies in my vector-algebra package, that uses
> some global tmp-object to optimize memory use and reuse. To give you the
...
> since I do reference counting on the vectors. The thing with the tmp_vec
> enables me to reuse this vector several times, e.g. in d := a + b + c it is
> not necessary to allocate it new every time, I could just overwrite tmp_vec
> here.

Forgive me for a bit of ignorance, but how exactly is this quicker
than making tmp_vec a local variable inside of "+" (which would be
perfectly task safe)? Also, how are you saving enough speed with
either method to make up for the vector copy that happens at the
return statement? Also, complicated operations like your "a + b + c"
construction may even have to allocate memory from the heap to store
the intermediate results. If you are truly that worried about speed,
shouldn't you be using procedures with "in out" parameters instead of
functions?

-- 
T.E.D. 
Home     -  mailto:dennison@telepath.com (Yahoo: Ted_Dennison)
Homepage -  http://www.telepath.com/dennison/Ted/TED.html

Re: Making a package safe for use by multiple tasks

[Georg Bauhaus]

Alexander Boucke <alexb@lufmech.rwth-aachen.de> wrote:
: Hello!
: 
: I am just playing with the idea to use multiple tasks in a programm doing
: linear algebra. The problem lies in my vector-algebra package, that uses

This article by Martin Stift (posted in 2001) names a few resources:
google: protected parallel group:comp.lang.ada author:stift

Re: Making a package safe for use by multiple tasks

[Jeffrey Carter]

Using access values like this is dangerous, even without trying to bring
tasking into the mix. I strongly recommend that you not use access types
for your vector processing. Once you do that, it is simple to make your
operations Pure, which makes adding tasking very easy, since you need do
nothing else.

-- 
Jeff Carter
"If you think you got a nasty taunting this time,
you ain't heard nothing yet!"
Monty Python and the Holy Grail

Re: Making a package safe for use by multiple tasks

[Craig Carey]

On Fri, 07 Jun 2002 21:16:55 GMT, Jeffrey Carter <jrcarter@acm.org>
wrote:

>Using access values like this is dangerous, even without trying to bring
>tasking into the mix. I strongly recommend that you not use access types
>for your vector processing. Once you do that, it is simple to make your
>operations Pure, which makes adding tasking very easy, since you need do
>nothing else.

What is the name of the software and/or compiler, for which that problem
was detected ?. I guess that it is not GNAT 3.14+ in Windows and maybe
not GNAT in some other OSes.


Here is an old comp.lang.ada message of the creator of the thread that 
seems to have maybe significantly better advice:

From: Alexander Boucke (alexb@lufmech.rwth-aachen.de)
Subject: Re: efficient vector/matrix operations in Ada 
Newsgroups: comp.lang.ada
Date: 2001-08-14 01:17:27 PST 
...
>Together with a temporary vector holding all results from sums, this
> leads to equivalent efficiency as using the += operators. You have to
> deal with the overhead due to the garbage collection using controlled
> types, but that is negligible when using large vectors/matrices as in
> typical finite element programs.
...
>package vectors is
...
>  type Vector is new Ada.Finalization.Controlled with private;
...
>  type handled_vector_access is access handled_vector;
>
>  type vector is new ada.finalization.controlled with
>     record
>        the_vector : handled_vector_access;
>     end record;
>
>end vectors;
-----------------

Another message to this thread suggested use of the stack:

On Fri, 07 Jun 2002 15:31:31 +0200, "Dr. Michael Paus"
   <paus@ib-paus.com> wrote:
...
function "+" (left, right : vector) return vector is
>   tmp_vec : vector;
>begin
>    for i in tmp_vec'range loop
>       tmp_vec(i) := left(i) + right(i);
>    end loop;
>    return tmp_vec;
>end "+";
>
>Making tmp_vec a local variable has the following advantages:
>
>- You don't have any problems with tasking (of course the stack size
>   must be big enough to hold this array).


While the stack can be increased, the margin of safety is not especially
obvious. 

Also Ada 95 allows ".all"s to be omitted and hence the fact that access
values are being dereferenced, can be made less explicit and not
clutter up the code. It doesn't seem to be optional.


------------------

Some links to Ada matrix 95 source code doing matrix multiplication:

"Ada95 matrix package" (54KB tar.gz file): Drexel Fusion Laboratory:
   http://dflwww.ece.drexel.edu/research/ada/

Some vector operations in PragmAda (which is a thing going into the new
Ascl source code library, http://ascl.sourceforge.net/ ):
   http://home.earthlink.net/~jrcarter010/pragmarc.htm

Some matrix pivoting source code to solve linear equations:
  http://lglwww.epfl.ch//Team/MW/mw_components.html

Some Ada 95 maths software, simulated annealing:
   http://www.taygeta.com/ada.html , /annealing/simanneal.html

Multiply 2 matrices: http://www.almink.com/school/matrix.html

Bindings to a FORTRAN library:
   http://topo.math.u-psud.fr/~sands/Programs/BLAS/



Craig Carey

Mailing lists: http://www.ijs.co.nz/ada_95.htm

Re: Making a package safe for use by multiple tasks

[Dr. Michael Paus]

Craig Carey wrote:
> 
> On Fri, 07 Jun 2002 21:16:55 GMT, Jeffrey Carter <jrcarter@acm.org>
> wrote:
> 
> 
>>Using access values like this is dangerous, even without trying to bring
>>tasking into the mix. I strongly recommend that you not use access types
>>for your vector processing. Once you do that, it is simple to make your
>>operations Pure, which makes adding tasking very easy, since you need do
>>nothing else.
> 
> 
> What is the name of the software and/or compiler, for which that problem
> was detected ?. I guess that it is not GNAT 3.14+ in Windows and maybe
> not GNAT in some other OSes.

I don't think that Jeffrey Carter had any compiler problem in mind when
he wrote the above statement. The use of access types is dangerous here
because it is difficult to get the algorithm right and because you
encounter all sorts of problems with recursion and tasking. This has
nothing to do with any specific compiler or OS. Just try to figure out
how to extend the concept used for the "+" operator to the computation
of the cross product of two vectors. Try to figure out what happens with
a nested call of this operator.

I also have not seen any statement in this thread which explains what
you are gaining by this access fiddling.

Michael