黃杰英

【摘要】大規(guī)模非對(duì)稱線性方程組的求解在我國(guó)工程、計(jì)算機(jī)、資源探測(cè)、核爆模擬等領(lǐng)域都十分重要，隨著我國(guó)計(jì)算機(jī)和工程領(lǐng)域發(fā)展，大規(guī)模非對(duì)稱線性方程組求解所需時(shí)間也越來越長(zhǎng)，正是因?yàn)榍蠼獾闹匾院陀?jì)算的耗時(shí)性，因此，近年來越來越多的科學(xué)研究機(jī)構(gòu)組織與社會(huì)數(shù)學(xué)科學(xué)工作者，投入了大量的人力和物力，來對(duì)大規(guī)模非對(duì)稱線性方程組的求解進(jìn)行研究。在眾多算法中，并行計(jì)算方法逐漸脫穎而出，本文就大規(guī)模非對(duì)稱線性方程組的并行計(jì)算方法進(jìn)行的研究，提出了多種簡(jiǎn)便的新型并行計(jì)算方法，從而縮短了非對(duì)稱線性方程組的計(jì)算時(shí)間。

【關(guān)鍵詞】梯度計(jì)算法 線性方程組 分裂疊加法 并行計(jì)算

【中圖分類號(hào)】G642 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】2095-3089（2017）15-0211-02

一、引言

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

二、并行計(jì)算

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

1.并行計(jì)算程序模型

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

2.并行計(jì)算程序設(shè)計(jì)方法

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

三、梯度計(jì)算法

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

1.共軛梯度法計(jì)算非對(duì)稱線性方程組

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

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

2.分裂疊加法

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

四、結(jié)論

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

參考文獻(xiàn)：

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

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

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