系统级封装中总线在双边多绕道约束下的解绕方法

摘要

系统级封装中总线在双边多绕约束下的解绕方法，其特征在于，按从左到右总线信号顺序，对于总线中每一条连线，从预定义连接模式中选择合适模式实现互连，并通过后期检测，在可行情况下采用优化模式代替原有连接模式，达到以较少的绕道实现互连解绕。

主权项

系统级封装中总线在双边多绕约束下的解绕方法，其特征在于，它是在计算机中依次按照以下步骤实现的：步骤(1)，初始化，设顶部焊点序列为(a₁’,a₂’,a₃’.......a_n’)，底部焊点序列为(b₁’,b₂’,b₃’,.....b_n’)，输入：所有顶部焊点上需要解绕互连的总线信号组成的顶部总线信号序列(a₁,a₂,a₃.......a_n)，n为顶部总线信号个数，与顶部焊点个数相同，(a₁,a₂,a₃.......a_n)是由自然数序列{1，2，3，4，……，n}生成的一个排列,信号a_i＝k,i∈[1，n],k∈[1，n],表示顶部信号k在顶部焊点a_i’上；所有底部焊点上需要解绕的相应总线信号组成的底部信号序列(b₁,b₂,b₃,.....b_n)，n为底部总线信号个数，与所述顶部总线信号个数n在数值上相等，(b₁,b₂,b₃,.....b_n)也是由同一个自然数序列{1，2，3，4，…n}生成的一个排列,信号b_j＝k,j∈[1，n],k∈[1，n],表示底部信号k在底部焊点b_j’上；初始时,所述顶部总线信号序列(a₁,a₂,a₃.......a_n)与底部总线信号序列(b₁,b₂,b₃,.....b_n)中,顶部信号a_i与底部信号b_j的互连表示为a_i＝k,b_j＝k，其中i∈[1，n],j∈[1，n],k∈[1，n]；步骤(2)，按以下方法对总线信号进行重命名：对底部总线信号序列(b₁,b₂,b₃,…..b_n)中的每一个信号b_j，j∈[1，n]，重命名b_j以及与bj互连的对应的顶部信号a_i,使ai＝j,bj＝j；结果使底部信号序列为(b₁,b₂,b₃,.....b_n)＝(1、2、3、......n)，顶部信号序列(a₁,a₂,a₃.......a_n)为序列(1、2、3、......n)的一个新生成序列；以a_x代表当前顶部最左边第一个未连接的总线信号，以b_y代表底部左边第一个没有连接的总线信号,以u代表全部没有连接的信号对个数，x，y初始值为1，U初始值为n；步骤(3)，对每一个底部信号b_y，y∈[1，n]，把与其相连接的顶部信号a_x所在的顶部焊点序列的相对位置表示为T[y]，即a_T[y]与b_y相连，对于每一个顶部信号a_i,i∈[1，n],设置T[a_i]＝i，得到T[1]，T[2]，T[3]，......T[n]；步骤(4)，计算与顶部左边第一个信号a_x相连的底部信号b_ax左边当连接的总线信号个数p＝a_x‑y+1，包函b_ax；计算与底部左边第一个信号b_y相连顶部信号a_by的左边当前未连接的总线信号个数q＝T[y]‑x+1，包函a_by；步骤(5)，定义连接模式：步骤(5.1)，straight(a_x,b_y)模式：顶部总线信号a_x与底部总线信号b_y直接相连；步骤(5.2)，down‑left(b_ax,b_y,a_x)模式：连接线从底部总线信号b_ax出发，绕道底部信号b_ax与底部信号by之间的所有已经连接信号，然后穿过底部信号b_y,b_y‑1之间通道，然后与顶部信号a_x相连；步骤(5.3)，up‑right(a_x,a_c,b_ax)模式中，连接线从顶部总线信号ax出发，绕过顶部信号a_x与a_c之间所有已经连接信号，然后穿过顶部信号a_c,a_c+1之间，再与底部信号b_ax相连，其中a_c,b_ax分别是当前最右边未连接的顶部，底部总线信号；步骤(5.4)，up‑left(a_ty,a_x,b_y)模式：连接线从顶部总线信号aty出发，绕道顶部信号a_ty与顶部a_x之间所有已经连接的信号，穿过顶部信号a_x‑1,a_x之间，然后与底部信号b_y相连；步骤(5.5)，down‑right(b_y,b_c,a_ty)模式，连接线从底部总线信号by出发，绕道底部信号b_y与b_c之间所有已经连接的信号，穿过底部信号b_c,b_c+1之间，然后与顶部信号a_ty相连，其中a_ty,b_c分别是最右边没有连接的顶部和底部总线信号；步骤(5.6)，右框“[”连接模式：“[”(a_ty,a_c1,b_d1,b_y)连接模式指连线从顶部总线信号a_ty出发，经顶部信号a_c1与a_c1‑1之间通道和底部信号b_d1与b_d1‑1之间通道，与底部总线信号b_y相连接，绕道数为1；步骤(6)，根据p，q，u的大小关系，选择连接模式；步骤(6.1)，如果p＝q＝1,选择straight(a_x,b_y)模式连接a_x与b_y；步骤(6.2)，如果u>p>q；选择down‑left(b_ax,b_y,a_x)模式连接b_ax与a_x；步骤(6.3)，如果u＝p>q,选择down‑left(b_ax,b_y,a_x)模式连接或up‑right(a_x,a_c,b_ax)模式连接中绕道较少的模式连接b_ax与a_x；步骤(6.4),如果u>q>p,选择up‑left(a_ty,a_x,b_y)模式连接by与a_ty；步骤(6.5)，如果p<q＝u,选择up‑left(a_ty,a_x,b_y)连接模式或down‑right(b_y,b_c,a_ty)连接模式中绕道较少的模式连接by与a_ty；步骤(6.6)，如果p＝q<u,选择up‑left(a_ty,a_x,b_y)模式连接b_y与a_ty或选择down‑left(b_ax,b_y,a_x)模式连接a_x与b_ax；步骤(6.7)，如果p＝q＝u,选择up‑left(a_ty,a_x,b_y)或down‑right(b_y,b_c,a_ty)连接b_y与a_ty,选择up‑right(a_x,a_c,b_ax)或down‑left(b_ax,b_y,a_x)模式连接a_x与b_ax；步骤(7)，以右框“[”连接模式优化连接绕道数：对所有连接为down‑left(b_ax,b_y,a_ax)或up‑left(a_ty,a_x,b_y)连接模式且绕道数大于1的连接，如果以右框“[”模式代替以减少绕道数目，则用“[”模式代替原连接模式，当前连接模式为up‑left(a_ty,a_x,b_y)时，优化方法如下：设顶部总线信号a_x与a_ty之间的信号编号最小的已经连接的顶部总线信号为a_min＝k，则与a_min相连的底部总线信号为ba_min＝b_k，a_min与b_k的连接中连线从a_min出发，通过a_q与a_q‑1之间的通道与b_k相连，如果以下三个条件能够同时满足，则采用右框“[”模式优化互连结果：(1)顶部总线信号a_min与底部总线信号b_k的连接模式为up‑left(a_ty,a_q,b_k)且其中的绕道数为1；(2)从底部信号b_k到当前信号b_y之间的所有信号，与其互连的对应顶部信号全部在信号a_q与a_ty之间；(3)从顶部信号a_q到当前信号a_x之间的所有信号，与其互连的对应底部信号全部在信号b_k与b_y之间；如果以上三个条件同时成立，则可以用右框“[”(a_ty,a_q,b_k,b_y)模式优化连接，即连线从顶部信号a_ty出发，经过顶部信号a_q与a_q‑1之间通道和底部信号b_k与b_k‑1之间通道，与底部信号b_y实现互连；对于连接模式为down‑left(b_ax,b_y,a_ax)，按相同的方法优化；更新x,y，重新计算p,q,u值，重复步骤(4)‑步骤(6)，直到全部的总线信号连接完成。