POV-Ray : Newsgroups : povray.general : Algorithm question Server Time
31 Oct 2024 19:28:43 EDT (-0400)
  Algorithm question (Message 1 to 7 of 7)  
From: Anthony D  Baye
Subject: Algorithm question
Date: 9 Sep 2015 23:40:00
Message: <web.55f0faf83c3634f32aaea5cb0@news.povray.org>
does anybody know --approximately-- how much of the ray tracing process is
strictly serial (as a percentage)?

Regards,
A.D.B.


Post a reply to this message

From: clipka
Subject: Re: Algorithm question
Date: 10 Sep 2015 09:29:06
Message: <55f185a2$1@news.povray.org>
Am 10.09.2015 um 05:37 schrieb Anthony D. Baye:
> does anybody know --approximately-- how much of the ray tracing process is
> strictly serial (as a percentage)?

What do you mean by "serial" in this context?


Post a reply to this message

From: Anthony D  Baye
Subject: Re: Algorithm question
Date: 10 Sep 2015 12:40:01
Message: <web.55f1b144db4c28502aaea5cb0@news.povray.org>
clipka <ano### [at] anonymousorg> wrote:
> Am 10.09.2015 um 05:37 schrieb Anthony D. Baye:
> > does anybody know --approximately-- how much of the ray tracing process is
> > strictly serial (as a percentage)?
>
> What do you mean by "serial" in this context?

as in: Not parallel.

What percentage of the operation is carried out in a strictly sequential way,
with no parallel processing of any kind.

I want to calculate the theoretical speed increase per core/thread according to
Amdahl's Law, but I need to know what percentage of the operation is performed
serially.

S(N) = 1 / [ Ps + (1/n)Pp] => 1 / [Ps + (1/n)(1 - Ps)]

where N is the number of cores and Ps is the percentage of the operation that is
strictly serial.

Regards,
A.D.B.


Post a reply to this message

From: clipka
Subject: Re: Algorithm question
Date: 10 Sep 2015 14:56:59
Message: <55f1d27b$1@news.povray.org>
Am 10.09.2015 um 18:35 schrieb Anthony D. Baye:
> clipka <ano### [at] anonymousorg> wrote:
>> Am 10.09.2015 um 05:37 schrieb Anthony D. Baye:
>>> does anybody know --approximately-- how much of the ray tracing process is
>>> strictly serial (as a percentage)?
>>
>> What do you mean by "serial" in this context?
> 
> as in: Not parallel.
> 
> What percentage of the operation is carried out in a strictly sequential way,
> with no parallel processing of any kind.
> 
> I want to calculate the theoretical speed increase per core/thread according to
> Amdahl's Law, but I need to know what percentage of the operation is performed
> serially.
> 
> S(N) = 1 / [ Ps + (1/n)Pp] => 1 / [Ps + (1/n)(1 - Ps)]
> 
> where N is the number of cores and Ps is the percentage of the operation that is
> strictly serial.

In a nutshell, the only things in POV-Ray that are /entirely/ sequential
are (1) parsing and (2) assembling the computed pixels into an output image.

On the other end of the spectrum, rendering itself is (in general)
effectively /entirely/ parallel, as long as you choose a render chunk
size small enough and a resolution large enough so that all cores can be
kept busy.

In between, we have photon shooting, which is done sequentially for any
individual light source, while using parallel processing between
multiple light sources.

And finally, there's radiosity, which would need detailed analysis to
fit into the picture: It utilizes parallel processing, but has some
comparatively heavy multithreading overhead, not only to sync access to
the shared sample cache, but also because threads may do double work.


Post a reply to this message

