wxquare's Blogs

TCP和UDP协议

1. tcp头格式，其20个字节包含哪些内容？ udp头部格式，其8个字节分别包含哪些内容？

2. 为什么 UDP 头部没有「首部长度」字段，而 TCP 头部有「首部长度」字段呢？原因是 TCP 有可变长的「选项」字段，而 UDP 头部长度则是不会变化的，无需多一个字段去记录 UDP 的首部长度

3. tcp和udp的区别以及应用场景

   • TCP是面向连接的，而UDP是不需要建立连接的
   • TCP 是一对一的两点服务，UDP 支持一对一、一对多、多对多的交互通信
   • 可靠性，TCP 是可靠交付数据的，数据可以无差错、不丢失、不重复、按需到达。UDP 是尽最大努力交付，不保证可靠交付数据。
   • TCP有拥塞控制、流量控制
   • 首部开销，TCP 首部长度较长，会有一定的开销，首部在没有使用「选项」字段时是 20 个字节，如果使用了「选项」字段则会变长的。UDP 首部只有 8 个字节，并且是固定不变的，开销较小。
   • 传输方式，TCP 是流式传输，没有边界，但保证顺序和可靠。UDP 是一个包一个包的发送，是有边界的，但可能会丢包和乱序

   TCP 和 UDP 应用场景：由于 TCP 是面向连接，能保证数据的可靠性交付，因此经常用于，FTP 文件传输HTTP / HTTPS，由于 UDP 面向无连接，它可以随时发送数据，再加上UDP本身的处理既简单又高效，因此经常用于：包总量较少的通信，如 DNS 、SNMP 等视频、音频等多媒体通信广播通信

4. TCP协议如何保证可靠传输？

   • 三次握手四次挥手确保连接的建立和释放
   • 超时重发：数据切块发送，等待确认，超时未确认会重发
   • 数据完整性校验：TCP首部中数据有端到端的校验和，接收方会校验，一旦出错将丢弃且不确认收到此报文
   • 根据序列码进行数据的排序和去重
   • 根据接收端缓冲区大小做流量控制
   • 根据网络环境做拥塞控制。当网络拥塞时，会减少数据的发送

5. TCP怎么通过三次握手和四次挥手建立可靠连接以及需要注意的问题

   • 分别准确画出三次握手和四次挥手状态转换图 从上面的过程可以发现第三次握手是可以携带数据的，前两次握手是不可以携带数据的，这也是面试常问的题
   • 为什么需要三次握手？ 通过三次握手实现了同步序列号和避免了旧的重复连接初始化造成混乱，浪费服务器资源，两个作用
   • 为什么需要四次挥手？全双工通信
   • time_wait状态什么作用？ 防止之前的报文造成新连接数据混乱，通过2msl使前一连接数据失效；确保ack报文发送给服务端。

6. 超时重传和快速重传

   • 客户端通过定时器在指定时间内未发现会收到ack信息就认为进行超时重传
   • 客户端收到连续三个重复ack信息就会发起快速重传而不用等待超时重传

7. 如何解决可能出现的乱序和重复数据问题

   • 三次握手双方约定ISN
   • TCP建立链接时ISN是怎么产生的，为什么需要每次都不相同？
   • 根据序列号调整顺序

8. TCP流量控制和滑动窗口

   • 为了提高数据传输的小路，tcp避免了一问一答式的消息传输策略
   • 通过累积确认ACK的方式提高效率
   • 在累积确认时通过接收窗口进行流量控制

9. tcp拥塞控制和拥塞窗口？
   

   • tcp在数据发送时会结合整个网络环境调整数据发送的速率
   • 发送者如何判断拥塞已经发生的？发送超时，或者说TCP重传定时器溢出；接收到重复的确认报文段
   • 快重传算法（接收端到失序的报文段立即重传、发送端一旦接收三个重复的确认报文段，立即重传，不用等定时器）

10. TCP 的连接状态查看，在 Linux 可以通过 netstat -napt 命令查看

11. 什么是SYN攻击，怎么避免SYN攻击？

• SYN攻击属于DOS攻击的一种，它利用TCP协议缺陷，通过发送大量的半连接请求，耗费CPU和内存资源。SYN攻击除了能影响主机外，还可以危害路由器、防火墙等网络系统，事实上SYN攻击并不管目标是什么系统，只要这些系统打开TCP服务就可以实施。从上图可看到，服务器接收到连接请求（syn=j），将此信息加入未连接队列，并发送请求包给客户（syn=k,ack=j+1），此时进入SYN_RECV状态。当服务器未收到客户端的确认包时，重发请求包，一直到超时，才将此条目从未连接队列删除。配合IP欺骗，SYN攻击能达到很好的效果，通常，客户端在短时间内伪造大量不存在的IP地址，向服务器不断地发送syn包，服务器回复确认包，并等待客户的确认，由于源地址是不存在的，服务器需要不断的重发直至超时，这些伪造的SYN包将长时间占用未连接队列，正常的SYN请求被丢弃，目标系统运行缓慢，严重者引起网络堵塞甚至系统瘫痪。

12. 如何解决close_wait和time_wait过多的问题？

    • CLOSE_WAIT，只会发生在客户端先关闭连接的时候，但已经收到客户端的fin包，但服务器还没有关闭的时候会产生这个状态，如果服务器产生大量的这种连接一般是程序问题导致的，如部分情况下不会执行socket的close方法，解决方法是查程序
    • TIME_WAIT，time_wait是一个需要特别注意的状态，他本身是一个正常的状态，只在主动断开那方出现，每次tcp主动断开都会有这个状态的，维持这个状态的时间是2个msl周期（2分钟），设计这个状态的目的是为了防止我发了ack包对方没有收到可以重发。那如何解决出现大量的time_wait连接呢？千万不要把tcp_tw_recycle改成1，这个我再后面介绍，正确的姿势应该是降低msl周期，也就是tcp_fin_timeout值，同时增加time_wait的队列（tcp_max_tw_buckets），防止满了。

13. 什么是TCP粘包，应用层怎么解决，http是怎么解决的。tcp是字节流，需要根据特殊字符和长度信息将消息分开

14. udp协议怎么做可靠传输？
    由于在传输层UDP已经是不可靠的连接，那就要在应用层自己实现一些保障可靠传输的机制，简单来讲，要使用UDP来构建可靠的面向连接的数据传输，就要实现类似于TCP协议的，超时重传（定时器），有序接受 （添加包序号），应答确认 （Seq/Ack应答机制），滑动窗口流量控制等机制 （滑动窗口协议），等于说要在传输层的上一层（或者直接在应用层）实现TCP协议的可靠数据传输机制，比如使用UDP数据包+序列号，UDP数据包+时间戳等方法。目前已经有一些实现UDP可靠传输的机制，比如UDT（UDP-based Data Transfer Protocol）基于UDP的数据传输协议（UDP-based Data Transfer Protocol，简称UDT）是一种互联网数据传输协议。UDT的主要目的是支持高速广域网上的海量数据传输，而互联网上的标准数据传输协议TCP在高带宽长距离网络上性能很差。 顾名思义，UDT建于UDP之上，并引入新的拥塞控制和数据可靠性控制机制。UDT是面向连接的双向的应用层协议。它同时支持可靠的数据流传输和部分可靠的数据报传输。 由于UDT完全在UDP上实现，它也可以应用在除了高速数据传输之外的其它应用领域，例如点到点技术（P2P），防火墙穿透，多媒体数据传输等等

15. TCP 保活机制KeepAlive？其局限性？Http的keep-alive？为什么应用层也经常做心跳检查？

    • TCP KeepAlive 的基本原理是，隔一段时间给连接对端发送一个探测包，如果收到对方回应的 ACK，则认为连接还是存活的，在超过一定重试次数之后还是没有收到对方的回应，则丢弃该 TCP 连接。TCP-Keepalive-HOWTO 有对 TCP KeepAlive 特性的详细介绍，有兴趣的同学可以参考。
    • TCP KeepAlive 的局限。首先 TCP KeepAlive 监测的方式是发送一个 probe 包，会给网络带来额外的流量，另外 TCP KeepAlive 只能在内核层级监测连接的存活与否，而连接的存活不一定代表服务的可用。例如当一个服务器 CPU 进程服务器占用达到 100%，已经卡死不能响应请求了，此时 TCP KeepAlive 依然会认为连接是存活的。因此 TCP KeepAlive 对于应用层程序的价值是相对较小的。需要做连接保活的应用层程序，例如 QQ，往往会在应用层实现自己的心跳功能。
      除了TCP自带的Keeplive机制，实现业务中经常在业务层面定制“心跳”功能，主要有以下几点考虑：
    • TCP自带的keepalive使用简单，仅提供连接是否存活的功能
    • 应用层心跳包不依赖于传输协议，支持tcp和udp
    • 应用层心跳包可以定制，可以应对更加复杂的情况或者传输一些额外的消息
    • Keepalive仅仅代表连接保持着，而心跳往往还表示服务正常工作
      在 HTTP 1.0 时期，每个 TCP 连接只会被一个 HTTP Transaction（请求加响应）使用，请求时建立，请求完成释放连接。当网页内容越来越复杂，包含大量图片、CSS 等资源之后，这种模式效率就显得太低了。所以，在 HTTP 1.1 中，引入了 HTTP persistent connection 的概念，也称为 HTTP keep-alive，目的是复用TCP连接，在一个TCP连接上进行多次的HTTP请求从而提高性能。HTTP1.0中默认是关闭的，需要在HTTP头加入”Connection: Keep-Alive”，才能启用Keep-Alive；HTTP1.1中默认启用Keep-Alive，加入”Connection: close “，才关闭。两者在写法上不同，http keep-alive 中间有个”-“符号。 HTTP协议的keep-alive 意图在于连接复用，同一个连接上串行方式传递请求-响应数据。TCP的keepalive机制意图在于保活、心跳，检测连接错误。

16. TCP 协议性能问题分析？

    • TCP 的拥塞控制在发生丢包时会进行退让，减少能够发送的数据段数量，但是丢包并不一定意味着网络拥塞，更多的可能是网络状况较差；
    • TCP 的三次握手带来了额外开销，这些开销不只包括需要传输更多的数据，还增加了首次传输数据的网络延迟；
    • TCP 的重传机制在数据包丢失时可能会重新传输已经成功接收的数据段，造成带宽的浪费；

17. QUIC 是如何解决TCP 性能瓶颈的？

18. 科普：QUIC协议原理分析

http和https

1. HTTP协议协议格式详解

   • 请求行(request line)。请求方法、域名、协议版本。
   • 请求头部(header)从第二行起为请求头部，Host指出请求的目的地（主机域名）；User-Agent是客户端的信息，它是检测浏览器类型的重要信息，由浏览器定义，并且在每个请求中自动发送
   • 空行
   • 请求数据

2. http 常见的状态码有哪些？

   • 200 成功
   • 3xx重定向相关，301 永久重定向，302临时重定向
   • 4xx客户端错误，400请求报文有问题，403服务器禁止访问资源,404资源不存在
   • 5xx服务器内部错误,501 请求的功能暂不支持，502 服务器逻辑有问题，503 服务器繁忙

3. get 和 post 区别

   • GET参数通过URL传递，POST放在Request body中
   • GET请求只能进行url编码，而POST支持多种编码方式
   • GET请求在URL中传送的参数是有长度限制的，而POST没有
   • GET比POST更不安全，因为参数直接暴露在URL上，所以不能用来传递敏感信息。
   • GET请求参数会被完整保留在浏览器历史记录里，而POST中的参数不会被保留。

4. https的工作原理和流程

5. http和https的区别

   • http采用明文传输，http+ssl的加密传输
   • http是80端口，https是443端口
   • HTTP的连接很简单，是无状态的；HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，比HTTP协议安全

6. 浏览器输入http://www.baidu.com
   事件顺序
   (1) 浏览器获取输入的域名www.baidu.com
   (2) 浏览器向DNS请求解析www.baidu.com的IP地址
   (3) 域名系统DNS解析出百度服务器的IP地址
   (4) 浏览器与该服务器建立TCP连接(默认端口号80)
   (5) 浏览器发出HTTP请求，请求百度首页
   (6) 服务器通过HTTP响应把首页文件发送给浏览器
   (7) TCP连接释放
   (8) 浏览器将首页文件进行解析，并将Web页显示给用户。

7. http长连接和短连接？http长连接和短连接以及keep-Alive的含义，HTTP 长连接不可能一直保持，例如 Keep-Alive: timeout=5, max=100，表示这个TCP通道可以保持5秒，max=100，表示这个长连接最多接收100次请求就断开。

8. http cookie和session

   • Cookie和Session都是客户端与服务器之间保持状态的解决方案，具体来说，cookie机制采用的是在客户端保持状态的方案，而session机制采用的是在服务器端保持状态的方案
   • Cookie实际上是一小段的文本信息。客户端请求服务器，如果服务器需要记录该用户状态，就使用response向客户端浏览器颁发一个Cookie，而客户端浏览器会把Cookie保存起来。当浏览器再请求该网站时，浏览器把请求的网址连同该Cookie一同提交给服务器，服务器检查该Cookie，以此来辨认用户状态。服务器还可以根据需要修改Cookie的内容

9. http1.0,tttp1.1,http2.0,http 3.0各有什么变化

   • http 1.0
   • http 1.1, 长连接
   • http 2.0，二进制压缩+连接复用
   • http QUIC，udp+ssl

10. HTTP/3 竟然基于 UDP，HTTP 协议这些年都经历了啥？

11. 使用curl

12. https中间人攻击原理以及防御措施

13. 如何理解http的无连接和无状态的特点？

14. 半链接和Sync 攻击原理及防范技术

资料来源：OSI 7层模型

超文本传输协议（HTTPS/HTTP1.1/HTTP2/HTTP3）

https://aws.amazon.com/cn/compare/the-difference-between-https-and-http/

HTTP 是一种在客户端和服务器之间编码和传输数据的方法。它是一个请求/响应协议：客户端和服务端针对相关内容和完成状态信息的请求和响应。HTTP 是独立的，允许请求和响应流经许多执行负载均衡，缓存，加密和压缩的中间路由器和服务器。

一个基本的 HTTP 请求由一个动词（方法）和一个资源（端点）组成。 以下是常见的 HTTP 动词：

• HTTPS 是基于 HTTP 的安全版本，通过使用 SSL 或 TLS 加密和身份验证通信。
• HTTP/1.1 是 HTTP 的第一个主要版本，引入了持久连接、管道化请求等特性。
• HTTP/2 是 HTTP 的第二个主要版本，使用二进制协议，引入了多路复用、头部压缩、服务器推送等特性。
• HTTP/3 是 HTTP 的第三个主要版本，基于 QUIC 协议，使用 UDP，提供更快的传输速度和更好的性能

多次执行不会产生不同的结果。

HTTP 是依赖于较低级协议（如 TCP 和 UDP）的应用层协议。

来源及延伸阅读：HTTP

• README +
• HTTP 是什么？
• HTTP 和 TCP 的区别
• PUT 和 PATCH的区别

传输控制协议（TCP）

资料来源：如何制作多人游戏

TCP 是通过 IP 网络的面向连接的协议。 使用握手建立和断开连接。 发送的所有数据包保证以原始顺序到达目的地，用以下措施保证数据包不被损坏：

• 每个数据包的序列号和校验码。
• 确认包和自动重传

如果发送者没有收到正确的响应，它将重新发送数据包。如果多次超时，连接就会断开。TCP 实行流量控制和拥塞控制。这些确保措施会导致延迟，而且通常导致传输效率比 UDP 低。

为了确保高吞吐量，Web 服务器可以保持大量的 TCP 连接，从而导致高内存使用。在 Web 服务器线程间拥有大量开放连接可能开销巨大，消耗资源过多，也就是说，一个 memcached 服务器。连接池 可以帮助除了在适用的情况下切换到 UDP。

TCP 对于需要高可靠性但时间紧迫的应用程序很有用。比如包括 Web 服务器，数据库信息，SMTP，FTP 和 SSH。

以下情况使用 TCP 代替 UDP：

• 你需要数据完好无损。
• 你想对网络吞吐量自动进行最佳评估。

用户数据报协议（UDP）

资料来源：如何制作多人游戏

UDP 是无连接的。数据报（类似于数据包）只在数据报级别有保证。数据报可能会无序的到达目的地，也有可能会遗失。UDP 不支持拥塞控制。虽然不如 TCP 那样有保证，但 UDP 通常效率更高。

UDP 可以通过广播将数据报发送至子网内的所有设备。这对 DHCP 很有用，因为子网内的设备还没有分配 IP 地址，而 IP 对于 TCP 是必须的。

UDP 可靠性更低但适合用在网络电话、视频聊天，流媒体和实时多人游戏上。

以下情况使用 UDP 代替 TCP：

• 你需要低延迟
• 相对于数据丢失更糟的是数据延迟
• 你想实现自己的错误校正方法

来源及延伸阅读：TCP 与 UDP

• 游戏编程的网络
• TCP 与 UDP 的关键区别
• TCP 与 UDP 的不同
• 传输控制协议
• 用户数据报协议
• Memcache 在 Facebook 的扩展

远程过程调用协议（RPC）

Source: Crack the system design interview

在 RPC 中，客户端会去调用另一个地址空间（通常是一个远程服务器）里的方法。调用代码看起来就像是调用的是一个本地方法，客户端和服务器交互的具体过程被抽象。远程调用相对于本地调用一般较慢而且可靠性更差，因此区分两者是有帮助的。热门的 RPC 框架包括 Protobuf、Thrift 和 Avro。

RPC 是一个“请求-响应”协议：

