Unit3-sp

  • May 2020
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Unit3-sp as PDF for free.

More details

  • Words: 2,890
  • Pages: 39
Unit 3: Data Structures on Trees

․Course contents: ⎯ ⎯

Binary search trees Red-black trees

․Readings: ⎯

Unit 3

Chapters 10 (self reading), 12, 13

Y.-W. Chang

1

Example Chip Floorplans

Pentium 4 PowerPC Unit 3

Y.-W. Chang

2

B*-tree: A Binary Tree Modeling for Floorplans ․ Chang et al., “B*-tree: A new representation for non-slicing ․

floorplans,” ACM/IEEE Design Automation Conference, 2000. Apply the Depth-First Search (DFS) to construct the tree. ⎯ left child: adjacent, bottom-most module on the right. ⎯ right child: nearest module above with the same x-coordinate.

n0 b6

b5 b1

b2 b0

b3 b

n7

b10

4

n8 b9 b8

b11

b7

n2 n5

n11 n9

n3

n10

Compacted floorplan Unit 3

n1

n4

B*-tree Y.-W. Chang

n6

3

B*-tree Based Floorplanner for Complex Designs

12,752 cells, 247 macros 2003年教育部 IC/CAD Contest 定題組特優 (第一名) 2003 ACM/SIGDA University Booth Show (DAC-2003) CPU time = 0.78 min on By Tung-Chieh Chen (陳東傑) SUN Blade 2000 Unit 3

Y.-W. Chang

4

Binary Search Tree ․ Binary-search-tree (BST) property: Let x be a node in a BST. If y is a node in the left subtree of x, then key[y] ≤ key[x]. If y is a node in the right subtree of x, then key[x] ≤ key[y]. ․ Tree construction: Worst case: O(n2); average case: O(nlgn), where n is the # of nodes. ․ Operations Search, Minimum, Maximum, Predecessor, Successor, Insert, Delete can be performed in O(h) time, where h is the height of the tree. ․ Worst case: h = θ(n); balanced BST: h = θ(lgn). ․ Can we guarantee h = θ(lgn)? Balance search trees!!

Unit 3

Y.-W. Chang

5

Tree Search ․ Operations Search can be performed in O(h) time, where h is the height of the tree. Iterative-Tree-Search(x, k) 1. while x ≠ NIL and k ≠ key[x] 2. do if k < key[x] 3. then x ← left[x] 4. else x ← right[x] 5. return x

Unit 3

Y.-W. Chang

6

Tree Successor Tree-Successor(x) 1. if right[x] ≠ NIL 2. then return Tree-Minimum(right[x]) 3. y ← p[x] 4. while y ≠ NIL and x = right[y] y is the lowest ancestor of x, whose left child is also 5. do x ← y an ancestor of x 6. y ← p[y] 7. return y Tree-Minimum(x) 1. while left[x] ≠ NIL 2. do x ← left[x] 3. return x

y x y x Unit 3

4

Y.-W. Chang

7

Tree Insertion Tree-Insert(T, z) 1. y ← NIL 2. x ← root[T] 3. while x ≠ NIL 4. do y ← x 5. if key[z] < key[x] 6. then x ← left[x] 7. else x ← right[x] 8. p[z] ← y 9. if y = NIL 10. then root[T] ← z 11. else if key[z] < key[y] 12. then left[y] ← z 13. else right[y] ← z

Unit 3

Y.-W. Chang

xy xy 4

x z

8

Deletion in Binary Search Trees ․ Case a: The node to be deleted (z) has no children (i.e., a leaf). ․ Case b: The node to be deleted (z) has only one child. ․ Case c: The node to be deleted (z) has two children.

Unit 3

Y.-W. Chang

9

Tree Deletion Tree-Delete(T, z) 1. if left[z] = NIL or right[z] = NIL 2. then y ← z; 3. else y ← Tree-Successor(z); 4. if left[y] ≠ NIL 5. then x ← left[y]; 6. else x ← right[y]; 7. if x ≠ NIL 8. then p[x] ← p[y]; 9. if p[y] = NIL 10. then root[T] ← x; 11. else if y = left[p[y]] /* y is a left child.*/ 12. then left[p[y]] ← x; 13. else right[p[y]] ← x; 14. if y ≠ z then 15. then key[z] ← key[y]; /* Copy y's satellite data into z.*/ 16. 17. return y Unit 3

Y.-W. Chang

10

Tree Deletion (cont’d) Tree-Delete(T, z) 1. if left[z] = NIL or right[z] = NIL 2. then y ← z; 3. else y ← Tree-Successor(z); 4. if left[y] ≠ NIL 5. then x ← left[y]; 6. else x ← right[y]; 7. If x ≠ NIL 8. then p[x] ← p[y]; 9. if p[y] = NIL 10. then root[T] ← x; 11. else if y = left[p[y]] 12. then left[p[y]] ← x; 13. else right[p[y]] ← x; 14. if y ≠ z then 15. then key[z] ← key[y]; /* Copy y's satellite data into z. */ 16. 17. return y Unit 3

