Possible (summer of code) projects for Octave

classic Classic list List threaded Threaded
29 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Possible (summer of code) projects for Octave

Daniel Kraft
Hi all,

I'm interested to apply for Google Summer of Code with Octave next year
(provided there will be another GSoC and GNU is again accepted as
mentoring organization, but I guess both will be true) and in general to
look into contributing to Octave (although I don't know how much spare
time I can spend on it outside of something like GSoC at the moment).

Octave seems interesting to me in particular since I both use it
frequently (I've just finished Bachelor's courses in maths and physics
and am now doing the respective graduate courses where I do a lot of the
numerical / simulation programs in Octave since it is quite well suited
for what I need to do there) and am also especially interested both in
numerics aspects as well as computer language interpreter / compiler
implementation.  So far I did not dive into the Octave code (besides
compiling it from source and using the C++ interface), but have already
some experience with language implementation in general -- I did
implement emacs lisp support partially in GNU Guile as another GSoC
project two years ago (partially = core language except emacs/text
editor specific stuff like buffer-local bindings) and am working on the
gfortran front-end to GCC for three years now.

Ok, sorry so far for the off-topic description of myself.  What I wanted
to ask is whether there are some ideas for projects to work on that
could fit for GSoC or in general something which is possibly not "fixing
bugs" or doing a lot of "minor" improvements but seperate "new" things
to work on and getting started.  Of course, what came first to my mind
when thinking about this, was JIT or a byte-code VM approach to speed up
interpretation of loops and other stuff -- but from what I read on the
mailing list archives, this is already a somewhat "well known" project
and I understand that there are a lot of difficulties in particular
because of the dynamic typing.  Still, maybe there are currently some
ideas or motivation to try something into that direction?  Otherwise, I
also read something about attempts to make use of multiple cores -- this
sounds interesting, too, are the ongoing projects towards (or interest
in) that?  Some other things that would be useful for Octave and the
user community?

Or possibly it would be best to try implementing some package for
octave-forge which could provide some useful functionality?  I don't
have any idea here, but if there are some, I'd be happy to know and
think about that!

Thanks a lot!  Yours,
Daniel

--
http://www.pro-vegan.info/
--
Done:  Arc-Bar-Cav-Kni-Ran-Rog-Sam-Tou-Val-Wiz
To go: Hea-Mon-Pri
Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

Søren Hauberg
man, 03 01 2011 kl. 20:10 +0100, skrev Daniel Kraft:
> Of course, what came first to my mind
> when thinking about this, was JIT or a byte-code VM approach to speed up
> interpretation of loops and other stuff -- but from what I read on the
> mailing list archives, this is already a somewhat "well known" project
> and I understand that there are a lot of difficulties in particular
> because of the dynamic typing.  Still, maybe there are currently some
> ideas or motivation to try something into that direction?

When I talk to the compiler experts at university they tell me that it
is not an all-that-impossible task to implement something simple here.
Personally, I don't know the first thing in this field so I can't
comment much further except to say that few (if any at all) people on
this list are experts on JIT technology, so anybody working on this
would either need to be an expert or have a working relationship with an
expert.

> Otherwise, I
> also read something about attempts to make use of multiple cores -- this
> sounds interesting, too, are the ongoing projects towards (or interest
> in) that?

Some functionality exists in various packages for this, but having
something easier to use could be quite nice. I've seen work (can't find
the reference right now; ask if you're interested and I'll do my best at
digging it out) for NumPy where several functions got extended for an
extra argument for controlling parallisation of the function. E.g. you
could do something like (syntax is off-the-top-of-my-head)

  b = solve (A, x, num_nodes=10)

which would then distribute the program to 10 nodes in a cluster. I
would find something similar to be quite nice in Octave.

> Some other things that would be useful for Octave and the
> user community?

First things that come to mind:

* Improve the OpenGL graphics system.
* Implement support for object oriented programming using 'classdef'.

Søren

Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

Daniel Kraft
Hi Søren,

thanks a lot for the very quick reply!

Søren Hauberg wrote:

> man, 03 01 2011 kl. 20:10 +0100, skrev Daniel Kraft:
>> Of course, what came first to my mind
>> when thinking about this, was JIT or a byte-code VM approach to speed up
>> interpretation of loops and other stuff -- but from what I read on the
>> mailing list archives, this is already a somewhat "well known" project
>> and I understand that there are a lot of difficulties in particular
>> because of the dynamic typing.  Still, maybe there are currently some
>> ideas or motivation to try something into that direction?
>
> When I talk to the compiler experts at university they tell me that it
> is not an all-that-impossible task to implement something simple here.
> Personally, I don't know the first thing in this field so I can't
> comment much further except to say that few (if any at all) people on
> this list are experts on JIT technology, so anybody working on this
> would either need to be an expert or have a working relationship with an
> expert.

I'm also not really an expert or experienced with JIT technology of
related stuff, unfortunately.  What I do for gfortran/GCC is basically
front-end stuff (like implementation of Fortran 2003 OOP features) and I
did not yet touch any optimization or code-generation in GCC.  But on
the other hand, I guess that using existing frameworks like LLVM the
main concern is not compilation technology and code generation but more
about how to translate Octave into a more static form.