• 客户端程序 ── 调用客户端存根程序。就像调用本地方法一样，参数会被压入栈中。
• 客户端 stub 程序 ── 将请求过程的 id 和参数打包进请求信息中。
• 客户端通信模块 ── 将信息从客户端发送至服务端。
• 服务端通信模块 ── 将接受的包传给服务端存根程序。
• 服务端 stub 程序 ── 将结果解包，依据过程 id 调用服务端方法并将参数传递过去。

RPC 调用示例：

1
2
3
4
5
6
7

GET /someoperation?data=anId

POST /anotheroperation
{
  "data":"anId";
  "anotherdata": "another value"
}

RPC 专注于暴露方法。RPC 通常用于处理内部通讯的性能问题，这样你可以手动处理本地调用以更好的适应你的情况。

当以下情况时选择本地库（也就是 SDK）：

• 你知道你的目标平台。
• 你想控制如何访问你的“逻辑”。
• 你想对发生在你的库中的错误进行控制。
• 性能和终端用户体验是你最关心的事。

遵循 REST 的 HTTP API 往往更适用于公共 API。

缺点：RPC

• RPC 客户端与服务实现捆绑地很紧密。
• 一个新的 API 必须在每一个操作或者用例中定义。
• RPC 很难调试。
• 你可能没办法很方便的去修改现有的技术。举个例子，如果你希望在 Squid 这样的缓存服务器上确保 RPC 被正确缓存的话可能需要一些额外的努力了。

表述性状态转移（REST）

REST 是一种强制的客户端/服务端架构设计模型，客户端基于服务端管理的一系列资源操作。服务端提供修改或获取资源的接口。所有的通信必须是无状态和可缓存的。

RESTful 接口有四条规则：

• 标志资源（HTTP 里的 URI） ── 无论什么操作都使用同一个 URI。
• 表示的改变（HTTP 的动作） ── 使用动作, headers 和 body。
• 可自我描述的错误信息（HTTP 中的 status code） ── 使用状态码，不要重新造轮子。
• HATEOAS（HTTP 中的HTML 接口） ── 你的 web 服务器应该能够通过浏览器访问。

REST 请求的例子：

1
2
3
4

GET /someresources/anId

PUT /someresources/anId
{"anotherdata": "another value"}

REST 关注于暴露数据。它减少了客户端／服务端的耦合程度，经常用于公共 HTTP API 接口设计。REST 使用更通常与规范化的方法来通过 URI 暴露资源，通过 header 来表述并通过 GET、POST、PUT、DELETE 和 PATCH 这些动作来进行操作。因为无状态的特性，REST 易于横向扩展和隔离。

缺点：REST

• 由于 REST 将重点放在暴露数据，所以当资源不是自然组织的或者结构复杂的时候它可能无法很好的适应。举个例子，返回过去一小时中与特定事件集匹配的更新记录这种操作就很难表示为路径。使用 REST，可能会使用 URI 路径，查询参数和可能的请求体来实现。
• REST 一般依赖几个动作（GET、POST、PUT、DELETE 和 PATCH），但有时候仅仅这些没法满足你的需要。举个例子，将过期的文档移动到归档文件夹里去，这样的操作可能没法简单的用上面这几个 verbs 表达。
• 为了渲染单个页面，获取被嵌套在层级结构中的复杂资源需要客户端，服务器之间多次往返通信。例如，获取博客内容及其关联评论。对于使用不确定网络环境的移动应用来说，这些多次往返通信是非常麻烦的。
• 随着时间的推移，更多的字段可能会被添加到 API 响应中，较旧的客户端将会接收到所有新的数据字段，即使是那些它们不需要的字段，结果它会增加负载大小并引起更大的延迟。

RPC 与 REST 比较

资料来源：你真的知道你为什么更喜欢 REST 而不是 RPC 吗

网络通讯协议

OSI 七层网络模型

资料来源：OSI 7层模型

常用的应用层协议

HTTP (Hypertext Transfer Protocol)

用途：主要用于Web浏览器和服务器之间的通信，是万维网的数据传输基础。
特点：无状态、请求-响应模式。
版本：HTTP/1.1, HTTP/2, HTTP/3

FTP (File Transfer Protocol)

用途：用于在客户端和服务器之间传输文件。
特点：支持文件上传和下载，支持匿名访问和身份验证。

邮件协议

• SMTP (Simple Mail Transfer Protocol)
  用途：用于发送电子邮件。
  特点：主要用于邮件服务器之间的邮件传输。
• POP3 (Post Office Protocol 3)
  用途：用于从邮件服务器下载邮件到本地客户端。
  特点：下载后邮件通常会从服务器删除。
• IMAP (Internet Message Access Protocol)
  用途：用于从邮件服务器读取邮件。
  特点：支持在服务器上管理和存储邮件，客户端和服务器邮件同步

WebSocket

用途：提供全双工通信的协议，允许在客户端和服务器之间建立持久连接。
特点：低延迟、实时通信、减少HTTP请求开销。
为什么需要websocket

WebRTC (Web Real-Time Communication)

用途：用于实现浏览器和移动应用之间的实时音视频通信和数据共享。
特点：P2P通信、低延迟、高质量音视频传输。
webRTC

MQTT (Message Queuing Telemetry Transport)

用途：轻量级的发布/订阅消息传输协议，常用于物联网（IoT）设备之间的通信。
特点：低带宽、低能耗、可靠性高

超文本传输协议

• aws http 选择介绍
• HTTPS 是基于 HTTP 的安全版本，通过使用 SSL 或 TLS 加密和身份验证通信。
• HTTP/1.1 是 HTTP 的第一个主要版本，引入了持久连接、管道化请求等特性。
• HTTP/2 是 HTTP 的第二个主要版本，使用二进制协议，引入了多路复用、头部压缩、服务器推送等特性。
• HTTP/3 是 HTTP 的第三个主要版本，基于 QUIC 协议，使用 UDP，提供更快的传输速度和更好的性能

其它

1. https://blog.csdn.net/justloveyou_/article/details/78303617
2. 图解https的过程:https://segmentfault.com/a/1190000021494676
3. 35 张图解：被问千百遍的 TCP 三次握手和四次挥手面试题
4. 30张图解： TCP 重传、滑动窗口、流量控制、拥塞控制
5. 硬核！30 张图解 HTTP 常见的面试题

CPU任务调度，进程/线程/协程

1. 进程和线程的区别，了解协程吗？CPU调度，数据共享。
2. 复杂系统中通常融合了多进程编程，多线程编程，协程编程
3. 进程之间怎么通信，线程通信通信，协程怎么通信
4. 进程之间怎么同步（信号量，自旋锁，屏障），线程之间怎么同步（锁），协程怎么同步。进程之间通过共享内存、管道、消息队列消息队列等方式通信，通过信号和信号量进行同步。线程在进程内部，全部变量时共享的，通过锁机制来同步。
5. 死锁：产生的四个条件、四个解决方法,死锁检测
6. 守护进程，linux系统编程实现守护进程
7. 在Linux上，对于多进程，子进程继承了父进程的下列哪些？堆栈、文件描述符、进程组、会话、环境变量、共享内存
8. 僵尸进程和孤儿进程。孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。僵尸进程：一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵死进程。
9. 进程的状态。
   • TASK_RUNNING（运行态）：进bai程是可执行du的；或者正在执行，zhi或者在运行队列中等待执行。
   • TASK_INTERRUPTIBLE（可中断睡眠态）：进程被阻塞，等待某些条件的完成。一旦完成这些条件，内核就会将该进程的状态设置为运行态。
   • TASK_UNINTERRUPTIBLE（不可中断睡眠态）：进程被阻塞，等待某些条件的完成。与可中断睡眠态不同的是，该状态进程不可被信号唤醒。
   • TASK_ZOMBIE（僵死态）：该进程已经结束，但是其父进程还没有将其回收。
   • TASK_STOP（终止态）：进程停止执行。通常进程在收到SIGSTOP、SIGTTIN、SIGTTOU等信号的时候会进入该状态。
10. linux的CFS调度机制是什么？时间片/policy（进程类别）/priority（优先级）/counter。linux的任务调度机制是什么？在每个进程的task_struct结构中有以下四项：policy、priority、counter、rt_priority。这四项是选择进程的依据。其中，policy是进程的调度策略，用来区分实时进程和普通进程，实时进程优先于普通进程运行；priority是进程(包括实时和普通)的静态优先级；counter是进程剩余的时间片，它的起始值就是priority的值；由于counter在后面计算一个处于可运行状态的进程值得运行的程度goodness时起重要作用，因此，counter 也可以看作是进程的动态优先级。rt_priority是实时进程特有的，用于实时进程间的选择。 Linux用函数goodness()来衡量一个处于可运行状态的进程值得运行的程度。该函数综合了以上提到的四项，还结合了一些其他的因素，给每个处于可运行状态的进程赋予一个权值(weight)，调度程序以这个权值作为选择进程的唯一依据。
11. goroutine的GPM，没有时间片和优先级的概念，但也支持“抢占式调度”。 goroutine的主要状态grunnable、grunning、gwaiting
12. 线程的状态
    • runnable
    • running
    • blocked
    • dead
13. 进程、线程与协程的区别
14. 操作系统写时复制:https://juejin.cn/post/6844903702373859335
15. 操作系统为什么设计用户态和内核态，用户态和内核态的权限不同？怎么解决IO频繁发生内核和用户态的态的切换（缓存）？
16. select、epoll的监听回调机制，红黑树？
17. 从一道面试题谈linux下fork的运行机制
18. malloc分配多少内存：http://fallincode.com/blog/2020/01/malloc%e6%9c%80%e5%a4%9a%e8%83%bd%e5%88%86%e9%85%8d%e5%a4%9a%e5%b0%91%e5%86%85%e5%ad%98/

存储系统，内存和存储

