| 主权项 |
针对电路仿真的自适应并行LU分解方法，其特征在于，是在计算机上按照以下步骤实现的：步骤(1)，输入要仿真的电路的网单；步骤(2)，建立所要仿真的电路的n×n的电路稀疏矩阵，包括：add20，circuit_1，circuit_2，add32，rajat03，coupled，circuit_3，onetone1，onetone2，ckt11752_dc_1，circuit_4，ASIC_100ks，ASIC_100k，hcircuit，dc1，trans4，twotone，G2_circuit，transient，mac_econ_fwd500，Raj1，ASIC_320ks，ASIC_320k，mc2depi，rajat30，pre2，ASIC_680ks，ASIC_680k，Hamrle3，G3_circuit，memchip，Freescale1，circuit5M_dc，rajat31，circuit5M中的任何一个n×n的电路稀疏矩阵，称为矩阵A；步骤(3)，对所述矩阵A用J.R.Gilbert提出的“Predicting structure in sparsematrix computations”“稀疏矩阵计算中的结构预测”中所述的方法进行静态符号分解，得到下三角矩阵L和上三角矩阵U的符号结构，并统计二者的非零元总和NNZS，同时统计矩阵A中的非零元个数NNZA，A＝LU；步骤(4)，按下式判断，对所述矩阵A，适合于串行分解还是并行分解：若：α＜ζ，则适合于串行分解，若：α≥ζ，则适合于并行分解，其中，α＝NNZS/NNZA，ζ在1.5到2之间取值；步骤(5)，根据步骤(4)的结果，若所述矩阵A适合于串行分解，则对所述矩阵A使用向左看方法进行LU分解，其步骤如下：对于所述矩阵A的第k列：k＝1，2，…，n，采用T.A.Davis和E.P.Natarajan提出的“KLU，a direct sparse solver for circuit simulation problems”“KLU，用于电路仿真的直接稀疏求解器”中的串行向左看方法进行LU分解，依次进行符号预测，数值积累和部分选主元，然后依次对k＝1，2，…，n循环执行所述方法，以完成对所述矩阵A的LU分解；步骤(6)，根据步骤(4)的结果，若所述矩阵A适合于并行分解，则按以下步骤对所述矩阵A进行并行LU分解：步骤(6.1)，建立消去树，其步骤如下：步骤(6.1.1)，使所述消去树中的节点i对应于所述矩阵A中的第i列，步骤(6.1.2)，把节点i指向另一个节点j的有向边也称为消去树中的边，用i→j表示，称节点i是节点j的孩子节点，节点j是节点i的父亲节点，没有任何孩子节点的节点称为叶子节点，所述消去树中的边必须同时满足如下需求：a.若：节点j是节点i的父亲节点，则所述消去树中只存在一条由节点i指向节点j的边i→j，b.若：节点j对应的行号用j’表示，节点i对应的行号用i’表示，在所述矩阵A中，若第j’行、第i列的值A(j’，i)≠0或所述矩阵A中第i’行、第j列的值A(i’，j)≠0，那么所述消去树中存在且只存在一条边i→j，步骤(6.2)，对所述消去树中所述的各节点j分层，并把节点j所在的层记为level(j)：对于叶子节点，定义各叶子节点所在的层号为0，对于非叶子节点，定义节点j所处的层号等于level(j)＝max(level(i1)，…，level(ic)，…，level(iC))+1，其中：ic为节点j的一个孩子节点，c＝1，2，…，C，C为节点j的孩子节点的总数，level(ic)表示所述节点j的一个孩子节点ic的所处的层号，max(level(i1)，…，level(ic)，…，level(iC))表示各节点ic的所在层号中取最大值，把同一层号上的节点归在一起，获得调度器，步骤(6.3)，按以下方式确定所述调度器中各层所采用的并行方法：设定：调度阈值Nth，Nth在1到20之间取值，则：所述调度器中凡是层号上的节点数目大于Nth，使用“群”并行方法，层号上节点数目小于等于Nth的，用“流水线”并行方法，步骤(6.4)，所述“群”并行方法，按以下步骤对所述调度器的各层号逐层进行处理：把每一层上的所有节点，尽量平均分配给所设定的各个线程，所述各个线程同时按照带有部分选主元的串行的向左看LU分解方法按照符号预测、数值积累和部分选主元三个步骤依次进行，直到这一层上的所有节点都计算完毕，再用同样方法计算下一层，直到属于所述“群”并行方法要处理的层号都处理完成为止，步骤(6.5)，所述流水线并行方法，依次按以下步骤进行：步骤(6.5.1)，给各层的每个节点分配一个标志，初始状态下所有标志都是“未完成”，计算完毕后标志变成“完成”，步骤(6.5.2)，每个线程每次获取一个未完成的列号，记为k，步骤(6.5.3)，预分解：先执行所述符号预测，得到一个第k列的依赖列号的不完全集合，所述依赖列号是指进行第k列数值积累时要用到的第m列的数值结果，m＜k，对所述依赖依赖列号的不完全集合中的每一个列号m，进行数值积累运算，直到节点k在消去树中的所有孩子节点都完成为止，步骤(6.5.4)，后分解：首先进行一次完整的所述符号预测，以决定所述下三角矩阵L和所述上三角矩阵U的第k列的符号结构，其次，使用那些第k列所依赖的、在预分解中还未对所述第k列进行数值积累的列号进行数值积累运算，最后，进行所述部分选主元，并把所述第k列的标志为“完成”，步骤(6.5.5)，重复执行步骤(6.5.2)、步骤(6.5.3)、步骤(6.5.4)直到所有列的标志都变成“完成”为止；步骤(7)，回代求解：求解两个三角方程Ly＝b和Ux＝y，从而获得解x。 |
