英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
2018年IEEE第20届高性能计算与通信国际会议；IEEE第16届智能城市国际会议；IEEE第4届国际数据科学与系统会议
基于分形的并行CPU和GPU应用性能预测
Rodrigo Escobar和Rajendra V.Boppana
美国圣安东尼奥德克萨斯大学计算机科学系
rodrigod.escobar@gmail.com，rajendra.boppana@utsa.edu
摘要 -对于并行应用程序运行时间的准确估计,可用于更好的作业调度和高性能计算资源的利用，应用程序代码微调，功耗和改进的响应时间。我们提出了一个使用分形理论来估计并行CPU和GPU应用程序运行时间的性能模型。分形模型适用于主要计算部分的运行时间可以由形如aNc多项式来表示的应用，其中N为代表输入大小的数字，a和c为常数。我们的方法只需要对目标应用程序进行一些小规模的运行，并对相应的运行时间进行分析，以预测较大输入时应用程序运行的情况。我们的方法避免了文献中提出的更复杂的方法，例如静态分析源代码或捕获和分析详细的执行跟踪日志。我们对21个著名的CPU和GPU并行科学应用的实验结果表明，该方法具有很好的预测精度，在大多数情况下误差小于12%。
关键词-性能建模、分形理论、并行应用、GPU应用
一、引言
传统上，大规模、高性能计算（HPC）科学应用程序运行在超级计算机的中央处理器（CPU）或集群上。然而，最近许多核心加速器，如图形处理单元（GPU），已被用于各种科学、数据库和成像应用中，以获得更高的性能。准确估计应用程序的运行时间有几个优点，例如，帮助用户估计所需的HPC资源，识别可微调以提高性能的代码部分，提高集群的总体负载平衡和吞吐量，并提高应用程序响应时间[1]。
为了描述和预测并行应用程序的运行时间，识别应用程序的主要计算阶段，预测每个阶段的运行时间，并为应用程序运行时间的总体预测聚合预测阶段的运行时间。（阶段的定义因不同的方法而异，范围从低级硬件事件模式的变化[2]，到整个函数声明的变化[3]，[4]，再到进程间通信边界的变化[5]。
先前预测所有应用程序性能的方法包括指令混合和静态代码分析[3]、应用程序的计算密集型代码片段框架的执行[6]、[7]、曲线拟合[3]、[1]和机器学习算法[8]、[9]。这些方法需要仔细检查源代码，生成合成代码、参考内核数据库的预构建、大量的机器学习算法的执行样本，以便能够构建模型，或者基于所涉及的过程构建精确的仿真模型，例如执行跟踪分析。
最近，我们提出了一种预测方法，该方法使用小规模（小输入）执行和统计分析，将以前构建的参考数据库中的每个应用程序阶段与科学内核相匹配，并将匹配的内核运行时作为应用程序阶段运行时的代理[4]。然而，在目标体系结构上查找一组合适的内核并建立它们的运行时数据库既麻烦又耗时。在本文中，我们使用小规模运行和分形模型来避免对内核数据库的需求，并以较低的开销预测并行应用程序的运行时间。
基于少量（5-6）小规模运行和回归模型（线性或高次多项式）预测应用程序运行时的大的输入可能会导致不确定的预测。例如，图1显示了当基于六个小输入尺寸构建的1到4次多项式模型用于估计COMD的并行应用LJFORCE阶段的较大输入尺寸的运行时得到的结果[10]。这种疯狂预测的原因，即使一个阶段的执行时间可以被建模为一个多项式，包括：（a）阶段运行时间可以由非整数幂项组成，以及（b）整个应用程序执行复杂度可能不是多项式。
在这项工作中，我们开发了一个分形模型来估计CPU和GPU并行应用程序的运行时间使用性能数据从几个小规模的应用程序执行。分形理论[11]已被用于建模和预测程序所经历的缓存未命中率、访问网络中的流量以及云中工作负载的激增等。我们提出的分形模型特别适用于计算CPU和GPU应用程序的运行时间，这些应用程序的主要计算阶段的运行时间可以用输入大小的多项式和一些常量来近似。此外，应用程序阶段的底层算法可能具有时间复杂性（n），其中是整数但不是算法因素（如位置、内存层次结构或共享资源争用）的影响可能会将其执行时间复杂性更改为大约（n）。我们的分形模型估计了实际的时间复杂性。例如，使用图1中使用的相同运行时间数据的模型预测
|
978-1-5386-6614-2/18/$31.00copy;2018 IEEE |
610 |
|
doi 10.1109/hpcc/smartcity/dss.2018.00111 |
|
（a）一次多项式拟合 （b）二次多项式拟合 （c）三次多项式拟合 （d）四次多项式拟合
图1：不同的最小二乘多项式适用于64核上COMD[10]的LJ力相位。与实验数据相对应，拟合线与仅使用前六个数据点建立的相应多项式模型相对应。·
通过预测实验评估我们的方法并行科学应用程序的运行时间，使用MPI在多个CPU核心和节点上运行，以及在通用图形处理单元（GPGPU或简称GPU）上运行的应用程序。我们使用6个著名的并行科学应用程序，在288个核心集群上执行，15个GPU应用程序来自流行的基准套件，在支持计算统一设备架构（CUDA）的GPU上执行，拥有3000多个核心。我们的实验结果表明，所提出的分形模型能够给出准确的预测，在大多数情况下，绝对误差小于12%，平均值为8.5%（中位数为8%）。
论文的其余部分组织如下：第二节介绍了我们基于分形的建模方法。第三节介绍了性能模型的应用与并行应用的预测。第四节介绍了CPU和GPU应用的实验结果。第五节介绍了先前关于性能预测的工作。第六节结束论文
二。运行时估计的分形模型
分形理论被广泛地应用于自相似现象的建模和预测，这些自相似现象在多个领域以不同的尺度重复出现。对于具有多项式时间复杂度的应用阶段，我们证明了自相似性的性质，并证明了分形理论可以根据一些小规模运行的执行时间来模拟这些阶段的运行时间。考虑具有多项式时间复杂性的主要计算阶段的应用程序。让n1，n2，hellip;，nl，对于某些整数l，是我们可以运行应用程序的输入大小。分别让T1、T2、hellip;、TL作为执行这些输入大小的阶段所用的时间。此外，让b1，b2，hellip;，bl是一组reals，以便ni=bin表示某个值n，nl=bl n是要预测运行时的目标输入大小。在这项工作中，我们使用术语多项式时间复杂度来具体地指运行时，对于输入大小n和一些常量a、c和v，可以建模为n c v。然而，我们忽略v，因为与多项式术语相比，它一般不会严重影响应用程序阶段的执行时间。因此
Ti = aNic, 1 le; i le; L. （1）
通过对（1）两边取对数，我们得到了
ln (Ti) = ln (a) c ln (biN ) , 1 le; i le; L. （2）
特别的，对于NL，我们有
ln(TL) = ln(a) c ln(bLN). (3)
为了进一步简化线性模型，输入大小可以用nl进行归一化。考虑下表中针对标准化输入大小ni/nl=bi/bl的观测运行时ti，并应用自然对数。
我们可以使用以下线性回归方程，将表中的值、第1列中的值建模为x值，第2列中的值建模为y值：
这是相位时间复杂度的分形方程，其中m是运行时复杂度的估计分形维数，d是带有y轴的分形模型的截距。
利用（4），我们得到，
因此，输入大小nl的应用程序阶段的运行时通过
我们还可以通过对上述方程的代数运算，用分形方程参数d和m来估计模型参数a和c。如果多项式时间复杂度的假设是有效的，并且实验确定的前几个输入尺寸的运行时间是准确的，那么分形方程（4）只需少量的小规模运行就可以得到。下一节将介绍小规模运行的选择和分形模型的应用。
611
图2：预测方法。
- 应用分形模型性能预测
我们预测应用程序运行时的方法包括三个步骤：1）主要计算功能的检测1（在本工作中称为阶段）占应用程序运行时的大部分，2）基于阶段的分形维数预测阶段的运行时，以及3）整个应用程序运行时的预测。这些步骤分别在第III-A、III-B和III-C节中详细描述。图2给出了我们方法中步骤的框图。
a.检测主要应用阶段
我们从使用k小规模输入大小运行目标应用程序开始性能预测。调优和分析实用程序（tau[12]）和nvprof[13]分别用于分析CPU和GPU应用程序的小规模执行。tau是一个具有分析和跟踪功能的工具包，支持多种编程语言。同样，nvprof是一种分析工具，它允许用户收集和查看CUDA应用程序的分析数据。这两个分析器都可以自动检测源代码，并生成有关函数运行时信息的概要文件和跟踪日志。跟踪日志往往是大而复杂的，它们的生成可能会带来很大的开销。配置文件日志包括有关调用函数的次数和执行过程中花费的时间的摘要信息。此外，nvprof还可以提供设备到主机（dtoh）和主机到设备（htod）数据复制时间的相关信息。在这种情况下，设备指的是GPU卡，而主机指的是CPU系统。当配置为在基本配置文件模式下工作时，tau引入的开销为1-2%，nvprof引入的开销约为2%。
（a）相位周期（smg2000 cpu app）（b）相位内部（lud gpu app）
图3：两个应用程序阶段所用执行时间的分数。该点表示该分数稳定的值。
我们从tau和nvprof生成的配置文件日志中读取每个函数的平均执行时间，并确定构成大多数应用程序运行时的函数。由于它们的重复性，科学应用程序通常将时间花在一组小的函数[3]、[14]中迭代。这种迭代行为，在机器学习算法中也很常见，是由于使用了模板代码和近似方法，这些方法将收敛测试作为它们的停止标准[14]。在我们用来评估方法的大多数应用程序中，超过70%的应用程序总时间花在一个或两个函数上。图4显示了在两个应用程序的主要阶段花费的时间百分比。
我们对每个应用程序运行几个小的输入大小，并获得在应用程序主要阶段花费的总执行时间的百分比。我们将n设置为输入大小，超过该大小时，这些百分比是稳定的。在我们的实验中，需要5到6次运行来确定n。熟悉目标应用程序的用户也可以提供一个起点，该起点可以减少确定n所需的执行次数。图3a和3b分别显示了CPU和GPU应用程序n的值。
一旦确定了n的值，应用程序将运行k（k是一个小整数）附加的小输入尺寸n i，1le;ile;k，其中每个n i的delta;大于其前一个小值delta;。在我们的实验中，大约五次运行足以获得主要阶段的准确预测时间。
为了预测大输入量nlgt;nk阶段的运行时间，我们首先利用K小规模执行过程中轮廓器收集的数据构造一组K二维数据点。每个数据点的计算如下：
K数据点构造完成后，采用线性回归法将直线y=m x d拟合到数据点上，斜率m是相位运行时复杂度的分形维数，x是数据集中的x坐标，d是直线与y轴的交点，ed是nL的预测运行时数。图5显示了CPU应用程序的一个阶段和GPU应用程序的一个阶段的数据点与行的匹配。
虽然拥有更多的数据点可能会导致更精确的运行时预测模型，但是我们只生成一些数据点以实现更快的预测。在我们的实验中，在大多数情况下，5到6次小规模运行导致了良好的预测精度。
（a）256个进程上的hpcg（CPU应用程序）（b）kmeans（GPU应用程序）
图4：两个应用程序的时间分布
C.总体预测
要预测整个应用程序运行时，我们需要预测在前面的步骤中没有标识为代表性阶段的应用程序部分的运行时。利用k小规模运行和线性回归期间在每个主要阶段花费的应用程序执行时间百分比，我们预测目标输入大小nl在每个阶段花费的时间百分比；我们还预测将在应用程序的所有非阶段部分花费的执行时间百分比f0。计算f0需要将外推的相位百分比标准化为100%。
虽然拥有更多的数据点可能会导致更精确的运行时预测模型，但是我们只生成一些数据点以实现更快的预测。在我们的实验中，大多数情况下，五到六次小规模运行导致了良好的预测精度。
如果在第p1、p2、hellip;、ph阶段花费的总执行时间的估计百分比分别为fp 1、fp 2、hellip;、fp h，并且它们的预测运行时间分别为tp 1、tp 2、hellip;、tp h和ft=f0 fp 1 fp 2 hellip; fp h，然后我们对整个应用程序运行时的预测由以下公式给出
我们使用6个并行科学CPU应用程序和15个GPU应用程序评估我们的方法。这些应用程序已用于先前的运行时预测研究[6]、[3]、[5
全文共20778字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[2326]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
