一种基于重用代价的混合缓存管理方法及计算机可读介质与流程

1.本发明属于电力系统及自动化领域，尤其涉及一种基于重用代价的混合缓存管理方法及计算机可读介质。


背景技术：

2.近年来，随着数据规模的激增以及对可扩展性大数据处理的需求，各种大数据框架在工业和研究领域都得到长足发展。而“大数据时代”不断增长的数据量给内存计算框架带来了巨大的压力，这些框架必须定期处理tb甚至pb的数据。spark混合缓存系统是将访问频繁的缓存块保持在dram缓存中，将访问不频繁的缓存块保持在nvm缓存中。而使用哪种指标来判断缓存块访问频繁便成了一个关键问题。所以，为了让需要频繁访存的缓存块可以获得更好的响应，同时最大限度减少缓存块迁移带来的性能开销，并在扩展了缓存总容量的同时达到较好的缓存i/o性能，需要设计两种缓存介质间的缓存块放置和迁移策略。
3.有向无环图预测了rdd的未来访问模式，因此相比于lru和lfu的历史访问信息，可以更有效的指导缓存块的放置和驱逐。现有许多工作都是基于有向无环图依赖关系提出缓存管理策略，如最小有效引用计数、最少组合引用计数和最大引用距离等指导缓存块的存取。然而这些研究都是spark平台在dram内存上运行时的缓存管理策略，没有研究将有向无环图信息用于混合内存场景下的spark缓存管理优化。通常，对于高速内存和低速内存构成混合内存系统来说，为了充分利用高速内存设备读写速度快和低速内存设备扩展大容量的优势，就要将频繁访问的数据放置在高速内存中以提高系统整体访存性能，降低低速内存读写性能差的缺陷。


技术实现要素：