1. 寄存器、缓存cache、内存和磁盘
2. 可执行文件的空间结构，进程的空间结构(虚拟地址空间，栈，堆，未初始化变量，初始化区，代码）
3. 查看进程使用的资源，top，ps，cat /proc/pid/status
4. 进程的虚拟内存机制（虚拟地址-页表-物理地址）。Linux虚拟内存的实现需要6种机制的支持：地址映射机制、内存分配回收机制、缓存和刷新机制、请求页机制、交换机制和内存共享机制,内存管理程序通过映射机制把用户程序的逻辑地址映射到物理地址。当用户程序运行时，如果发现程序中要用的虚地址没有对应的物理内存，就发出了请求页要求。如果有空闲的内存可供分配，就请求分配内存(于是用到了内存的分配和回收)，并把正在使用的物理页记录在缓存中(使用了缓存机制)。如果没有足够的内存可供分配，那么就调用交换机制；腾出一部分内存。另外，在地址映射中要通过TLB(翻译后援存储器)来寻找物理页；交换机制中也要用到交换缓存，并且把物理页内容交换到交换文件中，也要修改页表来映射文件地址。
5. 操作系统内存分配算法常用缓存置换算法（FIFO，LRU，LFU），LRU算法的实现和优化？
6. Linux系统原理之文件系统（磁盘、分区、文件系统、inode表、data block）
7. 在linux执行ls上实际发生了什么
8. CPU寻址过程,tlb,cache miss.
9. 栈和堆的区别

系统编程以及其它注意事项

1. 使用过哪些进程间通讯机制，并详细说明,linux进程之间的通信7种方式
2. 内核函数、系统调用、库函数/API,strace系统调用追踪调试
3. coredump文件产生？内存访问越界、野指针、堆栈溢出等等
4. fork 和 vfork，exec，system（进程的用户空间是在执行系统调用的fork时创建的，基于写时复制的原理，子进程创建的时候继承了父进程的用户空间，仅仅是mm_struc结构的建立、vm_area_struct结构的建立以及页目录和页表的建立，并没有真正地复制一个物理页面，这也是为什么Linux内核能迅速地创建进程的原因之一。）写时复制(Copy-on-write)是一种可以推迟甚至免除拷贝数据的技术。内核此时并不复制整个进程空间，而是让父进程和子进程共享同一个拷贝。只有在需要写入的时候，数据才会被复制，从而使各个进程拥有各自的拷贝。也就是说，资源的复制只有在需要写入的时候才进行，在此之前，以只读方式共享。这种技术使地址空间上的页的拷贝被推迟到实际发生写入的时候。有时共享页根本不会被写入，例如，fork()后立即调用exec()，就无需复制父进程的页了。fork()的实际开销就是复制父进程的页表以及给子进程创建唯一的PCB。这种优化可以避免拷贝大量根本就不会使用的数据
5. 锁？互斥锁的属性设置、多进程共享内存的使用、多线程的使用互斥锁、pshaed和type设置。使用互斥量和条件变脸实现互斥锁
6. 共享内存的同步机制，使用信号量，无锁数据结构
7. 多线程里一个线程sleep，实质上是在干嘛，忙等还是闲等。？
8. exit()函数与_exit()函数最大的区别就在于exit()函数在调用exit系统调用之前要检查文件的打开情况，把文件缓冲区中的内容写回文件，就是”清理I/O缓冲”。
9. select/epoll https://www.cnblogs.com/anker/p/3265058.html

• select 内核态和用户态重复拷贝
• select 需要遍历遍历查找就绪的socket
• select 有数量限制1024
• epoll 注册时写进内核
• epoll_wait 返回就绪的事件

网络编程

1. 简单了解C语言的socket编程api。socket，bind，listen，accept，connect，read/write.

2. Linux下socket的五种I/O 模式，同步阻塞、同步非阻塞、同步I/O复用、异步I/O、信号驱动I/O

3. Linux套接字和I/O模型

4. select和epoll的区别

5. 什么是I/O 复用？关于I/O多路复用(又被称为“事件驱动”)，首先要理解的是，操作系统为你提供了一个功能，当你的某个socket可读或者可写的时候，它可以给你一个通知。这样当配合非阻塞的socket使用时，只有当系统通知我哪个描述符可读了，我才去执行read操作，可以保证每次read都能读到有效数据而不做纯返回-1和EAGAIN的无用功。写操作类似。操作系统的这个功能通过select/poll/epoll/kqueue之类的系统调用函数来使用，这些函数都可以同时监视多个描述符的读写就绪状况，这样，多个描述符的I/O操作都能在一个线程内并发交替地顺序完成，这就叫I/O多路复用，这里的“复用”指的是复用同一个线程。

6. 网络分析工具。ping/tcpdump/netstat/lsof

其它问题

1. 计算机中浮点数表示方法，以及浮点数转换中精度缺失的问题

一、

今年是2018年，腾讯20周年。我30周岁，刚好在腾讯工作满8年。

我从来没有想过自己会在同一家公司工作8年。因为4年足以读完大学，6年能让小孩读完小学，8年漫长得不可思议。

2010年，我刚大学毕业，加入腾讯。那一天，学生思维的我，不免以学生的尺度定计划：三年的时间，我应该足够从这一所“社会大学”毕业吧。

因此，我追赶时间，以这个截止日为目标，第一年学习高效地完成工作，第二年学习带新人，第三年学习影响力，翻译了一本前端书，和一本设计书。

我一步步从助理UI工程师晋级到高级UI工程师，先是积极响应需求，后来主动找事情做。我低着头，做事情非常“用力”，自信能把交给我的事情都做得很好。

我的博客文章80%都是头三年写的，现在回头看有很多幼稚的想法，但持续想和写才能提高。反过来说，要是现在还觉得好，那才糟糕。

二、

2013年，三年之痒。我开始觉得日常工作毫无挑战，考评时连续“优秀”跟“超出预期”拿到手软，但与此同时，也迎来新的工作挑战。

那时，我的领导问我以后的发展意向，是想继续研究技术深度，还是管理团队。我说如果有机会，尽量管理团队吧。

因为以我的理解，并不存在两种选项。这个问题就像“给你加工资，好不好啊”一样没有意义。学而优则仕，骨干不去领导团队，可能有点不负责任（现在想来很自恋，呵呵）。

虽然给了领导这样的答复，也开始进行正式的管理培训，但我内心还恋恋不舍想保留一点匠人心态。

个人能力要继续提高，我就开辟新的赛道：影响力。

2014年我认真地投入到写作练习中，在“26岁总结”中写下这段文字：

“在很多场景下我们都需要写作，我们要写短小的RTX，长一点的邮件，以及更长一点的分享文章、博客和专栏。关于写作，我觉得最有趣的一个事实是，优秀的写作者跟平庸的写作者所能达到的效果相差百倍以上，比优秀程序员和平庸程序员之间的差别还大。”

“优秀的写作者的RTX就是能让对方明白他的目的，并且像施了魔咒一样去合作。优秀的写作者的邮件能让接受者感兴趣，清晰地知道信息。优秀的写作者写的博客能用一段话击中读者心理，情不自禁点右上角的“分享到朋友圈”……这种效果100个平庸的写作者都达不到。”

“写作者需要的除了文笔，还有逻辑思维、数据分析、麦肯锡金字塔理论、心理学等等几乎所有的知识……”

每个人每天都要阅读微信、朋友圈、新闻、读书、知乎、小视频……关于写作对个人能力的的重要性，我认为怎么强调都不为过。因为广义的写作、演讲和设计，它们有一个共同的关键内核，就是搞清楚你的听众是谁，他们已有哪些信息，缺乏哪些信息，你要以怎么样的顺序来传达你想让对方做的事情。讲得邪乎点，它们都是一种“心理操纵术”。

那怎么才能学好写作（或者演讲，或者设计）呢？

答案无趣但有效：持续写。

反复阅读写出来的文字，毫不吝啬地删除无用的信息，重新再写。

达芬奇说过一句话：“Simplicity is the ultimate form of sophistication（简洁是终极的复杂）”。海明威每天写作之前都会把前一天的稿再改一次。

我也这样做，一开始在自己博客上写水文、在豆瓣写书评，感觉不够。2014年2月，我加入豆瓣专栏计划，需要每周写一篇超过3000字的专栏文章，结束后能获得200元鼓励金。我就像一个缺乏运动的人，强行把自己推入马拉松赛道。

我的前几篇写的很业余，错别字、口水话、病句、缺主语、串主语、一逗到底、唠唠叨叨、层级和顺序不对……那也还是要写。几个月后，20篇文章的专栏完结了，我的文字水平稳定从30分提升到50分，接近及格。

因为专栏内容相对新颖（可能是国内首批系统写“全栈工程师”的思考的专栏），慢慢积累一些读者并每周追看。读者宽容并热情地在评论区给我纠错。

后来，人民邮电出版社的责编在豆瓣上看到了我，就约我写稿。他说我写的东西已经很多，也有一些脉络，可以再整理一下出书。又是一个新的挑战。

先答应再说吧。

写书的过程只能说勉力支撑，因为只有50分的文字水平，却要输出80分的质量。把第一章整理好之后发过去，收到返回的修正稿，变成了另一篇文章。责编很专业，没有吐槽，只是做客观订正。

我羞愧难当，因为痛恨给人添麻烦。我记住修改过的问题种类，文法上字斟句酌，保证同类的不再犯。

因为责编会看出文字上的问题，然后给我修剪枝丫，但保持大树根基稳定就是我自己的责任，对读者的责任。我还买来《麦肯锡教我的写作武器》，更系统地学习写作。

经过好多轮的校对，我终于可以坦然说出，差不多达到基本的标准了。后面的事情我在“我出书了”中也都写了。2015年8月，我的书出版了。我在豆瓣上也慎重给《Web全栈工程师的自我修养》打了4星。

三、

写作成长磕磕碰碰的同时，管理之路也迂回曲折。试着带一段时间团队之后，我在2014年正式成为团队管理者。

当时对于团队管理的职责抱有几个不成熟心态：

管理比写代码更容易掌握，践行起来也更轻松
管理者门槛较低，相较于工程师缺乏核心竞争力，以后跳槽我还是要以工程师身份来定位
我喜欢专注做事情，不适合做管理
在工程师团队中，我要以最强的技术和努力来赢得尊重，我要有能力解决他们都解决不了的问题
因此，从2014-2016虽然也通过努力收获了一些个人成长，但对团队领导来讲其实我是不称职的。

有一个明显不称职的表现就是，每到员工考核期间，我就很纠结痛苦。我不希望有员工拿低于预期的考评，也害怕面对下属沟通面谈，当面对着他说你的绩效低于预期。

我能自律勤奋，但我很难改变自己的观念。最难的是，我甚至不知道自己是否应该改变自己的观念（瞧，这就是为什么改变观念是最难的），还是说退回去做一个还不错的工程师好了。

我在这个观念段位大概停留了两年多，经过断断续续的实践、阅读、观察和自省，我终于升级了。期间纠结和思考过程可以从2014到2016的博客文章中可见一斑。

总之，升级后的我认为：

管理比写代码（或任何一门硬技能）更难于掌握，这是我跟一些技术专家沟通得到的共识。硬技能的学习可以通过读书、培训班，甚至网络视频来学习，然后持续练习，越来越熟练，直到产生一个输出物。这非常简单，只要掌握了学习的方法，几个月就能学习一门硬技能。而管理的学习需要真实观念的转变，这个观念改变可能需要几年时间。
管理的核心观念是“管理者必须善于做有效的决策”。
管理者要注重组织对外的贡献。基于贡献来衡量每个人的绩效。
我开始积极与团队沟通，日常中看到不符合要求的输出，我就会直截了当地说“这不行，达不到基本水准”。

虽然比较严格，但也没有看到团队氛围下降的情况。因为从员工角度来讲，虽然乐于处在一个人际关系融洽的团队中，但更大的述求是加入一个充满专业人士的团队。每人都能从其他人身上学到特定知识，每人表现都是专业的。

我不再担心员工考核，因为它是一个有效的管理工具。有些无法用言语传达到的信息，可以通过绩效考核来传达。而且平时对于低绩效的员工就要做好预期管理，言行一致员工就不会困惑。

四、

2017年，我慢慢成为一个资深的管理者。又一次对工作驾轻就熟时，再次迎来新的挑战——转换岗位，领导腾讯微云UX设计团队。

我喜欢这个挑战，一方面它确实是一个“很大挑战”，受虐症的我无法拒绝。另一方面我一直处于产品流程中偏后的位置，但也对前置的思考很感兴趣。

因此，我梳理了自己面临的挑战：

之前领导的团队都是工程师，而现在的团队由交互设计师和视觉设计师组成。虽然管理的基本法是相通的，但新团队的成员还需要更多熟悉
自己的设计专业能力不够，尤其是在视觉上，无法给到“怎么做”的建议
新的UX设计团队面临比以前更复杂的外部关系
如何帮助下属专业晋升
但我也有我的优势：

能轻松地理解版本管理、多平台特性、开发挑战等“工程”难题，然后管理好风险
参加了三年多设计部的管理会，对设计的“味道”有感觉。或者说品味远远高出实现能力
在UI方案上，我有用户同理心，不只是从“好看”来评判设计
我的演讲呈现能力和写作能力可以提升团队
唔，也不全是坏消息嘛。那就开始做吧！

前半年仍然是勉力支撑（哭），但因为团队都在看着自己，不自信也要自信起来。

工作之余多体验各种APP，收集UI、运营、营收、品牌等方面的案例，进一步提升“产品力”。老婆平时在使用新的APP，或者被活动吸引付费时，我就会在边上观察她的行为。看到精彩处，我还会请求暂停，截图发给我。

总之，我希望自己的专业成长能快速补上权限扩大带来的差距。

慢慢地，有一些“腾讯微云用户体验不错”的口碑了，在自己能影响的范围内，使用我能调用的资源，慢慢地补齐漏洞，提升体验。

但仍然能力有限，有时候会出现仓促出的方案不合理的情况。这时更加如履薄冰，不是怕外部批评我，而是怕连累授权给我的上司，和被我能力所限的团队。加上腾讯微云也是一个有历史包袱的产品，所以仍然离自己心中的理想产品差很多。

团队成长上的挑战同样很大。

我仔细观察每一个人的优缺点，用人所长。于此同时我还要横向去看部门其他设计师的输出，不希望相对独立的产品导致了封闭的专业氛围。这将是接下来花半年到一年重点要解决的。

我对现在这个挑战，还远远没到驾轻就熟的状态，可能还需要两年以上时间来消化，所以有时工作会觉得比前几年加起来还累。

我时常以山本耀司的话给自己打鸡血：

我从不相信什么懒洋洋的自由，我向往的自由是通过勤奋和努力实现更广阔的人生，那样的自由才是珍贵的、有价值的。我相信一万小时定律，我从来不相信天上掉馅饼的灵感和坐等的成就。做一个自由又自律的人，靠势必实现的决心认真地活着。

勤奋和努力只是基础，以大多数人的努力程度之低，还根本谈不上拼天赋。

疲劳和兴奋交替，成就和挫折并存，曲折前行，比轻松混日子更有趣。

五、

回头看，这八年来，我从来都只是“短暂地胜任”自己的工作。每当我觉得能够驾轻就熟地处理目前的日常，就会迎来新的挑战。

想到这一点，我突然悟到一种“佛性”的工作哲学：

每当你能胜任当前的工作，就会迎来更高难度的挑战。

每一个能胜任当前工作岗位的人，都会被提拔。继续胜任，那就继续提拔，直到不能胜任。

因此，不用特别在意自己的头衔、权限和职级，外部的认可是你能力的反馈。你没有被提拔，大概率是因为还不胜任当前工作。如果完全胜任还没有被安排更有挑战的工作，要么自己找事情做，要么跳槽转岗。

反过来说，自知自己能力还达不到岗位要求也不用担心，不胜任是常态，以胜任为目标就好啦。

对于职场马拉松来说，心态放松，保持作息，持续养成好的习惯，学习好的方法和观念，这才是最重要的。

我写字的地方迁移到公众号啦~欢迎关注我的公众号：余果专栏

基本步骤

• hexo 文档：https://hexo.io/zh-cn/docs/
• 安装git、node、npm、hexo、next主题
• 在github建立wxquare.github.io仓库，两个branch，分别为master和hexo
• 使用markdown在hexo branch 写文章，hexo generate生成静态文件，并通过hexo deploy 部署到远端
• 申请域名wxquare.top，绑定wxquare.github.io
• https://wxquare.github.io/

写文章发布blog的流程

• 在hexo branch /source/_posts 下使用markdown写文章
• 使用hexo genergate 生成静态文件
• hexo server 查看本地效果
• hexo deploy 到远端
• 提交修改文件到hexo

1
2
3
4
5

npm i -g hexo  安装hexo
hexo init  初始化  
hexo generate  生成静态网页
hexo server 启动服务器 （浏览器输入http://localhost:4000/验证是否正确。）
hexo deploy 部署到远端 （wxquare.github.io）

hexo 配置

1. 修改站点配置文件_config.yml，使得能将本地博客部署到github上

   1 2 3 4

   deploy: type: git repo: https://github.com/wxquare/wxquare.github.io.git branch: master

next主题 配置

1. 主题设置和修改。hexo初始化默认的主题是landscape，https://hexo.io/themes/提供了许多的主题，根据喜好为博客的主题，主题的文档提供了使用方法，设置相应的参数，调整为自己喜欢的格式。我这里选择的Next主题
2. 安装next主题：https://theme-next.js.org/docs/getting-started/
3. 主题设置：https://theme-next.js.org/docs/theme-settings/

其它

1. 增加分类
2. hexo 增加支持markdown公式：http://stevenshi.me/2017/06/26/hexo-insert-formula/
3. 博客中的图片，将图片放在hexo分支的source/images目录下面，markdown和blog中均可以看到
4. Hexo博客Next主题添加统计文章阅读量功能：https://bjtu-hxs.github.io/2018/06/12/leancloud-config/

　　在2018年的CVPR上SiameseRPN模型被提出，它宣称在单目标跟踪问题上做到了state-of-the-art，能同时兼顾精度(accuracy)和速度(efficiency)。在这之后，很快又在ECCV上发表了DaSiamRPN模型，它在SiameseRPN基础进一步提升了追踪的性能。SiameseRPN不是一簇而就的，它的设计思想来源于SiameseFc，并引入物体检测领域的区域推荐网络(RPN),通过网络回归避免了多尺度测试，同时得到更加精准的目标框和目标的位置。实际使用中发现DaSiamRPN相比传统的KCF效果直观感受确实精度有较大提升，在普通pc无GPU环境上大概是10.6fps。这里主要结合SimeseRPN的论文和DaSiamRPN的代码帮助了解SimeseRPN的模型结构以及DaSiamRPN的运行过程。

SiameseRPN模型

　　Siamese-RPN本质上是组合网络模型，它包括用于特征提取的Siamese网络和生成候选区域的RPN网络。
　　Siamese特征提取网络：它目前在追踪领域使用比较多，包括模板分支(template branch)和检测分支(detection branch)，它们都是经过裁剪的AlexNet卷积网络，用于提取图像的特征。两个分支网络参数和权重值完全相同，只是输入不同，模板分支输入模板帧中的目标部分(target patch)，检测分支输入当前需要追踪的帧的区域(target patch)。
　　RPN(region proposal subnetwork)候选区域生成网络：它包括的分类(classification)和回归(regression)两个分支。这里有个重要的锚点(anchor),就是通过RPN对每个锚点上的k个不同宽度和高度的矩形分类和回归，得到感兴趣区域。每个anhcor box要分前景和背景，所以cls=2k；而每个anchor box都有[x, y, w, h]对应4个偏移量，所以reg=4k。

　　因此设模板分支输入为$z$维度为(127,127,3)，首先通过Siamese网络特征提取得到$ψ(z)$维度为(6,6,256)，然后再经历卷积分别的到$[ψ(z)]{cls}$和$[ψ(z)]{res}$。检测分支输入为$x$，$ψ(x)$为Siamese特征提取网路的输出，以$[ψ(z)]{cls}$和$[ψ(z)]{res}$为核卷积得到最终的SiameseRPN的输出，$*$表示卷积运算。
$$A_{w×h×2k}^{cls} = [ψ(x)]{cls} * [ψ(z)]{cls}$$

$$A_{w×h×4k}^{res} = [ψ(x)]{res} * [ψ(z)]{res}$$

DaSiamRPN视频追踪的过程

　　DaSiamRPN做视频目标追踪，DaSiamRPN相比SiameseRPN做了进一步的优化，例如训练时引入采样策略控制不平衡的样本分布，设计了一种distractor-aware模块执行增量学习等。结合官方的https://github.com/foolwood/DaSiamRPN 中的例子，很容易将demo运行起来。需要注意的是github上的代码需要gpu运行环境，如果要在无gpu机器上运行DaSiamRPN的demo需要将有关cuda代码去掉。例如将将net.eval().cuda()换成net.eval()。DaSiamRPN的运行包含两个步骤：

1. 初始化。输入模板帧，得到$[ψ(z)]{cls}$和$[ψ(z)]{res}$两个用于卷积的核。
2. 追踪。将待追踪帧输入到模型，得到每个候选区域的score和偏移delta。从候选区域中选出分数最高的候选区域proposal。

初始化

1. 输出模板图片im，模板图片中目标位置target_pos，目标大小target_size，使用get_subwindow_tracking函数裁剪目标区域临近部分(target patch),并将裁剪得到图片resize到宽和高为127的图片。
2. 将模板目标区域裁剪好的视频输入网络模型的模板分支(template branch)，得到$[ψ(z)]{cls}$和$[ψ(z)]{res}$
3. 使用generate_anchor函数产生anchers，其大小为$(271-127)/8+1=19,19*19*5=1805$，anchor的维度为(4,1805)，这表示会有1805个候选区域，偏移量$d_x,d_y,d_w,d_h$

追踪

1. 输入追踪的图片im，基于上一帧的target_pos和目标的大小位置target_size，在图片中裁剪部分区域并将该区域resize到271*271得到x_crop。
2. 将x_crop输入网络的检测分支(detection branch)得到对所有anchor进行分类和回归得到delta和score。
3. 根据delta获取细化后的候选区域(refinement coordinates)

   1 2 3 4 5

   # generate the refined top K proposals delta[0, :] = delta[0, :] * p.anchor[:, 2] + p.anchor[:, 0] #x delta[1, :] = delta[1, :] * p.anchor[:, 3] + p.anchor[:, 1] #y delta[2, :] = np.exp(delta[2, :]) * p.anchor[:, 2] #w delta[3, :] = np.exp(delta[3, :]) * p.anchor[:, 3] #h

4. 结合scale penalty、ration penalty、cosine window调整每个候选区域score中每个候选区域的分数,选出分数最大的候选区域best_pscore_id.

   1 2 3 4 5 6 7 8

   # size penalty s_c = change(sz(delta[2, :], delta[3, :]) / sz_wh(target_sz)) # scale penalty r_c = change((target_sz[0] / target_sz[1]) / (delta[2, :] / delta[3, :])) # ratio penalty penalty = np.exp(-(r_c * s_c - 1.) * p.penalty_k) pscore = penalty * score # window float pscore = pscore * (1 - p.window_influence) + window * p.window_influence best_pscore_id = np.argmax(pscore)

5. 计算出当前帧目标的位置target_pos和target_size。

   1 2 3 4 5 6 7 8 9 10 11 12

   target = delta[:, best_pscore_id] / scale_z target_sz = target_sz / scale_z lr = penalty[best_pscore_id] * score[best_pscore_id] * p.lr res_x = target_pos[0] + target[0] res_y = target_pos[1] + target[1] res_w = target_sz[0] * (1 - lr) + target[2] * lr res_h = target_sz[1] * (1 - lr) + target[3] * lr target_pos = np.array([res_x, res_y]) target_sz = np.array([res_w, res_h])

参考：

1. https://zhuanlan.zhihu.com/p/37856765
2. https://github.com/foolwood/DaSiamRPN
3. http://openaccess.thecvf.com/content_cvpr_2018/papers/Li_High_Performance_Visual_CVPR_2018_paper.pdf

　　TVM主要包括两个部分，一个是Relay和图优化(graph-level)，另一个就是算子（operator）级别优化，这里简单写最近了解到的关于relay和图优化方面的东西。我们都知道深度学习网络通常都是通过计算图来描述的，计算图中的节点表示各种同的算子(opertor),边表示算子之间的依赖关系。Relay可以理解为一种可以描述深度学习网络的函数式编程语言，通过relay可以描述复杂的深度网络，文中提到了control flow。最近一段时间的时间学习直观的感受的Relay编写网络模型和其它框架没什么太多的区别，但是提供的文本形式的中间表示，对开发和调试有很大的帮助。另外，它提供了许多用于图优化的pass，供大家学习和参考。测试代码都在0.6版本上调试通过。
代码地址：https://github.com/wxquare/programming/tree/master/blog/TVM_graph_optimization

一、Hello Relay

既然Relay是一种可以描述计算的函数式语言，逛社区的发现一段代码，可以当作Relay的第一个程序。
API参考:https://docs.tvm.ai/api/python/relay/index.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from tvm import relay
import tvm.relay.op

x = relay.expr.var('x', relay.scalar_type('int64'), dtype = 'int64')
one = relay.expr.const(1, dtype = 'int64')
add = relay.op.tensor.add(x, one)    
func = relay.expr.Function([x], add, relay.scalar_type('int64'))

mod = relay.Module.from_expr(func)  # note this API
print("Relay module function:\n", mod.astext(show_meta_data=False))
graph, lib, params = tvm.relay.build(mod, 'llvm', params={})
print("TVM graph:\n", graph)
print("TVM parameters:\n", params)
print("TVM compiled target function:\n", lib.get_source())

二、使用Relay定义卷积单元

在学习Relay的时候参考了https://zhuanlan.zhihu.com/p/91283238 这篇文章。但是可能因为版本的问题，很多API多不兼容了，因此修改了一些地方，建议读者也可以去看一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

import tvm
from tvm.relay import transform
import tvm.relay as relay
import numpy as np
from tvm.contrib import graph_runtime


def batch_norm_infer(data,
                    gamma=None,
                    beta=None,
                    moving_mean=None,
                    moving_var=None,
                    **kwargs):
    name = kwargs.get("name")
    kwargs.pop("name")
    if not gamma:
        gamma = relay.var(name + "_gamma")
    if not beta:
        beta = relay.var(name + "_beta")
    if not moving_mean:
        moving_mean = relay.var(name + "_moving_mean")
    if not moving_var:
        moving_var = relay.var(name + "_moving_var")
    return relay.nn.batch_norm(data,
                            gamma=gamma,
                            beta=beta,
                            moving_mean=moving_mean,
                            moving_var=moving_var,
                            **kwargs)[0]

def conv2d(data, weight=None, **kwargs):
    name = kwargs.get("name")
    kwargs.pop("name")
    if not weight:
        weight = relay.var(name + "_weight")
    return relay.nn.conv2d(data, weight, **kwargs)


def conv_block(data, name, channels, kernel_size=(3, 3), strides=(1, 1),
            padding=(1, 1), epsilon=1e-5):
    conv = conv2d(
        data=data,
        channels=channels,
        kernel_size=kernel_size,
        strides=strides,
        padding=padding,
        data_layout='NCHW',
        name=name+'_conv')
    bn = batch_norm_infer(data=conv, epsilon=epsilon, name=name + '_bn')
    act = relay.nn.relu(data=bn)
    return act


data_shape = (1, 3, 224, 224)
kernel_shape = (32, 3, 3, 3)
dtype = "float32"
data = relay.var("data", shape=data_shape, dtype=dtype)
act = conv_block(data, "graph", 32, strides=(2, 2))
func = relay.Function(relay.analysis.free_vars(act),act)


mod = relay.Module.from_expr(func)
mod = relay.transform.InferType()(mod)
shape_dict = {
    v.name_hint : v.checked_type for v in mod["main"].params}
np.random.seed(0)
params = {}
for k, v in shape_dict.items():
    if k == "data":
        continue
    init_value = np.random.uniform(-1, 1, v.concrete_shape).astype(v.dtype)
    params[k] = tvm.nd.array(init_value, ctx=tvm.cpu(0))

target = "llvm"
ctx = tvm.context(target, 0)
print("Relay module function:\n", mod.astext(show_meta_data=False))
print("TVM parameters:\n", params.keys())

with relay.build_config(opt_level=3):
    graph, lib, params = relay.build(mod, target, params=params)

print("TVM graph:\n", graph)
print("TVM parameters:\n", params.keys())
# print("TVM compiled target function:\n", lib.get_source())
module = graph_runtime.create(graph, lib, ctx)
data_tvm = tvm.nd.array((np.random.uniform(-1, 1, size=data_shape)).astype(dtype))
module.set_input('data', data_tvm)
module.set_input(**params)
module.run()
output = module.get_output(0)

三、Relay Graph Optimization

前面两个例子介绍了怎么使用relay构建网络，这个部分介绍怎么使用relay做图优化。上面例子代码中没有直接图优化的代码，而是包含在relay.build中。通过追踪代码，我们这部分的逻辑集中在 https://github.com/apache/incubator-tvm/blob/v0.6/src/relay/backend/build_module.cc 这个文件的optimize函数中。这里罗列了代码用到的pass，relay提供了方便的的文本形式中间描述，感兴趣的可以自己试一下每个pass之后，发生了哪些变化。

• relay::qnn::transform::Legalize())，这个pass和qnn有关
• transform::Legalize()，我理解的这个是和目标有关的优化，一个表达式虽然在语义上等效于另一个，但可以在目标上具有更好的性能。这个在需要在异构环境下生效。
• transform::SimplifyInference() 。
  简化推理阶段的数据流图。在语义上等于输入表达式的简化表达式将被返回。例如将BatchNorm展开以及去掉 dropout。
