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

摘要

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

关键词

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