Rambrain：一个虚拟扩展物理内存的库

*SoftwareX 6（2017）179原始软件出版物Rambrain-虚拟扩展物理内存的库M. Imgrunda，b，A.阿瑟a，c，*aUniversity Observatory Munich，Scheinerstraße1，81679 Munich，GermanybMax-Planck-Institute for Radio Astronomy，Auf dem Hügel 69，53121 Bonn，Germanyc马克斯-普朗克地外物理研究所，Giessenbachstrasse 1，85748 Garching，德国ar t i cl e i nf o文章历史记录：2016年10月11日收到2017年7月13日收到修订版，2017年保留字：内存管理物理内存限制抽象库系统分页开源MPI/OpenMPa b st ra ct我们介绍Rambrain，一个用户空间的C++库，管理数据密集型应用程序的内存消耗。使用Rambrain，可以过度使用超过系统中物理内存大小的内存虽然存在其他更先进的技术来解决这个问题，但Rambrain专注于通过提供快速，通用和易于使用的解决方案来节省开发时间Rambrain负责临时将数据交换到磁盘，并且可以处理当前物理内存大小的倍数。Rambrain是线程安全的，兼容OpenMP和MPI，并支持异步I/O。该库的设计要求对现有程序进行最小的更改，并且只造成很小的开销。©2018由Elsevier B.V.这是一篇CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）的网站上进行了介绍。代码元数据。代码元数据描述当前代码版本1.1用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX-D-16-00086GPL许可证使用git的代码版本控制系统使用C++、OpenMP、MPI的编译要求，操作环境依赖性Linux，libaio如果可用，链接到开发人员文档/手册http://mimgrund.github.io/rambrain/问题支持电子邮件arth@usm.uni-muenchen.de1. 介绍编写处理大型数据集的代码是许多科学家最耗时的任务之一。复杂的解决方案相当于针对手头的问题以优化但专门的方式编写内存管理函数，即所谓通讯作者：慕尼黑大学天文台，Scheinerstraße1，81679 Munich，Germany.电子邮件地址：imgrund@usm.uni-muenchen.de（M.Imgrund），arth@usm.uni-muenchen.de（A. Arth）。网址：https://github.com/mimgrund/rambrain（M. Imgrund）。http://dx.doi.org/10.1016/j.softx.2017.07.0042352-7110/©2018由Elsevier B. V.发布或者，可以尝试通过硬件来解决问题。例如，供应商提供附加组件，如非易失性存储器（NVRAM）或具有高带宽的存储器（MC-DRAM）。然而，并行化代码的任务仍然存在，并且一般来说，由于必须选择分布式存储器并行化并且编写可扩展的代码是困难的，因此实现起来并不容易。因此，我们引入Rambrain，一个库，便于快速开发需要大内存的应用程序它可以轻松地与Linux上现有的C++代码集成，并帮助应用程序交换暂时不需要的数据，以访问系统上可用的实际物理内存的倍数虽然可能存在其他更复杂的解决方案，但我们认为，这是一篇CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）的网站上进行了介绍。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softx180M. Imgrund，A. Arth / SoftwareX 6（2017）179在大多数情况下，快速、可靠和开箱即用的解决方案的灵活性优于几个百分点的性能增益。2. 避免内存不足错误可用物理内存的不足由操作系统通过使用系统交换来管理。作为一个应用程序开发人员，你会看到一个连续的虚拟内存地址空间。通常不清楚虚拟存储器的块（所谓的“页面”）是否在给定时间驻留在物理主存储器位置（称为“帧”）中。这一抽象层允许过度使用物理内存和临时将页面交换到辅助存储器[1]。当可用物理内存不足时，系统会由于交换活动而变慢，特别是在使用多个内存密集型应用程序时。存在全局内核参数，例如内核交换，以操纵内核交换行为。这些参数适用于典型的服务器和最终用户场景。例如，当空闲物理内存量与手头的问题相比非常大时，调优这个参数可以延迟交换，但是在某个时候，一个对内存非常贪婪的应用程序将占主导地位。另一种建议的缓解技术是mlock和mmap内核函数。mlock锁定内核换入/换出的地址范围但是，不能保证解锁页面将释放物理内存。使用内存映射到大文件可能会打开有限数量的然而，由总文件描述符数目施加的限制可能妨碍这些窗口的最佳控制和放置设计用于处理大型数据结构的库，如STXXL [2]，通过提供类似于标准模板库（STL）的大型标准容器来虽然非常有用，但它们也有缺点，例如仅限于POD（普通旧数据结构-没有con-or析构函数或虚拟成员的类）。手动解释换入和换出等价于问题的核外算法。特定问题的专业解决方案包括例如n体代码[3]或线性代数计算[4，5]。核心外方法的介绍性综述见[6，7]。然而，这与找到一个专注于节省开发时间的通用解决方案的目标在代码开发过程中，数据访问的顺序是很清楚的在下一节中，我们将介绍一个接口，它将这些信息传递给库，以计划交换操作。3. 接口Rambrain3.1. 基本用法Rambrain的设计要求对现有代码进行最小的更改。考虑清单1中的代码，它在堆内存上初始化一个数据类型为double的二维平面波场手动管理内存相当于调用加载和卸载第8行数据这些额外的行开始混淆算法代码结构。嵌套的for循环以及基本的初始化将很难被发现。整体结构与经典版本的差异很小直到第8行，我们只包装数据对象。我们在这里引入两个模板类managedPtr<>和adhereTo<>来嵌入Rambrain。第一个类managedPtr<>用Rambrain包装器代替了分配和交易位置这种替换对于隐藏指向逻辑内存中实际数据的指针是必要的，因为清单1：使用Ram- brain初始化典型的二维字段123456789101112131415161718对数据的访问由adhereTo<>完成，它以camel-case表示其含义：This objects adhere to the data。虽然根据作用域规则存在相应的adhereTo<>对象，但通过将adhereTo<>对象分配给指针，可以保证用户可以获取指向数据的有效指针，如第9行所做的那样作用域使用户不必解释数据暂时不再使用的状态当这个adhereTo<>对象被删除时，数据可能会被交换以释放物理内存。3.2. 数据结构为了从单独管理数据结构的一部分中获益，用户必须确保每个托管指针的有效载荷足够大，以便管理数据的开销变得很小。我们建议 按常规分 配较小的 结构， 并将数据 密集型元 素留给Rambrain。但是，如果选择了managedPtr<>，则必须知道管理的数据块将作为一个整体换出和换入理想情况下，请求的managedPtr<>的所有元素都将用于计算，因为Rambrain必须加载或卸载所有元素。幸运的是，正常的CPU缓存受益于这种局部性假设，开发人员习惯于优化这种连续的本地访问方案。对于术语局部性的回顾和进一步的提示，请参见示例[8，9]。4. 建筑和设计如图所示 1、Rambrain分为四个独立的类。我们提供了后端接口的参考实现和所有类的源代码文档[10，11]。有关库架构的更广泛描述，请参见[12]。4.1. 交换策略参考实现提供了一个通用的策略，应该能够以有效的方式处理随机访问和连续与Linux内核1类似，Rambrain跟踪数据访问，以便对托管数据进行排序并交换未使用的数据。 细节可以在图中看到。二、元素顺序表示为当用户取消引用时，这个指针。1感兴趣的读者可以参考例如：[13]或https://linux-mm.org/。doublek_x =1。 ，k_y=1。;在x_max=1024，y_max=1024的情况下，用x _ m ax= 1024的方法进行了计算;for（intx=0;xx_max;++x）//所有的操作都是按顺序的arr[x]=newamanagedPtrdouble >（y_max）;for（intx=0;xx_max;++x）{//intializefieldadheTodouble>glue（arr[x]）;manaloggedPtrdouble>narr[x_max];doubleline =glue;doublexx=x/（double）x_max;for（inty=0;yy_max;++y）{doubleyy=y/（double）y_max;l in e [y]= sin（（xx k_x+yyk_y））;}}//对字符串进行处理：for（intx=0;xx_max;++x）int[x]; //deallocatelinesM. Imgrund，A. Arth / SoftwareX 6（2017）179181将突出显示的第四行移到第六行之后，同步版本。使用异步I/O隐藏加载延迟，类似于GPU编程技术或缓存的预取[14，参见例如]。清单2：显式异步访问Fig. 1. Rambrain的架构：Rambrain分为四个主要类别，每个类别都有不同的用途。虚线框中的类是纯接口。图二. 循环管理内存：访问一个元素后，访问顺序很可能不会因每个转换而改变。该算法将异步预取具有连接端点的元素指针的双向链表该系统允许以有意义的顺序保存连续数据，并预测未来可能的需求。4.2. 抢占式元件换入Rambrain提供了抢先换入数据的功能，以通过实际计算来跟踪换入操作。这是自动发生的，并通过具有它可以填充的固定内存预算来适应情况这种方法显然有利于重复访问模式访问每个元素一次。对于随机访问策略，已经采取了确保也检测较小模式的措施我们通过调整预加载的内存块的数量来防止换入过于贪婪4.3. 异步I/OLinux内核为Rambrain提供了异步加载和保存数据到文件的能力。主要操作仅在文件系统缓存上执行，它经历了漫长的演变，是一种非常快速有效的方式来使用空闲物理空间，而不会在高负载下产生负面影响。在正常缓冲的基础上实现异步I/O意味着高效的写出，同时对体系结构的变化具有鲁棒性，并受益于内核缓存技术。数据的交换可以通过创建adhereTo<>-object.在异步I/O期间，可以进行其他计算。当最终获取指向实际数据的指针时，请求的有效负载可能已经在后台复制了。 同步和显式异步请求的流程图如图3所示，清单2中使用的代码略图。123456785. 结果和讨论测量内存管理器的性能并不简单，因为文件系统操作、内核异步I/O或调度器性能可能会影响速度和吞吐量。为了测试交换行为，我们建立了一个测试系统，配备了一台PC机只有一个小的RAM模块。然后使用OpenSuse 13.2（基于内核3.16）在Intel（R）Core（TM）2 Quad CPU Q6700上进行测试，CPU Q6700在2.66 GHz下运行，运行在具有32Kb L1 Cache、4MB L2 Cache和标准非品牌2GB内存模块的ASUSTeK P5NT WS处理器上。硬盘是Samsung SpinPoint S250。5.1. 没有交换的库开销我们提出了在足够的物理RAM大小的情况下，库对用户代码的执行时间施加的开销这允许判断Rambrain是否达到接近原生性能，因此如果不清楚目标系统是否需要它，则可以使用它。作为测试，我们使用前向欧拉积分器[15]对一组固定的粒子进行简单的n体模拟，并将轨迹和速度保存在二维阵列中。因此，程序使用的内存会随着时间的推移而增长。两次运行的结果如图所示。 四、从几MB的数据开始，两个方法的执行时间都是相等的，这表明负载和开销至少是相等的。这也可以通过蓝线快速下降并收敛到接近2GB标记的约2%的值来看出与本机代码相比，当没有数据需要交换时，Rambrain总是有点慢。但是，对执行时间的影响很小。5.2. 异步I/O和抢先读/写为了测量通过主动性和抢占式技术实现的加速我们应用模拟一些计算工作的整数乘法，以证明加载时间被隐藏。我们改变数据写入（加载）的内存阵列的百分比和数据块大小，模拟负载随数据的缩放请注意，数组元素可以被多次访问，导致负载大于100%。在图5中，可以清楚地看到，由于抢先策略，执行时间减少了。对于增加的计算负载，库的开销被屏蔽在百分之当然，一个特定于问题的方法，准确地预取下一个需要的元素而不猜测，可以进一步提高性能，但带来了增加开发时间的缺点。当磁盘带宽占主导地位的计算时间，只有部分的换入/出过程可以被屏蔽的抢先换入。这可以在图的右下面板中看到，因为当缓存空间耗尽并且向辅助存储器的写出占主导地位时，抢占式和非抢占式策略被同化处理器（1024），data2（1024）;和一个Todouble>glue（data）;和一个Todouble>glue2（data2）;double=glue;do_something_on_data（ptr）;doubleptr2=glue2;document. writeln（）;182M. Imgrund，A. Arth / SoftwareX 6（2017）179(a) 阻塞I/O。(b) 显式异步I/O。图三.用户代码与Rambrain库的示例性交互。虽然在（a）中等待数据到达的时间被浪费，但是用户可以使用该空闲时间来计算已经到达的数据，如（b）中所描绘的。Rambrain尝试自动预取所需的元素，就像在情况（b）中一样，而无需用户显式地硬编码。5.3. 与本机操作系统交换的最后，让我们比较一下Rambrain和系统交换的性能。在此测试中，我们使用了一个额外的10GB交换文件，用于非独占系统交换。我们进行了两次不同的运行，使用和不使用Rambrain。在第一个中，数据被连续写入到8GB大小的矩阵中。在第二个例子中，应用程序随机写入这个矩阵的元素。在后一个测试中，我们明确禁用了抢占式交换算法。在某些非托管运行中，本机应用程序被OOM杀手杀死。这可能是由于堆内存的快速增长而发生的。如果交换文件的大小比实际交换文件的大小至少大25%，那么OOM杀手通常会终止进程。当尝试成功时，系统实际上是不可用的，因为即使打开另一个shell提示符也需要几分钟。此外，本机代码对系统的干扰在应用程序退出时不会停止，而是使系统在几分钟到几小时的使用中处于缓慢反应状态，因为其他必要应用程序的大部分已经被换出到磁盘。此外 ， Rambrain 管理 的代 码的 实际执 行时 间也 有利于 使用Rambrain。在连续访问的情况下，使用库的版本比本机版本快约10%，使系统在计算期间可用。在随机访问的情况下，Rambrain只比本机代码快2%，如果我们遵守设计限制，即单个managedPtr<>的所有元素都将被访问。M. Imgrund，A. Arth / SoftwareX 6（2017）179183清单3：标准隐式异步加载1234567891011121314151617见图4。n-body代码累积速度和位置的执行时间：通过比较使用和不使用Rambrain的版本，我们可以看到，在合理的数据大小范围内，库的开销仅占执行时间的百分之几。5.4. 真实世界应用：差分成像为了证明Rambrain在实际示例中是有用的，我们选择了如[16]中的存储器密集型差分成像算法，其中我们实现了Rambrain以从局部卷积核到全局卷积核[17]。使用最先进的仪器拍摄的高分辨率图像的大小可以是140002像素，例如，参见参考文献[18，19]。典型地，使用具有数百个自由参数的内核，这导致以下内核矩阵的示例性存储器消耗：ImageSize· KernelSize·（Values+ Errors）·float=14000 2·400·2·4 B 600 GB。这超过了典型PC上的主存储器的物理大小，而这种分析所需的CPU时间仅为几百个CPU小时。图 6我们使用模拟数据给出了这种分析的结果。我们通过将重构信号与内核折叠并从输入中减去它来评估所实现的拟合的质量局部内核显示剩余的星形特征，而使用Rambrain计算的全局内核将结果降低到随机噪声。因此，能够使用这样的全局内核，可以恢复可变光源的信号的更大部分。随着Rambrain[20 ]第20段。对于实际观测图像的进一步科学分析，我们参考Riffeser等人即将发表的论文正在编写中6. 结论和前景我们详细描述了Rambrain如何能够在非常一般的情况下自动管理数据交换，以达到令人满意的性能。我们已经证明，概述的机制不仅有效地工作，而且优于天真的方法来模仿他们的策略。该库处理数据的异步传输，提供磁盘I/O操作的延迟隐藏，并在计算负载允许的情况下将空闲时间减少到百分之几由于所有这些都是由最小的用户端交互提供的，我们认为编写一个内存管理器的目标是使图五、抢占式加载：我们比较了Rambrain的启用和禁用抢占式机制，发现Rambrain的抢占式行为导致了显着的性能提升。unsigneditnumel=1024，bytesize;managedPtrmanagedPtr> n（numel，bytesize）的情况下;ADHERETOString（managedPtrchar>，你好，PTR）的情况下;flotload;floatretitimes=10ad/100。;intiteratins=10230;for（inti=0;iteratins; ++i）{unsignedintuse=（i//AdheToadhereTo glue（ptr [ use ]）;//将该位置添加到对象charge_loc =glue;对于（intr=0;r++），）的情况下，位置[r]}184M. Imgrund，A. Arth / SoftwareX 6（2017）179见图6。 差分成像残差：左：多个局部内核;中：具有Rambrain的全局内核;右：两个图像的差分。用户透明地访问多个要完成的物理Rambrain促进了在具有中等内存资源的机器上使用内存密集型算法，而不需要更多的开发时间。由于易于与现有代码集成，任何C++程序都可以利用Rambrain来处理大型数据集，如差分成像示例所示。感兴趣的读者可以找到作为开源项目发布的代码[11]，并附有大量的进一步文档[12]。确认我们感谢Karsten Wiesner和Christian Storm对本文高级主题的介绍提供了有益的评论。我们感谢Arno Riffeser与我们合作，在他的差异成像代码中实现和评估Rambrain我们感谢SusannaMaurer帮助我们在LMU组织了一个关于Rambrain的研讨会我们还要感谢匿名审稿人和我们的同事Stefan Heigl，他们帮助提高了论文的整体质量，并为完成论证提供了建议。此外，我们感谢所有帮助我们在实际实现中找到bug的人引用[1] 李国忠，李国忠，李国忠.记忆取证的艺术Wiley;2014.[2] Dementiev R，Kettner L，Sanders P. STXXL：XXL数据集的标准模板库。软件。- 实际有效期2008;38（6）：589-637.[3] Salmon JK，Warren MS，并行，核外方法用于n体模拟。In：PPSC.SIAM;1997.[4] 托莱多湾数值线性代数中的核外算法综述。I n ：Abello JM，Vitter JS，editors. 外 部 存 储 器 算 法 。 Boston， MA ， USA ： American MathematicalSociety;1999. p. 161比79[5] Reiley WC，van de Geijn RA. Pooclapack：并行核外线性代数包。美国德克萨斯州奥斯汀：德克萨斯大学奥斯汀分校; 1999年。[6] 托莱多湾数值线性代数中的核外算法综述。I n ：Abello JM，Vitter JS，editors. 外部存储器算法。DIMACS系列离散数学和理论计算机科学，美国数学学会，1999年。p. 161比79[7] 维特JS。外部存储器算法和数据结构：处理海量数据。ACM计算监视器2001;33（2）：209-71.[8] 丹宁PJ。地方性原则。Commun ACM2005;48（7）：19-24.[9] Chellappa S，Franchetti F，Püschel M.如何编写快速数字代码：一个小介绍。In：Lämmel R，Visser J，Saraiva Ja，editors. 软件工程生成和转换技术II：国际暑期学校，GTTSE 2007，葡萄牙布拉加，2007年7月2日至7日。修订文件。Berlin，Heidelberg：Springer Berlin Heidelberg;2008. p. 196-259[10] Imgrund M ， Arth A ， Rambrain 的 每 日 自 动 生 成 文 档 ， 2017 ，http://mimgrund.github.io/rambrain/。[11] ImgrundM ， ArthA ， GithubrepositoryforRambrain ， 2015 ，https://github.com/mimgrund/rambrain/.[12] Imgrund M，ArthA，Rambrain - a library for virtual extending physicalmemory，2015，ArXiv Preprint，https://arxiv.org/abs/1510.06358.[13] Rusling DA，《Linux内核》，1998年。[14] 放大图片作者：John W，John W.软件预取。第 四届编程语言和操作系统架构支持国际会议论文集。 ASPLOSIV，NewYork，NY，USA：ACM;1991. p. 40比52[15] 尤拉湖Institutionum calculi integralis，Number Bd.1.一、 进出口Acad. 进出口圣。1768年[16] Gössl CA，Riffeser A.用于在高度拥挤的领域中检测可变源的图像缩减流水线。Astron Astrophys2002;381：1095-109.[17] 阿拉德角使用空间变化核的图像减法。天文学增刊2000;144：363-70.[18] Lee C-H ， Riffeser A ， Koppenhoefer J ， Seitz S ， Bender R ， Hopp U ， 等 .PAndromeda-first 结 果 来 自 于 Pan-STARRS 1 对 M31 的 高 节 奏 监 测 。 AstronJ2012;143：89.[19] 李C-H，李福泽A，塞茨S，Bender R，Koppenhoefer J.WendelsteinCalar altopixellensing项目11年观测的微透镜事件。Astrophys J2015;806：161.[20] Barris BJ，Tennis JL，Novicki MC，Wood-Vasey WM. NN2通量差法构造可变物体光变曲线。Astron J2005;130：2272 - 7.