On optimal strategies for cycle-stealing in networks of workstations

We study the parallel scheduling problem for a new modality of parallel computing: having one workstation steal cycles from another. We focus on a draconian mode of cycle-stealing, in which the owner of workstation B allows workstation A to take control of B's processor whenever it is idle, with the promise of relinquishing control immediately upon demand. The typically high communication overhead for supplying workstation 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 militates in favor of supplying B with a sequence of small packets of work. The challenge is to balance these two pressures in a way that maximizes the amount of work accomplished. We formulate two models of cycle-stealing. The first attempts to maximize the expected work accomplished during 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 stealer can accomplish. We derive optimal scheduling strategies for sample scenarios within each of these models. Perhaps our most important discovery is the as-yet unexplained coincidence that two quite distinct scenarios lead to almost identical unique optimizing schedules. One scenario falls within our first model; it assumes that the probability of the return of B's owner is uniform across the lifespan of the episode; the optimizing schedule maximizes the expected amount of work accomplished 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 schedule maximizes the amount of work that one is guaranteed to accomplish during the lifespan.