用于分布式稀疏线性系统中改进的并行ilu分解的系统和方法

xiaoxiao2020-08-01  5

专利名称:用于分布式稀疏线性系统中改进的并行ilu分解的系统和方法
技术领域
本发明大体涉及用于分布式稀疏线性系统的并行ILU分解。更为具体地,本发明涉及一种用于在分布稀疏线性系统中求解系统之前,使用并行ILU分解预条件算子对方程的基本节点进行排序的方法。
背景技术
许多类型的物理过程,包括石油油藏内的流体流动,是由偏微分方程控制的。通常使用有限差、有限体积或者有限元方法来求解这些可能非常复杂的偏微分方程。所有这些方法将物理模型划分为被称为网格块、单元格或者元素的单元。在这些物理单元的每一个中,通过一个或更多的求解变量或未知量给出解。与每个物理单元相关的是一组用于控制这些未知量的特性的方程,方程的数量等于未知量的数量。这些方程还包含来自相邻的物理单元的未知量。因此,方程存在结构,同时,给定物理单元的方程含有来自该物理单元和来自相邻物理单元的未知量。最合宜地,使用节点和连接的组合对其进行描绘,其中节点是由小圆圈描绘的,而连接是由两个节点之间的线条描绘的。节点处的方程含有该节点处的未知量和连接至其上的相邻节点处的未知量。所有节点处的方程集合成单个的矩阵方程。通常,获得所期望的偏微分方程的解的关键任务是求解该矩阵方程。实现该任务的最有效的方式之一是通过使用不完全LU分解法或者ILU,其中原始矩阵被近似分解为两个矩阵L和U的乘积。矩阵L和U为下三角矩阵和上三角矩阵而且分别具有与原始矩阵的下部和上部类似的非零结构。使用这种分解, 通过前向和后向替换迭代地获得了解。一直存在对获得更好的求解准确性的需求。实现该需求的一种方式是将物理模型划分成更小的物理单元,或者换句话讲,使用更多的节点,可能是百万计数量的节点。当然, 为完成其而所需进行的计算的时间增加了。避免这种时间增加的一种方式是在多个处理器上以并行方式执行计算。存在两种类型的并行式计算机,即使用共享式内存和使用分布式内存的计算机。 共享式内存计算机只使用少量的处理器,其限制了可能的运行时间减少。常见的是使用数十个处理器的分布式内存计算机,但是也存在一些使用数千个处理器的分布式内存计算机。期望使用分布式内存并行处理。当使用分布式内存时,通过将物理模型划分成域而使计算并行化,同时,域的数量等于同时使用的处理器的数量。每个域被分配给一个特定的处理器,其执行与该域相关的计算。每个域包含特定的节点组,且每个节点设置在域内。整个建模过程涉及很多计算,几乎所有的计算都是逐个节点进行的。节点处的一些这样的计算只需要节点的本地信息。当信息被完全包含在与节点相同的域内时,该信息对于节点是本地的。这种计算有时被称作密集并行,因为它们不需要为了并行实施而执行特殊处理。其它的计算需要节点处和其相邻节点处的信息。如果节点在自己的域与另一个域的边界上,其一个或更多的相邻节点将位于另一个域内。为了实施需要边界节点处相邻信息的计算,必须从这些相邻节点所属的域内获得关于这些相邻节点的信息。如果所需的信息事先已知,其可以容易地通过“消息传递”获得,而且该计算易于并行进行。重要的是信息事先要已知,这是因为消息的传递将花费时间。具体地,与通常的计算时间相比,存在一个较长的延迟;换句话讲,消息的第一元素需要花费有限的时间到达其接受方。如果该信息是事先已知的,在另一个处理需要该信息之前,含有该信息的消息能够被发送。以这种方式,在需要该信息之前,其已经到达另一个处理。遗憾的是,在分解计算中,所需的信息事先是不知道的。正相反,其是在分解期间产生的。计算是具有“固有顺序”的。计算的一般流程如下1、以在其已被分解的相邻节点处实施的计算为基础,更新当前的节点方程。2、在当前节点处对所得到的修改过的方程进行分解。3、将与当前节点的分解相关的信息提供给其还未被分解的相邻节点。“相邻节点”不必为最接近的节点。它们可以是在几个节点之外的节点。如果只存在一个域,这些计算的顺序性就不成问题。如果存在多于一个的域,这些计算的顺序性将成为问题。信息必须从一个处理发送到另一个处理。如果直到其马上要被另一个处理需要之前才知道该信息,则当含有该信息的消息被发送时,存在一个延迟。如果对计算进行排序使得任何将发送到另一个处理的信息在其被该处理需要之前是充分已知的,则可以避免这些延迟。进一步考虑这一点,假设有两个域。每个域具有内部节点和边界节点,该内部节点只与在同一域内的节点通信,并且该边界节点与两个域内的节点都通信。可按下面的顺序进行处理1、处理域1中的内部节点。2、处理域1中的边界节点。3、从域1发送边界节点信息至域2。4、处理域2中的边界节点。5、处理域2中的内部节点。如果使用这一顺序,直到域1全部结束,域2才能开始其处理。根本不存在并行化计算。如下是一个更好的处理顺序1、以并行方式处理域1中的内部节点和域2中的内部节点。2、处理域1中的边界节点。3、从域1发送边界节点信息至域2。4、处理域2中的边界节点。使用这一顺序,内部节点的计算是并行实施的。这是意义重大的,因为内部节点多于边界节点。但是,边界节点仍是按顺序处理的。一般地,全部节点的20%-40%为边界节
点ο存在相当多的用于ILU分解的并行算法。2003年,工业与应用数学协会,Yousef Saad编写("Saad")的“用于稀疏线性系统的迭代方法(第二版)(Iterative Methodsfor Sparse Linear Systems (second edition)) ”一书中介绍了两种算法。其中之一是四5 页-392页描述的多级筛选算法,该算法利用了稀疏线性系统中存在的独立集的优势。然而该算法可能不适用于分布式数据结构。396页-399页描述的第二种算法是在每个处理器上同时对内部节点进行分解,然后以某种顺序处理边界节点。该第二种算法的缺点是当等待来自其它处理器的数据时,一些处理器保持闲置。George Karypis和Vipin Kumar于1998 年刊载在技术报告(Technical R印ort) #96-061上的“基于平行阈值的ILU分解(Parallel Threshold-based ILU factorization) ”中描述了第三种算法,除了对边界节点着色然后对每种颜色的节点进行分解之外,其类似于第二种算法。然而,其可能需要一些颜色。由于需要更多的颜色,必须在处理器之间传递更多的消息,因此通常消弱了求解器的总体性能。因此,存在对于改进的并行ILU分解算法的需求,该算法应能适用于分布式稀疏线性系统并且减少处理时间。

