Loading...
Please wait, while we are loading the content...
Similar Documents
On Trading Task Reallocation for Thread Management in MultiprocessorsLixin
| Content Provider | Semantic Scholar |
|---|---|
| Author | Rosenberg, Arnold L. Ramesh, K. Department, Sitaraman |
| Copyright Year | 2007 |
| Abstract | Most general-purpose multiprocessors are time-shared among multiple users. When a user arrives, s/he requests a submachine of size appropriate to his/her computation ; the processor-allocation algorithm then assigns him/her a portion of the multi-processor of the requested size. This study is motivated by the fact that, as successive users arrive, use a portion of the multi-processor, and depart, various individual processors in the multiprocessor may nd themselves managing quite disparate numbers of threads. This load-imbalance is clearly undesirable, and can be rectiied by reallocating (or migrating) the tasks periodically so as to balance the processors thread-loads. However, task reallocation is an expensive operation and must be performed infrequently , if ever. This paper establishes that there is a predictable trade-oo between the frequency of task reallocation and the imbalance in the processor loads. The processor-allocation algorithms devised in this paper are applicable to any hierarchically-decomposable multiprocessor, even though we state all our results for a tree-based multiprocessor. We devise a deterministic processor-allocation algorithm for an N-processor tree-machine that achieves a maximum load of min n (d + 1); l 1 2 (log N + 1) mo L ; where L is the optimal load achievable for the task sequence , and d is the reallocation parameter. We prove a lower bound by showing that no deterministic algorithm with reallocation parameter d can achieve a load less than min nl 1 2 (d + 1) m ; l 1 2 (log N + 1) mo factor away from the optimal load for all task sequences. Next, we present a randomized processor-allocation algorithm for an N-processor tree-machine that does not reallocate tasks and achieves a load of at most 2 log N log log N + 1 L ; where L is the optimal load of the task sequence; and, we show that no randomized processor-allocation algorithm without reallocation can achieve within a factor of 1 7 log N log log N 1=3 from the optimal load for all task sequences. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www-unix.ecs.umass.edu/~lgao/spaa96_final.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
