浅谈端上智能之计算优化

2022-05-11 07:20:45

一、背景 - 边缘智能

人工智能（Artificial intelligence）的迅速发展正在改变世界。以深度学习（Deep learning）为驱动力和代表的第三波AI浪潮，正在变革和赋能金融、制造、农业、交通、医疗、零售、教育等众多行业，同时也极大地影响着我们每个人的生活。当前，在移动设备上各种新的AI应用场景正在不断涌现。大量新的需求对端上的智能能力提出了新的挑战，也带来了新的机遇。今天，得益于AI技术的巨大突破与进步，我们可以与设备像人一样通过语音、手势等方式沟通，扫一下人脸即可确定身份进行支付，穿戴式设备可分析健康状况并给出建议，系统可以根据用户的使用习惯自动优化，汽车会检测识别周围环境给出指引或者自动驾驶。这样的应用还有许许多多。所有这些，背后都离不开AI的助力。

过去几年将智能计算放于云上的方式被广泛采用，即智能强依赖云端。这几年随着移动设备硬件能力飞速提升及智能需求井喷，边缘计算开始兴起。机器学习模型在服务器上训练好后可以被部署到端设备上，执行过程不依赖云端，从而很大程度地改善了用户体验。在不侵犯隐私的前提下，使用过程中产生的数据又可以帮助改善模型的效果，最终构成一个良性的智能闭环。总得来说，端上智能具有以下优点：

降低延迟：避免了与服务器沟通所带来的延迟，可以保证实时性。这在像ADAS等对实时性要求极高的场景下尤为重要，因为如果慢一些可能人就已经凉了。
不依赖网络：计算在本地完成，因此不受网络质量影响。像手机、车等移动设备因环境变化往往不能保证网络一直高质量可用。
保护隐私：数据不需要离开设备。对于像聊天记录、照片等隐私信息能得到充分地保护。
个性化：可以根据个体用户的特性和习惯进行适配，做到千人千面，提高用户粘度。
成本可伸缩性：计算如果放在服务器端，服务器的成本可能会随着用户的增长而同比增长。如果放在移动端上计算则不会有这个问题。

也正是由于边缘智能计算具备这些优点，使它成为业界的热点。但是，在带来机遇的同时，它也带来了巨大的挑战。这些挑战主要来源于边缘设备的资源限制，如计算速度、存储与功耗等。

二、基本问题 - 算力之殇

在过去几年里，深度学习在视觉、自然语言处理、语音识别、推荐、智能控制等领域获得了许多重大的突破，并在很多的专项上超越了人类水平。我们知道，深度学习有三大基石：数据、算法和算力。大数据的兴起为AI提供了契机，深度学习的主要优势之一就是能基于大量数据进行学习。算法则提供了处理数据和从数据中进行学习的有效方法。而要对大量数据和复杂的网络进行计算，需要强大算力的支撑。而某种意义上来说它们之间有一些互补关系。如随着近几年AutoML的火热，人们发现让机器搜索网络架构可以找到比人工设计更优的方案。Google的大神Jeff Dean（对，就是编译器从不给他警告，只有他给编译器警告的那位）就曾经表示：未来谷歌可能会用100倍的计算能力，取代机器学习专业知识。换句话说，如果拥有足够的算力，可以替代很大部分算法设计。

这就引出一个问题，多少的算力是足够的？这个问题估计谁也没法给出一个准确的答案，但我们可以通过一些数据侧面感受下。OpenAI发布的分析表明：自2012年，也就是深度学习爆发以来，人工智能训练任务中使用的算力呈指数级增长，其目前速度为每3.5个月翻一倍。相比之下，摩尔定律中芯片性能翻倍的速度是18个月。2012年来人们对于算力的需求增长了超过30万倍。另外，随之而来的能耗和成本问题也不容小视。据美国马萨诸塞大学研究人员表示，训练一个经典的Transformer网络，碳排放180吨，相当于把三辆汽车从全新用到报废。当然，这里是训练时所需的算力，移动端上因为大多只需要推理，其算力需求会小得多。我们以比较热门的自动驾驶来举例。自动驾驶汽车为了完成周围环境的感知，需要处理从camera、radar、LIDAR等一系列传感器来的数据。Intel CEO Brian Krzanich曾在一次大会keynote中称：估计到2020年，一辆自动驾驶车每天大约会产生4TB的数据。而这些数据很多是需要实时处理的。要处理如此大量的数据，其算力需求可想可知。Imagination汽车市场总监Bryce Johnstone表示：自动驾驶级别每升高一级，对计算力的需求至少增长十倍。第五级全自动驾驶，可能需要500TOPS以上计算力。而作为“低配版”自动驾驶的ADAS，根据功能的不同，也需要10到100+GFLOPS的计算力。

这几年，机器学习学术研究空前繁荣。Jeff Dean就曾发推给出数据：根据对arXiv上论文的统计，到2018年底，平均每天产生100篇。难怪有种论文读不过来的感觉。。。然而，与学术界遍地开花的一派繁荣景象相比，工业界落地难的尴尬境地困扰着不少业内人士。不少AI产品停留在PPT和概念演示阶段，然后，就没有然后了。。。其中最大的阻碍之一就是端上的计算资源有限，难以支持多样的、实时的AI相关计算任务。

以深度神经网络（DNN）为代表的AI计算任务，本质上是推动了边缘设备计算模式的转变。传统的移动端基本以I/O密集任务为主，偶尔来个计算密集任务可能用户就会觉得发烫，是不是哪里出问题了。而DNN的推理一次就动不动几十亿次运算，而且还是周期性高频率运行，外加系统中可能还有多个DNN同时运行，这传统的玩法根本扛不住。因此，我们的核心问题是算法需求与边缘硬件算力之间的矛盾。而且这个矛盾很可能会长期存在。就像之前的Andy and Bill’s Law，即便算力大幅度提升，市场会出现更多的场景需求，更高的准确率要求把这些增长的算力吃掉。注意算力还与存储、能耗等资源密切相关，因此在移动端性能优化的目标除了耗时外，还包括内存占用及功耗等等。

