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

approach, a template of attributes needs to be dei ned to identify the cate-
gory where the application will be assigned. Once the set of templates has
been dei ned, new applications can be added to the categories containing
similar applications, and the execution time and a coni dence interval can
be calculated. Different statistical techniques, such as mean or linear
regression, are applied to generate prediction. A prediction is formed from
each similar category of applications, and the prediction with the smallest
coni dence interval is selected to be the prediction for the application.
Instance-based learning (IBL), which is also called the locally weighted
learning technique, is another approach for runtime prediction. In this
approach, a database of experiences is used to make a prediction. For each
prediction, a query point is inputted into the database, and the data point
in the experience base that is most relevant to the query will be selected. A
proper distance metric is dei ned to measure the distances between data
instances. In fact, the IBL algorithm is a generalization of the template
approach, in which distances are simplii ed to binary values.

7. 4 .1. 2 Queue Wait-Time Predictions

Jobs submitted to a resource normally cannot be executed immediately.
They are placed in the queue waiting for resource allocation. Predictions
of queue wait times can guide a user in selecting an appropriate resource.
Wait-time predictions are also useful in grid environments when trying
to submit multiple requests so that the requests all receive resources
simultaneously. The third use of wait-time predictions is to plan other
activities in conventional supercomputing environments.
One approach to predicting wait time is using the wait times of applica-
tions in the past that were in a similar scheduler situation. This approach
uses the same mechanism as the approach to predict application execution
time. Another approach is to simulate scheduling algorithms such as i rst-
come i rst-served, least-work-i rst, and backi lling to obtain predictions
for queue wait times, where application runtimes used in simulations are
estimated using the template approach. Although this approach can
provide accurate wait-time predictions in some cases, it needs a detailed
knowledge of the scheduling algorithm to make the prediction. By perfor-
mance prediction, a scheduling system can capture future expected
resource behavior, guide the scheduler in selecting appropriate resources,
and therefore make the execution more efi cient.

7. 4 . 2 Resource Matching

In conventional resource management systems, a system model is estab-
lished, which contains information about the underlying resources. A
centralized allocator schedules the resources and maintains the allocation
information. Although such a resource management strategy works well