contents
題目描述
給定一序列矩陣，期望求出相乘這些矩陣的最有效方法的乘法次數。
sequence.c
|
|
輸入格式
有多組測資，每組第一行會有一個整數 $N$ 表示矩陣鏈上有 $N$ 個矩陣，第二行上會有 $N+1$ 個整數 $Z_i$，表示矩陣鏈的每一個行列大小，例如當 $N = 3$ 時，輸入 10 30 5 60 表示矩陣 $A_{10, 30} B_{30, 5} C_{5, 60}$ 相乘。
- $1 \le N \le 4096$
- $1 \le Z_i \le 4096$
輸出格式
對於每組測資輸出一行一個整數 $M$ 為最少乘法次數。
範例輸入
|
|
範例輸出
|
|
Solution
假設有 $p$ 個處理單元，矩陣大小為 $n \times n$，分析一般平行運算時間 $T_p$ 如下所示：
$$\begin{align*} T_p &= \sum\limits_{k=1}^{n} \left\lceil \frac{k}{p} \right\rceil \times (n - k) \end{align*}$$針對地 $k$ 次迭代，將第二層迴圈平行化，每一個執行緒處理 $\left\lceil \frac{k}{p} \right\rceil$ 個狀態計算，每個狀態繼續需要 $n-k$ 次計算。
$$\begin{align*} \sum\limits_{k=1}^{n} \left\lceil \frac{k}{p} \right\rceil \times k &= 1 \times (1 + 2 + 3 + \cdots + p) + \\ & \qquad 2 \times ((p+1) + (p+2) + (p+3) + \cdots + 2p) + \cdots + \\ & \qquad (n \bmod{p}) \times \left\lceil \frac{n}{p}\right\rceil (\lfloor n/p \rfloor \times p + 1 + \cdots + n) \\ &= \sum_{k=1}^{\lfloor n/p \rfloor} k \cdot \frac{p (2k+1) p}{2} + (n \bmod{p}) \times \left\lceil \frac{n}{p}\right\rceil \frac{(n \bmod{p})(n + \left\lfloor \frac{n}{p}\right\rfloor p + 1)}{2} \\ &= p^2 \left[ \frac{\left\lfloor n/p \right\rfloor(\left\lfloor n/p \right\rfloor+1)(2 \left\lfloor n/p \right\rfloor + 1)}{6} + \frac{\left\lfloor n/p \right\rfloor(\left\lfloor n/p \right\rfloor+1)}{4} \right] + (n \bmod{p})^2 \left\lceil n/p \right\rceil \frac{n + \left\lfloor n/p \right\rfloor p + 1}{2} \\ \sum\limits_{k=1}^{n} \left\lceil \frac{k}{p} \right\rceil \times n &= n \cdot p \cdot \frac{\left\lfloor n/p \right\rfloor (\left\lfloor n/p \right\rfloor + 1)}{2} + n \cdot (n - p \cdot \left\lfloor n/p \right\rfloor) \left\lceil n/p \right\rceil \end{align*}$$總結一下 $T_p = \sum\nolimits_{k=1}^{n} \left\lceil \frac{k}{p} \right\rceil \times n - \sum\nolimits_{k=1}^{n} \left\lceil \frac{k}{p} \right\rceil \times k = O(n^3 / p)$
針對前半段 $\sum\limits_{k=1}^{n} \left\lceil \frac{k}{p} \right\rceil$ 有以下兩種推法可供參考。
方法一
$$\begin{align*} \sum\limits_{k=1}^{n} \left\lceil \frac{k}{p} \right\rceil &= p \cdot 1 + p \cdot 2 + p \cdot 3 + \cdots + p \cdot \left\lfloor n/p \right\rfloor + (n \bmod{p}) \cdot \left\lceil n/p \right\rceil \phantom{0\over0}\\ &= \sum\limits_{k=1}^{\left\lfloor n/p \right\rfloor} k \cdot p + (n - p \cdot \left\lfloor n/p \right\rfloor) \left\lceil n/p \right\rceil \\ &= p \cdot \frac{\left\lfloor n/p \right\rfloor (\left\lfloor n/p \right\rfloor + 1)}{2} + (n - p \cdot \left\lfloor n/p \right\rfloor) \left\lceil n/p \right\rceil && \blacksquare \end{align*}$$方法二
套用定理如下：(解釋： $n$ 個人分成 $p$，每組人數最多差一。)
$$\begin{align} n = \left\lceil \frac{n}{p} \right\rceil + \left\lceil \frac{n-1}{p} \right\rceil + \cdots + \left\lceil \frac{n-p+1}{p} \right\rceil \end{align}$$套用上式從 $k = n$ 往回推。
$$\begin{align*} \sum\limits_{k=1}^{n} \left\lceil \frac{k}{p} \right\rceil &= \left\lceil \frac{n}{p} \right\rceil + \left\lceil \frac{n-1}{p} \right\rceil + \cdots + \left\lceil \frac{n-p+1}{p} \right\rceil + \sum_{k=1}^{n-p} \left\lceil \frac{k}{p} \right\rceil \\ &= n + (n - p) + (n - 2p) + \cdots + (n - \lfloor n/p \rfloor \cdot p) + \sum_{k=1}^{n \bmod{p}} \left\lceil \frac{k}{p} \right\rceil \\ &= \sum\limits_{k=0}^{\left\lfloor n/p \right\rfloor - 1} (n - k p) + (n \bmod{p}) \\ &= n \left\lfloor n / p \right\rfloor - \frac{\left\lfloor n/p \right\rfloor (\left\lfloor n/p \right\rfloor - 1)}{2} \times p + (n \bmod{p}) && \blacksquare \end{align*}$$基礎平行
- Accepted (50883 ms, 132224 KB)
平行地方呼之欲出，針對第二層迴圈直接平行化即可，下述代碼會帶入一點累贅，其原因在於做了各種實驗所致，但不影響正確性。只做了減少 thread 建立時的 overhead 的處理。
|
|
進階平行
- Accepted (9890 ms, 136320 KB)
從一般平行實驗結果中，發現明顯地加速倍率不對，明明使用 24 個核心，跑起來不到兩倍加速的原因到底在哪？是的，在第三層存取順序需要 dp[l][k] 和 dp[k+1][r] 隨著 $k$ 變大，在前者存取順序是連續的，而在後者存取順序每一次跳躍長度為 $N$，導致 dp[k+1][r] 常常會發生 cache miss，一旦發生 cache miss，需要數百的 cycle 等待資料被帶進記憶體中。
由於矩陣鍊乘積計算時只用了矩陣的上三角，那複製一份到下三角矩陣去吧！dp[l][r] = dp[r][l]，如此一來在第三層迴圈發生 cache miss 的機會就大幅度下降。
|
|
忘卻快取平行
Accepted (4264 ms, 134400 KB)
參考論文 High-perofrmance Energy-efficient Recursive Dynamic Programming with Matrix-multiplication-like Flexible Kernels
最主要的精神 cache-oblivious algorithm 設計，利用大方陣切割成數個小方陣，矩陣跟矩陣之間在足夠小的情況下進行合併計算。算法概述如下：
每一個函數參數中的藍色區塊答案算出，而其他參數則是要合併的左矩陣和下矩陣，直到計算大小足夠小時，直接跑序列版本的程式，此時所有陣列可以全部帶進快取，這時候計算變得更加有利。再加上很多層的快取，每一個 CPU 的 cache 重複使用率相當高。
一般的平行度最高只有 $N$，因為我們只針對其中一個迴圈平行，而在 cache-oblivious algorithm 中，平行度最高為 $N^{1.415}$。這些都只是理論分析，實作時為了考慮硬體架構是沒辦法達到理想狀態的。
|
|