[發明專利]用于分布式稀疏線性系統中改進的并行ILU分解的系統和方法

在審

• 申請號: 201410524508.1
• 申請日: 2009-11-05
• 公開（公告）號: CN105320566A
• 公開（公告）日: 2016-02-10
• 發明（設計）人: 王清華;詹姆斯·威廉姆三世·瓦茨
• 申請（專利權）人: 蘭德馬克繪圖國際公司
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F17/12
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 張欣

本申請是申請日為2009年11月5日，申請號為200980145215.X，發明名稱為“用于分布式稀疏線性系統中改進的并行ILU分解的系統和方法”的專利申請的分案申請。

技術領域

本發明大體涉及用于分布式稀疏線性系統的并行ILU分解。更為具體地，本發明涉及一種用于在分布稀疏線性系統中求解系統之前，使用并行ILU分解預條件算子對方程的基本節點進行排序的方法。

背景技術

許多類型的物理過程，包括石油油藏內的流體流動，是由偏微分方程控制的。通常使用有限差、有限體積或者有限元方法來求解這些可能非常復雜的偏微分方程。所有這些方法將物理模型劃分為被稱為網格塊、單元格或者元素的單元。在這些物理單元的每一個中，通過一個或更多的求解變量或未知量給出解。與每個物理單元相關的是一組用于控制這些未知量的特性的方程，方程的數量等于未知量的數量。這些方程還包含來自相鄰的物理單元的未知量。

因此，方程存在結構，同時，給定物理單元的方程含有來自該物理單元和來自相鄰物理單元的未知量。最合宜地，使用節點和連接的組合對其進行描繪，其中節點是由小圓圈描繪的，而連接是由兩個節點之間的線條描繪的。節點處的方程含有該節點處的未知量和連接至其上的相鄰節點處的未知量。

所有節點處的方程集合成單個的矩陣方程。通常，獲得所期望的偏微分方程的解的關鍵任務是求解該矩陣方程。實現該任務的最有效的方式之一是通過使用不完全LU分解法或者ILU，其中原始矩陣被近似分解為兩個矩陣L和U的乘積。矩陣L和U為下三角矩陣和上三角矩陣而且分別具有與原始矩陣的下部和上部類似的非零結構。使用這種分解，通過前向和后向替換迭代地獲得了解。

一直存在對獲得更好的求解準確性的需求。實現該需求的一種方式是將物理模型劃分成更小的物理單元，或者換句話講，使用更多的節點，可能是百萬計數量的節點。當然，為完成其而所需進行的計算的時間增加了。避免這種時間增加的一種方式是在多個處理器上以并行方式執行計算。

存在兩種類型的并行式計算機，即：使用共享式內存和使用分布式內存的計算機。共享式內存計算機只使用少量的處理器，其限制了可能的運行時間減少。常見的是使用數十個處理器的分布式內存計算機，但是也存在一些使用數千個處理器的分布式內存計算機。期望使用分布式內存并行處理。

當使用分布式內存時，通過將物理模型劃分成域而使計算并行化，同時，域的數量等于同時使用的處理器的數量。每個域被分配給一個特定的處理器，其執行與該域相關的計算。每個域包含特定的節點組，且每個節點設置在域內。

整個建模過程涉及很多計算，幾乎所有的計算都是逐個節點進行的。節點處的一些這樣的計算只需要節點的本地信息。當信息被完全包含在與節點相同的域內時，該信息對于節點是本地的。這種計算有時被稱作密集并行，因為它們不需要為了并行實施而執行特殊處理。其它的計算需要節點處和其相鄰節點處的信息。如果節點在自己的域與另一個域的邊界上，其一個或更多的相鄰節點將位于另一個域內。為了實施需要邊界節點處相鄰信息的計算，必須從這些相鄰節點所屬的域內獲得關于這些相鄰節點的信息。如果所需的信息事先已知，其可以容易地通過“消息傳遞”獲得，而且該計算易于并行進行。重要的是信息事先要已知，這是因為消息的傳遞將花費時間。具體地，與通常的計算時間相比，存在一個較長的延遲；換句話講，消息的第一元素需要花費有限的時間到達其接受方。如果該信息是事先已知的，在另一個處理需要該信息之前，含有該信息的消息能夠被發送。以這種方式，在需要該信息之前，其已經到達另一個處理。

遺憾的是，在分解計算中，所需的信息事先是不知道的。正相反，其是在分解期間產生的。計算是具有“固有順序”的。計算的一般流程如下：

1、以在其已被分解的相鄰節點處實施的計算為基礎，更新當前的節點方程。

2、在當前節點處對所得到的修改過的方程進行分解。

3、將與當前節點的分解相關的信息提供給其還未被分解的相鄰節點。

“相鄰節點”不必為最接近的節點。它們可以是在幾個節點之外的節點。

如果只存在一個域，這些計算的順序性就不成問題。如果存在多于一個的域，這些計算的順序性將成為問題。信息必須從一個處理發送到另一個處理。如果直到其馬上要被另一個處理需要之前才知道該信息，則當含有該信息的消息被發送時，存在一個延遲。如果對計算進行排序使得任何將發送到另一個處理的信息在其被該處理需要之前是充分已知的，則可以避免這些延遲。