DocumentCode :
2552856
Title :
Efficient response time predictions by exploiting application and resource state similarities
Author :
Li, Hui ; Groep, David ; Wolters, Lex
Author_Institution :
Leiden Inst. of Adv. Comput. Sci., Leiden Univ., Netherlands
fYear :
2005
fDate :
13-14 Nov. 2005
Abstract :
In large-scale grids with many possible resources (clusters of computing elements) to run applications, it is useful that the resources can provide predictions of job response times so users or resource brokers can make better scheduling decisions. Two metrics need to be estimated for response time predictions: one is how long a job executes on the resource (application run time), the other is how long the job waits in the queue before starting (queue wait time). In this paper we propose an instance based learning technique to predict these two metrics by mining historical workloads. The novelty of our approach is to introduce policy attributes in representing and comparing resource states, which is defined as the pool of running and queued jobs on the resource at the time to make a prediction. The policy attributes reflect the local resource scheduling policies and they can be automatically discovered using a genetic search algorithm. The main advantages of this approach compared with scheduler simulation are two-folds: Firstly, it has a better performance to meet the real time requirement of Grid resource brokering; secondly, it is more general because the scheduling policies are learned from past observations. Our experimental results on the NIKHEF LCG production cluster show that acceptable prediction accuracy can be obtained, where the relative prediction errors for response times are between 0.35 and 0.70.
Keywords :
data mining; genetic algorithms; grid computing; learning (artificial intelligence); queueing theory; resource allocation; scheduling; search problems; NIKHEF LCG production cluster; application state similarities; genetic search algorithm; grid computing; grid resource brokering; historical workload mining; instance based learning; job queueing; job response time prediction; policy attributes; resource scheduling policies; resource state similarities; scheduling decisions; Accuracy; Application software; Delay; Genetics; Grid computing; Large-scale systems; Physics computing; Processor scheduling; Production; Scheduling algorithm;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Grid Computing, 2005. The 6th IEEE/ACM International Workshop on
Print_ISBN :
0-7803-9492-5
Type :
conf
DOI :
10.1109/GRID.2005.1542747
Filename :
1542747
Link To Document :
بازگشت