云环境下中间数据集存储问题优化算法研究

发布时间：2020-06-01 14:54

【摘要】：随着科学研究过程越来越复杂,科学计算的步骤越来越繁多,因此云计算平台上运行科学工作流越来越受欢迎。然而,科学工作流在云计算平台上运行伴随着云环境下中间数据集存储问题,该问题本质是代价最小化。科学工作流运行过程中会产生大量含有对于科学家们来说至关重要信息的中间数据集,因此,如何处理这些中间数据集变得尤为重要。云计算平台提供了处理这些中间数据集所需的存储资源、计算资源和宽带资源。然而,用户在享受这些云服务的同时,还需付出存储代价、计算代价和传递代价,因此,怎样让用户高效享受云服务的同时付出较小代价显得尤为重要。目前,云环境下中间数据集存储问题的研究主要集中在以下三个方面:第一、云环境下中间数据集存储问题代价模型优化;第二、单云环境下线性数据流和非线性数据流存储问题算法研究;第三、多云条件下线性数据流和非线性数据流存储问题算法研究。本文研究的主要内容是云环境下线性数据流存储问题代价最小化算法时间效率优化和云环境下非线性数据流中间数据集存储问题代价模型优化,具体如下:(1)阐述云环境下中间数据集存储问题优化算法的理论基础,包括问题定义、代价模型以及对应的中间数据集存储算法,并指出算法存在的问题和研究重点;(2)采用动态规划思想优化多云条件下线性数据流存储问题算法,将时间复杂度由O(m~4n~3)改进为O(m~3n~3);(3)针对多云条件下中间数据集存储问题存在代价模型表达不够全面的问题,通过研读大量参考资料,将数据集的使用频率、用户数据访问延迟容忍度、传递代价有效组合,得出该问题新代价模型,新模型定义数据集的使用频率为更能反映用户的实际需求的高峰期数据集使用频率;(4)在新代价模型条件下,使用贪心策略,提出一个新算法并通过实验模拟结果对算法进行分析,实验结果表明贪心策略对新的代价模型是可行的。论文最后总结本文的主要工作,并且对下一阶段云环境下中间数据集存储问题算法的研究重点进行展望。
【图文】：

依赖图

传递构造

图 2.3 代价传递构造图定义 2.3-1：计算状态的中间数据集直接存储前驱集合是由离该数据集最近存储数据集组成，用 S-prior 集合表示。如图 2.1，d5的直接存储前驱集合为 S-prior(d5)={d1, d2}。定义 2.3-2：计算状态的中间数据集计算路径是由该数据集存储前驱集合中的数直接后继到该数据集的所有路径，，用 C-path(di)集合表示。如图 2.1，d5的计算路径有两条，即 C-path(d5)={{d3, d5}, {d4, d5}}。定义 2.3-3：通过数据集的计算路径，根据公式(2.2)计算该数据集的计算代价：( ) ( )ixdjαCpathdidαddxdjcomputatio n_costd + ∈ ∈∧≠ = (其中，x(d)表示数据集 d 的计算代价，α表示 di的某个计算路径。则根据公式(2.2)可计算出 d5的计算代价，即：Computation_cost(d5)=x(d3)+x(d4)+x(d5)定义 2.3-4：单云条件下代价模型，如公式(2.3)所示：
【学位授予单位】：中南民族大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP393.09

【参考文献】