大規(guī)模非對稱線性方程組的并行計算方法研究

黃杰英

【摘要】大規(guī)模非對稱線性方程組的求解在我國工程、計算機、資源探測、核爆模擬等領域都十分重要，隨著我國計算機和工程領域發(fā)展，大規(guī)模非對稱線性方程組求解所需時間也越來越長，正是因為求解的重要性和計算的耗時性，因此，近年來越來越多的科學研究機構組織與社會數(shù)學科學工作者，投入了大量的人力和物力，來對大規(guī)模非對稱線性方程組的求解進行研究。在眾多算法中，并行計算方法逐漸脫穎而出，本文就大規(guī)模非對稱線性方程組的并行計算方法進行的研究，提出了多種簡便的新型并行計算方法，從而縮短了非對稱線性方程組的計算時間。

【關鍵詞】梯度計算法 線性方程組 分裂疊加法 并行計算

【中圖分類號】G642 【文獻標識碼】A 【文章編號】2095-3089（2017）15-0211-02

一、引言

目前我國側重于大規(guī)模的發(fā)展科學技術與工程，資源探測，核爆模擬等領域。這些領域涉及了眾多的復雜非對稱線性方程組的計算[1-3]。在眾多求解方法中，并行計算法計算法的應用范圍最廣，國內(nèi)對并行計算求解的需求量是推動并行計算法快速發(fā)展的主要動力。在我國科學發(fā)展的道路上，對并行計算求解法的需求是無止境的，并行計算法是電子計算機工程中，自然氣候，天氣預報，核爆數(shù)值模擬等等領域對非對稱線性方程組求解的核心技術之一。據(jù)調(diào)查顯示，在部分非對稱線性方程組計算領域中，方程組的求解占據(jù)了80%-90%的時間，因此，大規(guī)模非對稱線性方程組并行計算方法的研究已經(jīng)成為了目前十分重要的研究領域。

二、并行計算

并行計算法是指將大規(guī)模復雜的非對稱線性方程組，并行到同一臺計算機或系統(tǒng)上，然后有系統(tǒng)將方程組分為若干個小方程組，再將小方程組分別下發(fā)給該系統(tǒng)的各個子方程組處理器，由各個子處理器統(tǒng)一進行并行計算，各子處理器間進行計算的數(shù)據(jù)傳輸，交換，協(xié)調(diào)并行的各自進行計算，從而達到加快計算速度的目的。要對大規(guī)模復雜的非對稱線性方程組進行并行計算就必須要滿足并行計算機，并行計算算法，并行計算方程這三個條件。并行計算算法是指，進行計算的方程組必須滿足并行計算的條件，通常可以進行并行計算的方程組需要滿足方程組可以分解成為若干個小方程組的條件，只有可以分裂為若干個小方程組的方程組才可以進行并行計算，而將方程組分為若干個子任務的過程，我們稱為并行計算算法。并行計算的編程是指，下分給個子服務器任務后，服務器在并行計算機提供的編程程序上進行獨立的求解計算。

1.并行計算程序模型

并行計算程序模型通常分為內(nèi)存處理系統(tǒng)共享型模型，并行處理器消息傳輸型模型，信息數(shù)據(jù)并行模型三種。 內(nèi)存處理系統(tǒng)共享型模型主要是進行大規(guī)模復雜的非對稱線性方程組并行計算程序中的進程或線程時所采用的模型。其模型可以通過對數(shù)據(jù)信息共享內(nèi)存區(qū)的整體信息進行操作，從而達到使個子服務器間進行相互的數(shù)據(jù)信息傳輸和配合的目的。一邊來說，并行計算程序的程序員只需要集中精力在并行計算子任務的分配以及映射到各子服務器的進程或線程任務的分配，而對于那些被處理掉的無用數(shù)據(jù)信息所處的位置并不需要進行共享和編程。我們較為常見內(nèi)存處理系統(tǒng)共享型模型的編程主要可以分為共享內(nèi)存模型式和自行編寫模型編程式。并行處理器消息傳輸型模型是指各個子處理器間的并行任務之間不能通過編程程序的地址來進行相互的數(shù)據(jù)信息傳輸或交換，只能獨立的進行計算任務。各子服務器間若想要通過訪問其他子服務器來獲得另一個子服務器的所進行的任務數(shù)據(jù)信息，就必須向核心任務系統(tǒng)提出數(shù)據(jù)相互通信請求，請求成功后才可以進行各子服務器間的數(shù)據(jù)信息傳輸和交流。因此，一般來說，進行并行計算系統(tǒng)編程程序的程序員必須在進行任務劃分后將子任務映射到編程進程的實體，然后在編程程序碼中加入進行數(shù)據(jù)交換的請求代碼，此編程模式要求編程程序員必須關注個子服務器的數(shù)據(jù)的分布情況。一般我們較為常見的編程就歸類于并行處理器消息傳輸型模型，編程程序號自行編寫多個小進程，并通過各進程間的通信方來進行交互交換數(shù)據(jù)信息的模型方法也可以歸類為此模型。信息數(shù)據(jù)并行模型是指該種模型方法可以通過在并行計算機和并行計算機上的任務分配和網(wǎng)絡信息傳遞來實現(xiàn)大規(guī)模復雜的非對稱線性方程組的求解。信息數(shù)據(jù)并行編程模型一般可以提供給編程程序員一個可觀全局性的網(wǎng)絡空間地址，程序員可以通過該地址來觀察各子服務器間的數(shù)據(jù)傳輸交流及方程組求解情況，對不同的數(shù)據(jù)信息都可以執(zhí)行相同的操作來進行數(shù)據(jù)的整體控制。常見的MICD以及FRCOLD編程都屬于信息數(shù)據(jù)并行的編程模型。三種并行編程程序的模型如表一所示。

