随着应用程序的规模越来越大，应用程序对计算机算力的需求也越来越高，促进了近年来超级计算机的飞速发展。传统的超级计算机主要面向科学计算类应用，对其他类型的应用，如机器学习^[1]、图计算^[2]、大数据处理等类型的应用支持欠佳，限制了超级计算机的应用场景。现代超级计算机从硬件层面和软件层面都逐渐增加了对不同应用类型的支持。新一代神威超级计算机是继神威·太湖之光^[3]后的最新一代国产超级计算机系统。神威系列超级计算机的芯片，即申威系列芯片，由中国自主研发生产，其体系结构与典型结构有着较大差异，导致运行于其上的系统软件也有较大的不同。为了满足应用需求，新一代神威超级计算机支持两种不同的执行模式：高性能模式和动态模式。1) 高性能模式使用加载器控制系统资源的调度，有效提高了程序的执行效率，但要求程序为静态编译，不支持动态链接库。这种模式在传统科学计算类应用中使用较多。2) 动态模式使用操作系统进行资源调度，可以对系统资源进行动态管理，因而可以支持Python等语言。然而，在动态模式下，由于神威体系结构的不同，一些针对典型计算机体系结构的系统实现在神威上会出现性能问题。例如，在神威体系结构中，尽管操作系统内核运行在页式空间，但用户态内存管理采用段式管理。这种混合管理模式导致在动态模式下用户态程序调用内存分配器分配大块内存时，会出现明显的性能降低。

本文针对新一代神威超级计算机的动态模式，充分考虑了神威体系结构的特点和应用本身的负载特征，设计了一个高效内存分配器——SWAlloc，并基于SWAlloc深度优化了超大规模机器学习训练框架“八卦炉”。实验结果表明，SWAlloc相对于原有的神威版本C标准库中的内存分配器malloc，在进行大内存分配时，可以有若干个数量级的性能提升，能使八卦炉的端到端性能提升88.44倍。同时，本文也通过随机内存分配记录和标准测试程序集PARSEC^[4]中应用的内存分配记录对SWAlloc进行了测试，证明了SWAlloc的通用性和高效性。SWAlloc目前已经被布署于新一代神威超级计算机上，并被深度整合到了SWPytorch和SWTensorFlow等框架中，用于包括大规模机器学习训练、分子动力学模拟等在内的多个应用。

1 相关工作

内存是计算机系统的重要组成部分，而内存分配也是程序运行过程中的重要一环。内存分配可以分为静态分配和动态分配两种：静态内存分配是指在程序运行前已经完成相应的内存分配，例如对静态对象的内存分配；而动态内存分配是指在程序运行过程中进行的内存分配，由内存分配器来完成，例如对动态对象的内存分配。由于许多对象无法在程序运行之前确定其数量和大小，因此动态内存分配对于应用程序，尤其是复杂应用程序是必不可少的。本节将对两个典型的内存分配算法，空闲列表(freelist)分配器^[5]和伙伴(buddy)分配器^[6]，进行介绍，并简要介绍典型内存系统中的内存管理方式和现有的内存分配器优化工作。

1.1 空闲列表分配器

空闲列表分配器以一个链表来维护当前所有空闲的内存块。当进行内存分配时，分配器会遍历空闲列表，找到一个不小于请求大小的空闲内存块，并从该内存块中分割出所需大小的内存返回给应用程序，而剩余的内存作为新的内存块存储在空闲列表中；当进行内存释放时，分配器将待释放的内存放回空闲列表，并通过与相邻的空闲内存块合并的方式进行碎片回收。由于内存分配与释放涉及链表查找操作，空闲列表分配器的时间复杂度为O(n)。

1.2 伙伴分配器