三、解决方向 - 希望之光

要解决上一节提到的问题，缓解算法需求与移动端算力的矛盾，业界有几个基本思路：

给定算法模型如何让它跑得快
1. 设计牛X的专用硬件
2. 结合硬件做深度计算优化
3. 通过调度提高硬件利用率
给定准确率目标如何让模型尽可能简化
1. 如何设计更轻量化的网络结构
2. 给定模型的情况下其计算量是否必要（不是的话如何压缩）

下面分别就这几个思路稍作展开。

1. 神经网络芯片 - 软件定义芯片

以DNN为代表的现代流行机器学习模型在端上的大量应用带来了计算模式的变化。DNN中的典型计算（如矩阵乘加）普遍有逻辑简单，计算量大，且反复计算的特点。这种计算模式的变化推动了芯片的发展与变化。目前主要的挑战来自两个方面：

摩尔定律的失效：1965年英特尔联合创始人戈登·摩尔提出了著名的摩尔定律：当价格不变时，集成电路上可容纳的元器件的数目，约每隔18-24个月便会增加一倍，性能也将提升一倍。半导体行业在这个定律的推动或者说引导下发展了50多年。然而，物理元件不可能无限缩小。当晶体管体积到达物理极限，该趋势将难以为继。摩尔定律虽称为定律，但并不是推导出来的科学定律，而是经验法则。今天，就算不能说它完全失效，也可以说是明显地放缓了。
冯·诺依曼瓶颈：现代的主流处理器基于冯·诺依曼架构。在该架构中，计算模块和存储单元互相分离，数据需要从存储器提取，经过处理单元处理后再写回存储器。这些频繁的访存操作造成了延时，也提高了功耗。这种架构优点是通用性，适用于逻辑复杂的计算，但对于像矩阵乘加这种比较特殊的计算，效率并不高。使情况变得更糟的是，摩尔定律加持下的芯片计算性能在过去几十年里迅猛增长，而存储器的性能增长却远不及它，从而形成了处理器与存储器速度的gap。另外，DNN中的计算中涉及大量参数与中间结果，因此需要很大的memory bandwidth。这多种因素使得DNN的计算很多时候的瓶颈在于访存而不是计算。

针对以上挑战，业界进行了各种尝试来克服。我们知道，神经网络的执行很多时候就是在做矩阵计算。既然是非常耗时的特殊计算，那最好的方式就是用专门的硬件（就像编解码芯片），从而达到高性能、低功耗。这种为专门目的而设计的集成电路被称为ASIC。FPGA与ASIC类似，也是用硬件实现软件算法。只是它是一种“半成品”，可以自定义。这几年，各种神经网络芯片可以说是一个接一个，层出不穷。一时间，各种"xPU"横空出世。貌似26个字第都快用完了。。。

本质上，它们大多是为了解决上面提到的根本问题。对于摩尔定律的放缓或者失效，一个自然的路子就是通过并行来提速。CPU经历了从单核到双核再到多核的发展历程，然而毕竟作为通用处理器由于硬件设计上的一些限制无法堆太多核。将并行计算推向大规模的先行者是Nvidia，早在2006年，Nvidia推出了CUDA，非常明智地将之前专用于图形领域的GPU推向通用计算领域，摇身变为GPGPU。2012年，以绝对优势获得ImageNet冠军的AlexNet正是用了CUDA来加速训练。Nvidia随着之后兴起的深度学习浪潮进入了一条快车道，其硬件与软件生态已成为服务器端的绝对主流和标配。与CPU不同，GPU拥有数以千计的核心，能同时做并行任务中的操作。这样其整体性能就可以不受单个核心频率的限制。其局限是只适用于规则的可并行计算任务，对于DNN中的矩阵乘加就非常适合，因此，在深度学习的任务中，GPU的吞吐量可以比CPU高出一个数量级。

然而，GPU毕竟设计之初不是为神经网络专用的，它仍是一个通用处理器。虽比CPU更专用了，但硬件设计仍需考虑一定的通用性，因此也不能做得太激进。这就给了ASIC进一步的发展空间。ASIC因为是专用的，因此可以针对性地进行硬件设计，从而达到极致的能效。与GPU相比，用于神经网络的ASIC芯片的显著特点是一般会有更多的计算单元（如TPU包含65536个8位MAC矩阵乘法单元）。但是，像之前提到的，只考虑计算速度是不够的，很多时候瓶颈在于访存。很多时候我们谈算力指标言必FLOPS，其实这个指标很容易让人误解，似乎只需FLOPS到了一切都妥妥的了。其实由于访存速率的限制很多时候硬件算力只能发挥出一部分甚至是10%不到。在Roofline模型中，由计算平台的算力和带宽上限决定的"roofline"将整个区域分为两个部分-memory bound和compute bound。根据模型在图中的位置可以判断它的瓶颈在哪里。我们发现不少模型，尤其是像MobileNet等轻量级的模型由于计算密度较低大多会落入memory bound区域。也就是说，这种情况下硬件计算速度再快也白瞎。针对访存这块，神经网络芯片一般会在设计上做针对性的优化，比如更大的片上内存（如TPU的有28M）。另外，像有David Patterson（图灵奖获得者）背书的Google出品的TPU为了更大幅度缓解冯·诺依曼瓶颈，让脉动阵列架构重回到舞台。在这种架构下，每次执行乘法运算时，结果会被直接传递给后面的乘法器，并进行求和。在整个过程中，无需访问内存。去除这些访存开销，还会有额外好处，即功耗的降低。我们知道与计算相比，访存才是功耗大户。通过这种方式可以有效提高能效比。