• transform::EliminateCommonSubexpr(fskip))，去除公共子表达式。
• transform::CombineParallelConv2D(3)，将多个conv2d运算符合并为一个，这部分优化会将具有相同输入的卷积合并成一个大的卷积运算。
• transform::CombineParallelDense(3))，将多个dense运算符组合为一个
• transform::FoldConstant()，常量传播优化。
• transform::FoldScaleAxis()
• transform::CanonicalizeCast()，
  将特殊运算符规范化为基本运算符。这样可以简化后续分析，例如将bias_add扩展为expand_dims和broadcast_add
• transform::CanonicalizeOps()
• transform::AlterOpLayout()，layout 变换
• transform::FuseOps()，算子融合，根据一些规则，将expr中的运算符融合为较大的运算符。

四、使用Python API Relay 图优化

TVM核心代码是采用C++编写的，但是也提供了Python接口，这方面初学者体验的使用。Relay图优化核心功能都提供了对应的API，因此可以尝试一下，非常简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def my_optimize(func,params=None):

    if params:
        graph = _bind_params(func, params)

    # https://docs.tvm.ai/api/python/relay/transform.html
    optimize = relay.transform.Sequential([relay.transform.SimplifyInference(),
                                      relay.transform.FoldConstant(),
                                      relay.transform.FoldScaleAxis(),
                                      relay.transform.CanonicalizeOps(),
                                      relay.transform.FoldConstant()])

    mod = relay.Module.from_expr(graph)
    mod = optimize(mod)
    return mod["main"]

mod['main'] = my_optimize(mod['main'], params)
print("Relay module function:\n", mod.astext(show_meta_data=False))

这里可以对比优化前后的IR.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Relay module function:
 v0.0.4
def @main(%data: Tensor[(1, 3, 224, 224), float32], %graph_conv_weight: Tensor[(32, 3, 3, 3), float32], %graph_bn_gamma: Tensor[(32), float32], %graph_bn_beta: Tensor[(32), float32], %graph_bn_moving_mean: Tensor[(32), float32], %graph_bn_moving_var: Tensor[(32), float32]) -> Tensor[(1, 32, 112, 112), float32] {
  %0 = nn.conv2d(%data, %graph_conv_weight, strides=[2, 2], padding=[1, 1], channels=32, kernel_size=[3, 3]) /* ty=Tensor[(1, 32, 112, 112), float32] */;
  %1 = nn.batch_norm(%0, %graph_bn_gamma, %graph_bn_beta, %graph_bn_moving_mean, %graph_bn_moving_var) /* ty=(Tensor[(1, 32, 112, 112), float32], Tensor[(32), float32], Tensor[(32), float32]) */;
  %2 = %1.0;
  nn.relu(%2) /* ty=Tensor[(1, 32, 112, 112), float32] */
}
# =====================================
Relay module function:
 v0.0.4
def @main(%data: Tensor[(1, 3, 224, 224), float32]) -> Tensor[(1, 32, 112, 112), float32] {
  %0 = nn.conv2d(%data, meta[relay.Constant][0] /* ty=Tensor[(32, 3, 3, 3), float32] */ /* ty=Tensor[(32, 3, 3, 3), float32] */, strides=[2, 2], padding=[1, 1], channels=32, kernel_size=[3, 3]) /* ty=Tensor[(1, 32, 112, 112), float32] */;
  %1 = multiply(%0, meta[relay.Constant][1] /* ty=Tensor[(32, 1, 1), float32] */ /* ty=Tensor[(32, 1, 1), float32] */) /* ty=Tensor[(1, 32, 112, 112), float32] */;
  %2 = add(%1, meta[relay.Constant][2] /* ty=Tensor[(32, 1, 1), float32] */ /* ty=Tensor[(32, 1, 1), float32] */) /* ty=Tensor[(1, 32, 112, 112), float32] */;
  nn.relu(%2) /* ty=Tensor[(1, 32, 112, 112), float32] */
}

// meta data omitted. you can use show_meta_data=True to include meta data

参考与进阶学习：
[1]. https://www.zhihu.com/question/331611341/answer/875630325
[2]. https://zhuanlan.zhihu.com/p/91283238
[3]. https://docs.tvm.ai/dev/relay_intro.html
[4]. https://docs.tvm.ai/dev/relay_add_op.html
[5]. https://docs.tvm.ai/dev/relay_add_pass.html
[6]. https://arxiv.org/pdf/1810.00952.pdf

　　在《初识TVM，相比于tensorflow的2倍性能提升》之后，最近花了一点业余时间了解TVM及其周边，并进行相应的性能测试。整体感受是计算优化(GEMM)是非常繁杂的工程工作，需要花费大量的时间和精力才能有比较好的效果。numpy非常优秀，大矩阵乘法硬件利用率在90%以上。TVM在GEMM优化上能实现和numpy相当的效果，重要的是它能大大简化工作量。参考了一些文章，这里简单罗列了几个知识点和测试数据。

1. 怎么评估硬件的理论性能？浮点峰值？
2. 简单测试一下numpy的性能数据，硬件利用率
3. 怎么做GEMM优化？
4. TVM怎么做GEMM的优化？及其与numpy性能的比较

怎么评估硬件的计算性能

　　对于性能优化来说，了解硬件的性能指标是非常有必要的。在Linux系统上可以通过/proc/cpuinfo文件看看机器的配置。比如CPU主频、CPU核数core、cache大小、是否支持向量指令SSE、AVX2、AVX512等，这些对于计算性能有非常大的影响。浮点峰值那些事儿。通常我们使用浮点计算能力来衡量硬件的性能，对于多核服务器来说，频率为2.4G，支持AVX2，FMA向量指令，单核性能如下：
对于float32理论峰值为2.4G * （8+8） * 2 = 76.8 GFLOPS
对于float64理论峰值为2.4G * （4+4） * 2 = 38.4 GFLOPS

测试numpy GEMM硬件利用率

