OpenMP support?

[Ian Ozsvald]

For ages I've wondered if adding openmp support into a shedskin
program was possible. I never had a need to try it until now...

I'm experimenting with an nbody calculator. ShedSkin beats PyPy (which
beats Cython and CPython) but I'd like to make it go faster
still...this is for my EuroPython tutorial.

When I run my code (without OpenMP) on my dual core Macbook I get
90-95% cpu utilisation. This surprised me, I'd expected just 50%. Does
some sort of automatic vectorisation occur in the background? I'm
iterating over lists of floats in a dictionary using straight Python
code.

Has anyone tried adding OpenMP into the generated .cpp files before?
I've got it working (the changes weren't hard) but have race
conditions on this implementation (so...back to the drawing board).

Ian.

--
Ian Ozsvald (A.I. researcher, screencaster)
i...@IanOzsvald.com

http://IanOzsvald.com
http://SocialTiesApp.com/
http://MorConsulting.com/
http://blog.AICookbook.com/
http://TheScreencastingHandbook.com
http://FivePoundApp.com/
http://twitter.com/IanOzsvald

[Ian Ozsvald]

The beginner mistake here is that the nbody problem requires
sequential updates else the numerical evolution changes, so I can't
parallelise this problem.

However, I'll share the code changes, maybe that'll help someone else
(and I'd love an answer to the 90% cpu question if possible).

Initially I had a main loop in the .cpp file that started with:
FAST_FOR(i,0,n,1,9,10)

I took the FAST_FOR definition out of builtin.hpp and replaced it,
commenting out the 'if' check which gets in the way of the omp
parallel directive:
/* defined as FAST_FOR(i, l, u, s, t1, t2)*/
/* removed the first two lines of FAST_FOR
if(s==0) \
__throw_range_step_zero(); \
*/
This left me with:
#pragma omp parallel private(th_id)
for(__9 = 0, __10 = n; ; __9 += 1) {
if (1 >= 0) {
if (__9 >= __10)
break;
}
else {
if (__9 <= __10)
break;
}
i=__9;
where __9, __10 and the other variables are hand substituted from what
would have come out of the #define (had it been evaluated).

I also added #include <omp.h> to the top of the file and added
'-fopenmp' to the CCFLAGS in the Makefile. To try more or less threads
I ran 'export OMP_NUM_THREADS=2' at the command line.

Hope that's useful to someone (and now I'm off to find a
parallelisable bit of code to play with...),
Ian.

[Thomas Spura]

On Wed, 1 Jun 2011 13:53:28 +0100
Ian Ozsvald wrote:

> For ages I've wondered if adding openmp support into a shedskin
> program was possible. I never had a need to try it until now...
>
> I'm experimenting with an nbody calculator. ShedSkin beats PyPy (which
> beats Cython and CPython) but I'd like to make it go faster
> still...this is for my EuroPython tutorial.
>
> When I run my code (without OpenMP) on my dual core Macbook I get
> 90-95% cpu utilisation. This surprised me, I'd expected just 50%. Does
> some sort of automatic vectorisation occur in the background? I'm
> iterating over lists of floats in a dictionary using straight Python
> code.
>
> Has anyone tried adding OpenMP into the generated .cpp files before?
> I've got it working (the changes weren't hard) but have race
> conditions on this implementation (so...back to the drawing board).

Hmm, I didn't try it yet, but I don't think it's that easily, how you
tried with replacing the For macro.

When I find the time, I'll also try to dig into this, so if you have a
nice testcase let the list know :)

Thanks,
Thomas

[Ian Ozsvald]

Hi Thomas. Replacing the FOR loop for threads=1 was easy (it produced
the correct output). But yes, whether it preserves the semantics of
Marc's library is another thing...maybe there are race
conditions/deadlocks etc behind the scenes.

I'll upload the nbody code to see if anyone can spot any obvious
improvements to the style of the code. I'll also share a parallel
problem once I've formulated one that'll work between
shedskin/cython/pypy etc :-)

i.

> --
> You received this message because you are subscribed to the Google Groups "shedskin-discuss" group.
> To post to this group, send email to shedskin...@googlegroups.com.
> To unsubscribe from this group, send email to shedskin-discu...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/shedskin-discuss?hl=en.

[Harri Pasanen]

Wednesday, June 01, 2011 03:26 pm

