Predicting Running Time of Grid Tasks based on CPU Load Predictions

CPU LOAD PREDICTION

A. Polynomial Fitting

B. One-step-ahead Prediction Strategy

1) Prediction based on Polynomial Fitting.

From our observations we found that 2nd or 3rd order polynomial fitting achieves much better (and the best) fitting effect than the 1st order (linear) fitting

2阶3阶多项式拟合效果更好

1阶线性拟合

3 (V_(T-2), V_(T-1), V_T) or 4 (V_(T-3), V_(T-2), V_(T-1), V_T)

Polynomial fitting function and then use the function value at polynomial the next time point as P_(T+1)

2) Prediction based on Similar Patterns

when the load traces vary smoothly and monotonously,多项式拟合取得好的效果,

遇到拐点就不好使了。

如下图,There are many similar "patterns" in the load traces

We use the value of last turning point(拐点) as the prediction value for the current point, P_(T+1).

We think that next point will be a turning point.

If we can't find a successively increasing series we will predict using a "conservative" strategy: we use V_T as P_(T+1)

For the other cases we also choose a conservative prediction strategy(比较保守的预测) that set the increment (decrement增减) between V_T and P_(T+1) as 0.

步进预测策略

算法预测(V1,V2,...,VT),输入CPU加载路径历史(V1,V2,... VT)

输出P_(T+1),预测V_(T+1)的值。

Begin

if 

    if  V_{T-5}是拐点,在它之前的五个点也相继递减,

          则 P_{T+1}=V_{T-5}#直接使用拐点值作为预测结果,结合单调性

    else 预测P_{T+1}使用多项式拟合

if V_T是拐点

    搜索V_T之前最后一个拐点,使用递增度量VT预测PT+1

if VT-1是拐点

    if  最后模式改变方向在五个点之后

        使用点递增两步要求最终拐点为VT递增 

    else PT+1=VT

if VT>VT-1>VT-2>VT-3

    IF VT-3>VT-4 PT+1=VT

    ELSE P_T+1=VT-(VT-VT-1)

对于其他情况,PT+1=VT

end

 

3) Multi-steps-ahead Prediction Strategy.多步直接预测

multi-steps-ahead CPU load prediction based on the above one-step-ahead prediction strategy

当我们预测第i步加载P-T+i(i>0),我们使用2)依次预测P-T+1,P-T+1,...,P-T+I-1,then we use the historical load trace and all the predicted load values P-T+i之前的历史信息来预测P-T+i

 

IV.预测任务运行时间

A.连续时间的任务运行时间估计

爱编程-编程爱好者经验分享平台

文章评论

  

版权所有 爱编程 © Copyright 2012. w2bc.com. All Rights Reserved.
闽ICP备12017094号-3