PHP Search Engine

Feb 13 In-Class Exercise Thread .

Hey Everyone,

Post your solutions to the Feb 13 In-Class Exercise to this thread.

Best,

Chris

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?''

``

'''Solution: ''' Brent/Blumofe Leirsons's theorem provides an upper bound of T_P\le T_1/P + T_\infty. Given that P=2, T_1 = 17, and T_\infty = 8, the upper bound for T_2 is given by T_2\le 17/2+8 = 16.5.

''Mark up the graph with the complete and incomplete steps.''

``

'''Solution: '''Using a DFS rule for the greedy scheduler,

Using a BFS rule for the greedy scheduler,

''How many steps does the computation actually take?''

``

'''Solution: ''' Because T_1 = 17, 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.

(Edited: 2019-02-15)

''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

(Edited: 2019-02-13)

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

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.

(Edited: 2019-02-13)

((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

The computation take 11 steps. Step 1, 7, 9, 10, 11 are incomplete steps.

(Edited: 2019-02-13)

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.

How many steps does the computation actually take?

It takes 10 steps of which 1, 9 and 10 are incomplete

(Edited: 2019-02-15)

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

Steps 1, 9, and 10 were incomplete.

(Edited: 2019-02-16)

((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 Description for In-class-02_13-converted.pdf

(Edited: 2019-02-16)

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

-- Feb 13 In-Class Exercise Thread

<pre>

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

10 steps

</pre>

(Edited: 2019-02-17)

<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

Maximum runtime

T1 = 17, Tinf=8, P=2. Tmax <= (T1)/P + Tinf = 17/2 + 8 = 33/2

How many step?

10 steps.

(Edited: 2019-02-18)

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))

Feb 13 In-Class Exercise Thread .

&#039;&#039;Suppose we were to run P-Fib(4) whose execution graph we saw last day on two processors.&#039;&#039;

''Suppose we were to run P-Fib(4) whose execution graph we saw last day on two processors.''