|
Assume that the largest piece of work at any point is W
|
səhifə | 16/23 | tarix | 26.12.2016 | ölçüsü | 0,99 Mb. | | #3369 |
|
After V(p) requests, the maximum work remaining at any processor is less than (1 - α)W; after 2V(p) requests, it is less than (1 - α)2W. After (log1/1(1- α )(W/ε))V(p) requests, the maximum work remaining at any processor is below a threshold value ε.
Analyzing DFS If tcomm is the time required to communicate a piece of work, then the communication overhead is given by T0 = tcommV(p)log W (1) The corresponding efficiency E is given by
Asynchronous Round Robin: V(p) = O(p2) in the worst case. Global Round Robin: V(p) = p. Random Polling: Worst case V(p) is unbounded. We do average case analysis.
Let F(i,p) represent a state in which i of the processors have been requested, and p - i have not. Let f(i,p) denote the average number of trials needed to change from state F(i,p) to F(p,p) (V(p) = f(0,p)).
Dostları ilə paylaş: |
|
|