CS4021 HARDWARE TRANSACTIONAL MEMORY
Tutorial 3
•
implement and compare the performance of
1) a binary tree protected by a lock
1) a lockless binary tree using HLE
2) a lockless binary tree using RTM
•
test framework should

add and remove random keys using 1 to 2*NCPU threads

test key ranges 16 [0..15], 256, 4096, 65536, 1048576
© 2014 [email protected] 28-Nov-14
School of Computer Science and Statistics, Trinity College Dublin
1
CS4021 HARDWARE TRANSACTIONAL MEMORY
Binary Search Tree Revision
5
• add(key)
 always adds to a leaf node
 add(22)
 add(40)
20
10
• nodes can be added concurrently if they do not
conflict with each other
30
25
40
22
© 2014 [email protected] 28-Nov-14
School of Computer Science and Statistics, Trinity College Dublin
2
CS4021 HARDWARE TRANSACTIONAL MEMORY
Binary Search Tree Revision…
• remove(key)




depends on number of children
NO children
ONE child
TWO children
5
20
10
• NO children
 remove(45)
 simply remove node
30
25
40
22
50
• ONE child
45
 remove(25)
 parent points to child
© 2014 [email protected] 28-Nov-14
School of Computer Science and Statistics, Trinity College Dublin
3
CS4021 HARDWARE TRANSACTIONAL MEMORY
Binary Search Tree Revision…
5
• remove(key)
20
22
• TWO children

remove (20)




find node 20
find smallest key in its right sub tree [22]
overwrite key 20 with 22
remove old node 22 [will have ONE or zero
children]
10
30
25
22
50
24
© 2014 [email protected] 28-Nov-14
School of Computer Science and Statistics, Trinity College Dublin
40
45
4
CS4021 HARDWARE TRANSACTIONAL MEMORY
Node
class Node {
public:
INT64 key;
Node *left;
Node *right;
Node() {key = 0; right = left = NULL;}
// default constructor
};
NB: will need to specify add volatile specifiers for multi-threaded version
© 2014 [email protected] 28-Nov-14
School of Computer Science and Statistics, Trinity College Dublin
5
CS4021 HARDWARE TRANSACTIONAL MEMORY
BST
class BST {
public:
Node *root;
// initially NULL
BST();
int contains(INT64);
int add(Node*);
int remove(INT64);
//
//
//
//
constructor
return 1 if key in tree
add node to tree
remove key from tree
};
© 2014 [email protected] 28-Nov-14
School of Computer Science and Statistics, Trinity College Dublin
6
CS4021 HARDWARE TRANSACTIONAL MEMORY
BST…
• recursive or iterative code?
• which will minimise the read and write sets of a transaction?
• recursion could lead to more stack frames [larger read and write sets], but a compiler
could easily use tail recursion optimisation to convert recursive into iterative code
• play safe, use iterative code
© 2014 [email protected] 28-Nov-14
School of Computer Science and Statistics, Trinity College Dublin
7
CS4021 HARDWARE TRANSACTIONAL MEMORY
BST::add ()
int BST::add (Node *n)
{
Node* volatile *pp = &root;
Node *p = root;
while (p) {
if (n->key < p->key) {
pp = &p->left;
} else if (n->key > p->key) {
pp = &p->right;
} else {
return 0;
}
p = *pp;
}
*pp = n;
return 1;
}
© 2014 [email protected] 28-Nov-14
School of Computer Science and Statistics, Trinity College Dublin
8
CS4021 HARDWARE TRANSACTIONAL MEMORY
BST::remove()
Node* BST::remove(INT64 key)
{
Node **pp = &root;
Node *p = root;
while (p) {
if (key < p->key) {
pp = &p->left;
} else if (key > p->key) {
pp = &p->right;
} else {
break;
}
p = *pp;
}
if (p == NULL)
return NULL;
© 2014 [email protected] 28-Nov-14
School of Computer Science and Statistics, Trinity College Dublin
9
CS4021 HARDWARE TRANSACTIONAL MEMORY
BST::remove()…
if (p->left == NULL && p->right == NULL) {
*pp = NULL;
// NO children
} else if (p->left == NULL) {
*pp = p->right;
// ONE child
} else if (p->right == NULL) {
*pp = p->left;
// ONE child
} else {
Node *r = p->right;
// TWO children
Node **ppr = &p->right;
// find min key in right sub tree
while (r->left) {
ppr = &r->left;
r = r->left;
}
p->key = r->key;
// could move...
p = r;
// node instead
*ppr = r->right;
}
return p;
// return removed node
}
© 2014 [email protected] 28-Nov-14
School of Computer Science and Statistics, Trinity College Dublin
10
CS4021 HARDWARE TRANSACTIONAL MEMORY
Tutorial 3
1. add binary tree into existing framework
2. test with single thread
3. protect tree with a testAndTestAndSet lock
4. convert testAndTestAndSet to an HLE lock
5. wrap each add() and remove() function call in a transaction
6. provide non-transactional path
7. after each test, check that BST is valid and that NO Nodes are lost
8. need to use a PC that supports TSX (eg ICT huts)

can check using rtmSupported() function in helper.cpp
© 2014 [email protected] 28-Nov-14
School of Computer Science and Statistics, Trinity College Dublin
11

Slides - LRR - Technische Universität München

ホンダNBOX REMOVE「リモーブ」取付