SwapAdvisor

papers deep learning swap
发布时间 :
阅读 : 评论:
  1. Reference & Notations
  2. Abstract
  3. Introduction
  4. Background
  5. Challenge and Our Approach
    1. Our approach
  6. SwapAdvisor Design
    1. Operator Schedule and memory allocation
      1. Operator schedule
      2. Memory allocation
    2. Swap planning
      1. Which tensors to swap out?
      2. When to swap in and out?
  7. Optimization via Genetic Algorithm
    1. Algorithm overview
      1. Selection methodology.
    2. Creating new schedules
      1. Encoding
      2. Crossover
      3. Mutation
    3. Creating new memory allocation
      1. Encoding
      2. Crossover
      3. Mutation
  8. Evaluation
    1. Experimental setup
      1. Prototype implementation
      2. Testbeds
      3. Genetic algorithm parameters
      4. Evaluated DNN models
      5. Baselines
    2. Wider and deeper DNN model training
      1. RNN performance
      2. CNN performance
      3. Comparing with TFLMS
    3. DNN models inference evaluation
      1. 低端机器上的推理
      2. 分时复用GPU算力
    4. The effectiveness of SwapAdvisor’s design choices
      1. the effectiveness of scheduling and memory allocation.
      2. the performance of the genetic algorithm
    5. Simulator accuracy
  9. Related Work
  10. Discussion, limitations and future work
    1. Dynamic dataflow graph
    2. Multi-GPU Support
    3. Alternative search methods.
  11. Conclusions
  12. References
  13. Questions

Reference & Notations

Item Instructions
Title SwapAdvisor: Push Deep Learning Beyond the GPU Memory Limit via Smart Swapping
Authors Chien-Chin Huang, GuJin, Jinyang Li
EuroSys’18 TensorFlow’s swap extension swap工作，没有利用DNN中已知的flow信息来优化swap
arXiv’18 TFLMS, MICRO’16 vDNN swap工作，仅交换了根据拓扑排序确定的激活Tensor
PPoPP’18 SuperNeurons swap工作，仅交换了卷积操作的数据
GA Genetic Algorithm: 启发式算法，能利用多核GPU做并行计算（快）
Np 超参：遗传算法中种群的大小
TS 数据流图中的排序后的不unique tensor sizes

Abstract

支持swap GPU和CPU内存，可以训练更大的模型，但是现有工作只支持特定models，并且不能达到满意的性能。

SwapAdvisor从3个维度做优化：

  1. Operator scheduling
  2. Memory allocation
  3. Swap decisions

此外，SwapAdvisor还设计了一个算法来搜索方案。

Evaluation部分评测了很多种类的大模型，表明SwapAdvisor最多可以训练12x于显存大小的模型，并且能达到相比于无限显存的53%~99%性能。

Introduction

对于训练大模型的现有工作的解决方法：

  1. 低精度/压缩： 可能影响模型精度，引入额外超参数
  2. 时间换空间： 对于大模型，模型参数重新计算开销很大
  3. swap memory between CPU and GPU

以下3点利好方法3：

  1. CPU memory 相比于 GPU memory大得多，便宜的多。
  2. 现代GPU可以高效overlap计算与通信
  3. CPU-GPU之间的通信变快：PCI-e 5.0， NVLink

DNN中swap 与传统swap的优势：执行前清楚DNN的计算结构，可以最大化overlap计算和通信

之前Swap工作的缺陷：

work weakness
TensorFlow’s swap extension 没利用事先清楚DNN计算结构的优势
TFLM, vDNN 仅交换了activation tensors
SuperNeurons only swap data for convolution operations
summary 限制了DNN种类与性能

设计了SwapAdvisor：用有限的显存可以训练与推理多种大模型。在执行前决定何时+哪些数据需要交换。

决策需要考虑的信息：

  1. dataflow graph
  2. operators scheduling
  3. memory allocation

搜索空间很大，设计了一个算法来搜索。

应用于训练的意义：训练12x于显存大小的模型。性能达到理论无限大显存下的53%-99%（有意思，baseline的性能咋测试的？）

应用于推理的意义： 推理的时候单张卡内会放多个推理模型，当所有模型的占用显存和相加超过物理显存的时候，会采用时分复用的策略。SwapAdvisor提供的方法相比于时分复用有4x lower latency.

SwapAdvisor的限制：

  1. 需要一个没有control-flow primitives的静态数据流图。
  2. 仅支持single GPU

Background

