降边增效：CGraph中冗余边剪裁思路总结

大家好，我是不会写代码的纯序员——Chunel。之前，我们跟大家分享过，基于图论如何计算CGraph中dag的最大并行度(最大并行度文章链接)，该思路也有幸被腾讯的童鞋采纳并运用在项目中。希望我们的内容，能够帮助到更多做类似事情的朋友，也随时欢迎大家交流指教。

今天，我们继续依靠图论，来对CGraph中的dag进行裁边的优化，以达到更优图的目的。按照惯例，首先上源码：

https://github.com/ChunelFeng/CGraph

问题描述

我们先来描述一下问题哈。我们知道，色图已经在各行各业被广泛落地使用，也有很多人针对现有的逻辑进行二次开发。也正是因为被使用的多了，很多问题被提了出来。

比如说在机器视觉，特别是检测场景，就会遇到上图这种缺口、形变、脏污的组合拳。当作者组合好之后，使用 perf 逻辑打印出来耗时之后，我们会发现，这张图有点奇怪，但又说不上哪里有问题。

让我们聚焦到红框内部，来细看一下吧。框里有4个节点和5条边。这其中，实际上有很多冗余连接。比如吧，A和C之间，有两条路线（AC和AB->BC），很容易看出。这个AC的连接（对应边2）是多余的，因为无论这条边连或者不连，C都需要等B执行完后，才开始执行，而B又要等A结束才开始。同样的情况，还出现在AD和 AB->BD 的情况，和图中其他几乎各个位置。

我们知道，在CGraph中，是没有显示的边的概念的，所有的node都是通过依赖关系来决定执行顺序。在这种依赖关系明显变多的情况下，虽然不会导致执行异常，但会增加每次执行时解图的工作量。虽然这点工作量（1us之内），针对动则10+ms 的算子逻辑来说，可以忽略不计，但站在一个合格的中间件开发工程师这一层来看，明显是多余了。

解决思路

明确问题之后，就考虑如何实现这个功能。刚开始的时候，也能想到，通过链路，来标记依赖关系。但想来想去，总感觉离彻底解决这个问题有一步的距离。

不过，有了之前计算最大并行度的经验，我们就知道这样的问题该请教谁了[/狗头] 。对，我们又请教了当时还是在读研究生，现在已经是互联网大厂算法工程师的倪童鞋，得到了一条非常有用的公式：

解释一下，节点V的所有父节点（例 Ui 和Uj）中，如果其中任意一个是另外一个的祖先（包含父节点），则删除该祖先节点（Uj）和当前节点(V)的连接。这样说如果还觉得有点抽象的话，我们来通过一个具体的例子，来说明这个问题。

看上面这张图哈。左上角是一个DAG，包含了三条联通路径，见左下角。依据路径信息，我们可以生成右边的联通矩阵。这里针对矩阵稍作解释：

横向表示单个节点，纵向表示该节点是否是横向的后继。用图中蓝色背景的那个1来说吧，这个说明B节点是A节点的后继。反过来就说A是B的前驱——可以是父亲，也可以是祖先。
矩阵表示一个有向图，中轴线上的值，都是0，表示自己不是自己的祖先。
如果M[x][y] = 1，则 M[y][x] 一定是0

得到这个矩阵之后，我们就开始具体的裁边操作了:

选取第一个节点V
遍历当前节点的所有的一级父节点（Ua…Uz），如果这些节点中，如果Uj 是Ui 的祖先，则删除Uj和 V之间的连接
依次遍历所有的节点，重复完成上述操作

再具体一点：
当遍历到B点的时候，发现B只有一个直系father，也就是A。不满足条件，继续遍历。
当遍历到D点的时候，发现A和B都是直系father，然后就看A和B之间的关系，发现A也是B 的祖先，则删除A和D之间的连边。

结果分析

好了，讲到这里，应该已经讲清楚了裁冗余边的所有流程，接下来的就是把逻辑实现一下就好了。