发明内容
本发明通过提供用于分布式稀疏线性系统中并行ILU分解的系统和方法,满足了上述需求并克服了现有技术中的一个或更多缺陷,该系统和方法采用了对系统内方程的基本节点排序的独特方法并且减少了处理时间。在一个实施例中,本发明包含用于对分布式稀疏线性系统中方程的多个基本节点进行排序的方法,其包括i)指定不具有跨越分区界面的连接的节点为内部节点;ii)指定具有跨越分区界面的连接的节点为边界节点;iii)指定不多于三个的代码,以区分边界节点;和iv)通过a)分配第一代码至每个代表第一边界节点的边界节点,其中每个第一边界节点连接不能跨越分区界面以连接两个第一边界节点;b)分配第二代码至每个代表第二边界节点的边界节点,其中每个第二边界节点连接不能跨越分区界面以连接两个第二边界节点;和c)分配第三代码至每个代表第三边界节点的边界节点,其中每个第三边界节点连接不能跨越分区界面以连接一个内部节点;在计算机系统上处理每个边界节点。在另一个实施例中,本发明包含用于携载用于在分布式稀疏线性系统中对方程的多个基本节点进行排序的计算机可执行指令的程序载体装置。所述指令是可执行的,用于实施i)指定不具有跨越分区界面的连接的节点为内部节点;ii)指定具有跨越分区界面的连接的节点为边界节点;iii)指定不多于三个的代码,以区分所述边界节点;iv)分配第一代码至每个代表第一边界节点的边界节点,其中每个第一边界节点连接不能跨越分区界面以连接两个第一边界节点;ν)分配第二代码至每个代表第二边界节点的边界节点,其中每个第二边界节点连接不能跨越分区界面以连接两个第二边界节点;和Vi)分配第三代码至每个代表第三边界节点的边界节点,其中每个第三边界节点连接不能跨越分区界面以连接一个内部节点。从下面对不同实施例的描述和有关附图中,本发明的其它方面、优势和实施例对于本领域技术人员来说会变得显而易见。


