融合策略求解
经过融合条件判断后,若发现两个节点可以融合,可能会产生多种融合结果的组合,例如下图中的融合策略1和融合策略2,当存在多种融合策略时,需要确定哪种策略为最优。

计算整图的融合策略最优解是较为困难的,主要原因有以下两点:
- 算法复杂度可能较高,一种可行的思路是动态规划求解,保证在nlog(n)有难度。
- 性能估算模型不准确,没有上板实际测试前,难以准确确定融合后的真实性能。
基于上述原因,追求严格的全局最优解必然涉及大量的整图融合尝试和上板实测,从而导致时间复杂度显著增加。因此,现阶段采用score+贪心的简单融合策略求解算法:将图上可融合节点两两配对,逐个进行CanFuse判断,在可融合的情况下,再根据打分进行排序(以决定融合的先后顺序),最后依次进行融合处理。第一轮融合后的节点将再次重复该处理,尝试进行多轮融合,最多融合10轮。融合打分规则:
- 节省的内存大小计算(利用符号实现大小比较,越大优先级越高)。
- 节点间的临近性计算(使用topo序ID的差值,越小优先级越高)。
排序优先级:
首先比较内存大小,当内存大小相同时,再比较临近性;若临近性也相同,则按topo序从小到大排列,并进行去重处理,最终得到可融合的节点对,后续将按此顺序依次进行融合处理。
如图1所示,A、B、C、D组成AB、BC、CD融合节点对,排序后确定融合顺序,假设融合顺序CD优先,AB次之,融合后变成CD、AB;当处理BC融合时B已经变成AB,C已经变成CD,最后变成AB+CD的融合处理。
如图2所示,如果排序是AB优先,BC次之融合过程会发生变化,AB先融合,在处理BC融合时由于B已经变成了AB会进行AB+C的融合,融合成ABC,同理CD融合会进行ABC+D的融合。
两个场景的最终融合结果相同,都是ABCD。然而,假设A和D不能融合,实际结果会有所不同:图1的结果是AB、CD,而图2的结果是ABC、D。由此可见,融合的顺序变化会导致融合过程和结果的不同。当前算法也存在局限性:当前的贪心算法仅考虑局部最优,可能会导致全局并非最优。例如,当A和D不能融合时,如果优先融合CD,可能会导致ABC无法融合,从全局角度来看,可能并非是最优策略。