以上只是举些小例子，其它各种神经网络的ASIC也是各显神通，用足了各种优化来克服传统计算方式的缺点。虽然目前这条路子仍然是绝对的主流，但人们同时也开始探索新型的计算形式和计算硬件用于神经网络计算，如：

神经拟态计算：又称脉冲神经网络（SNN）。它来自于大脑的启发。在神经系统中，神经元间通过突触发送脉冲信号，其间的连接可能被抑制或是被强化。神经信息被认为是通过神经元的触发频率来编码的。相比之下，传统方式则需要较大的memory来存储模型权重。相关的研究包括IBM的True North、Intel的Loihi、BrainChip的Akida NSoC和清华大学等机构提出的天机芯片架构。
光学计算：虽然光纤可以以光的形式传输数据，但最终要分析这些数据时，需要进行光-电转换后再进行处理。MIT的研究者提出了一种使用光子技术实现神经网络的方法。这种可编程纳米光子处理器用光来执行人工智能算法的计算。德国明斯特大学物理研究所的研究者提出了一种在光子芯片上实现的全光学神经网络。使用基于光学计算的方法在加速和能耗方面都会有很大的优势。
量子计算：量子计算基于量子力学的模型来实现计算。量子计算机的理论基础也是图灵机，它可以实现经典计算机能实现的计算。量子计算的核心优势是拥有指数级的存储和计算能力。因此，它可以使现在很多“不可解”的问题变得可解。这将是颠覆性的，因此也引得大家的极大关注。神经网络作为当前热点之一，自然也是量子计算的应用方向之一。如Google构建了量子神经网络QNN，用于在量子处理器上执行神经网络。

尽管经过科学家们的不懈努力，这些新型的计算方式和硬件的价值已初现端倪，但目前仍主要处在研究阶段。要将它们落地并大规模应用，还需要克服很多困难。而一旦它们技术成熟，那将会是革命性的。

2. 计算实现优化 - 结合硬件特性与能力

很多时候，程序执行符合80/20法则。即80%的时间在跑20%的代码（当然，这里的数是虚指）。对于神经网络来说也不例外。如对于视觉任务中典型的CNN，通常卷积与全连接层会占到总计算量的80%~90%甚至更高。另外像在语音、自然语言理解领域常用的RNN中大量存在LSTM和GRU层，它们本质上也是做矩阵计算。因此很多时候大家做性能优化会focus在矩阵计算上。

抛开实现谈优化意义不大，或者说油水不多。只有考虑与平台硬件结合的深度优化，才能充分挖掘潜在的性能。因此，在计算实现中，需要考虑硬件特性和能力。例如处理器对于不同类型指令性能差异（如大多计算硬件上乘法比加法更耗时和耗能）和存储器层次结构（每一级的延时和能耗都可能相差数量级）。考虑到平台相关的硬件加速能力还有CPU的并行指令、GPU的并行编程等等。

最简单的方法当然是按公式来计算，称为直接法。全连接层其实就是矩阵和向量乘，不用多说。卷积层的定义稍稍复杂一些。为简单先不考虑stride，dilation等特殊卷积，且卷积核size宽高相等。记输入为$X$，其维度为$N \times C_i \times H_i \times W_i$，卷积核为$W$，其维度$C_o \times C_i \times K \times K$，输出为$Y$，维度为$N \times C_o \times H_o \times W_o$，则对输出张量中的每个元素，计算公式为：

$$ Y_{n,c,x,y} = \sum_{m=0}^{C_i - 1} \sum_{u=0}^{K - 1} \sum_{v=0}^{K - 1} X_{n, m, x+u, y+v} W_{c, m, u, v} $$

算法复杂度为$O(N C_i C_o H_o W_o K^2)$。其优点简单粗暴，且几乎无需额外的内存开销。其缺点也是显而易见的，就是效率会比较低。现代计算库一般都会使用一系列的计算实现优化，几个比较典型的如：

Im2col-based：一边是大量卷积计算需求，另一边是几十年来深度优化的成熟的BLAS库。如何将两者连接起来呢？经典的im2col方法将输入矩阵转化成Teoplitz矩阵，这样卷积操作就转化成了矩阵间乘法操作，从而可以作为GEMM利用成熟计算库来加速。但它有个缺点是需要比较大的内存开销来存储临时矩阵。
kn2系：im2col方法虽然可以利用BLAS的GEMM函数加速，但它需要$O(C_iK^2H_iW_i)$的额外存储空间。在移动端设备内存也是很稀缺的资源，有没有可能在享受到BLAS加速的同时又可以占用少一些内存呢。kn2系方法避免了Toepliz矩阵的构建，其基本思想是将卷积分解成为多个矩阵乘用GEMM计算，然后移位后累加。额外内存减少到$O(C_o H_i W_i)$。其代价是更多次的GEMM调用。如果说im2col是拿空间换时间，那这个就是拿时间再换回一些空间。
Strassen algorithm：这个矩阵乘法的优化大家一定不陌生，它也可以被扩展到卷积计算。我们知道，不少看上去还比较intuitive的算法会让人有种“我要是他我也能想出来”的错觉，然而有一些看完则会让人觉得“这怎么想出来的！”。该算法应该就属于后一种。通过一系列tricky的构造，它将分块递归过程中的8个子矩阵乘法干到7个，硬生生将复杂度从$\Theta(n^3)$减到$O(n^{2.81})$。但其代价是会引入一些额外的矩阵加操作，因此在实际使用中需要有条件地使用，如矩阵比较大时。
FFT-based：根据经典的Convolution theorem，空间域上的卷积操作等同于频率域上的乘积。因此，可以将原卷积经过傅立叶变换转到频率域，在频率域经过乘积后再通过逆傅立叶变换转到原空间域。这个过程的计算复杂度为$O(H_iW_i \log (H_iW_i) (C_o C_i + NC_i + NC_o) + H_iW_iNC_iC_o)$。先不要管这式子为毛这么长，总之与前面直接法时间复杂度相比，这里没有卷积核的size了。这非常好，同时这也意味着只有当卷积核越大，它的优势越明显。另外，虽然这里有一来一回域间变换的额外运算，但一方面有快速傅立叶变换助力，另一方面由于每一个输入feature map要被重复使用多次，因此对应的转换可以重用。当然，这也意味着，feature map的通道数越多越适用。
Winograd-based：该方法基于Winograd algorithm。它以更多的加法数量和中间结果乘法数量为代价达到理论上最少的乘法次数。该方法的计算复杂度随着卷积核size平方的速度增长，因此和上面FFT-based方法相反，它主要适用于小的kernel（如3x3）。不过，好在现代主流的神经网络也是以这种小kernel为主，因此被广泛使用。

