多項式乘法CilkPlus

Question

我試圖使用cilk_for使這個代碼的並行的Cilk代碼：串行代碼

c[0:2*n-1] = 0; 
    for (size_t i=0; i<n; ++i) 
     c[i:n] += a[i]*b[0:n]; 

：

for(size_t j=0; j<2*n-1; ++j) 
     c[j] = 0; 
    for (size_t i=0; i<n; ++i) 
     for(size_t j=0; j<n; ++j) 
      c[i+j] += a[i]*b[j]; 

例如：

x^2+x+1 
2x^2+3x+5 


C[0]=A[0]·B[0] 
C[1]=A[0]·B[1]+A[1]·B[0] 
..... 

Answer 1

最簡單的方法是編寫一個循環遍歷輸出係數的cilk_for循環，並在循環內部爲每個輸出係數累加內部產品。

調用輸出係數c [k]。循環將是這樣的：

cilk_for(k=0; k<2n-1; ++k) 
    c[k] = __sec_reduce(a[...:...]*b[...:...:-1]); 

的...需要是產生有助於每個輸出係數小節表達式。我有一個間歇性的互聯網連接，所以我將它作爲練習留給讀者。

該書的下載站點（http://parallelbook.com/downloads）具有比上述方案漸近更快的遞歸版本。