《异构分布计算环境下应用程序的执行时间预测研究》由会员分享，可在线阅读，更多相关《异构分布计算环境下应用程序的执行时间预测研究（2页珍藏版）》请在金锄头文库上搜索。
1、第22卷第10期 计算机应用与软件 Vol.22, No.10 2005年10月 Computer Applications and Software Oct. 2005 异构分布计算环境下应用程序的执行时间预测研究异构分布计算环境下应用程序的执行时间预测研究 梁正友 , 张 凌 董守斌 亓旭光 (华南理工大学广东省计算机网络重点实验室 广东 广州 510641) (广西大学计算机与电子信息学院 广西 南宁 530004) 摘 要 随着网格计算技术的发展，需要一种预测应用在这种异构分布计算环境下执行时间的工具，以获得高性能调度和服务 级协议。本文提出了一种结合统计数据、工作量模型和机器计算速度
2、的应用程序执行时间预测方法。理论分析和初步的实验表明， 该方法有效可用，比现有的其他预测方法简单、适应范围广。 关键词 执行时间预测 异构 分布计算系统 网格 RESEARCH ON PREDICATING APPLICATIONS EXECUTION TIME IN HETEROGENEOUS DISTRIBUTED COMPUTING ENVIROMENT Liang Zhengyou , Zhang Ling Dong Shoubin Qi Xuguang 1(GuangDong Key Laboratory of Computer Network , South China Unive
3、rsity of Technology , Guangzhou Guangdong 510641, China) 2(College of Computer and Electronic Information, Guangxi University, Nanning Guangxi 530004, China) Abstract With the grid computing technology developing, a tool to predicate the execution time of an application in heterogeneous distributed
4、computing environment is needed in order to obtain high performance for scheduling and SLA. A prediction method of applications execution time was proposed in this paper, which combine the statistic data, computing workload and machines computing speed. Theoretic analysis and experiments show that t
5、his predication method is available, and is simpler than existing tools. Keywords Estimating execution time Heterogeneous Distributed computing system Grid 1 引 言 引 言 网格系统是多用户的，系统中通常会运行多个应用，为了 获得的高性能，需要一个任务调动器对这些应用进行调度。而 预测应用的执行时间是获取系统高性能的基本条件。 另一方面， 网格用户也需要知道他提交的作业的执行时间。当用户提交一 个作业给网格系统时，他通常使用最终完成期限作
6、为SLA（服 务级协议）的一个参数。然而，网格的计算资源池是异构和动 态的，用户不直接掌握用于进行估计任务执行时间的所需的资 源性能特征。因此，他们需要一种评估作业执行时间的工具。 预测串行程序执行时间是预测并行程序执行时间的基础， 本文提出了一个串行任务的执行时间预测方法，它比现有的性 能预测工具PACE1和Prophesy2要简单，因为后者需要人工参 与描述系统或应用特征，而本方法不需要人工参与。理论分析 表明它比文3提出的执行时间预测算法有更好的时间复杂性。 2 执行时间模型和预测方法 执行时间模型和预测方法 设一个串行任务的工作量为，计算机执行的计算速度是 ，分配给任务的平均CPU利用
7、率记为，任务的执行时间是 T.则可计算如下： =T (1) 2.1 工作量预测 工作量预测 一个任务的工作量可用包括控制精度在内的输入数据集作 为一个数字参数向量 21p xxxX?= 来刻画，其中 i x 是 其中的一个输入数据参数， , 1pi ，p是参数个数。工作 量表示如下： )(Xf= (2) 对于(2)，由于不知道它的解析式，不能直接计算。解决该 问题的方法之一是非参数回归算法3，它根据过去的观测值集 n ii o i X 1 ),( = ( o i 是输入为 i X时的观测工作量)进行预测： = = n i o ii XW n Xf 1 )( 1 )( (3) 其中， )(XWi
8、 是一个权重函数。 对任何向量X， )(Xf 是 o i 的加权平均值。通常，在靠近参数X的观测值， )(XWi 被赋予 较高的值，而远离X的观测值， )(XWi 被赋予较低的值。在实 践上，并非所有的n个观测值都用来计算 )(Xf ，而只是从n 个值中选取最靠近参数X的k个观测值来计算 )(Xf ，这种方 法即为K-NN算法3。该算法的时间复杂度为O(n(p+logn)，比 文3预测算法的时间复杂度O(n(p+r+logn)要好， 其中，r是表 示机器性能的维度，p是X维数，n如前述。 收稿日期:2005-07-15。广西大学科研项目（CC1402, CC1407）。梁正友， 副教授，博士生
9、，主研领域：网格计算，并行分布计算。 第10期 梁正友等：异构分布计算环境下应用程序的执行时间预测研究 121 2.2 CPU 利用率预测利用率预测 CPU利用率是指操作系统分配给任务的CPU时间的百分 比。在时分系统中，系统分给任务的时间片决定于任务的优先 级、计算机中运行任务总数及其属性。在专用情况下，同种任 务获得的CPU时间片是一样的。因此，我们简单的将上次的观 测值作为预测值，即： o kji p kji, 1, = (4) 其中 p kji, 是应用K的第i次执行在机器j上平均CPU利用 率预测值。 o kji, 1 为第i-1次执行的观测值， 在执行时由调度器 测量CPU时间和执
10、行时间T，并按公式(5)计算。 T TCPU o kji = , 1 (5) 其中，T是任务的执行时间，TCPU是任务执行时的CPU 时间。 2.3 计算速度 计算速度 计算速度用性能基准来表示。但计算机对不同的应用类型 的执行速度是不一样的。在实践上，我们选用BYTEmark工具 4提 供 的 10项 性 能 基 准 作 为 预 置 的 值 ， 用 性 能 向 量 1021 iiii bbbB= 表示，提交作业时，从这10项性能基准中选择 相近的类型作为计算机的计算速度。 2.4 执行时间预测算法 执行时间预测算法 我们根据前面的技术设计一个完整的性能预测算法。该算 法开始于一个先前的工作量
11、观测值集 ),( 1 n i o iik XA = ，和CPU 利用率观测值集 )( 1, n i o kji= 。给定观测值集，输入数据和计算 节点的计算速度。完整的执行时间预测的伪代码如下： 给定应用A及其输入数据 21p xxxX?=和应用类型做： (1)使用公式(3)预测任务A的工作量 p n1+ ； (2)对网格系统中的每一个计算节点i做： (a)根据任务A的算法类型获取计算节点i的计算速度v； (b)使用公式(4)预测计算节点i的平均CPU利用率 p Ain, 1+ ； (c)使用公式(1)预测任务A的在节点i上的执行时间 p n T 1+; (3)将以上的执行时间预测值应用到一个
12、具体的调度算法， 调度算法将返回一个用于执行任务A的计算节点j； (4)在节点j上执行任务A, 并测量执行时间Tj和CPU时间 TjCPU; (5)用 jjcpu o Ajn TT/ , 1 = + 计算观测平均值 o Ajn, 1+ ； (6)用 o Ajnj o n vT , 11+ =计算任务A的观测工作量 o n 1+ ； (7)将),( 11 o nn XA + 和 o Ajn, 1+ 添加到先前的观测数据集； (8)n=n+1。 对该算法，每执行任务一次，就有一个新的观测值被添加 到先前的观测数据集中；因此预测的质量将随观测数据的增加 而得到改善。而初始观测数据集可在开发、测试和调
13、试应用时 获得。 3 实 实 验验 我们的异构分布计算实验床由多台计算机通过一个100M 的交换机进行互连。各机器配置如表1。我们开发了一个基于 ProActive的网格网络性能监测和任务调度器5。我们将本文提 出的性能预测算法集成到该监控和调度器中进行实验。 表 1 计算节点配置, 主频单位 Hz 机器号0 1 2 3 4 CPU P4 2.4GP4 2.4G 赛扬 2G 赛扬 2G赛扬 367M 内存 1024M512M 512M 256M 32M 用于测试性能预测和任务调度的应用程序是计算值的串 行程序CPI，它有一个输入参数E，E-1是控制计算结果所必须 的精度。我们在实验床上实验20
14、次。对实验结果进行统计，执 行时间预测的最大误差是125，平均误差是19.6，而误差 比较大的是输入参数第一次出现的情况， 随着实验次数的增加， 观测值也增加，这时候实验误差越来也小。 4 结束语 结束语 本文中，我们提出了一个异构分布计算环境下串行程序的 执行时间预测方法，这种方法通过结合历史统计数据、工作量 模型和机器的计算速度预测应用的执行时间，初步的试验表明 这种方法简单有效。进一步的研究工作是研究预测并行程序的 执行时间以及应用到调度系统中。 参 考 文 献 参 考 文 献 1 G.R. Nudd, D.J. Kerbyson, E. Papaefstathiou, S.C. Per
15、ry, J.S. Harper, D.V. Wilcox, PACE a toolset for the performance prediction of parallel and distributed systems, International Journal of High Performance Computing Applications, 2000,14(3): 228251. 2 J.-U. In, A. Arbree, P. Avery, R. Cavanaugh, S. Katageri, S.Ranka, SPHINX: a scheduling middleware
16、for data intensive applications on a grid, In: Proc of Computing in High Energy Physics, Interlaken, Switzerland, September, 2004. 3 M.A. Iverson, F. Ozguner, L.C. Potter, Statistical prediction of task execution times through analytic benchmarking for scheduling in a heterogeneous environment, IEEE Transactions on Computers, 1999,48(12): 13741379. 4 BYTEmark benchmark,
