集成电路模板提取算法综述

摘要：数据通路型集成电路中存在着高度的规律性，利用其规律性可以实现规则的布图以提高芯片的性能。该文介绍了基于图论的集成电路模板提取算法的研究进展情况，给出了TREE、SPOG和FAN等典型模板提取算法的思想，综合分析了各算法的优缺点及其适用情况，总结并比较了模板提取算法的一些重要性质，并对未来模板提取技术作了一下展望。

关键词：可重构；模板提取；图同构；子图扩展；数据流图

中图分类号：TP391 文献标识码：A 文章编号：1009-3044(2011)01-0251-03

An Overview of Regularity Extraction Algorithms in Integrated Circuits

ZHANG Hou-jun, ZHOU Zhou

(Department of Computer Science and Technology, Tongji University, Shanghai 201804, China)

Abstract: Data-path dominated integrated circuits always have a good amount of regularity in them. Regularity of integrated circuits has the merits for predigesting design, shortening the period of design, reducing the design cost, and improving the performance of the system. This paper is a literature review. It introduces the recent study of graph-theory based regularity extraction algorithms in summary. Meanwhile the solving idea and time-complexity of some classical algorithms, such as TREE and SPOG, are introduced. The advantages and disadvantages are analyzed too. Moreover, some important properties are summarized and compared. Last, this paper provides a referenced direction for the study of regularity extraction.

Key words: reconfigurable; regularity extraction; graph isomorphism; sub-graph extension; data-flow graph

1 概述

随着集成电路制造技术的进步和应用需求的增长，整个系统现在已经可以集成在单个芯片之中，片上系统(system on a chip，SoC)已成为集成电路系统设计的重要形式和热点研究内容。然而，当前集成电路设计能力不足已成为制约集成电路工业进一步发展的重要因素。因此必须尽快改进设计方法，不断提高设计能力[12]。

传统的设计方法中忽略了系统描述本身所包含的结构特性。在以数据处理为主的应用描述中往往具有高度的规律性，存在着大量的相似结构，利用其规律性可以实现规则的布图以提高芯片的性能及可制造性。因此，如果能够将基于模板的技术用在集成电路的设计当中，分析和提取电路中相似结构以实现规则性的布图，那么芯片在性能和集成度方面将会有大大改善。

电路模板技术是指将电路中重复出现的子电路抽象出来作为模板，它在电路性能的提高、电路的验证、设计重用、电路划分等领域以及处理高层次综合领域中的调度和分配问题都具有重要的作用[12]。因此对集成电路的规则性提取问题的研究在VLSI 自动化设计领域具有深远的意义。

此外，嵌入式多媒体应用程序的一个显著特点也是规则运算很多，运算时间复杂度很高，因此也迫切需要提高性能，降低功耗。

从输入数据流图(data-flow graph, DFG)中提取出图中频繁运用的子图集合或相似子图集合，通过后续模板覆盖、任务划分和调度阶段对原始DFG进行模板覆盖，将相似子程序调度到相同的PE阵列上去，这使得程序的调度更有效，最大可能地复用模块单元实现系统的功能，提高重用性，减少系统的面积。因此，基于模板的技术也是可重构系统任务编译器前端设计中一种较有效的方法。如果能在可重构系统的编译器当中使用模板技术，那么对系统的并行处理及逻辑优化等将会有很大帮助。

无论是对数据通路型集成电路还是对嵌入式多媒体应用程序进行规律性提取时，通常都是将电路的门级网表或者程序转化为对应的DFG表示。因此，本文主要讨论基于图论的模板提取。

2 问题定义

对于一个DFG，结点表示一个简单的操作（比如ADD，SUB等），有向边表示数据流的方向。设G(V，E)表示一个DFG，V为其顶点集，E为其边集，有如下定义。

定义1 若图SG(SV，SE) 满足SV∈V 及SE∈E，则称SG是G 子图[16]。

定义2 对于G(V，E)中的两个子图G1(V1，E1)，G2(V2，E2)，如果V1和V2之间存在一一对应的映射关系f：V1V2，对于vi，vj∈V1，∈E1当且仅当∈E2，并且与的重数相同，那么称G(V，E)的两个子图G1(V1，E1)，G2(V2，E2)是同构的[16]。

定义3 模板T就是DFG中频繁出现的子图结构，而与此模板结构相同的子图称为该模板的实例，这种子图的个数称为该模板的频数[13]。

定义4 若SG(SV，SE)是G(V，E)的一个子图，将SV记为有序的结点集，则SV的第一个结点称为SV或子图SG的起点[12]。

