Lock-Free Programming on AMD Multi-Core Systems

[Gerd Isenberg]

Might be interesting...
http://ein.designreactor.com:8080/amd_d ... .jsp?id=89

[Zach Wegner]

Yikes. Looking at the algorithms they have makes me think of how much of a implementational nightmare it would be to do this in my program. My code is complicated enough already!

[Dann Corbit]

Might be interesting...
http://ein.designreactor.com:8080/amd_d ... .jsp?id=89

This is a more general solution that scales to a zillion processors smoothly:
http://en.wikipedia.org/wiki/Software_t ... nal_memory

[bob]

Yikes. Looking at the algorithms they have makes me think of how much of a implementational nightmare it would be to do this in my program. My code is complicated enough already!

Right. The idea is old. The details are difficult to deal with. And unless you go absolutely ape with locks, they are _not_ a big deal in a typical chess program running on a reasonable number of processors (at least 16)...

[Mangar]

Hi,

I like the idea of a "lockless exchange". It may save me some locks without much overhead. How is it implemented in a most portable way (intel, amd, windows, linux ..)?

Greetings Volker

[Gerd Isenberg]

Hi,

I like the idea of a "lockless exchange". It may save me some locks without much overhead. How is it implemented in a most portable way (intel, amd, windows, linux ..)?

Greetings Volker

Hi Volker,

I guess intel/amd is not an issue with recent processors.
Win-Api has InterlockedCompareExchange* to implement CAS
http://msdn2.microsoft.com/en-us/library/ms683560.aspx

Atomic operations package for Linux found here
http://www.hpl.hp.com/research/linux/qp ... nload.php4

Cheers,
Gerd

[Allard Siemelink]

In bright, I use this:

http://gcc.gnu.org/onlinedocs/gcc-4.2.2 ... ltins.html

or actually I wrap these in macro's such that the Interlocked* functions that Gerd mentioned are used when compiling with vc++ instead of gcc.

Hi,

I like the idea of a "lockless exchange". It may save me some locks without much overhead. How is it implemented in a most portable way (intel, amd, windows, linux ..)?

Greetings Volker

[Michael Sherwin]

Might be interesting...
http://ein.designreactor.com:8080/amd_d ... .jsp?id=89

I know next to nothing about how to make a multiprocessor chess program. However, using hash tables as an example my first thought would be to do the following when reading and writing to the hash from different threads. Include a counter byte (or bits) in the hash record and when reading or writing the first thing that I would do is increment the counter. Then read that counter back and if the value is one, it is safe to read or modify. If the counter is more than 1 I decrement the counter then loop back and try again. When done reading or writing I decrement the counter and continue on. Seems like a cheap solution since reading from and writing to the same hash record at the same time would not be all that common. But I guess that another thread could get in its own increment between the increment and read back of the first thread, but that would simply keep both threads from accessing the hash record. That condition should clear itself and one thread would gain access. Just some thoughts.

[Ratta]

Yeah, the idea of the (atomic) counter is not new, for instance linux kernel has spin locks that are actually just counters that can be locked for reading (and there can be many readers) or writing (and there can be only just one writer an no readers). Still, you require atomic primitives to operate on the counters, because one increment in such as var++ could actually mean read/increment register/write. On the other side i don't know if it is worth using them to protect hashtable entries, but i use them to protect the nodes of the virtual stack of my iterative search function, in order to achieve quick local locking (ie i don't have one big lock).
Regards!

[Michael Sherwin]

Thanks, do the atomic counters increment first and read second like I suggest? Anyway, 'nothing new under the sun'.

Just a further thought about what I suggest would be to, in the case of the hash file, not loop back to read or write. So a few reads or writes are missed amoung millions. The speed gained by not waiting around should more than offset that.