下面参考所附附图对本发明进行描述,其中同样的元素引用同样的附图标记,并且其中
图1为例示了用于实施本发明的系统的框图。图2A为例示了用于实施本发明的方法的一个实施例的流程图。图2B为图2A中所例示的方法的延续。图2C为图2B中所例示的方法的延续。图2D为图2C中所例示的方法的延续。图2E为图2D中所例示的方法的延续。图2F为图2E中所例示的方法的延续。图2G为图2F中所例示的方法的延续。图2H为图2B中所例示的方法的延续。图3为图2E中所例示的方法的延续。图4为图3中所例示的方法的延续。图5例示了域分解的实例。图6A和6B例示了为常规边界节点着色的实例。图7A、7B和7C例示了为超级边界节点着色的实例。图8例示了不完全分解的实例。
具体实施例虽然特定地描述了本发明的主题,但是说明书本身并不用于限制本发明的范围。 因此所述主题也可用其它方式实施,从而以与其它当前或将来的技术相结合的方式,包括不同的步骤或与此处所描述的步骤类似的步骤的组合。而且尽管术语“步骤”在此处可用于描述所使用方法的不同元素,所述术语不应解释为暗示在此处所公开的不同步骤之中或之间的任何具体顺序,除非说明书明确地将其限定为具体顺序。系统说明本发明可通过计算机可执行指令程序实施,例如程序模块,一般指的是由计算机执行的软件应用或应用程序。软件可包括,例如例程、程序、对象、组件和执行具体任务或实施具体的抽象数据类型的数据结构。软件形成了容许计算机根据输入源作出反应的界面。 NEXUS 是由兰德马克制图(Landmark Graphiscs)公司销售的商业软件应用,其可作为界面应用来实施本发明。所述软件也可与其它代码区段合作以启动各种任务,以对与接收到的数据源一同被接收的数据做出响应。软件也可存储和/或携载在任何种类的存储介质上,例如CD-ROM、磁盘、磁泡存储器和半导体内存(例如,各种类型的RAM或ROM)。另外,软件和其结果可以在各种载体介质上传输,例如光纤、金属导线和可用空间,和/或通过各种网络中的任何一种传输,例如因特网。而且,本领域技术人员会理解,可使用多种计算机系统配置实施本发明,包括手持装置、多重处理器系统、基于微处理器或用户可编程的电子设备、微型计算机和大型计算机等。任何数量的计算机系统和计算机网络都可被接受与本发明一起使用。本发明也可在分布式计算环境中实施,其中任务是通过由通信网络连接的远程处理装置完成的。在分布式计算环境中,程序模块可位于包含存储装置的本地和远程计算机存储介质两者内。因此,本发明可以与计算机系统或其它处理系统中的各种硬件、软件或其组合相关联实施。现在参照图1,例示出一种用于在计算机上实施本发明的系统的框图。该系统包括计算单元,有时称为计算系统,其包括存储器、应用程序、用户界面和处理单元。计算单元只是适用的计算环境的一个实例,并不用于提出对本发明的使用范围或功能性的任何限制。存储器主要存储应用程序,其也可被描述为含有计算机可执行指令的程序模块, 该指令由用于实施此处所描述的和图2A-4所例示的方法的计算单元执行。因此,该存储器含有ILU分解模块,该模块能实施参照图2A-4所描述和例示的方法,以及NEXUS 。尽管计算单元被示出为具有广义存储器,但计算单元通常包括各种计算机可读介质。举例来说但不受其限制的,计算机可读介质可包括计算机存储介质和通信介质。计算系统存储器可包括诸如只读存储器(ROM)和随机存取存储器(RAM)的易失性和/或非易失性存储器形式的计算机存储介质。基本输入/输出系统¢10 —般存储在ROM内,该基本输入/输出系统包含基本例程,其有助于例如在启动过程中在计算单元内的元件之间传递信息。RAM—般包含可以通过处理单元立即访问和/或由处理单元即刻操作的数据和/或程序模块。举例来说但不受其限制的,计算单元包括操作系统、应用程序、其它程序模块和程序数据。存储器中所示的组件也可包含在其它可移动/非可移动、易失性/非易失性计算机存储介质内。仅用于举例说明的,硬盘驱动器可从非可移动、非易失性磁介质读取或对其写入,磁盘驱动器可从可移动、非易失性磁盘读取或对其写入,并且光盘驱动器可从可移动、非易失性光盘(例如CD ROM或者其它光学介质)读取或对其写入。其它能够在示例性操作环境中使用的可移动/非可移动、易失性/非易失性计算机存储介质可包括但不限于 盒式磁带、闪存卡、数字通用盘、数字录像带、固态RAM、固态ROM等。因此,上面所讨论的驱动器和其相关的计算机存储介质存储和/或携载有计算机可读指令、数据结构、程序模块和其它用于计算单元的数据。用户可以通过用户界面将指令和信息输入计算单元,该用户界面可以是如键盘和定点装置的输入装置,通常指的是鼠标、轨迹球或触摸板。输入装置可以包括麦克风、控制杆、卫星天线和扫描仪等。通常,这些和其它的输入装置通过耦合至系统总线的用户接口与处理单元相连接,但其也可通过其它接口和总线结构连接,例如并行端口或者通用串行总线(USB)。监视器或者其它类型的显示装置可通过诸如视频接口的接口连接到系统总线。除了监视器之外,计算机也可包括其它外围输出装置,例如扬声器和打印机,其可通过输出外围接口连接。尽管计算单元的许多其它内部元件未示出,本领域普通技术人员会理解,这样的元件和其相互连接关系是公知的。方法说明现在参照图5,为了描述本发明将怎样利用并行处理(此处有时也称为并行计算) 来求解分布稀疏线性系统的目的,例示了域分解的一个实例。在图5中,二维网格化矩形模型500被分解为两个域(Ω1和Ω 2),其被虚线506分开。该实施例以使用包括实线和点的五点模板502的有限差或者有限体积的计算为基础,所得到的系数矩阵具有与图5中所示的模型500相同的连通性。然而,本发明也可适用于其它更复杂的实例,此处使用该实例是因为其简单性。对应于域Ω1和Ω2的线性方程分别被加载到处理器Pl和Ρ2。并行计算利用了这样的优势事实上一个域内的所有内部节点不与另一个域内的任何节点连接,这容许两个处理器同时处理其本地数据。边界节点504如空心圆所示,其应该可被两个处理器访问,但是仍然可以通过使用基于颜色的排序在它们之中实现并行计算。例如,如图6A和6B所示,为了获得更好的排序,可对常规边界节点着色。在图6A 和6B中,每个域分别由分区界面602和604分开。较浅的虚线代表同一域内节点之间的连接,因此每条实线代表跨域的连接。尽管术语“着色”在此处指的是将边界节点与内部节点区分并描述用于对节点进行排序的处理,但也可使用其它类型的编码作为替代来实现同样的目的。本发明采用以下的规则,该规则应用于图6A和6B中的节点1、1(内部)节点只能连接同一域内的节点;2、Cl节点不可连接不同域内的Cl节点;3、C2节点不可连接不同域内的C2节点;以及4、C3节点可以连接任何域内的任何颜色的节点。C3节点充当一个域和不同域内的Cl节点之间以及一个域和不同域内的C2节点之间的缓冲器。如果节点的连接性如图6A所示,则不需要该缓冲器,并且不存在C3节点。如果存在如图6B所示的对角线连接,则需要该缓冲器并且该缓冲器由示出的两个C3节点提{共。现在,可采用以下顺序计算(处理)节点1、以并行方式,将域1的C3信息发送到域2,并将域2的C3信息发送到域1。2、以并行方式,处理域1中的内部节点,接着处理域1中的Cl边界节点,以及处理域2中的内部节点,接着处理域2中的Cl边界节点。3、以并行方式,将域1的Cl边界节点信息发送到域2,将域2的Cl边界节点信息发送到域1,然后处理C3节点。4、以并行方式,处理域1中的C2边界节点和域2中的C2边界节点。通常,全部节点的大约-5%为C3节点。本发明将所有节点分成两类,即内部节点和边界节点。在所有处理器上同时处理内部节点,并且内部节点的计算在CPU时间中非常密集,因为内部节点通常比边界节点多。 传统方法不使用这一本地计算以覆盖处理器之间的任何通信,这是低效的。设计了一种新的着色算法,以利用这一内部节点中的本地计算来覆盖跨处理器的通信,并同时将边界节点的颜色的数量限定至三个。着色的基本原理是属于两个不同域的任何相邻节点不能具有除附属颜色C3之外的相同颜色,并且每一主要颜色(Cl和C2)必须在所有处理器上出现。在具有常规模板和合理的域分解的多数情况下,两种颜色是足够用于着色的。需要附属颜色C3来跨边界地转换主要颜色,从而实现基本着色原理的第二部分。在本发明中,通过最开始的消息传递,使得具有第三种颜色(O)的边界节点(如果有的话)可到达该边界的两侧,从而该通信可与内部节点的分解中的本地计算重叠。随着C3节点可到达分区的两边,分解与前向和后向替换程序与只有两个边界颜色的情况大致相同,即这些程序中的每一个只需要一个消息传递,并且该消息传递很容易与边界节点中的本地计算重叠。由此,有可能设计可扩展的并行ILU预条件算子。以下说明应用了上述规则并在三个主要阶段中处理节点i)着色;ii)分解;和 iii)求解。着色阶段确定了节点的顺序,其依次确定方程被分解的顺序和执行求解的顺序。一旦确定了着色,分解和求解将是程序化的,尽管其也许是复杂的。着色参照图2A-2H描述了用于执行着色阶段的方法的一个实施例。另外,参照图7A-7C 例示了对超级边界节点着色的实例。在图7A-7C中,连接到多个外部域的边界节点被定义为超级边界节点。所有其它边界节点称作常规边界节点。图6A、6B和7A-7C中的连接代表系数矩阵内的非零入口,其没必要与网格连接性相同,因为系数矩阵内的连接性取决于使用哪种模板进行偏微分方程的离散化。在这些图中,只有由实线表示的跨域连接为着色程序而考虑。虚线代表分离每个域的分区界面。现在参考图2A,方法200A为着色阶段的开端。在步骤202中,寻找将被用于确定节点颜色的所有连接(跨域连接)。只有这些连接被用于确定节点颜色。在步骤204中,识别不具有跨越域边界的连接的内部节点。在步骤206中,识别具有跨越域边界的连接的边界节点。在步骤208中,识别那些被连接到除了其所处的域之外的至少两个域的超级边界节点。在步骤210中,建立超级边界节点的连通性矩阵。在步骤212中,本领域所公知的多重着色贪心(greedy)算法适用于对超级边界节点着色。该着色的基本原理为不存在具有相同颜色的两个相连的节点。使用不同的种子节点运行若干次所述多重着色算法,以寻找颜色的最少数量。在步骤214中,确定颜色的数量是否大于三。在步骤216中,大于三的所有颜色被作为颜色3 (O)。由此,一些相邻的超级边界节点可具有相同的颜色,并且该颜色必须是C3,如图7B所示。对于合理的域分解,将存在非常有限数量的这样的颜色3与颜色3的(C3-C;3)连接。现在参考图2B,方法200B是用于执行着色阶段的方法200A的延续。在步骤216中,s等于分区界面的数量。在步骤218中,对于每个分区界面ρ (s),构建仅具有跨越ρ (s)的连接的连通性矩阵。在步骤220中,寻找先前使用颜色I(Cl)、颜色2 (C2)和颜色3 (C3)着色的所有节
点ο在步骤222中,如果存在Cl或C2,方法200B继续执行图2H中的步骤观4。如果不存在Cl或C2,步骤2M选择具有更多未着色节点的侧作为起始侧,并将此侧上的第一个未着色节点放置在ι-队列中。在步骤226中,Cl被分配给C1,作为起始侧上的起始颜色,并且C2被分配给(;。现在参照图2C,方法200C是用于执行着色阶段的方法200B的延续。在步骤228中,χ等于1-队列中节点的数量。在步骤228a中,确定节点i (χ)的相邻节点j。在步骤228b中,y等于节点i的相邻节点j的数量。在步骤230中,确定节点j(y)是否着色。如果j (y)已着色,则步骤232确定j (y)是否着色为C1。如果j(y)未着色,则将j着色为C,并在步骤23 中将其添加到r-队列。在步骤232中,如果j(y)已着色C1,则在步骤232b中将j (y)重新着色为C3,然后继续执行步骤234。如果j (y)未着色C1,则该方法继续执行步骤234。在步骤234中,确定y是否大于1。如果y不大于1,则i的所有相邻节点j (y)已被访问并且方法200C继续执行步骤236。如果在步骤234中y大于1,则i的一些相邻节点j (y)尚未被访问并且方法200C继续执行步骤23如。在步骤23 中,y等于y减1。该方法从步骤23 返回到步骤230。在步骤236中,将节点i(x)从1-队列中移除。在步骤238中,确定χ是否大于1。如果χ大于1,则1_队列不为空,并且步骤238a 设定X等于X减1。如果X不大于1,则1-队列为空并且方法200C继续至图2D。现在参考图2D,方法200D是用于执行着色阶段的方法200C的延续。在步骤MO中,m等于r-队列中的节点数量。在步骤MOa中,确定节点i (m)的相邻节点j。在步骤MOb中,η等于节点i的相邻节点j的数量。在步骤M2中,确定节点j (η)是否已着色。如果j(n)已着色,则步骤244确定 j (η)是否着色为Cr0如果j (η)未着色,则将j (η)着色为C1并在步骤244b中将其添加到 1-队列。在步骤M4中,如果j(n)着色为C,,则在步骤对如中将j(n)重新着色为C3,然后继续执行步骤对6。如果j (η)未着色为C,,则方法继续执行步骤236。在步骤246中,确定η是否大于1。如果η不大于1,则i (m)的所有相邻节点j (η) 已被访问并且方法200D继续执行步骤Μ8。如果步骤246中η大于1,则i (m)的一些相邻节点j (η)尚未被访问并且方法200D继续执行步骤M6a。在步骤中,η等于η减1。该方法从步骤返回到步骤M2。在步骤M8中,将节点i(m)从r-队列中移除。在步骤250中,确定m是否大于1。如果m大于1,则r_队列不为空,并且步骤250a 设定m等于m减1。如果m不大于1,则队列为空并且方法200D继续至图2E。现在参考图2E,方法200E是用于执行着色阶段的方法200D的延续。在步骤252中,确定着色节点的数量是否达到任一侧上节点总数的一半。如果已着色节点的数量等于任一侧上节点总数的一半,则该方法继续至图2F以交换颜色C1和(;。 如果已着色节点的数量不等于任一侧上节点总数的一半,则该方法继续至步骤254。在步骤邪4中,确定是否所有节点都已着色。如果所有节点都已着色,则该方法继续至步骤25如。如果还有一些节点没有着色,则该方法继续至步骤25如。在步骤25 中,确定s是否大于1。如果s不大于1,则所有界面已被访问并且该方法继续至图3中的步骤302。如果s大于1,则步骤254b设定s等于s减1并且该方法返回至图2B中的步骤218。在步骤25 中,确定1-队列是否为空。如果1-队列为空,则步骤256寻找起始侧上的第一个未着色节点,将其着色为C1,并放置在1-队列中,然后继续至图2C中的步骤 228。如果1-队列不为空,则该方法继续至图2C中的步骤228。现在参考图2F,方法200F是用于执行着色阶段的方法200E的延续。在着色过程中,当任一侧上已着色的节点数量达到了该侧上节点总数的一半时,必须交换颜色C1和(;。 在颜色可被交换之前,方法200F必须为这一切换首先确定是否有任何节点已被着色为颜色3。在步骤256a中,t等于1_队列中的节点数。在步骤258中,确定t是否大于1。如果t不大于1,则1_队列为空并且该方法继续至图2G中的步骤276。如果t大于1,则1-队列不为空;并且步骤260确定1-队列中节点i(t)的相邻节点j。在步骤262中,确定是否i (t)的所有相邻节点j都被着色为Cr0如果i (t)的所有相邻节点j都被着色为(;,则步骤274将节点i⑴从1-队列中移除。如果i⑴的一些相邻节点未被着色为(;,则步骤264设定ζ等于i (t)的相邻节点j的数量。在步骤沈6中,确定相邻节点j(z)是否已着色。如果j(z)已着色,则步骤确定j(z)是否被着色为Q。如果j(z)未被着色,则步骤270将j (ζ)放置在r-队列中而不着色。在步骤中,如果节点j(z)被着色为C1,则步骤268将i⑴重新着色为C3, 并且该方法继续至步骤274。如果节点j未被着色为C1,则该方法200F继续至步骤272。在步骤270中,j (ζ)被放置在r-队列中而不着色。在步骤272中,确定ζ是否大于1。如果ζ大于1,则一些相邻节点还未被访问且步骤27 设定ζ等于ζ减1。如果ζ不大于1,则所有相邻节点j (ζ)已被访问且方法200D 继续至步骤274。在步骤274中,将节点i(t)从1-队列中移除。在步骤27 中,t等于t减1,且该方法返回至步骤258。现在参照图2G,方法200G是用于执行着色阶段的方法200F的延续。在步骤274b中,u等于r-队列中的节点数。在步骤276中,确定r-队列是否为空。如果r_队列为空,则在步骤276a中交换颜色C1和C;且方法200G返回至图2E中的步骤254。如果r_队列不为空,则在步骤278中, 确定r-队列中节点i (u)的相邻节点j。在步骤观0中,确定是否所有相邻节点j都被着色为C1。如果一些相邻节点j未被着色为C1,则步骤^Oa将节点i (u)着色为C3。如果所有的相邻节点j都被着色为C1, 则步骤280b将节点i (u)着色为Cr0在步骤观2中,将节点i(u)从r-队列中移除。在步骤观加中,u等于u-1,然后该方法返回至步骤276。现在参照图2H,方法200H是用于执行着色阶段的方法200B的延续。在步骤观4中,对界面两侧上具有颜色Cl和C2的节点进行计数。在步骤观6中,将界面的任一侧上具有最多节点的颜色选为起始颜色,由C1表示。在步骤观8中,将具有最SC1节点的界面选为起始界面。在步骤四0中,将起始侧上的C1节点存储在名为1-队列的队列中。在步骤四2中,将区别于C1的颜色分配给C,。在步骤四4中,确定在与1-队列中的节点跨域连接的节点之中是否存在C,。如果在与1-队列中的节点跨域连接的节点之中存在(;,则在步骤四6中将那些C;节点存储在名为r-队列的队列中。如果在与1-队列中的节点跨域连接的节点之中不存在(;,则该方法继续执行方法200C中的步骤228。分解现在参照图3,方法300是用于执行分解阶段的方法200E的延续。方法300例示了根据本发明的不完全分解。下面的步骤以并行的方式在每个处理器上实施。在步骤302中,如果存在C3节点,则通过消息传递使得其方程可访问边界的两侧。 步骤302启动非阻塞式消息发送和接收。在步骤304中,所有本地内部节点通过ILU分解被近似地分解。存在若干个公知的ILU分解的变量,其可由&iad获得并在其中被描述。该步骤的CPU时间密集且应该容许来得及使步骤302中发出的消息到达其目的地。在步骤306中,Cl边界节点被分解。在步骤308中,下达以非阻塞方式发送和接收与Cl节点相关的上分解系数和与C3 节点相关的内部系数的命令。在步骤310中,使用来自本地内部节点的信息来更新C2节点。在步骤312中,当步骤302中的消息到达后,使用来自本地内部节点和Cl节点的信息来更新C3节点。在步骤314中,当步骤308中的消息到达后,C3和C2节点被分解。求解现在参照图4,方法400是用于通过前向和后向替换而执行求解阶段的方法300的延续,该前向和后向替换为本领域公知的技术。在步骤402中,如果存在C3节点,则启动其右手侧的消息传递。在步骤404中,对内部节点执行前向解法。在步骤406中,对Cl节点执行前向解法。在步骤408中,下达以非阻塞方式发送和接收Cl节点以及连接至C3节点的内部节点处的前向解的命令。在步骤410中,在本地内部和Cl解的基础上更新C2和C3节点。在步骤412中,当步骤408中的消息到达后,根据远程内部和Cl解更新C2和C3 节点。在步骤414中,对C3和C2节点执行前向解
在步骤416中,对C2节点执行后向解法。在步骤418中,下达以非阻塞方式发送和接收C2节点解的命令。在步骤420中,根据本地C2解更新C3和内部节点。在步骤422中,当步骤418中的消息到达后,根据远程C2解更新C3、Cl和内部节
点ο在步骤424中,对C3节点执行后向解法。在步骤426中,对Cl节点执行后向解法。在步骤428中,对内部节点执行后向解法。现在参照图8,其例示了用于两个处理器的重新排序矩阵的不完全分解和求解的实例。I和C分别代表内部节点和边界节点。在该图中可以容易地解释分解和求解两个步骤。在分解和前向替换中,处理器(PIA^)首先处理内部节点,然后处理Cl边界节点,最后处理C2/C3边界节点。在后向替换中,两个处理器首先求解C2边界节点,然后求解C3、Cl 和I节点。在分解和前向替换中对Cl边界节点进行处理之后,或者在后向替换中对C2边界节点进行处理之后,开始消息传递。在进行分解和前向替换之前,任何关于C3边界节点的信息(如果存在的话)在两个处理器之间交换。尽管已经结合当前的优选实施例描述了本发明,本领域技术人员会理解,本发明并不限于这些实施例。例如,本发明不局限于石油或者燃气工业并且可广泛地应用在需要求解一般线性系统的许多领域中。这样的应用包括但不限于,现场可编程门阵列(FPGA)和其它类型的电子电路模拟。因此,预期到在不背离由所附权利要求书和其等同内容所限定的本发明的主旨和范围的情况下可对所公开的实施例做出各种替代的实施方式和修改。相关申请的交叉引用在此要求于2008年11月12日提交的12/269,6M号美国非临时专利申请的优先权,并且其说明书通过引用的方式并入于此。关于联邦资助研究的声明不适用。
权利要求
1.一种用于在分布式稀疏线性系统中对方程的多个基本节点进行排序的方法,其包括将不具有跨越分区界面的连接的节点指定为内部节点; 将具有跨越分区界面的连接的节点指定为边界节点; 指定不多于三个的代码,以区分所述边界节点; 通过将第一代码分配给每一代表第一边界节点的边界节点,其中每一第一边界节点连接不能跨越分区界面以连接两个第一边界节点;将第二代码分配给每一代表第二边界节点的边界节点,其中每一第二边界节点连接不能跨越分区界面以连接两个第二边界节点;以及将第三代码分配给每一代表第三边界节点的边界节点,其中每一第三边界节点连接不能跨越分区界面以连接一个内部节点,在计算机系统上处理每一所述边界节点。
2.如权利要求1所述的方法,其中每一第三边界节点连接能够连接两个第三边界节点,一个第三边界节点和一个第二边界节点,或者一个第三边界节点和一个第一边界节点。
3.如权利要求1所述的方法,其中每一分区界面分隔多个域。
4.如权利要求3所述的方法,其中每一域包括一组边界节点和一组内部节点。
5.如权利要求3所述的方法,还包括将与域内的每一第三边界节点相关联的信息传送至另一域;将与所述另一域内的每一第三边界节点相关联的信息传送至所述域;以及并行执行每一传送步骤。
6.如权利要求5所述的方法,还包括处理所述域内的每一内部节点,随后处理所述域内的每一第一边界节点; 处理所述另一域内的每一内部节点,随后处理所述另一域内的每一第一边界节点;以及并行执行每一处理步骤。
7.如权利要求6所述的方法,还包括将与所述域内的每一第一边界节点相关联的信息传送至所述另一域; 将与所述另一域内的每一第一边界节点相关联的信息传送至所述域;以及并行执行每一传送步骤。
8.如权利要求7所述的方法,还包括 处理所述域内的每一第二边界节点;处理所述另一域内的每一第二边界节点;以及并行执行每一处理步骤。
9.如权利要求1所述的方法,其中每一代码为不同的颜色。
10.如权利要求1所述的方法,其中每一内部节点连接只连接在单独域内的节点。
11.一种用于携载用于在分布式稀疏线性系统中对方程的多个基本节点进行排序的计算机可执行指令的程序载体装置,其包括将不具有跨越分区界面的连接的节点指定为内部节点; 将具有跨越分区界面的连接的节点指定为边界节点;指定不多于三个的代码,以区分所述边界节点;将第一代码分配给每一代表第一边界节点的边界节点,其中每一第一边界节点连接不能跨越分区界面以连接两个第一边界节点;将第二代码分配给每一代表第二边界节点的边界节点,其中每一第二边界节点连接不能跨越分区界面以连接两个第二边界节点;将第三代码分配给每一代表第三边界节点的边界节点,其中每一第三边界节点连接不能跨越分区界面以连接一个内部节点。
12.如权利要求11所述的程序载体装置,其中每一第三边界节点连接能够连接两个第三边界节点,一个第三边界节点和一个第二边界节点,或者一个第三边界节点和一个第一边界节点。
13.如权利要求11所述的程序载体装置,其中每一分区界面分隔多个域。
14.如权利要求13所述的程序载体装置,其中每一域包括一组边界节点和一组内部节点ο
15.如权利要求13所述的程序载体装置,还包括将与域内的每一第三边界节点相关联的信息传送至另一域;将与所述另一域内的每一第三边界节点相关联的信息传送至所述域;以及并行执行每一传送步骤。
16.如权利要求15所述的程序载体装置,还包括处理所述域内的每一内部节点,随后处理所述域内的每一第一边界节点; 处理所述另一域内的每一内部节点,随后处理所述另一域内的每一第一边界节点;以及并行执行每一处理步骤。
17.如权利要求16所述的程序载体装置,还包括将与所述域内的每一第一边界节点相关联的信息传送至所述另一域; 将与所述另一域内的每一第一边界节点相关联的信息传送至所述域;以及并行执行每一传送步骤。
18.如权利要求17所述的程序载体装置,还包括 处理所述域内的每一第二边界节点;处理所述另一域内的每一第二边界节点;以及并行执行每一处理步骤。
19.如权利要求11所述的程序载体装置,其中每一代码为不同的颜色。
20.如权利要求11所述的程序载体装置,其中每一内部节点连接只连接在单独域内的节点。
全文摘要
一种用于分布式稀疏线性系统中并行ILU分解的系统和方法,所述系统和方法采用了对系统内方程的基本节点进行排序的方法并且降低了处理时间。
文档编号G06F15/16GK102334110SQ200980145215
公开日2012年1月25日 申请日期2009年11月5日 优先权日2008年11月12日
发明者王清华, 詹姆斯·威廉姆三世·瓦茨 申请人:兰德马克绘图国际公司

最新回复(0)