(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210424807.2 (22)申请日 2022.04.21 (71)申请人 南京大学 地址 210023 江苏省南京市栖霞区仙林大 道163号 (72)发明人 周明贤　钱柱中　 (74)专利代理 机构 南京泉为知识产权代理事务 所(特殊普通 合伙) 32408 专利代理师 许丹丹 (51)Int.Cl. G06F 9/455(2006.01) G06F 9/50(2006.01) (54)发明名称 一种面向大数据处理的动态缓存替换方法 及设备 (57)摘要 本发明公开了一种面向大数据处理的动态 缓存替换方法及设备， 方法包括： 将大数据处理 应用抽象成有向无环图G＝(V,E)， 节点集合V表 示大数据处理应用中计算的数据， 边集合E表示 数据间的依 赖关系； 基于有向无环图G＝(V,E)中 包含的数据， 以最小化大数据处理应用的整体执 行时间为目标建立缓存替换问题数学模型， 模型 决策每个时刻t的待缓存数据； 基于大数据处理 特征简化 缓存替换问题； 基于动态 规划思想求解 简化后的缓存替换问题。 本发明实现了动态适配 数据处理过程中的数据访问模式的缓存替换， 能 够提高内存使用效率， 大幅降低大数据处理应用 的执行时间。 权利要求书2页 说明书11页 附图2页 CN 114691302 A 2022.07.01 CN 114691302 A 1.一种面向大 数据处理应用的动态缓存替换 方法， 其特 征在于， 包括以下步骤： (1)将大数据处理应用抽象成有向无环图G＝(V,E)， 其 中节点集合V的每个节点表示大 数据处理应用的数据， 集合V中的任一元素v包含两项属性： 数据占用内存空间sv和计算该 数据所需时间cv； 边集合E的每条边＜u,v＞表示大数据处理应用中数据v的计算依赖于数 据u； (2)基于有向无环图G＝(V,E)以及 大数据处理应用、 作业、 阶段、 数据之间的层次关系， 获取大数据处理应用中第i个执行的作业Ji的执行时延， 表述为f(Si,j,CS)， 表示缓存数据 集合CS情况 下， 作业Ji中阶段Si,j计算完成的时刻与 作业Ji开始执行时刻的差值； (3)以最小化大数据处理应用的整体执行时间为目标建立缓存替换问题数学模型， 缓 存替换问题P1被表述为在每个数据计算完成的时刻t决策存入缓存空间的数据集合CSnew,t， 以最小化该应用自第pt个作业起后续作业的总体完成时间； (4)求解缓存替换问题P1， 获得动态缓存替换 策略。 2.根据权利要求1所述的动态缓存替换方法， 其特征在于， 所述步骤(2)中， 所述层次关 系为： 大数据 处理应用由多个串行执行 的大数据处理作业组成， 大数据 处理作业包含多个 串行或并行执行的大数据处理阶段， 大数据处理阶段包含多个串 行或并行计算的抽象数据 集。 3.根据权利要求1所述的动态缓存替换方法， 其特征在于， 所述步骤(2)中， f(Si,j,CS) 通过以下 方法计算： 其中， Si,j表示应用中第i个作业的第j个阶段， xi,j,k表示阶段Si,j中第k个计算的抽象数 据集， Ni,j表示阶段Si,j中的抽象数据集数量， D(Si,j)表示阶段Si,j在作业Si中依赖的阶段组 成的集合， g(Si,j,x,CS)表示阶段Si,j在缓存数据集合CS下的执行时延等于阶段Si,j中最终 计算数据 计算完成的时刻与阶段Si,j开始执行时刻的差值， 其计算方法如下： 其中c(x,Si,j)表示在阶段Si,j中计算数据x所需时间， P(x,Si,j)表示数据x在阶段Si,j中 依赖的数据组成的集 合。 4.根据权利要求1所述的动态缓存替换方法， 其特征在于， 所述步骤(3)中， 缓存替换问 题P1表述为： P1： s.t.1≤pt≤|J|, 其中， CSold,t表示缓存空间在时刻t未存入xt前的已缓存数据集合， CSnew,t表示缓存空间 在时刻t存入xt后的已缓存数据集合， xt表示在时刻t被计算完毕的数据， 表示应用中所权　利　要　求　书 1/2 页 2 CN 114691302 A 2有数据计算完毕的时间集合， pt表示在时刻t执行的作业的下标， L表示缓存空间的总内存 上限， |J|表示应用中的作业数量。 5.根据权利要求1所述的动态缓存替换方法， 其特征在于， 所述步骤(4)中， 求解缓存替 换问题P1包括： 基于大数据处理特征简化缓存替 换问题P1， 并基于动态规划思 想求解简化后 的缓存替换问题。 6.根据权利要求5所述的动态缓存替换方法， 其特征在于， 所述基于大数据处理特征简 化缓存替换问题P1包括： 将应用中每个作业的所有阶段替换为 “作业关键路径 ”， 数据处理阶段的执行模式从并 行变为串行， 问题P1被简化为问题P2， 其中“作业关键路径 ”被定义为 该作业中执行时间最长 的阶段计算链； 将每个阶段中计算的抽象数据集替换为 “热点访问数据 ”， 数据处理阶段中数据计算模 式由并行变为串行， 问题P2被简化为问题P3， 其中“热点访问数据 ”被定义为应用抽象而成的 有向无环图中出度大于1的节点所表示的抽象数据集； 将每个数据处理阶段中的 “热点访问数据 ”替换为“阶段代表性计算 ”的执行结果， 问题 P3被简化为问题P4， 问题P4与0‑1背包问题等价， 其中 “阶段代表性计算 ”为数据处理阶段中 最终计算的数据所表示的数据处 理算子。 7.根据权利要求6所述的动态缓存替换方法， 其特征在于， 所述基于动态规划思想求解 简化后的缓存替换问题包括： 基于问题简化思想的预处理： 接收参数作业集合J、 在t时刻缓存空间中已有的数据 CSold,t和在t时刻待加入缓存空间的数据xt， 通过计算 “作业关键路径 ”、 分析“热点访问数 据”和统计“阶段代表 性计算”及其缓存收益， 返回 “阶段代表 性数据集合 ”x'和“阶段代表 性 数据”的缓存收益R RT； 基于动态规划思想的缓存替换： 根据预处理返回的 “阶段代表性数据集合 ”x'和“阶段 代表性数据”的缓存收益RRT， 同时结合 缓存空间的内存上限L作为输入， 随着对缓存空间的 内存上限L的每个值和 “阶段代表性数据 ”集合x'中每个元素的遍历， 通过动态规划将缓存 替换问题分解 为多个子问题， 从而得到问题P4的最优缓存决策CSnew,t。 8.根据权利要求7所述的动态缓存替换方法， 其特征在于， 在缓存空间的内存上限L与 每个数据x所占用的内存sx为自然数时， 该基于动态规划思想 的缓存替换算法的结果为最 优缓存决策。 9.一种计算机设备， 其特 征在于， 包括： 一个或多个处 理器； 存储器； 以及一个或多个程序， 其中所述一个或多个程序被存储在所述存储器中， 并且被配置 成由所述一个处理器执行， 所述程序被处理器执行时实现如权利要求1 ‑8中的任一项所述 方法的步骤。 10.一种计算机可读存储介质， 其上存储有一个或多个计算机程序， 其特征在于， 当程 序被处理器执行时实现如权利要求1 ‑8中的任一项所述方法的步骤。权　利　要　求　书 2/2 页 3 CN 114691302 A 3