> Fix all of the global variables and other weirdness (like variable reuse)
> and then it would be a fairly easy task.

Agreed.

But usually you can find some low level which sacrifices generality and
elegance (but avoids the globals problem) in critical routines that can be
threaded to yield 90 percent of the performance improvement without doing a
full-up SMP design.  Kind of a thread-lite approach.  I have had some
surprising results with a little effort on routines that I thought were
impossible to multi-thread, like fuzzy c-means clustering (FCM).  That
involved splitting the image work into two threads, synchronizing completion
and then doing a final pass to merge the results.  But it essentially
doubled the performance with two processors.

I have the source installed, what's a good candidate routine?

regards,

Tim Hutcheson
w4l### [at] bellsouthnet


Ron Parker <par### [at] fwicom> wrote in message
news:374b0039.0@news.povray.org...
> On Tue, 25 May 1999 14:48:58 -0500, Tim Hutcheson wrote:
> >Certain types of image processing routines are almost trivial to break
into
> >SMP threads under NT, especially if you can get all the performance from
> >just partitioning the image.  It can be done using only a thread control
> >structure, ResumeThread, SuspendThread, and Sleep functions and wrappers
> >around the needed image processing routines.  Alternating scanlines is
> >better because it minimizes paging at the various cache levels.
> >
> >This doesn't give a very general solution but works great under NT and
the
> >code can run fine in Win98.  It only gets messy when the multiple threads
> >have to access the same data, that is, if the changes made by one thread
> >depend on the changes made by the other thread.  Then the synchronization
to
> >avoid exceptions destroys the performance or exception handling itself
> >becomes too complicated to manage.  If the core routines can be
individually
> >treated, that's where all the performance gain is anyway.
>
> Raytracing in general is very parallelizable.  It's just POV in specific
> that's a tough nut to crack, because the design did not anticipate
threading.
> Fix all of the global variables and other weirdness (like variable reuse)
> and then it would be a fairly easy task.

Post a reply to this message

On Tue, 25 May 1999 16:24:14 -0500, Tim Hutcheson wrote:
>> Fix all of the global variables and other weirdness (like variable reuse)
>> and then it would be a fairly easy task.
>
>Agreed.
>
>But usually you can find some low level which sacrifices generality and
>elegance (but avoids the globals problem) in critical routines that can be
>threaded to yield 90 percent of the performance improvement without doing a
>full-up SMP design.  Kind of a thread-lite approach.  I have had some
>surprising results with a little effort on routines that I thought were
>impossible to multi-thread, like fuzzy c-means clustering (FCM).  That
>involved splitting the image work into two threads, synchronizing completion
>and then doing a final pass to merge the results.  But it essentially
>doubled the performance with two processors.
>
>I have the source installed, what's a good candidate routine?

That's the problem, there is no good candidate routine.  The best way to 
parallelize POV is by tracing different rays in different threads, but 
it's the code that traces a ray that isn't threadsafe, and the problems
are spread throughout the code.  Somewhere in excess of 90% of the code
is called from within the "trace a ray" function at one time or another.

As an example of some things that aren't thread safe:

o The crackle pattern generates an array of nearby centers to determine 
  where it is within the voronoi diagram.  This array is a global 
  variable and is cached from use to use.  If two threads are rendering
  a crackle pattern at the same time, one could refill this array while
  the other is trying to calculate with it.  If you serialize access to
  it, you may end up serializing some scenes entirely.  If you eliminate
  the caching, you will slow down the trace considerably.

o The area light code saves off the center of the light source into a
  local variable, "fiddles" with it during the calculations, then 
  restores it when it's done.  Hopefully it's obvious why this isn't
  threadsafe.

o The crackle pattern saves the current RNG seed before filling its array, 
  then restores it afterward.  While filling its array, it depends on the 
  sequence of "random" numbers being reproducible.  The black hole warp 
  is similarly dependent.  If one thread came in and grabbed a random
  number while another thread was inside this code, the image would be
  ruined in a very obvious manner.  

o Some code apparently depends on the RNG being repeatable, as one of the
  changes in a recent update was the saving and restoring of the RNG seed
  mentioned in the previous point.  If two or more threads are using the
  same RNG, it will not be repeatable.

