英语原文共 11 页
异构多核系统中dags的稳健资源分配
摘要 - 在这项研究中，我们考虑一个环境由基于多核的异构集群组成用于分析卫星图像的机器。 工作量涉及大型数据集，通常需要截止日期限制。 多个应用程序，每个应用程序由一个有向无环图（DAG），被分配给专用异构分布式计算系统。 每个顶点在DAG中表示需要执行的任务任务执行时间因机器而异。这项研究的目标是分配应用程序基于多核的并行系统以这样的方式申请在共同截止日期之前完成，以及它们的完成时间对于不确定性是有效的在执行时间。 我们定义了量化的度量在这种环境中的稳健性。我们设计，比较和评估尝试的两种资源分配启发式方法最大化稳健性。
1.导言
我们考虑异构计算（HC）系统基于用于分析卫星数据的多核芯片。分析中使用的数据处理应用程序通常需要对大型数据集进行计算，以及他们的执行可能需要完成截止日期。
多个应用程序，每个应用程序表示为定向任务的非循环图（DAG），将被分配给一个HC系统执行。 这项研究的目标是将任务分配给处理器，使所有应用程序在一个共同的截止日期之前完成，并且应用程序完成时间对于任务执行时间中的不确定性很强。 我们定义了一个衡量标准在这种情况下的稳健性，我们设计，比较和该研究得到了美国国家科学基金会CNS-0615170的资助和CNS-0905399，以及科罗拉多州立大学乔治T.Abell Endowment。
评估两次尝试的资源分配启发式算法最大化稳健性。
模拟环境用于比较和评估这些启发式是由类似的系统推动的在DigitalGlobeplusmn;和国家中心使用大气研究（NCAR）。 在这些系统中，接收并分发来自卫星的数据卫星数据处理HC系统中的存储单元，那里有：（a）异构硬盘（HD）访问率，（b）不同的计算能力跨计算节点，以及（c）不同的数据集大小。该卫星数据处理系统具有以下特征特点：（a）卫星数据的初始分配HDs由启发式决定，（b）有限每台机器都有RAM，（c）数据项有明确地分阶段并从RAM中删除，（d）某些任务可以使用并行化执行，并且（e）必须采用HD和RAM之间的传输时间考虑到了。 模拟环境对此进行建模HC系统和应用程序。
每个应用程序仅需要总数的子集从卫星下载的数据集合。此环境中的资源分配需要两者选择系统内的位置来存储每个位置卫星数据项和计算节点的映射任务执行。 所有应用及其所需的卫星数据项在卫星收集之前是已知的数据，所以这是静态资源分配的一个实例
问题[1]。 一般映射问题是NP完全[6]，[8]，[11];因此，需要启发式算法以在合理的时间内获得接近最优的分配
。
我们的贡献是：（a）模型和模拟一个复杂的基于多核的数据处理环境执行数据密集型应用程序，（b）健壮性此环境的度量标准，以及（c）资源分配启发式使用此度量标准最大化稳健性。
在下一节中，我们将描述问题声明。 第三节中定义了两种新的启发式方法。相关工作在第IV节中讨论。 第五节和VI分别提供结果和结论。
- 问题陈述
- 系统模型
在这种环境中资源分配的目标是在共同的截止日期之前完成所有申请（Delta;）。 让appk成为k申请。 每个appk都是分为Tk任务，由DAG表示。 在里面DAG，进入任务仅需要卫星数据和退出任务产生必须存储在HD上的最终结果。
任务可能需要两个卫星数据集，表示SDi和其他任务产生的数据集，表示TDi 在计算节点alpha;内，数据集可以是位于RAM或HD中。 数据的位置表示计算节点alpha;内的集合（TD或SD）localpha;，即localpha;isin;{RAMalpha;，HDalpha;}。
该HC系统由N个计算节点组成，其中每个计算节点j都有专用存储（DSj），由RAMj和HDj组成。 每个计算节点还有一到八个处理单元（PEs），并且每个PE可以一次只执行一个任务（即，没有多任务）。 每个节点都包含一个集合多核芯片。 计算节点内的PEs很好，但是假设跨计算节点PEs是异质的。 每个计算节点j具有Vj PE哪里的xth PE表示为P Ej,x(1 le; x le; nu;j ),所有计算节点上的PEs总数为M (M =PNj=1 nu;j )。 计算的组成节点j如图1所示。
图1.在该图中，示出了计算节点j的组成
在每个计算节点中，RAM存储空间是有限，可能无法存储所有需要的数据同时设定; 但是，假设每个HD大到足以存储分配给的任何SD和TD它。 如果要释放RAM中的TD，但稍后需要作为任务的输入，必须将其复制到HD。因为所有SD最初存储在HD上，SD不会需要在被覆盖之前保存到HD内存。
任务所需的所有输入数据集必须是在任务可以开始执行之前在本地RAM中，和必须保留在RAM中，直到执行完成。RAM中的存储空间，用于输出任务在开始执行之前必须在本地保留。 在在该系统中，同一计算节点上的所有PE共享专用存储和网络访问。 访问的时间假设PE的本地RAM可以忽略不计; 但是HD访问不是，并且对于读取或写入是不同的。
用于本研究的网络拓扑很高性能并行接口（HiPPI）交叉开关（图2）。 每个计算节点可以同时进行一次发送和接收一个数据集，但可能不会广播。 来自一个计算的数据传输速率节点到另一个取决于数据在两者中的位置源和目的地，即RAM或HD。
图2.在该图中，示出了HiPPI网络的图示。
因为数据可能有两个位置存储和传输中涉及的两个计算节点，有四个案例。在第一种情况下，我们希望转移从源计算节点上的RAM到RAM的数据目标计算节点。此转让仅限通过网络带宽（所有计算节点都相同）因为RAM的带宽总是更大。在第二种情况，来自HD的数据传输速率在源计算节点上到目标上的RAM计算节点受网络中较小的网络限制带宽和源HD的读取带宽。在第三种情况，来自RAM的数据传输速率在目标计算上将计算节点源到HD节点限于较小的网络带宽以及目的地HD的写入带宽。在里面第四种情况，从HD上传输数据的速率源计算节点到目的地的HD计算节点受网络中较小的网络限制带宽，来自源HD的读取带宽以及目标上HD的写入带宽计算节点。
对于每个任务ti，我们假设已经提供了在每个计算节点j上计算的估计时间，表示为ET C（i，j），可能是根据过去的任务确定的执行时间，这是一个常见的假设（例如，[5]，[7]，[9]，[12]，[13]，[19]，[22]）。 这个目标研究是将任务分配给PE，以便意外估计任务计算时间的增加不会导致完成所有申请所需的总时间（完工时间）超过Delta;。 有关示例，请参见图3DAG的资源分配。
图3.该图显示了DAG的图。 PE显示在计算节点1（P E1,1）中执行需要SD1的t1计算节点3.在这种情况下，计算节点1上的T D3和T D7需要为t6发送到计算节点2。 t6的结果必须是存储在系统的HD中，并且存储结果的时间必须在计算完工时间时要考虑。
任务的子集旨在可分解用于在单个计算节点内并行执行。每个可分解的任务都被赋予一个除数值表明任务是如何适应并行处理，ETCparallel（i，j）=ETC（i，j）除数。 任务分为良好的并行任务和糟糕的并行任务。 除数我们在模拟中使用的值如表I所示。
表I 表显示并行任务的分区
- 稳健性
如果资源分配满足给定的要求，则资源分配是健性能标准，尽管出现意外扰动，仍能保持这种性能[4]（例如，[16]，[20]）。定量比较之间的稳健性不同的可能资源分配，三个问题关于稳健性必须回答[3] :( 1）系统的行为是什么让它变得稳健？我们的系统是如果所有应用程序在共同之前完成截止日期∆.（2）系统的稳健性存在哪些不确定性反对？不确定性是之间的关系估计每个任务的执行时间和每个任务的实际数据相关执行时间。 （3）量化，系统究竟有多强大？坚固性给定资源分配是最小的共同点所有任务执行时间的百分比增加（rho;）导致完工时间等于截止日期∆.因此，本研究的稳健性度量最大化。通常，最小化完工时间不会最大化稳健性。示出了资源分配的示例在图4中。
图4.在该图中，示出了资源分配的示例。 （a）中任务的每个执行时间增加50％结果如（b）所示。 注意，通信时间不会增加，并且（b）（等于Delta;）的完工时间远小于（a）的完工时间增加了50％。 在（a）中，完工时间PE为P E3,1。 在所有任务执行时间增加50％后，P E3,1不再存在完工时间PE。 此示例直观地显示了在具有任务间的环境中，完工时间不是衡量稳健性的良好指标通讯。
C.绩效指标
仅通过使用，无法计算稳健性估计资源分配的完工时间因为计算机间节点引入的复杂性数据传输，即稳健性与公正不同通过rho;增加完工时间。
在实际系统中，所有任务的执行时间都将是不会增加相同的百分比。 但是，rho;可以用作一个合适的稳健性度量这种环境 - 它可以被视为最坏的情况保证。
这项研究的绩效指标是稳健性rho;。 由于环境的复杂性，它很难确定一个封闭形式的表达式资源分配的稳健性。 因此，一个迭代使用搜索程序。
我们将执行时间增加了一个百分点lambda;%来定义完工时间作为完工时间lambda;。 计算lambda;的一个过程，使得完工时间lambda; = ∆, 是乘以所有的估计任务执行时间为1 lambda;.。 然后，使用二进制搜索lambda;的值，找到最接近的lambda;的值。 二进制的起始上限值搜索是lambda;（ULlambda;）的上限。
用于二分搜索的ULlambda;计算如下。对于每个PE，将所分配任务的ETC值相加那个PE。 设mu;是这些总和的最大值在所有PE中。 二进制搜索的起始值是：
（1）
二进制搜索将在1％和ULlambda;之间。 对于在二进制搜索的每次迭代中，我们计算出完工（包括沟通），直到找到lambda;的值（最接近的百分比）给出了makepanlambda;=Delta;。
- 启发式算法
- 动态可用任务关键路径（DATCP）
DATCP启发式（基于Dy namic Critical Path（DCP）[15]的概念）使用了与应用程序无法处理的无限数量的处理器以比其关键路径长度更快的速度执行。没有失去一般性，假设所有应用程序DAG的所有入口节点都具有共同的前驱这是伪顶点条目任务tentry。同样的，假设有一个唯一的退出节点texit。 计算关键路径是一个开始的递归过程用texit和tentry结束。 每个任务计算它执行到texit的时间然后传递这个时间值它的前身任务。 任务的执行时间是使用所有计算中的平均值计算节点。 我们将ti的平均执行时间定义为AET（ti），并按如下方式计算：
（2）
为了估计传输时间，使用了两个平均带宽：（a）平均带宽时间HD是所有计算的平均读取带宽节点，以及（b）使用网络传输带估计通过网络发送的TD。该关键路径计算方法的伪代码是在图5中。
|
（1）让ti = texit （2）计算SD估计的传输时间为ti（SD的大小除以平均带宽时间HD）。 （3）计算平均任务执行时间（AET（ti））。 （4）计算T D估计到后继节点的传输时间（TD的大小除以网络传输带宽）。 （5）确定从任何后继（子）节点到texit（maxtime）的最长时间。 （6）关键路径值是T D和SD数据传输时间，maxtime和AET（ti）之和。 （7）选择另一个任务（其后继者具有计算的关键路径值）并转到步骤（2）直到全部任务处理完毕。 |
图5.用于计算DATCP启发式关键路径的过程
启发式的下一步确定了列表可用任务，即进入任务或任务前辈已被映射。 可用的任务然后将最大关键路径时间映射到计算节点，最大化稳健性值rho;。然后从mappable列表中删除该任务任务和过程重复进行，直到所有任务都完成映射。 图6中列出了该算法的伪代码。如果两个可能的分配具有相同的稳健性，然后DATCP选择计算中的PE大多数PE具有相同鲁棒性的节点。
（2）动态创建可用于映射的所有任务的列表。 （3）从可用任务列表中确定具有最长关键路径的任务。 （4）对于（3）中确定的任务ti， （a）对于每个计算节点j中的每个PE k，计算P Ej的稳健性，如果ti被映射到k则为k节点j（有关SD放置的详细信息，请参见第III-A3节）。 （b）找到具有最大数量的最大稳健性值PE的计算节点j（这是可能的 其他PE具有相同的稳健性值）。 该计算节点表示为nodemax。 （c）安排从先前任务和卫星数据传输到nodemax的通信转移。 （d）将任务映射到具有最大稳健性的PE（或PE）（详见第III-A2节）。 （e）从列表中删除任务ti。 （5）重复步骤（2） - （4），直到映射完所有任务。 |
图6.用于生成资源分配的DATCP启发式过程。
- 内存管理：启发式调度数据集按资源分配的要求进行传输。当考虑任务调度时，可用RAM中的空间决定了是否完成了任务它需要的输入数据可以立即存储在RAM中，即，RAM中是否有足够的空间。 如果还不够空间，启发式检查任务的输入数据集合可以移动到内存中并安排它开始当时执行。
如果从计算节点传输数据集我是一个计算节点j，并且有空间可用在RAMj中，然后它直接转移到RAMj中。如果RAMj中没有空间，则数据为搬到了HDj。 在评估哪些数据集时可以从RAM中删除，算法选择数据集目前尚未使用，并且使用最少剩余的任务需要它们（TD被复制到HD以避免数据丢失）。
2）可并行化的任务：研究了两种方法对于DATCP启发式的图6中的步骤4（d）。 对于第一种方法，没有使用并行化。 为了第二种方法（“最大”方法），启发式总是将任务并行化到计算
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
