Corner block list representation and its application with boundary constraints

Floorplanning is a critical phase in physical design of VLSI circuits. The stochastic optimization method is widely used to handle this NP-hard problem. The key to the floorplanning algorithm based on stochastic optimization is to encode the floorplan structure properly. In this paper, corner block list (CBL)-a new efficient topological representation for non-slicing floorplan-is proposed with applications to VLSI floorplan. Given a corner block list, it takes only linear time to construct the floorplan. In floorplanning of typical VLSI design, some blocks are required to satisfy some constraints in the final packing. Boundary constraint is one kind of those constraints to pack some blocks along the pre-specified boundaries of the final chip so that the blocks are easier to be connected to certain I/O pads. We implement the boundary constraint algorithm for general floorplan by extending CBL. Our contribution is to find the necessary and sufficient characterization of the blocks along the boundary repre     

平面布局的蚁群算法

为提高平面布局的优化结果和效率，使用蚁群算法作为平面布局优化算法。在算法中定义B*-tree结构来描述布局空间，定义模块布局利用率作为信息素，使得占用面积小的局部模块之间的依赖关系加强，引入蚁群的变异特征来加快算法的收敛效率。通过试验表明，蚁群算法同模拟退火算法相比，在解决硬模块(hard module)的平面布局问题时，能够得到较优化布局的结果和较快的运行效率。     

融合用户需求和边界约束的平面图生成算法

平面图设计是房屋设计的重要过程,而现有的自动化平面图设计方法缺乏考虑用户需求和建筑边界的共同约束,存在生成房间形状缺角、房间之间遮挡严重以及房间超越边界的布局不合理问题。针对上述问题,提出一种融合用户需求和边界约束的房屋平面图生成对抗网络（GBC-GAN）,它由约束布局生成器和房间关系鉴别器构成。首先,将用户指定的房屋布局需求（包括房间数量和类型以及房屋之间的邻接方位关系）转化为约束关系图结构,之后对建筑边界和约束关系图分别编码并进行特征融合;然后,在约束布局生成器中引入边界框预测模块以将平面图生成问题转化为各房间对象边界框生成问题,并利用几何边界优化损失来解决房间之间遮挡严重、房间超越边界的问题;最后,将房间边界框布局和约束关系图输入到房间关系鉴别器训练生成符合房间对象及其关系的平面图布局。在大型真实建筑数据集RPLAN上,该方法的弗雷歇距离（FID）和结构相似性指数（SSIM）比House-GAN方法分别提升了4.39%和2.3%。实验结果表明,在不同用户需求和边界限制条件下,所提方法提高了房屋平面图的合理性和真实性。     

Fast evaluation of Bounded Slice-line Grid

Bounded Slice-line Grid (BSG) is an elegant representation of block placement, because it is very intuitionistic and has the advantage of handling various placement constraints. However, BSG has attracted little attention because its evaluation is very time-consuming. This paper proposes a simple algorithm independent of the BSG size to evaluate the BSG representation in O(nloglogn) time, where n is the number of blocks. In the algorithm, the BSG-rooms are assigned with integral coordinates firstly, and then a linear sorting algorithm is applied on the BSG-rooms where blocks are assigned to compute two block sequences, from which the block placement can be obtained in O(n log logn) time. As a consequence, the evaluation of the BSG is completed in O(nloglogn) time, where n is the number of blocks. The proposed algorithm is much faster than the previous graph-based O(n^2) algorithm. The experimental results demonstrate the efficiency of the algorithm.     

面向应用的片上网络的网络拓扑生成算法

针对面向应用的片上网络,提出了一种三阶段的低功耗网络拓扑生成算法.首先基于内核通信量和物理坐标信息做划分驱动的布图规划,以确定内核的摆放位置以及内核和转换器之间的映射关系;其次考虑转换器和网络接口的面积消耗,并把它们的同时插入问题抽象成整数线性规划模型,通过求解此优化模型确定其最佳插入位置,生成互连网络;最后通过路由分配策略确定互连网络上的通信量分布,进一步优化功耗.实验结果表明,该算法平均能节省35.2%的功耗开销以及5.7%的中转转换器数目.     

65nm工艺下百万门级芯片的物理设计

随着集成电路工艺的发展,集成电路后端物理设计变得越来越复杂,遇到了很多新的挑战。本文介绍了一款65nm工艺百万门级芯片的物理设计过程,论述了在布局规划、电源网络规划、时钟树设计、信号完整性、可制造性设计等方面的解决方案,提出了设计方法学上的改进,提高了后端物理设计效率和芯片的良率。     

快速buffer添加算法

在深亚微米设计中,连线延迟时间已经超过器件延迟时间,成为影响性能的瓶颈之一。在线网中插入缓冲器（buffer）是改善线延迟的一种有效方法,但是目前基于缓冲器块（bufferblock）的方法一般因其计算量比较大,算法比较慢,并且也增加布局（floorplan）的复杂性。为此本文提出并实现了一种新的快速算法来解决芯片顶层互连中缓冲器添加问题。     

VLSI芯片平面图中不确定性问题研究

文章首先介绍了切片式平面图的表示及其主要特征，然后通过引入矩形模块高和宽的可信度，研究了切片式平面图中矩形模块的不确定性问题的相应的度量计算方法。     

UPRFloor:一种动态可重构FPGA建模方法与布局策略

针对现场可编程门阵列（Field Programmable Gate Array,FPGA）布局过程中片上可重构资源利用率低与通信开销过高问题,本文提出了一种支持多描述模型的布局策略Union Partial Reconfiguration Floorplans（UPRFloor）.首先,该策略根据逻辑功能客观形状,定义了矩形、非矩形多描述模型,然后利用混合整数线性规划方法,从可重构资源利用率、逻辑功能间通信开销与逻辑功能内部通信开销三个方面进行多目标优化,实现了三者之间相互影响与共同作用下的最优布局方案.该策略已在FPGA芯片上进行了仿真布局,结果表明：与基于矩形模型的布局方法相比,UPRFloor布局策略在资源利用率方面最高有25.59%的提升.在Microelectronics Center of North Carolina（MCNC）标准测试集上的对比实验表明：在耗时几乎相同的情况下,UPRFloor较其它算法的布线长度最多减少了22.49%;在Software Defined Radio（SDR）测试数据中,UPRFloor在节约29.41%可重构资源的同时,布线长度节省了13.41%,从而有效降低了资源浪费与通信开销.     

一种基于组的时序驱动布局规划方法

本文提出了一种基于组的时序驱动布局规划方法，它利用现有的EDA工具将网表划分为组，并充分利用设计师的体系结构经验进行布局、调整和优化。该方法能在设计早期获取较为准确的线负载模型，提高前端与后端的一致性，并且可以以组为单位规划电源和地的布局，提高布通率。该方法在已研制成功的32位嵌入式微处理器Estar的物理设计中得到实际应用。结果表明，该方法能够有效地改善关键路径时序和加快设计进程。