My impression is also, that maybe one could find some simple heuristics
for infering types in "easy cases" (whatever that means) that still give
good performance improvements for real-world codes.  Sounds like a
possibility -- at least if I have some ideas for what to propose there.
  But this means that currently there are no projects in planning or
development to tackle something like that?

>> Otherwise, I
>> also read something about attempts to make use of multiple cores -- this
>> sounds interesting, too, are the ongoing projects towards (or interest
>> in) that?
>
> Some functionality exists in various packages for this, but having
> something easier to use could be quite nice. I've seen work (can't find
> the reference right now; ask if you're interested and I'll do my best at
> digging it out) for NumPy where several functions got extended for an
> extra argument for controlling parallisation of the function. E.g. you
> could do something like (syntax is off-the-top-of-my-head)
>
>   b = solve (A, x, num_nodes=10)
>
> which would then distribute the program to 10 nodes in a cluster. I
> would find something similar to be quite nice in Octave.

My first thought was more about using simple parallel algorithms (and
probably mostly shared-memory with few cores rather than cluster
computing) for stuff like matrix/vector element-wise operations,
dot-products or BLAS in general.  Although, I think that it is not
always easy to come up with code that performs well on different
architectures or for different problem sizes -- and AFAIK, Octave uses
BLAS/LAPACK routines for (some of) those operations, right?  I don't
really know, but I could imagine that there are already projects out
there to develop (free and portable) parallel BLAS routines.  So maybe
one could "simply" try integrating them into Octave and implementing
some framework to control parallelization depending on the problem size
and user preferences or the like.

But of course also extension of selected existing Octave functions in a
way you mention it above seems like an interesting idea.  Do you know
what the opinions of "the community" are with respect to this ansatz in
general?  Would it be considered useful, and for which functions /
functionality?

>> Some other things that would be useful for Octave and the
>> user community?
>
> First things that come to mind:
>
> * Improve the OpenGL graphics system.
> * Implement support for object oriented programming using 'classdef'.

Thanks for the suggestions here!  I have to admit that so far I did not
yet use the OpenGL graphics (but have used OpenGL a bit from C++ if that
is related or could help) and am also using Octave usually in a "simple"
way (i.e., no OOP) -- but I am and have been somewhat involved in the
(ongoing) implementation of OOP features in gfortran.  Of course, OOP in
Octave is probably much different from OOP in Fortran (as this is very
different in certain areas from OOP in C++/Java), but this also sounds
interesting.

Yours,
Daniel

--
http://www.pro-vegan.info/
--
Done:  Arc-Bar-Cav-Kni-Ran-Rog-Sam-Tou-Val-Wiz
To go: Hea-Mon-Pri
Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

Søren Hauberg
man, 03 01 2011 kl. 21:49 +0100, skrev Daniel Kraft:
> I'm also not really an expert or experienced with JIT technology of
> related stuff, unfortunately.  What I do for gfortran/GCC is basically
> front-end stuff (like implementation of Fortran 2003 OOP features) and I
> did not yet touch any optimization or code-generation in GCC.  But on
> the other hand, I guess that using existing frameworks like LLVM the
> main concern is not compilation technology and code generation but more
> about how to translate Octave into a more static form.

The simplest thing (according to the compiler people I hang out with
from time to time) would most likely be to output C++ code. Then the
missing part is essentially "just" type estimation. I don't think this
is particularly easy, but I'm really no expert here...

>   But this means that currently there are no projects in planning or
> development to tackle something like that?

Not anything I know of.

> My first thought was more about using simple parallel algorithms (and
> probably mostly shared-memory with few cores rather than cluster
> computing) for stuff like matrix/vector element-wise operations,
> dot-products or BLAS in general.  Although, I think that it is not
> always easy to come up with code that performs well on different
> architectures or for different problem sizes -- and AFAIK, Octave uses
> BLAS/LAPACK routines for (some of) those operations, right?  I don't
> really know, but I could imagine that there are already projects out
> there to develop (free and portable) parallel BLAS routines.  So maybe
> one could "simply" try integrating them into Octave and implementing
> some framework to control parallelization depending on the problem size
> and user preferences or the like.

I would tend to agree. Having mechanisms for switching BLAS/LAPACK
implementation at run-time could potentially be quite nice. I'm not sure
it's particularly easy, though.

> But of course also extension of selected existing Octave functions in a
> way you mention it above seems like an interesting idea.  Do you know
> what the opinions of "the community" are with respect to this ansatz in
> general?  Would it be considered useful, and for which functions /
> functionality?

I would consider it useful. My guess would be that others would feel the
same way if the code was simple enough to maintain. Such features would
never stand a chance if they where too hard to maintain.

Cheers
Søren

Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

Jaroslav Hajek-2
On Mon, Jan 3, 2011 at 10:22 PM, Søren Hauberg <[hidden email]> wrote:

