面向倒装封装技术的增量式I/O规划方法

摘要

面向倒装封装技术的增量式I/O规划方法，属于集成电路计算机辅助设计领域，尤其涉及布图规划后处理领域，其特征在于，依次含有以下步骤：计算模块对输入输出缓冲器的需求；把模块对缓冲器的需求转化为对空白区的需求；根据模块的空白区需求进行空白区重分配；建立将缓冲器插入空白区的网络流模型；用压入与重标记方法求解网络流模型，求得缓冲器的最佳插入方案；建立对封装凸点进行信号分配的网络流模型；用压入与重标记方法求解网络流模型，求得封装凸点的最佳信号分配方案。

主权项

1.面向倒装封装技术的增量式I/O规划方法，其特征在于，所述方法是在计算机中依次按照以下步骤实现的：步骤(1)，计算机初始化：输入芯片的原始布局信息，包括：模块信息、网表信息、电源地缓冲器信息、输入输出缓冲器信息以及输入输出缓冲器数和电源地缓冲器数之比，称为电源信号比R^SPG；步骤(2)，计算模块的空白区需求：步骤(2.1)，定义：粘附边，是指在所述输入输出缓冲器中，与其中每一个缓冲器所在线网的边框相交的模块的边框，所述粘附边的数目用Nae_k表示，k是所述缓冲器的序号，把1/Nae_k称之为所述缓冲器k分配到所述粘附边上的概率，1/Nae_k也叫做模块对缓冲器k的需求；步骤(2.2)，计算所述模块的输入输出缓冲器需求：其中：TBuf_i、BBuf_i、LBuf_i、RBuf_i分别表示模块i的上、下、左、右各边框的缓冲器需求；步骤(2.3)，把步骤(2.2)得到的模块i对缓冲器的需求转化为对空白区的需求：TW_i＝TBuf_i×Abuf_k×(1+1/R^SPG)BW_i＝BBuf_i×Abuf_k×(1+1/R^SPG)LW_i＝LBuf_i×Abuf_k×(1+1/R^SPG)，其中：RW_i＝RBuf_i×Abuf_k×(1+1/R^SPG)Abuf_k为所述模块i对应的所述缓冲器的面积，TW_i、BW_i、LW_i、RW_i分别表示所述模块i上、下、左、右边框的空白区需求；步骤(3)，根据步骤(2.3)得到的各模块i的空白区需求对空白区进行重分配，步骤如下：步骤(3.1)，建立空白区重分配的目标函数：$\min \underset{i\in M}{\Sigma }\{h_i(L_i-l_i)+h_i(R_i-r_i)+w_i(T_i-t_i)+w_i(B_i-b_i)\},$其中：h_i为模块i的高，w_i为模块i的宽，L_i为模块i左边界所需空白区的宽度，R_i为模块i右边界所需空白区的宽度，T_i为模块i上边界所需空白区的高度，B_i为模块i下边界所需空白区的高度，l_i是与L_i对应的最终分配的空白区宽度，r_i是与R_i对应的最终分配的空白区宽度，t_i是与T_i对应的最终分配的空白区高度，b_i是与B_i对应的最终分配的空白区高度，M是模块i的集合，L_i＝LW_i/h_i，        R_i＝RW_i/h_i，T_i＝TW_i/w_i，        B_i＝BW_i/w_i，LW_i、RW_i、TW_i、BW_i分别如步骤(2.3)所述；步骤(3.2)，建立约束关系：步骤(3.2.1)，模块间的几何位置约束为：其中：分别为位于模块i左边的的左下角横坐标、宽度以及最终分配给右边框的空白区宽度，分别为位于模块i下边的的左下角纵坐标、高度和最终分配的给上边框的空白区高度，x_i、y_i、l_i、b_i分别为模块i的左下角横坐标、左下角纵坐标、最终分配给左边框的空白区宽度以及最终分配给下边框的空白区高度；步骤(3.2.2)，芯片的面积约束为：x_i≥l_i，y_i≥b_i，x_i+w_i+r_i≤W，y_i+h_i+t_i≤H，其中：W为芯片的宽，H为芯片的高；步骤(4)，利用最小代价流算法将所述输入输出缓冲器插入到新得到的空白区中，并使芯片上的线长最短，步骤如下：步骤(4.1)，为一个所述输入输出缓冲器定义一个矩形的可放置区域，以便从其可放置区域内部选择一个空白矩形块来放置所述的这个输入输出缓冲器；步骤(4.2)，设置所述输入输出缓冲器的可放置区域的大小：使用输入输出缓冲器所对应的线网边框作为其可放置区域的初始值，为了保证每一个输入输出缓冲器都至少有一个供其放置的空白矩形块，需要将其可放置区域扩大至包含给定数目的阈值为10的空白矩形块，并把空白矩形块的一部分面积留给电源缓冲器；步骤(4.3)，建立缓冲器插入的网络流模型的最小代价流模型：网络流模型中，除了源点和汇点之外，其他的节点表示输入输出缓冲器和空白矩形块，从源点到每一个输入输出缓冲器节点都有一条边，相应的，从每一个空白矩形块节点到汇点也都有一条边，从源点到输入输出缓冲器节点的边的容量设置为1，代价设置为0，假设A_g是空白矩形块g的面积，考虑到芯片上的电源信号比，则从空白矩形块g节点到汇点的边的容量Φ_g设置为：Φ_g＝A_g/(Abuf_k×(1+1/R^SPG))其代价设置为0，如果输入输出缓冲器节点k到空白矩形块节点g之间存在边，则表示空白矩形块g在输入输出缓冲器k的可放置区域中，这些边的容量设置为1，代价为当将输入输出缓冲器k放置到空白矩形块g的中心位置时，输入输出缓冲器i所对应的线网半周长；步骤(4.4)，求解缓冲器插入的网络流模型的最小代价流模型：用压入与重标记方法求解最小代价流模型，找到满足容量约束的从源点到所要插入的输入输出缓冲器再到空白矩形块最后到汇点的最小代价流，就找到了该输入输出缓冲器的插入方案，就知道了将每一个输入输出缓冲器分配到了哪一个空白矩形块中；步骤(4.5)，放置输入输出缓冲器：为了将输入输出缓冲器插入到空白矩形块中的具体位置，将空白矩形块划分成一个个小格子，每一个小格子的面积等于输入输出缓冲器的面积，然后将输入输出缓冲器顺序放入这些小格子中，输入输出缓冲器的具体位置在详细布局阶段做进一步的优化；步骤(5)，利用最小代价流算法求解封装凸点的信号分配问题，使其封装线长最短：在将输入输出缓冲器分配到空白矩形块之后，需要将输入输出缓冲器分配到封装凸点上去，对封装凸点进行信号分配，为了使封装线长最短，需要将输入输出缓冲器分配给其附近的封装凸点，故将封装凸点的信号分配问题形式化为凸点信号分配的网络流模型，步骤如下：步骤(5.1)，定义输入输出缓冲器的可分配区域：输入输出缓冲器的可分配区域是一个矩形区域，从可分配区域内部选择一个封装凸点分配给这个输入输出缓冲器；步骤(5.2)，设置输入输出缓冲器的可分配区域的大小：首先为输入输出缓冲器的可分配区域设置一个初始值，为了保证每一个输入输出缓冲器都至少有一个供其分配的的封装凸点，将其可分配区域扩大至包含给定数目的封装凸点；步骤(5.3)，建立封装凸点的信号分配网络流模型：网络流模型中，除了源点和汇点之外，其他的节点表示输入输出缓冲器和封装凸点，从源点到每一个输入输出缓冲器节点有一条边，从每一个封装凸点节点到汇点也有一条边，由于一个输入输出缓冲器只能分配给一个封装凸点，而一个封装凸点也只能分配一个输入输出缓冲器，故这些边的容量设置为1，代价设置为0，如果输入输出缓冲器节点k到封装凸点节点q之间存在边，则表示封装凸点q在输入输出缓冲器k的可分配区域中，这些边的容量设置为1，代价为输入输出缓冲器k和封装凸点q之间的距离；步骤(5.4)求解凸点信号分配的网络流模型的最小代价流模型：通过压入与重标记方法求解最小代价流模型，找到满足容量约束的从源点到输入输出缓冲器再到封装凸点最后到汇点的最小代价流，就找到了封装凸点的信号分配方案；步骤(5.5)，为封装凸点分配信号：根据步骤(5.4)中得到的分配方案，将输入输出缓冲器分配给指定的封装凸点，每一个输入输出缓冲器都会被分配给一个封装凸点，但封装凸点的数目会多于输入输出缓冲器的数目，存留一些空白封装凸点，备用。