Y.-W. Chang

11

Balanced Search Trees: Red-Black Trees ․ Add color field to nodes of binary trees. ․ Red-black tree properties: 1. 2. 3.

4.

Unit 3

Every node is either red or black. Every leaf (NIL) is black. If a node is red, both its children are black (i.e., no two consecutive reds on a simple path). Every simple path from a node to a descendent leaf contains the same # of black nodes.

Y.-W. Chang

12

Black Height ․ Black height of node x, bh(x): # of blacks on path to leaf, not counting x. ․ Theorem: A red-black tree with n internal nodes has height at most 2lg(n+1). ⎯



Unit 3

Strategy: First bound the # of nodes in any subtree, then bound the height of any subtree. Claim 1: Any subtree rooted at x has ≥ 2bh(x) - 1 internal nodes. Proof by induction: bh(x) = 0 → x is a NIL (leaf) node. Assume the claim is true for all trees with black height < bh(x). If x is red, both subtrees have black height bh(x) - 1. If x is black, both subtrees have black height at least bh(x)-1. Thus, # of internal nodes in any subtree rooted at x is nx ≥ (2bh(x)-1 - 1) + (2bh(x)-1 - 1) + 1 ≥ 2bh(x) - 1.

Y.-W. Chang

13

Black Height (cont'd)

․Let h be the height of the red-black tree. ⎯



Claim 2: bh(root) ≥ h/2. (i.e., at least half the nodes on any single path from the root to leaf must be black.) By Property 3: ≤ h/2 nodes on that path are red. At root, n ≥ 2bh(root) - 1 ≥ 2h/2 - 1 ⇒ h ≤ 2 lg(n+1).

․Thus, red-black trees are balanced. (Height is at most twice optimal.) ․Corollary: Search, Minimum, Maximum, Predecessor, Successor take O(lgn) time. ․How about Delete and Insert? ⎯

Unit 3

Need to maintain the red-black tree properties!

Y.-W. Chang

14

Rotations

․Left/right rotations: The basic restructuring step for binary search trees. ․Rotation is a local operation changing O(1) pointers. ․In-order property preservation: An in-order search tree before a rotation stays an in-order one. ⎯ ⎯

Unit 3

In-order: The property of a binary search tree still holds!!

Y.-W. Chang

15

Left Rotation Left-Rotate(T, x) 1. y ← right[x]; /* Set y.*/ 2. right[x] ← left[y]; /* Turn y's left subtree into x's right subtree.*/ 3. if left[y] ≠ NIL 4. then p[left[y]] ← x; 5. p[y] ← p[x]; /* Link x's parent to y.*/ 6. if p[x] = NIL 7. then root[T] ← y; 8. else if x = left[p[x]] /* x is a left child */ 9. then left[p[x]] ← y; 10. else right[p[x]] ← y; 11. left[y] ← x; /* Put x on y's left.*/ 12. p[x] ← y

Unit 3

Y.-W. Chang

16

Insertion

․Every insertion takes place at a leaf; this changes a black NIL pointer to a node with two black NIL pointers. ․To preserve the black height of the tree, the new node is set to red. ⎯

If the new parent is black, then we are done; otherwise, we must restructure (Property 3 violation)!!

․How to fix two reds in a row? Check uncle's color! ⎯

Unit 3

If the uncle is red, reversing the relatives' colors either solves the problem or pushes it one-level higher.

Y.-W. Chang

17

Insertion: Black Uncle

․How to fix two reds in a row? Check uncle's color! ⎯



Unit 3

If the uncle is black (all nodes around the new node and its parent must be black), rotate right about the grandparent. Change some nodes' colors to make the black height the same as before.

Y.-W. Chang

18

Insertion: Pseudocode

Unit 3

RB-Insert(T, x) 1. Tree-Insert(T, x); 2. color[x] ← RED; 3. while x ≠ root[T] and color[p[x]] = RED 4. do if p[x] = left[p[p[x]]] 5. then y ← right[p[p[x]]]; 6. if color[y] = RED /* uncle's color is red */ 7. then /* Case 1 */ 8. color[p[x]] ← BLACK; 9. color[y] ← BLACK; 10. color[p[p[x]]] ← RED; 11. x ← p[p[x]]; 12. else if x = right[p[x]] /* uncle's color is black */ 13. then /* Case 2*/ 14. x ← p[x]; 15. Left-Rotate(T,x); 16. color[p[x]] ← BLACK; /* Case 3*/ 17. color[p[p[x]]] ← RED; 18. Right-Rotate(T, p[p[x]]); 19. else (same as then clause with “right” and “left” exchanged) 20. color[root[T]] ← BLACK; Y.-W. Chang

19

Insertion: Example

left rotate

Unit 3

Y.-W. Chang

20

Deletion in Binary Search Trees Revisited ․ Case a: The node to be deleted has no children (i.e., a leaf). ․ Case b: The node to be deleted has only one child. ․ Case c: The node to be deleted has two children.

Unit 3

Y.-W. Chang

21

Deletion in Red-Black Trees

․If y (the spiced out node) is black, call RBDelete-Fixup (line 17) to fix the black height. (z: the deleted node; x: y's sole child)

Unit 3

RB-Delete(T,z) 1. if left[z] = nil[T] or right[z] = nil[T] then 2. y ← z; 3. else y ← Tree-Successor(z); 4. if left[y] ≠ nil[T] then 5. x ← left[y]; 6. else x ← right[y]; 7. p[x] ← p[y]; 8. if p[y] = nil[T] then 9. root[T] ← x; 10.else if y = left[p[y]] then left[p[y]] ← x; 11. 12. else right[p[y]] ← x; 13. if y ≠ z then 14. key[z] ← key[y]; 15 /* Copy y's satellite data, too. */ 16. if color[y] = BLACK then 17. RB-Delete-Fixup(T,x); 18. return y Y.-W. Chang

22

Deletion Color Fixup

․If y is black, we must give each of its descendants

another black ancestor ⇒ push y's blackness onto its child x. ․If an appropriate node is red, simply color it black; must restructure, otherwise. ⎯

⎯ ⎯

Black NIL becomes doubly black. Red becomes black. Black becomes doubly black.

․Goal: Recolor and restructure the tree so as to get rid of doubly black. ․Key: Move the extra black up the tree until ⎯ ⎯ ⎯

Unit 3

x points to a red node, simply color it black. x points to the root, the extra black can simply be removed. Suitable rotations and recolorings can be performed. Y.-W. Chang

23

Four Cases for Color Fixup ․ Case 1: The doubly black node x has a red sibling w. ․ Case 2: x has a black sibling and two black nephews. ․ Case 3: x has a black sibling, and its left nephew is red and its right nephew is black. ․ Case 4: x has a black sibling, and its right nephew is red (left nephew can be any color). ․ The # of black nodes in each path is preserved. ․ At most 3 rotations are done; only case 2 can be repeated. B A

Unit 3

Y.-W. Chang

24

Case 1 for Color Fixup

․Case 1: The doubly black node x has a red sibling w. ․One left rotation around p[x] and constant # of color changes are done. ․The # of black nodes in each path is preserved. ․Converts into case 2, 3, or 4.

Unit 3

Y.-W. Chang

25

Case 2 for Color Fixup

․Case 2: x has a black sibling and two black nephews. ․Take off one black from x and and its sibling, push one black up to p[x], and repeat the while loop with p[x] as the new node x. ․The # of black nodes in each path is preserved. ․Perform constant # of color changes and repeat at most O(h) times. (No rotation!!) B

Unit 3

Y.-W. Chang

26

Case 3 for Color Fixup

․Case 3: x has a black sibling, and its left nephew is red and its right nephew is black. ․Perform a right rotation on x’s sibling and constant # of color changes. ․The # of black nodes in each path is preserved. ․Convert into case 4.

Unit 3

Y.-W. Chang

27

Case 4 for Color Fixup

․Case 4: x has a black sibling, and its right nephew is red (left nephew can be any color). ․Performs a left rotation on p[x] and constant # of color changes => remove the doubly black on x. ․The # of black nodes in each path is preserved. ․Make x as the root and terminate the while loop.

Unit 3

Y.-W. Chang

28

Color Fixup for Deletion RB-Delete-Fixup(T,x) 1. while x ≠ root[T] and color[x] = BLACK do 2. if x=left[p[x]] then 3. w ← right[p[x]]; 4. if color[w] = RED then 5. color[w] ← BLACK; /* Case 1 */ 6. color[p[x]] ← RED; /* Case 1 */ 7. Left-Rotate(T, p[x]); /* Case 1 */ 8. w ← right[p[x]]; /* Case 1 */ 9. If color[left[w]] = BLACK and color[right[w]] = BLACK then 10. color[w] ← RED; /* Case 2*/ 11. x ← p[x]; /* Case 2 */ 12. else if color[right[w]] = BLACK then 13. color[left[w]] ← BLACK; /* Case 3*/ 14. color[w] ← RED; /* Case 3*/ 15. Right-Rotate(T, w); /* Case 3*/ 16. w ← right[p[x]]; /* Case 3*/ 17. color[w] ← color[p[x]]; /* Case 4*/ 18. color[p[x]] ← BLACK; /* Case 4*/ 19. color[right[w]] ← BLACK; /* Case 4*/ 20. Left-Rotate(T, p[x]); /* Case 4*/ 21. x ← root[T]; 22. else (same as then clause with "right" and "left" exchanged) 23. color[x] ← BLACK; Unit 3

Y.-W. Chang

29

Conclusion: Red-Black Trees

․Red-black trees are balanced binary search trees. ․All dictionary operations (Minimum, Maximum, Search, Successor, Predecessor, Insert, Delete) can be performed in O(lgn) time. ․At most 3 rotations are done to rebalance.

Unit 3

Y.-W. Chang

30

Example Floorplans Revisited

Pentium 4 PowerPC Unit 3

Y.-W. Chang

31

Slicing Tree ․ Otten, “Automatic floorplan design,” ACM/IEEE Design Automation Conference, 1982. ․ Binary-tree structure for slicing floorplans. ⎯ An internal node denotes a vertical or a horizontal cut. ⎯ A leaf denotes a module. V H

b3

b1

H 1

2 b4 b2

V

V b6

3

b5 b7

6

A slicing floorplan Unit 3

H

7 4

5

A slicing tree Y.-W. Chang

32

B*-tree Revisited ․ Chang et al., “B*-tree: A new representation for non-slicing ․

floorplans,” ACM/IEEE Design Automation Conference, 2000. Apply the Depth-First Search (DFS) to construct the tree. ⎯ left child: adjacent, bottom-most module on the right. ⎯ right child: nearest module above with the same x-coordinate.

n0 b6

b5 b1

b2 b0

b3 b

n7

b10

4

n8 b9 b8

b11

b7

n2 n5

n11 n9

n3

n10

Compacted floorplan Unit 3

n1

n4

B*-tree Y.-W. Chang

n6

33

Cost Evaluation: Packing

․ x-coordinates can be determined by the tree structure. ⎯ ⎯

Left child: the lowest, adjacent block on the right (xj = xi + wi). Right child: the first block above, with the same x-coordinate (xj = xi).

․ y-coordinates? b5 b b11

n0

b6 b3

b2

b10

n7

b4

n1

n8

x1=x0 b00

n2 n5

b9 b8

b11

n11 n9

n3

n6

b7 (x0,y0)

w0 Unit 3

x7=x0+w0 Y.-W. Chang

n10

n4 34

Computing y-coordinates

․Reduce the complexity of computing a y-coordinate to amortized O(1) time. horizontal contour vertical contour b10

b1 b3 b

4

b0

b9 b8

b11 b7

Unit 3

Y.-W. Chang

35

Perturbations

․Example perturbations Op1: rotate a module Op2: delete & insert a module Op3: swap 2 modules

⎯ ⎯ ⎯

2

2 4 1 13 15

4

7

1

12 3

11

13

5

1

12 7

11 10

13

6 5

15 9

9

12 3

10

11

9 14

14

14

8

8

Unit 3

7

Op2(11, 5)

6

15

10

4

3

Op3(7, 3)

6 5

2

Y.-W. Chang

8

36

B*-trees for Large-Scale Designs

9800 modules, dead space = 3.44%, CPU time = 256 min on SUN Ultra 60

Unit 3

Y.-W. Chang

12,752 cells, 247 macros CPU time = 0.78 min on SUN Blade 2000 37

B*-trees for Analog Circuit Design ․ The best analog layout placement tool by Balasa et al. (ICCAD2002, ASP-DAC-2003 best paper nomination) based on RB B*trees

Unit 3

Y.-W. Chang

38

Floorplan Quality Comparison ․ B*-tree is the best representation for packing reported in a recent survey (Chan, Adya, Markov, ISPD-05) ․ B*-tree citations: more than 100 citations in ACM/IEEE papers since its publication at DAC-2K (> 70% of floorplanning papers) ․ B*-tree code is available at http://eda.ee.ntu.edu.tw/research.htm/ MCNC SP Q-Seq O-tree CBL Slicing TCG Ckts (Japan) (Japan) (USA) (China) (USA) (Ours) 1995 2002 1999 2001 2005 DAC 2001

TCG-S (Ours) DAC 2002

CS B*-tree (Ours) (Ours) TVLSI DAC 2003 2000

apte

48.12

46.92

47.1

NA

46.92

46.92

46.92

46.92

46.92

xerox

20.69

19.93

20.1

20.96

20.20

19.83

19.796

19.83

19.796

hp

9.93

9.03

9.21

NA

9.03

8.947

8.947

8.947

8.947

ami33

1.22

1.194

1.25

1.20

1.183

1.20

1.185

1.18

1.168

ami49

38.84

36.75

37.6

38.58

36.24

36.77

36.4

36.24

36.4

Best chip areas are in red (mm2) Unit 3

Y.-W. Chang

39