[發(fā)明專利]由序列通項表達(dá)式驅(qū)動的并行計算傳輸列表實時壓縮方法

有效

• 申請?zhí)枺?/td>: 201510010178.9
• 申請日: 2015-01-08
• 公開（公告）號: CN104485967B
• 公開（公告）日: 2017-10-03
• 發(fā)明（設(shè)計）人: 吳峻峰;許躍生;張勇瑞;林英展;王健珊;關(guān)文超;何鴻愷;李達(dá)超;葉緯材;張永東;江穎
• 申請（專利權(quán)）人: 中山大學(xué)
• 主分類號: H03M7/30
• 分類號: H03M7/30
• 代理公司: 廣州市華學(xué)知識產(chǎn)權(quán)代理有限公司44245
• 代理人: 黃磊,李斌

技術(shù)領(lǐng)域

本發(fā)明涉及并行計算機程序的數(shù)據(jù)通信研究領(lǐng)域，特別涉及一種由序列通項表達(dá)式驅(qū)動的并行計算傳輸列表實時壓縮方法。

背景技術(shù)

以往解決并行計算的傳輸列表壓縮問題的時候，有三種方案。這些方案不包括用傳統(tǒng)的文件壓縮算法壓縮傳輸列表，原因是那些壓縮算法的實時性達(dá)不到要求。

第一種方案適用于某些特定的并行計算流程，這些流程已經(jīng)有專用的軟件封裝數(shù)據(jù)通信過程了，例如Hypre、PESTc、ScaLAPACK等。封裝的功能一般包括了傳輸列表的壓縮，因此應(yīng)用程序自身代碼不用管傳輸列表。由于并行計算流程的特殊性，這些專用軟件往往能為傳輸列表找到很簡短的表示方式。這是因為在較窄應(yīng)用范圍內(nèi)，傳輸列表往往是很有規(guī)律的，明確了規(guī)律之后就容易找到其最佳的表示方式。還有更幸運的情況，傳輸列表甚至不需要包含在數(shù)據(jù)通信消息中，這是因為在某些非常特殊的并行計算流程里，專用軟件的程序可以在數(shù)據(jù)擁有者節(jié)點安排一段代碼扮演“代理”的角色。這類“代理”可以在擁有者處通過計算生成一份一模一樣的傳輸列表，替請求者遞交給數(shù)據(jù)擁有者。

第二種方案適用于某些簡化的并行計算流程。這些流程非常簡單，簡單到可以配套“通用”軟件框架來封裝數(shù)據(jù)通信。典型的例子是Map-Reduce。這里“通用”打引號是因為那只是計算部分的通用，通信部分的流程則要按照簡化的固定的模式來走。通信部分的簡化使傳輸列表很結(jié)構(gòu)化，有固定形式、甚至能預(yù)先確定，因此軟件框架不需要知道數(shù)據(jù)的具體專業(yè)領(lǐng)域的信息，也不需要應(yīng)用程序代碼的幫助，就能做好傳輸列表的壓縮甚至“代理”。

第三種方案適用于通用的并行計算流程。這些流程通常使用通用的數(shù)據(jù)通信支持庫來實現(xiàn)(例如MPI、PVM等)，但需要程序自主管理數(shù)據(jù)傳輸過程。這種方法的數(shù)據(jù)傳輸，可以使用雙邊通信功能，也可以用單邊通信功能。其中，雙邊是指數(shù)據(jù)請求者和數(shù)據(jù)擁有者兩邊，單邊則特指數(shù)據(jù)請求者這一邊。雙邊通信需要兩邊都知道傳輸列表。數(shù)據(jù)請求者當(dāng)然是知道傳輸列表的，問題在于怎樣讓數(shù)據(jù)擁有者得到傳輸列表，和前面說的一樣，可以把傳輸列表先發(fā)送給數(shù)據(jù)擁有者，也可以在擁有者處定制一份“代理”代碼來計算出一份一模一樣的傳輸列表。不管是發(fā)送還是計算，一旦應(yīng)用程序的自身代碼讓兩邊都有了傳輸列表，雙邊通信就能很默契地高效完成了。單邊通信實際上是由單邊激發(fā)通信，真正的通信過程仍然要兩邊都參與。單邊通信與雙邊通信的區(qū)別在于單邊通信自動化了把傳輸列表發(fā)給數(shù)據(jù)擁有者的過程，因此單邊通信不可能使用“代理”代碼，并且對傳輸列表只能采取機械化的表示方式。

上述第一種方案的缺點是專業(yè)領(lǐng)域上的適用面窄，其缺點的原因是需要針對非常特殊的并行計算流程，利用數(shù)據(jù)的專業(yè)領(lǐng)域信息，來定制傳輸列表的表示方式和“代理”代碼。換到另外一種應(yīng)用，專業(yè)領(lǐng)域上的差別可以是非常大的。

上述第二種方案的缺點是計算流程上的適用面窄。其缺點的原因是并行計算流程過度簡化，不能適應(yīng)很多應(yīng)用的計算需求。

上述第三種方案的缺點是程序優(yōu)化難度大，程序開發(fā)成本高。對于雙邊通信，應(yīng)用程序要在自身代碼中自主定制傳輸列表的表示方式和“代理”代碼，過程繁瑣。對于單邊通信，由于傳輸列表已經(jīng)被機械化地自動處理了，所以程序優(yōu)化空間小，無法為傳輸列表選擇較好的表示方式，也無法用“代理”代碼來減少傳輸列表的發(fā)送。單邊通信的優(yōu)化，最直接的做法往往是換成合理的雙邊通信。

發(fā)明內(nèi)容

本發(fā)明的主要目的在于克服現(xiàn)有技術(shù)的缺點與不足，提供一種由序列通項表達(dá)式驅(qū)動的并行計算傳輸列表實時壓縮方法，用于實現(xiàn)并行計算傳輸列表的表示方式和“代理”代碼的定制和實現(xiàn)。

為了達(dá)到上述目的，本發(fā)明采用以下技術(shù)方案：

由序列通項表達(dá)式驅(qū)動的并行計算傳輸列表實時壓縮方法，包括下述步驟：

S1、傳輸列表的邏輯分解并將傳輸列表按對象歸屬地劃分，由于邏輯命題“對象在某地”在數(shù)學(xué)中可以用“對象的位置在某地范圍內(nèi)”這種不等式所表示，所以所述劃分是通過求解由多維的不等式組得到的，而不等式組的求解可以先根據(jù)不等式之間的依賴關(guān)系拆分為相互獨立的小不等式組，以降低求解的復(fù)雜度，這就是所述的邏輯分解；

S2、非線性部分優(yōu)化，利用非線性部分不等式的表格化來繼續(xù)縮小范圍，用組內(nèi)涉及的變量的范圍來驗證非線性部分不等式；

S3、“代理”代碼定制，對于只包含線性表達(dá)式的組，只要該組表達(dá)式中的“常量”是在數(shù)據(jù)擁有者節(jié)點上可知的，那么該組就可以用“代理”代碼；