我们可以看到，就像其它很多计算任务一样，没有一种实现方法是万能的。因此，用时需要根据实际情况来。实际使用中还会有不少坑，如有些方法可能对精度有较大影响，而有些是基于一些硬件特性假设的。因此，如果你尝试了一种看起来非常牛X的计算优化，结果却不尽如人意，不要伤心，不要难过，很可能只是不满足该算法的某些隐式假设。为了避免人肉挑选之苦，业界也有尝试通过自动化的方法来为神经网络中每个卷积选取最合适的实现算法。

还有一类优化是并行优化。对于矩阵乘加这样天然可并行的计算，不并行白不并行。常用的手段有几类：

CPU并行指令：SIMD指令，即一条指令可以操作多个数据。比如对于4个乘法操作，原本要分4个指令，现在一条指令搞定。x86平台上有SSE和AVX指令集，ARM平台上有NEON指令集。当只能用CPU时，这几乎总能给性能带来明显的提升。
多线程：虽没有GPU的大规模并行能力，但CPU也有多核。其并行能力可以通过多线程来利用。我们大多时候不必从头写线程调度，可以依赖OpenMP这样的库，或者更高层的库。
GPU并行编程：这个topic就非常非常大了。比较主流的有CUDA和OpenCL。严格意义上讲两个不是完全平级的东西，虽然都可以指一种并行编程接口。前者是Nvidia家的，是一整个生态，只要用的N卡基本没谁就它了。后者是一个标准，具体由各厂家去实现，最大优点就是跨平台通用（不过也得看各家支持的情况。。。）。

再次回到访存优化的话题。无论是CPU还是GPU，都存在存储器层次结构（memory hierarchy）的概念。对于这个hierarchy中的每两个层级之间，其速率都可能有数量级的差异。为了让计算尽可能少地访问内存，就需要让程序尽可能cache friendly。做得好和不好有时性能会是成倍的差异。在NN计算优化中，针对访存的优化很多。举两个常见且效果明显的典型例子：

Tiling/Blocking：对于两个矩阵相乘，我们知道用原始定义计算的话对cache不友好。如果矩阵比较大的话，尽管一个元素会多次参与计算，但当它下次参与计算时，早被踢出cache了。一个好的办法就是分块。那么问题来了，分块分多大，按哪个轴分，都对性能有很大影响。另问题更加复杂的是这个最优值还是和具体计算任务和硬件平台相关的。一种方法是针对平台做尽可能通用的优化。这就像做爆款，对大部分人来说都不错；另一种方式就是干脆量体裁衣，对给定模型在特定平台通过tuning得到最合适的参数，如AutoTVM通过Halide分离算法实现与硬件上的计算调度，然后通过自动搜索找出最合适的执行参数。经过tuning后其性能很多时候可以超过芯片厂商的推理引擎（毕竟厂商的推理引擎没法给每个模型量身定制）。
Operator fusion：这是一种最为常用的graph-level的优化。它将多个算子融合成一个，从而减少运行时间。无论是像Conv-BN-ReLU这样的纵向融合，还是Inception module这种多分支结构的横向融合，其实本质上都没有减少计算量，但现实中往往能给性能带来比较明显的提升。主要原因之一是它避免了中间数据的传输开销。

3. 异构调度 - 充分榨取多硬件能力

在过去的几年里，服务器市场基本是Nvidia GPU的天下。尽管近几年它也受到了来自TPU等各方面的压力，但总体来说，对于服务器端异构多元化程度没那么大。而与之不同的是，在移动端，不仅硬件种类多，而且同一类硬件差异也大。CPU有ARM和x86的，GPU有Adreno、Mali、Vivante等（虽说有像OpenCL这样的接口标准，但和CUDA不同，毕竟是多厂商各有各的实现，良莠不齐。而且很多厂商还会有私有扩展）。各类芯片如CPU、GPU、FPGA、DSP、ASIC不仅能力各异，算力也有数量级的差异，能效甚至有几个数量级之差。当然，理想情况下，如果ASIC一统江湖，在性能、成本、算子支持等方面都完爆、吊打和摩擦其它芯片，那事情倒简单一些。但这毕竟还需要些时间。因此，当前如何在AI时代充分挖掘和利用这些异构硬件的计算能力就成了一个很有趣的问题。

