CN105677956B - 一种芯片缓冲器的插入方法 - Google Patents

Abstract

本发明涉及涉及集成电路技术领域，尤其涉及一种芯片缓冲器的插入方法，所述方法包括：单元化所述芯片，以在所述芯片上形成若干均等的单元格；分别确定位于所述芯片上的所有门中每个门的可移动范围；基于所述每个门的可移动范围，在满足每个所述单元格至多被一个所述门或一个缓冲器覆盖的条件下，确定可插入在所述芯片内的所述缓冲器的数量。本发明通过将芯片单元化，在确定出芯片上的每个门的可移动范围之后，根据每个门的可移动范围可以确定出可插入在芯片内的缓冲器的数量，从而，不仅优化了芯片的布局，提高了芯片上可插入缓冲器的缓冲区的数量，还降低了芯片的互联延时。

Description

一种芯片缓冲器的插入方法

技术领域

本发明涉及集成电路技术领域，尤其涉及一种芯片缓冲器的插入方法。

背景技术

芯片上的gate是MOS管(Metal Oxide Semiconductor)上的控制用的门。通常，芯片上会分布有多个门，门与门之间具有一定距离，当需要在两个门之间放置缓冲器(buffer)，但是，两个门之间没有足够的位置时，只能将缓冲器移动到其他能够容纳该缓冲器的区域。如图1所示，假设需要在gate7和gate8之间插入一个缓冲器，但是，gate7和gate8之间没有足够大的位置放置缓冲器，缓冲器只能被移动到gate2和gate3之间进行放置。然而，在移动缓冲器的过程中，将会增加线长，当线长过大时，会增加芯片上的互联延时。

综上所述，按照现有技术中的上述缓冲器插入方法，不仅芯片上可插入的缓冲器的数量有限，而且，在移动缓冲器的过程中容易造成缓冲区的总线长过大，从而增大芯片上的互联延时，降低缓冲器插入的效率。

发明内容

本发明通过提供一种芯片缓冲器的插入方法，解决了现有技术在芯片上可插入的缓冲器的数量有限，且缓冲器移动过程中线长过大所造成的芯片互联延时过长的技术问题。

本发明实施例提供了一种芯片缓冲器的插入方法，所述方法包括：

单元化所述芯片，以在所述芯片上形成若干均等的单元格；

分别确定位于所述芯片上的所有门中每个门的可移动范围；

基于所述每个门的可移动范围，在满足每个所述单元格至多被一个所述门或一个缓冲器覆盖的条件下，确定可插入在所述芯片内的所述缓冲器的数量。

可选的，确定每个门的可移动范围，具体为：

根据每个门在所述芯片上的初始位置，以及所述芯片的高度和宽度，确定每个门在所述芯片的垂直方向和水平方向上的可移动范围。

可选的，所述芯片上的所述门或所述缓冲器逐行分布。

可选的，一个所述门至少覆盖一个所述单元格，一个所述缓冲器至少覆盖一个所述单元格。

可选的，当一个所述单元格或一组所述单元格被所述门覆盖时，一个所述单元格的顶点或一组所述单元格的顶点与所述门的顶点重合；

当一个所述单元格或一组所述单元格被所述缓冲器覆盖时，一个所述单元格的顶点或一组所述单元格的顶点与所述缓冲器的顶点重合。

可选的，所述基于所述每个门的可移动范围，在满足每个所述单元格至多被一个所述门或一个缓冲器覆盖的条件下，确定可插入在所述芯片内的所述缓冲器的数量，具体包括：

根据整数线性规划，构建如下方程组：

目标函数：

其中，γ_i,j用于表示门是否被放置在顶点坐标为(i，j)的单元格内，β_i,j用于表示缓冲器是否被放置在顶点坐标为(i，j)的单元格内，当门被放置在顶点坐标为(i，j)的单元格内，则γ_i,j为1，否则γ_i,j为0，当缓冲器被放置在顶点坐标为(i，j)的单元格内，则β_i,j为1，否则β_i,j为0，P为所述芯片上的任一单元格的顶点；

求解所述方程组，从而确定可插入在所述芯片内的所述缓冲器的数量。

本发明实施例中的一个或多个技术方案，至少具有如下技术效果或优点：

