基于双向搜索的指令候选集生成算法

Instruction Candidate Set Generation Algorithm Based on Bidirectional Search

摘要

指令候选集生成是扩展指令集处理器设计中必不可缺的一部分，但该过程也是一种计算密集型任务。为提升候选集生成效率，提出一种双向搜索后融合的算法。首先，基于数据流图的邻接表提出一种高效的连通子图搜索树建立算法；其次，在搜索树遍历过程中整体采用双向并行搜索的思路来提升搜索效率，针对由不同树节点构成的子图，应用多约束裁剪优化技术来提升搜索速度。实验结果表明，所提算法能够适应多种约束条件，且性能为已有算法的1~2倍。

Abstract

Instruction candidate set generation is an essential component of extended instruction set processor design, but it is also recognized as a computationally intensive task. To improve the efficiency of candidate set generation, a bidirectional search algorithm with post-fusion is proposed. First, an efficient search tree construction algorithm for connected subgraphs is developed based on the adjacency list of the data flow graph. Second, during the traversal of the search tree, a bidirectional parallel search approach is systematically implemented to enhance search efficiency. Additionally, a multi-constraint pruning optimization technique is applied to subgraphs composed of different tree nodes to further accelerate the process. Experimental results demonstrate that the proposed algorithm not only adapts to multiple constraints but also has one to two the performance of existing algorithms.

Graphical abstract

关键词

候选集生成 / 扩展指令集 / 子图搜索 / 数据流图 / 指令设计

Key words

candidate set generation / extended instruction set / subgraph search / data flow graph / instruction design

0 引言

近年来基于扩展指令集的处理器得到广泛的研究与关注^[1]，特别是在嵌入式系统领域和专用计算领域。其设计思想是在指令集加入面向特定领域的粗粒度指令^[2]，并在中央处理器（Central Processing Unit, CPU）基础上加入专用指令执行部件^[3]补偿细粒度指令的缺陷。由于兼顾灵活性和性能，因此其成为体系结构创新中非常重要的研究分支^[4]。

在基于扩展指令集处理器的设计过程中，其中一个关键问题是指令的设计，其必须满足特定的指令约束，常见的约束包括最大输入/输出约束、凸约束等^[5-7]。指令候选集生成的常见方法包含手动生成和自动生成。手动生成候选集耗时且容易出错。自动生成算法将指令特点作为约束条件对算法数据流图（Data Flow Graph, DFG）进行子图搜索，将所有适合作为指令的子图挖掘出。文献[8]通过巧妙构建搜索二叉树并设计修剪规则，给出了子图完全搜索算法，包含所有可以作为指令的连通图和非连通图，但该搜索算法是指数搜索算法，当数据流图较大时算法性能很差。文献[9]采用引导函数将DFG中非关键边删除，将大图转换为若干小图降低了搜索复杂度，将候选集生成与子图选择过程结合了起来。文献[10]的并行识别算法实际上是利用顶点包含约束将搜索过程划分若干不相交的子任务，但由于每个子任务的计算负载不同，因此又提出了多深度图划分的并行识别算法^[11]。

为了提升候选集的生成效率，提出了一种基于双向搜索的指令候选集生成算法。首先提出了一种连通子图的搜索算法，在此基础上利用指令的约束条件，提出了一种双向优化、多裁剪策略的指令候选集生成算法。最终的实验结果表明，在对数据流图搜索过程中，所提算法能够适应多种约束条件，且性能为已有算法的1~2倍。

1 定义与性质