　　numpy非常优秀，我们通过矩阵乘法了解其性能数据。测试机器为一台多核的服务器，主频是2.4G，支持FMA和AVX2向量指令。测试了不同size矩阵相乘的性能数据。分别测试了单核和四核状态下对float32和float64的不同size(32,128,1024,2048等）矩阵相乘的性能数据。测试结果显示numpy在大矩阵相乘中，硬件利用率大概在90%左右。

name | 32 | 128|1024|2048|4096|10240|硬件利用率|
-|-|-|
单核float32|1.82|36.16|67.99|67.94|68.88|69.88|91.0%
单核float64|1.67|19.49|35.56|35.40|36.11|36.90|96.1%
四核float32|6.6|52.2|225.42|246.2|244.2|256.0|83.8%
四核float64|5.56|37.62|116.42|120.39|127.03|141.15|91.9%
测试代码

怎么优化GEMM？

　　通用矩阵乘(GEMM)是计算领域非常基础且核心的工作，目前已有大量的工作，这里就不赘述了。大体上通过分块来减少访存次数、存储顺序、提高cache命中率、利用寄存器提高效率、利用SSE等向量指令提高计算效率等方法。https://github.com/flame/how-to-optimize-gemm/wiki 一步一步详细介绍了GEMM优化的过程，这里在此基础上增加FMA指令的使用，测试了其在1024*1204矩阵相乘的硬件利用率：

name | 64 | 256 |512|1024|硬件利用率|主要优化点|
-|-|-|
MMult0|1.51|0.79|0.66|0.65|1.69%|base
MMult_1x4_5|2.15|1.08|0.72|0.716|2.6%|一次计算1x4个数
MMult_1x4_9|4.90|3.15|3.10|3.14|8.18%|1x4，寄存器
MMult_4x4_5|2.76|1.53|1.26|1.26|3.28%|一次计算4x4个数
MMult_4x4_9|5.19|2.92|2.88|2.87|7.47%|4x4，寄存器
MMult_4x4_10|5.95|4.16|4.04|4.01|10.4%|4x4，寄存器，SSE
MMult_4x4_10_1|10.0|6.6|6.35|6.4|16.7%|4x4，寄存器，FMA
MMult_4x4_11_1|14.5|8.95|7.16|7.08|18.4%|4x4，寄存器，FMA，分块(缓存)
MMult_4x4_15_1|11.3|11.6|11.7|11.7|30.4%|4x4，寄存器，FMA，分块，内存顺序

测试代码

TVM GEMM优化与numpy性能比较

　　TVM官网上有关于其针对GEMM的优化的schedule，这里也不赘述了，感兴趣的可以参考后面的参考文章进一步学习，这里测试了在1024*1024矩阵乘法的效率以及其和numpy的比较，可以看出TVM在简单编码的基础上能达到和numpy相当的性能。

| TVM运行时间 | numpy运行时间 |
-|-|-|
baseline|2.49s|0.0135s
blocking|1.73s|0.012s
vectorization|0.411s|0.0117s
loop permutaion|0.104s|0.0116s
packing|0.0987s|0.0103s
write_cache|0.0926s|0.01158s
parallel|0.018s|0.012s
auto-tvm|0.014s|0.0112s
每个阶段测试代码

参考学习链接：
1、浮点峰值那些事儿https://zhuanlan.zhihu.com/p/28226956
2、通用矩阵乘（GEMM）优化算法，https://jackwish.net/gemm-optimization.html
3、如何利用TVM快速实现超越Numpy(MKL)的GEMM。https://zhuanlan.zhihu.com/p/75203171
4、tutorial：https://docs.tvm.ai/tutorials/optimize/opt_gemm.html
5、d2ltvm:http://tvm.d2l.ai/chapter_cpu_schedules/index.html
6、https://github.com/flame/how-to-optimize-gemm

代码生成的接口

　　TVM代码生成的接口和主要类型，可以总结为两个build，两个module，两个function。它提供了两个代码生成的接口，tvm.build和tvm.relay.build，前者是针对算子的代码生成，后者是针对relay计算图的代码生成。在0.7版本中，tvm进行了IR的统一，使得两个build的输入参数类型都可以是IRModule，输出类型都是运行时Module。尽管两个build接口统一了输入类型，但是内部包含的函数类型是不一样的，算子编译时是tvm.tir.function.PrimFunc，而relay图编译时函数类型是tvm.relay.function.Function。TVM在设计时提供了方便的调试功能，通过IRModule的astext函数可以查看ir中间描述，通过运行时module的get_source查看生成的代码。下面通过两个简单的例子查看算子和relay图的ir中间描述和以及对应生成的源代码。

• tvm.build
• tvm.relay.build
• tvm.ir.module.IRModule
• tvm.runtime.module.Module
• tvm.tir.function.PrimFunc
• tvm.relay.function.Function

算子编译

import tvm
from tvm import te

M = 1024
K = 1024
N = 1024

# Algorithm
k = te.reduce_axis((0, K), 'k')
A = te.placeholder((M, K), name='A')
B = te.placeholder((K, N), name='B')
C = te.compute(
           (M, N),
           lambda x, y: te.sum(A[x, k] * B[k, y], axis=k),
           name='C')

# Default schedule
s = te.create_schedule(C.op)
ir_m = tvm.lower(s, [A, B, C], simple_mode=True,name='mmult')
rt_m = tvm.build(ir_m, [A, B, C], target='c', name='mmult')

# print tir
print("tir:\n", ir_m.astext(show_meta_data=False))
# print source code
print("source code:\n",rt_m.get_source())

relay图编译

import ssl
ssl._create_default_https_context = ssl._create_unverified_context

from tvm import relay
from tvm.relay import testing
from tvm.contrib import util
import tvm

# Resnet18 workload
resnet18_mod, resnet18_params = relay.testing.resnet.get_workload(num_layers=18)

with relay.build_config(opt_level=0):
    _, resnet18_lib, _ = relay.build_module.build(resnet18_mod, "llvm", params=resnet18_params)

# print relay ir
print(resnet18_mod.astext(show_meta_data=False))

# print source code
print(resnet18_lib.get_source())

代码生成的流程

　　通过上面两个例子我们知道tvm代码生成接口上是IRModule到运行时module的转换，它完成tir或者relay ir到目标target代码的编译，例如c或者llvm IR等。下面的流程图描述整个代码的编译流程，深色表示C++代码，浅色表示python代码。算子编译时会首先进行tir的优化，分离出host和device部分，之后会调用注册的target.build.target函数进行编译。relay图编译相比算子稍微复杂一点，核心代码采用C++开发。它会通过relayBuildModule.Optimize进行relay图优化，之后针对module中的每个lower_funcs进行编译之前，合成最终的运行时module，其后部分的编译流程和算子编译相似。

Codegen的实现

TVM针对不同的target实现了许多的codgen，它完成了tir到目标代码的翻译工作，例如c,llvm ir等。我们也可以根据需求实现自己的codegen，官网提供了一个教程。

• target.build.c
• target.build.llvm
• target.build.cuda
• target.build.opencl
• target.build.opengl
• target.build.metal
• target.build.vulkan

References

[1]. Unified IR RFC,https://github.com/apache/incubator-tvm/issues/4617
[2]. Codegen的实现：https://tvm.apache.org/docs/dev/relay_bring_your_own_codegen.html

　　
　　最近在做深度学习模型加速的工作，先后尝试了模型权重量化(quantization)、模型权重稀疏（sparsification）和模型通道剪枝(channel pruning)等压缩方法，但效果都不明显。权重量化和稀疏属于非结构化的压缩，需要推理引擎和硬件的优化才能实现推理加速，通道剪枝能直接减少FLOPs，确实能卷积网络的效率，在ResNet56网络中能大概提升卷积50%的速度。在工程实践中，除了通过模型压缩提升推理性能，还可以通过优化推理引擎提高推理效率。目前存在多种开源的推理引擎，我首先尝试了TVM。

为什么选择TVM

　　为提升深度学习模型的推理效率，设备平台制造商针对自己的平台推出优化的推理引擎，例如NAVIDA的tensorRT，Intel的OpenVINO，Tencent针对移动端应用推出NCNN等。目前，深度学习模型应用广泛，在服务端和移动端都有应用，甚至于特殊的嵌入式场景想，它们都有加速模型推理的需求。个人感觉针对不同平台选择不同的推理引擎，学习成本太高。我这里选择尝试TVM，主要有以下几个原因：

• 尝试了过一些模型压缩方法，效率提升有限
• 有些是模型压缩方法需要推理引擎和硬件的支持的，例如量化
• tensorflow推理效率有限，需要更好的推理引擎
• 针对平台选择不同推理引擎，学习成本太高
• 需要能支持跨平台的推理引擎，未来可能在定制的嵌入式芯片上运行深度学习模型
• 除了TVM之外，还存在XLA之类方案，选择TVM也是因为tianqi等大佬主导的项目，相信大佬！

初次体验TVM，相比于tensorflow2倍的性能提升

　　看了几篇TVM介绍文章后，了解到它是从深度学习编译器的角度来做推理引擎，目前技术领域还比较新，具体技术细节以后有机会会深入学习，这里主要想体验一下使用TVM做深度模型推理，重点是推理效率的提升，因为是骡子还是马得拉出来遛遛。参考官方文档进行编译安装，整个过程还是比较简单的，结果显示相比于tensorflow大概100%的性能提升。实验环境是ubuntu 19.04，x86_64架构。

1. 安装llvm,也可源码编译

   1	$ sudo apt-get install llvm

2. 编译TVM

   1 2 3 4 5 6 7

   $ git clone --recursive https://github.com/dmlc/tvm.git $ cd tvm $$ mkdir build $ cp cmake/config.cmake build # 编辑config.cmake 然后将USE_LLVM OFF 改为 set(USE_LLVM /usr/bin/llvm-config) $ cd build $ cmake .. $ cmake -j4

3. 编辑.bashrc配置Python环境

   1 2	export TVM_HOME=/home/xxxx/code/tvm export PYTHONPATH=$TVM_HOME/python:$TVM_HOME/topi/python:$TVM_HOME/nnvm/python

4. 官方Compile Tensorflow Models
   直接运行出现了两个问题，下载文件时和SSL相关，另外一个是缺少antlr

   1 2 3 4 5 6 7

   # install antlr $ pip install antlr4-python3-runtime # debug ssl import ssl ssl._create_default_https_context = ssl._create_unverified_context # run demo $ python from_tensorflow.py

5. 在代码中加入时间测试，实验测试结果。TVM与测试时间为0.277s，tensorflow为0.586s。

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   ============ TVM ============ 0.2770531177520752 African elephant, Loxodonta africana (score = 0.58335) tusker (score = 0.33901) Indian elephant, Elephas maximus (score = 0.02391) banana (score = 0.00025) vault (score = 0.00021) ============= Tensorflow ===== 0.58619508743286133 ===== TENSORFLOW RESULTS ======= African elephant, Loxodonta africana (score = 0.58394) tusker (score = 0.33909) Indian elephant, Elephas maximus (score = 0.03186) banana (score = 0.00022) desk (score = 0.00019)

未填的坑

　　过程遇到一个坑，查了TVM社区，没有很好的解答，看起来好像会和性能有关，希望路过的大佬能帮忙解决。https://discuss.tvm.ai/t/cannot-find-config-for-target-llvm-when-using-autotvm-in-tensorflow-example-for-cpu/1544

1
2
3
4

WARNING:autotvm:Cannot find config for target=llvm, workload=('conv2d', (1, 8, 8, 2048, 'float32'), (1, 1, 2048, 384, 'float32'), (1, 1), (0, 0), (1, 1), 'NHWC', 'float32'). A fallback configuration is used, which may bring great performance regression.
WARNING:autotvm:Cannot find config for target=llvm, workload=('conv2d', (1, 8, 8, 2048, 'float32'), (1, 1, 2048, 448, 'float32'), (1, 1), (0, 0), (1, 1), 'NHWC', 'float32'). A fallback configuration is used, which may bring great performance regression.
WARNING:autotvm:Cannot find config for target=llvm, workload=('conv2d', (1, 8, 8, 2048, 'float32'), (1, 1, 2048, 192, 'float32'), (1, 1), (0, 0), (1, 1), 'NHWC', 'float32'). A fallback configuration is used, which may bring great performance regression.

参考：

1. tvm install: https://docs.tvm.ai/install/from_source.html
2. tvm tutorial: Compile Tensorflow Models
3. 未填的坑：https://discuss.tvm.ai/t/cannot-find-config-for-target-llvm-when-using-autotvm-in-tensorflow-example-for-cpu/1544

　　坚持了接近一年的视频算法相关的项目，老板最终还是喊停了。并没有感到特别意外，只是在对一个东西突然有些兴趣或者说入门的时候，戛然而止，多少有些不甘心和遗憾，但是以后会在业余继续学习的，也希望自己在2020年能把工作逐渐聚焦到这块吧。

　　接触TVM到有两个原因。一是需要支持多种优化手段的推理引擎，例如量化、图优化、稀疏优化、模型压缩剪枝等。尝试过在tensorflow的quantization和非结构性剪枝(no-structural pruning)，加速效果非常一般，因为这些优化手段需要推理引擎的支持，但是当时我们都是纯后台出身，也没人掌握这个内容。再之后尝试channel pruning，终于取得了一些进展，但是30%的提升leader并不满意。二是需要支持多种平台的推理引擎，例如NV GPU/x86/ARM GPU等。由于组内业务迟迟没有好的落地场景，尝试了多种手段，需要的把深度模型部署在不同的平台上。记得有次，花了两周的时间把DaSiamRPN模型移植到终端上。从零开始pytorch、onnx、tflite、android，期间踩了许多的坑，结果在移动端运行需要4秒时间来处理一帧图像。。。期间同事也曾通过tensorRT部署模型，效率反而下降。一次偶然的机会了解到TVM，当时感觉它可能是比较适合我们团队的需求的。

　　由于我之前学习信号处理的，比较容易理解量化。模型量化quantization也在深度学习在部署落地时提高效率的常用的方法。之前有写过关于tensorflow模型量化的方法，写得不好，对于想学习模型量化知识的可以参考下面链接进行学习：

模型量化相关：
【1】神经网络量化简介
【2】Tensort量化:8-bit-inference-with-tensort
【3】阮一峰：浮点数的二进制表示
【4】Quantizing deep convolutional networks for efficient inference

TVM量化相关RFC
【INT8 quantization proposal】：https://discuss.tvm.ai/t/int8-quantization-proposal/516（2018.02.02）
【TVM quantizationRFC】 https://github.com/apache/incubator-tvm/issues/2259(2018.12.09)

　　目前，官网上还没有关于模型量化的教程和文档，对于刚接触新手来说可能有些麻烦，这里提供提供一个参考代码，方便新手学习。除此之外，也测试了TVM的int8量化性能，结果显示TVM的量化加速效果不是很好，甚至略有下降，需要配合autotvm一起使用。测试代码地址。测试结果如下，希望对大家了解TVM有帮助。

　　深度学习模型落地需要考虑决定推理（inference）过程所需的计算资源（成本）和效率（系统的吞吐量和延时），有时甚至需要进行适当的模型裁剪和压缩工作。理论上说，模型结构一旦确定是可以计算它的复杂度和计算量，但这有些繁琐。实际中可以借助一些工具帮助预估模型实际的性能，比较模型优化前后的差别，主要使用到的是benchmark_model和summarize_graph。

一、benchmark_model模型推理速度分析

　　在深度学习模型工程落地时，我们追求在成本可控的前提下提高良好的用户体验，因此模型的推理效率和计算代价是重要的衡量指标。通常用FLOPs（floating point operations）描述模型的计算力消耗，它表示浮点运算计算量，用来衡量算法/模型的复杂度。我们是可以从原理上计算出模型需要的FLOPs，参考：https://www.zhihu.com/question/65305385。 除了从理论计算之外，还可以使用tensorflow中的 benchmark_model 工具来进行粗略估计，它可以帮助估算出模型所需的浮点操作数(FLOPS)，然后你就可以使用这些信息来确定你的模型在你的目标设备上运行的可行性。除此之外，比较容易混淆的概念是FLOPS（floating point operations per second），意指每秒浮点运算次数，理解为计算速度，它是衡量硬件性能的指标对于来说TESLA P40可以每秒处理12T个FLOP，普通单核CPU每秒大概处理100亿次的FLOP。当有了计算操作消耗的估计之后，它就对你计划的目标设备上有所帮助，如果模型的计算操作太多，那么就需要优化模型减小FLOP数量。

　　例如下面的例子中，我们通过benchmark_model分析resetNet20-cifar10，大概有82.15M的FLOPs，该机器每秒执行21.89B，因此该模型大概需要4ms的计算时间。在使用benchmark_model之前，需要使用tensorflow源码进行编译。

1
2
3
4
5
6
7
8
9
10
11
12

编译benchmark_model
$ bazel build -c opt tensorflow/tools/benchmark:benchmark_model
$ bazel-bin/tensorflow/tools/benchmark/benchmark_model \
--graph=model_original.pb \
--input_layer="net_input" \
--input_layer_shape="1,32,32,3" \
--input_layer_type="float" \
--output_layer="net_output" \
--show_flops=true \
--show_run_order=false \
--show_time=false \
--num_threads=1

预估FLOPs

1
2

2019-10-11 21:30:31.288678: I tensorflow/tools/benchmark/benchmark_model.cc:636] FLOPs estimate: 82.15M
2019-10-11 21:30:31.288744: I tensorflow/tools/benchmark/benchmark_model.cc:638] FLOPs/second: 21.89B

查看不同类型节点消耗的时间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

========================= Summary by node type ==========================================
 [Node type]	  [count]	  [avg ms]	    [avg %]	    [cdf %]	  [mem KB]	[times called]
          <>	       65	     4.110	    47.269%	    47.269%	     0.000	       65
FusedBatchNorm	       19	     2.028	    23.324%	    70.592%	   240.384	       19
      Conv2D	       22	     2.003	    23.036%	    93.629%	   868.352	       22
         Pad	        2	     0.239	     2.749%	    96.377%	   115.456	        2
        Relu	       19	     0.082	     0.943%	    97.320%	     0.000	       19
       Const	       65	     0.071	     0.817%	    98.137%	     0.000	       65
        NoOp	        1	     0.066	     0.759%	    98.896%	     0.000	        1
         Add	        9	     0.059	     0.679%	    99.574%	     0.000	        9
        Mean	        1	     0.010	     0.115%	    99.689%	     0.256	        1
     Softmax	        1	     0.008	     0.092%	    99.781%	     0.000	        1
_FusedMatMul	        1	     0.007	     0.081%	    99.862%	     0.040	        1
     _Retval	        1	     0.005	     0.058%	    99.919%	     0.000	        1
     Squeeze	        1	     0.005	     0.058%	    99.977%	     0.000	        1
        _Arg	        1	     0.002	     0.023%	   100.000%	     0.000	        1

Timings (microseconds): count=1000 first=7287 curr=7567 min=7198 max=18864 avg=8794.03 std=1249
Memory (bytes): count=1000 curr=1224488(all same)

• node type：进行操作的节点类型。
• start：运算符的启动时间，展示了其在操作顺序中的位置。
• first: 以毫秒为单位。默认情况下 TensorFlow 会执行 20 次运行结果来获得统计数据，这个字段则表示第一次运行基准测试所需的操作时间。
• avg ms：以毫秒为单位。表示整个运行的平均操作时间。
• %：一次运行占总运行时间的百分比。这对理解密集计算区域非常有用。
• cdf%：整个过程中表格中当前运算符及上方全部运算符的累积计算时间。这对理解神经网络不同层之间的性能分布非常重要，有助于查看是否只有少数节点占用大部分时间。
• mem KB：当前层消耗的内存大小。
• Name：节点名称。

二、summarize_graph 模型大小分析

　　服务端深度模型落地时主要关注模型的预测效率，移动端模型落地需要考虑模型的大小。通过summarize_graph工具可以帮助我们简要分析模型的参数量和包含哪些op。设置–print_structure=true可以观察到模型的结构，这也可以通过tensorboard来可视化实现。

1
2
3
4
5
6

tensorflow-1.14.0编译summarize_graph工具
$ bazel build -c opt tensorflow/tools/graph_transforms:summarize_graph
$ bazel-bin/tensorflow/tools/graph_transforms/summarize_graph \
--in_graph=reset20_cifar10_original.pb \
--print_structure=true

1
2
3
4
5

Found 1 possible inputs: (name=net_input, type=float(1), shape=[?,32,32,3]) 
No variables spotted.
Found 1 possible outputs: (name=net_output, op=Softmax) 
Found 272572 (272.57k) const parameters, 0 (0) variable parameters, and 0 control_edges
Op types used: 194 Const, 77 Identity, 22 Conv2D, 19 Relu, 19 FusedBatchNorm, 11 Add, 6 Slice, 5 Pad, 5 Reshape, 4 Sub, 4 MatchingFiles, 3 Switch, 2 Squeeze, 2 ShuffleDataset, 2 ShuffleAndRepeatDataset, 2 StridedSlice, 2 Shape, 2 TensorSliceDataset, 2 RealDiv, 2 PrefetchDataset, 2 ParallelMapDataset, 2 ParallelInterleaveDataset, 2 Transpose, 2 OneHot, 2 BatchDatasetV2, 2 Cast, 2 Maximum, 2 DecodeRaw, 1 GreaterEqual, 1 All, 1 Assert, 1 BiasAdd, 1 Softmax, 1 ExpandDims, 1 FixedLengthRecordDataset, 1 FloorMod, 1 Mul, 1 ReverseV2, 1 Less, 1 MatMul, 1 RandomUniformInt, 1 RandomUniform, 1 Mean, 1 Placeholder, 1 Merge

https://tensorflow.juejin.im/mobile/optimizing.html

这周没什么产出，在TVM社区闲逛。。。

1.TVM编译和安装

• https://wxquare.github.io/2019/10/24/other/TVM-hello/

2.TVM中向量相加

• http://tvm.d2l.ai/chapter_getting_started/vector_add.html

3.TVM编译tensorflow模型

• https://wxquare.github.io/2019/10/24/other/TVM-hello/
• https://docs.tvm.ai/tutorials/frontend/from_tensorflow.html#sphx-glr-tutorials-frontend-from-tensorflow-py

4.TVM怎么做模型量化？(doing)

• https://discuss.tvm.ai/t/int8-quantization-proposal/516
• https://discuss.tvm.ai/t/quantization-story/3920