伙伴分配器将空闲内存以2^k B大小划分为块，相同大小的内存块组成空闲列表。在进行内存分配时，从不小于待分配内存大小的2^k B的空闲列表中分配出一个内存块。如果当前已经没有2^k B的内存块，则对更大的内存块进行分裂操作，如将2^k+1 B的内存块分裂为两个2^k B的内存块，若没有2^k+1 B的内存块：则以此类推找更大的内存块进行分裂。这两个分裂得到的内存块被称为伙伴内存块。在进行内存释放时，如果被释放的内存块的伙伴内存块也处于空闲状态，则将这两个内存块合并为一个更大的内存块从而进行碎片回收。由于内存的分配和释放涉及内存块的分裂与伙伴内存的合并，因此伙伴分配器的时间复杂度为O(log n)。伙伴分配器在分配内存时必须以2的整次幂为单位进行分配，当应用程序中存在大量非2的整次幂的内存时，单独使用伙伴分配器会造成大量的内存浪费。

1.3 典型内存系统中的内存管理

典型内存系统通常采用页式内存管理^[7]，即将内存划分为大小为2的整次幂的内存页(一般为512 B~8 kB)，并通过页表进行索引。当进行内存分配时，空的内存页的虚拟地址并未映射到物理地址上，只有当进行内存访问触发缺页时，才会将其映射到物理内存。伙伴分配器通常用于页表的分配，由于页表的大小为2的整次幂，避开了伙伴分配器可能造成内存浪费的缺点。对于更细粒度的内存分配，则通过额外使用其他的内存分配算法，如slab算法^[8]，来减少内存浪费。

同时，虚拟内存也大大减少了伙伴分配器的内存浪费问题。例如，当需要分配1.1 GB的内存时，伙伴内存分配器实际会分配出2 GB的内存，带来0.9 GB的内存浪费。但在页式内存管理下，未触发缺页时无须分配物理内存，因此伙伴分配器实际浪费的物理内存大小不会超过内存页的大小。

1.4 现有的内存分配器优化工作

由于内存分配效率对系统性能有较大的影响，许多研究者提出了适用于不同场景的内存分配器。Al-Yatama等^[9]针对云服务场景提出了一种基于内存分区的内存分配器。Khaled^[10]利用静态内存分配方法提高了并行递归搜索算法的性能。Pupykina等^[11]针对高性能计算系统中的异构加速器，实现了一种支持服务质量(quality of service，QoS)的基于预测的内存分配算法。针对内存更为有限的嵌入式系统的内存分配问题，曾非一等^[12]分析了实时多处理器系统(real-time executive for multiprocessor systems，RTEMS)中现有内存分配方案的效率。宋敏超等^[13]通过结合二级间隔表动态内存分配算法(two-level-segregated fit，TLSF)和内存直接分配算法，提高了内存分配效率。此外，一系列研究工作还总结和评价了在不同的平台和负载下各种内存分配方案的优化方法和性能特性^[14-21]。

2 研究背景 2.1 新一代神威超级计算机系统体系结构

新一代神威超级计算机系统使用中国自主研发的申威26010-pro处理器。每个计算节点包含2个申威26010-pro处理器和192 GB的内存，两个处理器各96 GB内存。节点之间通过国产自主可控高速互连网络连接，节点内或节点间的处理器之间使用信息传递接口(message passing interface，MPI)^[22]进行通信。

申威26010-pro处理器的架构如图 1所示，包含了6个核组，核组之间通过环形网络(简称为环网)连接。每个核组包含1个运算控制核心(management processing element，MPE，通常称为主核)负责运行操作系统、执行控制流等，同时包含64个运算核心(computing processing elements，CPE，通常称为从核)，这64个从核被统称为从核阵列。在一个从核阵列中，从核被组织成8×8的网格，同时允许从核之间直接进行数据通信。

新一代神威超级计算机中，用户态内存空间采用段式管理。内存空间主要分为私有段、连续段和交叉段3部分。其中：私有段为从核的私有内存空间，作用范围为每个从核。连续段，也叫做共享段，作用范围为单个核组。由于一个核组内的主核和从核共享连续段的内存空间，因此可以使用连续段内存支持核组内通信。交叉段的作用范围为整个处理器，通过对6个核组的内存空间进行交叉编址，交叉段可以支持6个核组之间的互相访问。然而，由于交叉段的编址粒度为256 B，访存操作的地址在不对齐256 B时需要对访存操作进行拆分，会造成访存性能的下降。

2.2 新一代神威超级计算机的执行模式