> man, 03 01 2011 kl. 21:49 +0100, skrev Daniel Kraft:
>> I'm also not really an expert or experienced with JIT technology of
>> related stuff, unfortunately.  What I do for gfortran/GCC is basically
>> front-end stuff (like implementation of Fortran 2003 OOP features) and I
>> did not yet touch any optimization or code-generation in GCC.  But on
>> the other hand, I guess that using existing frameworks like LLVM the
>> main concern is not compilation technology and code generation but more
>> about how to translate Octave into a more static form.
>
> The simplest thing (according to the compiler people I hang out with
> from time to time) would most likely be to output C++ code. Then the
> missing part is essentially "just" type estimation. I don't think this
> is particularly easy, but I'm really no expert here...
>
>>   But this means that currently there are no projects in planning or
>> development to tackle something like that?
>
> Not anything I know of.
>
>> My first thought was more about using simple parallel algorithms (and
>> probably mostly shared-memory with few cores rather than cluster
>> computing) for stuff like matrix/vector element-wise operations,
>> dot-products or BLAS in general.  Although, I think that it is not
>> always easy to come up with code that performs well on different
>> architectures or for different problem sizes -- and AFAIK, Octave uses
>> BLAS/LAPACK routines for (some of) those operations, right?  I don't
>> really know, but I could imagine that there are already projects out
>> there to develop (free and portable) parallel BLAS routines.  So maybe
>> one could "simply" try integrating them into Octave and implementing
>> some framework to control parallelization depending on the problem size
>> and user preferences or the like.
>
> I would tend to agree. Having mechanisms for switching BLAS/LAPACK
> implementation at run-time could potentially be quite nice. I'm not sure
> it's particularly easy, though.
>

I really doubt that. It often takes some effort to tune the
configuration to make a single BLAS/LAPACK library compile with
Octave, let alone multiple ones. For no obvious benefit, at least I
don't see one. A number of BLAS libs (e.g. GotoBLAS) are parallelized
and the number of threads is usually controllable by some run-time
mechanism, but for obvious reasons that differs. NumPy is (at least
was when I last checked) strongly ATLAS-biased and I would not be
surprised if they simply exposed the feature just for ATLAS.
Octave tries to be more neutral w.r.t. BLAS, so if anyone wanted to do
something like this in Octave, it would probably involve some
extensive configure-checking to assess the proper API. But otherwise
it wouldn't be that hard.


>> But of course also extension of selected existing Octave functions in a
>> way you mention it above seems like an interesting idea.  Do you know
>> what the opinions of "the community" are with respect to this ansatz in
>> general?  Would it be considered useful, and for which functions /
>> functionality?
>
> I would consider it useful. My guess would be that others would feel the
> same way if the code was simple enough to maintain. Such features would
> never stand a chance if they where too hard to maintain.
>
> Cheers
> Søren
>
>
Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

Jaroslav Hajek-2
In reply to this post by Daniel Kraft
On Mon, Jan 3, 2011 at 8:10 PM, Daniel Kraft <[hidden email]> wrote:
> Hi all,
>
> I'm interested to apply for Google Summer of Code with Octave next year
> (provided there will be another GSoC and GNU is again accepted as mentoring
> organization, but I guess both will be true) and in general to look into
> contributing to Octave (although I don't know how much spare time I can
> spend on it outside of something like GSoC at the moment).
>

IIRC, mentors from Google itself are also acceptable under some
conditions. If that's still true, I could volunteer as a mentor. I
used to be a very active Octave developer not so long ago :)

> Octave seems interesting to me in particular since I both use it frequently
> (I've just finished Bachelor's courses in maths and physics and am now doing
> the respective graduate courses where I do a lot of the numerical /
> simulation programs in Octave since it is quite well suited for what I need
> to do there) and am also especially interested both in numerics aspects as
> well as computer language interpreter / compiler implementation.  So far I
> did not dive into the Octave code (besides compiling it from source and
> using the C++ interface),

If you compiled with (almost) all dependencies, that's already a minor
achivement :)

> but have already some experience with language
> implementation in general -- I did implement emacs lisp support partially in
> GNU Guile as another GSoC project two years ago (partially = core language
> except emacs/text editor specific stuff like buffer-local bindings) and am
> working on the gfortran front-end to GCC for three years now.
>
> Ok, sorry so far for the off-topic description of myself.  What I wanted to
> ask is whether there are some ideas for projects to work on that could fit
> for GSoC or in general something which is possibly not "fixing bugs" or
> doing a lot of "minor" improvements but seperate "new" things to work on and
> getting started.

My favorite is implementing the OOP versions of delaunay triangulation
and interpolation functions. See
http://www.mathworks.ch/help/techdoc/ref/delaunaytriclass.html
http://www.mathworks.ch/help/techdoc/ref/trirepclass.html
http://www.mathworks.ch/help/techdoc/ref/triscatteredinterpclass.html

in contrast to the existing delaunay et al. functions, the OOP
approach is not only fancy, it allows you encapsulate & reuse more
important topological data to make things like lookup & interpolation
way faster.
For instance, if you want to triangulate an area nad then lookup
enclosing triangles for a set of points, you'd use delaunay & tsearch
in Octave; the problem is that the latter is sadly inefficient because
it's not able to accept any more information than a plain list of
triangles from the delaunay triangulation (it can't even assume the
triangulation is delaunay).


