[發(fā)明專利]對(duì)基于矩陣的分布式編程語(yǔ)言進(jìn)行自動(dòng)優(yōu)化的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201610101123.3
• 申請(qǐng)日: 2016-02-24
• 公開(kāi)（公告）號(hào): CN105786583B
• 公開(kāi)（公告）日: 2019-03-29
• 發(fā)明（設(shè)計(jì)）人: 武永衛(wèi);章明星;陳康;鄭緯民
• 申請(qǐng)（專利權(quán)）人: 鄞州浙江清華長(zhǎng)三角研究院創(chuàng)新中心
• 主分類號(hào): G06F8/41
• 分類號(hào): G06F8/41
• 代理公司: 北京清亦華知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11201
• 代理人: 張大威

1.一種對(duì)基于矩陣的分布式編程語(yǔ)言進(jìn)行自動(dòng)優(yōu)化的方法，其特征在于，包括以下步驟：

S1：將用戶輸入的程序按照預(yù)設(shè)的編程模型進(jìn)行規(guī)范化處理；

S2：對(duì)規(guī)范化處理后的程序進(jìn)行基于數(shù)據(jù)流的靜態(tài)分析，以得到各個(gè)變量間的數(shù)據(jù)依賴關(guān)系；

S3：對(duì)規(guī)范化處理后的程序進(jìn)行條件敏感的靜態(tài)分析，以得到語(yǔ)句間的控制流依賴關(guān)系；

S4：對(duì)規(guī)范化后的程序進(jìn)行分塊，以使每一個(gè)程序塊都可以完全依賴本地的數(shù)據(jù)，且在完全不進(jìn)行網(wǎng)絡(luò)通訊的情況下進(jìn)行計(jì)算，以使程序塊的數(shù)量最少；以及

S5：在得到的程序塊之間插入網(wǎng)絡(luò)通訊原語(yǔ)，以使所述網(wǎng)絡(luò)通訊的開(kāi)銷最小。

2.根據(jù)權(quán)利要求1所述的對(duì)基于矩陣的分布式編程語(yǔ)言進(jìn)行自動(dòng)優(yōu)化的方法，其特征在于，所述預(yù)設(shè)的編程模型為KASEN編程模型，所述KASEN編程模型為自定義的編程模型，具有如下特征：對(duì)局部變量和全局變量的區(qū)分，并且規(guī)定局部變量?jī)H可通過(guò)局部變量計(jì)算得出，全局變量?jī)H可通過(guò)全局變量計(jì)算得出；定義了完全分開(kāi)的網(wǎng)絡(luò)通訊及計(jì)算原語(yǔ)；定義了兩類共4個(gè)不同的計(jì)算原語(yǔ)，其中，vector-only類的原語(yǔ)包括Map，Reduce和ZipWith；matrix-vector類的原語(yǔ)包括MxV，所述S1進(jìn)一步包括：

所述KASEN編程模型通過(guò)定義Local類變量、Shared類變量、Vector類變量和Matrix類變量對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)，其中，Local類變量表示的是局部數(shù)據(jù)，每一個(gè)Local類變量在各個(gè)機(jī)器上都各自有一份實(shí)例，并且這些實(shí)例之間不需要進(jìn)行同步，Shared類變量表示的是一種全局變量，每一個(gè)Shared類變量在各個(gè)機(jī)器上也都各自有一份實(shí)例，并且Shared類變量的值需要實(shí)時(shí)保持同步，各個(gè)機(jī)器上的Shared變量的值必須相等，Vector類變量同樣是一種全局變量，且Vector類變量中的每一個(gè)元素只會(huì)被存儲(chǔ)在一個(gè)機(jī)器之上，Matrix類變量也是一種分布式的存儲(chǔ)在集群中的全局變量，其存儲(chǔ)方式由用戶預(yù)先設(shè)定；

所述KASEN編程模型通過(guò)定義Map操作、Reduce操作、ZipWith操作和MxV操作對(duì)數(shù)據(jù)進(jìn)行相應(yīng)操作，其中，Map操作的輸入和輸出分別是一個(gè)數(shù)組，系統(tǒng)將給定的用戶函數(shù)應(yīng)用于輸入數(shù)組的每一個(gè)元素上，以得到輸出數(shù)組，Reduce操作的輸入為一個(gè)數(shù)組，但輸出僅為一個(gè)標(biāo)量，系統(tǒng)利用用戶給定的歸并函數(shù)不斷的將輸入數(shù)組的數(shù)據(jù)歸并，直至得到最終的結(jié)果，將所述最終的結(jié)果作為所述標(biāo)量，ZipWith操作的輸入為兩個(gè)數(shù)組，輸出為一個(gè)數(shù)組，系統(tǒng)將用戶給定的函數(shù)應(yīng)用于兩個(gè)輸入數(shù)組中下標(biāo)相等的兩個(gè)元素中從而得到相應(yīng)的輸出，MxV操作執(zhí)行類似于線性代數(shù)中矩陣與向量的乘積操作，將輸入的一個(gè)數(shù)組和一個(gè)矩陣相乘得到結(jié)果數(shù)組。

3.根據(jù)權(quán)利要求2所述的對(duì)基于矩陣的分布式編程語(yǔ)言進(jìn)行自動(dòng)優(yōu)化的方法，其特征在于，還包括：所述編程模型提供兩種不同的網(wǎng)絡(luò)原語(yǔ)，分別為gather和scatter，其中，

所述gather用于將分布式狀態(tài)下的全局變量轉(zhuǎn)換成集中式的存儲(chǔ)；

所述scatter用于將集中式存儲(chǔ)的變量轉(zhuǎn)換成分布式狀態(tài)。

4.根據(jù)權(quán)利要求1所述的對(duì)基于矩陣的分布式編程語(yǔ)言進(jìn)行自動(dòng)優(yōu)化的方法，其特征在于，所述S2進(jìn)一步包括：

對(duì)規(guī)范化處理后的程序進(jìn)行流敏感的數(shù)據(jù)流分析，以得到每一個(gè)變量的always-depended信息和may-depended信息，其中，所述always-depended信息為一個(gè)變量的集合，在該集合中的所有變量，無(wú)論輸入數(shù)據(jù)如何都會(huì)被該輸入數(shù)據(jù)所依賴，所述may-depended信息為一個(gè)變量的集合，在該集合中的所有變量，在特定的條件下會(huì)被輸入數(shù)據(jù)所依賴；

根據(jù)所述always-depended信息和may-depended信息得到所述規(guī)范化處理后的程序中各個(gè)變量間的依賴關(guān)系。