面向资源约束的数据流并行自适应缓存管理研究

发布时间：2021-08-16 10:00

　　数据并行系统中应用程序的爆炸式增长,以及对任务处理和数据分析的日益增长的高效需求,使得数据并行系统在处理具有高实时性需求的I/O密集型数据集时承受着较大的内存压力。低效的缓存策略会严重降低资源的利用率影响系统性能。通常情况下,对于需要大量内存计算的数据流任务,如何实现高效的缓存管理是权衡性能和内存开销的主要措施。近些年,设计出恰当的缓存管理策略以平衡工作负载,缓解传输瓶颈,减少内存资源消耗是内存计算中的研究重点之一。在缓存的设计和选择的问题上,研究证实当前主流的基于内存计算并行数据处理系统中包括LRU在内的默认的传统缓存算法并不能有效满足当前环境下应用特征和实时需求,且容易造成低命中率、不必要的I/O开销和资源浪费,主要归因于这些缓存算法多未充分利用数据并行系统中的数据依赖语义信息,而是依赖传统的基于数据项最近访问信息和频率信息等局部信息进行缓存管理。本文旨在设计一种新的缓存算法以达到性能与开销之间进行折衷的目的,该算法称为非关键路径最小引用计数（Non-critical Path Least Reference Count,简称NLC）。其与现有算法的不同之处在于:其一,NLC充分利... 

【文章来源】：中国科学院大学(中国科学院深圳先进技术研究院)广东省

【文章页数】：60 页

【学位级别】：硕士

【部分图文】：

内存计算硬件架构

第2章背景知识介绍11图3：最小引用计数算法示例计算作业的数据依赖DAG的可用性不仅限于Spark当中，常见的并行框架例如ApacheTez[7]也可以提供数据依赖语义信息，Tez的设计包括支持从Task收集相关信息的可插拔顶点管理模块。其API允许程序员明确定义工作流程DAG应用程序，事先可供Tez调度程序使用，同时在运行时可以动态调整数据流图以达到优化性能和提高资源利用率的目的。2.3最小引用计数算法上节中介绍了在计算机领域和数据并行系统中数据依赖语义的具体含义。尽管在数据并行系统中存在有别于传统系统的数据依赖语义信息，然而现有常见的数据并行系统在默认情况下的缓存算法中并未充分利用该信息，如在1.2提到最近最少使用策略(LeastRecentlyUsed,LRU)，它依然时是在Spark中，BlockManager在存在高内存压力的情况时默认的缓存策略。然而仅仅依靠用于缓存管理的最新访问和访问频率信息会浪费大量内存以保存也许永远不会在下游计算中使[27]用的数据块，这将会无可避免地会导致低效的资源利用率。因此这一节将介绍一个最小引用计数算法以及Yu等人地相关工作，改算法在一定程度上利用了数据并行系统中的依赖语义信息。Figure3：AnexampleofLeastReferenceCount图3最小引用计数示例

面向资源约束的数据流并行自适应缓存管理研究12在该示例中，最小引用计数算法根据下游数据依赖信息制定缓存规则，如图3的例子所示，在DAG提交时，块A、B、C和D的引用计数分别为A=4>B=3>C=2>D=1最小引用计数(LRC)策略跟踪每个数据块的引用计数，在需要的时候，它会清除引用计数最小的数据块。直观地说，引用计数越高，那么在未来该数据块被访问地可能性就越大。为了验证引用计数(ReferenceCount)能否成为未来数据访问的简单可行指标。Yu等人针对最近使用信息，最频繁使用信息，引用计数三种不同指标的代表算法进行了一系列实验测量其优先级。实验表明使用引用计数的始终能比其他两种指标效果要好。Figure4:Uncertaintyofdatadependence如图4中的一个例子。在计算了数据块块C和D之后，假设集群调度器提交两个任务集Task1和Task2分别计算数据块M和N（假设E和F已经在内存中）。在这种情况下，首先计算哪个块E或F取决于Task1和Task2的调度顺序，而这又决定了块E和F的访问次序,局部数据依赖语义信息如下:((′)∩())≠Φ((′)∩())≠Φ((′)∩())≠Φ((′)∩())≠Φ图4数据依赖的不确定性


本文编号：3345464