中山大學應用數學研究所一年級 莊玉如

利用矩陣相乘的程式，並配合CONVEX上編譯程式所提供不同程度的最佳化選擇，觀察程式執行所需的時間並討論其結果。使用者可配合程式的架構選擇不同方式的最佳化處理，當然，越高等級的最佳化處理便會使用愈多的系統資源。

1. 程式內容與執行時間

由於矩陣相乘的程式中會利用不少的for-loop，這正是測試最佳化程度的最好機會。首先寫了一個矩陣相乘的程式，由於不同程度的最佳化會導致程式執行時間的快、慢差異，為了便於觀察最佳化的程度，於是將矩陣的大小訂定為10001000。

首先，利用亂數產生被乘與乘的矩陣MA、MB，接著利用三層的loop做矩陣相乘的結果。以下便是選擇不同最佳化程度，程式所執行的時間表：

2. 討論

選擇不做任何最佳化的情況，所花的時間必然是最多的。O0與O1的情況則有點類似，不過O0是針對Local即同一function中，而O1則針對Global做存量計算最佳化。這兩種最佳化的選擇導致程式執行時間比不做任何最佳化執行時間短並不令人意外，雖然，Local最佳化並沒有加快多少程式執行速度，但是，Global最佳化竟將速度提昇二倍以上。直覺上，Global最佳化的效果比Local最佳化好並沒有問題，只是有個疑問，有沒有什麼情況下，使用Local最佳化會比Global最佳化來的好呢？由於這份作業是針對單一程式做討論，所以無法針對這個問題做更測底的研究。

O0和O1最佳化是想辦法消除多餘的運算式或將運算的結果先放在暫存器中，等真正做完再放入變數名稱中，例如：

利用O2的最佳化選擇，程式執行時間一下子降為原來的七十幾分之一，竟然，10001000大小的矩陣相乘，需要百萬個乘法和加法只要17秒便可以完成！到底O2的最佳化是如何做到的呢？O2的最佳化方法是調整loop的順序使其更能充分運用向量化來執行程式，例如：

在我的程式中，計算矩陣相乘的Original Code如下；

for( i = 0; i < 1000; i ++)

程式一

如果將它改為:

for( k = 0; k < 1000; k ++)

程式二

我們可以發現在新的程式MB[k][j]只在i改變的時候才會變，不像原來的程式，MA[i][k]與MB[k][j]總是每次都會改變。

所以，在做矩陣乘法時調整一下loop的順序，就算沒有減少任何的乘法與加法的次數，應該也可以增加程式執行的速率。

令外，O3最佳化是將loop分成了幾個部份，分別在不同的CPU上同時計算以加快程式的速度，但這裡我們可以觀察出這樣的效果也很顯著，但不比O2最佳化來的好，可見選擇最佳化並不一定就是愈高級的愈好，而是要選擇適合這個程式結構的最佳化才是最理想的。

3. 實驗

觀察到這些結果後，我想，何不自己幫程式最佳化，看看程式的執行時間會不會真的加快。於是我修改了部份程式，調換loop的順序成程式二，並選擇了O1最佳化來編譯(選擇O1的原因是我想我已經幫它作了一些最佳化了)，但出乎我意料的是這樣竟然花了1759秒，甚至比原來的程式不作任何最佳化的時間要多的多；但選擇O2最佳化仍然是花了17秒，不多不少。如果只針對程式二來說，O2最佳化比O1快了一百多倍，而程式一也算是程式二某種程度的最佳化。

但程式二的時間竟然會變長仍然讓人覺得非常奇怪，於是我又將這兩個程式同時放在ibm的機器上執行則程式一需花864秒，而程式二需花1398秒，這時又發生一件令人驚奇的事，即在ibm的機器上編譯，不下任何的參數，兩個程式執行的結果竟然都比在超級電腦上O0最佳化後還快，程式二更是比O1最佳化快! 我們知道不同機器上的編譯程式會有所不同，可能針對程式二來說，ibm上的compile比CONVEX上O1最佳化來的好吧!

	程式一	程式二
ibm	864(s)	1398(s)
CONVEX	1012(s)(O0)	1759(s)(O1)

我想也許loop的順序調換有誤，我再試了另一寫法如下；

for( k = 0; k < 1000; k ++)

程式三

我又將程式三分別放到CONVEX與ibm上執行，結果如下；

果然，時間幾乎都縮短了，由在ibm上執行，便可看出的確有最佳化的效果，即使只能在ibm上執行，所花的時間已相當於程式一在ONVEX上O1最佳化的時間了。

4. 結論

選擇最佳化的等級應該針對程式的需要，不見得等級愈高的就會愈快，也不見得使用超級電腦就會是最快的，就像程式一、程式二和程式三所做的事情皆相同，只不過調換了loop的順序，時間便有這麼大的差異，所以應該充份了解最佳化的原理，進而修改程式，則不需要超級電腦也可以加快程式的執行速度，這也是我做這次作業的最大收穫。