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

• 作者: 林孝康 葛宁 薄拾
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 凸连通子图 有向无环图 数据流图 枚举 可配置处理器 定制指令
• 年，卷（期）: 2010,（12）
• 页码范围: 3106-3115
• 分类号: TP301
• 字数: 6421字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2010.03676

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	林孝康	清华大学电子工程系	128	1192	17.0	30.0
2	葛宁	清华大学电子工程系	80	431	10.0	18.0
3	薄拾	清华大学电子工程系	5	9	1.0	2.0