DNN内存消耗三大门户：

  1. Model Parameters. (本文中认为是此占据大部分的内存)
  2. Intermediate results: activation, gradient, error tensors. 其中推理时仅有activation
  3. Scratch space(辅助空间): 一些算子计算的时候需要申请额外空间完成计算，例如conv。但是最多占用1G，不大。

Challenge and Our Approach

仅根据data flow graph来决策是不够的，还需要考虑：

  1. Memory allocation. 例如MXNe中使用内存池来管理，会提前分配很多固定大小的空间。所以当剩余显存足够，但是剩余的对应固定大小空间的tensor不够，也需要做swap。结论：需要小心配置内存池。
  2. Operator scheduling. data flow graph中有分支、合并、循环等，而不是一条链。

Parameters: 前向计算不修改，所以swap出去的时候不需要复制到CPU memory中。
Activations: 由OP计算得到，所以swap进来的时候直接分配一块空间即可，不需要从CPU拷贝；但是swap出去的时候，必须一直保存在CPU memory中，因为反向会用到。

Our approach

  1. 在给定dataflow graph, memory allocation scheme, operator schedule后，可以给出一个swapping plan(即：确定哪个tensor什么时候被swap in/out)
  2. 穷举所有可能的allocation scheme + operator schedule组合。
  3. 用simulator估计swapping plan的实际性能

SwapAdvisor Design

overview图

随机选一个operator scheduling & memory allocation, 不断做optimize。

Operator Schedule and memory allocation

Operator schedule

定义：无环数据流图G中，对G中节点的一个拓扑排序序列。根据序列中的前后关系决定节点的执行先后。

SwapAdvisor用了3个streams：

  1. GPU execution
  2. GPU memory -> CPU memory
  3. CPU memory -> GPU memory

Memory allocation

定义：预留大小的种类，G中每个tensor对应预留多大。

Togo: 似乎有的时候一个tensor可以对应多个预留大小。例如正常的时候1MB应该对应1MB预留大小，但是在1MB空间不够，2MB空间足够的情况下，可以临时用2MB的空间，而不用swap。

Swap planning

定义：which tensors to swap and when?

Which tensors to swap out?

假设大小为s的tensor对应的预留大小是s’。
当需要在内存中增加一个大小为s的tensor时候，若不存在空闲的s’大小的预留空间，则从当前占用了s’的所有tensor中选择一个距离下次使用时间最长 并且 最近一次使用与当前时间相隔超过某阈值(不然无法做overlap)的，做swap-out操作。

double-pass:

  1. first pass: 一开始所有parameters均在CPU中，结束后有部分parameters’留在了GPU中。
  2. second pass：一开始在first pass中留到最后的parameters’预加载到GPU中；扫描过程中因为内存压力，可能会将部分parameters’移出GPU（记作parameter’’）。最终parameter’ - parameter’’则是常驻GPU的参数，雷打不动，不参与swap的。

double-pass的意义：衔接DNN训练中前后两个iteration。

When to swap in and out?

越早越好，还得保证安全。
如何保证安全？添加一条control flow edge.

Optimization via Genetic Algorithm

Algorithm overview

交叉：一对父母 $\rightarrow$ 4个孩子（2 new schedules x 2 new allocations)

变异：1个孩子 $\rightarrow$ 另1个孩子

选择：很多个孩子 $\rightarrow$ $N_p$个孩子作为下一代

Selection methodology.

选取表现最好的若干孩子的问题：失去多样性，过早收敛。
表现定量化（simulator） $\rightarrow$ 正则化 $\rightarrow$ 通过softmax得到每个个体对应的存活概率（表现好的存活概率大）

选择softmax的原因 ：实验表明并其他的selection方式有更好的稳定性。

Creating new schedules

Encoding

将schedule编码：就是将每个节点按顺序排列(SCH)。

Crossover

CR：图中灰色虚线前面有几个节点，图中CR=3.

解释如何得到$SCH_{C1}$:

  1. 照搬$SCH_2$的前3个
  2. $SCH_2$剩下的节点，按照$SCH_1$的相对顺序排序，填充$SCH_{C1}$的剩余部分。

具体解释：234|51如何变成234|15？
234不变，51根据12543中的order重排序变成15，结合得到234|15

Mutation

有1-P的概率按照原来的schedule取下一个，有P的概率从就绪的node中选下一个。选完为止。

Creating new memory allocation

Encoding

