並行高斯算法

Question

我想並行化這種高斯算法。我找不到任何解決方案與其他進程共享循環中的計算。是否有機會並行化整個代碼或代碼片段？

for k=1:n-1 
for i=k+1:n 
    M(i,k) = M(i,k)/M(k,k); 
    a(i) = a(i) - a(k)*M(i,k); 
    for j=k+1:n 
     M(i,j) = M(i,j) - M(k,j)*M(i,k); 
    end 
end end 

起初，這是一個理論問題。在我有解決方案之後，我想用OpenMPI對此代碼進行編程。

非常感謝！ 約翰

Answer 1

高斯消除確實是一個強烈的順序過程。在完成上一個淘汰步驟之前，您不能選擇一個數據透視元素。消除可以通過給處理單元分配一段行來並行化，但是要更新的數組的分數會逐漸減少（按原樣）。

另一種方法可以是塊分解，在農業模式下將塊分配給處理單元。這裏再一次難以保持所有PU的繁忙。