> Of course, what came first to my mind when thinking about
> this, was JIT or a byte-code VM approach to speed up interpretation of loops
> and other stuff -- but from what I read on the mailing list archives, this
> is already a somewhat "well known" project and I understand that there are a
> lot of difficulties in particular because of the dynamic typing.

And not my favorite one, I must add :)

> Still,
> maybe there are currently some ideas or motivation to try something into
> that direction?  Otherwise, I also read something about attempts to make use
> of multiple cores -- this sounds interesting, too, are the ongoing projects
> towards (or interest in) that?  Some other things that would be useful for
> Octave and the user community?
>

I think what Octave needs to be considered seriously in the future is
better support for high-level parallelism. Low-level cheap stuff like
parallelizing sum() is laughable, IMHO - might be good for MW to boost
their PR image, but in real life that will win you almost nothing. I
and D. Bateman actually experimented with code to parallelize some
element-wise matrix operations, and the results were, IMHO, poor.
Parallelizing costly built-ins like pinv() or fft() is a good idea,
but that's usually best handled by libs that implement them (BLAS,
FFTW). Some mappers (e.g. erfinv) may also fall into this area, and
that should not be hard to do.

The main problem with this is that the interpreter is not remotely
thread-safe, which makes high-level multithreading impossible. One
option is to use multiprocessing instead - look at general/parcellfun
or openmpi on OctaveForge. The other option, of course, is to make
Octave thread-safe. That would be a big enough project without any
doubt, I'm just not sure it's academic enough.
Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

bpabbott
Administrator
On Jan 4, 2011, at 8:18 AM, Jaroslav Hajek wrote:

>> Ok, sorry so far for the off-topic description of myself.  What I wanted to
>> ask is whether there are some ideas for projects to work on that could fit
>> for GSoC or in general something which is possibly not "fixing bugs" or
>> doing a lot of "minor" improvements but seperate "new" things to work on and
>> getting started.
>
> My favorite is implementing the OOP versions of delaunay triangulation
> and interpolation functions. See
> http://www.mathworks.ch/help/techdoc/ref/delaunaytriclass.html
> http://www.mathworks.ch/help/techdoc/ref/trirepclass.html
> http://www.mathworks.ch/help/techdoc/ref/triscatteredinterpclass.html
>
> in contrast to the existing delaunay et al. functions, the OOP
> approach is not only fancy, it allows you encapsulate & reuse more
> important topological data to make things like lookup & interpolation
> way faster.
> For instance, if you want to triangulate an area and then lookup
> enclosing triangles for a set of points, you'd use delaunay & tsearch
> in Octave; the problem is that the latter is sadly inefficient because
> it's not able to accept any more information than a plain list of
> triangles from the delaunay triangulation (it can't even assume the
> triangulation is delaunay).

This would also benefit Octave's core since the new OOP approach is not yet complete in Octave.

Ben
Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

Jordi Gutiérrez Hermoso
In reply to this post by Jaroslav Hajek-2
On 4 January 2011 07:18, Jaroslav Hajek <[hidden email]> wrote:
> On Mon, Jan 3, 2011 at 8:10 PM, Daniel Kraft <[hidden email]> wrote:

>> What I wanted to ask is whether there are some ideas for projects
>> to work on that could fit for GSoC or in general something which is
>> possibly not "fixing bugs" or doing a lot of "minor" improvements
>> but seperate "new" things to work on and getting started.
>
> My favorite is implementing the OOP versions of delaunay triangulation
> and interpolation functions. See
> http://www.mathworks.ch/help/techdoc/ref/delaunaytriclass.html
> http://www.mathworks.ch/help/techdoc/ref/trirepclass.html
> http://www.mathworks.ch/help/techdoc/ref/triscatteredinterpclass.html

Speaking of Delaunay triangulations, I just came across this, which
was wikispammed in Wikipedia's article about the topic:

     http://www.s-hull.org/

The algorithm does indeed appear to outperform QHull at least for some
cases. The code is in really bad shape, though. It's not actually
GPLed, apparently. The actual license you see in the tarball is more
BSD-like, but it's homegrown, and the author seems to have little
patience for licensing administrivia, as he frequently includes silly
conditions like "you must not wear a red tie". It's also got a lot of
dead code, cargo cult sections (e.g. none of the libraries the
Makefile links to are necessary), many unncessary #includes,
uncommented debug code, "goat" as a frequent variable name...

Regardless, the algorithm seems to work. It could be worthwhile to
polish the code and contact the author about providing reasonable
licensing conditions. I've been doing the former privately, but I
don't think I should publish my modifications before asking the author
if it's ok.

- Jordi G. H.
Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

David Bateman
In reply to this post by Jaroslav Hajek-2
Jaroslav Hajek-2 wrote
On Mon, Jan 3, 2011 at 8:10 PM, Daniel Kraft <d@domob.eu> wrote:
> Still,
> maybe there are currently some ideas or motivation to try something into
> that direction?  Otherwise, I also read something about attempts to make use
> of multiple cores -- this sounds interesting, too, are the ongoing projects
> towards (or interest in) that?  Some other things that would be useful for
> Octave and the user community?
>