memory allocation:

  1. how to map size to a size class(有多少类size)
  2. how many objects to assign to each size class(每类size有多少个)
Notations Meaning
TS the sorted list of unique tensor sizes observered in the dataflow graph
CLS CLS[i]表示TS[i]对应第CLS[i]个size class
CNT CNT[i]表示第i个size class对应预先分配CNT[i]个
N len(TS)

一些性质，帮助理解：

  1. len(CLS) == len(TS)
  2. number of size-classes == Max(CLS) == len(CNT)

令CLS非递减，则可将CLS的搜索空间从O($N^N$)降低到O($2^N$)

Crossover

  • $TS$=[1MB, 2MB, 3MB, 4MB]: 表示有4种tensor sizes:
  • $CLS_1$ = [1,1,1,1]: 1/2/3/4MB $\rightarrow$ 4MB
  • $CNT_1$ = [4]: 预先分配4个4MB的空间
  • $CLS_2$ = [1,2,2,2]: 1MB $\rightarrow$ 1MB; 2/3/4MB $\rightarrow$ 4MB
  • $CNT_2$ = [8,1]: 预先分配8个1MB, 1个4MB
  • $CNT_{EXT_1}$ = [4,4,4,4]:
  • $CNT_{EXT_2}$ = [8,1,1,1]

解释：

  1. 扩展$CNT$到$CNT_{EXT}$
    • $CNT_{EXT_1}$ = [4,4,4,4]:
    • $CNT_{EXT_2}$ = [8,1,1,1]
  2. 选取分割点，CR=2
  3. 交叉
    • $CNT_{EXT_{C1}}$ = [8,1,4,4]
    • $CNT_{EXT_{C2}}$ = [4,4,1,1]
  4. 对应到同一个size-class的CNT做平均
    • $CNT_{C1}$ = [8,3]: 结合$CLS_{C1}$=[1,2,2,2], 第1个size-class对应[8]，第2个size-class对应[1,4,4]，做平均得到[8,3]
    • $CNT_{C2}$ = [4,1]
  5. 按照对应size-class大小成反比的方式修改对应元素大小
    • $CNT_{C1}$ = [4,2]: 原来时[8,3]，这里1MB对应的$8\rightarrow4$，少了4个; 4MB对应的$3\rightarrow2$，少了1个; 1MB对应少4个与4MB对应少1个，成反比关系。换个说法：[8,3]对应的内存占用为$81+34=20$, 假设的物理内存为12（MB），需要降低8MB。平均分配，1MB和4MB均需要降低4MB的占用，那么1MB需要减少4个，4MB需要减少1个。
    • $CNT_{C2}$ = [4,1]

Mutation

  1. CLS/CNT： 依次扫描，对每个元素，有P的概率突变，1-P的概率保持不变
  2. CLS： CLS[i]==CLS[i-1] —> CLS[i]++ ; CLS[i] == CLS[i-1]+1 —> CLS[i]—
  3. CNT: 以CNT[i]作为均值，做高斯分布，随机取值，大概率取一个邻近值，小概率取一个偏远值

Evaluation

评估对象：throughput。
评测结果：

  1. 训练部分：达到理想baseline的53%-99%
  2. 推理部分：latency 4x（应该是75% lower）
  3. Joint Optimization相对于仅搜索memory allocation/scheduling来说，有20%-1100%的性能提升。

Experimental setup

Prototype implementation

基于MXNet，修改了stream部分，替换了memory allocator。 GA与simulator采用python实现，GA支持CPU并行。

Testbeds

item hardware
run SwapAdvisor 72 virtual CPU cores, 144GB memory
train with produced plan V100 16GB x1, 8 virtual CPU cores, 61GB memory, PCIe: 12GB/s单向+20GB/s双向

注：对需要超过61GB内存的，作者转而换了有更大内存的instance做实验，但是只用了一个GPU。（可能为了省钱吧）

Genetic algorithm parameters

所有参数都是手动调参出来的（empirically）。
详见论文。

  1. 线程数=144：对应72 CPU cores
  2. 突变概率P=10%：一般10%比较好，不同的模型对应的P不同，那来一个新模型，我怎么晓得哪个P？
  3. 搜索时间： 30分钟。

Evaluated DNN models

Table1
Model MemUsage OPs tensorSizes batchsize
WResNet-152-10 180GB 882 26 64
Inception-4 71GB 830 64 64
NasNet-25 193GB 5533 65 64
RNN-8-8K 118GB 8594 7 256
BRNN-4-8K 99GB 9034 9 128

