云环境下科学工作流的两阶段数据放置与任务调度策略

三、科学工作流形式化描述和问题分析
• 3.1 相关模型和符号定义
★定义1 数据中心设为
表示编号为i数据中心, capi表示数据中心的计算能力，并用执行同一任务 所需的时间的倒数来量化表示，并假设该值保持不变；
csi表示dci的存储空间大小；
λ ini表示在科学工作流建立阶段，数据中心可以使用的存储空间的比例。 因为科学工作流执行过程中产生的中间数据有可能规模庞大，因此在原始 数据分配阶段要留有一定的空间来存储中间数据，所以0＜λ ini＜1。 λ ini是一个经验值，它的大小取决于科学工作流的性质。
引言
本文的贡献主要表现在以下几个方面：
在科学工作流建立阶段，提出了基于数据依赖的初始化数据布局方法，充分 挖掘数据相关性，使得数据布局尽可能的符合使用规则，同一个任务所需数 据集最大规模地聚集在一个数据中心。 在科学工作流运行阶段，提出一种相应的任务调度策略，将任务调度到所需 数据集规模最大的数据中心上，减少数据中心之间的数据传输量，加快科学 工作流执行速度。
★图１（ｂ）是按照文献［１１］（杨耘方 案）中的数据放置策略对产生的中间数据 集｛d６｝进行放置．因为｛d６｝和｛d １，d２｝同时被两个任务｛t２，t３｝使 用，｛d６｝和｛d３，d４＿f｝同时被任 务｛t４｝使用，所以｛d６｝产生后放置 在dc１上，科学工作流总的数据移动次数 是2次．
★图１（ｃ）使用的数据放置策略则 将｛d６｝放在dc２上，科学工作流 总的数据移动次数是５次。
五、结论与展望
★本文首先对科学工作流在云平台上的执行过程做出了分析，指 出了多个数据中心之间的数据传输开销是制约科学工作流执行 性能的一个瓶颈，并在此基础上提出了一种基于相关度的数据 放置策略，该策略综合考虑数据相关、数据集大小、固定数据 集比例及数据中心计算能力。通过与其它数据放置策略进行实 验对比，结果表明这种数据放置策略可以有效提升科学工作流 的执行效率，减少跨数据中心之间的数据传输流量。
（4）数据中心的计算能力、存储能力对科学工作流的影响．由于各个数据中心隶属 于不同的组织机构，其计算能力、存储能力可能差异较大。合理的数据放置策略也要 也要将这两个因素考虑到，即在存储空间足够的前提下，向计算能力强的数据中心放 置尽量多的数据集，以加快科学工作流的执行速度。
★由于数据移动开销对科学工作流性能影响较大，因此合理的数据放置策略 应该努力减少数据移动量，本文针对这种情况提出了一种基于相关度的数 据放置策略，该策略综合考虑了数据相关度（即数据之间被相同任务使用 的多少）、数据大小、固定数据集、数据中心的计算能力和存储能力，有 效提升了科学工作流的执行效率。
• 如图２所示，在科学工作 流建立阶段需要对所有的 原始数据进行预分配，其 流程大致如下:
• 第1步（语句1～5）算法首 先将所有的原始数据分为 两类，固定数据集FD和非 固定数据集NFD。
• 第2步（语句6～22） 判断 di的deplink中相关度最大的 数据集di是固定数据集还 是非固定数据集。 • 第3步（语句23～27） 对 DCwait中的数据集进行预
II.
III. 构造这样的系统往往需要付出异常昂贵的代价，申请访问这些系统也需 要复杂耗时的过程。云计算技术提供共享基础架构的方法，通过这种方 式，云计算中心可以提供高性能的计算资源和海量的存储资源，而且成 本低廉，使用简单。
引言
★科学工作流任务间存在较强的数据依赖关系，其执行往往需要频繁对跨数 据中心的数据集进行传输和访问，不合理的数据放置和任务调度策略容易 导致数据中心间数据传输量和访问量过大： 增加用户使用云资源的费用，
★定义2 原始数据集设为DSini＝｛d1，d2，d3…｝


DSini表示在科学工作流建立时所存在的数据集，即所有原始输入。
中间数据集设为DSgen＝｛d1，d2，d3…｝ DSgen表示在科学工作流执行过程中所产生的数据集。

