基于连接关系的标准单元布局算法研究

李丛

摘 要：本文对一种基于连接关系的快速布局算法进行了探索研究，该算法以优化一次线长为目标，利用单元给定连接关系信息消除单元重叠。

关键词：权重 分层 布局算法

中图分类号：TP393.02 文献标识码：A 文章编号：1672-3791（2014）02（c）-0010-01

超大规模集成电路的单元布局问题是一个在给定单元信息的基础上对单元集合进行布局的问题。它即使在最简单的情况下也是一个NP难的问题。因此，随着集成电路规模的增大，对超大规模的布局算法是一个挑战。布局阶段要求把模块分配到芯片上的合适位置，算法分为两种：一种是线长驱动的布局算法，一种是性能驱动的布局算法。其中线长驱动以线长最短为目标，在保证单元之间没有重叠摆放的前提下优化线长，线长越短，算法效果越好。[1～3]

因此，在保证算法质量的情况下，本文提出了一种基于单元的物理位置的连接关系分层算法。连接关系是指在给定NetList中包含线网的信息，在布局优化的趋势来看，在同一个线网中的单元被分布到相近的区域有助于总线长的减少，因此在初始阶段，提出以下两点方法：

（1）根据单元的连接关系对单元进行分层。

（2）根据分层后单元的分布情况，对权重进行调整。

1 布局问题描述

本文利用一次线长模型进行线长估计，分为三个部分：初始布局、总体布局、详细布局。[4]其中初始布局部分的流程如图1所示。

2 连接关系算法介绍

布局区域版面有I/O等固定点，如图2所示。

初始布局后多数单元在版面中心处堆叠，根据单元与固定点的连接关系，对单元进行分层处理，将这些堆叠的单元散开。如图2所示，最外层边框上有I/O点，首先将与I/O直接相连的单元移动到最外层；第二步，将与第一层的单元直接相连的单元移动至次外层；第三步，将与第二层的单元直接相连的单元移动至第三层圆角矩形的边缘，依此进行迭代重复。最终使单元被均匀分布到设计版面上。

本算法描述如下：

（1）找到文件中的固定单元，形成一个单元集合i（i=0），此时设置一个level标记变量，置为0。（2）根据单元集合i（i=0）找到与它们直接相连的可移动的单元的集合i（i=1），level自加1。（3）修改矩阵中的值，将集合i中的可移动单元与固定单元的连接权重增加，计算求出结果，将坐标结果记录，并将i中单元的移动状态置为fixed。（4）level+1，根据集合i找到与之直接相连的可移动单元的集合，i+1，重复（3）。直到单元都为固定状态时，结束。

3 算法结果分析

本文用C++进行算法实现，并在Intel Xeon3.0Hz CPU，6G内存的服务器上运行。分层之后的布局结果表明，迭代求解次数减少，在保证求解质量的前提下，提高了算法的效率。

4 结语

在这篇文章中，提出一种基于连接关系的总体布局算法，并通过大量实验探索研究影响该算法结果的各个因子。通过大量实验发现了该算法的有效性和合理性。

参考文献

[1] 徐宁，洪先龙.超大规模集成电路物理设计理论与算法[M].北京：清华大学出版社，2009.

[2] C.Sechen and K.W.Lee， “An Improved Simulated Annealing Algorithm for Row-Based Placement”， In proceeding of International Desing Automation Conference[M].IEEE/ACM，1988：180-183.

[3] J. Vygen. Algorithms for large-scale flat placement. In Proc[M]. ACM/IEEE Design Automation Conf.， 1997：746-751.

[4] M.-C. Kim， D.-J. Lee， and I. L. Markov， “SimPL： An Effective Placement Algorithm”[M].ICCAD，2010：649-656.endprint

摘 要：本文对一种基于连接关系的快速布局算法进行了探索研究，该算法以优化一次线长为目标，利用单元给定连接关系信息消除单元重叠。

关键词：权重 分层 布局算法

中图分类号：TP393.02 文献标识码：A 文章编号：1672-3791（2014）02（c）-0010-01

超大规模集成电路的单元布局问题是一个在给定单元信息的基础上对单元集合进行布局的问题。它即使在最简单的情况下也是一个NP难的问题。因此，随着集成电路规模的增大，对超大规模的布局算法是一个挑战。布局阶段要求把模块分配到芯片上的合适位置，算法分为两种：一种是线长驱动的布局算法，一种是性能驱动的布局算法。其中线长驱动以线长最短为目标，在保证单元之间没有重叠摆放的前提下优化线长，线长越短，算法效果越好。[1～3]

因此，在保证算法质量的情况下，本文提出了一种基于单元的物理位置的连接关系分层算法。连接关系是指在给定NetList中包含线网的信息，在布局优化的趋势来看，在同一个线网中的单元被分布到相近的区域有助于总线长的减少，因此在初始阶段，提出以下两点方法：

（1）根据单元的连接关系对单元进行分层。

（2）根据分层后单元的分布情况，对权重进行调整。

1 布局问题描述

本文利用一次线长模型进行线长估计，分为三个部分：初始布局、总体布局、详细布局。[4]其中初始布局部分的流程如图1所示。

2 连接关系算法介绍

布局区域版面有I/O等固定点，如图2所示。

初始布局后多数单元在版面中心处堆叠，根据单元与固定点的连接关系，对单元进行分层处理，将这些堆叠的单元散开。如图2所示，最外层边框上有I/O点，首先将与I/O直接相连的单元移动到最外层；第二步，将与第一层的单元直接相连的单元移动至次外层；第三步，将与第二层的单元直接相连的单元移动至第三层圆角矩形的边缘，依此进行迭代重复。最终使单元被均匀分布到设计版面上。

