cds::algo::elimination Namespace Reference

Elimination technique. More...

Data Structures
struct	operation_desc
	Base class describing an operation for eliminating. More...
struct	record
	Per-thread elimination record. More...

Functions
template<typename OperationDesc >
static record *	init_record (OperationDesc &op)
	Acquires elimination record for the current thread.
static void	clear_record ()
	Releases elimination record for the current thread.

Detailed Description

Elimination technique.

Elimination technique allows highly distributed coupling and execution of operations with reverse semantics like the pushes and pops on a stack. If a push followed by a pop are performed on a stack, the data structure's state does not change (similarly for a pop followed by a push). This means that if one can cause pairs of pushes and pops to meet and pair up in separate locations, the threads can exchange values without having to touch a centralized structure since they have anyhow "eliminated" each other's effect on it. Elimination can be implemented by using a collision array in which threads pick random locations in order to try and collide. Pairs of threads that "collide" in some location run through a synchronization protocol, and all such disjoint collisions can be performed in parallel. If a thread has not met another in the selected location or if it met a thread with an operation that cannot be eliminated (such as two push operations), an alternative scheme must be used.