CPU usage pattern discovery using suffix tree for computational resource advisory system
Loading...
Date
2006-07
Authors
Ooi, Boon Yaik
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In grid computing environment, resource availability often changes from time to
time. Thus, schedulers require resource prediction help to make effective scheduling
decision. This is because the decision for each job submission must be made prior to
submitting a job. The selection of suitable combination of resources is essential to
obtain acceptable application performance level. Most of the resource prediction
methods were designed with the objective of getting the prediction as accurate as
possible. However, there are cases where longer term of prediction is preferred. For
example, a job that requires days to complete and has less tolerance to interruption.
Therefore, estimation of the average CPU usage for the next few hours or days is
going to be more useful than CPU usage prediction at a single future point in time.
This thesis devises a CPU usage advisory model to discover CPU usage patterns
from its usage data history using suffix tree. The model produces pattern reports and
CPU usage predictions to allow users to understand the CPU usage better, provide
extra information to enhance scheduling decision and help to find opportunities for
exploiting the available CPU resources. CPU usage data is treated as a time series
and processed with a series of steps namely data reduction, normalisation
discretisation and pattern discovery. In the pattern discovery process, a suffix tree
constructed and used to reveal usage pattern in the CPU data.
The discovery of usage patterns allows us to perform more step-ahead predictions
as compared to the conventional CPU usage prediction methods. Information such as
the time when a resource is usually available and how long will this resource continue
to be available could be derived from the discovered patterns. We introduce a CPU
usage prediction strategy that assumes a frequent pattern will reoccur in the future and
implemented this strategy with two approaches. If the reoccurrences of a frequent
pattern is known in advance, then a longer term prediction is feasible. The cyclic
pattern prediction approach captures the reoccurrence cycle of a pattern and performs
prediction by estimating the reoccurrence of the next cycle. The non-cyclic frequent
pattern approach performs prediction when the CPU usage pattern sl'lows some
similarity to the starting part of a segment of a frequent pattern.
This model is implemented and evaluated with 20 sets of CPU usage data from 10
different machines. The experimental results are promising. Frequent patterns do exist
in CPU usage data. We discovered that some patterns could be related to the CPU
owner's usage behaviour. CPU frequent patterns can be used to perform prediction.
Most of the patterns used for prediction are horizontal line which indicates no usage
changes. This is because the usage of an active CPU changes dynar~1ically and rarely
exhibit similar patterns. Our pattern prediction approach is capable of providing longer
term prediction compared to Network Weather Services and Tendency-based
predictors. Pattern prediction approach is able to provide better estimation especially
when the CPU usage changes drastically.
Description
Keywords
Pattern discovery using suffix tree , Resource advisory system