###
DOI:
Journal of Software:2010.21(12):3106-3115

一种高效的凸连通子图枚举算法
薄拾,葛宁,林孝康
()
Efficient Algorithm for Convex Connected Subgraph Enumeration
BO Shi,GE Ning,LIN Xiao-Kang
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3761   Download 3363
Received:October 24, 2008    Revised:July 07, 2009
> 中文摘要: 在可配置处理器的定制指令设计过程中,需要提取热点代码数据流图的凸连通子图.为实现子图的快速枚举,对有向无环图内的凸子图特性进行了研究.根据凸子图特性和节点邻接关系,提出了一种AS(adjacent search) 算法用于枚举有向无环图内满足I/O端口约束的凸连通子图.实验数据显示,AS算法比现有算法具有更高的效率,加速比可达10~1000X.当现有算法因数据流图规模较大而失效时,应用AS算法仍能成功完成子图枚举.
Abstract:Enumerating convex connected subgraphs from data flow graphs of application hot-spots is required when designing instructions for a configurable processor. To achieve fast enumeration, properties of convex subgraphs of directed acyclic graph are studied. Based on the properties of convex subgraphs and adjacency of vertices, AS (adjacent search), a novel algorithm for enumerating convex connected subgraphs satisfying I/O constraints is presented. Results of experiments show that AS algorithm is more efficient than the existing algorithm, and rate is 10~1000X as fast. While the existing algorithm fails on large scale data-flow graphs, the AS algorithm is still able to accomplish enumeration successfully.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by 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)) Supported by 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))
Foundation items:
Author NameAffiliation
BO Shi  
GE Ning  
LIN Xiao-Kang  
Reference text:

薄拾,葛宁,林孝康.一种高效的凸连通子图枚举算法.软件学报,2010,21(12):3106-3115

BO Shi,GE Ning,LIN Xiao-Kang.Efficient Algorithm for Convex Connected Subgraph Enumeration.Journal of Software,2010,21(12):3106-3115