4.为了解决上述技术问题，本发明提出了一种基于重用代价的混合缓存管理方法及计算机可读介质。
5.本发明方法的技术方案为一种基于重用代价的混合缓存管理方法，具体步骤如下：
6.步骤1：构建多节点spark执行有向无环图，每个节点在执行spark计算任务时，每个节点执行对应的每个读取目标缓存块的写入任务、执行对应的每个写入目标缓存块的读取任务；
7.步骤2：将所有节点对应的所有写入目标缓存块构建多个待写入目标缓存块，计算每个待写入目标缓存块的dram向nvm迁移的迁移代价；将所有节点对应的所有读取目标缓存块构建多个待读取目标缓存块，计算每个待读取目标缓存块的nvm向dram迁移的迁移代价；
8.步骤3：每个待写入目标缓存块根据对应的dram向nvm迁移的迁移代价决策dram向nvm迁移的任务；每个待读取目标缓存块根据对应的nvm向dram迁移的迁移代价决策nvm向dram迁移的任务；
9.作为优选，步骤1所述每个节点执行对应的每个读取目标缓存块的写入任务、执行对应的每个写入目标缓存块的读取任务，具体如下：
10.步骤1.1：若每个节点对应的每个写入目标缓存块需要存储或者迁移到dram空间时，每个节点对应的每个写入目标缓存块获取dram的可用的空闲空间大小；
11.每个节点对应的每个写入目标缓存块向dram发起每个节点对应的目标缓存块的缓存空间请求；
12.dram接收到缓存空间的请求后，检测dram空间中的空闲空间，若dram中空闲空间大于等于每个节点对应的每个写入目标缓存块的缓存空间请求则跳转至步骤1.3，否则跳转步骤1.2；
13.步骤1.2：进行dram中占用空间的缓存块筛选；
14.dram中占用空间中每个缓存块结合有向无环图进行预测得到dram中占用空间中每个缓存块的未来重用次数；
15.将每个节点对应的每个写入目标缓存块结合有向无环图进行预测得到每个节点对应的目标缓存块的未来重用次数；
16.将dram中占用空间中每个缓存块的未来重用次数与每个节点对应的每个写入目标缓存块的未来重用次数进行比较，若dram中占用空间中缓存块的未来重用次数小于每个节点对应的每个写入目标缓存块的未来重用次数，则将dram中占用空间中对应的缓存块的空间放入释放队列；
17.重复执行步骤1.2直至dram中预计空闲空间大于等于每个节点对应的目标缓存块的缓存空间请求，则将所有释放队列中的缓存块迁移至nvm，并跳转至步骤1.3，若步骤1.2无法清理出足够的缓存空间，则请求将每个节点对应的每个写入目标缓存块分配至nvm；
18.步骤1.3：dram根据每个节点对应的每个写入目标缓存块的缓存空间请求，使用dram中的空闲空间进行每个节点对应的每个写入目标缓存块的缓存块分配；
19.步骤1.4：每个节点对应的每个读取目标缓存块接收读取请求用于计算时，若每个节点对应的每个读取目标缓存块存在在dram中，直接读取dram中的缓存块，若不在，则跳转至步骤1.8；
20.nvm接收到缓存空间的请求后，检测nvm空间中的空闲空间，若nvm中空闲空间大于等于每个节点对应的每个读取目标缓存块的缓存空间请求则跳转至步骤1.6，否则跳转步骤1.5；
21.步骤1.5：若每个节点对应的每个写入目标缓存块存储于nvm，每个节点对应的每个写入目标缓存块获取nvm的空闲空间的缓存块；
22.每个节点对应的每个写入目标缓存块向nvm发起每个节点对应的每个写入目标缓存块的缓存空间请求；
23.nvm接收到缓存空间的请求后，检测缓存空间中空闲空间，若nvm中空闲空间大于等于每个节点对应的每个写入目标缓存块的缓存空间请求则跳转至步骤1.7，否则跳转步骤1.6；
24.步骤1.6：进行nvm中占用空间的缓存块筛选；
25.nvm中占用空间中每个缓存块结合有向无环图进行预测得到nvm中占用空间中每个缓存块的未来重用次数；
26.将每个节点对应的每个写入目标缓存块结合有向无环图进行预测得到每个节点对应的目标缓存块的未来重用次数；
27.将nvm中占用空间中每个缓存块的未来重用次数与每个节点对应的目标缓存块的未来重用次数进行比较，若nvm中占用空间中缓存块的未来重用次数小于每个节点对应的每个写入目标缓存块的未来重用次数，则将nvm中占用空间中对应的缓存块的空间放入释放队列；
28.重复执行步骤1.6直至nvm中预计空闲空间大于等于每个节点对应的每个写入目标缓存块的缓存空间请求，则将所有释放队列中的缓存块直接清除，并跳转至步骤1.7，若步骤1.6无法清理出足够的缓存空间，则清除每个节点对应的目标缓存块并结束该次分配；
29.步骤1.7：nvm根据每个节点对应的每个写入目标缓存块的缓存空间请求，使用nvm中的空闲空间进行每个节点对应的每个写入目标缓存块的缓存块分配；
30.步骤1.8：若每个节点对应的每个读取目标缓存块存在nvm中，则直接读取nvm中的缓存块，此时若dram中存在空闲空间或每个节点对应的每个读取目标缓存块的未来重用次数大于迁移阈值，则会触发缓存块从nvm缓存向dram缓存的迁移；若在nvm中搜索不到每个节点对应的每个读取目标缓存块，则需要重新计算出对应的每个读取目标缓存块；
31.作为优选，步骤2所述计算每个待写入目标缓存块的dram向nvm迁移的迁移代价，具体如下：
[0032][0033][0034]
其中，表示第k个待写入目标缓存块的dram向nvm迁移的迁移代价，表示第k个待写入目标缓存块在dram中的迁移方案的总访问时间代价，k表示待写入目标缓存块的数量，表示第k个待写入目标缓存块不进行迁移直接将在dram中的缓存块放置在nvm中的方案的总访问时间代价；
[0035][0036]
其中，rpmd表示dram中每mb数据的读时间，表示第k个待写入目标缓存块的大小，表示第k个待写入目标缓存块未来重用次数，rpmn表示nvm中每mb数据的读时间，表示dram缓存中未来重用次数最低的缓存块的空间大小，表示dram缓存中未来重用次数最低的缓存块的未来重用次数，wpmn表示nvm中每mb数据的写时间，epmd表示dram中每mb数据的清除时间，wpmd表示dram中每mb数据的写时间；
[0037][0038]
其中，rpmn表示nvm中每mb数据的读时间，表示第k个待写入目标缓存块的大小，表示第k个待写入目标缓存块未来重用次数，rpmd表示dram中每mb数据的读时间，
表示dram缓存中未来重用次数最低的缓存块的空间大小，表示dram缓存中未来重用次数最低的缓存块的未来重用次数，wpmn表示nvm中每mb数据的写时间；
[0039]
步骤2所述每个待读取目标缓存块的nvm向dram迁移的迁移代价，具体如下：
[0040][0041]
其中，表示第i个待读取目标缓存块的nvm向dram迁移的迁移代价，表示第i个待读取目标缓存块的在nvm中的迁移方案的总访问时间代价，n表示待写入目标缓存块的数量，表示第i个待读取目标缓存块不进行迁移直接在nvm中读取的方案的总访问时间代价；
[0042][0043]
其中，rpmd表示dram中每mb数据的读时间，表示第i个待读取目标缓存块的大小，表示第i个待读取目标缓存块的未来重用次数，rpmn表示nvm中每mb数据的读时间，表示nvm缓存中未来重用次数最低的缓存块的空间大小，分别表示nvm缓存中未来重用次数最低的缓存块的未来重用次数，wpmn表示nvm中每mb数据的写时间，epmd表示dram中每mb数据的清除时间，wpmd表示dram中每mb数据的写时间，epmn表示nvm中每mb数据的清除时间；
[0044][0045]
其中，rpmn表示nvm中每mb数据的读时间，表示第i个待读取目标缓存块的大小，表示第i个待读取目标缓存块的未来重用次数，rpmd表示dram中每mb数据的读时间，表示nvm缓存中未来重用次数最低的缓存块的空间大小，分别表示nvm缓存中未来重用次数最低的缓存块的未来重用次数；
[0046]
作为优选，步骤3所述每个待写入目标缓存块根据对应的dram向nvm迁移的迁移代价决策dram向nvm迁移的任务，具体如下：
[0047]
若migrationbenefit
toput
为正时，将对应的待写入迁移缓存块驱逐到nvm中，并更新所有缓存块的未来重用次数，发现未来重用次数为0的缓存块直接进行清除；
[0048]
步骤3所述每个待读取目标缓存块根据对应的nvm向dram迁移的迁移代价决策nvm向dram迁移的任务，具体如下：
[0049]
若migrationbenefit
toread
为正时，将dram中未来重用次数最低的缓存块驱逐到nvm中，然后将对应的需要迁移的缓存块从nvm迁移到dram中，并更新所有缓存块的未来重用次数，发现未来重用次数为0的缓存块直接进行清除。
[0050]
本发明还提供了一种计算机可读介质，所述计算机可读介质存储电子设备执行的
计算机程序，当所述计算机程序在电子设备上运行时，执行所述基于重用代价的混合缓存管理方法的步骤。
[0051]
采用上述方法后，本发明具有以下改进：
[0052]
能够将关键数据或频繁访问的数据维持在访问延迟低的高速存储设备dram中，可以有效提高应用程序的运行性能。另外，它还实现了从全局dag信息中获取缓存块的未来重用次数，并在运行时更新。它可以在不影响性能和缓存块迁移成本的同时，利用最小重用代价策略指导缓存块的放置和迁移操作，使得缓存块整体的重用代价最小，缓存系统的读写性能最高。
[0053]
本发明在dram缓存的性能提升和缓存块迁移成本之间进行权衡。将nvm缓存中的缓存块迁移到dram缓存可以提高该缓存块的访问性能，但是，nvm和dram之间迁移也会导致整体的访问延迟增加。于是，通过在迁移时选取稳定的迁移成本，可以使缓存块的整体重用代价最小，缓存系统的整体读写性能最高。
[0054]
本发明综合考虑缓存块的未来重用次数和混合缓存间的迁移代价，确保了频繁访问的缓存块被保存在dram缓存中并降低迁移开销，使缓存系统整体的重用代价最小，提升了整体性能。
[0055]
本发明在需要进行混合缓存之间的迁移时，通过缓存块的读写时间等信息计算迁移缓存块带来的性能收益，迁移收益为正时才进行缓存块的迁移，减少了缓存块迁移带来的性能开销。
[0056]
本发明最小重用代价方法从全局dag信息中获取rdd的未来重用次数，并在运行时更新。未来重用次数高的缓存块将被优先保存在dram缓存中，未来重用次数最低的缓存块将被驱逐或清理，确保了未来重用频繁的缓存块放置在高速缓存中。
附图说明
[0057]
图1：本发明实施例的方法流程图；
具体实施方式
[0058]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0059]
具体实施时，本发明技术方案提出的方法可由本领域技术人员采用计算机软件技术实现自动运行流程，实现方法的系统装置例如存储本发明技术方案相应计算机程序的计算机可读存储介质以及包括运行相应计算机程序的计算机设备，也应当在本发明的保护范围内。
[0060]
下面结合图1介绍本发明实施例的技术方案为一种基于重用代价的混合缓存管理方法，具体如下：
[0061]
参见图1，本发明实施例的方法流程图。
[0062]
步骤1：构建多节点spark执行有向无环图，每个节点在执行spark计算任务时，每个节点执行对应的每个读取目标缓存块的写入任务、执行对应的每个写入目标缓存块的读
取任务；
[0063]
步骤1所述每个节点执行对应的每个读取目标缓存块的写入任务、执行对应的每个写入目标缓存块的读取任务，具体如下：
[0064]
步骤1.1：若每个节点对应的每个写入目标缓存块需要存储或者迁移到dram空间时，每个节点对应的每个写入目标缓存块获取dram的可用的空闲空间大小；
[0065]
每个节点对应的每个写入目标缓存块向dram发起每个节点对应的目标缓存块的缓存空间请求；
[0066]
dram接收到缓存空间的请求后，检测dram空间中的空闲空间，若dram中空闲空间大于等于每个节点对应的每个写入目标缓存块的缓存空间请求则跳转至步骤1.3，否则跳转步骤1.2；
[0067]
步骤1.2：进行dram中占用空间的缓存块筛选；
[0068]
dram中占用空间中每个缓存块结合有向无环图进行预测得到dram中占用空间中每个缓存块的未来重用次数；
[0069]
将每个节点对应的每个写入目标缓存块结合有向无环图进行预测得到每个节点对应的目标缓存块的未来重用次数；
[0070]
将dram中占用空间中每个缓存块的未来重用次数与每个节点对应的每个写入目标缓存块的未来重用次数进行比较，若dram中占用空间中缓存块的未来重用次数小于每个节点对应的每个写入目标缓存块的未来重用次数，则将dram中占用空间中对应的缓存块的空间放入释放队列；
[0071]
重复执行步骤1.2直至dram中预计空闲空间大于等于每个节点对应的目标缓存块的缓存空间请求，则将所有释放队列中的缓存块迁移至nvm，并跳转至步骤1.3，若步骤1.2无法清理出足够的缓存空间，则请求将每个节点对应的每个写入目标缓存块分配至nvm；
[0072]
步骤1.3：dram根据每个节点对应的每个写入目标缓存块的缓存空间请求，使用dram中的空闲空间进行每个节点对应的每个写入目标缓存块的缓存块分配；
[0073]
步骤1.4：每个节点对应的每个读取目标缓存块接收读取请求用于计算时，若每个节点对应的每个读取目标缓存块存在在dram中，直接读取dram中的缓存块，若不在，则跳转至步骤1.8；
[0074]
nvm接收到缓存空间的请求后，检测nvm空间中的空闲空间，若nvm中空闲空间大于等于每个节点对应的每个读取目标缓存块的缓存空间请求则跳转至步骤1.6，否则跳转步骤1.5；
[0075]
步骤1.5：若每个节点对应的每个写入目标缓存块存储于nvm，每个节点对应的每个写入目标缓存块获取nvm的空闲空间的缓存块；
[0076]
每个节点对应的每个写入目标缓存块向nvm发起每个节点对应的每个写入目标缓存块的缓存空间请求；
[0077]
nvm接收到缓存空间的请求后，检测缓存空间中空闲空间，若nvm中空闲空间大于等于每个节点对应的每个写入目标缓存块的缓存空间请求则跳转至步骤1.7，否则跳转步骤1.6；
[0078]
步骤1.6：进行nvm中占用空间的缓存块筛选；
[0079]
nvm中占用空间中每个缓存块结合有向无环图进行预测得到nvm中占用空间中每
个缓存块的未来重用次数；
[0080]
将每个节点对应的每个写入目标缓存块结合有向无环图进行预测得到每个节点对应的目标缓存块的未来重用次数；
[0081]
将nvm中占用空间中每个缓存块的未来重用次数与每个节点对应的目标缓存块的未来重用次数进行比较，若nvm中占用空间中缓存块的未来重用次数小于每个节点对应的每个写入目标缓存块的未来重用次数，则将nvm中占用空间中对应的缓存块的空间放入释放队列；
[0082]
重复执行步骤1.6直至nvm中预计空闲空间大于等于每个节点对应的每个写入目标缓存块的缓存空间请求，则将所有释放队列中的缓存块直接清除，并跳转至步骤1.7，若步骤1.6无法清理出足够的缓存空间，则清除每个节点对应的目标缓存块并结束该次分配；
[0083]
步骤1.7：nvm根据每个节点对应的每个写入目标缓存块的缓存空间请求，使用nvm中的空闲空间进行每个节点对应的每个写入目标缓存块的缓存块分配；
[0084]
步骤1.8：若每个节点对应的每个读取目标缓存块存在nvm中，则直接读取nvm中的缓存块，此时若dram中存在空闲空间或每个节点对应的每个读取目标缓存块的未来重用次数大于迁移阈值，则会触发缓存块从nvm缓存向dram缓存的迁移；若在nvm中搜索不到每个节点对应的每个读取目标缓存块，则需要重新计算出对应的每个读取目标缓存块；
[0085]
步骤2：将所有节点对应的所有写入目标缓存块构建多个待写入目标缓存块，计算每个待写入目标缓存块的dram向nvm迁移的迁移代价；将所有节点对应的所有读取目标缓存块构建多个待读取目标缓存块，计算每个待读取目标缓存块的nvm向dram迁移的迁移代价；
[0086]
步骤2所述计算每个待写入目标缓存块的dram向nvm迁移的迁移代价，具体如下：
[0087][0088]
其中，表示第k个待写入目标缓存块的dram向nvm迁移的迁移代价，表示第k个待写入目标缓存块在dram中的迁移方案的总访问时间代价，k＝500表示待写入目标缓存块的数量，表示第k个待写入目标缓存块不进行迁移直接将在dram中的缓存块放置在nvm中的方案的总访问时间代价；
[0089][0090]
其中，rpmd表示dram中每mb数据的读时间，表示第k个待写入目标缓存块的大小，表示第k个待写入目标缓存块未来重用次数，rpmn表示nvm中每mb数据的读时间，表示dram缓存中未来重用次数最低的缓存块的空间大小，表示dram缓存中未来重用次数最低的缓存块的未来重用次数，wpmn表示nvm中每mb数据的写时间，epmd表示dram中每mb数据的清除时间，wpmd表示dram中每mb数据的写时间；
[0091][0092]
其中，rpmn表示nvm中每mb数据的读时间，表示第k个待写入目标缓存块的大小，表示第k个待写入目标缓存块未来重用次数，rpmd表示dram中每mb数据的读时间，表示dram缓存中未来重用次数最低的缓存块的空间大小，表示dram缓存中未来重用次数最低的缓存块的未来重用次数，wpmn表示nvm中每mb数据的写时间；
[0093]
步骤2所述每个待读取目标缓存块的nvm向dram迁移的迁移代价，具体如下：
[0094][0095]
其中，表示第i个待读取目标缓存块的nvm向dram迁移的迁移代价，表示第i个待读取目标缓存块的在nvm中的迁移方案的总访问时间代价，n＝500表示待写入目标缓存块的数量，表示第i个待读取目标缓存块不进行迁移直接在nvm中读取的方案的总访问时间代价；
[0096][0097]
其中，rpmd表示dram中每mb数据的读时间，表示第i个待读取目标缓存块的大小，表示第i个待读取目标缓存块的未来重用次数，rpmn表示nvm中每mb数据的读时间，表示nvm缓存中未来重用次数最低的缓存块的空间大小，分别表示nvm缓存中未来重用次数最低的缓存块的未来重用次数，wpmn表示nvm中每mb数据的写时间，epmd表示dram中每mb数据的清除时间，wpmd表示dram中每mb数据的写时间，epmn表示nvm中每mb数据的清除时间；
[0098][0099]
其中，rpmn表示nvm中每mb数据的读时间，表示第i个待读取目标缓存块的大小，表示第i个待读取目标缓存块的未来重用次数，rpmd表示dram中每mb数据的读时间，表示nvm缓存中未来重用次数最低的缓存块的空间大小，分别表示nvm缓存中未来重用次数最低的缓存块的未来重用次数；
[0100]
步骤3：每个待写入目标缓存块根据对应的dram向nvm迁移的迁移代价决策dram向nvm迁移的任务；每个待读取目标缓存块根据对应的nvm向dram迁移的迁移代价决策nvm向dram迁移的任务；
[0101]
步骤3所述每个待写入目标缓存块根据对应的dram向nvm迁移的迁移代价决策dram向nvm迁移的任务，具体如下：
[0102]
若migrationbenefit
toput
为正时，将对应的待写入迁移缓存块驱逐到nvm中，并更新所有缓存块的未来重用次数，发现未来重用次数为0的缓存块直接进行清除；
[0103]
步骤3所述每个待读取目标缓存块根据对应的nvm向dram迁移的迁移代价决策nvm向dram迁移的任务，具体如下：
[0104]
若migrationbenefit
toread
为正时，将dram中未来重用次数最低的缓存块驱逐到nvm中，然后将对应的需要迁移的缓存块从nvm迁移到dram中，并更新所有缓存块的未来重用次数，发现未来重用次数为0的缓存块直接进行清除。
[0105]
本发明的具体实施例还提供了一种计算机可读介质。
[0106]
所述计算机可读介质为服务器工作站；
[0107]
所述服务器工作站存储电子设备执行的计算机程序，当所述计算机程序在电子设备上运行时，使得所述电子设备执行本发明实施例的基于重用代价的混合缓存管理方法的步骤。
[0108]
应当理解的是，本说明书未详细阐述的部分均属于现有技术。
[0109]
应当理解的是，上述针对较佳实施例的描述较为详细，并不能因此而认为是对本发明专利保护范围的限制，本领域的普通技术人员在本发明的启示下，在不脱离本发明权利要求所保护的范围情况下，还可以做出替换或变形，均落入本发明的保护范围之内，本发明的请求保护范围应以所附权利要求为准。

