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
LIFO stack based parallel processing?
Moderators: hgm, Rebel, chrisw
-
- Posts: 2658
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: LIFO stack based parallel processing?
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 wrote: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
-
- Posts: 2658
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
Re: LIFO stack based parallel processing?
You are right,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 thought the builtin atomic memory operations of OpenCL could handle this,
but a simple testprogramm shows the race conditions.
--
Srdja
Re: LIFO stack based parallel processing?
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
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
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: LIFO stack based parallel processing?
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 wrote: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 wrote: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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: LIFO stack based parallel processing?
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...sje wrote: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 wrote: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 wrote: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.
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: LIFO stack based parallel processing?
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...
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...
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: LIFO stack based parallel processing?
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.
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.
-
- Posts: 2658
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
Re: LIFO stack based parallel processing?
That sounds good, i will give it a try.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.
--
Srdja
-
- Posts: 2658
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
Re: LIFO stack based parallel processing?
...try and fail.That sounds good, i will give it a try.
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