定义5 图G(V，E)的顶点平均度，记作

其中，deg(vi)为顶点vi的度，表示与vi相邻顶点的个数[11]。

3 现有模板提取算法分析

目前，国外有些学者提出了一些模板提取的算法，并取得了一定的研究成果，国内研究尚处于初级阶段。下面对一些典型的模板提取算法的思想作一下介绍。

3.1 模板提取算法

3.1.1 TREE和SPOG算法[8]

由Chowdhary等人提出的TREE算法能够提取出单输出和内部没有汇聚的模板。而且其通过两个假设（假设1：把图G的子图集S限制在只包括某些子图，这些子图满足不再是S中任一图的子图，且在S中其频数大于1。假设2：对于G中每一个有入边的结点v，假设其有f条入边，前驱结点分别为u1,u2…uf，每一条边都被赋予一个唯一的索引号，k[ui, v]=i, 1≤i≤f）将树形模板的数量减少到v(v-1)/2。算法的基本思想如下：

1）对G的所有结点进行拓扑排序v1,v2…vn。

2）对于任意两个编号的结点vi, vj(1≤i,j≤n)，生成以这两个结点为根的功能上相同的最大子图作为一个模板Sm。

3）判断模板库中是否存在于Sm功能上等价的模板。如果不存在，将Sm加入到模板库当中；否则，舍弃Sm。

SPOG算法则是在TREE算法基础上的扩展和改进，将生成的模板扩展到多输出模板。此时SPOG子图的数量可以被限制在v(v-1)。

TREE算法和SPOG算法是典型的模板提取算法，它能够提取出基于两个假设以及各自限制条件之内的所有模板，这对于后续的模板覆盖有很大的帮助，覆盖率较高。但同时此算法也有着很大的不足之处，都适用于分散图，且生成的模板限制在tree形或spog形，算法的复杂度也很高，为O(v5)，不适合实际工程的需要。

3.1.2 FAN算法[15]

潘伟涛等人提出的FAN算法通过边权值编码，先生成小规模模板，然后再逐级扩展生成较大规模模板，产生扇形频繁子电路。算法的基本思想如下：

1）统计电路中每种标准单元出现的频率。依据最小支持度确定为各标准单元作标记还是删除它，并计算所有顶点的有效输入权值。

2）搜索所有同构实例，对于每一个同构实例在最左顶点扩展一条边。

3）统计扩展后的扇形子电路的种类和频数。依据最小支持度确定将此子电路标记为模板并进行下一轮的扩展还是将它删除。

FAN算法采用最小支持度对每次扩展生成的子图进行限制，通过比较子电路的出现的频数，有效地避免了子图扩展时一些不必要的冗余扩展，并且此算法采用逐级扩大规模的方法，得到的模板层次化较强，可以对电路进行更好的覆盖实用性较强。

3.1.3 其他算法

Rao and Kurdahi [3]最早关注于数据通路型集成电路的模板提取，它将基于模板的聚类思想应用到数据通路的综合上，这里的模板提取过程也就是基于不同子图（它们可以被复制来覆盖整个DFG）的识别过程。文献[4]在解决模板提取问题时，假设子模块已经生成，主要解决子模块分类问题，但是一般情况下需要自动生成模块。文献[5-6]提出了一些模块生成算法，但均是先选择某一顶点作为一个模块，然后在此模块内不断加入其它的顶点形成新的模块。这几种算法对模块的形式没有限制，但也有其固有的缺点，就是所生成的模块形式依赖于起始模块的选择。文献[11]提出了一种基于顶点的辐射路特征的门级到功能模块级的快速子电路提取算法，解决了宏单元模板自动匹配，通过单个顶点的相似度特征，将子图同构问题转化为顶点之间的匹配问题，算法最差时间复杂度为■（其中，n和k为两图结点数，d为原始电路的直径）。文献[12]中算法对DFG的整体结构以及模块的结构没有要求，增强了算法的健壮性，而且生成的模板的层次化较强，模板覆盖率较高，但在同构判断时无针对性，需对所有模板进行一一判断，导致程序复杂性的提高。

3.2 模板提取算法的比较与分析

模板提取算法有以下一些重要性质：1）输入DFG的类型，如连通图、有向图和无环图等；2）遍历策略，如深度优先或者广度优先等；3）候选子图的产生策略，如逐级扩展还是其他；4）对重复图的消除策略，如主动地或被动地；5）生成模板的层次化，如较好或较差。表1详细列出了一些模板提取算法的重要性质，并进行了比较。