I think what Octave needs to be considered seriously in the future is
better support for high-level parallelism. Low-level cheap stuff like
parallelizing sum() is laughable, IMHO - might be good for MW to boost
their PR image, but in real life that will win you almost nothing. I
and D. Bateman actually experimented with code to parallelize some
element-wise matrix operations, and the results were, IMHO, poor.
Parallelizing the element-wise matrix operators gave poor performance, but parallelizing the mapper functions gave speed-ups that scaled well with the number of cores. In the thread

http://octave.1599824.n4.nabble.com/Using-OpenMP-in-Octave-td1694553.html

You tested with 2 threads and Kai Habel with 4 and you both showed nearly linear speed-up with the mapper functions. Kai on his AMD even showed slight improvements for the element-wise operators. I'd say its worth trying to improve the speed of the mappers.

D.
Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

Jaroslav Hajek-2
On Tue, Jan 4, 2011 at 4:52 PM, David Bateman <[hidden email]> wrote:

>
>
> Jaroslav Hajek-2 wrote:
>>
>> On Mon, Jan 3, 2011 at 8:10 PM, Daniel Kraft <[hidden email]> wrote:
>>> Still,
>>> maybe there are currently some ideas or motivation to try something into
>>> that direction?  Otherwise, I also read something about attempts to make
>>> use
>>> of multiple cores -- this sounds interesting, too, are the ongoing
>>> projects
>>> towards (or interest in) that?  Some other things that would be useful
>>> for
>>> Octave and the user community?
>>>
>>
>> I think what Octave needs to be considered seriously in the future is
>> better support for high-level parallelism. Low-level cheap stuff like
>> parallelizing sum() is laughable, IMHO - might be good for MW to boost
>> their PR image, but in real life that will win you almost nothing. I
>> and D. Bateman actually experimented with code to parallelize some
>> element-wise matrix operations, and the results were, IMHO, poor.
>>
>
> Parallelizing the element-wise matrix operators gave poor performance, but
> parallelizing the mapper functions gave speed-ups that scaled well with the
> number of cores. In the thread
>
> http://octave.1599824.n4.nabble.com/Using-OpenMP-in-Octave-td1694553.html
>
> You tested with 2 threads and Kai Habel with 4 and you both showed nearly
> linear speed-up with the mapper functions. Kai on his AMD even showed slight
> improvements for the element-wise operators. I'd say its worth trying to
> improve the speed of the mappers.
>

Yes, I never objected to that, it's just harder than it seems because
of the exceptions issues.
It is possible to either
1. make the parallelizing code exception-safe
2. parallelize only mappers that don't throw exceptions (possibly
conditionally on configuration)

first I wanted to do 1., but eventually I realized that 2. would not
be that bad and probably simpler.
Regarding the multithreaded element-wise ops, we basically have a
patch. I would just object to putting it into 3.4. on the basis that
it is the most useless part of low-level multithreading. Octave don't
need to kid its users that it can do mt when it actually can't mt
anything useful.
Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

Michael Creel


On Tue, Jan 4, 2011 at 5:26 PM, Jaroslav Hajek <[hidden email]> wrote:
On Tue, Jan 4, 2011 at 4:52 PM, David Bateman <[hidden email]> wrote:
>
>
> Jaroslav Hajek-2 wrote:
>>
>> On Mon, Jan 3, 2011 at 8:10 PM, Daniel Kraft <[hidden email]> wrote:
>>> Still,
>>> maybe there are currently some ideas or motivation to try something into
>>> that direction?  Otherwise, I also read something about attempts to make
>>> use
>>> of multiple cores -- this sounds interesting, too, are the ongoing
>>> projects
>>> towards (or interest in) that?  Some other things that would be useful
>>> for
>>> Octave and the user community?
>>>
>>
>> I think what Octave needs to be considered seriously in the future is
>> better support for high-level parallelism. Low-level cheap stuff like
>> parallelizing sum() is laughable, IMHO - might be good for MW to boost
>> their PR image, but in real life that will win you almost nothing. I
>> and D. Bateman actually experimented with code to parallelize some
>> element-wise matrix operations, and the results were, IMHO, poor.
>>
>
> Parallelizing the element-wise matrix operators gave poor performance, but
> parallelizing the mapper functions gave speed-ups that scaled well with the
> number of cores. In the thread
>
> http://octave.1599824.n4.nabble.com/Using-OpenMP-in-Octave-td1694553.html
>
> You tested with 2 threads and Kai Habel with 4 and you both showed nearly
> linear speed-up with the mapper functions. Kai on his AMD even showed slight
> improvements for the element-wise operators. I'd say its worth trying to
> improve the speed of the mappers.
>

Yes, I never objected to that, it's just harder than it seems because
of the exceptions issues.
It is possible to either
1. make the parallelizing code exception-safe
2. parallelize only mappers that don't throw exceptions (possibly
conditionally on configuration)