固定数据集和非固定数据集分别设为FD和NFD．FD表示必须放置在固定数据中心 的数据集，这是因为某些数据需要特定数据中心的特定设备才能处理，或者某些数据 具有私有性和产权性．NFD表示没有固定数据中心的数据集，这是相对FD而言。
★但如果考虑数据大小，比如｛d１＝１ＭＢ，d２＝１Ｍ Ｂ，d６＝３０ＭＢ｝，那么图１（ｂ）中数据移动次 数虽然是两次，但数据移动量是６０ＭＢ，而图１（ｃ） 的数据移动次数是５次，但数据移动量是３４ＭＢ，总 的数据移动量大幅减少．所以数据集大小对于科学工作 流的数据放置策略和任务调度有着很大影响。
★以上图为例，科学工作流的数据放置策略需要考虑以下几点：
从图１（ａ）中可以看出，｛ d1，d2｝ 同时被任务{ t1，t2，t3 ｝使用，｛ d3， d4_f，d6｝同时被任务｛t４｝使用， ｛d５｝被任务｛t５｝使用并且任务执 行完毕后会产生一个中间数据 ｛d ６｝．由于移动数据比调度任务代价更 大，即相比之下调度任务的开销几乎可 以忽略，所以需要将关系紧密的数据集 尽量放置到同一个数据中心．
在科学工作流建立阶段: 构建一个相关度矩阵。 通过BEA算法得到聚类矩阵。
通过该矩阵将所有数据集划分为K个集合。（每一个集合内部的数据集都是高内聚 的，集合之间的数据集则是低耦合）
科学工作流执行阶段，在考虑存储条件满足的情况下，新产生的数据集 被放置在与它相关度最大的数据中心上。 ★实验表明，该方法可以有效减少跨据中心之间的数据移动次数。但这种方 法并未考虑移动的数据大小，如果移动次数较少，但所移动的数据太大， 传输开销不一定降低，导致科学工作流的执行效率反而下降。
• 定义5 数据集相关度设为
count（Ti∩Tj）×min｛si，sj｝，di，dj∈NFD • depij＝ count（Ti∩Tj） ×si， count（Ti∩Tj） ×si ， 0， ★depij表示数据di和数据dj的相关度大小。 count（Ti∩Tj）表示共同使用di和dj的任务数量。 di∈NFD， dj∈FD di ∈FD, dj∈NFD di，dj∈ FD
根据数据依赖关系图在工作流建立阶段将关系紧密的数据集放置到同一个数 据中心，将关系松散的数据集放置在不同数据中心。 任务调度策略在运行阶段将任务调度到数据依赖最大的数据中心执行，并将 新产生数据集放置到相关度最高的数据中心。
★实验表明：本文提作流任务的并行执行效率，同时也节省了用户的云资源使用费用。
数据放置策略：它首先预先分配数据到执行任务的计算单元，这样可以加 快任务的执行速度，降低任务等待时间；然后动态地删除那些不会被后续 任务使用的数据，以减少存储开销。
这种策略只是保证了数据传输的可靠性和有效性，并没有考虑到云计算环 境下因为数据交互引起的跨数据中心之间的传输开销。
二、相关工作
★聚类矩阵的数据放置策略：由澳大利亚杨耘等人提出，用于多数据中心之 间数据集的放置。 该方法的数据放置策略分为两步，
严重影响了科学工作流的执行效率。 ★研究基于云环境的高效数据放置策略和任务调度策略对减少跨数据中心数 据传输量、提升科学工作流执行性能、减少用户费用等方面具有重要意义。
引言
★本文通过分析科学工作流数据集之间的依赖关系、数据集和数据中心之间 的相关度以及任务和数据中心之间的相关度，提出了一种云平台下基于相 关度的两阶段高效数据放置策略。
min{si,sj}表示选择数据集较小的数据集 depij与数据集大小有关。由定义４知，数据集di有一个属性deplink，此处定义为deplink （i）= ｛< di , depij >|j≠i｝，根据depij大小形成一个降序链表。
★定义6 预分配数据中心设为DCk，k＝1，2，…，m，假定DCk的存 储空间值为相应的dck存储空间大小。在科学工作流建立阶段，需要 先将原始数据集逻辑上分配到DCk，k＝1，2，…，m，然后按照 DCk→dck的映射原则，将逻辑上的分配方案在物理的数据中心上实 现。 ★定义7 待分配数据集集合设为DCwait。在科学工作流建立阶段，该 集合中存放的是与其它任何数据集相关度均为0的数据集；在科学工 作流运行阶段，该集合中存放在后续过程中需要分配的数据集。

deplink是一个链表。（ depij与数据集大小有关。由定义４知，数据集di有一个属性 deplink，此处定义为deplink （i）=｛< di , depij >|j≠i｝，根据depij大小形成一个降序 链表。）
• 3.2 实例分析与问题说明
★ 图１（a）给出了一个科学工作流 的例子，该科学工作流包含5个 子任务｛t1，t2，t3，t4，t5｝，5 个输入数据集｛d1，d2，d3， d4_f，d5｝和一个中间数据集 ｛d6｝，其中｛d4_f｝是dc2上的 固定数据集，不能移动。
针对任务执行过程中产生的中间数据集，本文利用数据集之间的关系，通过 量化计算将它们放置到合适的数据中心，使得后续的任务调度与执行能够快 速展开。
二、相关工作
★PEGASUS工作流 PEGASUS是由美国南加州大学网格技术中心开发出的一个开源的工作流映 射引擎，它的主要功能是将复杂抽象的科学工作流映射到分布式资源上， 它使用户从实际的运行环境中解放出来，而只需要考虑抽象层面上的工作 流表示问题。
主要内容
• 一、引言
• 二、相关工作
• 三、科学工作流形式化描述和问题分析 • 四、基于相关度的两阶段数据放置 • 五、结论与展望
引言
科学工作流系统通过对复杂 科研流程进行分解,并对各 步骤间的数据依赖关系进行 分析和组合,控制各步骤在 时间空间和资源等约束条件 下按照科学家指定的顺序完 成。
科学工作流是工作流技术 在科学研究方面的应用和 发展,它与传统的事务工作 流有着一定的相似性,但由 于科学工作流面向科学实 验,它是以数据为中心的。
云环境下优化科学工作流执行性能的 两阶段数据放置与任务调度策略
科学工作流建立阶段数据放置策略
摘要
云环境中跨数据中心科学工作流的高效执行通常面临数据交互量大的问 题。
本文给出基于相关度的两阶段高效数据放置策略和任务调度策略。
最终通过实验表明，该策略能有效减少跨数据中心科学工作流执行时的 数据传输量，从而能有效提升科学工作流的执行效率，并能减少资源的 租赁费用。
四、基于相关度的两阶段数据放置与任务调度策略
• 4.1 建立阶段数据放置策略
• 在科学工作流建立阶段，该策略对所有的原始输入数据集在逻辑上进行预分配，这样做可以优化数 据分配方案，防止前期出现不合理分配的情况。预分配主要从局部性考虑，使得子任务在调度后， 所需使用的数据集都尽量在本地数据中心上存储。
表示在科学工作流上运行的任务集，每一个任务执行都需要若干数据集作为输入。
★定义3 T＝｛t1，t2，t3…｝ ★定义4 di＝〈Ti，si，dci，fix＿flag，deplink〉
di表示科学工作流中编号为i的数据集。


Ti＝｛t1，t2，t3…｝表示使用di的任务集合；
si表示数据集的大小； dci表示di所对应的数据中心； fix＿flag为true表示di是固定数据，反之则为非固定数据；
（1）数据相关对科学工作流的影响。科学工作流运行中数据集和任务之间并不是一 对多或者多对一的关系，而是多对多的关系，即一个数据集可能会被多个任务同时使 用，一个任务也可能调用多个数据集。
（2）数据集大小对科学工作流的影响。
（3）固定数据集对科学工作流的影响。固定数据集对科学工作流的影响。因为固定 数据集只能放置在特定的数据中心，无法向外传输，一旦任务使用到固定数据集，该 任务一定会被调度到这个数据中心上执行。
引言
I. 在众多科学研究领域中，科学计算过程往往由成千上万个步骤构成，这 往往需要对TB甚至PB量级的数据进行分析和处理。在过去，科学家通常 使用简单的方法编排任务以及管理数据，但是这种方式不仅耗时而且容 易出错。 科学工作流系统开始受到关注并被用来进行自动化科学任务的编排、执 行、监控以及追踪。随着问题求解规模的增大，当今大型科学工作流通 常需要在复杂的分布式计算机系统上执行。