边缘智能论文阅读之IONN: Incremental Offloading of Neural Network Computations from Mobile Devices to...

摘要

• 论文完整标题：IONN: Incremental Offloading of Neural Network Computations from Mobile Devices to Edge Servers
• 论文下载链接：https://pan.baidu.com/s/1GUyXw4nhYw0YFhGl3s-33Q 提取码：iuim
• 这篇论文发表在2018年的国际会议ACM Symposium on Cloud Computing 2018 (B类)

动机

在资源受限的移动设备上运行计算密集型深度神经网络（DNN）的方法一般是，先在中央云服务器上预先安装相应的DNN模型，然后再向中央云服务器进行DNN查询。但是这种方法不适合分散式云设施（比如， cloudlet和边缘/雾服务器），在这种设施中，客户端可以向位于网络边缘的任何附近服务器发送计算请求，因此，在开始执行DNN请求前，客户端需要先将其DNN模型上传到服务器，但如果一次性上传整个模型，会导致时间过长，DNN的推理受阻。

IONN简介

本文提出了IONN，一种基于分块的神经网络增量卸载技术，IONN将客户端的DNN模型划分为几个分区，并逐个将它们上传到边缘服务器，当每个DNN分区到达时，服务器增量地构建DNN模型，同时，在整个DNN模型上传完成前，客户端就可以开始执行DNN。为了确定最佳的DNN分区策略和上传顺序，IONN使用了一种新的基于图的启发式算法。

具体实现

总体框架

IONN分为客户端和服务器两个部分，每个部分都有安装和运行时两个阶段：

• 客户端安装阶段：当在移动设备上安装了一个使用DNN的应用程序时，IONN客户端会先运行该模型，并记录每个DNN层的执行时间，保存在DNN执行文件中
• 服务器安装阶段：根据服务器的配置，创建一个预测函数，当客户机进入其服务区域时，服务器将该预测函数发送到客户机。这里构造预测函数的方法跟NeuroSurgeon一致，是一个线性回归函数，输入为DNN模型的层类型等，输出为每一层在服务器上运行的估计时间。
• 客户端运行时阶段：当客户机接收到预测函数后，以DNN层的类型和参数为输入，预测DNN的每一层在当前边缘服务器的执行时间。然后，客户机中的分区引擎就会根据本地执行时间和边缘执行时间，使用基于图的分区的启发式算法，创建一个最佳的上传计划。客户端的执行时包括两个线程，与服务器端的两个线程协同进行上传和DNN推理操作。
• 服务器运行时阶段：包括两个线程，与客户端协同执行，具体流程如下：
  
• 上传线程：客户端的上传线程会按顺序将计划列表中的DNN分区发送到服务器，服务器的上传线程则使用收到的DNN分区构建DNN模型，并发送确认消息（ACK）。
• 执行线程：检查每个DNN分区的ACK，将分区分为上传分区和本地分区（没有上传的分区）两种，当新收到一个DNN查询时，执行线程会先执行本地分区，到下一个上传分区之前停止，然后将结果和分区索引发送给服务器，服务器的执行线程收到数据后，会接着执行DNN模型后面的层，执行完成后又将结果发回客户端，如此循环，直到最终到达最后的输出层。

分区上传策略

已经知道了IONN的总体框架，现在的问题是如何创建分区，接下来的部分主要介绍分区策略。
首先，我们需要明确，如果一次性上传所有的层，会需要很长的时间，而在上传模型的这段时间内，如果来了一个DNN推理请求，那么该请求就只能全部放在本地执行，无法从服务器处获利，导致推理的效率很低。那么我们的目的就是将一个大的DNN按层划分为很多个小分区，然后逐个上传，很显然，我们希望最先上传那些性能最好的分区（即，上传时间很短，在服务器上执行的时间也很短的分区），这可以转换为最短路径问题来求解，所以，我们为DNN模型构建了一个NN执行图，并通过迭代的搜索图的最短路径来创建DNN分区。首先，介绍图的构造方法。

NN执行图的构造

将DNN的每一层都转换为三个节点（层A: 1, 2, 3,层 B: 4, 5, 6, 层 C: 7, 8, 9），左侧节点属于客户端（0,1,4,7,10），右侧节点属于服务器（2,3,5,6,8,9）。客户端节点之间的边表示在本地执行当前层的时间（如，1->4），同一层中服务器节点之间的边表示在服务器端执行时间加层的上传时间（如，2->3），客户端节点和服务器节点之间的边表示传输时间（如，1->2）。因此，DNN查询的执行路径就可以用图上的路径来表示，比如，路径0-1-4-5-6-7-10表示在客户端执行层A，将层B卸载到服务器执行，继续在客户端执行层C。

切割算法

如果能知道查询的未来情况就可以找到最优的解决方案，比如，如果知道下一个查询来的比较晚，就可以先上载一个大分区，但如果来的很快，就可以先上传一个小分区，但是由于这是无法知道的，所以本文采用了启发式算法。

DNN分区算法的距离流程如下：
(1) 根据执行文件，预测函数和网络带宽，构建一个NN执行图；
(2) 利用最短路径算法，搜索最短路径；
(3) 将包含在最短路径中的服务器端节点对应的层，组成DNN分区，并加入分区计划集合中。
(4) 将层上传时间乘以K（小于1的正数），获得权重更新后的图，在新图中重新搜索新的最短路径，直到层上传时间的边权重几乎为零（通过减小上传时间，可以使得新的最短路径中包含比前一条路径更多的服务器节点）。

切割算法应用实例

多路径DNN的处理

问题(a)：当NN某层的输出被传递到多个层时，如果直接采用算法1，会导致部分层的执行被丢失。如上图(a)，从一个输入到一个输出的最短路径将只包括中间三层中的一层，其余两层的执行就被丢失了。
解决办法(b)：构造NN执行图时，将必须包含在路径中的层定义为支配层（如A，B），在构建NN执行图时，将相邻两个支配层之间的层（A和B之间的层）和后一个支配层（B）看做一个层，权重为组合层中所有层的执行时间之和，然后再执行算法1。

总结

本文提出了IONN，一种面向边缘计算的DNN卸载技术，IONN对DNN层进行分区，并以增量方式上传分区，以允许客户端和边缘服务器之间协同执行，甚至在上载整个DNN模型之前。实验结果表明，与一次上传整个模型的方法相比，该方法提高了DNN模型上传期间的查询性能和能耗。

作者的下一步工作

(1) 研究一种更现实的情况，即客户端在多个边缘服务器之间移动并自由的更改服务器。
(2) 研究一种更先进的DNN分区算法，以处理多个移动客户端同时向边缘服务器卸载DNN执行的情况。
(3) 扩展IONN，以支持更多类型的DNN（如RNN或CRNN）和其他DNN计算（例如DNN训练）。