大家好，我是不会写代码的纯序员——Chunel，很高兴又在这里跟大家见面了，今天我们来聊聊CGraph 中最新引入的 并发度计算 功能，在介绍之前，我愿称之为色丶图至今为止，实现思路最复杂且被用到的概率最低的功能，哈哈。
在开始之前，我们照例，提供源码链接，跪求大家来个star。
| 问题描述 |
色丶图项目从开始组件团队的时候，就一直很乐意做一些共建和赋能的事情。前阵子，有幸被选中成为开源推理引擎 SimpleInfer 项目的底层调度组件，跟作者也有一些沟通。
聊到功能的时候，基本上所有的需求都是可以支持的。但是，有一个问题，当 SimpleInfer 组建好一个 pipeline之后，如何分配一个合理的执行线程数。
顿时，我就敏感起来了。前阵子做性能分析的时候，我们发现不同的线程数设置，对执行的效率影响是非常巨大的。CGraph虽然可以设置独立线程池，也支持不同的pipeline设置共享线程池，但其实解决的是是否能设置的问题，下一步要解决的，是怎么设置好的问题了。
我们先来回顾一下这个问题哈：
我们看上面的这三个dag图哈，左上方的dag最大的情况下，需要2thread来执行，因为有依赖关系，即便在最极限的情况下，只有 B和C 两个算子（蓝色）可以并行。
右上方的那个呢，理论上C/D/E/F 四个算子有可能能并行，也就是说，最大的并发度是4。同理啊，下方的那个全连接网络，也是理论上最多只有 D/E/F/G 这4个算子，可以同时进行。
如果设定的线程数超过了这个最大值，不仅不可能带来任何性能提升，而且会造成系统资源浪费，这个就叫做 dag 的最大并发度了。既然有这个理论背景了，下一步就是通过计算，把这个数字求出来了。
| 问题分析 |
刚开始看到这个问题的时候，我感觉是比较简单的，直接做个bfs就好。但后来看看，并没有这么简单。比如上方右上角的那个图吧，如果做 bfs的话，应该是 【A,BCD,EF,G】，max值是3（即为 BCD），这个明显和实际不符。
再想想，能否给 dag转成 对应的二维矩阵，然后通过矩阵论的方式来解决。看了一下，貌似也不行。因为dag中，连接的信息是不全的。再拿右上角的图来举例子，我们是无法一次性看出来 A和E，C和E之间是否有联系的——A和E中间隔着一个B，C和E是真的没有关系。
我们再想回溯（或者着色），遇到稍微深一点的图，都会导致复杂度的极度上升。貌似实现起来也很难哦，没啥好的思路。
无奈中，我们来请教 chatgpt吧。我们发现，原以为无敌的gpt的回答结果，其实就是最基本的层序遍历，这个只能在最简单的场景中，正确结果。稍微复杂一点，计算的结果值就是错的了。国内厂商提供的大模型，更是一言难尽，刚开始提供的代码，根本无法通过编译。整个问答的过程，像极了面试写题的时候，不会却非要写点啥的纯序员本员了，哈哈。
最后，我们去谷歌和 leetcode 上搜索，都找不到对应的解决方案——连靠谱一点的分析也没有。所以，可以说，接下来的内容，应该是大家在网上能看到的第一篇靠谱的方法了，啊哈哈哈哈。
| 问题解法 |
本着搞不定就放弃的原则，这篇文章，就已经结束了。
哦，不不不，意识到这是一个比较有意义的基础问题，还是要尝试去解决一下的。于是，我们请教了身边的很多朋友。经过长时间的讨论、尝试和分析，终于来自杭电计算机院的 倪博士，提出了理论可行，且可以实现（复杂度较低）的算法方案。
下面，我们就以下图（左上角）中的DAG图，来拆解一下计算过程。
- 求出全路径
这一步比较简单，做个dfs就可以了。可以看出，上图中一共有三条完整路径，分别是 A-B-D-F，A-B-E-F，A-C-F ，如图中右上方所示
- 根据全路径，得出所有可达点对
看一下上图的蓝色字体部分，表示的是每一条路径中的点对（point pair）的集合。需要说明的是，这个点集是无向并去重的。比如，path1 和 path2中，都包含 AB 的点集，直接去重即可。
这一步的作用，得出所有的前后依赖关系，特别是可以一次性看出 D和A之间，是有依赖关系的——前面聊过，这在原先的dag中，是不容易直接看出这个关系的，因为中间有B。
- 根据上面的点集信息，得到对应的二维矩阵
看上面的点集信息，如果是 有AB，则 AB和BA的位置，均设置为1（这个是无权图）；又如没有BC，则对应的位置都写0。还有就是，对角线上都写0。
- 求出上图（二维矩阵）的最大独立集
然后，求出上图中的最大独立集合。集合中元素的个数，就是我们需要求的最大并发度。且集合中的元素，就是无法并发的节点。
| 求图的最大独立集 |
原先的问题解决了，但又引入了一个新的问题——如何求 图的最大独立集。我搜索了一下，并没有什么很常用的算法，来完成这个功能。但是，我们可以将这个问题，转移成另外一个等价的问题：
原图的最大独立集 = 原图补图的最大团
补图的意思，就是将原图中的0和1值，进行倒转。最大团是图（数据结构）中的一个基本概念，是结点数最多的极大团。如果不了解这一块的内容，可以看一下这篇文章：团、极大团、最大团 ，或者 最大团介绍视频(B站)
而解最大团的方法，通常有最大团回溯算法，和Bron-Kerbosch算法，有兴趣的朋友可以自己去搜索一下。By the way，chatgpt 是可以直接写出来以上两种算法的，亲测可用。
| 本章小结 |
就这样，这个困扰了我们近半个月的难题，就被解决了。具体的实现代码，在CGraph 的 GMaxParaOptimizer.h 中，有兴趣的朋友可以去看看源码，里面包含了非常详细的注释。
通过这个问题的解决过程，我也有了一些自己的感悟。大家经常会讨论刷leetcode有啥用 这样的问题。我想，如果只是处理一些常规的流程性质的coding，是基本没啥用的。
但是，如果遇到一些需要分析思路的问题的话，刷没刷过的差距就显而易见了——这也在一定程度上，区分出了高手和普通程序员。上面的几个流程，每个小流程都是leetcode中的题目，没刷过题（或打过竞赛）的朋友，其实是很难有这些思路的。当然了，我相信，如果只是纯刷也不行，我们还应该有很好的意识，将其中学到的知识活学活用，合理的用到对应的领域——不只面试哈，哈哈哈哈。
这里要大赞倪童鞋，倪童鞋在学校从事AI基础算法研究工作，水平、经验和阅历明显超过身边其他人一大截。我们一群工作了很多年的人（比如坤叔、乐哥）在群里讨论了两个星期也没解决的问题，倪童鞋仅用一晚上，就提出了可行的思路和实现方案。不得不承认，人跟人之间，差距还是很大的。当然了，我这里不是说坤叔和乐哥不行啊，我没有这个意思哦，请大家不要误会哦。
还有一点遗憾，就是当前算法，在面对包含子图，甚至是子图套子图的dag的时候，是无法完成计算的。我想了一下，也并不是简单的加入分治的思路就可以解决的。这个问题，我们会继续关注，也欢迎有兴趣的朋友加入我们，一起讨论交流，多多指教。
最近工作中，极大的依赖chatgpt的功能，这次终于找到了AI暂时无法解决的问题。同时，这也应该是全网第一篇，完整介绍dag并发度计算方法的博客——至少在中文领域是这样的。很高兴有机会跟大家分享这些内容。
今天还是母亲节，祝福天下母亲节日快乐。虽然不在身边，但我还是决定出去吃点好吃的，为老妈庆祝一下节日，哈哈。
[2023.05.14 by Chunel]
推荐阅读
- 纯序员给你介绍图化框架的简单实现——执行逻辑
- 纯序员给你介绍图化框架的简单实现——循环逻辑
- 纯序员给你介绍图化框架的简单实现——参数传递
- 纯序员给你介绍图化框架的简单实现——条件判断
- 纯序员给你介绍图化框架的简单实现——面向切面
- 纯序员给你介绍图化框架的简单实现——函数注入
- 纯序员给你介绍图化框架的简单实现——消息机制
- 纯序员给你介绍图化框架的简单实现——事件触发
- 纯序员给你介绍图化框架的简单实现——线程池优化（一）
- 纯序员给你介绍图化框架的简单实现——线程池优化（二）
- 纯序员给你介绍图化框架的简单实现——线程池优化（三）
- 纯序员给你介绍图化框架的简单实现——线程池优化（四）
- 纯序员给你介绍图化框架的简单实现——线程池优化（五）
- 纯序员给你介绍图化框架的简单实现——线程池优化（六）
- 纯序员给你介绍图化框架的简单实现——距离计算
- CGraph 主打歌——《听码农的话》
- 聊聊我写CGraph的这一年
- 从零开始主导一款收录于awesome-cpp的项目，是一种怎样的体验?
- 炸裂！CGraph性能全面超越taskflow之后，作者却说他更想…
- 【B站视频】CGraph 入门篇
- 【B站视频】CGraph 功能篇
个人信息
微信: ChunelFeng
邮箱: chunel@foxmail.com
个人网站：www.chunel.cn
github地址: https://github.com/ChunelFeng
