很荣幸能够参与到这次的鲲鹏众智项目中，在这半年的项目实践过程中受益匪浅。我们团队的项目主要研究图算法的代数转换求解的理论体系构建和优化，给出等价性推导过程和正确性证明，并基于 suiteSparse 完成算法求解原型 demo 开发，性能达到指定目标，主要完成理论体系优化和算法性能优化。

对我个人来言，能参与到这个项目不仅是一次学习的机会，也是一次挑战。因为这是我第一次参与这么大型的项目开发，独自负责某项算法的优化与开发，在此之前，更多是跟着组长的指导进行团队工作，所以这次实现过程中，我又紧张又兴奋。在项目实现过程中，遇到不少技术难点，也遇到过不知道如何解决的问题，通过多次阅读文献、理解文献，以及翻阅参考书、上网查阅相关资料等方法，或是和老师、学长学姐们讨论，最终也一一解决了。在这个过程中，不仅让我收获了成就感与满足感，也丰富了我的知识储备，坚定了我遇到问题要勇于解决的信心。

在这里向大家分享环路检测算法一些关键技术。

传统单机的环路检测算法有Tirenan算法。该算法的思路是所有顶点依次执行深度优先搜索，对于顶点u执行深度优先搜索的过程，等价于寻找以u作为起点的一条简单路径。在搜索的过程中，每次选择当前路径上最后一个顶点v的邻居 w 进行扩展。为了避免重复搜索，每次选择的邻居顶点 w 要求满足以下三个条件：

（1）没有在当前路径中出现过

（2）w 的 id 大于 u 的 id

（3）visit[w]=false

选择邻居顶点 w 后标记 visit[w]=true。当不能找到下一个扩展邻居时，这一次的深度优先搜索过程结束。此时判断当前路径的最后一个顶点与路径起点是否相邻，如果相邻则组成了一个环，将这个结果加入到结果集中。

我们整个设计思路围绕着用合适的代数化语言来建模描述搜索和剪枝过程。但是在设计代数化建模方法的过程中遇到了困难，最初的设想是基于一篇完全模仿深度优先搜索过程的论文进行搜索设计，再进行剪枝。

但这样的建模方法额外带来了很多层循环，导致对其进行并行化计算带来的收益并不能超过循环造成的额外时间开支，反而要比基线方法更慢些。而且这样的建模环境之下节点扩展的信息不易保存，对于剪枝方法的引入造成了影响。

所以我们试图找到一种更简单的过程中操作更少的代数化建模方法。

我们按照基线算法Tiernan的数学过程完全自己实现了矩阵的存取和运算操作，考虑到鲲鹏CPU的核心数众多，在环路检测算法中，对每个出发节点的环路检测计算相互间不耦合，因此可利用Scala多线程机制，用多个线程分别计算每个顶点的环路信息，从而充分释放鲲鹏算力优势。

为了进一步优化性能，将整体方法移植到GraphBLAS框架中，在公开数据集上进行测试与最优开源基线算法对比性能，实验结果证明在GraphBLAS框架下性能提升且结果正确。

在项目执行过程中，团队中的我们同心协力，不断合作，每周定期开展会议，讲述自己在项目中遇到的问题和困难，相互交流进行改进和纠正，大大提高了我们的效率。

最后，十分感谢华为鲲鹏众智计划给了我们这次学习和实践的机会，感谢老师、学长学姐们的指导，也感谢对接的每一个华为专家，让我学习到了很多知识，并应用到实践中。

北京理工大学-计算机学院-数据科学与知识工程实验室-曹梦婕

指导老师：张志威老师