first I wanted to do 1., but eventually I realized that 2. would not
be that bad and probably simpler.
Regarding the multithreaded element-wise ops, we basically have a
patch. I would just object to putting it into 3.4. on the basis that
it is the most useless part of low-level multithreading. Octave don't
need to kid its users that it can do mt when it actually can't mt
anything useful.


Perhaps some effort to allow GPUs to be used for certain computations would be possible? The Theano project mentions "transparent use of a GPU" http://deeplearning.net/software/theano/index.html   
Happy new year to all,
Michael
Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

John W. Eaton
Administrator
On  4-Jan-2011, Michael Creel wrote:

| Perhaps some effort to allow GPUs to be used for certain computations would be
| possible? The Theano project mentions "transparent use of a GPU" http://
| deeplearning.net/software/theano/index.html   

Is there any way of doing this that doesn't require proprietary CUDA
libraries?

jwe
 
Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

Jordi Gutiérrez Hermoso
In reply to this post by Daniel Kraft
On 3 January 2011 13:10, Daniel Kraft <[hidden email]> wrote:
> was JIT or a byte-code VM approach to speed up interpretation of
> loops and other stuff
[snip]
> Otherwise, I also read something about attempts to make use of
> multiple cores
[snip]
> Or possibly it would be best to try implementing some package for
> octave-forge which could provide some useful functionality?

There is another project which is just as important as all these even
if it's not as glamourous: Octave needs a GUI, IDE, black-on-white
terminal with antialiased fonts; whatever you want to call it, and it
needs an officially sanctioned one, in the same source tree as the
rest of Octave, or at least as a Mercurial subrepo.

The reason for this isn't technical, but social and aesthetic. Selling
Octave right now is difficult not due to its technical merits which
are many, but because people associate Octave with "a DOS application"
or "CLI only, and I don't know CLI". It doesn't matter if people who
believe these things about Octave are right or not. We are simply not
going be able to reach as many people as long as Octave doesn't have
an interface that more people are familiar with.

I think QtOctave is right now the project closest to achieving this
goal. It has many problems, but the project's overall direction is
correct. By using Qt, it solves the aesthetic problem multiplatformly,
and it already has the fluff that people expect from applications. It
doesn't have to mimic Matlab's interface, and in fact I hope it
manages to find its own style. A worksheet-like interface instead of a
glorified terminal like what Matlab does would be quite nice.

The biggest problems QtOctave right now have all stem from the awkward
terminal it creates and the IPC with Octave. I think the coupling
should be much tighter, perhaps multithreading the two into one
process. From what you say about yourself, I don't think you would be
interested in this project, because it involves almost zero
mathematical sophistication. It's just a task that really needs to be
done for Octave's sake. I mentioned this possibility anyways because
it's important.

- Jordi G. H.
Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

Michael Creel
In reply to this post by John W. Eaton


On Tue, Jan 4, 2011 at 6:23 PM, John W. Eaton <[hidden email]> wrote:
On  4-Jan-2011, Michael Creel wrote:

| Perhaps some effort to allow GPUs to be used for certain computations would be
| possible? The Theano project mentions "transparent use of a GPU" http://
| deeplearning.net/software/theano/index.html   

Is there any way of doing this that doesn't require proprietary CUDA
libraries?

jwe

There is OpenCL, which I believe is licensed in a way that could be used with Octave. CUDA is definitely a no-go. I haven't looked at GPU stuff for a while though, so I'm not sure.
Michael
Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

Jordi Gutiérrez Hermoso
Btw, this thread is a wonderful opportunity go and review and update
this list, perhaps categorising it by difficulty for the benefit of
potential GSoC mentees:

     http://wiki.octave.org/wiki.pl?Projects

- Jordi G. H.
Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

Daniel Kraft
In reply to this post by Søren Hauberg
Søren Hauberg wrote:

> man, 03 01 2011 kl. 21:49 +0100, skrev Daniel Kraft:
>> I'm also not really an expert or experienced with JIT technology of
>> related stuff, unfortunately.  What I do for gfortran/GCC is basically
>> front-end stuff (like implementation of Fortran 2003 OOP features) and I
>> did not yet touch any optimization or code-generation in GCC.  But on
>> the other hand, I guess that using existing frameworks like LLVM the
>> main concern is not compilation technology and code generation but more
>> about how to translate Octave into a more static form.
>
> The simplest thing (according to the compiler people I hang out with
> from time to time) would most likely be to output C++ code. Then the
> missing part is essentially "just" type estimation. I don't think this
> is particularly easy, but I'm really no expert here...

But this then means we would try to compile a whole function by writing
out a generated C++ implementation of it and then running mkoctfile?  Or
a little more sophisticated?

I think it would possibly also be useful to JIT only certain blocks of
code (like loops which have a large number of iterations but do not
contain any complicated (or any at all) function calls).  Or do you mean
we should/could output also C++ code only for such a loop and have it
compiled into a function which is then called instead of interpreting
the loop?

BTW, my impression is that mkoctfile takes rather long times to complete
-- on the order of some seconds on my system usually.  This is not
really what I expect as comile-times for JIT'ing code.

Yours,
Daniel