o The radiosity code saves some global settings, modifies them, and then 
  restores them later.

o Determine_Apparent_Colour - a very important, central function - saves
  the texture, weight, and light lists before doing whatever it does, then
  restores them afterward.

Post a reply to this message

Interesting...and I see the problem now.  tnx

--
Tim Hutcheson
w4l### [at] bellsouthnet


Ron Parker <par### [at] fwicom> wrote in message
news:374b1d23.0@news.povray.org...
> On Tue, 25 May 1999 16:24:14 -0500, Tim Hutcheson wrote:
> >> Fix all of the global variables and other weirdness (like variable
reuse)
> >> and then it would be a fairly easy task.
> >
> >Agreed.
> >
> >But usually you can find some low level which sacrifices generality and
> >elegance (but avoids the globals problem) in critical routines that can
be
> >threaded to yield 90 percent of the performance improvement without doing
a
> >full-up SMP design.  Kind of a thread-lite approach.  I have had some
> >surprising results with a little effort on routines that I thought were
> >impossible to multi-thread, like fuzzy c-means clustering (FCM).  That
> >involved splitting the image work into two threads, synchronizing
completion
> >and then doing a final pass to merge the results.  But it essentially
> >doubled the performance with two processors.
> >
> >I have the source installed, what's a good candidate routine?
>
> That's the problem, there is no good candidate routine.  The best way to
> parallelize POV is by tracing different rays in different threads, but
> it's the code that traces a ray that isn't threadsafe, and the problems
> are spread throughout the code.  Somewhere in excess of 90% of the code
> is called from within the "trace a ray" function at one time or another.
>
> As an example of some things that aren't thread safe:
>
> o The crackle pattern generates an array of nearby centers to determine
>   where it is within the voronoi diagram.  This array is a global
>   variable and is cached from use to use.  If two threads are rendering
>   a crackle pattern at the same time, one could refill this array while
>   the other is trying to calculate with it.  If you serialize access to
>   it, you may end up serializing some scenes entirely.  If you eliminate
>   the caching, you will slow down the trace considerably.
>
> o The area light code saves off the center of the light source into a
>   local variable, "fiddles" with it during the calculations, then
>   restores it when it's done.  Hopefully it's obvious why this isn't
>   threadsafe.
>
> o The crackle pattern saves the current RNG seed before filling its array,
>   then restores it afterward.  While filling its array, it depends on the
>   sequence of "random" numbers being reproducible.  The black hole warp
>   is similarly dependent.  If one thread came in and grabbed a random
>   number while another thread was inside this code, the image would be
>   ruined in a very obvious manner.
>
> o Some code apparently depends on the RNG being repeatable, as one of the
>   changes in a recent update was the saving and restoring of the RNG seed
>   mentioned in the previous point.  If two or more threads are using the
>   same RNG, it will not be repeatable.
>
> o The radiosity code saves some global settings, modifies them, and then
>   restores them later.
>
> o Determine_Apparent_Colour - a very important, central function - saves
>   the texture, weight, and light lists before doing whatever it does, then
>   restores them afterward.

Post a reply to this message

With next generation of processors and 4-way chip sets coming down the pike,
quad motherboards may begin to show up just like the duals we have around
now and the argument for SMP Povray is going to become very interesting and
compelling...Maybe a major rewrite to do it though, if it can be done.  tnx
agn

--
Tim Hutcheson
w4l### [at] bellsouthnet


Jan Danielsson <Jan### [at] falunmailteliacom> wrote in message
news:wnaqnavryffbasnyhaznvygryvnpbz.fcawr70.pminews@news.povray.org...
> How should a multithreaded povray work?
>
> I guess the user specifies how many threads he/she wants, then what?
>
> Should the threads render lines, or should it devide to picture in to
> 'imageheight devided by threads' blocks and render them?
>
>
>  /j
>
>
>

Post a reply to this message

The majority of these 'cached' variables could be put in the thread's scope
instead of the global scope.  But I had to go and introduce even more global
variables in my photon mapping stuff (so that I could pass values around
without adding more parameters to the existing functions).  Of course, you'd
have to find all of these, but that's not impossible.  In fact, I'm going to
label the ones I make in future releases of the photon patch with the
comment:
  /* not thread safe */
