Guidelines for scheduling some common computation-dags for Internet-based computing

doi:10.1109/TC.2005.65

2005-04-01

PRE

Arnold L. Rosenberg

M. Yurkewych

DOI：10.1109/TC.2005.65

原文链接

原文求助

摘要

En 中文

A pebble game is developed to model the process of scheduling computation-dags for Internet-based computing (IC, for short). Strategies are derived for scheduling three common, significant families of such dags for IC: reduction-meshes, which represent (the intertask dependencies of) computations that can be performed by up-sweeps of meshes; reduction-trees, which represent accumulative computations that can be performed by up-sweeps of trees; and FFT ( Fast Fourier Transform) dags, which represent a large variety of convolutional computations. Two criteria are used to assess the quality of a schedule: its memory requirements and its rate of producing tasks that are eligible for allocation to remote clients. These criteria are important because of, respectively, the typically enormous sizes of IC computations and the typical temporal unpredictability of remote clients in IC. In particular, a high production rate of eligible tasks decreases a computation's vulnerability to the gridlock that can occur when a computation stalls pending the return of intermediate results by remote clients. Under idealized assumptions, the schedules derived are optimal in the rate of producing eligible tasks and are either exactly or approximately optimal in memory requirements.

Keyword:

Internet-based computing

grid computing

global computing

Web computing

scheduling

reduction computations

convolutional computations

mesh-structured computations

tree-structured computations