Grid Resource Allocation - Grid Computing: Infrastructure, Service, and Applications - page 171

each computation node. Moreover, some particular formations of perfor-
mance information, such as quantii able metrics, are needed to i t the
requirement of grid scheduling.
There is static and dynamic information on a resource. Static informa-
tion changes slowly with respect to program execution lifetimes. Due to
quick changes, application execution time on the resource and job waiting
time in the queue are dynamic characteristics. Since grid schedulers do
not have central control over resources, these dynamic l uctuations make
scheduling complex and difi cult. In order to accurately predict the
performance, people developed several ways to model this information.

7. 4 .1.1 Runtime Predictions

Many techniques have been proposed to predict application execution
time. The type of prediction techniques can generally be separated into
statistical and analytical approaches. Statistical approaches use statistical
analysis of previous applications that have completed to conduct the
prediction, whereas analytical approaches construct equations to describe
application execution time. Statistical approaches can be further classii ed
into three classes: time series analysis [13], categorization [14], and instance-
based learning [15]. Analytical approaches develop models by hand [16] or
use automatic code analysis or instrumentation [17]. Figure 7.1 shows that
the runtime prediction approaches taxonomy.
However, studies showed that the statistical properties of these charac-
teristics are difi cult to model since time series of measurements for a given
characteristic have a slowly decaying auto-correlation structure. Despite
these statistical properties, predictions based on historical data are more
general since no direct knowledge about applications is required.
The categorization approach derives execution time prediction from his-
torical information of previous similar runs. This approach is based on the
observation that similar applications are more likely to have similar
runtimes than applications that have nothing in common [18]. In this

Time series analysis

Categorization

Statistical

Runtime
prediction

Instance-based learning

Model by hand

Analytical

Automatic code/
instrumentation

FIGURE 7.1 Runtime prediction approaches taxonomy.