2.并行計算程序設計方法

并行計算程序的設計方法主要分為并行任務的劃分，并行處理器間的相互數(shù)據(jù)信息傳輸交流，各子任務處理器求解結果信息的匯總和最終處理結果的顯示四個步驟。并行任務的劃分主要是將大規(guī)模復雜的非對稱線性方程組的求解計算任務劃分為盡可能多的小任務，然后將這些小任務分配給各子處理器系統(tǒng)，由子處理器系統(tǒng)進行計算。折衷法方法可以充分的發(fā)展并行算法的計算并行性和計算范圍的可擴展性。通常我們所采用的子任務劃分方法分為兩種。一是按照需要處理的大規(guī)模復雜的非對稱線性方程組的數(shù)據(jù)進行小任務的分解和按照算方程組的功能來進行分解。在進行數(shù)據(jù)分解和計算功能的分解時，需要做到兩種分解方式的計算數(shù)據(jù)和計算區(qū)域，計算方法相互不重復，無交集，互為獨立的處理系統(tǒng)。

三、梯度計算法

基于大規(guī)模復雜的非對稱線性方程組的并行計算方法中的方程組分解法，我們對大規(guī)模復雜的非對稱線性方程組的并行計算方法進行了深入的研究，提出了一種新型的計算方法，梯度計算法，梯度計算法主要是對并行計算法中搜索方向技術進行優(yōu)化，從而提出的一種新興的簡便計算方法，一般稱為多方向計算方法。這種計算方法主要是對劃分到每個子服務器的任務進行定向搜索，傳統(tǒng)的并行計算方法是對所有子服務器的方向進行逐個搜索，其搜索范圍廣，耗時長，因此會延緩方程組的求解時間，而梯度計算法則是對子任務進行定向搜索，其搜索范圍小，用時較短。無需像傳統(tǒng)方法那樣進行全方面的搜索。梯度計算方法的關鍵是利用對小型的線性方程組的求解取代了傳統(tǒng)方法中對方程組整體內(nèi)積的求解計算。將大規(guī)模的非對稱線性方程組劃分成為每個小方程組，每個小方程組的結構通常是基于劃分區(qū)域的分解方式和定向搜索方向的選取，其核心主要是利用直接求解法代替?zhèn)鹘y(tǒng)求解法進行方程組求解。若用梯度法的近似求解，則可以得出MISD一CAG方法的一種近似與梯度求解的形式，這種近似方法僅需要對相鄰兩個子區(qū)域之間的數(shù)據(jù)信息進行傳輸，通訊和配合。從而完全去掉了方程組的整體內(nèi)積的計算。我們將這種近似梯度法求解的方法稱之為共軛梯度方法，共軛梯度方法特別適合大規(guī)模復雜的非對稱線性方程組的計算。

1.共軛梯度法計算非對稱線性方程組

大規(guī)模的非對稱線性方程組求解，耗時的主要問題在于方程組的不對稱性。對于傳統(tǒng)并行計算方法中的方程組的正對稱問題上，傳統(tǒng)的并行計算方法很難講劃分到各個子服務器的小方程組進行正對稱的計算，因此一般來說求解匹配結果時間過長，會造成方程組的求解效率降低。因此，在對大規(guī)模的非對稱線性方程組進行求解時，我們最需要解決的就是方程組的正對稱問題對于對稱問題，因此，我們采取共軛梯度的方法來對對稱的線性方程組進行求解計算。共轆梯度方法可以非常有效的解決非對稱線性方程組中的子空間搜索方法。一般來說，共軛梯度法對大規(guī)模的非對稱線性方程組的計算難點主要在于，對各個子任務的并行化和對子任務空間的內(nèi)積進行計算。對子服務器方程組整體內(nèi)積的計算在大規(guī)模非對稱線性方程組的并行計算中顯得尤為重要，因為在對方程組進行并行計算過程中，子方程組的內(nèi)積總是擔當同步存貯點并需要整體數(shù)據(jù)信息進行相互的交流，傳輸和存貯。對于子服務器內(nèi)積的計算，我們既需要對子服務器方程組的計算方法進行優(yōu)化，也需要對聚集在子方程組上的數(shù)據(jù)信息進行整理和計算。因為多有的子服務器都需要知道處理結果，再根據(jù)數(shù)據(jù)信息的處理結果進行進一步的求解計算。對各個子服務器方程組的求值結果進行進一步的計算，主要取決于進行并行計算的計算機和進行并行計算的花銷。當子服務器方程組計算花銷較大時，整體的子服務器通訊占領了計算的主導地位。對并行計算處理系統(tǒng)已經(jīng)造成了嚴重的限制。因此，解決子服務器內(nèi)積的問題尤為重要。