--
http://www.pro-vegan.info/
--
Done:  Arc-Bar-Cav-Kni-Ran-Rog-Sam-Tou-Val-Wiz
To go: Hea-Mon-Pri
Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

Daniel Kraft
In reply to this post by Jaroslav Hajek-2
Jaroslav Hajek wrote:

> On Mon, Jan 3, 2011 at 8:10 PM, Daniel Kraft <[hidden email]> wrote:
>> Hi all,
>>
>> I'm interested to apply for Google Summer of Code with Octave next year
>> (provided there will be another GSoC and GNU is again accepted as mentoring
>> organization, but I guess both will be true) and in general to look into
>> contributing to Octave (although I don't know how much spare time I can
>> spend on it outside of something like GSoC at the moment).
>>
>
> IIRC, mentors from Google itself are also acceptable under some
> conditions. If that's still true, I could volunteer as a mentor. I
> used to be a very active Octave developer not so long ago :)

I think that's true -- however, I guess that an application for the GNU
project (in case it is again accepted) would also do and you (or someone
else from Octave) could mentor for it.  This is how I worked on GNU
Guile two years ago.

> If you compiled with (almost) all dependencies, that's already a minor
> achivement :)

Well, I did with what I need -- and this in several steps, but now I
have at least SuiteSparse, QHull and ARPACK working; maybe something
else, but if so I just forgot that. :)

>> Ok, sorry so far for the off-topic description of myself.  What I wanted to
>> ask is whether there are some ideas for projects to work on that could fit
>> for GSoC or in general something which is possibly not "fixing bugs" or
>> doing a lot of "minor" improvements but seperate "new" things to work on and
>> getting started.
>
> My favorite is implementing the OOP versions of delaunay triangulation
> and interpolation functions. See
> http://www.mathworks.ch/help/techdoc/ref/delaunaytriclass.html
> http://www.mathworks.ch/help/techdoc/ref/trirepclass.html
> http://www.mathworks.ch/help/techdoc/ref/triscatteredinterpclass.html
>
> in contrast to the existing delaunay et al. functions, the OOP
> approach is not only fancy, it allows you encapsulate & reuse more
> important topological data to make things like lookup & interpolation
> way faster.
> For instance, if you want to triangulate an area nad then lookup
> enclosing triangles for a set of points, you'd use delaunay & tsearch
> in Octave; the problem is that the latter is sadly inefficient because
> it's not able to accept any more information than a plain list of
> triangles from the delaunay triangulation (it can't even assume the
> triangulation is delaunay).

This actually sounds quite interesting!  Although I did not yet work at
all with OOP in Octave (or Matlab), but I guess this would make it even
more interesting and beneficial and should not be too hard to get into.

I'm just not sure how "important" this would be for Octave itself --
delaunay triangulation and related stuff seems like a more or less
specific topic; although there was also a reply that this could help OOP
in Octave in general (but at the moment I do not know how).

Are you aware of more cases like this?  Then one could think about a
more general project to implement some OOP interfaces to functions.

>> Still,
>> maybe there are currently some ideas or motivation to try something into
>> that direction?  Otherwise, I also read something about attempts to make use
>> of multiple cores -- this sounds interesting, too, are the ongoing projects
>> towards (or interest in) that?  Some other things that would be useful for
>> Octave and the user community?
>>
>
> I think what Octave needs to be considered seriously in the future is
> better support for high-level parallelism. Low-level cheap stuff like
> parallelizing sum() is laughable, IMHO - might be good for MW to boost
> their PR image, but in real life that will win you almost nothing. I
> and D. Bateman actually experimented with code to parallelize some
> element-wise matrix operations, and the results were, IMHO, poor.
> Parallelizing costly built-ins like pinv() or fft() is a good idea,
> but that's usually best handled by libs that implement them (BLAS,
> FFTW). Some mappers (e.g. erfinv) may also fall into this area, and
> that should not be hard to do.

So it seems that here we either have stuff that is not really useful
(like the element-wise operators or sum), or is / is to be handled by an
external library (FFT, more complex BLAS, LAPACK).  For the mappers,
there seems to be already some existing code and efforts.

> The main problem with this is that the interpreter is not remotely
> thread-safe, which makes high-level multithreading impossible. One
> option is to use multiprocessing instead - look at general/parcellfun
> or openmpi on OctaveForge. The other option, of course, is to make
> Octave thread-safe. That would be a big enough project without any
> doubt, I'm just not sure it's academic enough.

Hm, this also sounds like something really useful.  Maybe this could
help in general with parallelization projects (whatever they are in the
end) or for user-side, high-level parallelization (like, for instance,
OpenMP-style declarations for parallel loops and the like -- although
I'm not sure how useful this would be in Octave).

And in order to make it more "interesting" or "academic" (in case this
is really needed), one could just add some efforts building on this
towards parallization ;)

Cheers,
Daniel

--
http://www.pro-vegan.info/
--
Done:  Arc-Bar-Cav-Kni-Ran-Rog-Sam-Tou-Val-Wiz
To go: Hea-Mon-Pri
Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