Ian Ozsvald writes:
>
> However, I'll share the code changes, maybe that'll help someone else
> (and I'd love an answer to the 90% cpu question if possible).
>

What tool do you use to check CPU usage? It may be that it gives 90% even if
only one core is busy and not waiting on I/O.

On linux top will give 100% CPU utilization for a simple loop:
for i in xrange(1e8): x = i*3.14

But htop will show you individual cores and only one is pegged, rest mostly
idle.

Harri

[Ian Ozsvald]

Hi Harri. Sadly it was Operator Error. Firefox was busily working on
nothing (I *think* calculating Life, The Universe and Everything in
the 1 Google Doc I had open...) and I was only looking at the CPU
counter. Very silly me.

I confirm with the nbody code that both CPython and ShedSkin 0.8 use
50% of the CPU when calculating. At least that solves that mystery :-)

i.

> --
> You received this message because you are subscribed to the Google Groups "shedskin-discuss" group.
> To post to this group, send email to shedskin...@googlegroups.com.
> To unsubscribe from this group, send email to shedskin-discu...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/shedskin-discuss?hl=en.
>
>

--

[Mark Dufour]

I will reply to this in more detail tonight, but in attachments I used the multiprocessing module to parallelize nbody2.py. I wanted to say for fun, but it was not fun at all! and it still seems incorrect, but I have no time to look into this further now.. note there are 2000 planets here, otherwise there's not much to gain.

shedskin -e nbody2 && make
python nbody_main.py 20 1 # 20 iterations, 1 process
python nbody_main.py 20 4 # 20 iterations, 4 processes


thanks,
mark.

http://www.youtube.com/watch?v=E6LsfnBmdnk

[Mark Dufour]

On Wed, Jun 1, 2011 at 2:53 PM, Ian Ozsvald <i...@ianozsvald.com> wrote:

For ages I've wondered if adding openmp support into a shedskin
program was possible. I never had a need to try it until now...

Has anyone tried adding OpenMP into the generated .cpp files before?
I've got it working (the changes weren't hard) but have race
conditions on this implementation (so...back to the drawing board).

I don't think hand editing generated cpp code is a very elegant way of achieving parallellism.. ;-) it also seems quite a difficult problem for compilers to try and figure out by themselves that things may be parallelised (beyond some really simple loops), at least for imperative languages. this is an interesting problem, though I'm hardly an expert, so I'm not sure I can say much sensible about it.

we could probably add a command-line switch to shedskin, to give it some guarantees that make it easier to parallelize things ('I promise not to depend on side-effects'), so we can parallelize builtins such as 'map' or perhaps even any list comprehension. or perhaps we could use an existing python parallel processing interface ('for result in parmap(..)'). in both cases, we could probably use openmp internally.

none of this makes me very excited though. the reason for this may be that I'm a big fan of process-level parallelisation. it may be a bit more work in some cases, but it's simpler in many ways and works over the network. it's also faster when using cpython, because of the GIL, and it's nice to be able to have a fast cpython version, too.

I'm aware that in some cases you really, really want threads. but if processes suffice in most cases, and given that it would be a lot of work, it's probably not worth spending much effort on this at the moment. I would probably prefer to work on escape analysis (analyze object lifetimes, so we can (de)allocated them through/on the stack, instead of the heap), because that can boost even fully parallelized processes.

btw, I'm sure shedskin is not thread safe, or at least I never consciously aimed for this. I'm sure it could be made to be (probably at the cost of some performance!), but it's probably not something I will ever focus on myself..


thanks,
mark.

--
http://www.youtube.com/watch?v=E6LsfnBmdnk

[Ian Ozsvald]

Hi Mark. I've had a hack adding openmp around the 'for' loop in my
mandelbrot solver, all it does is make things slower...

I set all the variables inside the loop as 'private', this means that
private copies are made between threads (so there's no thread safety
issues), I get a stable output each time. But - for each extra thead,
the execution time doubles in length (not what I wanted!).

I'm not going to invest any more time here (I agree re. process level
parallelism, I already have a nice mandelbrot version using
multiprocessing). I'm curious though as to why things are going so
slow - is there any dependence on the GIL when getting/setting
objects?

I made sure I set a big(ish) loop of 10,000 elements per thread (so
each thread does 10k elements, then steps ahead to the next 10k), that
makes no difference to the execution speed. It feels more like it is
block. Looking at the CPU output (top, htop) there's only 1 processes
worth of work it seems (though openmp reports 2 processes).

I figured it'd be interesting to throw this into the tutorial but I'll
abandon this line of enquiry (but a reply on 'blocking' would be
appreciated, just for knowledge).

If I can get my 32bit build working then I can show ShedSkin (and
Cython) being used via multiprocessing (and maybe parallelpython) to
exploit what's available.

i.

> --
> You received this message because you are subscribed to the Google Groups
> "shedskin-discuss" group.
> To post to this group, send email to shedskin...@googlegroups.com.
> To unsubscribe from this group, send email to
> shedskin-discu...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/shedskin-discuss?hl=en.
>

--