在最新版本的CGraph中，已经有具体的实现了。全局搜索一下 GTrimOptimizer，就可以看到对应的代码逻辑。如果不想看实现代码的话，直接调用 GPipeline 的 trim() 接口即可。顺便说一下，函数的返回值是被裁掉的边的条数。当 pipeline中有group，group中多余的边，也会被裁掉。

void demo_trim() {
    GPipelinePtr pipeline = GPipelineFactory::create();
    GElementPtr a, b, c, d = nullptr;

    pipeline->registerGElement<MyNode1>(&a, {}, "nodeA");
    pipeline->registerGElement<MyNode1>(&b, {a}, "nodeB");
    pipeline->registerGElement<MyNode1>(&c, {a}, "nodeC");
    pipeline->registerGElement<MyNode1>(&d, {a, b}, "nodeD");    // A和D之间有连边

    pipeline->trim();
    pipeline->dump();    // 从dump的结果就可以看出来，A和D之间的边，被裁掉了
    GPipelineFactory::remove(pipeline);
}

多余的边是裁掉了，我们再来简单分析一下效果哈。分两种情况来看：

第一种情况，上述例子中的情况，裁掉了一条边，怎么说呢，虽然整个图的确是好看了一些，但是对整体执行耗时，基本没有任何影响。原因上文也说了，相比于node的执行逻辑，这一点图计算耗时，只能说是九牛一毛，基本没有任何影响。

第二种情况，大家应该知道，CGraph针对纯串行、纯并行逻辑都有一些执行优化。如果裁边之后，正巧变成了这种结构，整体调度性能会有意想不到的提升。

具体trim前后的执行耗时对比，我就不测了。在实际落地的过程中，还是更建议结合 perf 去优化具体node的耗时，或者根据耗时去更合理的编排组合dag逻辑。前阵子工作中，就遇到了一个真实的问题。我针对之前做过的一个组件做了各种优化，但看整体进程的性能，并没有什么提升。后来分析了一下才发现，我处理的这一块耗时仅占整体的1%左右，瓶颈根本就不在这里。

整了好长时间，经验和技术是攒到了，n+1也快到手了。哈哈，开玩笑哈，我建议大家工作中，要时刻关注kpi，但不要只面向kpi编程哈，个人的思考创新、经验积累，和对团队的潜在的提升的可能性也同样重要。我相信，很多爆炸性的突破，看着像是瞬间出现的，实际上都是这些内容积累到一定程度，自然然而发生的。

写在最后

看到这里，相信你应该应该已经了解，CGraph在针对DAG结构中，剪裁冗余边的思路和实现方式。是不是没有用的知识，又增加了一点点。我自己构造了很多场景，实测剪裁逻辑都是正确的。我们水平有限，如果您发现上述思路在某种情况下有逻辑漏洞，或者是验证过程中，发现个别反例，导致裁边之后，整体逻辑不对了，请随时联系我们并指正。

又让我想到了这几年，行业里如火如荼的裁员潮，基本上所有公司都在通过裁员的方式降本增效，仿佛裁掉20%的人，就能及时止损20%一样。但实际上，有没有一种可能，人头数并不是公司陷入困境的主要原因？这背后，行业的波动起伏，公司的管理、战略方向和创新力，对人才的聚集力，是更重要的原因呢？而在这个过程中，一个人、一条边能有多大的影响呢？

如果您对我们的项目感兴趣，非常欢迎通过下面的方式，和我们取得联系，以便于随时技术交流。也欢迎给我们的项目star、fork and pr哈，感谢您看到这里，小纯给你比心了。

mmqrcode1602771241876

                                                             [2024.09.08 by Chunel]

个人信息

微信: ChunelFeng
邮箱: chunel@foxmail.com
个人网站：www.chunel.cn
github地址: https://github.com/ChunelFeng

问题描述

解决思路

结果分析

写在最后

推荐阅读

个人信息