so if you search for that, you'll find them.

-Nathan


Ron Parker wrote:
> 
> On Tue, 25 May 1999 16:24:14 -0500, Tim Hutcheson wrote:
> >> Fix all of the global variables and other weirdness (like variable reuse)
> >> and then it would be a fairly easy task.
> >
> >Agreed.
> >
> >But usually you can find some low level which sacrifices generality and
> >elegance (but avoids the globals problem) in critical routines that can be
> >threaded to yield 90 percent of the performance improvement without doing a
> >full-up SMP design.  Kind of a thread-lite approach.  I have had some
> >surprising results with a little effort on routines that I thought were
> >impossible to multi-thread, like fuzzy c-means clustering (FCM).  That
> >involved splitting the image work into two threads, synchronizing completion
> >and then doing a final pass to merge the results.  But it essentially
> >doubled the performance with two processors.
> >
> >I have the source installed, what's a good candidate routine?
> 
> That's the problem, there is no good candidate routine.  The best way to
> parallelize POV is by tracing different rays in different threads, but
> it's the code that traces a ray that isn't threadsafe, and the problems
> are spread throughout the code.  Somewhere in excess of 90% of the code
> is called from within the "trace a ray" function at one time or another.
> 
> As an example of some things that aren't thread safe:
> 
> o The crackle pattern generates an array of nearby centers to determine
>   where it is within the voronoi diagram.  This array is a global
>   variable and is cached from use to use.  If two threads are rendering
>   a crackle pattern at the same time, one could refill this array while
>   the other is trying to calculate with it.  If you serialize access to
>   it, you may end up serializing some scenes entirely.  If you eliminate
>   the caching, you will slow down the trace considerably.
> 
> o The area light code saves off the center of the light source into a
>   local variable, "fiddles" with it during the calculations, then
>   restores it when it's done.  Hopefully it's obvious why this isn't
>   threadsafe.
> 
> o The crackle pattern saves the current RNG seed before filling its array,
>   then restores it afterward.  While filling its array, it depends on the
>   sequence of "random" numbers being reproducible.  The black hole warp
>   is similarly dependent.  If one thread came in and grabbed a random
>   number while another thread was inside this code, the image would be
>   ruined in a very obvious manner.
> 
> o Some code apparently depends on the RNG being repeatable, as one of the
>   changes in a recent update was the saving and restoring of the RNG seed
>   mentioned in the previous point.  If two or more threads are using the
>   same RNG, it will not be repeatable.
> 
> o The radiosity code saves some global settings, modifies them, and then
>   restores them later.
> 
> o Determine_Apparent_Colour - a very important, central function - saves
>   the texture, weight, and light lists before doing whatever it does, then
>   restores them afterward.

Post a reply to this message

Its been an interesting discussion about the problems with multithreading
the current version of POV.  However, I agree with the point Tim made about
future machines going more and more to SMP (or similar) systems.

In the planning for POV v4, is there any attempt to rewrite the code so that
multithreading could be more easily implemented?  I've caught hints in this
newsgroup that v4 will be recast in C++ so, if that much of a rewrite is
going to occur, wouldn't it make sense to make sure it was multithreadable
too?

--
Jim

Check out my web site http://www.kressworks.com/
It'll blow your mind (politically), stimulate your senses (artistically)
and provide scientific insights that boggle the mind!!


Jan Danielsson wrote in message ...
>How should a multithreaded povray work?
>
>I guess the user specifies how many threads he/she wants, then what?
>
>Should the threads render lines, or should it devide to picture in to
>'imageheight devided by threads' blocks and render them?
>
>
> /j
>
>
>

Post a reply to this message

Spider wrote:

> Ron Parker wrote:
> >
> > And of course it wouldn't
> > run on Win9x, which still seems pretty popular for some reason.
>
> hehe, in my case, I'm running win 95 from the reason of... Size. the installed
> size of 95 compared to either NT workstation(not an alternative due to driver
> problems) and 98 is big. I hope win2k will address this a bit...
>
> don't bother responding to this, since the discussion would probably end up in
> the OS wars. and I'm too OT as it is.

