[發明專利]對基于矩陣的分布式編程語言進行自動優化的方法

有效

• 申請號: 201610101123.3
• 申請日: 2016-02-24
• 公開（公告）號: CN105786583B
• 公開（公告）日: 2019-03-29
• 發明（設計）人: 武永衛;章明星;陳康;鄭緯民
• 申請（專利權）人: 鄞州浙江清華長三角研究院創新中心
• 主分類號: G06F8/41
• 分類號: G06F8/41
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 張大威

本發明提出一種對基于矩陣的分布式編程語言進行自動優化的方法，包括以下步驟：將用戶輸入的程序按照預設的編程模型以進行規范化處理；對規范化處理后的程序進行基于數據流的靜態分析，以得到各個變量間的數據依賴關系；對規范化處理后的程序進行條件敏感的靜態分析，以得到語句間的控制流依賴關系；對規范化后的程序進行分塊，以使每一個程序塊都可以完全依賴本地的數據，且在完全不進行網絡通訊的情況下進行計算，以使程序塊的數量最少；在得到的程序塊之間插入網絡通訊原語，以使網絡通訊的開銷最小。本發明可以自動地對給定的基于矩陣的程序進行優化，通過減少內存的讀取與寫入，提升緩存的利用率，減少通訊量等手段將程序的運行效率提升。

技術領域

本發明涉及大數據處理技術領域，特別涉及一種對基于矩陣的分布式編程語言進行自動優化的方法。

背景技術

傳統的基于矩陣的編程語言，比如說MATLAB、R等，能夠用一種緊湊的方法表達對數據的操作。因此，他們被廣泛地應用于數據分析和科學計算領域。為了保證這些語言的易用性，并同時能夠通過增加機器數目進行線性擴展，很多工具被研究人員們提出。這些工具一般來說會提供一個與上述語言相似的基于矩陣的編程接口，同時它們的底層實現會基于MapReduce等大數據編程模型。通過自動地將這兩種模型進行轉換得到既保留上層語言的可編程性，又能夠做到擴展以及容錯的系統。然而，由于這些面向于MapReduce的底層系統缺乏相應的原語，它們執行矩陣運算時的效率并不高，并且通訊量也很大，因此并不是一個合適的方法。

由于上述的問題，后續的研究人員嘗試開發了直接基于分布式矩陣操作的分布式計算框架。這些框架(比如Spartan，ComBLAS等)將數據描述為一維或多維的數組，并利用矩陣計算原語對它們進行操作。由于利用了目前已有的一些技術實現，比如2.5D矩陣乘法、分片等，它們得以獲得了很高的運行效率。根據它們的測評結果，這一類的計算框架一般都遠快于傳統的計算框架(至少10倍的效率提升)。

然而，這樣的體系結構仍然是不完美的。有一類重要的組件不存在于這一類結構之中，即優化器。優化器應該要可以通過講操作進行合并或者調整操作間的順序等辦法對程序進行優化。相對地，目前的這一類系統基本上都采取的是最簡單的實現方法，既完全按照程序員所給定的步驟，一步一步地執行，這就好像是在程序編譯的時候加上了–O0選項一樣。這一狀況昭示了在這一部分仍然有很大的優化空間。舉例來說Spartan系統采用了一個很簡單的優化策略，既將相鄰的多個Map操作或者Map－Reduce對組合到一個函數中去一起執行。根據它們的測試，這樣簡單的優化就能夠取得最高達到兩倍的優化。

雖然在傳統的單機領域對基于矩陣的編程語言進行優化是一個已經被研究了很多年的話題，但在多機領域仍然沒有先例。在多極情況下優化器必須考慮到數據間的同步情況，因此并不能進行任意的跳換按順序。根據相關研究發現，現有的方法主要面臨著以下幾個問題：1)現有的編程模型要么過于局限以至于有很大一類的算法不能夠被支持，要沒過于廣泛以至于無法進行有效的優化；2)利用傳統的基于矩陣的語言進行編程的時候會產生很多的中間結果數組，需要對他們進行合并處理；3)數據同步的順序需要仔細考慮，從而減少網絡通訊的開銷。

發明內容

本發明旨在至少在一定程度上解決上述相關技術中的技術問題之一。

為此，本發明的目的在于提出一種對基于矩陣的分布式編程語言進行自動優化的方法，該方法可以自動地對給定的基于矩陣的程序進行優化，通過減少內存的讀取與寫入，提升緩存的利用率，減少通訊量等手段將程序的運行效率提升。