(A)

For all of you out there waiting for radiosity to get fixed, a short status
report:

Let me put it this way - let's be happy that radiosity does *something* in the
beta at all :) There's a hell lot of work to do, as the code has been
"amputated" in many places, obviously to get the other code to compile at all.
So it's basically a re-integration job.

(B)

I think I have an idea how to use SMP to speed up radiosity pretrace as well,
without too much modification to the existing architecture.

Obviously, the problem with thread synchronization during radiosity pretrace is
that the sample octree needs to be accessed from multiple threads. The worst
case scenario is that multiple threads might find it necessary to build a new
root at the same time.

However, tasks traversing the tree in search for samples, while another is
actually updating the tree, should not be a problem, if tree modification is
performed carefully.

Competing writes to the same sample tree node can be avoided, if instead of
using a single linked list of sample blocks each node contains as many such
lists as there are threads. The overhead for retrieving blocks should be
insignificant.

Competing writes to the tree hierarchy can be avoided - without all-too-frequent
messing with locks - as follows:

- Each thread keeps a small private list of samples it wasn't able to hook in
yet, because the corresponding nodes didn't exist yet and fast tree
modifications would have been too unsafe.

- Whenever a thread's private sample list reaches a certain size, it attempts to
lock the sample tree; however, if it doesn't get the lock immediately it just
continues to do its job, and retries when its private list of samples has
increased by another certaing amount.

- If the thread does acquire a lock on the tree, it hooks in the samples it has
accumulated by now, then releases the lock and resumes tracing.

This way the threads will not block if they need to do a modification.


A few more considerations regarding this idea:

- Deadlocks are not possible, because if threads can't acquire the lock they
will just do something else.

- Livelocks are unlikely, because the time until a certain number of samples in
non-existing nodes has been taken will have significant jitter.

- Starvation of a single thread is unlikely for similar reasons; plus, it can be
further reduced by having a task try for a lock more frequently the longer its
list of un-hooked samples gets.

- The list of un-hooked samples could include a reference to the node below
which a new sub-tree is needed, to speed up the actual tree modification.

- If a thread cannot acquire a lock, it can still check its list of un-hooked
samples to see if another thread has already built the required nodes by now.

- Separate locks could be used for "root growth" and "leaf growth", as building
a new root will not interfere with the rest of the tree.

Post a reply to this message