要解决问题，首先是问题的定义与描述。绝大多数计算任务可以被抽象成计算图，或者更具体地，有向无环图（DAG）。如一个DNN就是一个典型的DAG，一个场景中pipeline的各个节点也可以抽象成一个DAG。如在监控场景，一般摄像头数据进来先做预处理，再进行物体检测，同时可能还会做光流。物体检测结果会送去做细分类（如车牌识别，车型识别，行人ID识别等），另外还会拿来做跟踪。形式化地，计算图记为$G=(V, E, w, c)$。节点$V=v_1, ..., v_n$为操作，边$E=e_1, ..., e_m$表示操作间的依赖关系。$w_i \in \mathbb{R}$对应边上对应的通信代价。$c_i \in \mathbb{R}$对应节点上的计算代价。目标是使某个指定的性能指标最小（如整个计算图执行完的时间）。对于异构调度来说，同时还需要满足一些约束。这些约束包括但不限于：有些硬件只能执行整型计算，某些硬件只能支持或者加速某些特定算子，某几个算子需要放在同一设备上跑等等。

显然，这本质上是一个调度问题，而调度问题古而有之。因此，类似的问题也一定被前人研究过。对于一般的调度问题，可以描述为RCPS（Resource-constrained project scheduling）问题。RCPS问题的一种特例为MS（Machine scheduling）问题。MS问题的一种重要特例为JSS（Job shop scheduling）问题。在该问题中，一坨job需要调度到一堆机器上。每个job包含一个或多个必须按序执行的操作。而每个操作必须在指定机器上完成。目标是找到每台机器上的操作序列使得某个性能指标（如makespan）最小。基于JSS问题衍生出非常多的变体和扩展。其中与本节关注问题比较相切的是FJSS（Flexible job shop scheduling）问题。它将操作与机器的绑定关系解除了，即一个操作可以在多台机器上执行。这意味我们还需要确定操作与机器的对应关系，于是调度就分为两个子问题：machine assignment和local scheduling。遗憾的是，无论是对于JSS问题还是它的扩展，亦或是子问题，都是NP-hard的。也就是说，至少在目前的人类文明水平下，无法在多项式时间复杂度下找到最优解。

那么问题来了，怎么解呢？业界大体有这么几类方式：

精确算法：最简单最爽快的办法，直接奔着最优解去。前面的调度问题可以被形式化成MILP（Mixed integer linear programming）问题，然后用像常见的branch and bound algorithm咔咔走起。但是，就像前面提到的该问题是NP-hard的，意味着除非是在非常小的规模下，基本不能在合理时间保证找到最优解。而现代流行的大多数神经网络过于复杂，不太符合这种前提假设。
启发式策略：基于某种与问题领域相关的启发构造近似解。比如最简单的策略就是将每个算子都分配到最快的设备上执行。复杂些的启发比如基于后续节点的计算开销，计算图中的关键路径，或者聚类信息等。这类方法大多基于贪心法思想，因此无法保证找到最优解（准确来说，其它方法也不能保证，只能说它找不到更全局意义上的更优解）。其优点是速度快，运行时间可控。因不需要搜索或者学习的过程，在移动端可以在线完成。
元启发式搜索：为了避免启发式策略的局限，元启发式搜索通过本地提升方法与高层搜索策略的交互迭代过程来在解空间中进行搜索，更大程度上避免局部最优解。因为元启发式搜索对问题的特有条件相关性较小，因此，常见的比如遗传算法，禁忌搜索，模拟退火，粒子群算法，蚁群算法等都可以应用到调度问题上。这类方法一般可以比单纯的启发式策略或规则找到更优的解，但也需要耗费更长的时间，因此比较难做到在线即用。
基于学习的方法：其实把这块放在上面也能说得通，把它单列纯粹是想把它单列来说。毕竟我们理想的目标不仅仅是找到优的解，最好还能“举一反三”，而这需要知识的迁移。我们可以用基于机器学习的方法来实现调度，另外近年发展迅猛的GNN给调度的知识迁移提供了充足弹药。Reinforcement learning（增强学习，或译强化学习）是一类常用于智能决策的方法。而调度本质上也是一种决策，因此强化学习也是调度问题中的常客。如Microsoft和Google分别基于它来做服务器端的任务调度与网络模型执行时算子的device placement，获得了可观的性能收益。强化学习是有着几十年历史的机器学习重要分支之一，自从与深度学习结合后演变成DRL后重新焕发出强大的活力（早些年写的几篇reinforcement learning相关介绍：深度增强学习漫谈 - 从DQN到AlphaGo，深度增强学习漫谈 - 从AC到A3C，深度增强学习漫谈 - 信赖域（Trust Region）系方法）。

要进行异构调度，还需要有软件框架。这个框架需要有runtime来进行模型解析、优化、调度、执行等任务，还需要能接入各种硬件加速方案以供调度。硬件加速组件需要用HAL进行抽象封装，这样就可以将runtime与HAL加速实现解耦，让第三方加速方案方便地接入。业界的典型例子如Google的Android NN runtime。自Android 8.1以来，厂商可以通过NN HAL接口接入runtime被其调度。另一个例子如Microsoft的ONNXRuntime。它通过ExecutionProvider接口接入多种加速后端。但是，它们目前的分图和调度方案都是基于比较简单的规则，基本原则是哪个快让让哪个跑。这样的贪心策略注定无法得到全局更优的解。虽然通过异构调度我们可以得到一些性能上的好处，但仍有不少的挑战亟待我们解决。如：

动态负载：以上的很多方法中，要得到优的调度依赖于精确的cost model。静态条件下的cost model其实还好，可以通过对不同类型的算子进行采样得到样本，然后通过机器学习方法进行建模，可以达到比较低的预测误差。但是，要在考虑动态负载的情况下对广泛的情况建立准确的cost model这就是个比较大的挑战了。而在实际使用中，动态负载是个不得不考虑的问题。比如ASIC是很快，但如果它已经满负载了，再来一个任务的话，与其将它放于ASIC，还不如放在GPU或者CPU上，从而避免一块芯片忙到吐血，其它芯片吃瓜的状态。
多任务多优先级：在一个系统中，通常会有多个AI应用同时运行。它们可能有不同的优先级，ADAS可能需要更高优先级，交互相关的优先级可能略低一些。当计算资源冲突时，我们需要进行调度保证前者的延时在可接受范围。这将涉及到资源的优先调度和任务抢占，考虑抢占的话还要考虑抢占的粒度，不同硬件上抢占的实现等。另外，不同任务的主要指标和工作频率可能也不同，如监控中的目标检测一般高频执行，且优先考虑延迟；而车牌识别一般低频执行，优先考虑准确率，对延迟不敏感。所有这些，都是未来值得深挖的方向。