From: Anthony D  Baye
Subject: Re: Algorithm question
Date: 10 Sep 2015 20:55:00
Message: <web.55f22623db4c28502aaea5cb0@news.povray.org>
clipka <ano### [at] anonymousorg> wrote:
> Am 10.09.2015 um 18:35 schrieb Anthony D. Baye:
> > clipka <ano### [at] anonymousorg> wrote:
> >> Am 10.09.2015 um 05:37 schrieb Anthony D. Baye:
> >>> does anybody know --approximately-- how much of the ray tracing process is
> >>> strictly serial (as a percentage)?
> >>
> >> What do you mean by "serial" in this context?
> >
> > as in: Not parallel.
> >
> > What percentage of the operation is carried out in a strictly sequential way,
> > with no parallel processing of any kind.
> >
> > I want to calculate the theoretical speed increase per core/thread according to
> > Amdahl's Law, but I need to know what percentage of the operation is performed
> > serially.
> >
> > S(N) = 1 / [ Ps + (1/n)Pp] => 1 / [Ps + (1/n)(1 - Ps)]
> >
> > where N is the number of cores and Ps is the percentage of the operation that is
> > strictly serial.
>
> In a nutshell, the only things in POV-Ray that are /entirely/ sequential
> are (1) parsing and (2) assembling the computed pixels into an output image.
>
> On the other end of the spectrum, rendering itself is (in general)
> effectively /entirely/ parallel, as long as you choose a render chunk
> size small enough and a resolution large enough so that all cores can be
> kept busy.
>
> In between, we have photon shooting, which is done sequentially for any
> individual light source, while using parallel processing between
> multiple light sources.
>
> And finally, there's radiosity, which would need detailed analysis to
> fit into the picture: It utilizes parallel processing, but has some
> comparatively heavy multithreading overhead, not only to sync access to
> the shared sample cache, but also because threads may do double work.

But the processes running within a single thread are likely to be serial, right?
 I'm operating at the edges of my knowledge here.

I imagine it would take detailed analysis to determine how much of the work done
in individual threads is only able to be done sequentially, and what part of the
whole that work represents.  Certainly not a trivial task, I was just wondering
if anybody had thought about it.

Regards,
A.D.B.


Post a reply to this message

From: scott
Subject: Re: Algorithm question
Date: 11 Sep 2015 03:25:27
Message: <55f281e7$1@news.povray.org>
> But the processes running within a single thread are likely to be serial, right?
>   I'm operating at the edges of my knowledge here.

Threads run within processes, not the other way round. There is a single 
POV process that spawns off multiple threads. Each thread runs its own 
code in serial. The process can then use up 100% of your multi-core CPU 
because it has enough threads to fill up all the cores.

> I imagine it would take detailed analysis to determine how much of the work done
> in individual threads is only able to be done sequentially, and what part of the
> whole that work represents.  Certainly not a trivial task, I was just wondering
> if anybody had thought about it.

In POV it will heavily depend on the scene. But if you ignore parsing 
(and the other things clipka mentioned) then it's pretty much 100% parallel.


Post a reply to this message

From: clipka
Subject: Re: Algorithm question
Date: 11 Sep 2015 07:17:25
Message: <55f2b845$1@news.povray.org>
Am 11.09.2015 um 02:53 schrieb Anthony D. Baye:

> But the processes running within a single thread are likely to be serial, right?
>  I'm operating at the edges of my knowledge here.
> 
> I imagine it would take detailed analysis to determine how much of the work done
> in individual threads is only able to be done sequentially, and what part of the
> whole that work represents.  Certainly not a trivial task, I was just wondering
> if anybody had thought about it.

Oh God -- if /that's/ what your question is about (put in different
words, that's the question of how much of the code could be rearranged
and executed out-of-sequence by a heavily optimizing compiler and/or CPU
execution pipeline), then I suspect you're out of luck.

Shadow and simple shading computations could almost always be
deserialized, as it doesn't really matter in which order the shadows for
the individual light sources are computed.

Also, obviously there are plenty of vector operations and quite some
colour operations in POV-Ray; in most of those, the order of execution
among the three dimensions or colour channels doesn't matter (a fact
that the Windows SSE2 and 64-bit binaries should already make use of, by
employing SIMD instructions).

There is also certainly a lot of other code that is
"micro-deserializable", by which I mean that some nearby instructions
could be swapped or executed in parallel without affecting the result.

But when it comes to actual numbers, the only thing that can be said
with certainty is that they'll vary -- probably quite a lot -- between
scenes.


Post a reply to this message

Copyright 2003-2023 Persistence of Vision Raytracer Pty. Ltd.