共軛梯度處理方法每步只需兩個子服務器的內(nèi)積計算，在并行計算機的處理系統(tǒng)中，一般來說每并行一個方程組，只需要對其中的五個元素進行矩形列陣的計算。當自服務器處理系統(tǒng)的元素量超過200時，子服務器的內(nèi)積就占領了主導地位，共軛梯度法主要是通過控制自服務器內(nèi)積的方法來對子服務器進行控制，確保其計算的流暢性。共軛梯度處理方法每步只需要對兩個子服務器內(nèi)積進行計算，計算依次進行，成梯度方式，確保內(nèi)積不會占領數(shù)據(jù)的主導地位。通過降低子計算機之間的同步點數(shù)來提高子計算機與計算開銷的比值。將兩個分離的子計算機內(nèi)積用三個連續(xù)的小內(nèi)積進行代替計算，這三個小內(nèi)積可以進行并行計算，從而可組合它們的計算數(shù)據(jù)，對小內(nèi)積間的計算數(shù)據(jù)進行對比分析和取值。從而提高了計算效率，減小了子計算機內(nèi)積對大規(guī)模的非對稱線性方程組求解的影響。

2.分裂疊加法

分裂疊加法計算大規(guī)模的非對稱線性方程組主要是通過對主并行計算機的分裂來實現(xiàn)。進行并行計算的各子計算機之間是相互獨立的，因此，對于一臺主計算機控制多臺子計算機進行計算的方法可以通過分裂疊加法來實現(xiàn)。在計算的每一步，每一個子計算機都會進行一次局部的數(shù)據(jù)信息傳輸，將數(shù)據(jù)信息統(tǒng)一傳輸?shù)街饔嬎銠C上，集中由主計算機進行數(shù)據(jù)的計算。然后將計算后的數(shù)值傳輸回各子計算機上，再由子計算機進行下一步的計算。計算后將數(shù)據(jù)信息在此傳輸?shù)街饔嬎銠C中，由主計算機進行數(shù)據(jù)信息的計算，再將兩次計算的結果進行疊加，將疊加出的新數(shù)據(jù)信息傳輸回子服務器，由子服務器進行計算。以開始下一步的疊加計算，以此類推，最終疊加出的數(shù)據(jù)則為該方程組的求值。采用縮小計算規(guī)模的方式，來減小大規(guī)模的非對稱線性方程組的計算時間，從而達到計算的高效性。

四、結論

隨著科學技術的不斷發(fā)展，越來越多的科學和工程領域需要進行對大規(guī)模的非對稱線性方程組進行并行計算。本文就并行計算法的基礎上提出了新型的更適合對非對稱線性方程組的計算方法。首先，我們先對并行計算法的計算模型進行了分析。得出了并行計算系統(tǒng)程序的建立方法，從而設計了解非對稱線性方程組的系統(tǒng)程序。之后我們提出了共軛梯度的方法來對非對稱線性方程組進行并行計算，共軛梯度法主要是對傳統(tǒng)梯度法中的子計算機內(nèi)積進行優(yōu)化，從而增大計算效率。最后提出了分裂疊加法，通過對主計算機的方程組進行分裂，然后依次對數(shù)據(jù)進行疊加和新數(shù)據(jù)的計算，傳輸，疊加。從而減小計算難度，增加計算效率。本文所提出的計算方法，解決了大規(guī)模非對稱線性方程組的計算難度。

參考文獻：

[1]白中治，王德人.異步并行矩陣多分裂多參數(shù)松弛方法，高校計算數(shù)學學報，1994，16（2）：107-115.

[2]吳建平，王正華.李曉梅線性方程組的高效求解與并行計算湖南：湖南科學技術出版社，2004.

[3]王馳，劉羽.GPU優(yōu)化的大規(guī)模線性方程組并行求解的研究與比較[J].信息通信，2016，6（12）：23-30.