Transformer/CNN/RNN 时间复杂度的对比

一.矩阵、张量乘法的时间复杂度

一个形状为 [公式] 的矩阵，与另一个形状为 [公式] 的矩阵相乘，其运算复杂度来源于乘法操作的次数，时间复杂度为 [公式]

二. 具体网络

Self-Attention

[公式]

  • [公式]
  • 相似度计算 [公式] ： [公式] 与 [公式] 运算，得到 [公式] 矩阵，复杂度为 [公式]
  • softmax计算：对每行做softmax，复杂度为 [公式] ，则n行的复杂度为 [公式]
  • 加权和： [公式] 与 [公式] 运算，得到 [公式] 矩阵，复杂度为 [公式]

故最后self-attention的时间复杂度为 [公式]

对于受限的self-attention，每个元素仅能和周围 [公式] 个元素进行交互，即和 [公式] 个 [公式] 维向量做内积运算，复杂度为 [公式] ，则 [公式] 个元素的总时间复杂度为 [公式]

Multi-Head Attention

[公式]

对于multi-head attention，假设有 [公式] 个head，这里 [公式] 是一个常数，对于每个head，首先需要把三个矩阵分别映射到 [公式] 维度。这里考虑一种简化情况： [公式] 。(对于dot-attention计算方式， [公式] 与 [公式] 可以不同)。

  • 输入线性映射的复杂度： [公式] 与 [公式] 运算，忽略常系数，复杂度为 [公式] 。
  • Attention操作复杂度：主要在相似度计算及加权和的开销上， [公式] 与 [公式] 运算，复杂度为 [公式][公式]
  • 输出线性映射的复杂度：concat操作拼起来形成 [公式] 的矩阵，然后经过输出线性映射，保证输入输出相同，所以是 [公式] 与 [公式] 计算，复杂度为 [公式]

故最后的复杂度为： [公式]

注意：多头的计算并不是通过循环完成的，而是通过 transposes and reshapes，用矩阵乘法来完成的。假设有 [公式] 个head，则新的representation dimension： [公式] 。因为，我们将 [公式] 的矩阵拆为 [公式] 的张量，再利用转置操作转为 [公式] 的张量。故 [公式] 的计算为： [公式] 与 [公式] 做计算，得到 [公式] 的张量，复杂度为 [公式] ，即 [公式] 。注意，此处 [公式] 实际是一个常数，故 [公式] 复杂度为 [公式] 。

Recurrent

[公式]

  • [公式] ： [公式] 与 [公式] 运算，复杂度为 [公式] ， [公式] 为input size
  • [公式] ： [公式] 与 [公式] 运算，复杂度为 [公式]

故一次操作的时间复杂度为 [公式] ， [公式] 次序列操作后的总时间复杂度为 [公式]

Convolution

注: 这里保证输入输出都是一样的，即均是 [公式]

  • 为了保证输入和输出在第一个维度都相同，故需要对输入进行padding操作，因为这里kernel size为 [公式] ，（实际kernel的形状为 [公式] ）如果不padding的话，那么输出的第一个维度为 [公式] ，因为这里stride是为1的。为了保证输入输出相同，则需要对序列的前后分别padding长度为 [公式] 。
  • 大小为 [公式] 的卷积核一次运算的复杂度为： [公式] ，一共做了 [公式] 次，故复杂度为 [公式]
  • 为了保证第二个维度在第二个维度都相同，故需要 [公式] 个卷积核，所以卷积操作总的时间复杂度为 [公式]

三.参考

3+

模型并行训练

算是自己经常使用的两种方法吧，其他的非分布式的方法就不介绍了。

一. PyTorch

torch.distributed，分配n个进程，分别运行在n个GPU上

  • 单机多卡：CUDA_VISIBLE_DEVICES=0,1,2,3 python -m torch.distributed.launch –nproc_per_node=4  ––master_port=29501 main.py （最好指定端口，否则出现端口被占用）
  • 多机多卡：
    • 机器1: CUDA_VISIBLE_DEVICES=0,1,2,3 python -m torch.distributed.launch –nproc_per_node=4 –nnodes=2 –node_rank=0 –master_addr=”156.132.1.2″  –master_port=1234 main.py
    • 机器2: CUDA_VISIBLE_DEVICES=0,1,2,3 python -m torch.distributed.launch –nproc_per_node=4 –nnodes=2 –node_rank=1 –master_addr=”156.132.1.2″  –master_port=1234 main.py

参考：pytorch DistributedDataParallel多卡并行训练 torch.distributed(该页末尾) 当代研究生应当掌握的并行训练方法（单机多卡）

二. Tensorflow

使用horovod

  • 单机多卡：horovodrun -np 8 -H localhost:8 python run_classifier.py
  • 多机多卡：
    • 机器1:  horovodrun -np 16 -H localhost:8,172.31.60.175:8  python run_classifier.py
    • 机器2: horovodrun -np 16 -H 机器1的ip:8,172.31.60.175:8  python run_classifier.py

参考：private_bert

Difference between hvd.rank() and hvd.local_rank()

 

2+

shell 字符串处理

一. 字符串截取

1. 关键字(词)截取

  • # 号截取，删除左边字符，保留右边字符
var=http://www.aaa.com/123.htm
echo ${var#*//} # 从左边开始删除第一个 // 号及其左边的所有字符
# 输出为 www.aaa.com/123.htm
  • ## 号截取，删除左边字符，保留右边字符
var=http://www.aaa.com/123.htm
echo ${var##*/} # 从左边开始删除最后（最右边）一个 / 号及其左边的所有字符
# 输出123.htm
  • %号截取，删除右边字符，保留左边字符
var=http://www.aaa.com/123.htm
echo ${var%/*} # 从右边开始，删除第一个 / 号及其右边的字符
# 输出 http://www.aaa.com
  • %% 号截取，删除右边字符，保留左边字符
var=http://www.aaa.com/123.htm
echo ${var%%/*} # 从右边开始，删除最后一个（最左边） / 号及其右边的字符
# 输出 http:

2. 定位截取

  • 从左边第几个字符开始，及字符的个数
var=http://www.aaa.com/123.htm
echo ${var:0:5} # 0 表示左边第一个字符开始，5 表示字符的总个数
# 输出 http:
  • 从左边第几个字符开始，一直到结束
var=http://www.aaa.com/123.htm 
echo ${var:5} # 5 表示左边第6个字符开始，一直到结束。 
# 输出 //www.aaa.com/123.htm
  • 从右边第几个字符开始，及字符的个数
var=http://www.aaa.com/123.htm 
echo ${var:0-7:3} # 0-7 表示右边算起第七个字符开始，3 表示字符的个数
# 输出 123
  • 从右边第几个字符开始，一直到结束
var=http://www.aaa.com/123.htm
echo ${var:0-7} # 从右边第七个字符开始，一直到结束
# 输出 123.htm

二. 字符串拼接

  • 字符串与字符串的拼接
echo "111""222"
# 输出 111222
  • 字符串与变量拼接
var="aaa"
echo "111"${var}
# 输出 111aaa

echo "111${var}" 
# 输出 111aaa
  • 变量与变量拼接
a="123"
b="456"
echo $a$b
# 输出 123456

三. 参考

0