基本介紹
- 中文名：Cilk
- 所屬：英特爾
- 類別：語言擴展技術
- 主要用途：發掘多處理器能力變得更加容易
Cilk 技術主要用途,使用 Cilk 技術,Cilk 技術套用實例,Cilk 中的 Reducer 視圖,
Cilk 技術主要用途
Cilk 技術的設計特別適合但不限於 “divide 和 conquer” 的算法。它將問題分解成可以獨立完成的子問題（任務），然後再將這些執行結果合併起來。另外，對於那些常常使用 “divide 和 conquer” 算法的遞歸函式， Cilk 技術同樣也支持得很好。 任務既可以在不同的函數裡實現，也可以在一個疊代的循環中完成。Cilk 關鍵字能有效地標識可並行執行的函式調用和循環，同時，Cilk 技術的運行環境能有效率地將這些任務調度到空閒的處理器上運行。
使用 Cilk 技術
下面描述了使用 Cilk 技術創建一個並行程式的操作步驟：
通常，要有一個已經實現了基本功能的串列 C++ 程式。要確保該串列程式是正確無誤的。因為雖然在串列程式中的任何 bug 仍會在並行程式中發生，但是這些 bug 在並行程式中將更加難以辨別和調試。找出程式中可以從並行操作中獲益的代碼段。那些執行時間相對長，並且能獨立執行的操作是首選修改目標。用三個 Cilk 關鍵字標明那些能並行執行的任務： _Cilk_spawn（或 cilk_spawn, 如果程式包含了 cilk.h 檔案）表示對一個函式（“子”）的調用，能與調用者（“父”）一起被並行處理。 _Cilk_sync（或 cilk_sync, 如果程式包含了 cilk.h 檔案）表示所有衍生的“子”函式完成後，才能繼續後續代碼執行。 _Cilk_for（或 cilk_for, 如果程式包含了 cilk.h 檔案）表示一個循環包含的疊代可以被並行執行。編譯程式： Window* 作業系統：選擇使用 icl 命令行工具，或者在微軟的 Visual Studio* 下進行編譯。如果使用 Visual Studio* 進行開發，確保已經從英特爾® Parallel Composer 相關選單中選擇了“Use Intel C++” Linux* 作業系統：使用 icc 命令執行程式。如果沒有競爭條件，並行程式將輸出和串列程式相同的結果。通過使用 reducer，鎖，或者重寫代碼解決任何由於競爭條件而產生的衝突問題。
Cilk 技術套用實例
下面以 Quicksort 為例，演示如何用 Cilk 技術編寫一個並行化程式。
其中使用函式名 sample_qsort 以避免和標準 C 函式館中的 qsort 函式的衝突。例中的一些語句行被刪除，但是保留了相應的行號。
9 #include <algorithm>1011 #include <iostream>12 #include <iterator>13 #include <functional>1415 // Sort the range between begin and end.16 // "end" is one past the final element in the range.19 // This is pure C++ code before Cilk conversion.2021 void sample_qsort(int * begin, int * end)22 {23 if (begin != end) {24 --end; // Exclude last element (pivot)25 int * middle = std::partition(begin, end,26 std::bind2nd(std::less<int>(),*end));28 std::swap(*end, *middle); // pivot to middle29 sample_qsort(begin, middle);30 sample_qsort(++middle, ++end); // Exclude pivot31 }32 }3334 // A simple test harness35 int qmain(int n)36 {37 int *a = new int[n];3839 for (int i = 0; i < n; ++i)40 a[i] = i;4142 std::random_shuffle(a, a + n);43 std::cout << "Sorting " << n << " integers" << std::endl;4445 sample_qsort(a, a + n);4849 // Confirm that a is sorted and that each element // contains the index.50 for (int i = 0; i < n-1; ++i) {51 if ( a[i] >= a[i+1] || a[i] != i ) {52 std::cout << "Sort failed at location i=" << i << " a[i] = "53 << a[i] << " a[i+1] = " << a[i+1] << std::endl;54 delete[] a;55 return 1;56 }57 }58 std::cout << "Sort succeeded." << std::endl;59 delete[] a;60 return 0;61 }6263 int main(int argc, char* argv[])64 {65 int n = 10*1000*1000;66 if (argc > 1)67 n = std::atoi(argv[1]);6869 return qmain(n);70 }現在，可以開始在 qsort 程式中引入並行。
Cilk_spawn 關鍵字表示一個函式（“子”）可以和其後語句（“父”）並行執行。關鍵字允許但不要求並行操作。當系統有多個處理器可用時 Cilk 技術會動態地決定哪些操作會被並行執行。
_Cilk_sync 語句表示它將等待同一函式中的所有_Cilk_spawn請求被處理完成後，該函式才能繼續執行。_Cilk_sync 語句不會影響在其他函式中衍生的並行 strand（strand 是一串沒有任何並行控制的串列指令序列）。
21 void sample_qsort(int * begin, int * end)22 {23 if (begin != end) {24 --end; // Exclude last element (pivot)25 int * middle = std::partition(begin, end,26 std::bind2nd(std::less<int>(),*end));28 std::swap(*end, *middle); // pivot to middle29 _Cilk_spawn sample_qsort(begin, middle);30 sample_qsort(++middle, ++end); // Exclude pivot31 _Cilk_sync;32 }33 }通過在程式中包含頭檔案 <cilk.h>，前面的用例可以用簡化的 Cilk 關鍵字形式來重新編寫。新的宏提供了沒有下劃線的小寫方式的命名。下面的程式行顯示了用簡化命名的 cilk_spawn 和 cilk_sync。
19 include <cilk.h>21 void sample_qsort(int * begin, int * end)22 {23 if (begin != end) {24 --end; // Exclude last element (pivot)25 int * middle = std::partition(begin, end,26 std::bind2nd(std::less<int>(),*end));28 std::swap(*end, *middle); // pivot to middle29 cilk_spawn sample_qsort(begin, middle);30 sample_qsort(++middle, ++end); // Exclude pivot31 cilk_sync;32 }33 }在上述兩例中，第 29 行的語句將衍生出對 sample_qsort 的一次可異步執行的遞歸調用。這樣，當 sample_qsort 在第 30 行再次被調用時，第 29 行的語句可能還沒有執行完成。在第 31 行的 cilk_sync 語句表示在同一函數裡的所有 cilk_spawn 請求執行完成前，該函式不能繼續執行。
在每一個函式的末尾都有一個系統隱含的 cilk_sync 用來等待當前函式衍生的所有任務完成，所以第 31 行的 cilk_sync 語句是多餘的，但是這裡為了使代碼更清晰而加入了這行。
上面的改動採用了一個典型的二分法策略來實現遞歸算法的並行化。在每一層的遞歸調用中，會產生一個兩路的並行；“父” strand （第29行）繼續執行當前的函式；而“子” strand 執行其他遞歸調用。這種遞歸調用能產生相當多的並行運算。
Cilk 中的 Reducer 視圖
Reducer視圖 (The Reducer View)這裡我們來討論一下Cilk中的Reducer視圖。在Cilk中， Reducer是我們支持的一種超級對象(Hyperobject)。什麼是超級對象？ 他是一種被cilk運行環境支持的構件，使多個strand能互不影響地訪問共享變數和數據結構，它是通過同時提供給每個strand一個超級對象的不同視圖來實現。Reducer是我們目前唯一支持的超級對象。 根據超級對象的概念我們可以知道， 視圖(View)其實是超級對象的一個狀態。視圖作為輸入(input)提供給strand， 不同的strand具有不同的Reducer視圖， 他們根據該視圖可以互不影響的訪問共享變數和數據。
理解了Reducer視圖的概念，那么Cilk運行系統如何產生一個Reducer 視圖呢？ 我們同樣用一個例子來說明視圖的生成。
假設我們有下面這樣一些任務。
mywork (1);A: cilk_spawn mywork(3)mywork(2)B: cilk_sync;mywork(4)
我們知道， cilk_spawn衍生出一個新的可以並行執行的任務。 這時可以分為密取發生和不發生兩種情況。當密取不發生的時候， 如下圖所示， 此時的程式執行是串列的， 沒有新的執行緒來並行執行， 也就沒有新的Reducer 視圖被創建。
當密取行為發生的時候，如下圖所示， 此時在A點， 我們的主執行緒(I)有一個Reducer的當前執行視圖(V1)， 執行緒(I)執行strand (3), strand(3)中使用的視圖就是V1. 另一執行緒(II)密取工作strand (2), 這時strand(2)會得到一個新的Reducer視圖(V2)。新生成的V2擁有Reducer的恆等值(identity value)， strand(2)基於該V2進行操作。 在B點進行Reducer同步的時候，新生成的V2與原來的視圖V1進行合併。 合併後， V2被註銷。 strand(4) 繼續基於V1進行操作。
理論上說， 我們可以理解為每個strand都有一個reducer的私有視圖。然而基於性能的考慮， 視圖的產生是延遲的(Lazy semantics)。並不是每一次的衍生調用都會有新的視圖的生成。新視圖的創建了必須符合下面兩個條件:1. 首先，新的視圖的創建必須在密取行為發生之後。 如果密取行為沒有發生， 程式的執行其實是線性的。 這時就沒有必要產生新的視圖。
2. 其次， 只有在新的strand裡面首次存取reducer的時候，新的視圖才會被創建。 也就是說， 當密取行為發生後， 視圖也不是馬上被創建出來的。 如果在新的strand裡面沒有基於reducer的存取操作， 那么我們是沒有必要產生新的reducer視圖的。如果新的strand裡面有對reducer的存取操作， 那么在首次存取該reducer的時候， 系統才會在該存取點創建新的視圖實例。
如果新的視圖被創建， 他會在cilk_sync點與先前的視圖進行合併。 如果沒有新的視圖生成， 合併是不必要的。
