𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Guidelines for Data-Parallel Cycle-Stealing in Networks of Workstations: I. On Maximizing Expected Output

✍ Scribed by Arnold L. Rosenberg


Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
192 KB
Volume
59
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis


We derive computationally efficient guidelines for nearly optimal scheduling of data-parallel computations within a draconian mode of cycle-stealing in networks of workstations (nows). In this computing regimen, workstation A takes control of workstation B 's processor whenever it is idle, with the promise of relinquishing control immediately upon demand thereby losing all work in progress on B. The typically high communication overhead for supplying workstation B with work and receiving its results recommends that one supply B with large amounts of work at a time; the risk of losing work in progress when B is reclaimed recommends that one supply B with a succession of small bundles of work. The challenge is to balance these two pressures in a way that maximizes (some measure of ) the amount of work accomplished. Our guidelines attempt to maximize the expected work accomplished by workstation B in an episode of cycle-stealing, assuming knowledge of the instantaneous probability of workstation B 's being reclaimed. The schedules produced by our guidelines accomplish almost as much work as do the ad hoc optimal schedules crafted in S. N. Bhatt, F. R. K. Chung, F. T. Leighton, and A. L. Rosenberg, On optimal strategies for cycle-stealing in networks of workstations, IEEE Trans. Comp. 46 (1997), 545 557. Our study is thus a step toward rendering prescriptive the descriptive study of cycle-stealing in that source.


📜 SIMILAR VOLUMES