参考：
【1】 [Dive into Deep Learning Compiler](Dive into Deep Learning Compiler “http://tvm.d2l.ai/“)
【2】 https://tvm.ai/

　　tensorflow针对训练、预测、服务端和移动端等环境支持多种模型格式，这对于初学者来说可能比较疑惑。目前，tf中主要包括.ckpt格式、.pb格式SavedModel和tflite四种格式的模型文件。SavedModel用于tensorflow serving环境中，tflite格式模型文件用在移动端，后续遇到相关格式模型文件会继续补充。这里主要介绍常见的ckpt和pb格式的模型文件，以及它们之间的转换方法。

CheckPoint(*.ckpt)

　　在使用tensorflow训练模型时，我们常常使用tf.train.Saver类保存和还原，使用该类保存和模型格式称为checkpoint格式。Saver类的save函数将图结构和变量值存在指定路径的三个文件中，restore方法从指定路径下恢复模型。当数据量和迭代次数很多时，训练常常需要数天才能完成，为了防止中间出现异常情况，checkpoint方式能帮助保存训练中间结果，避免重头开始训练的尴尬局面。有些地方说ckpt文件不包括图结构不能重建图是不对的，使用saver类可以保存模型中的全部信息。尽管ckpt模型格式对于训练时非常方便，但是对于预测却不是很好，主要有下面这几个缺点：

1. ckpt格式的模型文件依赖于tensorflow，只能在该框架下使用;
2. ckpt模型文件保存了模型的全部信息，但是在使用模型预测时，有些信息可能是不需要的。模型预测时，只需要模型的结构和参数变量的取值，因为预测和训练不同，预测不需要变量初始化、反向传播或者模型保存等辅助节点;
3. ckpt将模型的变量值和计算图分开存储，变量值存在index和data文件中，计算图信息存储在meta文件中,这给模型存储会有一定的不方便。

frozen model(*.pb)

　　Google推荐将模型保存为pb格式。PB文件本身就具有语言独立性，而且能被其它语言和深度学习框架读取和继续训练，所以PB文件是最佳的格式选择。另外相比ckpt格式的文件，pb格式可以去掉与预测无关的节点，单个模型文件也方便部署，因此实践中我们常常使用pb格式的模型文件。那么如何将ckpt格式的模型文件转化为pb的格式文件呢？主要包含下面几个步骤，结合这几个步骤写了个通用的脚本，使用该脚本只需指定ckpt模型路径、pb模型路径和模型的输出节点，多个输出节点时使用逗号隔开。

• 通过传入的ckpt模型的路径得到模型的图和变量数据
• 通过 import_meta_graph 导入模型中的图
• 通过 saver.restore 从模型中恢复图中各个变量的数据
• 通过 graph_util.convert_variables_to_constants 将模型持久化
• 在frozen model的时候可以删除训练节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# -*-coding: utf-8 -*-
import tensorflow as tf
from tensorflow.python.framework import graph_util
import argparse


def freeze_graph(input_checkpoint,output_pb_path,output_nodes_name):
    '''
    :param input_checkpoint:
    :param output_pb_path: PB模型保存路径
    '''
    saver = tf.train.import_meta_graph(input_checkpoint + '.meta', clear_devices=True)
    with tf.Session() as sess:
        saver.restore(sess, input_checkpoint) #恢复图并得到数据
        graph = tf.get_default_graph()
        # 模型持久化，将变量值固定
        output_graph_def = graph_util.convert_variables_to_constants(  
            sess=sess,
            input_graph_def=sess.graph_def,
            output_node_names=output_nodes_name.split(","))# 如果有多个输出节点，以逗号隔开

        print("++++++++++++++%d ops in the freeze graph." % len(output_graph_def.node)) #得到当前图有几个操作节点
        output_graph_def = graph_util.remove_training_nodes(output_graph_def)
        print("++++++++++++++%d ops after remove training nodes." % len(output_graph_def.node)) #得到当前图有几个操作节点

        # serialize and write pb model to Specified path
        with tf.gfile.GFile(output_pb_path, "wb") as f: 
            f.write(output_graph_def.SerializeToString()) 

if __name__ == '__main__':
    parser = argparse.ArgumentParser()
    parser.add_argument('--ckpt_path', type=str, required=True,help='checkpoint file path')
    parser.add_argument('--pb_path', type=str, required=True,help='pb model file path')
    parser.add_argument('--output_nodes_name', type=str, required=True,help='name of output nodes separated by comma')

    args = parser.parse_args()
    freeze_graph(args.ckpt_path,args.pb_path,args.output_nodes_name)

参考：
https://blog.metaflow.fr/tensorflow-how-to-freeze-a-model-and-serve-it-with-a-python-api-d4f3596b3adc

一、概述

　　最近在做模型压缩(model compress)相关工作，之前分别尝试了权重量化(weight quantization)【1】和权重稀疏(weight sparsification)【2】，遗憾的是它们都需要推理引擎和硬件的特定优化才能实现推理加速，而tensorflow在x86架构的CPU下并没有没有针对量化和稀疏矩阵的优化，因此效果一般。吸取前两次的经验，这次尝试了结构化压缩通道剪枝(channel pruning)，它通过删减模型中冗余通道channel，减少的模型前向计算所需的FLOPs。通道剪枝来自论文ICCV2017论文 Channel Pruning for Accelerating Very Deep Neural Networks。 这里会首先简单介绍channel pruning的原理，然后通过PocketFlow压缩工具对ResNet56进行通道剪枝，结果显示channel pruning在精度不怎么损失的基础上，减小接近50%的FLOPs。由于剪枝后模型中增加了许多的conv2d 1x1卷积，实际提升推理效率大概20%。

二、channel pruning 基本原理

1. 什么是通道剪枝

　　虽然论文末尾谈到channel pruning可以应用到模型训练中，但是文章的核心内容还是对训练好的模型进行channel pruning，也就是文章中说的inference time。通道剪枝正如其名字channel pruning核心思想是移除一些冗余的channel简化模型。下图是从论文中截取的通道剪枝的示意图，它表示的网络模型中某一层的channel pruning。B表示输入feature map，C表示输出的feature map；c表示输入B的通道数量，n表示输出C的通道数量；W表示卷积核，卷积核的数量是n，每个卷积核的维度是ckhkw，kh和kw表示卷积核的size。通道剪枝的目的就是要把B中的某些通道剪掉，但是剪掉后的B和W的卷积结果能尽可能和C接近。当删减B中的某些通道时，同时也裁剪了W中与这些通道的对应的卷积核，因此通过通过剪枝能减小卷积的运算量。

2. 通道剪枝数学描述

　　通道剪枝的思想是简单的，难点是怎么选择要裁剪的通道，同时要保证输出feature map误差尽可能得小，这也是文章的主要内容。channel pruning总体分为两个步骤，首先是channel selection，它是采用LASSO regression来做的，通过添加L1范数来约束权重，因为L1范数可以使得权重中大部分值为0，所以能使权重更加稀疏，这样就可以把那些稀疏的channel剪掉；第二步是reconstruction，这一步是基于linear least优化，使输出特征图变化尽可能的小。

　　接下来通过数学表达式描述了通道剪枝。Ｘ($N*c* k_h*k_w$)表示输入feature map，W($n * c * k_h * k_w$)表示卷积核，Y($N*n$)表示输出feature map。$\beta_i$表示通道系数，如果等于0，表示该通道可以被删除。我们期望将输入feature map的channel从c压缩为c’($0<=c’<= c$)，同时要使得构造误差(reconstruction error)尽可能的小。通过下面的优化表达式，就可以选择哪些通道被删除。文章中详细介绍了怎么用算法解决下面的数据问题，这里就不赘述了。另外文章还考虑分支情况下的通道剪枝，例如ResNet和GoogleNet，感兴趣的可以仔细研读该论文【3】。

三、PocketFlow

　　PocketFlow是腾讯AI Lab开源的自动化深度学习模型压缩框架，它集成了腾讯自己研发的和来自其他同行的主流的模型压缩与训练算法，还引入了自研的超参数优化组件，实现了自动托管式模型压缩与加速。PocketFlow能够自动选择模型压缩的超参，极大的方便了算法人员的调参。这里主要使用里面的channel pruning算法（learner）进行通道剪枝。【4】

1.实验准备:

1.cifar10数据集： https://www.cs.toronto.edu/~kriz/cifar-10-python.tar.gz
2.ResNet56预训练模型：https://share.weiyun.com/5610f11d61dfb733db1f2c77a9f34531
3.下载Pocketflow: https://github.com/wxquare/PocketFlow.git

2.准备配置文件path.conf

1
2
3
4
5
6
7

# data files
data_dir_local_cifar10 = ./cifar-10-binary/cifar-10-batches-bin #cifar10数据集解压的位置

# model files 
# 这里模型文件用wget下载不下来，要登录下载，解压到PocketFlow根目录的model目录下面
model_http_url = https://share.weiyun.com/5610f11d61dfb733db1f2c77a9f34531
   

3.在本地运行通道剪枝的learner

1
2
3
4
5
6

$ ./scripts/run_local.sh nets/resnet_at_cifar10_run.py \
--learner=channel \
--cp_uniform_preserve_ratio=0.5 \
--cp_prune_option=uniform \
--resnet_size=56

4. 模型转换

步骤3之后会在models产生ckpt文件，需要通过进行模型转化,最终会生成model_original.pb，model_transformed.pb，同时也会生成移动端对应的tflite文件。

1
2
3
4

$ python tools/conversion/export_chn_pruned_tflite_model.py \
--model_dir=models/pruned_model 
--input_coll=train_images
--output_coll=logits

四、剪枝前后模型分析

　　我们可以通过之前介绍的模型基准测试工具benchmark_model分别测试剪枝前后的模型。可以很清楚看到通道剪枝大大减少了模型前向计算的FLOPs的变化，以及各阶段、算子的耗时和内存消耗情况。可以发现模型下降为原来的1/2，卷积耗时下降接近50%。除此之外通过netron工具可以直观的看到模型通道剪枝前后结构发生的变化，通道剪枝之后的模型中明显增加了许多conv1*1的卷积。这里主要利用1x1卷积先降维，然后升维度，达到减少计算量的目的。1x1卷积还有多种用途，可以参考【5】。

1
2
3
4
5
6
7
8
9
10
11

$ bazel-bin/tensorflow/tools/benchmark/benchmark_model \ 
--graph=model_original.pb \
--input_layer="net_input" \
--input_layer_shape="1,32,32,3" \
--input_layer_type="float" \
--output_layer="net_output" \
--show_flops=true \
--show_run_order=false \
--show_time=true \
--num_threads=1

参考：
[1]. tensorflow模型权重量化(weight quantization)实战
[2]. tensorflow模型权重稀疏(weight sparsification)实战
[3].Channel Pruning for Accelerating Very Deep Neural Networks
[4].PocketFLow
[5].1x1卷积：https://www.zhihu.com/question/56024942

一、概述

　　深度模型通常会有更好的预测精度，但是它面临计算开销过大的问题。模型压缩(model compress)是提高深度模型推理效率的一种解决方案，它期望在不损失精度或者精度损失可控的范围内，加速推理效率，减低内存开销。目前，模型压缩算法主要包括权重量化(quantization)、剪枝(pruning)、低秩分解等。上周尝试了tensorflow中的模型量化，发现量化需要硬件或者推理引擎的对低精度8-bit计算支持，目前tensorflow在x86和gpu环境下还没有很好的支持，因此量化只帮助实现了模型大小下降，没有实现推理的加速。model pruning学习的材料是tensorflow repo中的tensorflow/contrib/model_pruning，实际了解后发现它属于pruning中no-structural pruning，其加速效果依赖具体的硬件实现，加速效果一般，tensorflow 中对稀疏矩阵运算没有特别好的优化（依赖于底层的 SparseBLAS 实现，目前还没有特别好的）。model pruning中还有一种structural pruning 则不改变计算方式，可以直接使用，加速效果相对较好，之后也会继续尝试。

二、tensorflow/contrib/model_pruning原理

　　Michael Zhu and Suyog Gupta, “To prune, or not to prune: exploring the efficacy of pruning for model compression”, 2017 NIPS
　　tensorflow中model_pruning理论来自上面这篇文章。文章中指出目前有些深度学习网络模型是过度设计（over-parameterized）。为了使其在资源受限的环境下高效的进行推理预测，要么减少网络的隐藏单元（hidden unit）同时保持模型密集连接结构，要么采用针对大模型进行模型剪枝（model pruning）。文章中的模型行剪枝是一种非结构化的剪枝（no-structural pruning），它在深度神经网络的各种连接矩阵中引入稀疏性（sparsity），从而减少模型中非零值参数的数量。文章比较了大而稀疏（large-sparse）和较小密集（small-dense）这两种模型，认为前者是优于后者的。除此之外，文章提出了一种新的渐进剪枝技术（gradual pruning technique），它能比较方便的融入到模型训练的过程中，使其调整比较小。

　　tensorflow中的模型剪枝是一种训练时剪枝。对于需要被剪枝的网络模型，对于网络中每个需要被剪枝的层（layer)添加一个二进制掩码变量（binary mask variable ），该变量的大小和形状和改层的权重张量（weight tensor）相同。在训练图中加入一些ops，它负责对该层的权重值（weights）的绝对值进行排序，通过mask将最小的权重值屏蔽为0。在前向传播时该掩模的对应位与选中权重进行相与输出feature map，如果该掩模对应位为0则对应的权重相与后则为0，在反向传播时掩模对应位为0的权重参数则不参与更新。除此之外，文章提出了一种新的自动逐步修剪算法（automated gradual pruning），它实际上是定义了一种稀疏度变化的规则，初始时刻，稀疏度提升较快，而越到后面，稀疏度提升速度会逐渐放缓，这个主要是基于冗余度的考虑。因为初始时有大量冗余的权值，而越到后面保留的权值数量越少，不能再“大刀阔斧”地修剪，而需要更谨慎些，避免“误伤无辜”。其表达式如下，官方文档中列出了一些的剪枝超参数，主要的有下面几个。
$$s_{t}=s_{f}+\left(s_{i}-s_{f}\right)\left(1-\frac{t-t_{0}}{n\Delta t}\right)^{3} $$

• initial_sparsity：初始稀疏值$s_i$
• target_sparsity：目标稀疏值$s_f$
• sparsity_function_begin_step：开始剪枝的step $t_0$
• sparsity_function_end_step: 剪枝停止的step
• pruning_frequency：剪枝的频率$\Delta t$，文章提出在100到1000之间通常比较好
• sparsity_function_exponent: 剪枝函数的指数，表示式中已描述为默认的3，表示由快到慢，为1时表示线性剪枝

三、tensorflow中的model_pruning实践

　　tensorflow中model_pruning的源码位于tensorflow/contrib/model_pruning。

1. 准备tensorflow-1.14.0源码

2. 编译model_pruning

   1	$bazel build -c opt tensorflow/contrib/model_pruning/examples/cifar10:cifar10_train

3. 通过设置一些参数，开始针对cifar10剪枝

   1 2 3 4 5 6 7

   $bazel-out/k8-py2-opt/bin/tensorflow/contrib/model_pruning/examples/cifar10/cifar10_train \ --train_dir=/home/terse/code/programming/tensorflow/model_pruning/train \ --pruning_hparams=name=cifar10_pruning,\ initial_sparsity=0.3,\ target_sparsity=0.9,\ sparsity_function_begin_step=100,\ sparsity_function_end_step=10000

4. 可通过tensorboard查看剪枝过程。可以清楚的看出随着训练步骤的增加，conv1和conv2的sparsity在不断的增长。 在GRAPHS 页面，双击conv节点，可以看到在原有计算图基础上新增了mask和threshold节点用来做 model pruning

   1	$tensorboard --logdir=/home/terse/code/programming/tensorflow/model_pruning/train

5. 模型剪枝之后将剪枝的ops从训练图中删除。

   1 2 3 4 5 6

   $bazel build -c opt tensorflow/contrib/model_pruning:strip_pruning_vars $bazel-out/k8-py2-opt/bin/tensorflow/contrib/model_pruning/strip_pruning_vars \ --checkpoint_dir=/home/terse/code/programming/tensorflow/model_pruning/train \ --output_node_names=softmax_linear/softmax_linear_2 \ --output_dir=/home/terse/code/programming/tensorflow/model_pruning \ --filename=pruning_stripped.pb

四、model_pruning源码简单分析

　　使用tensorflow的model_pruning进行模型剪枝，主要包括两方面的工作，一是apply_mask，二是在训练图中增加剪枝的节点（pruning ops）。这里分别截取了其中的两段代码。

1
2
3
4
5
6
7
8
9
10
11
12

