MATLAB 程式設計入門篇 程式碼與記憶體之最佳化

Presentation on theme: "MATLAB 程式設計入門篇 程式碼與記憶體之最佳化"— Presentation transcript:

1 MATLAB 程式設計入門篇 程式碼與記憶體之最佳化
張智星 清大資工系 多媒體檢索實驗室

2 2-1 程式碼的向量化 6.5 版之前，MATLAB 程式環境是一個傳統的解譯器（Interpreter），在執行 MATLAB的程式碼時，會進行下列動作: 逐列對程式碼轉換為 p-code，這是 MATLAB 可以解讀的格式。 對產生的 p-code 進行逐列執行。

3 2-1 程式碼的向量化 在執行每一列 p-code 時，都還包含一些「經常開銷」（Overhead）
該列執行需要大量運算，經常開銷就會顯得很渺小而不會拖累程式執行速度。 該列只是簡單的運算，那經常開銷的比例就會相對提高 該列是放在迴圈內，那麼程式碼的執行速度就會被這些經常開銷大幅拖慢。

4 2-1 程式碼的向量化 若要加快執行速度 對向量化運算來進行說明，主要著眼點在於：
MATLAB 6.5 版之前，就要盡量不使用迴圈 ，而盡量改用向量化的運算，以降低經常開銷的比例。 MATLAB 6.5 版（含）之後，已經加入了 JIT-Accelerator，有效地降低了經常開銷的比例，同時也使得向量化程式碼的重要性越來越低。 對向量化運算來進行說明，主要著眼點在於： 很多舊的程式碼還是包含向量化的運算。 MATLAB 6.5 之前的版本，向量化的運算還是提高執行效率的主要關鍵。 某些情況下，JIT-Accelerator 的效能無法完全發揮，還是需要配合向量化的運算才可以讓程式碼更有效率。

5 2-1 程式碼的向量化 計算 n 項調和數列的總和，若使用 for 迴圈，當 n = 100,000 時，可計算其執行時間如下：
範例2-1：hsum01.m tic n = ; total = 0; for i = 1:n total = total+1/i; end toc elapsed_time =

6 2-1 程式碼的向量化 由上可知，當 n = 100,000 時，使用 for 迴圈的程式碼約需 2.63 秒才能執行完畢。若改用向量化的運算，可計時如下： 範例2-2：hsum02.m tic n = ; sequence = 1:n; total = sum(1./sequence); toc elapsed_time = 0.0600

7 提示 上述的測試時間是根據Pentium-450, 256 MB RAM在 MATLAB 6.1 所得到的結果。如果你的電腦更快，計算時間的差異性就不會那麼顯著。 在 MATLAB 6.5 版之後，採用了 JIT (Just-In-Time) 的編譯技術，因此「向量化」和「非向量化」的程式執行速度，已經幾乎沒有差異。

8 2-1 程式碼的向量化 要能夠熟練地運用向量化的運算，有下列三要素： 對矩陣的索引（Indexing）非常熟悉。
對 MATLAB 可用的內建（Built-in）指令非常瞭解。

9 2-1 程式碼的向量化 一矩陣 x，若要將 a 的每一個元素乘上 x 的每一個直行，我們可使用內建的 diag 指令來達成此功能，例如：
範例2-3： colMultiply01.m x = [1 2 3; 1 1 1]; a = [3 2 1]; y = x*diag(a) y =

10 2-1 程式碼的向量化 使用 diag 指令，也可以將 a 的每一個元素乘上 x 的每一個橫列，例如：
範例2-4： rowMultiply01.m x = [1 2 3;4 5 6]; a = [3 1]; y = diag(a)*x y =

11 2-1 程式碼的向量化 將一個行向量拷貝 n 份，可執行如下： 範例2-5：copyCol.m
a*ones(1, n) 也可以產生相同的效果。 n = 10; a = [1 3 7]'; rep = a(:, ones(1,n)) rep =

12 2-1 程式碼的向量化 將一個列向量拷貝 n 份，可執行如下： 範例2-6：copyRow.m
ones(n, 1)*a 也可以產生相同的效果。 n = 5; a = [1 4 8]; rep = a(ones(1,n), :) rep =

13 2-1 程式碼的向量化 將一個 m×n 矩陣 A 拷貝 M×N 次,並安排成維度大小為(M*m)×(N*n)的大矩陣，可輸入如下：
範例2-7：copyMatrix.m A = [1 2 3; 4 5 6]; m = size(A, 1); n = size(A, 2); M = 3; N = 2; mIndex = (1:m)'*ones(1,M); nIndex = (1:n)'*ones(1,N); B = A(mIndex, nIndex) B =

14 2-2 JIT加速器 6.5 版後，MATLAB 引進了 JIT (Just-In-Time) 的編譯技術，簡稱 JIT 加速器（JIT-Accelerator） 大幅地降低了迴圈的執行效率。 使得一般程式碼的撰寫，可以使用程式設計師最能代表演算法精神的方式來呈現。 不必為了提高效率、勉強使用向量化運算，造成程式碼維護的困難。

15 2-2 JIT加速器 向量化運算可以提高執行速度達到 40 倍之多，但是在 JIT 加速器的運作下，向量化運算的光環不在，測試範例如下：
範例2-8：hsum03.m ns = 1000:1000:100000; for i=1:length(ns) n = ns(i); % 第一種方法：for-loop operation tic total = 0; for j = 1:n total = total+sin(1/j); end