Win2K?? He he he he. Poor guy (not trying to continue an OS war, just bring up a
few facts).

Win2k is just Windows NT 5. They had been hoping to be able to drop the 95 OS and
force everyone up to NT, but it aint going to happen this round. Win9x is alive
for a while. Of course, since Win2K is just NT 5 renamed, you can then take from
that the info that it will require even more resources than NT 4, and thus you
will not be wanting to run that either.

(Not trying to OS bash, but getting frustrated having to program on Windows. Oy,
my head)

Now, as far as size... You might just want to get good ol' Linux on your box (if
by size of the OS you mean performance overhead in general). A couple of months
ago I switched my home system from Win95 to dual boot to Linux and ended up
staying in Linux most the time, especially for POVRay. This was on a 133 w/ 48 MB
RAM.

Oh, and like you I had stayed away from NT (despite having a few legal copies for
home) due to the weakness of my system. Once I put on Linux & Enlightenment it
seemed so much more responsive than with 95 (OSR/2).

(Oh, one other major reason for 9x staying around is becuase of WinNT's
archetecture just not allowing decent performance for games on lower end systems.
But then again, you all already knew that)

I almost forgot. To get things back on topic: Linux, of course, does SMP. And
clustering. (smiling as I dangle these extra carrots). A "Cray-matching Linux
cluster" anyone??? http://slashdot.org/articles/99/03/10/109215.shtml (drool,
drool)

Post a reply to this message

On Tue, 25 May 1999 23:29:39 -0700, "Jon A. Cruz"
<jon### [at] geocitiescom> wrote:

>Of course, since Win2K is just NT 5 renamed, you can then take from
>that the info that it will require even more resources than NT 4, and thus you
>will not be wanting to run that either.

I am running it.  PII/333, 128M RAM.  Barely acceptable performance.
When I had 64M RAM in that machine, it was ridiculously slow and
swapped all the time.

There's a reason the people who pay to be in the "beta program" get a
coupon good for a discount on more memory.

Post a reply to this message

Jim Kress wrote:
> 
> Its been an interesting discussion about the problems with multithreading
> the current version of POV.  However, I agree with the point Tim made about
> future machines going more and more to SMP (or similar) systems.
> 
> In the planning for POV v4, is there any attempt to rewrite the code so that
> multithreading could be more easily implemented?  I've caught hints in this
> newsgroup that v4 will be recast in C++ so, if that much of a rewrite is
> going to occur, wouldn't it make sense to make sure it was multithreadable
> too?
> 
<...>

Hi,
I heard a rumored yes on efforts/thoughts of the POV Team to include SMP
into the rewrite. But don't cite me on that one.
I would bet quite a lot, that such an effort like parallizing POVRay
will be much more simple with 4.0. And that the efforts done on the 3.x
branch would be most presumably lost.

As this point comes up every second week (or was it twice a week),
someone powerfull should explain the special kind of 'maybe' to warp, so
it can be included in the vfaq.

I wonder how much of 4.0 is fixed already. The overall plan posted here
some months ago is propably a bit more precise by now.

Axel

Post a reply to this message

"Ronald L. Parker" wrote:

> On Tue, 25 May 1999 23:29:39 -0700, "Jon A. Cruz"
> <jon### [at] geocitiescom> wrote:
>
> >Of course, since Win2K is just NT 5 renamed, you can then take from
> >that the info that it will require even more resources than NT 4, and thus you
> >will not be wanting to run that either.
>
> I am running it.  PII/333, 128M RAM.  Barely acceptable performance.
> When I had 64M RAM in that machine, it was ridiculously slow and
> swapped all the time.
>
> There's a reason the people who pay to be in the "beta program" get a
> coupon good for a discount on more memory.

Argh!
One year ago I had checked it out on a system with only 32MB (pretty decent at the
time). Just opening Word (not any docs, just Word) caused it to begin almost
constant disk-thrashing. I had hoped they had corrected that. Guess not. Good to
know what practical requirements are (remember Win95 saying '8MB'??? Yeah, right)

With Linux now officially supported, it's looking more and more like a great
choice for POVRay users. And, it does SMP (just to keep things a tiny bit on
topic).

Post a reply to this message