並行乘以小矩陣

Question

我一直在編寫代碼來使用POSIX線程並行乘以矩陣，並且在大矩陣上操作時我已經看到了很大的加速;然而，當我縮小矩陣的大小時，天真的連續O（n^3）矩陣乘法算法開始超過並行實現的性能。

這是正常還是表示質量較差的算法？難道我只是注意到創建和處理線程的額外開銷，並且超過了某個時間點，額外的時間佔據了計算的主導地位？

注意，這是一個家庭作業，所以我不會被張貼我的代碼，我不想破壞我的大學的學術誠信政策。

Answer 1

不可能給出一個確切的答案沒有看到代碼（或算法的詳細描述，至少），但一般是正常的簡單算法來上，因爲較小的恆定的小輸入更好執行因子。此外，線程創建/上下文切換不是免費的，因此創建線程然後執行一些簡單的計算可​​能需要更長的時間。因此，如果您的算法在大型輸入上的工作速度比天真的快得多，那麼應該沒有理由擔心它。