在新一代神威超级计算机中，程序使用神威加速计算框架(Sunway accelerate computing architecture，SACA)执行。针对不同的程序类型，新一代神威平台上的SACA支持两种不同的执行模式：高性能模式(加载器模式)和动态模式(akernel模式)。

高性能模式针对传统科学计算应用，使用加载器控制计算资源。这种模式自神威·太湖之光开始就被广泛支持。在高性能模式下，代码使用特定的编译选项进行编译，之后通过加载器执行。加载器预先进行所有的内存分配与映射，同时接管所有的系统调用。高性能模式下，程序被完全执行在用户态，保证了执行效率。然而，这种模式下，由于需要加载器预先进行内存分配，链接过程必须使用静态链接。这一特点给高性能模式下应用的运行带来了很大的限制。例如，Python解释器就需要动态链接的支持。因此，高性能模式不能支持许多应用程序的执行。

动态模式针对通用应用需求，使用操作系统控制计算资源，是新一代神威超级计算机新提供的执行模式。这种模式避免了高性能模式对程序本身的限制，可以支持几乎所有典型计算机系统支持的应用。例如，神威平台上Python解释器即运行于动态模式，并在此基础上支持了SWPytorch、SWTensorFlow等机器学习框架。然而，很多软件本身并没有针对神威平台的体系结构特性进行专门优化。虽然这些程序在动态模式下可以正常执行，但执行过程中会出现大量性能问题，例如动态模式下分配大块内存时会有严重的性能下降，这给新一代神威超级计算机的高效使用带来了巨大挑战。

3 研究问题分析

在动态模式下，内存分配默认使用C标准库(libc)的内存分配器malloc实现。本文在新一代神威超级计算机和典型计算机系统中，分别调用C标准库的malloc进行不同大小的内存分配，并测量其分配时间。典型计算机系统x86平台的实验使用双路Intel Xeon CPU E5-2680 v4，主频为2.40 GHz。结果如图 2所示。可以看到，x86平台下的内存分配性能与分配内存大小相关性较小；而在神威平台中，在分配小块内存时其性能相对稳定，但在分配大块内存时其性能会出现明显下降。从16 MB大小的内存分配到32 MB大小的内存分配，性能陡降44 000倍。这种大块内存分配的性能下降严重影响了神威平台动态模式的性能。这一现象发生的原因与神威体系结构的特点以及C标准库内存分配器的实现方法有关。在典型计算机系统中，内存分配时只分配虚拟地址，不进行内存映射，当第1次实际访问该地址时发生缺页中断，才会由操作系统分配物理内存，并建立虚拟内存和物理内存的映射。C标准库中的malloc使用两种分配方法进行虚拟内存分配：对小块内存，使用brk直接进行分配；而对大块内存，则使用内存映射(memory map，MMAP)匿名调用进行分配。其分配方法的选择取决于分配内存的大小，阈值为128 kB~32 MB的动态值，与运行负载相关。在本实验中，阈值为32 MB，因此在分配内存大于等于32 MB时，神威平台的内存分配时间相对较长。

malloc在典型计算机系统中可以很好地工作，而在神威平台上，由于内存使用段式管理，虚拟内存和物理内存有明确的映射关系，不会再由操作系统进行物理内存分配。MMAP匿名调用包含初始化内存空间为0的操作，在x86平台是在触发缺页错误时进行的，不会影响内存分配的时间，且在初始化时该块内存即将被使用，可以被放入缓存中，因此不会带来明显的性能影响。然而，在神威平台上，为了满足初始化为0的语义，MMAP必须在分配时直接进行初始化操作，这个过程跟分配内存大小直接相关。因此，相对于x86平台，在神威平台的动态模式下分配大块内存会出现十分显著的性能下降，同时分配时间和分配内存大小呈显著的正相关，如图 2所示。

另外，MMAP的内存分配使用伙伴算法，这种算法的缺点是只能分配2的整次幂大小的内存，对内存空间的利用率较低。在x86平台中，由于页式内存管理的存在，虚拟内存空间可以大于物理内存空间，没有被用到的虚拟内存不会被分配物理内存，因此不存在实际的物理内存浪费。但在神威平台上，由于使用的是段式内存管理，所有内存都会被映射到实际的物理内存，因此伙伴算法会导致神威平台的内存利用率相对较低。

