基于判例构造的并行作业性能预测

针对基于MPI 的并行作业性能预测问题,鉴于历史预测与建模分析方法在异构网络计算环境中性能预测的局限,提出了基于判例构造的并行作业性能预测方法.在MPI 库PMPI 接口中插入封套函数,获取通信日志,并设计了日志规整和合并算法.将最核心的日志循环收缩问题,转化为字符串循环子串收缩问题,提出了一种基于后缀数组算法,在理论和实际的性能方面均优于已有算法;判例程序自动构建阶段,解决了计算时间与通信时间等比例缩放问题,设计了自动构建可执行判例程序的方法.同构与异构机群环境实验结果表明,判例预测方法能够比较准确地预估计算作业的运行时间,对于同构机群误差不超过3%,异构机群误差不超过10%,与同类算法相比,具有较好的综合性能.

Parallel Job Performance Prediction Based on the Case Reconstruction

Accurate prediction of the running time of parallel jobs under different computing resources is the foundation of many job scheduling approaches. A job performance prediction method based on the Performance Skeleton is proposed to avoid the inaccuracy of historical and modeling analysis prediction methods in heterogeneous clusters. To record the running trace, a method is designed to access all communication traces during the runtime. To merge these traces, this paper designs a trace-merge algorithm to structure the communication traces. To compress the circulatory traces, which is the most central and difficult, this paper converts it into a circular sub-string compressing problem, and proposes an algorithm based on the suffix array. Its performance is theoretically and practically better than the existing algorithms. To automatically reconstruct the Performance Skeleton, it solves the scalable problem of calculation and communication time. Experimental results show that these methods can accurately estimate the running time of computing jobs. The error is less than 3% for homogeneous clusters, and 10% for heterogeneous clusters.