4 总结和展望

随着集成电路产业的发展，迫切地需要提高芯片的性能，而利用集成电路自身的规律性可以实现规则的布图。因此，基于模板的技术将会对提高芯片的性能及可制造性有很大的帮助。本文归纳了基于图论的模板提取的各种算法，目前在这方面的研究已经取得了很大成绩，并被应用到一些实际的系统中。本文重点介绍了TREE、SPOG和FAN等典型的模板提取算法，并对其他算法进行了简要介绍。归纳出模板提取算法的一些重要性质，并对现有各算法进行了比较。

虽然目前存在的算法较多，且执行效率较高，但我们觉得还可以在以下方面加以改进或做进一步的研究：

1）现实生活中有各种各样的图形：有向图，无向图，加权图，无连通图等，但目前的算法大部分都是针对连通图的提取，对加权图有环图等的提取算法很少，因此对加权图有环图等的提取算法的研究也是一个重要的研究方向。

2）现有方法优势还主要集中在对小规模集成电路的提取上，集成电路产业的发展要求我们能够对大规模甚至超大规模集成电路进行提取，因此需要研究大规模集成电路的提取方法。

3）模板提取评测方法的研究。目前主要是靠算法复杂度的评估以及模板覆盖率等，在模板覆盖阶段，现有最大模板优先和最频繁模板优先的方法，但这样不能达到对系统最好覆盖，因此我们应该考虑如何在模板的规模和频数之间进行权衡，以利用所提取的模板达到对系统的最完美覆盖，最大程度地减小系统面积开销。

参考文献：

[1] Philip Brisk,Adam Kaplan,Ryan Kastner,Majid Sarrafzadeh.Instruction Generation and Regularity Extraction For Reconfigurable Processors[C].Proceedings of the ACM,Grenoble,France,2002:262-269.

[2] Yuanqing Guo,Gerard J M,Smit Hajo,et al.Template Generation and Selection Algorithms[C].Proceedings of The 3rd IEEE International Workshop on System-on-Chip for Real-Time Applications,2003.

[3] Rao D S,Kurdahi F J.Partitioning by regularity extraction. In: Proceedings of the ACM[C].IEEE Design Automation Conference,Anaheim,California,USA,1992:235-238.

[4] Rao D S,Kurdahi F J.An approach to scheduling and allocation using regularity extraction[C].Proceedings of the Europe Conference on Design Automation,Paris,France,1993:557-561.

[5] Arikati S R,Varadarajan R.A signature based approach to regularity extraction[C].Proceedings of the International Conference on Computer Aided Design,San Jose,California,USA,1997:542-545.

[6] Kutzschebauch T.Efficient logic optimization using regularity extraction[C].Proceedings of the International Workshop on Logic Synthesis,Austin,Texas,USA,1999:487-493.

[7] Shmidt D,Druffel L.A fast backtracking algorithm to test directed graphs for isomorphism using distance measures[J].Journal of ACM,1976,23(3):433-445.

[8] Chowdhary A,Kale S,Saripella P,et al.A general approach for regularity extraction in datapath circuits[C].Proceedings of the International Conference on Computer Aided Design,San Jose, California,USA,1998:332-339.

[9] Rosiello A P E,Ferrandi F,Pandini D,et al.A Hash-based Approach for Functional Regularity Extraction During Logic Synthesis[C]//IEEE Computer Society Annual Symposium on VLSI.New York:IEEE, 2007:92-97.

[10] Chowdhary A,Kale S.Extraction of Functional Regularity in Datapath Circuits[J].IEEE Trans on Computer Aided Design,1999,18(9):1279-1296.

[11] 李长青,汪雪林,彭思龙.辐射路匹配：从门级到功能模块级的子电路提取算法[J].计算机辅助设计与图形学学报,2006,18(9):1377-1382.

[12] 郎荣玲,秦红磊,路辉.集成电路中的规则性提取算法[J].计算机学报,2006,29(4):597-601.

[13] 潘伟涛,谢元斌,郝跃,等.二同构扩展集成电路规律性提取算法[J].西安电子科技大学学报:自然科学版,2009,36(3):452-457.

[14] 韩睦华,刘雷波,魏少军.基于模板的SoC结构自动划分方法[J].计算机辅助设计与图形学学报,2009,21(5):680-687.

[15] 潘伟涛,谢元斌,郝跃,等.基于扇形模板的数字集成电路规律性提取算法[J].电子学报,2010,38(1):199-203.