[發明專利]基于數據流分析的單線程程序并行化的實現方法

無效

• 申請號: 200910097147.6
• 申請日: 2009-03-23
• 公開（公告）號: CN101515231A
• 公開（公告）日: 2009-08-26
• 發明（設計）人: 陳天洲;蔣冠軍;繆良華;王超;陳劍
• 申請（專利權）人: 浙江大學
• 主分類號: G06F9/38
• 分類號: G06F9/38
• 代理公司: 杭州求是專利事務所有限公司
• 代理人: 林懷禹

1.一種基于數據流分析的單線程程序并行化的實現方法，其特征在于：

1)分解算法的實現：

分解算法是把單線程程序分解成多個線程的算法實現，這個算法根據聯合依賴關系圖當中的指令依賴性，把單個線程分解成兩個或多個線程，分解算法是一個遞歸的過程，它首先作出非嵌套循環或者無循環部分的聯合依賴關系圖，根據原程序中指令執行的時間以及數據依賴關系，向圖中的節點和邊的添加屬性，之后是圖的分解過程，分解算法考慮的是分解后線程的通信代價和線程之間的平衡性，把圖中的節點分配到不同的組中，組成不同的線程，然后向線程中插入生產者消費者指令，分解后，被分解的部分被當作一個節點插入原來代碼當中，分解算法繼續分解新組成的代碼中的非嵌套循環部分，如此遞歸進行，直到分解完整個需要分解的代碼；

2)根據指令依賴關系作出聯合依賴關系圖：

單線程程序指令之間存在兩種依賴關系，分別是指令之間的數據依賴和控制依賴。當單線程程序別分解成多個線程而并行執行的時候，還存在反向的數據依賴關系。聯合依賴關系圖是混合這三種依賴關系的圖，它的作法是這樣的：首先以程序中的指令作為圖的節點，然后根據指令之間的依賴關系添加上述的三種依賴關系。在添加完依賴關系以后，以圖中不存在依賴的節點為起始節點，消除與這些節點連接的所有邊，查找圖中新的不存在依賴的節點，取出這些節點加入到起始節點的集合中，在起始節點的集合中添加新節點與舊節點在程序執行中的先后關系，消除新節點在原來依賴圖中所有與之相連的邊。這樣循環進行直到所有節點被添加到起始節點集合為止；

3)函數、過程內聯和程序中三種基本元素的分解：

函數和過程會使指令流跳出到被分解部分的代碼，這使得分解過程難以繼續進行，因此需要把被分解代碼部分內的函數和過程被內聯進來。基本塊、條件分支和循環是程序的三種基本元素，循環被分解算法作為基本分解單元，分支和循環需要控制條件值的傳遞，基本塊可以被直接分解，但會存在數據依賴和反向數據依賴；

4)生產者消費者通信模式及硬件實現：

分解后線程之間的通信通過生產者消費者方式解決，生產者消費者需要在倉庫中存儲和消費所通信的值，如果以內存為倉庫，由于內存的速度慢，對內存的讀寫影響分解后線程的性能，為了能夠更快的完成生產者消費者，減少通信代價，一種硬件的實現可以有效的改進效率；

5)分解后線程間通信的一個特殊例子考慮：

對于生產者消費者的實現，有一個特殊的例子需要被考慮，當消費者消費的值有可能來自分支或循環內部，也有可能來之分支或循環前面時生產者需要在一個特定的點生產或者向倉庫中的同一個單元進行生產，不然消費者得到的值可能是錯誤的或者過時的。