Daniel Kraft
In reply to this post by Jordi Gutiérrez Hermoso
Jordi Gutiérrez Hermoso wrote:

> On 3 January 2011 13:10, Daniel Kraft <[hidden email]> wrote:
>> was JIT or a byte-code VM approach to speed up interpretation of
>> loops and other stuff
> [snip]
>> Otherwise, I also read something about attempts to make use of
>> multiple cores
> [snip]
>> Or possibly it would be best to try implementing some package for
>> octave-forge which could provide some useful functionality?
>
> There is another project which is just as important as all these even
> if it's not as glamourous: Octave needs a GUI, IDE, black-on-white
> terminal with antialiased fonts; whatever you want to call it, and it
> needs an officially sanctioned one, in the same source tree as the
> rest of Octave, or at least as a Mercurial subrepo.
>
> The reason for this isn't technical, but social and aesthetic. Selling
> Octave right now is difficult not due to its technical merits which
> are many, but because people associate Octave with "a DOS application"
> or "CLI only, and I don't know CLI". It doesn't matter if people who
> believe these things about Octave are right or not. We are simply not
> going be able to reach as many people as long as Octave doesn't have
> an interface that more people are familiar with.

I totally agree here -- but personally (maybe like most of the people on
this list?) I'm more a fan of command-line interfaces and probably would
not use such an interface in case it existed.  I'm also probably not
really creative at designing graphical interfaces... so I think this is
not the right project for me.

But yes, I really understand and agree that this is something very
important to help spread Octave and make it attractive for more users.

Yours,
Daniel

--
http://www.pro-vegan.info/
--
Done:  Arc-Bar-Cav-Kni-Ran-Rog-Sam-Tou-Val-Wiz
To go: Hea-Mon-Pri
Reply | Threaded
Open this post in threaded view
|

Re: Possible (summer of code) projects for Octave

Søren Hauberg
In reply to this post by Daniel Kraft
tir, 04 01 2011 kl. 19:35 +0100, skrev Daniel Kraft:

> Søren Hauberg wrote:
> > man, 03 01 2011 kl. 21:49 +0100, skrev Daniel Kraft:
> >> I'm also not really an expert or experienced with JIT technology of
> >> related stuff, unfortunately.  What I do for gfortran/GCC is basically
> >> front-end stuff (like implementation of Fortran 2003 OOP features) and I
> >> did not yet touch any optimization or code-generation in GCC.  But on
> >> the other hand, I guess that using existing frameworks like LLVM the
> >> main concern is not compilation technology and code generation but more
> >> about how to translate Octave into a more static form.
> >
> > The simplest thing (according to the compiler people I hang out with
> > from time to time) would most likely be to output C++ code. Then the
> > missing part is essentially "just" type estimation. I don't think this
> > is particularly easy, but I'm really no expert here...
>
> But this then means we would try to compile a whole function by writing
> out a generated C++ implementation of it and then running mkoctfile?  Or
> a little more sophisticated?
>
> I think it would possibly also be useful to JIT only certain blocks of
> code (like loops which have a large number of iterations but do not
> contain any complicated (or any at all) function calls).  Or do you mean
> we should/could output also C++ code only for such a loop and have it
> compiled into a function which is then called instead of interpreting
> the loop?
>
> BTW, my impression is that mkoctfile takes rather long times to complete
> -- on the order of some seconds on my system usually.  This is not
> really what I expect as comile-times for JIT'ing code.

For many applications it would be just to be able to generate C++ code
and compile it even if that process would take a couple of minutes. This
could be done for the m-files distributed with Octave and people could
do it manually if needed. Obviously an automatic solution would be
nicer, but this would solve many practical problems.

Søren

Reply | Threaded
Open this post in threaded view
|

GUI [was: Re: Possible (summer of code) projects for Octave]

Søren Hauberg
In reply to this post by Jordi Gutiérrez Hermoso
tir, 04 01 2011 kl. 11:35 -0600, skrev Jordi Gutiérrez Hermoso:
> There is another project which is just as important as all these even
> if it's not as glamourous: Octave needs a GUI, IDE, black-on-white
> terminal with antialiased fonts; whatever you want to call it, and it
> needs an officially sanctioned one, in the same source tree as the
> rest of Octave, or at least as a Mercurial subrepo.

I think what is really needed is a nicer C++ interface to the
interpreter. Quite some time ago I played a bit with GUI's and I arrived
at the conclusion that the best solution right now is that taken by
OctaveDE (hooking into the readline idle loop). With that approach you,
however, not do much more than embed a terminal in your application.

I would love it if we had a C++ interface that allowed you to:

      * Determine if a line of code could be fully parsed, i.e. it would
        return true for "plot (x, y);", but false for "while (true)".
      * Evaluate a line of code and return the output as a string (it
        would be best if it could provide three strings: output,
        warnings and errors).
      * Query defined variables, i.e. get a list of currently defined
        variables. Bonus points if it could tell you if anything had
        changed since the last time you checked the variables (could
        also be done with signals).

If we had a single C++ class that would allow this, then I'm sure it
would be much easier to write a proper GUI.

Søren

12