4. 轻量化网络结构 - 网络容量与计算开销间的权衡

模型的容量（Capacity）即其能拟合复杂函数的能力，简单来说即其表达能力。这是个非常抽象的概念，我们很难用具体的测度衡量它。但很多时候，从统计意义上来说，模型参数越多，capacity相对更大（虽然也不绝对）。它像是一把双刃剑。更强的表达能力当然是我们想要的。然后同时它可能也会让网络更难训练，且计算量更大。从2012年深度学习火热起来的几年里，学界的主流方向就是奔着更高的准确率刷榜，ImageNet就像奥运会百米赛跑一样，记录一次次被刷新。但与此同时，网络也变得越来越重，越来越复杂。而实际使用中，尤其是移动端往往难以运行这样重量级的网络。人们看到这样的问题，于是一系列轻量级的网络应运而生。当然，各个子领域基本都会有针对性的轻量化工作。由于这个topic涉及内容很多，而且网上这方面的介绍多如牛毛。这里篇幅有限，只拿几个经典的通用主干网络简单走一下。另外因一些网络有多个版本，所以这里我想按年份来排：

2015及以前：主要处在萌芽期。业界已经开始意识到工业及商业应用中的轻量化需求，但这时大多网络设计还不是专门奔着轻量化去的，基本是在主要追求更高准确率的同时也会考虑降低计算量。像经典的Inception系列引入了一系列设计原则和技巧提升参数的利用效率，让网络在达到高准确率的同时比早年VGG这种“大家伙”轻了不少。其中一些经典的思想也启蒙了后面的不少相关工作。这时的一些网络你放到移动平台上去跑吧，也能跑，但可能会跑得比较。。。勉强。这一时期还出现了像深度可分离卷积（Depthwise separable convolution）这样对往后轻量化网络设计产生重大影响的结构，它是后面Xception、MobileNet等经典网络中的基础。
2016年：SqueezeNet是早期比较经典的针对嵌入式平台网络结构设计的尝试。它的核心fire module，由squeeze和expand两层组成：Squeeze层通过1x1卷积核进行通道降维，再由expand层的一系列1x1和3x3卷积核对其计算，最后进行concat融合。由于squeeze层相当于做了“压缩”的操作因此可以降低后面操作的计算量。论文中实验表明它可将模型压缩50倍且准确率几乎无影响，比同期的模型压缩方法还要有效。而结合模型压缩方法能进一步将模型压缩数百倍。
2017年：这一年，Google推出了专用于移动平台的MobileNet，旷视也推出了类似定位的ShuffleNet，开始了他们竞赛的旅程。MobileNet主要基于深度可分离卷积。直觉上，在一个卷积层，我们想要空间维度和通道维度的信息都充分融合，普通卷积就是将这两个维度信息同时融合。基于这两个维度信息相互正交的假设，深度可分离卷积采取让它们一个一个来的做法。即先用depthwise convolution融合空间维再用pointwise convolution融合通道维。这样一来3x3卷积核下计算量可以减少8、9倍，同时对准确率影响还不太大。另一方面它引入两个调节因子width和resolution multiplier分别用于调节通道数和输入的分辨率，使网络可以在准确率和计算量间根据需要调节。ShuffleNet针对当时网络中大量使用的1x1卷积，建议使用group convolution降低计算量。又由于group convolution不利于通道间信息融合的问题提出了特色的channel shuffle操作，并且表示效果上胜于MobileNet。
2018年：Google推出了升级版MobileNet v2，旷视也推出了升级版ShuffleNet v2。MobileNet v2通过对非线性激活函数ReLU对高维空间中内嵌的低维流形影响的研究，和bottleneck已经包含所有必要信息的intuition，提出了结合了linear bottleneck和inverted residual的新结构，在前面工作基础上进一步提升了效果。ShuffleNet v2重点关注了影响运行速度中除了FLOPs外的另外因素-访存开销与并行度，提出了设计轻量化网络四大原则，并且基于这些原则设计了ShuffleNet v2，达到了当时的SOTA。我们知道，理论计算量小未必跑得快，因为可能对硬件不友好。要设计对硬件友好的网络架构，一条路是老师傅人工设计；还有条路就是让机器自己找硬件友好的网络结构。这就要提到自动神经网络架构搜索（NAS）了。自2016年左右，NAS的春风吹遍大地，经过一段时间的高速发展其耗时以数量级的速度减少，实用性大大增强（之前整理的一些NAS相关东西：神经网络架构搜索（Neural Architecture Search）杂谈）。Google在NAS领域非常活跃，在轻量化网络上自然也不会落下。这一年Google提出了MnasNet，同准确率下性能优于MobileNet v2。与早期传统NAS只关注准确率不同，它在优化目标中加入了性能因素，从而扩展到了多目标优化问题。后面关于NAS的研究也越来越多考虑执行性能，出现了像FBNet等一批hardware/platform-aware NAS方法。
2019年：Google再度升级MobileNet，推出了MobileNet v3，并表示比前面几代MobileNet、ShuffleNet啥的都牛掰。这次比较特色的是通过人机共创的方式设计网络架构。它先结合platform-aware NAS和NetAdapt对网络结构进行搜索，然后再对搜索得到的网络中最前和最后计算量比较大的部分进行了人工调整。同年，Google还提出了EfficientNet。前面提到MobileNet引入width/resolution multiplier作为参数对模型进行调节，这里还加了控制网络层数的depth参数，并且指出它们的调节不能瞎调，得按套路，即按固定的比例。通过调节这个比例系数，可以得到一系列各个重量级下的EfficientNet变种，并且在每个重量级上表现都不错。

