Hey Everyone, Post your solutions to the Feb 13 In-Class Exercise to this thread. Best, Chris

-- Feb 13 In-Class Exercise Thread

''Suppose we were to run P-Fib(4) whose execution graph we saw last day on two processors.'' ---- ''What would be the maximum run time according to Brent/Blumofe Leirsons's theorem?'' @BT@@BT@ '''Solution: ''' Brent/Blumofe Leirsons's theorem provides an upper bound of @BT@T_P\le T_1/P + T_\infty@BT@. Given that @BT@P=2, T_1 = 17@BT@, and @BT@T_\infty = 8@BT@, the upper bound for @BT@T_2@BT@ is given by @BT@T_2\le 17/2+8 = 16.5@BT@. ---- ''Mark up the graph with the complete and incomplete steps.'' @BT@@BT@ '''Solution: '''Using a DFS rule for the greedy scheduler, ((resource:IMG_0170.jpg|Resource Description for IMG_0170.jpg)) Using a BFS rule for the greedy scheduler, ((resource:IMG_2DEF148FC217-1.jpeg|Resource Description for IMG_2DEF148FC217-1.jpeg)) ---- ''How many steps does the computation actually take?'' @BT@@BT@ '''Solution: ''' Because @BT@T_1 = 17@BT@, given that we have 3 incomplete steps (1 strand each), we will have 7 complete steps (2 strands each). Therefore the total number of steps is 10 steps.

-- Feb 13 In-Class Exercise Thread

b) I, C , C, C, C, C, C, I, I, I, I ((resource:Class Exercise 1-13.JPG|Resource Description for Class Exercise 1-13.JPG))

-- Feb 13 In-Class Exercise Thread

((resource:Feb 11, 2019 (1).jpg|Resource Description for Feb 11, 2019 (1).jpg)) Max running time by Brent's: max time <= T_1 / P + T_infinity = 17 / 2 + 8 = 16.5 max running time is 16. Actually, it takes 10 steps. Step 1, 9, 10 are incomplete steps.

-- Feb 13 In-Class Exercise Thread

What would be the maximum run time according to Brent/Blumofe Leirsons's theorem? TP≤T1P+T∞ = 17/2 + 8 = 33/2 ((resource:fib.png|Resource Description for fib.png)) The computation take 11 steps. Step 1, 7, 9, 10, 11 are incomplete steps.

-- Feb 13 In-Class Exercise Thread

Suppose we were to run P-Fib(4) whose execution graph we saw last day on two processors. What would be the maximum run time according to Brent/Blumofe Leirsons's theorem? T1 = 17, T(infi) =8 T(max)<=17/2 +8 = 33/2 Mark up the graph with the complete and incomplete steps. Make as small an image of this as legibly possible. ((resource:Untitled Diagram (4).jpg|Resource Description for Untitled Diagram (4).jpg)) How many steps does the computation actually take? It takes 10 steps of which 1, 9 and 10 are incomplete

-- Feb 13 In-Class Exercise Thread

 Based on Brents's Algorithm T_{P} <= T_{1}/P + T_{infinity}

 T_{1} = 17, P = 2, T_{inf} = 8

 17/2 + 8 = 17/2 + 16/2 = 33/2

((resource:Untitled.png|Resource Description for Untitled.png)) Based on Brents's Algorithm T_{P} <= T_{1}/P + T_{infinity} T_{1} = 17, P = 2, T_{inf} = 8 17/2 + 8 = 17/2 + 16/2 = 33/2 Steps 1, 9, and 10 were incomplete.

-- Feb 13 In-Class Exercise Thread

((resource:In-class-02_13-converted.pdf|Resource Description for In-class-02_13-converted.pdf))

-- Feb 13 In-Class Exercise Thread

1) Maximum run time according to Brent's theorem 
 
T_p <= (T_1 / P) + T_inf
T_1 = 17, P = 2, T_inf = 8
T_p <= 17/2 + 8
T_p <= 33/2 
 
2) 10 steps 
 

<pre> 1) Maximum run time according to Brent's theorem T_p <= (T_1 / P) + T_inf T_1 = 17, P = 2, T_inf = 8 T_p <= 17/2 + 8 T_p <= 33/2 2) 10 steps </pre> ((resource:image1.jpg|Resource Description for image1.jpg))

-- Feb 13 In-Class Exercise Thread

1. Maximum runtime T1 = 17, Tinf=8, P=2. Tmax <= (T1)/P + Tinf = 17/2 + 8 = 33/2 2. How many step? 10 steps. ((resource:capture.JPG|Resource Description for capture.JPG))