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

Instruction Candidate Set Generation Algorithm Based on Bidirectional Search

作　　者：范旺 刘勤让[1] 赵博[1] 高彦钊 祁晓峰 FAN Wang;LIU Qinrang;ZHAO Bo;GAO Yanzhao;QI Xiaofeng(Information Engineering University,Zhengzhou 450001,China)

机构地区：[1]信息工程大学,河南郑州450000

出　　处：《信息工程大学学报》2025年第2期182-188,共7页Journal of Information Engineering University

基　　金：国家重点研发计划(2022YFB4500901)。

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

关 键 词：候选集生成 扩展指令集 子图搜索 数据流图 指令设计 

分 类 号：TP332.1[自动化与计算机技术—计算机系统结构]