4 SWAlloc内存分配器

为了满足在神威超级计算机上进行高效内存分配的需求，本文设计了一个高效的内存分配器，SWAlloc。SWAlloc利用双向链表和平衡树在搜索时的高效性，实现了一个复杂度为O(log n)的内存分配器。同时，针对神威平台自带的内存分配器的性能特征和应用的内存分配特征，本文又进一步为SWAlloc增加了大小感知功能的设计，采用不同的分配策略应对不同大小的内存分配，以进一步提高SWAlloc的效率。

4.1 双向链表分配器

基于单向链表设计的空闲列表分配器在内存分配时的查询阶段、内存释放时的碎片回收阶段需要对链表进行遍历查找，其复杂度为O(n)。为了降低其复杂度，本文利用双向链表和平衡树，设计了一个O(log n)复杂度的分配器。

数据结构设计    SWAlloc内存分配器同样以内存块的方式管理内存。每个内存块由4部分组成：填充块、元数据块、数据块和剩余块。其中：填充块用来辅助进行内存对齐，元数据块用来存储该内存块的分配信息，数据块为实际返回被应用程序使用的内存，剩余块为本次分配完成后内存块中多余的内存。元数据块与数据块相连，因此元数据块的起始地址与数据块的起始地址满足：元数据块起始地址+元数据块大小=数据块起始地址。每个内存块头部存储该内存块的元数据，包括该内存块的大小、分配状态、对齐信息等，其基本数据结构如图 3所示。这些元数据以双向链表进行连接，以保证其可以进行高效的双向遍历，降低在内存碎片回收阶段的搜索时间。

同时，为了能够在内存分配时快速找出满足待分配内存大小的空闲内存块，分配器采用平衡树维护所有空闲内存块，称为空闲平衡树。不同于空闲列表，空闲平衡树可以在O(log n)的时间复杂度内完成插入或删除操作，从而保证了内存分配与释放的高效性。

内存分配   在内存分配阶段，分配器会通过空闲平衡树查找出大于待分配内存的最小内存块，并通过修改这块内存的元数据，将其设置为已分配状态。数据块的起始地址将被返回给应用程序供应用程序使用。数据块之后多余部分的内存，即剩余块，仍然为空闲状态。如果完成分配后剩余块的大小大于特定值(在本文的配置中为元数据块大小+128 kB)，则剩余块将被设置成一个新的内存块，并被置于未分配状态。新内存块的信息也同时更新到空闲平衡树中。具体算法如图 4所示。

内存对齐   内存对齐对程序的性能有显著影响。在神威平台上，内存需以256 B对齐，才能最大限度地发挥计算性能。为了满足内存对齐的需求，在进行内存分配时，会通过向右偏移的方式将数据块的起始地址进行内存对齐。为了保证元数据块与数据块相连，元数据块将随数据块一起向右偏移，而该内存块中最左侧多出的额外部分以填充块的形式存在。显然，填充块的大小会小于内存对齐的数值，因此不会造成过多的内存浪费。在进行内存释放时，分配器会根据元数据块中记录的填充块大小将其一并释放。

内存释放   在进行内存释放时，应用程序所传入的指针地址为数据块起始地址。分配器将该地址减去元数据块大小，即可得到元数据块的起始地址，从而进一步读取该内存块的所有元数据。接下来，分配器会将该内存块的元数据修改为未分配状态，并写入到该内存块的起始位置，即“元数据块的起始地址-填充块大小”，从而完成内存释放。具体算法如图 5所示。

碎片回收   为了避免内存碎片化从而造成内存浪费，在内存释放时需要考虑内存的碎片回收。在完成内存释放后，分配器将相邻且均处于空闲状态的内存块进行合并。由于使用了双向链表的存储方式，分配器可以方便地找到与刚释放的内存块相邻的2个内存块，将该内存块与其中空闲的内存块进行合并，并将新的元数据更新到其中最靠前的内存块的头部。同时，空闲平衡树中的对应信息也会被更新，合并前的内存块信息被删除，然后加入新产生的内存块信息。

