tanbinh123 / combining-tree

A Combining Tree is an N-ary tree of nodes, that follows software combining to reduce memory contention while updating a shared value.

A Combining Tree is an N-ary tree of nodes, that follows software combining to reduce memory contention while updating a shared value.

The shared value is placed at the root of the tree, and threads perfrom getAndOp() at the leaf nodes. Each leaf node handles N threads. The combined value is then propagated up the tree by an active thread. There can be several active threads, but eventually one active thread updates the root node. It then shares this message to all other threads behind it.

This was contention at a single memory location is avoided. However, i guess that such a design is normally useful only in hardware, as it becomes too slow in software. Useful for educational purposes.

Course: Concurrent Data Structures, Monsoon 2020
Taught by: Prof. Govindarajulu Regeti

CombiningTree.getAndOp(x, op):
Gets current value, and then updates it.
x: value to OP with, op: binary op
1. Select leaf index using thread id.
2. Perform get & op at desired leaf.

CombiningTree.getAndOp(x, op, i):
Gets current value, and then updates it.
x: value to OP with, op: binary op, i: leaf index
1. Perform get & op at desired leaf (ensure in limit).

Node.getAndOp(x, op)
Gets current value, and then updates it.
x: value to OP (accumulate), op: binary operator
1. Wait until node is free.
2. Perform get & op based on 3 possible cases.
2a. Root node
2b. Active thread (first to visit node)
2c. Passive thread (visits later)

Node.getAndOpRoot(x, op)
Performs get & op for root node.
x: value to OP (accumulate), op: binary operator
1. Get old value, by combining (a).
2. Empty the node.
3. Insert a OP x
3. Return old value.

Node.getAndOpActive(x, op)
Performs get & op for active thread.
x: value to OP (accumulate), op: binary operator
1. Insert value.
2. Wait until node is full, or timeout.
3. We have the values, so start pushing.
4. Combine values into one with OP.
5. Push combined value to parent.
6. Distribute recieved value for all threads.
7. Start the pulling process.
8. Decrement count (we have our pulled value).
9. Return pulled value.

Node.getAndOpPassive(x, op)
Performs get & op for passive thread.
x: value to OP (accumulate), op: binary operator
1. Insert value.
2. Wait until active thread has pulled value.
3. Decrement count, one pulled value processed.
4. If count is 0, the node is free.
5. Return value of this thread.

## OUTPUT
3-ary 3-depth Combining tree.
Starting 25 threads doing increments ...
30: done in 51ms
14: done in 60ms
13: done in 68ms
23: done in 53ms
12: done in 56ms
21: done in 54ms
32: done in 56ms
31: done in 56ms
22: done in 54ms
28: done in 7831ms
11: done in 7836ms
10: done in 7838ms
19: done in 7833ms
20: done in 7833ms
29: done in 7831ms
24: done in 8165ms
33: done in 8160ms
25: done in 8165ms
16: done in 8167ms
34: done in 8159ms
15: done in 8167ms
26: done in 11970ms
17: done in 11972ms
27: done in 12239ms
18: done in 12241ms
Total: 2500

Was valid? true

See CombiningTree.java, Node.java for code, Main.java for test, and repl.it for output.

references

• The Art of Multiprocessor Programming :: Maurice Herlihy, Nir Shavit