並行矩陣產品

Question

爲了計算並行模式下2個矩陣A和B（nxm維度）之間的乘積，我有以下限制：服務器向每個客戶端發送來自矩陣A的若干行，來自矩陣B的行。這不能改變。此外，客戶可以在彼此之間交換信息，以便計算矩陣產品，但是他們不能要求服務器發送任何其他數據。

這應做最有效的可能，通過最小化進程之間發送的消息的數量意思 - 視爲一個昂貴的操作 - 並且通過這樣做小的計算並行地，儘可能多地。

據我的研究，客戶之間交換的實際消息的次數最多爲n^2，在情況下，每個進程廣播其線路連接到所有其他人。現在，問題是，如果我最小化發送的消息數 - 這將圍繞分發輸入數據的log（n） - 但計算只能由一個進程完成，或者更多，但無論如何，它不是再一次平行完成，這是問題的主要思想。

什麼可能是一個更有效的算法，可以計算這個產品？

（我正在使用MPI，如果它有任何區別）。

Answer 1

爲了計算矩陣乘積C = A x B元素的元素，你簡單地計算C(i,j) = dot_product(A(i,:),B(:,j))。也就是說，C的（i，j）元素是A的第i行和第j列的點積。

如果你堅持發送A行和B行的行，那麼你將有編寫一個並行程序的難度很大，它的性能超過了一個簡單的串行程序。相反，你應該做的是發送行A和B的列到處理器計算C的元素。如果你被約束髮送A行和B行，那麼我建議你這樣做，但計算產品在服務器上。也就是說，忽略所有的工作處理器，只是連續執行計算。

一種替代方法是計算工作人員處理器上的部分點積並累積部分結果。這將需要一些棘手的編程;它可以完成，但如果在第一次嘗試時，您可以編寫一個優於簡單串行程序的程序（在執行速度上），我會感到非常驚訝。

（是的，還有其他的方法來分解矩陣，矩陣產品，爲並行執行，但他們比前面更爲複雜。如果你想調查這些然後Matrix Computations是開始閱讀的地方。）

您還需要認真思考您提出的效率衡量標準 - 最有效的信息傳遞程序將是不傳遞任何信息的程序。如果消息傳遞的成本遠遠超過計算成本，那麼無信息傳遞的實現將是兩種方法最有效的。一般來說，並行程序的效率度量是加速比與處理器數量的比率：所以在8個處理器上的8倍加速是完全有效的（並且通常不可能實現）。

正如你所說的是不是一個明智的問題。問題制定者可能錯誤地指定了它，或者你錯誤地陳述了（或誤解了）正確的規範。

Answer 2

某些東西不對：如果兩個矩陣都有n x m尺寸，則它們不能相乘（除非n = m）。在A * B的情況下，A必須具有與B具有行數一樣多的列。你確定服務器沒有發送B的轉置行嗎？這相當於從B發送列，在這種情況下解決方案是微不足道的。

假設所有這些都檢出，並且您的客戶確實從A和B獲得了行：最簡單的解決方案可能是爲每個客戶端將其行的矩陣B發送到客戶端＃0，該客戶端重新對原始矩陣B ，然後將其列發送回其他客戶端。基本上，客戶＃0將作爲一個真正知道如何有效分解數據的服務器。這將是2*(n-1)消息（不包括用於統一產品矩陣的消息），但考慮您如何在客戶端之間分配A和B矩陣的消息，沒有顯着的性能損失（它仍然是O(n)消息）。

這裏最大的瓶頸顯然是矩陣B的初始聚集和重新分配，這個矩陣非常可縮放，所以如果你有相當小的矩陣和很多進程，你可能會更好地在服務器上串行計算產品。

Answer 3

我不知道這是否是功課。但如果它不是家庭作業，那麼你應該使用一個圖書館。一種想法是ScaLAPACK的

http://www.netlib.org/scalapack/scalapack_home.html

的ScaLAPACK在FORTRAN writtten，但你可以從C調用它++。