一种高效的凸连通子图枚举算法

摘要：

在可配置处理器的定制指令设计过程中,需要提取热点代码数据流图的凸连通子图.为实现子图的快速枚举,对有向无环图内的凸子图特性进行了研究.根据凸子图特性和节点邻接关系,提出了一种AS(adjacent search) 算法用于枚举有向无环图内满足I/O端口约束的凸连通子图.实验数据显示,AS算法比现有算法具有更高的效率,加速比可达10～1000X.当现有算法因数据流图规模较大而失效时,应用AS算法仍能成功完成子图枚举.

关键词：凸连通子图、有向无环图、数据流图、枚举、可配置处理器、定制指令

所属期刊栏目：21

分类号：TP301(计算技术、计算机技术)

资助基金：the National High-Tech Research and Development Plan of China under Grant No.2007AA01Z2b3 国家高技术研究发展计划863;the National Basic Research Program of China under Grant No.2007CB310608 国家重点基础研究发展计划973

在线出版日期：2011-03-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：3106-3115