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

Efficient Algorithm for Convex Connected Subgraph Enumeration

作　　者：薄拾[1] 葛宁[1] 林孝康[1] 

机构地区：[1]清华大学电子工程系,北京100084

出　　处：《软件学报》2010年第12期3106-3115,共10页Journal of Software

基　　金：国家高技术研究发展计划(863)No.2007AA01Z2b3;国家重点基础研究发展计划(973)No.2007CB310608~~

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

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

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