对于有向无环图G\left(V,E\right)，V为顶点集，E为边集。图G^{\text{'}}\left(V^{\text{'}},E^{\text{'}}\right)为图G的导出子图^[12]，即V^{\text{'}}\subseteq V、E^{\text{'}}\subseteq E，且\forall u,v\in V^{\text{'}}，若\left(u,v\right)\in E,则必有\left(u,v\right)\in E^{\text{'}}。

1.1 相关定义

定义1 凸子图。\forall u,v\in V^{\text{'}}，如果不存在t\in

\{V\setminus V^{\text{'}}\}，并且u、t、v之间存在路径，则称G^{\text{'}}是G的一个凸子图^[13]。

定义2 前驱结点与后继结点。\forall u,v\in V,若\left(u,v\right)\in E则称u是v的前驱结点，v是u的后继结点。v的所有前驱结点称为v的前驱结点集，记为P\left(v\right)，u的所有后继结点称为u的后继结点集，记为S\left(u\right)。对于G的子图G^{\text{'}}和结点v\in V，u\in P\left(v\right)，如果u\in V^{\text{'}},则称u为v相对子图G^{\text{'}}的内部前驱结点，记为u\in I\left(G^{\text{'}},v\right);如果u\notin V^{\text{'}},则称u为v相对子图G^{\text{'}}的外部前驱结点，记为u\in T\left(G^{\text{'}},v\right);同理定义u相对子图G^{\text{'}}的内部后继结点I\left(G^{\text{'}},u\right)和外部后继结点T\left(G^{\text{'}},u\right)。

定义3 指令约束。受系统体系架构（最大输入端口{\mathit{I}}_{\mathrm{m}\mathrm{a}\mathrm{x}}，最大输出端口{\mathit{O}}_{\mathrm{m}\mathrm{a}\mathrm{x}}，禁忌结点集F）与指令本身特性的约束，符合指令要求的子图G^{\text{'}}必须满足以下条件，其中\mathrm{I}\mathrm{p}和\mathrm{O}\mathrm{p}分别表示计算子图输入端口与输出端口：

1） \mathrm{I}\mathrm{p}\left(G^{\text{'}}\right)\le {\mathit{I}}_{\mathrm{m}\mathrm{a}\mathrm{x}},\mathrm{O}\mathrm{p}\left(G^{\text{'}}\right)\le {\mathit{O}}_{\mathrm{m}\mathrm{a}\mathrm{x}}；

2） \forall u\in V^{\text{'}}，u\notin F；

3） G^{\text{'}}为G的凸连通子图。

1.2 相关性质

对于有向无环图G\left(V,E\right),对图结点进行拓扑排序：如果\left(u,v\right)\in E，那么。

定理1 如果G^{\text{'}}\left(V^{\text{'}},E^{\text{'}}\right)不符合输入约束或者凸约束，对于结点s\in \{V\setminus V^{\text{'}}\}，\forall a\in V^{\text{'}}，\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\left(s\right)>\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\left(a\right)，那么由\{V^{\text{'}}\bigcup s\}在图G上的导出子图依然违背输入约束或者凸约束，即G^{\text{'}}扩展结点s后仍不满足约束。

证明 对于输入约束，\mathrm{I}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}\left(s\right)\ge \mathrm{0};如果P\left(s\right)

=I\left(G^{\text{'}},s\right),那么s的所有输入均来自与G^{\text{'}},不存在从集合\{\mathrm{V}\setminus \{V^{\text{'}}\bigcup s\}\}到s的边，那么\mathrm{I}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}\left(V^{\text{'}}\bigcup s\right)=\mathrm{I}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}\left(V^{\text{'}}\right)>{\mathit{I}}_{\mathrm{m}\mathrm{a}\mathrm{x}};如果I\left(G^{\text{'}},s\right)⊊P\left(s\right),即T\left(G^{\text{'}},s\right)\ne \mathrm{\varnothing }，那么\mathrm{I}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}\left(V^{\text{'}}\bigcup s\right)>\mathrm{I}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}\left(V^{\text{'}}\right)>{\mathit{I}}_{\mathrm{m}\mathrm{a}\mathrm{x}},因此G^{\text{'}}扩展s结点后的子图依然不符合输入约束。

对于凸约束，G^{\text{'}}不满足凸约束，说明\exists u,v\in V^{\text{'}}，t\in \{V\setminus V^{\text{'}}\}，使得u和t间存在路径，t和v间存在路径，并且,假设添加结点s之后，扩展后的图不违背凸约束，那么只有令结点s等于结点t时，所以。由条件可知，\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\left(s\right)>\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\left(v\right),因此G^{\text{'}}扩展s扩展后的子图依然违背凸约束。

定理2 如果G^{\text{'}}\left(V^{\text{'}},E^{\text{'}}\right)不符合输出约束或者凸约束，那么对于s\in \{V\setminus V^{\text{'}}\}，\forall a\in V^{\text{'}}，，那么由\{V^{\text{'}}\bigcup s\}在图G上的导出子图依然违背输出约束或凸约束，即G^{\text{'}}扩展结点s后仍不满足约束。

证明 证明过程同定理1。

定理3 给定凸子图G^{\text{'}}，以及结点s\in \{V\setminus V^{\text{'}}\}，\forall a\in V^{\text{'}}, \mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\left(s\right)>\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\left(a\right),记S^{\text{'}}是由\{V^{\text{'}}\bigcup s\}在图G上的的导出子图，那么当\forall u\in V^{\text{'}}\mathrm{、}v\in T\left(G^{\text{'}},s\right)，且u和v之间不存在路径时S^{\text{'}}为凸子图。

证明 假设S^{\text{'}}非凸，则\forall u,m\in \{V^{\text{'}}\bigcup s\}且，那么必然存在t\in \{F\setminus V^{\text{'}}\}，使得u和t、t和m之间存在路径。由于s为S^{\text{'}}拓扑序中最大的结点，因此u\in V^{\text{'}}。如果m\ne s，则u\mathrm{、}m\in V^{\text{'}},则G^{\text{'}}不是凸子图，与已知条件矛盾，因此m=s。那么必然存在t\in \{F\setminus V^{\text{'}}\}，使得u和t存在路径，且\left(t,s\right)\in D，即t\in T\left(G^{\text{'}},s\right)，与已知条件矛盾，因此S^{\text{'}}不可能为非凸。

定理4 给定凸子图G^{\text{'}},以及结点s\in \{V\setminus V^{\text{'}}\}，且\forall a\in V^{\text{'}}，，S^{\text{'}}是由\{V^{\text{'}}\bigcup s\}在图G上的导出子图，那么当任取\forall u\in V^{\text{'}},v\in T\left(G^{\text{'}},s\right)，且u和v之间不存在路径时S^{\text{'}}为凸子图。

证明 证明过程同定理3。

2 双向搜索后融合算法

本节主要对所提算法进行详细介绍，核心思想是双向并行搜索，以应用算法DFG为输入，寻找所有符合约束条件的算核。如果DFG输入/输出数量比较多，通过手动添加虚拟节点的方式汇聚所有输入/输出就可以使整个DFG变为单输入单输出结构。此时由于DFG的输入和输出都是确定且唯一的，那么在搜索的过程中就可以从输入和输出两个方向进行搜索，最后对两部分的结果进行融合。

以上为本文所提算法的核心优化思路，但在实际实现过程中，如果要得到符合约束的连通子图，那首先需要解决两个问题：如何搜索连通子图；如何进行约束检查。基于这两个问题，提出了4个算法。

2.1 搜索树建立

为了遍历数据流图中的连通子图，构建了一棵连通子图搜索树，具体过程如算法1所示。

算法1 连通子图搜索树建立算法

输入:图的邻接表

输出:搜索树

1. 添加虚拟输入结点

2. 并进行拓扑排序

3. 添加flag_node为根结点，0号节点为其子节点

4. 添加flag_node为0号结点的子结点

5. 获取当前树的叶子结点，放入队列

6. while!（叶结点全为flag_node且扩展列表为空）

7. while 队列不空

8. leaf_to_extend=queue.get（）#取出结点

9. if leaf_to_extend=flag_node:

10. 上溯leaf_to_extend祖先结点中第1个flag_node，记为flag_ancestor

11. 获取flag_node与flag_ancestor间所有结点,记为base_nodes

12. 根据邻接表获取base_nodes中的所有结点的大于max（base_nodes）的邻接点，记为Childrens

13. 获取leaf_to_extend在树中的所有编号大于leaf_to_extend的兄弟结点，记为Siblings

14. for child in Childrens:

15. 在树中为child建立结点，指定父结点为leaf_to_extend

16. if child in Siblings: 删除Siblings的child

17. else:#结点为普通结点

18. if tree.contains（leaf_to_extend）

19. 添加flag_node，指定父结点为leaf_to_extend

20. 获取leaf_to_extend在树中的所有编号大于leaf_to_extned的兄弟节，记为Siblings

21. for sibling in Siblings:

22. 在树中为sibling建立结点，指定父结点为leaf_to_extend

23. 获取当前树中的所有叶结点,并放入队列存储

探索树构建如图1所示。

如果输入图为单输入图，那么步骤1可跳过，如果图为多输入，需要通过人为添加结点的方式汇聚所有输入结点，使整个图变为单输入结构。拓扑排序即为对所有结点进行编号，如果\left(u,v\right)\in E，那么，如图1（a）所示。flag_node结点并无实际意义，只是辅助树的建立和遍历，如图1（c）中x结点。算法1第3~5行是固定的，为0号结点在树中建立结点，并作为整棵树的树根。算法1第7~23行的整体思路是，扩展当前树的所有叶子结点，如果叶子结点为flag_node,则扩展flag_ancestor与flag_node间结点的邻接结点；如果叶子结点为普通结点，则扩展flag_node结点以及该结点的兄弟结点，直到所有结点均为flag_node并且每个flag_node与其flag_ancestor之间结点的邻接结点均为空。从整体上看，在两个flag_node之间扩展结点的方式类似于子集生成算法中的增量构造法。算法1第16和18行的目的是防止由于图结点间关系复杂导致树中存在重复的分支。对图1（b）所示的数据流图来说，1号结点和2号结点既有父子关系又有兄弟关系，那么在树中就会形成重复分支，比如在图1（d）中蓝色线圈和橙色线圈其实表示的是同一个图（由结点0、1、2组成的图）。因此在为树建立结点时，如果该结点也在待扩展结点的兄弟结点中出现，那么从兄弟结点中删除该结点，此时的搜索树如图1（e）所示。

从结点i出发向后扩展可以得到的子图是包含在以x-i-x为祖先结点的子树中，这种结构叫做扩展点。对DFG中的每个结点，在搜索树中都能找到对应的扩展点。如图1（c）中红色线圈表示从结点1出发向后扩展可得到的包含所有子图的树，紫色线圈表示从结点2出发向后扩展可得到的包含所有子图的树。同理可以完成down树的构建。

2.2 约束检查与树的遍历

上文的树结构实际上为子图的搜索定义了一个遍历顺序，但是子图也必须同时满足定义3的约束条件。在树的建立过程中，采用了临接点和拓扑序的准则来增加结点，实际上就是在得到连通子图的前提下尽可能利用约束条件来减小搜索空间。由于up树是基于结点序增大的方式构建的，那么基于定理1，在搜索过程中，如果子图不满足输入约束或者凸约束，则该分支可直接放弃搜索；同理对于down树，如果子图不满足输出约束或者凸约束，那么该分支可直接放弃搜索。因此采用深度优先的方式来遍历树。约束检查过程如算法2所示。

算法2 约束检查算法

输入：子图，图的邻接矩阵，{\mathit{I}}_{\mathrm{m}\mathrm{a}\mathrm{x}}，{\mathit{O}}_{\mathrm{m}\mathrm{a}\mathrm{x}}

输出：输入检查结果、输出检查结果、凸性检查结果

function input_check:#输入检查

1. 统计子图所有结点的输入总数In_edge

2. 统计子图结点间内部互联边的数量Inner_edge

3. 计算子图的输入In=In_dege-Inner_edge

4. IfIn <= I_max: 输入满足约束Return True

5. If In> I_max: 输入违例Return False

function Output_check:#输出检查

1 #与input_check同理，将输入统计改为输出

function Convex_check:#凸性检查

1. 从S的结点中获取具有最大编号的结点Max_label

2. 获取Max_lebel的Ext_Pred_set（S, Max_label）

3. For node_src in S except the Max_label

4. For node_dstin Ext_Pred_set（S, Max_label）

5. If has_path（node_src, node_dst）= True：

6. 凸性约束违例，Return False

7. Else：凸性约束满足，Return True

上面算法是以up树为例。对于down树，输入和输出检查是一样的，在凸性检查中，需要获取的是Min_label，以及\mathrm{E}\mathrm{x}\mathrm{t}\_\mathrm{S}\mathrm{u}\mathrm{c}\mathrm{c}\_\mathrm{s}\mathrm{e}\mathrm{t}\left(G^{\text{'}},\mathrm{M}\mathrm{i}\mathrm{n}\_\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\right)。Convex_check中的has_path函数是解决图中的可达性问题，可以通过深度优先遍历、广度优先遍历、可达矩阵等方法实现。从树中得到由单结点扩展出的子图的遍历过程如算法3所示。

算法3 遍历算法

输入:树结构，图结构，初始遍历点，{\mathit{I}}_{\mathrm{m}\mathrm{a}\mathrm{x}}, {\mathit{O}}_{\mathrm{m}\mathrm{a}\mathrm{x}}

输出:满足约束的子图列表Subgraph_list

1. While 1#结束条件在内部，直接return结束

2. 从当前搜索分支中获取待检查子图

3. if 去除虚拟结点的子图是连通的：

4. 去掉去除虚拟结点后进行约束检查

5. if 3个约束条件都满足

6. Subgraph_list.append（）

7. 获取当前搜索分支在树中的Children

8. if Children=none:#当前分支搜索结束

9. 获取搜索分支在树中的右兄弟结点Sibling

10. 如果Sibling为空或所有元素均为禁忌结点，则继续向上回溯查找

11. ifSibling=none:#所有合适分支搜索结束

12. 停止搜索并return结束

13. else:#存在合适的搜索分支

14. 将Sibling中编号值最小且不是禁忌结点的元素加入基图

15. else:#Children is not empty

16. 将min（Children）加入基图

17. If min（Children）是禁忌结点:

18. 重复9~14#结束当前分支，搜索兄弟分支

19. elif input_check=0 or convex_check=0:

20. 重复9~14#结束当前分支，搜索兄弟分支

21. elif output_check=0:

22. 存储当前子图#用于后面融合操作

23. repeat line7 to line18#跳过该子图

24. else: repeat line7 to line18

该算法的思路是根据约束检查结果设置相应搜索策略。在第3和24行中，对图的连通性进行判断，是因为虚拟结点可能是割点。在第4~18行中，如果所有约束都满足条件，那么将子图加入结果列表，采用深度优先的思想继续向后搜索。第17~18行中，当基图扩展的结点在禁忌列表中时则不再向下扩展，而是直接结束该分支，并转而去搜索兄弟分支，因为禁忌结点无法通过后续结点修复。第19~20行中，对于up树来说，如果输入约束或者凸约束不满足，由定义1知，直接停止搜索当前分支。第21~23行中，对于up树如果输出约束不满足，处理策略同第7~18行，只能跳过当前子图，但不能结束当前分支，因为输出违例可能通过后续结点得到修复。上面以up树为例介绍了搜索过程，down树与之类似。

2.3 双向搜索算法

在上文中给出了一种满足约束条件的连通子图搜索算法，在本节将对整个图的搜索过程做进一步的优化，其核心思想可以概括为“双向优化、中间相遇”，如图2（a）所示。

在对数据流图按拓扑序编号之后0n，选择一个结点m,利用结点0到m构建up树，利用结点（m+1）到n构建down树，分别遍历up树和down树，找到两棵树中满足指令约束的子图。由于up树中只包含结点0到m，为了子图搜索的完整性，对up树中的结果还需要扩展（m+1）到n中的结点，因此需要连接up树结果与down树的结果，简称为融合。记up树中不满足输入约束或者凸约束的子图集合Q1，其他子图为Qt1，down树中不满足输出约束或者凸约束的子图集合为Q2，其他子图集合为Qt2，可以证明融合过程只需要考虑Qt1与Qt2中的元素，不需要考虑Q1或者Q2。具体过程如算法4所示。

算法4 双向搜索算法

输入:邻接矩阵、禁忌列表，{\mathit{I}}_{\mathrm{m}\mathrm{a}\mathrm{x}}，{\mathit{O}}_{\mathrm{m}\mathrm{a}\mathrm{x}}

输出:符合条件的子图集合

1. 产生分割点m，建立up和down树，获取扩展点

2. 遍历up树得到Q1和Qt1，down树得到Q2和Qt2

3. 将Qt2中每个元素按结点数量做升序排序

4. 计算Qt1中每个元素在（m+1）到n范围内且不在禁忌列表中的后继结点down_adjac

5. prune_list=[[] for i in range（len（Qt1））]

6. for i in range（len（Qt1））

7. for subgraph_Qt2 in Qt2:

8. if \mathrm{d}\mathrm{o}\mathrm{w}\mathrm{n}\_\mathrm{a}\mathrm{d}\mathrm{j}\mathrm{a}\mathrm{c}\left[i\right]\bigcap \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{h}\_Qt\mathrm{2}\ne \mathrm{n}\mathrm{o}\mathrm{n}\mathrm{e}:

9. if prune_list[i]的所有元素均不是subgraph_Qt2的子集

10. 合并Qt1[i]与subgraph_Qt2得到com_subgraph

11. 对com_subgraph做约束检查

12. if 所有约束都满足：加入子图列表

13. elif if input违例或凸性违例

14. prune_list[i].append（subgraph_Qt2）

15. 获取包含0号结点且具有多个输出分支的子图或者包含max（lebel）结点且具有多输入分支的子图

16. 将子图作为新的虚拟结点，替换子图在原图的位置

17. 对修改后的图重复上述算法

整个算法的思路是首先得到up树与down树中所有满足条件的子图集合，再判断up树中子图的后继结点与down树中子图是否有公共结点，如果有则合并之后仍为连通图，对该连通图接着进行约束检查。第3行将Qt2中元素按结点数量做升序排列之后，第7行会首先遍历结点数较少的子图，如果结点数量较少的子图不满足输入或者凸约束，那么包含该子图的更大子图也不满足约束，因此第5行定义了修剪列表来记录能产生违例的子图。

第15~17行用来解决多扩展点子图无法修复的问题。在图2（b）中，记红色线圈子图为subgraph1，紫色线圈子图为subgraph2。这两个图均为连通子图。但是up树只能搜索到subgraph1却搜索不到subgraph2，down树与之相反。但是在up树搜索到subgraph1之后，将subgraph1视作单个虚拟结点，形成如图2（c）中的DFG，并重复建树与搜索过程。在连通性检查过程中，算法会检测到图2（c）中的DFG在去掉虚拟结点后依然连通，那么就可以对subgraph2做进一步的约束检查。同理，对于down树也可以对subgraph1做约束检查，如图2（d）所示。

3 实验

下面通过实验对所提算法进行测试和评估，实验环境为Win11 Core（TM） i7-12700H，主频为2.30 GHz，算法采用Python编码，在Pycharm上用Python3.10完成编译。实验包含两部分，分别进行了随即图以及特定领域算法DFG的测试。

3.1 随机图测试

本节利用随机图为输入，通过改变图数据的结点数和边数，查看在不同约束条件下满足约束的合法子图的数量以及树遍历和约束检查的时间消耗。在图3~图6中，图例4-2、6-3、8-4、ALL等标记，表示的是在不同约束下的输入和输出端口数量。

在图3和图4中，令图的结点数量\left|V\right|=\mathrm{20}，观察边的数量\left|E\right|对子图数量与算法运行时间的影响。在图5和图6中，令\left|E\right|/\left|V\right|=\mathrm{1.5}，通过改变结点数量观察\left|V\right|对算法的影响。为方便描述，将|E|/|V|记为边点比。

在图4和图6中，约束宽松的曲线是高于约束严苛的曲线。主要因为约束条件越宽松，符合要求的子图数量越多，利用约束条件能够裁剪的搜索空间越小，因此需要的搜索时间就越多。在图3中，随着\left|E\right|/\left|V\right|比值的增大，符合约束的子图数量反而减少，主要是因为边数量的增多导致不符合凸性约束的子图数量增多；这同时也造成了凸性判断难度增大，因此搜索时间也大幅增加。在图5和图6中，当控制\left|E\right|/\left|V\right|为一个合理值时，顶点数量的增多导致搜索空间的增大，因此消耗的时间也增多，但符合约束条件的子图数量也增多。所以，图的结构、规模等属性都会对算法性能和结果产生较大影响。

3.2 算法DFG测试

在本节中选取Mibench和Mediabench数据集中几个有代表性的程序，包括通信、多媒体等，并利用LLVM编译器生成中间结果IR，从中提取出程序的DFG。TD^[14]和BS^[15]是当前对DFG的凸子图进行枚举的算法，将{\mathit{I}}_{\mathrm{m}\mathrm{a}\mathrm{x}}和{\mathit{O}}_{\mathrm{m}\mathrm{a}\mathrm{x}}设置为无穷大，在同样条件下对比程序的执行效率。表1给出了采用的程序的基本信息。图7给出了本文所提算法相比TD和BS产生的加速比。

从图7可以发现，本文所提算法性能要比BS和TD性能更好。对BS算法的性能提升高达6倍，对TD算法的性能提升也可以达到1.5~2.5倍之间。究其原因，主要源自两个方面。首先并行搜索带来了时间节省，其次图分割以及多约束裁剪方法减低了搜索复杂度。

4 结束语

针对扩展指令集处理器设计中的指令候选集生成效率问题，提出了一种基于双向并行搜索与多约束裁剪优化的创新算法。通过构建双向搜索树结构，结合拓扑排序特性实现动态剪枝策略，在保证子图连通性和凸约束的前提下，将算法性能提升至传统方法的1~2倍，实验证明其能有效适应输入/输出端口限制、禁忌节点等多重约束。该成果为嵌入式系统及专用计算领域的指令自动化设计提供了高效解决方案，下一步可通过动态约束扩展和机器学习优化进一步拓展应用场景，推动处理器架构设计与领域专用计算的协同创新。

参考文献

[1] 窦勇、王嘉伦、苏华友， 从计算机体系结构发展历程看数据流计算思想［J］.中国科学：信息科学，2020，50（11）：1697-1713.

[2] PAULINO N， FERREIRA J， CARDOSO J. Improving performance and energy consumption in embedded systems via binary acceleration： a survey［J］. ACM Computing Surveys，2020，53（1）：1-36.

[3] 肖成龙， 王珊珊， 王心霖， 可扩展处理器的自定义指令自动识别综述［J］. 电子学报， 2020， 48（8）： 1655-1664.

[4] HUMBLET T S， MCCASKEY A， LYAKH D I， et al. Quantum computers for high-performance computing［J］. IEEE Micro， 2021，41（5）：15-23.

[5] WANG S， XIAO C. Reinforcement learning for selecting custom instructions under area constraint［J］. IEEE Transactions on Artifical Intelligence， 2023，5（4）：1882-1884.

[6] ALKIM E， EVKAN H， LAHR N， et al. ISA extensions for finite field arithmetic accelerating kyber and NewHope on RISC-V［J］. IACR Transactions on Cryptographic Hardware and Embedded Systems， 2020（3）：219-242.

[7] 吕雅帅，沈立，黄立波 面向嵌入式应用的指令集自动扩展［J］. 电子学报，2008（5）：985-988.

[8] POZZI L， ATASU K， IENEN P. Exact and approximate algorithms for the extension of embedded processor instruction sets［J］. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2006，25（7）：1209-1229.

[9] CLARK N， ZHONG H， MAHLKE S. Automated custom instruction generation for domain-specific processor acceleration［J］. IEEE Transactions on Computers， 2005，54（10）：1258-1270.

[10] XIAO C， WANG S， LIU W， et al. Parallel custom instruction identification for extensible processors［J］. Journal of Syatems Architecture， 2017，76：149-159.

[11] WANG S， XIAO C， LIU W. Parallel enumeration of custom instructions based on multidepth graph partitioning［J］. IEEE Embedded Systems Letters， 2018，11（1）：1-4.

[12] 朱维军，张春艳，周清雷，有向图k顶点导出子图的DNA粘贴算法［J］.计算机科学，2019，46（1）：309-313.

[13] GIAQUINTA E， MISHARA A， POZZI L. Maximum convex subgraphs under I/O constraint for automatic identification of custom instructions［J］. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2015，34（3）：483-494.

[14] XIAO C， WANG S， LIU W， et al. An optimal algorithm for enumerating connected convex subgraphs in acyclic digraphs［J］. IEEE Transactions on Circuits and Systems II：Express Briefs， 2020，68（1）：261-265.

[15] WANG S， XIAO C， LIU W. A faster algorithm for enumerating connected convex subgraphs in acyclic digraphs［J］. IEEE Embedded Systems Letters， 2017，9（1）：9-12.

基金资助

国家重点研发计划(2022YFB4500901)