本算法描述如下：

（1）找到文件中的固定单元，形成一个单元集合i（i=0），此时设置一个level标记变量，置为0。（2）根据单元集合i（i=0）找到与它们直接相连的可移动的单元的集合i（i=1），level自加1。（3）修改矩阵中的值，将集合i中的可移动单元与固定单元的连接权重增加，计算求出结果，将坐标结果记录，并将i中单元的移动状态置为fixed。（4）level+1，根据集合i找到与之直接相连的可移动单元的集合，i+1，重复（3）。直到单元都为固定状态时，结束。

3 算法结果分析

本文用C++进行算法实现，并在Intel Xeon3.0Hz CPU，6G内存的服务器上运行。分层之后的布局结果表明，迭代求解次数减少，在保证求解质量的前提下，提高了算法的效率。

4 结语

在这篇文章中，提出一种基于连接关系的总体布局算法，并通过大量实验探索研究影响该算法结果的各个因子。通过大量实验发现了该算法的有效性和合理性。

参考文献

[1] 徐宁，洪先龙.超大规模集成电路物理设计理论与算法[M].北京：清华大学出版社，2009.

[2] C.Sechen and K.W.Lee， “An Improved Simulated Annealing Algorithm for Row-Based Placement”， In proceeding of International Desing Automation Conference[M].IEEE/ACM，1988：180-183.

[3] J. Vygen. Algorithms for large-scale flat placement. In Proc[M]. ACM/IEEE Design Automation Conf.， 1997：746-751.

[4] M.-C. Kim， D.-J. Lee， and I. L. Markov， “SimPL： An Effective Placement Algorithm”[M].ICCAD，2010：649-656.endprint

摘 要：本文对一种基于连接关系的快速布局算法进行了探索研究，该算法以优化一次线长为目标，利用单元给定连接关系信息消除单元重叠。

关键词：权重 分层 布局算法

中图分类号：TP393.02 文献标识码：A 文章编号：1672-3791（2014）02（c）-0010-01

超大规模集成电路的单元布局问题是一个在给定单元信息的基础上对单元集合进行布局的问题。它即使在最简单的情况下也是一个NP难的问题。因此，随着集成电路规模的增大，对超大规模的布局算法是一个挑战。布局阶段要求把模块分配到芯片上的合适位置，算法分为两种：一种是线长驱动的布局算法，一种是性能驱动的布局算法。其中线长驱动以线长最短为目标，在保证单元之间没有重叠摆放的前提下优化线长，线长越短，算法效果越好。[1～3]

因此，在保证算法质量的情况下，本文提出了一种基于单元的物理位置的连接关系分层算法。连接关系是指在给定NetList中包含线网的信息，在布局优化的趋势来看，在同一个线网中的单元被分布到相近的区域有助于总线长的减少，因此在初始阶段，提出以下两点方法：

（1）根据单元的连接关系对单元进行分层。

（2）根据分层后单元的分布情况，对权重进行调整。

1 布局问题描述

本文利用一次线长模型进行线长估计，分为三个部分：初始布局、总体布局、详细布局。[4]其中初始布局部分的流程如图1所示。

2 连接关系算法介绍

布局区域版面有I/O等固定点，如图2所示。

初始布局后多数单元在版面中心处堆叠，根据单元与固定点的连接关系，对单元进行分层处理，将这些堆叠的单元散开。如图2所示，最外层边框上有I/O点，首先将与I/O直接相连的单元移动到最外层；第二步，将与第一层的单元直接相连的单元移动至次外层；第三步，将与第二层的单元直接相连的单元移动至第三层圆角矩形的边缘，依此进行迭代重复。最终使单元被均匀分布到设计版面上。

本算法描述如下：

（1）找到文件中的固定单元，形成一个单元集合i（i=0），此时设置一个level标记变量，置为0。（2）根据单元集合i（i=0）找到与它们直接相连的可移动的单元的集合i（i=1），level自加1。（3）修改矩阵中的值，将集合i中的可移动单元与固定单元的连接权重增加，计算求出结果，将坐标结果记录，并将i中单元的移动状态置为fixed。（4）level+1，根据集合i找到与之直接相连的可移动单元的集合，i+1，重复（3）。直到单元都为固定状态时，结束。

3 算法结果分析

本文用C++进行算法实现，并在Intel Xeon3.0Hz CPU，6G内存的服务器上运行。分层之后的布局结果表明，迭代求解次数减少，在保证求解质量的前提下，提高了算法的效率。

4 结语

在这篇文章中，提出一种基于连接关系的总体布局算法，并通过大量实验探索研究影响该算法结果的各个因子。通过大量实验发现了该算法的有效性和合理性。

参考文献

[1] 徐宁，洪先龙.超大规模集成电路物理设计理论与算法[M].北京：清华大学出版社，2009.

[2] C.Sechen and K.W.Lee， “An Improved Simulated Annealing Algorithm for Row-Based Placement”， In proceeding of International Desing Automation Conference[M].IEEE/ACM，1988：180-183.

[3] J. Vygen. Algorithms for large-scale flat placement. In Proc[M]. ACM/IEEE Design Automation Conf.， 1997：746-751.

[4] M.-C. Kim， D.-J. Lee， and I. L. Markov， “SimPL： An Effective Placement Algorithm”[M].ICCAD，2010：649-656.endprint