[發明專利]一種基于多階段模擬退火的靜態異構可重構陣列布局方法

在審

• 申請號: 202010088759.5
• 申請日: 2020-02-12
• 公開（公告）號: CN111291529A
• 公開（公告）日: 2020-06-16
• 發明（設計）人: 景乃鋒;行華彧;蔣劍飛;王琴;繩偉光;賀光輝
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F30/392
• 分類號: G06F30/392
• 代理公司: 上海旭誠知識產權代理有限公司 31220
• 代理人: 鄭立

本發明公開了一種基于多階段模擬退火的靜態異構可重構陣列布局方法，涉及可重構陣列的互連架構領域。其特征在于，利用圖距離來構建異構資源的位置約束，利用分階段模擬退火的方法來分離所述異構資源在同一次所述模擬退火中的相互影響。本發明通過構建基于圖距離的新型代價函數，來解決傳統代價函數對異構陣列建模不精確的問題，進而根據不同異構單元的特性，提出分階段模擬退火的布局方案。與傳統方案應用在異構陣列上的結果相比，應用新型代價函數的多階段模擬退火方法在同等互連資源的條件下可平均提高29.6％的布通率。

技術領域

本發明涉及可重構陣列的互連架構領域，尤其涉及一種基于多階段模擬退火的靜態異構可重構陣列布局方法。

背景技術

可重構陣列處理器是一種被認為是具備優秀的自定義配置能力，可以承擔數據密集型運算，也能夠相較FPGA獲得更好的工作頻率，實現高性能運算的新型處理器，是一種靈活性與專用性的折中方案，既可以保持相對于專用集成電路(ASIC)的較高性能，又可以實現類似FPGA一樣的高自由度?？芍貥嬯嚵械拿恳淮芜\行前首先接收配置信息，配置控制模塊將配置信息送入每一個執行單元和每一個互連資源上，應用程序正式啟動之后，每個執行單元按照配置好的流程進行運算。

映射算法設計解決具體的應用程序如何利用互連資源在陣列上運行的問題，因此映射算法也常常被稱為布局布線算法。布局布線問題的本質是一個圖匹配問題。該問題接收兩個輸入即數據流圖與陣列互連資源圖，在資源圖中對數據流圖進行匹配，將數據流圖中的點映射在資源圖中執行單元所代表的節點；將數據流圖中的邊映射在資源圖中互連資源所代表的節點。輸出則是數據流圖在陣列資源圖上的匹配結果。

這類圖匹配問題被證明是一個NP完全問題，不存在多項式時間復雜度的解法。對于動態可重構陣列來說，布局布線算法在理論上不會出現失敗的情況，只會因為過分增加迭代間隔導致并行度的下降。而對于靜態可重構陣列，由于沒有辦法通過時間展開的方式來解決布局布線算法中無法布通的情況，因此通常采用類似FPGA中布局布線的模擬退火算法，在陣列的互連資源較豐富且不降低并行度的前提下布通。

在模擬退火布局算法中，代價函數是及其重要的一環，它直接影響了布局質量與布通率。代價函數最關鍵的部分在于正確的對布線難易程度進行建模。對于傳統的同構可重構陣列，DFG圖(Data Flow Graph)的映射已經有了較為成熟的解決方案，主要方法為以模擬退火為核心的布局過程與布通率驅動的布線過程；在布局布線工具VPR中，采用線性擁擠函數來評估布線質量，優勢是建模準確，并且函數計算簡單，在同構陣列下，線性擁擠函數有很好的效果。但是隨著發展，有較多新型異構陣列被提出。在異構陣列中存在不同類型計算資源的位置約束，傳統的映射方案中沒有對這類異構問題進行建模，因此在異構陣列下不能精準的反應位置約束，因此會出現布通率下降甚至無法布通的問題。

因此，本領域的技術人員致力于開發一種既可以保持相對于專用集成電路(ASIC)的較高性能，又可以實現類似FPGA一樣的高自由度，布通率更高的異構可重構陣列布局方法。

發明內容

有鑒于現有技術的上述缺陷，本發明所要解決的技術問題是提高異構可重構陣列處理器的布通率。

為實現上述目的，本發明提供了一種基于多階段模擬退火的靜態異構可重構陣列布局方法，其特征在于，利用圖距離來構建異構資源的位置約束，利用分階段模擬退火的方法來分離所述異構資源在同一次所述模擬退火中的相互影響。

進一步地，所述圖距離是將DFG圖無向化之后，兩點間的最短路徑的邊數。

進一步地，所述模擬退火分為三個階段，LC退火階段，LS退火階段和PE退火階段。

進一步地，在所述PE退火階段，采用VPR中的線性擁擠函數來建模。

進一步地，在所述LS退火階段與所述LC退火階段，采取棋盤距離與所述圖距離結合的代價函數來建模。