[發明專利]基于指令序列與消息序列指引的深度依賴問題并行方法

在審

• 申請號: 201910879931.6
• 申請日: 2019-09-18
• 公開（公告）號: CN112527394A
• 公開（公告）日: 2021-03-19
• 發明（設計）人: 陳鑫;陳德訓;劉鑫;李芳;徐金秀;孫唯哲;郭恒;王臻
• 申請（專利權）人: 無錫江南計算技術研究所
• 主分類號: G06F9/38
• 分類號: G06F9/38;G06F9/30
• 代理公司: 蘇州創元專利商標事務所有限公司 32103
• 代理人: 王健

本發明公開一種基于指令序列與消息序列指引的深度依賴問題并行方法，包括以下步驟：S1、將解向量按塊進行平均劃分，通過這種劃分將解向量中各元素之間的依賴性轉換成向量塊之間的依賴性；S2、將一個向量塊完成計算稱為一次更新操作，此一次更新操作需要以下三個步驟：S21、部分更新：接收前繼塊發送的數據；S22、自我更新：對塊內元素進行計算更新；S23、完成更新：將本向量塊求解完畢的元素發送給所依賴的后繼塊；S3、眾核內每個計算核心按順序計算相應的向量塊，重復S2的更新操作步驟，實現了整個流水線作業計算；S4、為每個計算核心設計一串指令流，即指令序列。本發明提高眾核內部通信的相互協作性，減少訪存時間開銷，實現有效加速。

技術領域

本發明屬于數值計算技術領域，尤其涉及一種基于指令序列與消息序列指引的深度依賴問題并行方法。

背景技術

深度依賴問題是CFD領域常見的一類問題，例如常見的稀疏下三角方程求解，其解之間存在深度依賴關系，即后面的解依賴前面的解求解完畢，因此該問題的求解是一個非常串行的操作。即便是如此串行的操作也能發掘其中的并行部分，目前針對非結構網格中解向量元素之間的深度依賴問題，主要采用分層并行思想，即解向量x按照之間是否具有相關性進行分層處理，屬于同一層的未知數可以并行求解，層與層之間串行執行，為了保證計算時序正確性，計算完每一層之后需要同步。

分層并行算法主要缺陷在于需要先找出各個解之間的依賴層次關系，對解向量x先按照層次進行重排處理，稀疏矩陣也要進行相應處理才能參與計算。得到結果之后還需要再轉換成原來的解向量x，相當于兩次重排序，這部分時間開銷不可避免。另外，該算法需要每一層具有足夠的并行度，同步開銷才能足夠小，如果幾乎向量中的每一個元素xi都依賴于前一個元素xi-1（我們稱之為強依賴關系，反之為弱依賴關系），每一層只有若干個少量元素，那么這種算法性能將極差，很難以有效并行。另一方面，在數據復用性上，該算法也有缺陷，由于深度依賴關系，該算法無法預先緩存所需數據，只能夠細粒度離散訪存。假設x向量中的元素xi依賴于xj，而i與j之間的距離很大（即i-j1，我們稱之為深依賴關系，反之為淺依賴關系），這種情況下該算法無法預先緩存，只能夠細粒度離散訪存。此外，眾核內部通信采用寄存器的方式進行通信，不支持非同行非同列的眾核內部通信，由于非結構網格稀疏矩陣的隨機離散性，眾核內部存在多對多通信的可能，這將導致眾核內有很大概率會產生通信環，由于寄存器緩沖個數有限，將產生通信死鎖問題。

非結構網格問題由于數據的無序性造成稀疏矩陣非零元素無規律存儲。經過實際算例測試，非結構網格下的數據，往往都具有深度依賴關系，現有的申威平臺上針對這類問題還無法實現有效加速。

發明內容

本發明目的在于提供一種基于指令序列與消息序列指引的深度依賴問題并行方法，該并行方法提高眾核內部通信的相互協作性，減少訪存時間開銷，實現有效加速。

為達到上述目的，本發明采用的技術方案是：一種基于指令序列與消息序列指引的深度依賴問題并行方法，面向非網絡結構，包括以下步驟：

S1、根據從核之間計算負載均衡將解向量按塊進行平均劃分，并確定每個向量塊的編號，將解向量中各元素之間的依賴性轉換成向量塊之間的依賴性；

S2、將一個向量塊完成計算稱為一次更新操作，此一次更新操作需要以下三個步驟：

S21、部分更新：當前向量塊通過寄存器通信接收前繼向量塊發送的數據，其中最初的向量塊可直接求解；

S22、自我更新：當前向量塊利用前繼向量塊傳遞的數據，對當前向量塊內元素，即該向量塊對應的解向量進行求解；

S23、完成更新：當前向量塊將求解完畢的元素發送給所依賴的后繼向量塊；

S3、眾核內每個計算核心按順序計算相應的向量塊，重復S2的更新操作步驟，實現整個流水線作業計算；

S4、基于時間順序，為每個計算核心創建指令序列，指令序列按照時間順序嚴格執行，基于指令序列和消息序列的眾核通信模型如下：