LIFO stack based parallel processing?

[smatovic]

Have some thoughts about a LIFO stack based parallel processing scheme,
so one thread gets one position from the stack and puts the generated childs back on the stack,

The point is that i dont have a clue how to handle the scores for such an process.

Does somebody have an idea or an hint?

--
Srdja

[bob]

Have some thoughts about a LIFO stack based parallel processing scheme,
so one thread gets one position from the stack and puts the generated childs back on the stack,

The point is that i dont have a clue how to handle the scores for such an process.

Does somebody have an idea or an hint?

--
Srdja

First thought is that it is a gigantic race condition that is going to end up spending a lot of time waiting for access to that "stack". I think the more traditional approach offers better performance and less scaling issues.

[smatovic]

First thought is that it is a gigantic race condition that is going to end up spending a lot of time waiting for access to that "stack".

You are right,

i thought the builtin atomic memory operations of OpenCL could handle this,
but a simple testprogramm shows the race conditions.

--
Srdja

[joca]

use an elimination-backoff stack (a stack with an elimination array and exponential backoff). if well implemented has low contention and is highly parallelizable

a version is described in the book "The Art of Multiprocessor Programming" (http://www.elsevier.com/wps/find/bookde ... escription). you can probably find some slides about it in some parallel programming course available on the web

[sje]

Have some thoughts about a LIFO stack based parallel processing scheme,
so one thread gets one position from the stack and puts the generated childs back on the stack,

The point is that i dont have a clue how to handle the scores for such an process.

First thought is that it is a gigantic race condition that is going to end up spending a lot of time waiting for access to that "stack". I think the more traditional approach offers better performance and less scaling issues.

I've been thinking about a similar scheme. I think it's possible to avoid race, and the stack can be guarded by a spinlock. To reduce overall waiting, only stack entries with draft greater than N (N is say, 4 or so) are allowed.

[bob]

Have some thoughts about a LIFO stack based parallel processing scheme,
so one thread gets one position from the stack and puts the generated childs back on the stack,

The point is that i dont have a clue how to handle the scores for such an process.

First thought is that it is a gigantic race condition that is going to end up spending a lot of time waiting for access to that "stack". I think the more traditional approach offers better performance and less scaling issues.

I've been thinking about a similar scheme. I think it's possible to avoid race, and the stack can be guarded by a spinlock. To reduce overall waiting, only stack entries with draft greater than N (N is say, 4 or so) are allowed.

Spinlocks ALWAYS solve races, but do you want a common data structure that has to be locked and unlocked frequently? Not to mention it doesn't really sound like a viable way to make it work cleanly...

[Zach Wegner]

You could easily make a lockless queue and not have any spinlocks.

The problem is that with alpha-beta you need to delete elements from the middle of the queue. So I don't think it could be done in any efficient way...

[sje]

My experiments with using spinlocks on transposition table regions (1/256 segments) shows access degradation times of less than one percent.

A LIFO stack implemented as a two way linked list requires changing only a few pointers during a lock period. Queue elements can be dynamically allocated with unused ones getting attached to a free list for re-use.

[smatovic]

A LIFO stack implemented as a two way linked list requires changing only a few pointers during a lock period. Queue elements can be dynamically allocated with unused ones getting attached to a free list for re-use.

That sounds good, i will give it a try.

--
Srdja

[smatovic]

That sounds good, i will give it a try.

...try and fail.

It is nearly impossible to implement a parallel LIFO stack on a GPU considering that threads inside a SIMD Unit are again divided into Warps/Wavefronts.

--
Srdja