5. 模型压缩 - 探索模型计算量下界

众所周知，机器学习分为训练和推理两个阶段。在这两个阶段中，计算任务是有差别的。一方面，一些算子在训练时需要，而在推理时是不需要的（或者形式不一样）。另外模型中的计算图可以作很多简化和优化（如冗余计算消除，内存布局优化，Operator fusion等）。因此我们在将训练好的模型部署前会对模型进行一些图优化和转化；另一方面，业界普遍认为模型过参数化（Over-parameterization）和高精度对训练有好处，而在推理时并不必要。这样的假设支持我们可以在不严重影响准确率的前提下对模型进行简化。这样的好处是多方面的。不仅减少了延时，也降低了功耗。同时还减少了内存占用，内存占用的减少还会提高cache利用率，甚至可能原来需要放在DRAM中的模型现在可以塞进SRAM中，从而又进一步提高性能、降低功耗。另外，更小的模型还利于应用更新或者OTA升级。可谓好处多多，一举多得。

深度学习自爆发后朝着更高、更强目标狂奔几年后，比较明显的轻量化之风大约兴起于2015年左右。除了轻量化网络结构设计之外，另一个重要的分支就是模型压缩。当时，韩松等人的deep compression相关工作有着标志性的影响。它通过结合多种压缩方法，将网络模型size压缩了几十倍，性能获得成倍的提升。这让大家意识到当时的DNN模型中可榨油水如此之多。另外，因深度学习领域工作获得图灵奖的三位大神Geoffrey Hinton, Yann LeCun和Yoshua Bengio在该领域也早有布局，做了先驱和奠基性的工作，如Hinton的知识蒸馏，Bengio在量化模型训练方法上的研究及二值化网络BinaryConnect，和LeCun用于网络参数裁剪的OBD方法以及低轶分解方面的工作。

剪枝（Pruning）：基于上面提到的过参数化假设，对网络的连接进行裁剪可能是最直觉的做法了。早在上世纪90年代，就有学者开始研究神经网络的参数裁剪（当然，当时还不是DNN）。这里最大的困难在于pruning的同时我们需要让准确率损失尽可能小。不能说pruning完快是快了，但啥都识别不出来了。。。就像前面的调度问题一样，给个解容易，找最优解那是难上加难。业界提出了很多方法，比如逐层按重要程度来进行裁剪，重要程度排序可以按其绝对值、对最终loss或者对特征的可重建性的影响。而对于参数的裁剪比例，一些论文指出网络中每层其敏感程度都不一样，因此也不能一刀切。对一些模型，其中的某些层可能裁剪个三、四成就会明显降低准确率，而一些层即使裁剪九成也不会对准确率造成很大影响，另外有些层可能是由于overfit，反而在pruning后准确率提高了。为了考虑参数间的相互影响关系，研究者们也提出了各种（如基于离散空间搜索、基于梯度、基于聚类、基于Bayesian等）方法来试图找全局意义上的更优解。为了弥补准确率的损失，一般会在pruning后做fine-tuning用来恢复准确率。另外，pruning的姿势也很重要，早期的pruning是非结构化剪枝，这样就有个问题：参数张量上都是“洞”，除非拿专门的硬件加速，否则该做的计算还是省不了，所以目前主流研究的是结构化剪枝，即以channel/filter这个维度来剪，剪完后参数张量只是变“瘦”，这样便可以实打实地减少计算量。值得注意的是，近年比较有意思的一些工作开始重新审视了以前固有的假设，比如过参数化是否真是那么有益，重用pretrained模型参数是否是最好的选择。另外业界还有非常多有意思的工作，这里不一一展开（之前读一些pruning相关论文的整理：闲话模型压缩之网络剪枝（Network Pruning）篇）。
量化（Quantization）：业界共识是对于推理而言，不需要和训练一样的精度。基于这样的假设，量化通过降低weight和activation的精度，成倍减少模型的大小（如32位到8位就是4倍），同时也提高了性能和降低了功耗。一方面一般整数运算要快于浮点运算，另一方面就8位整数和32位浮点操作为例，其能耗可以相差几十倍。正是因为这么明显的好处，量化成为了业界的趋势。无论是框架，计算库和芯片硬件，都在逐步完善对量化模型的支持。和pruning类似，量化本身不是事儿，难的是如何量化的同时保留尽可能高的准确率。量化按精度可分很多种。最为安全的是FP16，大多数情况下它能对性能有较大比例的提升，且对准确率不会有很大影响。但它仍是浮点运算。整数量化中目前最流行的是8位，基本主流训练框架和多数推理框架都官方支持了。在实践中它是一种很有效的提升性能的做法，尤其是对于除CPU外都比较弱的低端平台。但8位量化下就得比较小心准确率的损失了。本质上我们需要为每一层找到最优的量化所需参数，使其量化后信息量损失最小。大体可以分为两种方式：post-training quantization和quantization-aware training。前者是拿到模型后做的压缩，不需要训练环境；后者需在训练时加入特殊算子，一方面在forward时模拟量化效果，另一方面帮助得到量化所需参数，因此准确率损失会更小。但对于post-training quantization，我们可以通过少量数据集来得到量化所需参数（如Nvidia的TensorRT中的calibration过程）。更加激进的就是更低精度的量化了，如4位，3位，2位甚至1位。到了1位时，像卷积和全连接层就可以通过位运算完成，这样的计算对硬件来说是很友好的。然而在这样低的精度下，在量化同时保持准确率就是个大问题了。很多时候纯靠训练后量化就不行了，需要在训练时就考虑低精度。这几年该分支涌现出了像BinaryConnect，BWN，TWN，XNOR，FFN，INQ，BNN等一系列优秀的方法，到今天仍然是个炙手可热的研究方向。
低轶分解（Low-rank factorization）：对于搞工程的同学降维是个老朋友了，很多时候我们对于高维输入先做个降维是常规操作之一。如大家熟悉的SVD分解，通过对分解后对角线矩阵中奇异值的筛选，我们可以用多个低轶矩阵的累加代替或者说近似原矩阵。模型压缩中的低轶分解方法就是基于类似的思想，基于参数张量中普遍存在大量冗余的假设，对参数张量进行低轶分解来近似原参数，从而减少计算量。对于全连接层或卷积的Toeplitz矩阵，可以直接应用SVD。而对于卷积核这样的高阶张量，可以使用SVD的推广 - Tucker分解。另外常见的分解方法还包括CP分解，Block Term分解等。
知识蒸馏（Knowledge distillation）：基本思想是将比较重的（一个或一坨）teacher模型的知识迁移到比较轻（适于部署）的student模型中去，这个过程称为“蒸馏”。就像AI中很多其它算法一样，其实你也没法从数学上严格证明它的正确及有效性，只是从生物界得到的启发，而且事实上也很好用。2015年Hinton老爷子提出和阐述了神经网络中的KD方法。我们知道，在图片分类的网络模型中，最后给的是logit（如果经过softmax则可以看作一个分布），我们一般会选最大的作为预测输出。文中指出teacher模型中该分布中所有其它的值其实也能提供如何泛化的信息，这些信息有助于student模型的学习。换言之，它可以提供除ground truth以外更丰富的监督信息。最朴素的版本是让student模型去学习teacher模型的logit层。后面，研究者们就将它玩出各种花来了，比如演变出student模型去学习teacher模型的feature map，两个student网络相互学习，自我学习等等。另外，知识蒸馏还可以与其它模型压缩方法自然地结合，因为其它方法中经过“压缩”的模型可以作为student模型。

