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

無效

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

技術領域

本發明涉及單線程程序并行化的領域，尤其涉及一種基于數據流分析的單線程程序并行化的實現方法。

背景技術

隨著電子技術的發展，電子芯片的制造工藝由原來的90nm減小到65nm、45nm，現在甚至還出現了32nm的芯片，制造工藝的改進使得固定面積的芯片可以集成更多的晶體管，進而也使得單個芯片上可以被設計成更復雜的結構和更多的計算資源；同時較高的芯片集成度使得原來通過提高芯片工作頻率的做法不再有效，一方面芯片的電路延時使得芯片的頻率不能被無限提升，另一方面，過高的頻率帶來了更高的能耗，使得高集成度的芯片散熱成為一個巨大的問題。為了解決上述問題，更好和更合理的利用單個芯片上的資源，芯片多處理器(Chip?Multi?Processor，CMP)結構就應運而生了。CMP集成多個處理器核在單個芯片上，不僅能夠解決能耗和散熱的問題，同時能夠是芯片具有更好的并行性。CMP同時帶來的一個問題是當面對傳統的基于單核結構而設計的單線程程序，CMP并不能夠取得良好的加速比，甚至在有些時候，單線程程序在CMP上的運行性能還不如結構復雜的單核處理器。

現在在CMP上提高單線程程序性能的主要方法是探索單線程程序的并行部分，這樣不同的計算資源就能夠同時運行實現并行性。比較常用的實現并行的手段有指令級的并行(Instruction?Level?Parallelism，ILP)，線程級的并行(ThreadLevel?Parallelism，TLP)和投機(Speculation)。指令級的并行是一種粒度較小的并行手段，它主要實現指令的并行執行，指令級并行在單核處理器中同樣被使用，現在使用的多級指令流水技術，超長指令字等方法都是指令級的并行方法。

線程級的并行或稱為軟件級的并行主要是把一個單線程程序抽取成多線程程序，這些多線程程序并行執行從而實現程序的并行執行。線程級并行的實現方式很多，它是一種粒度較大的并行方式。例如在某些科學計算和多媒體應用的環境中，由于程序所處理的數據前后依賴性不強，所以可以同時處理原始數據中的不同部分，這種方式叫做數據級的并行，是一種線程級并行；再譬如在程序的某個循環中，可以把循環分解成前后的不同部分，前面部分的輸出可以作為后面部分的輸入，進而形成前后部分的流水讓前后兩部分并行執行，這種方式叫做軟件級的流水，也是一種線程級并行。

投機也是實現程序并行的一種方法，它通過預測來提前執行程序的某一個部分，如果這個部分在將來被執行，那么它的結果可以直接被使用，如果將來未被執行，那么只要拋棄先前執行的結果便可。投機是現在研究中的一個重要方向，有許多不同的方法來實現投機，但是當投機錯誤的時候，它并不能改變程序的性能，甚至有可能損失一部分程序性能。投機的粒度變化較大，小可以小的一條匯編指令，大可以大到一個循環部分或者一個函數。

無論人們如何嘗試著程序并行化的方法，程序中指令前后的依賴性是限制程序并行的最主要約束，建立新的編程模型可能能夠使得程序之間的依賴關系有所改善，但是由于任務的過程性，程序之間的依賴關系不可能被消除，所以現在所做的一切關于并行的研究都是建立在依賴性的基礎上的。程序內部的依賴關系有控制依賴和數據依賴兩種，但是如果需要并行的執行某一段代碼，反向的依賴關系也是必須考慮的一個問題，反向的相關存在于指令級的并行和線程級的并行當中，例如處理器的亂序執行，投機和軟件流水。

通常在程序執行的某一個時刻存在多個數據流，這些數據流相互交織在一起組成了程序的執行流程。事實上，在具有控制依賴關系的指令之間，如果把控制條件的值作為后面指令的輸入的話，那么控制依賴也可以被當成是一種數據上的依賴。加之程序中本身存在的反向的依賴關系，那么可以簡單的確定程序中的某些指令必定執行在另外一些指令之后。在編譯器的優化技術中，指令之間的依賴關系和程序的數據流都是程序優化的基礎。

生產者消費者方式是解決多線程程序在線程之間通信的一個方法，這個方法一般通過指定內存的某一塊區域為存放通信內容的倉庫，生產者線程向倉庫中存放需要通信的內容，而消費者線程從倉庫中得到所需要通信的內容。根據生產者消費者的軟件模型可以構建出一個生產者消費者的硬件架構。

發明內容

一種基于數據流分析的單線程程序并行化的實現方法能夠自動把單線程程序抽取成多線程程序，使之適合在多核結構上并行運行從而提升程序性能，它是一種編譯技術。

本發明解決技術問題所采用的技術方案是：

1)分解算法的實現：