ON OPTIMAL STRATEGIES FOR CYCLE-STEALING IN NETWORKS OF WORKSTATIONS

Citation
Sn. Bhatt et al., ON OPTIMAL STRATEGIES FOR CYCLE-STEALING IN NETWORKS OF WORKSTATIONS, I.E.E.E. transactions on computers, 46(5), 1997, pp. 545-557
Citations number
19
Categorie Soggetti
Computer Sciences","Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture
ISSN journal
00189340
Volume
46
Issue
5
Year of publication
1997
Pages
545 - 557
Database
ISI
SICI code
0018-9340(1997)46:5<545:OOSFCI>2.0.ZU;2-U
Abstract
We study the parallel scheduling problem for a new modality of paralle l computing: having one workstation ''steal cycles'' from another. We focus on a draconian mode of cycle-stealing, in which the owner of wor kstation a allows workstation A to take control of B's processor whene ver it is idle, with the promise of relinquishing control immediately upon demand. The typically high communication overhead for supplying w orkstation B with work and receiving its results militates in favor of supplying B with large amounts of work at a time; the risk of losing work in progress when the owner of B reclaims the workstation militate s in favor of supplying B with a sequence of small packets of work. Th e challenge is to balance these two pressures in a way that maximizes the amount of work accomplished. We formulate two models of cycle-stea ling. The first attempts to maximize the expected work accomplished du ring a single episode, when one knows the probability distribution of the return of B's owner. The second attempts to match the productivity of an omniscient cycle-stealer, when one knows how much work that ste aler can accomplish. We derive optimal scheduling strategies for sampl e scenarios within each of these models. Perhaps our most important di scovery is the as-yet unexplained coincidence that two quite distinct scenarios lead to almost identical unique optimizing schedules. One sc enario falls within our first model; it assumes that the probability o f the return of Bs owner is uniform across the lifespan of the episode ; the optimizing schedule maximizes the expected amount of work accomp lished during the episode. The other scenario falls within our second model; it assumes that B's owner will interrupt our cycle-stealing at most once during the lifespan of the opportunity; the optimizing sched ule maximizes the amount of work that one is guaranteed to accomplish during the lifespan.