本发明通过将芯片单元化，在确定出芯片上的每个门的可移动范围之后，根据每个门的可移动范围可以确定出可插入在芯片内的缓冲器的数量，从而，不仅优化了芯片的布局，提高了芯片上可插入缓冲器的缓冲区的数量，还降低了芯片的互联延时。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据提供的附图获得其他的附图。

图1为现有技术中缓冲器插入方法的示意图；

图2为本发明实施例中一种芯片缓冲器的插入方法的流程图；

图3为本发明实施例中一个具体实施方式的示意图。

具体实施方式

为解决现有技术在芯片上可插入的缓冲器的数量有限，且缓冲器移动过程中线长过大所造成的芯片互联延时过长的技术问题，本发明提供一种芯片缓冲器的插入方法。

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本发明实施例提供一种芯片缓冲器的插入方法，如图2所示，所述方法包括：

步骤101：单元化芯片，以在芯片上形成若干均等的单元格。

在具体实施过程中，首先将芯片按照事先定义好的一个单元的大小进行单元化，即，将芯片分为若干单元格，各个单元格的大小相同。一个门至少覆盖一个单元格，同样，一个缓冲器至少覆盖一个单元格。具体的，一个门可以覆盖一个单元格，一个门也可以覆盖多个单元格，当一个门覆盖多个单元格时，多个单元格即成为一组单元格。同样，一个缓冲器可以覆盖一个单元格，一个缓冲器也可以覆盖多个单元格，当一个缓冲器覆盖多个单元格时，多个单元格即成为一组单元格。其中，可以以每个单元格或每组单元格的左下角作为该一个单元格或该一组单元格的顶点，例如，对于一个单元格而言，该单元格的左下角作为该单元格的顶点，对于一组单元格而言，该组单元格中最左边的一个单元格的左下角作为该组单元格的顶点。

进一步，当一个单元格或一组单元格被门覆盖时，一个单元格的顶点或一组单元格的顶点与门的顶点重合，同样，当一个单元格或一组单元格被缓冲器覆盖时，一个单元格的顶点或一组单元格的顶点与缓冲器的顶点重合。例如，当门覆盖在一个单元格上，则，门的顶点与该单元格的左下角重合，当门覆盖在一组单元格上，则，门的顶点与该组单元格中最左边的单元格的左下角重合，缓冲器具有同样的覆盖规则，此处不再赘述。

在执行完步骤101之后，本申请执行步骤102：分别确定位于芯片上的所有门中每个门的可移动范围。

在具体实施过程中，根据每个门在芯片上的初始位置，以及芯片的高度和宽度，给定每个门在芯片的垂直方向和水平方向上的可移动范围，即，每个门在芯片的x方向和y方向上的可移动范围。例如，如图3所示，在一具体实施例中，按照预定义好的一个单元的长度对芯片单元化之后，在一行芯片上形成6个单元格，该芯片上分布有2个门，分别为门1(gate1)和门2(gate2)，gate1的初始位置位于第二单元格，gate2的初始位置位于第四单元格，gate1的顶点与第二单元格的顶点重合，gate2的顶点与第四单元格的顶点重合。给定的gate1的可移动范围为向左和向右移动1个单元格，则，gate1可以放置在第一单元格或第二单元格或第三单元格中。给定的gate2的可移动范围为向左和向右移动2个单元格，则，gate2可以放置在第二单元格或第三单元格或第四单元格或第五单元格或第六单元格中。

在执行完步骤102之后，本申请执行步骤103：基于所述每个门的可移动范围，在满足每个所述单元格至多被一个所述门或一个缓冲器覆盖的条件下，确定可插入在所述芯片内的所述缓冲器的数量。

在具体实施过程中，根据整数线性规划(ILP，Integer Linear Programming)，构建如下方程组：

目标函数：

其中，γ_i,j用于表示门是否被放置在顶点坐标为(i，j)的单元格内，β_i,j用于表示缓冲器是否被放置在顶点坐标为(i，j)的单元格内，当门被放置在顶点坐标为(i，j)的单元格内，则γ_i,j为1，否则γ_i,j为0，当缓冲器被放置在顶点坐标为(i，j)的单元格内，则β_i,j为1，否则β_i,j为0，P为所述芯片上的任一单元格的顶点。例如，γ_1,1＝1，即表明门可以被放置顶点坐标为(1,1)的第一单元格内。P为芯片上的任一单元格的顶点。通过求解上述方程组，从而确定可插入在芯片内的缓冲器的最大数量。