四、小结

在文章的末尾，我想简单聊下个人以为的，对于未来发展趋势和方向的，一些不成熟的看法。

Hardware/Software Co-design：极致的优化一定需要软件和硬件的协同与配合。一方面软件充分利用硬件特性与能力深度优化；而另一方面硬件也正被软件重新定义与推动。当今我们看到这两个方向都在快速的演进。目前，AI芯片除了针对矩阵计算作了大量优化外，还针对当前深度神经网络的一些发展趋势加入相应的特性，如低精度量化，稀疏计算的支持等等。
神经科学交叉：到今天为止，人类对自己的大脑的认知仍然非常有限。尽管由于各种小编为博眼球的断章取义，让刷着科技新闻的我们可能会有种“一切已尽在掌握”的错觉。然而，大脑的创造力、情感、记忆、推理如何运作，还有那超高的能效，其实我们都还知之甚少。但即便是这样，人类也已经从神经科学中获得了不少启发，推动了机器学习领域中不少技术的发展。人脑就像是个巨大的宝藏等待发掘。人工智能的目标不是为了复制人脑，但是，每次对人脑的解密和神经科学的突破，总能给机器学习带来很大的启迪。DeepMind创始人Hassabis本身是神经科学博士，或许也正是这样的交叉学科背景帮助它缔造了这样一家传奇的公司。相信通往AGI的路上神经科学必是最有力的助推器之一。
AutoML：我们知道一个完整的机器学习流程有很多步骤，包括数据生产、采集、处理、训练、部署、优化等等。展望过去的若干年，你会看到机器在各个步骤上正逐步替代人类，而且一些任务中机器会比人类做的更好。从特征选取、网络架构搜索、优化器设计到关乎性能优化的算子调参、模型压缩等各个方面，都被自动化方法替代或部分替代。因为其中的很多问题本质上都是大规模空间中的参数搜索问题。而这类问题不是人类的强项，却是机器的强项。长远来看，这方面人很难干过机器。人类围棋数千年的经验，却被AlphaGo碾压就是一个例子。蓬勃发展的AutoML在短中期将加速促进AI*化；长期还有可能让机器具备自我进化的能力，这给我们巨大的想象空间。
基于编译器优化：神经网络模型本质上描述了一段计算逻辑，和代码一样。就如代码可以用编译器优化获得性能提升一样，神经网络模型也可以。我们可以看到，其实神经网络计算引擎中的不少优化和传统编译器中的优化是类似的。目前，业界已有不少相关的项目，如XLA，TVM，Glow，Tensor Comprehensions。各个主流深度学习框架似乎也将基于编译器的优化作为必备和大力发展方向。这给结合多个level的end-to-end优化带来巨大的机会。这些技术发展到最后是会相互正交互补，还是合并趋同，是件很有意思的事。
端-云协同：边缘智能计算不代表与云端割裂，相反，它需要云和端更加紧密的结合。尤其是结合5G的发展，给我们广阔的想象空间。一方面，对于计算而言，未来的很多计算可以是中心控制分布计算的方式。一个计算任务可以分布到其它边缘设备，或者云端来共同完成。另一方面，这种协同还可以进一步提高智能化水平。尽管现在智能化产品应用广泛，但很多时候我们会戏称它们不是人工智能而是“人工智障”。个人认为，主要因素之一是因为目前主流方式都是云端统一训练，然后部署到端，过段时间再统一更新模型，进化不够及时。Google的federated learning起了一个好头，更多的变革让我们拭目以待。

码农公寓