[Question] HW6 How to get Parent of a bucket?

Question

[Question] HW6 How to get Parent of a bucket?

Closed this issue a month ago · 3 comments

Hi, I don't understand the following line in the paper: "This value is achieved by calling the GET PARENT macro that unsets bucket’s most significant turned-on bit". Does that mean, if we have bucket 0x101101, we have the following parent relationship?
0x101101 -> 0x001101 -> 0x000101 -> 0x000001 -> 0x000000 (where x->y means y is parent of x)

Thanks In Advance!

Answer 1 · 2024-05-21T10:24:29.000Z

See #699 (comment).

Answer 2 · 2024-05-21T10:49:14.000Z

I still don't understand. All explanations assume that bucket is b + 2^i where i is log_2(size) - 1. What if our bucket is 2^(i-1)? then its parent is 2^(i-1) - 2^(i) which gives negative. I know that for b + 2^i, setting MSB to zero gives b. I want to know if the general way is to set MSB to zero or not.

Answer 3 · 2024-05-21T11:42:50.000Z

Oh, the explanation of this part in the book is pretty rough. For the index with size less than 2^i, you should shift size to be less than the index. See fig 13.19. of the art of multiprocessor programming.

0x101101 -> 0x001101 -> 0x000101 -> 0x000001 -> 0x000000 (where x->y means y is parent of x)

In other words, this is correct.