16 2-2 JIT加速器 由此圖可以看出，time1/time2 的值都在 1 左右，甚至常比 1 還低，顯示 JIT 加速器的效能非常優異。
time1 = toc; % 第二種方法：vectorized operation tic total = sum(sin(1./(1:n))); time2 = toc; % 計算倍數 ratio(i)=time1/time2; end plot(ns, ratio, '.-'); grid on xlabel('n'); ylabel('time1/time2'); 由此圖可以看出，time1/time2 的值都在 1 左右，甚至常比 1 還低，顯示 JIT 加速器的效能非常優異。

17 2-2 JIT加速器 JIT 加速器的主要功能，列出如下： JIT 加速器可以分成兩部分：
JIT 加速器可將每一列 MATLAB 程式碼直接轉成「原機指令」，而不再直接使用 p-code，因此省去大部分 p-code 會遇到的經常開銷。 JIT 加速器也會對 Intel X86 為主的 Windows 及 Linux 進行程式碼最佳化。 JIT 加速器可以分成兩部分： Just-In-Time Code Generation：將 p-code 轉成原機指令。 Runtime Type Analysis：對資料型態的分析，以便用於 Just-In-Time Code Generation

18 2-2 JIT加速器 有了 JIT 加速器，是否還要使用向量化運算呢？基本的判斷原則如下：
所用的向量化運算是根基於「以空間換取時間」，就必須經過測試，才能決定是否值得使用。 所用的向量化運算並非根基於「以空間換取時間」，那還是要盡量使用（尤其是要盡量使用內建指令），因為這種向量化運算不需要額外的空間來暫存資訊，因此效率會比 JIT 加速器更好。 碰到較複雜的資料結構（例如稀疏矩陣及維度超過 3 維的陣列），JIT 加速器並不會轉成原機指令，因此在這種情況下，也要盡量使用向量化運算。

19 2-2 JIT加速器 使用「不需要額外空間」的向量化運算來提昇效率： 範例2-9： matMultiply01.m
ns = 10:50:1200; for j=1:length(ns) n = ns(j); a = rand(n); b = rand(n); % 第一種方法：for-loop operation c = zeros(n); tic for p = 1:n for q = 1:n c(p, q) = a(p, q)*b(p, q); end

20 2-2 JIT加速器 end time1(j)=toc; % 第二種方法：vectorized operation tic
c = a.*b; time2(j)=toc; subplot(2,1,1); plot(ns, time1, 'v-', ns, time2, '^-'); grid on legend('time1 for for-loop code', 'time2 for vectorized code'); xlabel('n'); ylabel('second'); subplot(2,1,2); plot(ns, time1./time2, '.-'); grid on xlabel('n'); ylabel('time1/time2');

21 2-2 JIT加速器 第一個圖畫出迴圈運算和向量化運算所花的時間。 第二個圖則是時間的比值。
由第二個圖可以看出，加速的倍數大約都在 5 倍以上。

22 2-2 JIT加速器 為了使 JIT 加速器發揮最大效能，我們的程式碼也要盡量配合，以下是幾點注意事項 迴圈中的索引變數盡量使用純量。
迴圈中的變數盡量是簡單的資料型態，並以不超過二維為主。 迴圈內所呼叫的函式僅限於 MATLAB 內建函式。

23 2-3 矩陣的預先配置 MATLAB 可隨時改變矩陣的維度，以容納新的資料，但是每一次增大矩陣的容量時:
造成記憶體使用的分散現象，可能導致「實際雖仍有充足的記憶體，但卻未有連續空間以處理較大矩陣」的現象。 基於以上種種原因，若預先知道使用矩陣的維度大小，則最好實施矩陣的預先配置

24 2-3 矩陣的預先配置 計算矩陣 A 的 n 次方的行列式，其中 n = 1~20000，可輸入如下：
範例2-10： preAllocate01.m A = [1 2; 3 4]; n = 20000; clear detValue; % 清除變數 detValue tic for i = 1:n detValue(i) = det(A^i); end time1=toc; detValue = zeros(1, n); % 預先配置所須矩陣

25 2-3 矩陣的預先配置 end time2=toc; fprintf('time1 = %g, time2 = %g, time1/time2 = %g\n', time1, time2, time1/time2); time1 = , time2 = , time1/time2 = 上述範例中，使用 detValue = zeros(1, n) 來事先宣告 detValue 所佔用的空間，因此程式碼的執行效率快了將近 10 倍。

26 2-4 記憶體管理 MATLAB 提供 4 個和記憶體管理直接相關的指令： 指令 說明 clear 從記憶體中清除變數或函數 pack
重新安排記憶體的使用情況，使記憶體分散使用的情況降至最低 doc memory 顯示如何處理「Out of memory」的相關措施 quit 離開 MATLAB，將所有變數佔用的記憶體歸還給作業系統

27 2-4 記憶體管理 執行 MATLAB 程式碼時，發生「Out of memory」的警告訊息，即表示已無足夠空間可容納新變數，可採取的解決方案為： 隨時使用 clear 指令清除不再須要的變數。 執行 pack 指令，減小記憶體分散使用的現象。 增加虛擬記憶體的大小。 選用適合的資料型態。 如果上述方法仍無法解決，那麼只有減少所用資料量的大小。