技术特征：
1.一种基于重用代价的混合缓存管理方法，其特征在于：构建多节点spark执行有向无环图，每个节点执行对应的每个读取目标缓存块的写入任务、执行对应的每个写入目标缓存块的读取任务；计算每个待写入目标缓存块的dram向nvm迁移的迁移代价、每个待读取目标缓存块的nvm向dram迁移的迁移代价；决策dram向nvm迁移的任务、nvm向dram迁移的任务。2.根据权利要求1所述的基于重用代价的混合缓存管理方法，其特征在于，包括以下步骤：步骤1：构建多节点spark执行有向无环图，每个节点在执行spark计算任务时，每个节点执行对应的每个读取目标缓存块的写入任务、执行对应的每个写入目标缓存块的读取任务；步骤2：将所有节点对应的所有写入目标缓存块构建多个待写入目标缓存块，计算每个待写入目标缓存块的dram向nvm迁移的迁移代价；将所有节点对应的所有读取目标缓存块构建多个待读取目标缓存块，计算每个待读取目标缓存块的nvm向dram迁移的迁移代价；步骤3：每个待写入目标缓存块根据对应的dram向nvm迁移的迁移代价决策dram向nvm迁移的任务；每个待读取目标缓存块根据对应的nvm向dram迁移的迁移代价决策nvm向dram迁移的任务。3.根据权利要求2所述的基于重用代价的混合缓存管理方法，其特征在于：步骤1所述每个节点执行对应的每个读取目标缓存块的写入任务、执行对应的每个写入目标缓存块的读取任务，具体如下：步骤1.1：若每个节点对应的每个写入目标缓存块需要存储或者迁移到dram空间时，每个节点对应的每个写入目标缓存块获取dram的可用的空闲空间大小；每个节点对应的每个写入目标缓存块向dram发起每个节点对应的目标缓存块的缓存空间请求；dram接收到缓存空间的请求后，检测dram空间中的空闲空间，若dram中空闲空间大于等于每个节点对应的每个写入目标缓存块的缓存空间请求则跳转至步骤1.3，否则跳转步骤1.2；步骤1.2：进行dram中占用空间的缓存块筛选；dram中占用空间中每个缓存块结合有向无环图进行预测得到dram中占用空间中每个缓存块的未来重用次数；将每个节点对应的每个写入目标缓存块结合有向无环图进行预测得到每个节点对应的目标缓存块的未来重用次数；将dram中占用空间中每个缓存块的未来重用次数与每个节点对应的每个写入目标缓存块的未来重用次数进行比较，若dram中占用空间中缓存块的未来重用次数小于每个节点对应的每个写入目标缓存块的未来重用次数，则将dram中占用空间中对应的缓存块的空间放入释放队列；重复执行步骤1.2直至dram中预计空闲空间大于等于每个节点对应的目标缓存块的缓存空间请求，则将所有释放队列中的缓存块迁移至nvm，并跳转至步骤1.3，若步骤1.2无法清理出足够的缓存空间，则请求将每个节点对应的每个写入目标缓存块分配至nvm；
步骤1.3：dram根据每个节点对应的每个写入目标缓存块的缓存空间请求，使用dram中的空闲空间进行每个节点对应的每个写入目标缓存块的缓存块分配；步骤1.4：每个节点对应的每个读取目标缓存块接收读取请求用于计算时，若每个节点对应的每个读取目标缓存块存在在dram中，直接读取dram中的缓存块，若不在，则跳转至步骤1.8；nvm接收到缓存空间的请求后，检测nvm空间中的空闲空间，若nvm中空闲空间大于等于每个节点对应的每个读取目标缓存块的缓存空间请求则跳转至步骤1.6，否则跳转步骤1.5；步骤1.5：若每个节点对应的每个写入目标缓存块存储于nvm，每个节点对应的每个写入目标缓存块获取nvm的空闲空间的缓存块；每个节点对应的每个写入目标缓存块向nvm发起每个节点对应的每个写入目标缓存块的缓存空间请求；nvm接收到缓存空间的请求后，检测缓存空间中空闲空间，若nvm中空闲空间大于等于每个节点对应的每个写入目标缓存块的缓存空间请求则跳转至步骤1.7，否则跳转步骤1.6；步骤1.6：进行nvm中占用空间的缓存块筛选；nvm中占用空间中每个缓存块结合有向无环图进行预测得到nvm中占用空间中每个缓存块的未来重用次数；将每个节点对应的每个写入目标缓存块结合有向无环图进行预测得到每个节点对应的目标缓存块的未来重用次数；将nvm中占用空间中每个缓存块的未来重用次数与每个节点对应的目标缓存块的未来重用次数进行比较，若nvm中占用空间中缓存块的未来重用次数小于每个节点对应的每个写入目标缓存块的未来重用次数，则将nvm中占用空间中对应的缓存块的空间放入释放队列；重复执行步骤1.6直至nvm中预计空闲空间大于等于每个节点对应的每个写入目标缓存块的缓存空间请求，则将所有释放队列中的缓存块直接清除，并跳转至步骤1.7，若步骤1.6无法清理出足够的缓存空间，则清除每个节点对应的目标缓存块并结束该次分配；步骤1.7：nvm根据每个节点对应的每个写入目标缓存块的缓存空间请求，使用nvm中的空闲空间进行每个节点对应的每个写入目标缓存块的缓存块分配；步骤1.8：若每个节点对应的每个读取目标缓存块存在nvm中，则直接读取nvm中的缓存块，此时若dram中存在空闲空间或每个节点对应的每个读取目标缓存块的未来重用次数大于迁移阈值，则会触发缓存块从nvm缓存向dram缓存的迁移；若在nvm中搜索不到每个节点对应的每个读取目标缓存块，则需要重新计算出对应的每个读取目标缓存块。4.根据权利要求3所述的基于重用代价的混合缓存管理方法，其特征在于：步骤2所述计算每个待写入目标缓存块的dram向nvm迁移的迁移代价，具体如下：其中，表示第k个待写入目标缓存块的dram向nvm迁移的迁移代
价，表示第k个待写入目标缓存块在dram中的迁移方案的总访问时间代价，k表示待写入目标缓存块的数量，表示第k个待写入目标缓存块不进行迁移直接将在dram中的缓存块放置在nvm中的方案的总访问时间代价；其中，rpm
d
表示dram中每mb数据的读时间，表示第k个待写入目标缓存块的大小，表示第k个待写入目标缓存块未来重用次数，rpm
n
表示nvm中每mb数据的读时间，表示dram缓存中未来重用次数最低的缓存块的空间大小，表示dram缓存中未来重用次数最低的缓存块的未来重用次数，wpm
n
表示nvm中每mb数据的写时间，epm
d
表示dram中每mb数据的清除时间，wpm
d
表示dram中每mb数据的写时间；其中，
n
表示nvm中每mb数据的读时间，表示第k个待写入目标缓存块的大小，表示第k个待写入目标缓存块未来重用次数，rpm
d
表示dram中每mb数据的读时间，表示dram缓存中未来重用次数最低的缓存块的空间大小，表示dram缓存中未来重用次数最低的缓存块的未来重用次数，wpm
n
表示nvm中每mb数据的写时间。5.根据权利要求4所述的基于重用代价的混合缓存管理方法，其特征在于：步骤2所述每个待读取目标缓存块的nvm向dram迁移的迁移代价，具体如下：其中，表示第i个待读取目标缓存块的nvm向dram迁移的迁移代价，表示第i个待读取目标缓存块的在nvm中的迁移方案的总访问时间代价，n表示待写入目标缓存块的数量，表示第i个待读取目标缓存块不进行迁移直接在nvm中读取的方案的总访问时间代价；其中，rpm
d
表示dram中每mb数据的读时间，表示第i个待读取目标缓存块的大小，表示第i个待读取目标缓存块的未来重用次数，rpm
n
表示nvm中每mb数据的读时间，表示nvm缓存中未来重用次数最低的缓存块的空间大小，分别表示nvm缓存中未来重用次数最低的缓存块的未来重用次数，wpm
n
表示nvm中每mb数据的写时间，epm
d
表
示dram中每mb数据的清除时间，wpm
d
表示dram中每mb数据的写时间，epm
n
表示nvm中每mb数据的清除时间；其中，rpm
n
表示nvm中每mb数据的读时间，表示第i个待读取目标缓存块的大小，表示第i个待读取目标缓存块的未来重用次数，rpm
d
表示dram中每mb数据的读时间，表示nvm缓存中未来重用次数最低的缓存块的空间大小，分别表示nvm缓存中未来重用次数最低的缓存块的未来重用次数。6.根据权利要求5所述的基于重用代价的混合缓存管理方法，其特征在于，包括以下步骤：步骤3所述每个待写入目标缓存块根据对应的dram向nvm迁移的迁移代价决策dram向nvm迁移的任务，具体如下：若migrationbenefit
toput
为正时，将对应的待写入迁移缓存块驱逐到nvm中，并更新所有缓存块的未来重用次数，发现未来重用次数为0的缓存块直接进行清除。7.根据权利要求6所述的基于重用代价的混合缓存管理方法，其特征在于，包括以下步骤：步骤3所述每个待读取目标缓存块根据对应的nvm向dram迁移的迁移代价决策nvm向dram迁移的任务，具体如下：若migrationbenefit
toread
为正时，将dram中未来重用次数最低的缓存块驱逐到nvm中，然后将对应的需要迁移的缓存块从nvm迁移到dram中，并更新所有缓存块的未来重用次数，发现未来重用次数为0的缓存块直接进行清除。8.一种计算机可读介质，其特征在于，其存储电子设备执行的计算机程序，当所述计算机程序在电子设备上运行时，使得所述电子设备执行如权利要求1-7任一项所述方法的步骤。

技术总结
本发明提出了一种基于重用代价的混合缓存管理方法及计算机可读介质。本发明构建多节点Spark执行有向无环图，每个节点执行对应的每个读取目标缓存块的写入任务、执行对应的每个写入目标缓存块的读取任务；计算每个待写入目标缓存块的DRAM向NVM迁移的迁移代价、每个待读取目标缓存块的NVM向DRAM迁移的迁移代价；每个待写入目标缓存块根据对应的DRAM向NVM迁移的迁移代价决策DRAM向NVM迁移的任务；每个待读取目标缓存块根据对应的NVM向DRAM迁移的迁移代价决策NVM向DRAM迁移的任务。本发明充分利用DRAM和NVM的缓存优势，极大限度减少缓存块迁移带来的性能开销，提高了缓存效率，并提升应用程序的运行速度。并提升应用程序的运行速度。并提升应用程序的运行速度。


技术研发人员：程大钊 梁黄黄 何智力 胡创 龚奕利
受保护的技术使用者：湖北珞珈实验室
技术研发日：2023.06.27
技术公布日：2023/10/15