Baselines

  1. ideal: 当显存不够，直接原地替换，不考虑计算正确性。可以得到基于swap系统的性能上限。
  2. ODSwap：即时决策，第一轮用LRU的方式对tensor做swap，得到swap策略后，应用到随后的训练。

Wider and deeper DNN model training

RNN performance

Figure6a & Figure6b:

  1. SwapAdvisor达到了理想性能的70%~80%
  2. ODSwap表现很差

分析了了下原因：
对于RNN与BRNN模型，同一个layer中的LSTM cells共享一份parameter tensors。MXNet默认的schedule是随机生成一个topoligical ordering，会执行不同layers的LSTM cells，导致很差的swap性能。

Togo: 原因还不懂

CNN performance

Figure6c & Figure6d & Figure6e:

  1. WResNet
    • 虽然显存占用很大（180GB），但是表现都挺好
    • SwapAdvisor达到了理想性能的95%
    • ODSwap达到了理想性能的80%。
    • 只有26个tensor sizes，做memory allocation更简单
    • 数据流图像一条直线（加一些Residual旁路），所以做schedule也很简单（意思就是不会随便选性能也不会差）
  2. Inception-4 & NasNet-25
    • 60多个tensor sizes，更复杂的数据流图
    • SwapAdvisor相对ODSwap有20%-150%的性能提升。
    • 当batchsize=16比较小的时候，SwapAdvisor达到了理想性能的80%，但是当batchsize=64时，SwapAdvisor的表现下降。
    • 分析了当batchsize增大时，表现下降的原因：当batchsize=64时，两个模型都有很大的ACTVITION数据（>500MB），加上还有60多个tensor sizes，使得很难去搜索出一个较好的memory allocation；同事NasNet-25的数据流图非常复杂，使得很难搜索较好的schedule。
    • 图中最差的表现组，SwapAdvisor仍然达到了理想性能的53%（NasNet-25， batchsize=64）

ResNet-152的data flow graph

Comparing with TFLMS

TFLMS：TensorFlow的一个插件，使TF支持swap。

但是TFLMS对于Figure6中的所有模型均不支持，所以只测试了WResNet-152-4.

TFLMS表现很差，因为它不支持swap parameter tensors（在WResNet-152-4中很大），TFLMS只支持交换activation tensors

DNN models inference evaluation

粗体：得用swap才能运行
斜体：运行时间与理想时间相差不超过1%。

低端机器上的推理

基本上就对应Table2中的batchsize=1的组别，可以用swap advisor来大大降低显存占用量。

分时复用GPU算力


将GPU的显存划分成多分，采用SwapAdvisor技术以使得划分后的单块显存能塞下整个模型。
假设：任务到达时间成泊松分布。

  • not shared: GPU中只保存一个ResNet-152模型
  • time share: 分时复用计算与内存
  • swapadv： 只分时复用计算，显存做partition

实验结果：

  1. 当吞吐量小于400task/s时，SwapAdvisor的延迟比理想最多2x slower
  2. 当吞吐量==300task/s时，not shared组别的延迟比理想慢8x（很差）

The effectiveness of SwapAdvisor’s design choices

the effectiveness of scheduling and memory allocation.

  • 需要同时考虑scheduling与memory allocation才能取得最好的效果。
  • 不同模型对于scheduling与memory allocation的依赖程度不一样。

the performance of the genetic algorithm

  • 100s 收敛
  • 最好与最差之间始终有距离，表示samples之间有足够的多样性（有多样性，遗传算法才能有效果）
  • Figure9c相对Figure9b证明了限制CLS非递减的作用。

Simulator accuracy

总之，结果就是很准

Togo: 有本事开源

Related Work

Discussion, limitations and future work

Dynamic dataflow graph

目前仅支持静态图。

Multi-GPU Support

  1. 数据并行：对于单机n卡，将GPU-CPU的带宽降低为原来的1/n即可
  2. 模型并行：不支持，也不好扩展

    Alternative search methods.

    Togo: 也就是为什么选择遗传算法。

  • 比模拟退火快得多
  • Empirically, 她工作的很好
  • 可以探索其他方式，例如强化学习
  • GA的使用会引入一些限制，例如限制我们用静态内存池，而用不了dynamic allocator

Conclusions

References

Questions

  1. 用作评估Swap Plan的Simulator，根本没提怎么实现。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。

©2021 zzqq2199

Built with Hexo and 3-hexo theme