# cifar10_pruning.py  apply_mask to the graph
with tf.variable_scope('conv1') as scope:
  kernel = _variable_with_weight_decay(
      'weights', shape=[5, 5, 3, 64], stddev=5e-2, wd=0.0)

  conv = tf.nn.conv2d(
      images, pruning.apply_mask(kernel, scope), [1, 1, 1, 1], padding='SAME')
  
  biases = _variable_on_cpu('biases', [64], tf.constant_initializer(0.0))
  pre_activation = tf.nn.bias_add(conv, biases)
  conv1 = tf.nn.relu(pre_activation, name=scope.name)
  _activation_summary(conv1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

 #Adding pruning ops to the training graph
with tf.graph.as_default():

  # Create global step variable
  global_step = tf.train.get_or_create_global_step()

  # Parse pruning hyperparameters
  pruning_hparams = pruning.get_pruning_hparams().parse(FLAGS.pruning_hparams)

  # Create a pruning object using the pruning specification
  p = pruning.Pruning(pruning_hparams, global_step=global_step)

  # Add conditional mask update op. Executing this op will update all
  # the masks in the graph if the current global step is in the range
  # [begin_pruning_step, end_pruning_step] as specified by the pruning spec
  mask_update_op = p.conditional_mask_update_op()

  # Add summaries to keep track of the sparsity in different layers during training
  p.add_pruning_summaries()

  with tf.train.MonitoredTrainingSession(...) as mon_sess:
    # Run the usual training op in the tf session
    mon_sess.run(train_op)

    # Update the masks by running the mask_update_op
    mon_sess.run(mask_update_op)

五、总结和未解决的问题

1. tensorflow中的模型剪枝属于no-structral，本质上是使权重稀疏化(weight sparsification),实践中发现它没有使推理加速，据其加速效果依赖具体的硬件实现，加速效果一般，tensorflow 中对稀疏矩阵运算没有特别好的优化（依赖于底层的 SparseBLAS 实现，目前还没有特别好的）
2. 实践中发现不管稀疏度为多少，其剪枝后的模型大小都是相同的，是不是tensorflow对稀疏的模型也是按照非稀疏格式存储的？
3. issue:model_pruning: Why 50% and 90% zeros of the stripped models are the same size? #32805
4. issue: [CNN.Model pruning: no gain in speeding up of inference #22732](CNN.Model pruning: no gain in speeding up of inference #22732)

参考：

1. https://github.com/tensorflow/tensorflow/tree/r2.0/tensorflow/contrib/model_pruning
2. Michael Zhu and Suyog Gupta, “To prune, or not to prune: exploring the efficacy of pruning for model compression”, 2017 NIPS
3. https://zhuanlan.zhihu.com/p/48069799

　　最近在项目中使用到visp库的模板追踪算法(template tracker)，由于接触算法的时间比较短，这里简单记录对算法的理解和认识。模板追踪算法原理比较简单，当代价函数为SSD时，抽象为数学中的非线性最优化问题，这里采用高斯牛顿法求解。高斯牛顿法应该是通用的一种求最优化问题的算法，高斯牛顿法核心是迭代公式，不断迭代更新出新的参数值。visp模板算法效率本身不高，因此在实现的时候提供了一些可调的优化的参数，例如金字塔、采样率、迭代次数、误差等。在项目中，visp模板追踪算法在参考模板没有遮挡的情况下，效果基本满足要求，但是在有遮挡的情况，会存在比较大的问题，因此我们针对遮挡情况，进行了特别的优化。除此之外，我们优化了一个并行版本的模板追踪算法，提升追踪效率。

概述

　　在了解visp模板追踪算法之前，可通过官网上的视频了解追踪算法的能力。它和kcf之类的追踪算法还不太一样，在kcf追踪算法中，我们需要告诉追踪器的追踪目标，通常情况下，我们不要求像素级别的进度的要求。而template tracker参考模板（reference template）计算视频中两帧之间的单应矩阵Homography，通过单应矩阵计算目标区域在当前帧的位置，从而实现追踪的效果。

数学描述

　　visp库中为模板追踪算法提供了SSD、ZNNC和在VISP 3.0.0时引入的MI(mutual information) 代价函数。这里以SSD代价函数描述模板追踪算法。模板追踪算法在数学描述为一个最优化问题，通过SSD代价函数，缩小误差，寻找最优的标记帧到当前帧的单应矩阵。模板追踪算法的数学描述如下：
$$ H_t = \arg \min \limits_{H}\sum_{x∈ROI}((I^*(x)-I_t(w(x,H)))^2 $$

• $I^*$表示标记帧(参考帧），$I_t$表示当前帧
• ROI表示参考区域（参考模板，reference template)
• $H$ 表示参考帧$I^*$到当前帧的的单应矩阵Homography
• $x$ 表示图像中的一个像素点
• $w(x,H)$ 表示标记帧上像素点$x$根据单应矩阵$H$到当前帧的映射关系

　　这里使用经典的高斯牛顿法(Gauss–Newton algorithm)迭代法求解，关于高斯牛顿法这里就不赘述了，最关键的是其迭代公式，感兴趣可以参考下面两篇文章：

• https://en.wikipedia.org/wiki/Gauss%E2%80%93Newton_algorithm
• https://zhuanlan.zhihu.com/p/42383070

　　其迭代公式如下，$J$表示雅克比矩阵，$J^T$表示$J$的转置，$H_t$表示迭代的初始值，$H_k$表示上一次迭代的结果，$r(H_k)$表示上一次迭代的残差residual。

$$ H_{t+1} = H_t + (J^TJ)^{-1}J^Tr(H_k) $$

关键实现步骤

　　了解了模板追踪算法的数学描述和高斯牛顿迭代算法，其基本实现应该是不难的，它本质上是一个迭代算法主要分为以下几步：
step1. 设定初始的$H$矩阵，第一帧为单一矩阵，之后上一帧的结果.
step2. 对于第$k$次迭代计算雅克比$J$, 残差$r(H_k)$，得到$\triangledown H=-(J^TJ)^{-1}J^Tr(H_k)$.
step3. 如果$\triangledown H$ 足够小或者达到最大循环次数就停止迭代
step4. 如果不满足迭代停止条件$H_{k+1}=H_{k} +\triangledown H$
step5. 迭代结束时，$H_{t+1}=H_{k}$

1.计算关键帧中的参考区域中(reference template）中每个像素点的雅克比:

• 计算关于x方向的梯度
• 计算关于y方向的梯度
• 对ROI中的每个点uv计算$J=[d_xu,d_xv,d_x,d_yu,d_yv,d_y,-d_xu^2-d_yuv,-d_xuv-d_yv^2]$

  1 2 3 4 5 6 7 8 9 10 11 12

  # img0 表示标记帧 dx = cv2.Sobel(img0, cv2.CV_64F, 1, 0, ksize) dy = cv2.Sobel(img0, cv2.CV_64F, 0, 1, ksize) img0 = cv2.GaussianBlur(img0, (ksize, ksize), 1) # uv表示标记帧参考区域的每个像素点 juv = [dx[uv] * u, dx[uv] * v, dx[uv], dy[uv] * u, dy[uv] * v, dx[uv], -dx[uv] * u * u - dy[uv] * u * v, -dx[uv] * u * v - dy[uv] * v * v] J = np.array(juv).T # MJ=-(JT*J)^-1 *JT MJ = -np.dot(np.linalg.pinv(np.dot(J.T, J)), J.T)

2.迭代计算当前帧的H的矩阵

• 迭代条件停止的条件，两次迭代误差小于一个指定值，例如$10^{-8}$
• 第一次为单位矩阵，之后为上一帧的追踪结果
• 根据H矩阵将关键帧上上参考区域的点映射到当前帧: uv1 = np.dot(H, uv)
• 计算关键帧上参考区域到当前帧的误差e：E = img0[uv] - img1[uv1]
• 计算$\triangledown H = -(J^TJ)^{-1}J_ne_n$
• 计算新的$H$

  1 2 3 4 5 6 7 8 9

  # for deltaH MJ = -np.dot(np.linalg.pinv(np.dot(J.T, J)*lambdaJTJ), J2.T) #MJ = -np.dot(np.linalg.pinv(np.dot(J2.T, J2)*lambdaJTJ), J2.T) deltaH =alpha* np.dot(MJ, E2) # for newH dh = np.insert(deltaH, 8, np.zeros(1), 0).reshape((3, 3)) dhinv = np.linalg.pinv(np.identity(3) + dh) newH = np.dot(H, dhinv)

实际实现考虑点及其存在的问题

为提高模板追踪算法的效率，visp库在实现模板追踪算法的时候设置了一些可调的参数：

• 对参考模板中的像素点进行采样处理setSampling
• 迭代时设置学习率，setLambda默认为0.001
• 设置最大迭代次数，setIterationMax(200)
• 设置金字塔的层数，tracker.setPyramidal(2, 1)

　　实际使用visp模板追踪算法中，发现当参考模板处有物体遮挡时，效果不好，因此需要做进一步的处理。另外，我们在工程实践时，为了提高追踪的效率，升级了一个并行版本的追踪，能提高数倍的追踪效率。

参考链接：

• https://visp.inria.fr/template-tracking/
• https://visp-doc.inria.fr/doxygen/visp-daily/tutorial-tracking-tt.html
• https://en.wikipedia.org/wiki/Gauss%E2%80%93Newton_algorithm
• https://zhuanlan.zhihu.com/p/42383070

　　
　　最近在尝试深度学习模型加速的工作，查了一些资料，发现模型推理加速的研究还挺多的，主要从四个方面进行，从头开始构建轻量高效的模型，例如mobileNets、squeezenet等；通过量化(quantization)、裁剪(pruning)和压缩(compression)来降低模型的尺寸；通过高效的计算平台加速推理(inference)的效率，例如Nvidia TensorRT、GEMMLOWP、Intel MKL-DNN等以及硬件定制。考虑到自身的能力，遵循从简单到复杂、通用到专用的原则，选择从模型量化(model quantization)入手，之后会陆续尝试其他优化手段。在一番尝试之后，挺遗憾的，因为tensorflow模型量化并没有使模型预测(inference)加速，根据tf成员在issue的回复，tf的模型量化主要针对移动端的优化，目前还没有针对x86和gpu环境的优化。有成功通过模型量化加速推理过程的同学欢迎打脸留言。

一、为什么要模型量化

　　为了尽可能保证深度学习模型的准确度(precision)，在训练和推理时候通常使用float32格式的数据。然而在实际商用中，有些模型由于层数和参数都比较多，推理预测需要很大计算量，导致推理(inference)的效率很低。模型量化(model quantization)是通用的深度学习优化的手段之一，它通过将float32格式的数据转变为int8格式，一方面降低内存和存储的开销，同时在一定的条件下(8-bit低精度运算 low-precision)也能提升预测的效率。目前还不太理解8-bit低精度运算，猜测这是模型量化没有实现推理加速的原因。模型量化适用于绝大数模型和使用场景，对于训练后的量化，不需要重新训练模型，可以很快将其量化为定点模型，而且几乎不会有精度损失，因此模型量化追求更小的模型和更快的推理速度。实验中量化确实时模型下降为原来的1/4，但在推理效率并没有提升，甚至略有下降。

二、什么是量化

2.1 实数量化

　　网络上关于模型量化的内容挺多的，量化本质上是一种仿射图(affine map)，它以表达式(1)将实数值表示映射为量化的uint8，当然也可以等效为表示式(2):

1
2

real_value = A * quantized_value + B             (1) 
real_value = C * (quantized_value + D)           (2) 

　　除此之外，深度学习模型量化中有一个约束条件，0必须准确的表示，不能有误差。因为对于某些神经网络层，实数0精确表示对于优化实现非常有用，例如在具有填充的卷积层或池化层中，长度对输入数组进行零填充(zero-padding)来实现填充是有用的。实数值0对应的量化值称之为零点(zero-point)。实际上，如果0不能完全表示，当我们用0对应的量化值进行填充时，因为这与实际值0不完全对应，会导致结果不准确，引入偏差。因此有：

1
2
3
4
5

　　0=A∗zero_point+B
　　zero_point=−B/A
　　0=C∗(zero_point+D)
　　0=zero_point+D
　　D=−zero_point

　　结合上述条件，可以得出量化的最终表达式为(3)，它能做到0值的准确表示，zero_point是0对应的量化值。表示式(3)中有两个常量，zero_point是量化值，通常是uint8值，scale是一个正实数，通常为float32。
$$real\_value = scale * (quantized\_value - zero\_point)　　(3)$$

2.2 矩阵乘法量化

　　根据表达式(3)，我们可以将实数值(通常为float32)用量化值(通常为uint8)表示，下面将介绍怎么把它应用到矩阵乘法当中。假设有两个实数矩阵$lhs\_real\_matrix, rhs\_real\_matrix$，量化之后就会有对应的$lhs\_scale, rhs\_scale, lhs\_zero\_point, rhs\_zero\_point$，矩阵中的实数值可以用其量化值表示为：

1
2

lhs_real_value[i] = lhs_scale * (lhs_quantized_value[i] - lhs_zero_point)
rhs_real_value[i] = rhs_scale * (rhs_quantized_value[i] - rhs_zero_point)

　　在矩阵乘法中，每个值($result\_real\_value$)都由对应的ｉ个值相乘累加得到，根据表达式(4)和(5)很容易得到表示式(6),它表示$result\_quantized\_value$可由$lhs\_quantized\_value、rhs\_quantized\_value$计算得出。注意这里面有几个问题需要解决，如何减小式(6)中与zero_point减法的开销(overhead)？如何将(lhs_scale * rhs_scale / result_scale)实数运算用整数运算处理？这部分的内容参考gemmlowp的实现。
　　https://github.com/google/gemmlowp/blob/master/doc/quantization.md

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

result_real_value
  = Sum_over_i(lhs_real_value[i] * rhs_real_value[i])
  = Sum_over_i(
        lhs_scale * (lhs_quantized_value[i] - lhs_zero_point) *
        rhs_scale * (rhs_quantized_value[i] - rhs_zero_point)
    )
  = lhs_scale * rhs_scale * Sum_over_i(
        (lhs_quantized_value[i] - lhs_zero_point) *
        (rhs_quantized_value[i] - rhs_zero_point)
    )                    (4)

result_real_value = result_scale * (result_quantized_value - result_zero_point)
result_quantized_value = result_zero_point + result_real_value / result_scale  (5)

result_quantized_value = result_zero_point +
    (lhs_scale * rhs_scale / result_scale) *
        Sum_over_i(
            (lhs_quantized_value[i] - lhs_zero_point) *
            (rhs_quantized_value[i] - rhs_zero_point)
        )          (6)

三、tensorflow模型量化方案

　　**训练后量化(post training Quantization)**。在许多情况下，我们希望在不重新训练模型的前提下，只是通过压缩权重或量化权重和激活输出来缩减模型大小，从而加快预测速度。“训练后量化”就是这种使用简单，而且在有限的数据条件下就可以完成量化的技术。训练后量化操作简单，只需要使用量化工具将训练好的模型执行量化类型，即可实现模型的量化。训练后量化包括“只对权重量化”和“对权重和激活输出都量化”，对于很多网络而言，都可以产生和浮点型很接近的精度。

　　**只对权重量化(weight only quantization)**。一个简单的方法是只将权重的精度从浮点型减低为8bit整型。由于只有权重进行量化，所以无需验证数据集就可以实现。一个简单的命令行工具就可以将权重从浮点型转换为8bit整型。如果只是想为了方便传输和存储而减小模型大小，而不考虑在预测时浮点型计算的性能开销的话，这种量化方法是很有用的。

　　量化权重和激活输出（Quantizing weights and activations）。我们可以通过计算所有将要被量化的数据的量化参数，来将一个浮点型模型量化为一个8bit精度的整型模型。由于激活输出需要量化，这时我们就得需要标定数据了，并且需要计算激活输出的动态范围，一般使用100个小批量数据就足够估算出激活输出的动态范围了。

　　**训练时量化（Quantization Aware Training)**。训练时量化方法相比于训练后量化，能够得到更高的精度。训练时量化方案可以利用Tensorflow的量化库，在训练和预测时在模型图中自动插入模拟量化操作来实现。由于训练时量化相对麻烦，加上权重量化没有实现加速的期望，所以没有尝试训练时量化，根据文档显示，其大概包括以下几个步骤：

1. 可以在预训练好的模型基础上继续训练或者重新训练，建议在保存好的浮点型模型的基础上精调
2. 修改估计器，添加量化运算，利用tf.contrib.quantize中的量化rewriter向模型中添加假的量化运算
3. 训练模型，输出对于权重和激活输出都带有各自量化信息（尺度、零点）的模型
4. 转换模型，利用tf.contrib.lite.toco convert定义的转换器，将带有量化参数的模型被转化成flatbuffer文件，该文件会将权重转换成int整型，同时包含了激活输出用于量化计算的信息
5. 执行模型，转换后的带有整型权重的模型可以利用TFLite interpreter来执行，也可以在CPU上运行模型

四、tensorflow模型权重量化实验

　　一开始尝试模型量化是因为有个复杂的视频分割模型推理效率很低，期望通过模型量化实现加速，在复杂模型上尝试失败之后，我用label_image的例子再次验证，结果显示也没有加速的效果。这里主要试验了训练后量化，尝试了只对权重量化和权重和激活量化，发现后者比前者性能更差，这里描述权重量化的过程。整个过程是比较简单的，tensorflow有两种量化方式，推荐使用第二种，编译命令行工具进行量化。

1. 在tensorflow r1.0的版本中有个量化的脚本可以提供量化的功能：

   1 2 3 4 5 6 7 8

   $wget "https://storage.googleapis.com/download.tensorflow.org/models/inception_v3_2016_08_28_frozen.pb.tar.gz" $tar -xzf tensorflow/examples/label_image/data $ work_dir=/home/terse/code/programming/tensorflow/quantization $ python tensorflow/tools/quantization/quantize_graph.py \ --input=$work_dir/inception_v3_2016_08_28_frozen.pb \ --output=$work_dir/inception_quantized0.pb \ --output_node_names=InceptionV3/Predictions/Reshape_1 \ --mode=weights

2. 在较新版本的tf中，quantize_graph.py量化的脚本已经废弃了需要编译tensorflow的源码生成

   1 2 3 4 5 6 7

   tensorflow-1.14.0编译transform_graph工具 $ bazel build tensorflow/tools/graph_transforms:transform_graph $ bazel-bin/tensorflow/tools/graph_transforms/transform_graph \ --in_graph=$work_dir/inception_v3_2016_08_28_frozen.pb \ --out_graph=$work_dir/inception_quantized1.pb \ --outputs=InceptionV3/Predictions/Reshape_1 \ --transforms='quantize_weights'

3. 使用summarize_graph分析量化前后的模型区别，权重量化、模型减小、增加了一些和量化和反量化的节点。

   1 2 3 4 5

   tensorflow-1.14.0编译transform_graph工具 $ bazel build tensorflow/tools/graph_transforms:summarize_graph $ bazel-bin/tensorflow/tools/graph_transforms/summarize_graph \ --in_graph=$work_dir/inception_quantized1.pb \ --print_structure=true

4. 使用权重量化的模型做推理验证

   1 2 3 4 5

   $ bazel build tensorflow/examples/label_image：label_image $ bazel-bin/tensorflow/examples/label_image/label_image \ --image=$work_dir/grace_hopper.jpg \ --labels=$work_dir/imagenet_slim_labels.txt \ --graph=$work_dir/inception_quantized1.pb

五、 为什么模型量化没有使推理加速

　　关于tensorflow模型量化没有实现模型加速的，我查了一些资料，发现出现类似的问题不在少数。根据tensorflow团队成员的回复，截了几个member的答复，大意是目前量化目前针对移动端的优化，当然也有一些移动端的人说速度下降了。tensorflow未来有可能针对intel x86，gpu量化优化，但不知道什么时候支持。

　　The quantization is aimed at mobile performance, so most of the optimizations are for ARM not x86. We’re hoping to get good quantization on Intel eventually, but we don’t have anyone actively working on it yet.

　　Quantized ops currently only work on the CPU, because most GPUs don’t support eight-bit matrix multiplications natively. I have just seen that the latest TitanX Pascal cards offer eight-bit support though, so I’m hoping we will be able to use that in the future.

参考：

1. https://zhuanlan.zhihu.com/p/33535898
2. https://arxiv.org/abs/1806.08342
3. https://github.com/google/gemmlowp/blob/master/doc/quantization.md
4. https://github.com/tensorflow/tensorflow/issues/2807

　　最近在做kcf算法在移动端优化的相关工作，由于kcf算法计算量太大，而移动端计算性能有限，因此打算将kcf部分耗时操作通过GPU计算进行提升算法的性能。由于接触GPU和OpenCL的时间比较短，原理性的东西理解得也不深刻，本文主要在移动端测试了一些GPU和OpenCL的数据，无法分析内在原因，方便后续移动端算法优化。主要工作如下：

1. 编译了OpenCL的opencv版本sdk，测试了mat到umat相互内存拷贝和cvtcolor函数的性能。
2. 测试了OpenCL核心API的性能
3. 以内存拷贝核函数为例，测试OpenCL work_item数量与效率的关系。
4. 测试OpenCL多commandqueue的性能

一、opencv+OpenCL

1.1 编译opencv+OpenCL的sdk

　　KCF算法总使用了不少的opencv函数，开始想的是编译一个包含OpenCL的opencv的sdk，然后通过调用该sdk从而实现使用GPU加速算法的目的。编译opencv+OpenCL的sdk当时踩了不少坑，多番尝试之后，使用下面的命令是可以成功编译。分别下载opencv-3.4.6、android-ndk-r16b、opencv_contrib-3.4.6,在opencv中建build目录，运行下面命令，命令中使用一些路径相关的参数要根据环境适当修改。

1

cmake -DCMAKE_BUILD_WITH_INSTALL_RPATH=ON -DCMAKE_TOOLCHAIN_FILE="/home/xxx/code/mobile/third_party/ opencv-3.4.6/platforms/android/android.toolchain.cmake" -DANDROID_NDK="/home/xxx/code/mobile/tools/android-ndk-r16b" -DANDROID_SDK="/home/xxx/code/mobile/tools/android_sdk/tools" -DANDROID_NATIVE_API_LEVEL=19 -DANDROID_ABI="arm64-v8a" -DANDROID_ARM_NEON=TRUE -DANDROID_STL=gnustl_static -DCMAKE_BUILD_TYPE=Release -DOPENCV_EXTRA_MODULES_PATH="/home/xxx/code/mobile/third_party/opencv_contrib-3.4.6/modules" -DCMAKE_INSTALL_PREFIX="/home/xxx/code/mobile/third_party/opencv-3.4.6/install_20190623_OpenCL" -DBUILD_opencv_java=ON -DBUILD_ANDROID_PROJECTS=OFF -DBUILD_ANDROID_EXAMPLES=OFF -DBUILD_DOCS=OFF -DBUILD_PERF_TESTS=OFF -DBUILD_TESTS=OFF -DBUILD_FAT_JAVA_LIB=OFF -DWITH_OpenCL=ON -DWITH_CUDA=OFF -DWITH_MATLAB=OFF -DBUILD_opencv_aruco=OFF -DBUILD_opencv_calib3d=OFF -DBUILD_opencv_features2d=OFF .. 

1.2 测试mat到umat的相互转换的性能

　　在编译好opencv sdk之后，首先简单测试了一下sdk是否使用到了GPU资源。测试图片从CPU拷贝到GPU的的性能，opencv提供两组API。UMat::copyTo(OutputArray dst)和Mat::getMat(int access_flags)，实际测试中发现copyto那组性能比get的性能更好些，mat.getUmat函数会报错，还不知道什么原因。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

void testMatCopyToUmat(const char* img, int times) {
    cv::Mat image = cv::imread(img, cv::IMREAD_UNCHANGED);
    cv::Mat out;
    cv::UMat u_img;
    if (u_img.empty()){
        //
    }
    struct timeval start, end;
    struct timeval last_time;
    gettimeofday(&start, NULL);
    last_time = start;
    for (int i = 0; i < times; i++) {
        image.copyTo(u_img);
        //cv::cvtColor(image, out, cv::COLOR_BGR2GRAY);
        gettimeofday(&end, NULL);
        P("mat.copyToUmat:%d,run times:%d, spend:%d us", i,times, (end.tv_sec - last_time.tv_sec) * 1000000 + 
                                       (end.tv_usec - last_time.tv_usec));
        last_time = end;
    }
    gettimeofday(&end, NULL);
    P("mat.copyToUmat: run times:%d, spend:%d ms", times, (end.tv_sec - start.tv_sec) * 1000 + 
                                       (end.tv_usec - start.tv_usec)/1000);
}
void testUMatCopyToMat(const char* img, int times) {
    cv::Mat image = cv::imread(img, cv::IMREAD_UNCHANGED);
    cv::Mat out;
    struct timeval start, end,last_time;
    cv::UMat u_img;
    image.copyTo(u_img);

    gettimeofday(&start, NULL);
    last_time = start;
    for (int i = 0; i < times; i++) {
        u_img.copyTo(out);
        gettimeofday(&end, NULL);
        P("mat.copyToUmat:%d,run times:%d, spend:%d us", i,times, (end.tv_sec - last_time.tv_sec) * 1000000 + 
                                       (end.tv_usec - last_time.tv_usec));
        last_time = end;
    }
    gettimeofday(&end, NULL);
    P("mat.copyToUmat: run times:%d, spend:%d ms", times, (end.tv_sec - start.tv_sec) * 1000 + 
                                       (end.tv_usec - start.tv_usec)/1000);
}

| 手机型号 | CPU型号 | GPU型号 | OpenCL版本 | 首次mat拷贝umat | mat拷贝umat | 首次umat拷贝mat | umat拷贝mat | 图片格式 | 上行带宽 | 下行带宽 |
| —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— |
|三星GALAXY On7|高通 骁龙410 MSM8916| Adreno306| 2| 25.2ms| 0.8ms| 1.5ms| 0.8ms| 720480 159KB| 运行1000次，221M/s| 运行1000次，258M/s|
|三星GALAXY On7|高通 骁龙410 MSM8916| Adreno306| 2| 30.18ms| 2.88ms| 5.5ms| 2.9ms| 19201080 6MB| 运行1000次，2.14G/s| 运行1000次，2.14G/s|
|小米6 MI6| 骁龙 835| 高通 Adreno540| 2|16.602ms| 0.754ms| 2.85ms| 0.795ms| 19201080 6MB| 运行1000次，7.9G/s| 运行1000次，8.06G/s|
|小米6 MI6| 骁龙 835| 高通 Adreno540| 2|17.010ms| 0.332ms| 1ms|0.265ms| 720480 159KB| 运行1000次，632M/S| 运行1000次，898.2M/s|
|小米mix2s| 骁龙 845| 高通 Adreno630| 2|8.7ms| 2.1ms| 6.1ms|0.9ms| 19201080 6MB| 运行1000次，6.6G/S| 运行1000次，6.62G/s|
|小米mix2s| 骁龙 845| 高通 Adreno630| 2|3.3ms| 0.5ms| 2.2ms|0.4ms| 720480 1579KB| 运行1000次，654M/S| 运行1000次，682M/s|

1.3 测试OpenCL cvtcolor函数性能

　　在测试完CPU和GPU内存拷贝的性能之外，之后测试了cvtcolor函数的性能，由于动态加载，OpenCL函数首次加载时特别耗时，大概需要200ms。除此之外，在不同规格的图片上，OpenCL的计算性能大概是cpu的2到3倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

void cpu(const char* img, int times) {
    cv::Mat image; 
    cv::Mat out;
    struct timeval start, end,last;
    for (int i = 0; i < times; i++) {
        image = cv::imread(img, cv::IMREAD_UNCHANGED);
        gettimeofday(&start, NULL);
        cv::cvtColor(image, out, cv::COLOR_BGR2GRAY);
        gettimeofday(&end, NULL);
        P("run times:%d, spend:%d us", i, (end.tv_sec - start.tv_sec) * 1000000 +
                                       (end.tv_usec - start.tv_usec));
    }
}
 
void OpenCL(const char* img, int times) {
    cv::UMat u_img;
    cv::Mat image; 
    cv::UMat out;
    cv::Mat out1;

    std::vector<cv::UMat> v;
    for(int i=0;i<times;i++){
      image = cv::imread(img, cv::IMREAD_UNCHANGED);
      cv::UMat u_img;
      image.copyTo(u_img);
      v.push_back(u_img);
    }
    struct timeval start, end,last;
    for (int i = 0; i < times; i++) {
        gettimeofday(&start, NULL);
        cv::cvtColor(v[i], out, cv::COLOR_BGR2GRAY);
        gettimeofday(&end, NULL);
        P("run times:%d, spend:%d us", i, (end.tv_sec - start.tv_sec) * 1000000 +
                                       (end.tv_usec - start.tv_usec));
    }
}

测试数据：

二、OpenCL核心API性能测试

三、 测试OpenCL work_item数量与效率的关系

　　在OpenCL编程中，work_item和work_group的设置对程序的性能有较大的影响。这里以内存拷贝为例测试OpenCL中work_item数量与效率的关系。通过一张3840x2160的图片拷贝，分别测试了CPU和GPU内存拷贝的性能，测试了在不同work_item条件下GPU内存拷贝性能的性能。从测试结果来看，不同work_item对opencl的性能有较大的影响。测试结果显示，最开始时work_item数量曾倍数关系，之后会在100ms抖动，最好的情况是work_item数量与bmpsize大小相同。测试机器为小米mix2s。

3.1循环拷贝

bmpsize = 3840x2160x3,运行时间13ms

1
2
3
4
5

char* out = new char[bmp_size];
 for(int i=0;i<bmp_size;i++){
   // P("%d",i);
   out[i] = bmp_data[i];
 }

3.2memcpy拷贝

bmpsize = 3840x2160x3,运行时间3ms

1

memcpy(out,bmp_data,bmp_size);

3.3 opencl拷贝

核函数：

1
2
3
4
5
6
7
8
9
10
11
12

__kernel void convert_image(__global const uchar* in, 
            __global uchar* out，const int channel,
            const int width, const int height){
    int thread_count = get_global_size(0);
    int size = width * height * channel;
    int each_thread = size / thread_count;
    int tid = get_global_id(0);
    ; out[tid] = in[tid];
    for(int i=tid*each_thread;i<(tid+1)*each_thread;i++){
        out[i] = in[i];
    }
}

关键代码与work_item的设置：

1
2
3
4
5
6
7

P("thread_count=%d", thread_count);
gettimeofday(&start,NULL);
err = queue.enqueueNDRangeKernel(kernel, cl::NullRange, cl::NDRange(thread_count, 1),
                           cl::NullRange, NULL, &event);
event.wait();
gettimeofday(&end,NULL);
P("opecl wait:%d ms", (end.tv_sec - start.tv_sec) * 1000 + (end.tv_usec - start.tv_usec)/1000);

疑问:当work_item为256或者512是个较好的值，但是不明白为什么2488320和24883200值效果会更好。

四、多commandqueue性能测试

　　在学习和测试OpenCL的过程中，有一个疑问能否使用多个commandqueue来做任务的并行。假设有n个任务，每个任务包含CPU到GPU内存拷贝，核函数执行，和GPU到CPU的内存拷贝。分别测试了使用一个commandqueue和n个commandqueue的性能，测试结果显示多个commandqueue会比使用单个commandqueue性能略好一些，但是差别不大。除此之外，与work_item的设置有关，多个commandqueue可能比单个commandqueue性能性能提升15%。从GPU利用率来说，单个commandqueuGPU曲线呈锯齿形状，而多个commandque呈梯形。部分代码如下：
单个commandqueue：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

void test(const char* cl_file, const char* name, 
      const char* bmp_data, const int bmp_size, 
      const int width, const int height, const int channels,
      const int line_size, const int thread_count,
      const int run_times) 
{
  cl::Platform platforms = cl::Platform::getDefault();
  //P("platform count:%d", platforms.size());
  cl::Context context(CL_DEVICE_TYPE_GPU, NULL);
  std::vector<cl::Device> devices = context.getInfo<CL_CONTEXT_DEVICES>();
  P("Device count:%d", devices.size());
  std::ifstream in(cl_file, std::ios::in);
  std::stringstream buffer;
  buffer << in.rdbuf();
  cl_int err = CL_SUCCESS;
  cl::Program program_ = cl::Program(context, buffer.str());
  err = program_.build(devices);
  if (err != CL_SUCCESS) {
    P("build error");
    return;
  }  
  cl::Kernel kernel(program_, name, &err);
  if (err != CL_SUCCESS) {
    P("build error");
    return;
  }

  cl::CommandQueue queue(context, devices[0], 0, &err);
  if (err != CL_SUCCESS) {
    P("CommandQueue create error");
    return;
  }

  struct timeval start, end;
  cl::Event event;
  err = CL_SUCCESS;
  for(int i = 0;i<run_times;i++){
  {
   
    //see: https://github.khronos.org/OpenCL-CLHPP/classcl_1_1_buffer.html
    cl::Buffer in_buf(context, CL_MEM_WRITE_ONLY, bmp_size);
    cl::Buffer out_buf(context, CL_MEM_READ_ONLY, bmp_size);
    err = queue.enqueueWriteBuffer(in_buf, true, 0, bmp_size, bmp_data, NULL, &event);

    kernel.setArg(0, in_buf);
    kernel.setArg(1, out_buf);
    kernel.setArg(2, line_size);
    kernel.setArg(3, channels);
    kernel.setArg(4, width);
    kernel.setArg(5, height);

    P("thread_count=%d", thread_count);
    gettimeofday(&start,NULL);
    err = queue.enqueueNDRangeKernel(kernel, cl::NullRange, cl::NDRange(thread_count, 1),
                               cl::NullRange, NULL, &event);
    event.wait();
    gettimeofday(&end,NULL);
    P("opecl wait:%d ms", (end.tv_sec - start.tv_sec) * 1000 + 
                                         (end.tv_usec - start.tv_usec)/1000);

  
    char* h_out_buf = new char[bmp_size];
    err = queue.enqueueReadBuffer(out_buf, true, 0, bmp_size, h_out_buf, NULL, &event);
    if(0!=memcmp(h_out_buf, bmp_data, bmp_size)){
      P("data not same");
      return;
    }else{
      P("data same");
    }
  }
}
}

多个commandqueue：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

void test_mutil_command_queue(const char* cl_file, const char* name, 
      const char* bmp_data, int bmp_size, 
      const int width, const int height, const int channels,
      const int line_size, const int thread_count,
      const int run_times) 
{
  cl::Platform platforms = cl::Platform::getDefault();
  //P("platform count:%d", platforms.size());
  cl::Context context(CL_DEVICE_TYPE_GPU, NULL);
  std::vector<cl::Device> devices = context.getInfo<CL_CONTEXT_DEVICES>();
  P("Device count:%d", devices.size());
  // cl::CommandQueue queue(context, devices[0], 0);
  //
  std::ifstream in(cl_file, std::ios::in);
  std::stringstream buffer;
  buffer << in.rdbuf();
  //
  //cl::Program::Sources source{
  //    std::make_pair(buffer.str().c_str(), buffer.str().size()) };
  cl_int err = CL_SUCCESS;
  cl::Program program_ = cl::Program(context, buffer.str());
  err = program_.build(devices);
  if (err != CL_SUCCESS) {
    P("build error %d",err);
    return;
  }  

  struct timeval start, end,end2;
  cl::Event event;
  err = CL_SUCCESS;
  gettimeofday(&start, NULL);
  std::vector<cl::CommandQueue> vQueue;
  std::vector<cl::Event> vEvents;
  std::vector<cl::Buffer> vInBuffers;
  std::vector<cl::Buffer> vOutBuffers;
  std::vector<char*> vHostOutBuf;
  std::vector<cl::Kernel> vKernels;
  std::vector<char*> vBmpdatas;

  for(int i=0;i<run_times;i++){
    cl::Event event;
    cl::CommandQueue queue(context, devices[0], 0, &err);
      if (err != CL_SUCCESS) {
      P("CommandQueue create error");
      return;
    }
    vQueue.push_back(queue);
    vEvents.push_back(event);
    cl::Buffer in_buf(context, CL_MEM_WRITE_ONLY, bmp_size);
    cl::Buffer out_buf(context, CL_MEM_READ_ONLY, bmp_size);
    vInBuffers.push_back(in_buf);
    vOutBuffers.push_back(out_buf);
    char* h_out_buf = new char[bmp_size];
    vHostOutBuf.push_back(h_out_buf);

    cl::Kernel kernel(program_, name, &err);
    if (err != CL_SUCCESS) {
      P("build error");
      return;
    }
    kernel.setArg(0, vInBuffers[i]);
    kernel.setArg(1, vOutBuffers[i]);
    kernel.setArg(2, line_size);
    kernel.setArg(3, channels);
    kernel.setArg(4, width);
    kernel.setArg(5, height);
    vKernels.push_back(kernel);

  }
  gettimeofday(&end, NULL);
  P("opecl create queue: spend:%d ms", (end.tv_sec - start.tv_sec) * 1000 + 
                                       (end.tv_usec - start.tv_usec)/1000);

  for(int i=0;i<run_times;i++){
    err = vQueue[i].enqueueWriteBuffer(vInBuffers[i], false, 0, bmp_size, bmp_data, NULL, &vEvents[i]);
  }
  for(int i=0;i<run_times;i++){
    vEvents[i].wait();
  }

  for(int i=0;i<run_times;i++){
    err = vQueue[i].enqueueNDRangeKernel(vKernels[i], cl::NullRange, cl::NDRange(thread_count, 1),
                                 cl::NullRange, NULL, &vEvents[i]);
  }

  for (int i = 0; i < run_times; ++i){ 
    vEvents[i].wait();
  }

  for(int i=0;i<run_times;i++){
    err = vQueue[i].enqueueReadBuffer(vOutBuffers[i], false, 0, bmp_size, vHostOutBuf[i], NULL, &vEvents[i]);
  }
  for(int i=0;i<run_times;i++){
    vEvents[i].wait();
  }
  
  for(int i=0;i<run_times;i++){
    if (0!=memcmp(vHostOutBuf[i], bmp_data, bmp_size)){
      P("data not same");
    }else{
      P("data same");
    }
  }
}