复杂度分析   在进行内存分配时，需要通过查找空闲平衡树来找出大小最适合的内存块，其时间复杂度为O(log n)。若产生了内存块分裂操作，需要进一步维护平衡树中的内存块信息，其时间复杂度也为O(log n)。其余操作复杂度皆为O(1)，因此SWAlloc的内存分配的时间复杂度为O(log n)。

在内存释放时，若产生空闲内存块合并操作，需要对应地更新空闲平衡树中的内存块信息，其时间复杂度为O(log n)。其余操作的复杂度均为O(1)，因此SWAlloc的内存释放的时间复杂度也为O(log n)。

4.2 基于大小感知的双层分配器设计

为了进一步提高内存分配的效率，本文考虑了神威超级计算机上C标准库内存分配器的性能特征和应用程序的内存分配规律，对SWAlloc作了进一步优化。

前文提到SWAlloc具有O(log n)的时间复杂度，为了进一步提高SWAlloc的性能，需要尽量将SWAlloc维护的内存分配量减小。本文通过对应用程序内存分配记录的观察与分析发现，典型的应用程序中大部分的内存分配为较小块的内存分配，只有相对少量的内存分配为大块的内存分配。因此，如果可以根据内存大小将分配方式进行分类，对小块内存和大块内存分别进行处理，即可减少分配器需要处理的内存数量，从而大大提高分配器的效率。由于神威平台上的内存分配器在分配小块内存时非常高效，只有对大块内存分配时才会有严重的性能问题，因此本文设计了一个能够感知内存大小的双层分配器，对于较大的内存，由SWAlloc来分配，而对于较小的内存，则使用神威平台自带的内存分配器。为了避免神威平台自带的C标准库内存分配器中的MMAP影响内存分配的性能，本工作选取C标准库内存分配器动态阈值的最小值，即128 kB，作为SWAlloc的大小感知功能设计中大块内存与小块内存的阈值，从而确保在任意情况下，当SWAlloc的小块内存分配调用C标准库内存分配器时，均使用brk方法进行快速分配。该优化可以显著降低SWAlloc需要管理的内存分配数量，从而降低其时间开销。

4.3 接口与实现

SWAlloc的主要接口包括初始化、内存分配、内存释放3个部分，其定义如图 6所示。

在使用SWAlloc时，用户需要在应用程序开始时进行初始化操作，从操作系统中分配出一块内存供SWAlloc使用，分配的大小由应用程序本身决定。在进行内存分配和释放时，分别通过调用Allocate和Free接口来完成。Allocate需要指定的参数为所需分配的内存大小与内存对齐量，返回一个指向所分配内存(即图 3中的数据块)起始地址的指针；Free的参数为所需要释放的内存(同样为数据块)起始地址指针。

SWAlloc在初始化阶段通过C标准库内存分配器malloc分配一个内存块供应用程序使用，在程序运行过程中调用Allocate和Free接口时，仅在初始化时分配的内存块上进行划分，无须对malloc再次调用，大幅提高了内存分配的效率。初始化过程中通过malloc进行的内存分配仅需要在整个应用程序运行过程中调用一次，其时间开销可以忽略不计。

5 实验

为了验证SWAlloc的效率，本文从多个角度对其性能进行了评测，并与C标准库中的内存分配器malloc进行了对比。测试主要分为4个部分：第1部分测试不同分配器在分配不同大小内存时的效率；第2部分测试不同分配器在真实应用“八卦炉”中的效率；第3部分测试不同分配器在不同内存驻留数量下的效率；第4部分测试不同分配器在标准测试集PARSEC^[4]中的运行效率。

5.1 实验配置

本节实验均在新一代神威超级计算机上进行，使用申威26010-pro处理器，运算控制核心主频为2.10 GHz。

在真实应用和标准测试集PARSEC中的实验，本文使用重放的方法测试不同内存分配器的效率，分别在程序执行过程中采集内存分配记录，并在神威平台重新执行记录内容，以测试内存分配执行时间。

5.2 分配不同大小的内存块的效率

