关键字 |
| 基于FM的混合算法，面积缩减，数字VLSI电路划分算法 |
介绍 |
| 分割是生产和制造电路设计的第一步。计算机辅助设计在算法建模和高效的逻辑设计优化中起着至关重要的作用。应用程序逻辑被映射为图形，所有设计元素的连通性被转换为非有向图。然后决定软块和硬块。完全定制或半定制asic的设计风格的选择取决于芯片的预期功能、上市时间和要制造的芯片总数。 |
| 设计风格可以被看作是为了满足应用程序开发目的的不同需求。全定制为高性能设计提供紧凑的布局，FPGA完全预制，不需要用户特定的制造步骤[2]。这就需要把这些连续的、明显不可逆的物理设计阶段统一起来。VLSI物理设计包括将电路划分为更小的部分，以方便设计和布局[2,3]。电路分区的主要目标包括使分区之间的互连数量最小化，使分区之间的互连造成的延迟最小化，以及使ratio-cut最小化[4,12]。所考虑的电路被认为是一个图。 |
| 示例图如图[1]所示。该图为ACM /SIGDA[15]测试电路的表示，有7个门。这是一个小尺寸的测试电路。图中所有的电路元件都表示为节点，连接则表示为图的边。考虑的电路有5个输入和2个输出。输入和输出连接到栅极上。分区也被称为切割[13,14]。分割的代价称为切割大小[6,7]，它是穿过切割的超边的数量。FM算法没有两个分区大小相同的基本要求。所以当分区1和分区2交换完成时。The gain of each swap is calculated in terms of number of nets crossing the partitions. |
相关工作 |
| 在过去的十年中，有很多作品强调了小型化的必要性。分区阶段形成了物理设计过程的基础。在图论最早的工作中，节点已经被建模和划分，使用算法来最小化距离并形成一个集群。这些算法是基于移动的，最早的算法集中在分区之间的节点相互交换[2,8]。这种方法不适用于节点数为奇数的分区，Fidduccia和Mathysses在进一步的工作中适应了不同大小的分区[3,9]。对VLSI应用面积参数最小化重要性的综合调查[4,5]表明，与CAD工具提供的默认优化设计相比，有足够的算法选择范围来减少设计面积。 |
算法 |
| A.设计考虑: |
| •将选定的初始电路转换为有向图。 |
| •向内连接与向外连接数量的差异计算为增益。 |
| •跟踪之前的工作区域。 |
| •考虑所有可能的分区，使增益接近1。 |
| B.提出的算法描述: |
| 该算法的目的是在电路CAD设计过程中，通过混合遗传算法减小超大规模集成电路的面积。该算法由四个主要步骤组成。 |
| 步骤1:在应用算法之前计算VLSI电路的面积 |
| 步骤2:将电路转换为节点并应用算法。 |
| 步骤3:为分区值计算优化电路的面积。 |
| 步骤4:改变分区值，得到优化后电路的面积缩减。 |
伪代码 |
| 步骤1:将电路转换为节点，映射邻接矩阵。 |
| 步骤2:实现VLSI电路，计算面积参数。 |
| 第三步:将其作为输入输入到C语言的FM +mincut +GA算法中。 |
| 第四步:检查下面的收敛条件。 |
| If (mindis1 = mindis) |
| 该区域是最佳的，因此不会在分区之间交换节点 |
| 其他的 |
| 交换节点并计算距离 |
| 第五步:实现优化后的VLSI电路并计算面积参数。 |
| 步骤6:同一电路分区值不同转步骤3。 |
| 步骤8:结束。 |
仿真结果 |
| 本文针对电路C17网表，在C语言中应用Fidducia Matthyses [FM]基于移动的算法，然后对分割结果应用合并GA[10,11]的mincut算法。此步骤使用分区阶段输出执行优化。根据EDA工具的综合报告，计算了杂化对电路面积物理参数的影响。该方法包括从图中获取网络列表，然后应用算法并优化划分结果。利用Cadence EDA工具在算法应用前后生成区域报告，以评估算法的效率。 |
| FM和mincut算法对C17和C1908测试电路的影响如图[2]所示。对应用面积的影响平均约为30%。对于不同的分区，区域优化也不同。遗传算法收敛的准则，由最小切算法定义。还观察到，电路的大小并不影响算法的性能，但分区的数量使优化输出不同。 |
结论及未来工作 |
| 基于混合遗传算法的FM-Mincut算法在一系列数字电路和基准上的实现，表明在统一划分和放置阶段方面有很大的优势。在进一步的物理设计阶段之前，区域优化可以更准确。将贪婪启发式算法应用于同一层次的物理设计中，并与本文讨论的混合算法相结合，可以得到区域的最优解。这种方法可以进一步优化电路的面积。这种方法的应用对生物医学电路和可穿戴传感器的设计有更大的影响，其中应用程序的大小是主要的设计约束。 |
|
数字一览 |
 |
 |
| 图1 |
图2 |
|
|
参考文献 |
- Christopher J. Augeri Hesham H. Ali，“新的基于图的VLSI电路划分算法”，国际电路与系统研讨会论文集，心理学报，2004,vol-4, pp:521-524,2004。
- 林世林，“一种有效的划分图的启发式程序”，贝尔系统技术学报，Vol. 49, pp. 291 - 307,1970。
- Andrew E. Caldwell, Andrew B. Kahng和Igor L. Markov，“VLSI超图划分的基于移动的启发式设计与实现”，ACM, 2000。
- Rajine Swetha R . B. Shekar Babu, Sumithra Devi K.A，“Vlsi物理设计的各种算法综述”，世界科学工程与技术学院，Vol:5 2011-03-21，国际科学索引Vol:5, No: 3,390 -395,2011。
- Rajine Swetha R等，“VLSI物理合成的分层混合尺寸放置算法的比较”，CSNT '11 2011年通信系统和网络技术国际会议论文集，IEEE计算机学会华盛顿特区，美国，430-435页。
- David A. Papa和Igor L. Markov，“超图划分和聚类”，在逼近算法和元启发式中，CRC出版社，ISBN:61-1-61-19,2007。
- 沙纳瓦斯，i.h.， Gnanamurthy, R.K.;Thangaraj, T.S，“寻找最适合VLSI分区的新方法-物理设计”;通信与计算最新技术进展国际会议(ARTCom)， 2010。
- Naveed Sherwani，“VLSI物理设计和自动化算法”，第三版，施普林格(印度)私人有限公司，新德里，ISBN: 0792383931, 2005。
- 伯斯坦先生和尤瑟夫先生。，” Timing influenced layout design.”, In Proceedings of the Design Automation Conference, Albuquerque, NM, pp. 124–130, 1984.
- A.E.邓禄普，V.D.阿格拉瓦尔，D.N.多伊奇，M.F.朱克尔，P.科扎克和M.威塞尔。“使用关键路径加权的芯片布局优化”，《设计自动化会议论文集》，拉斯维加斯，NV, 133-136页，1985。
- 于宏，兴兴，蔡元庆，MMP:“一种新的宏块和标准单元组合布局设计算法”，IEEE亚洲和南太平洋设计自动化会议论文集，第271-276页，2000。
- Mehmet Can Yildiz, Patrick H. Madden“基于分区的改进切割序列”，设计自动化会议论文集(DAC ' 01)，。ISBN: 1-58113-297-2, 2001。
- Charles J Alpret, Dinesh Metha和Sachin S Sapatnekar，“物理设计自动化算法手册”，CRC出版社，2008年
- Sabih H. Gerez，“VLSI设计自动化算法”，威利印度，ISBN: 10: 0471984892, 2007。
- www.cbl.net
|
菜单