具体来讲，在向芯片中插入缓冲器时，一方面应满足：芯片上的所有元件逐行分布，不存在任何一个元件跨行分布。另一方面应满足：芯片上的元件之间无叠加。本申请利用整数线性规划来求解缓冲器的放置问题，即，求解芯片上可插入的缓冲器的最大值，其中，缓冲器的数量也即缓冲区的数量。

在上述方程组中，目标函数为：第一约束条件为： 所有的门，即，所有的门必然分布在芯片上。第二约束条件为：

所有的P

即，芯片上的门和缓冲器之间无叠加。具体来讲，表示所有覆盖顶点为P的单元格的β_i,j的集合，即，缓冲器在移动过程中所有覆盖了顶点为P的单元格的可能位置的集合。表示所有覆盖顶点为P的单元格的γ_i,j的集合，即，门在移动过程中所有覆盖了顶点为P的单元格的可能位置的集合。

进一步，在求解方程组时假设缓冲器可以放在任一单元格内。例如，在上述的具体实施例中，参见图3，可列出如下方程组：

最后，通过单纯形算法(Simplex Method)可求解出该线性规划，得出结果，本例中可插入的缓冲器的最大值为4。

上述本申请实施例中的技术方案，至少具有如下的技术效果或优点：

本发明通过将芯片单元化，在确定出芯片上的每个门的可移动范围之后，根据每个门的可移动范围可以确定出可插入在芯片内的缓冲器的数量和位置，从而，不仅优化了芯片的布局，提高了芯片上可插入缓冲器的缓冲区的数量，还降低了芯片的互联延时。

尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例作出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本发明范围的所有变更和修改。

显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。

Claims (5)

1.一种芯片缓冲器的插入方法，其特征在于，所述方法包括：

单元化所述芯片，以在所述芯片上形成若干均等的单元格；

分别确定位于所述芯片上的所有门中每个门的可移动范围；

基于所述每个门的可移动范围，在满足每个所述单元格至多被一个所述门或一个缓冲器覆盖的条件下，确定可插入在所述芯片内的所述缓冲器的数量；

其中，所述基于所述每个门的可移动范围，在满足每个所述单元格至多被一个所述门或一个缓冲器覆盖的条件下，确定可插入在所述芯片内的所述缓冲器的数量，具体包括：

根据整数线性规划，构建如下方程组：

目标函数：

约束条件：

其中，γ_i,j用于表示门是否被放置在顶点坐标为(i，j)的单元格内，β_i,j用于表示缓冲器是否被放置在顶点坐标为(i，j)的单元格内，当门被放置在顶点坐标为(i，j)的单元格内，则γ_i,j为1，否则γ_i,j为0，当缓冲器被放置在顶点坐标为(i，j)的单元格内，则β_i,j为1，否则β_i,j为0，P为所述芯片上的任一单元格的顶点，表示所有覆盖顶点为P的单元格的β_i,j的集合，表示所有覆盖顶点为P的单元格的γ_i,j的集合；

求解所述方程组，从而确定可插入在所述芯片内的所述缓冲器的数量。

2.如权利要求1所述的方法，其特征在于，确定每个门的可移动范围，具体为：

根据每个门在所述芯片上的初始位置，以及所述芯片的高度和宽度，确定每个门在所述芯片的垂直方向和水平方向上的可移动范围。

3.如权利要求1所述的方法，其特征在于，所述芯片上的所述门或所述缓冲器逐行分布。

4.如权利要求1所述的方法，其特征在于，一个所述门至少覆盖一个所述单元格，一个所述缓冲器至少覆盖一个所述单元格。

5.如权利要求4所述的方法，其特征在于，当一个所述单元格或一组所述单元格被所述门覆盖时，一个所述单元格的顶点或一组所述单元格的顶点与所述门的顶点重合；

当一个所述单元格或一组所述单元格被所述缓冲器覆盖时，一个所述单元格的顶点或一组所述单元格的顶点与所述缓冲器的顶点重合。