首先测试不同内存分配器在神威平台上分配不同大小内存的性能。测试实验中的分配内存大小为4 B~128 MB，分别测试分配和释放各64次，取运行时间的平均值。每次分配、释放前分配器均无任何驻留内存。实验结果如图 7所示。可以看到，在分配较小块内存时，SWAlloc的性能和C标准库中malloc性能相近。在分配大块内存时，SWAlloc的性能显著优于malloc。在分配大小为128 MB的内存块时，SWAlloc带来的性能提升可以达到92 305倍。

5.3 真实应用中的表现

为了验证SWAlloc在真实应用中的加速效果，本文选用了超大规模机器学习训练框架“八卦炉”(BGL)作为实验对象，以验证不同内存分配器在内存分配过程中的性能表现，并对比了端到端的加速效果。

本实验分别采用隐层大小为3 072和6 144的两个模型，记作BGL-3 072和BGL-6 144。在训练过程中记录5个迭代的内存记录，记录过程不包括初始化操作。然后，在神威平台上使用不同的内存分配器进行重放，并计算每个迭代的运行时间，测试结果如图 8a所示。可以看到，相比于C标准库中的内存分配器，由于机器学习应用中存在大量的大块内存分配，SWAlloc可以取得4~5个数量级的性能提升。同时，相比于空闲列表分配器和不使用双层分配策略的SWAlloc，使用双层分配算法也可以显著提高内存分配效率。

在端到端测试实验中，本文记录了训练过程中每个迭代内除去内存分配以外的运行时间，并结合前面得到的内存分配时间，计算出不同分配器在每个迭代的端到端运行时间，实验结果如图 8b所示。可以看到，使用SWAlloc之后，内存分配不再是训练的性能瓶颈，在BGL-3 072和BGL-6 144两个模型中，分别可以达到78.96倍和88.44倍的端到端加速比。

5.4 不同内存驻留数下的分配性能

本实验针对不同的驻留内存块个数进行测试。测试中首先生成固定数量的内存分配，作为驻留内存，之后进行1 000 000条1∶1的随机分配和释放，以保证测试过程中内存驻留数保持稳定。测试中，分配内存大小在1 B~8 MB随机均匀分布长度，驻留数分别为256、512、1 024、2 048、4 096、8 192、16 384个。

实验结果如图 9所示。可以看到，SWAlloc可以有效提高内存分配效率，在驻留内存块个数为16 384时，相比于C标准库中的内存分配器，SWAlloc可以将内存分配性能提升至多94.21倍；相比于空闲列表分配器，SWAlloc可以将内存分配性能提升至多317.9倍。由于随机测试中内存分配的大小为随机生成，小块内存与大块内存的数量基本相当，因此双层设计的SWAlloc相对于未使用双层设计的SWAlloc并没有明显的性能提升，但在实际应用中，一般情况下小块内存的数量会远远大于大块内存的数量。

5.5 标准测试程序下的性能

本实验在神威平台针对标准测试集PARSEC中的内存记录进行重放测试，实验结果如图 10所示。可以看到，相比于空闲列表分配器和不使用双层设计的SWAlloc，SWAlloc在所有测试程序中均表现出了更好的性能，有效证明了SWAlloc及双层分配策略的效果。同时，相比于C标准库中的malloc，平均得到了36.04%的性能提升。在SW Alloc性能差于C标准库中的malloc的程序中，SWAlloc的性能下降最大为31.54%，而在SWAlloc性能优于malloc的程序中，性能提升最高为51.12倍。因此，SWAlloc对通用程序同样具有较强的适用性，且相比于C标准库中的内存分配器，在特定情况下能取得巨大的性能提升。

6 总结

本文基于新一代国产神威超级计算机设计了一个高效的内存分配器——SWAlloc。SWAlloc可以使超大规模机器学习训练框架八卦炉的内存分配速度提升最高达75 839倍，端到端性能提升最高达88.44倍。本文通过随机生成的内存分配记录以及PARSEC中的内存分配记录，验证了SWAlloc的通用性和高效性，在PARSEC中的应用程序上将内存分配效率提升最高为51.12倍(平均提升36.04%)。SWAlloc目前已经布署于新一代神威超级计算机上，并应用于包括SWPytorch、SWTensorFlow等在内的超大规模应用中。该方法还可以应用于x86平台或其他平台，特别是嵌入式设备等内存受限的平台，未来的工作将对此进一步探索。