權利保留 轉載禁止
CS 213，2001年秋季
實驗任務 L4：代碼優化
釋出日期：11月11日
截止：12月25日23:59
任務領頭人：Sanjit Seshia ([email protected])
1 介紹
此次實驗進行記憶體敏感代碼的優化。圖像處理提供了許多能夠通過優化而得到改良的函數。在此次實驗中，我們将考慮兩種圖像處理操作：roate， 此函數用于将圖像逆時針旋轉90°；以及smooth，對圖像進行“平滑”或者說“模糊”處理。
對于此次實驗，我們将認為圖像是以一個二維矩陣 M 來表示的，并以 Mi,j 來表記(i，j)位置的像素值。像素值是由紅，綠，藍(RGB)三個值構成的三元組。我們僅考慮方形圖像。以 N 來表記圖像的行數(同時也是列數)。行和列均以C風格進行編号——從0到 N - 1 。
在這種表示方法之下，rotate 操作可以借由以下兩種矩陣操作的結合來簡單實作：
轉置：對于每個(i，j)，交換 Mi,j 與 Mj,i 。
行交換：交換第 i 行與第 N - 1 - i 行。
詳情見圖1
圖1 将圖像逆時針旋轉90°
smooth 操作可以通過求每個像素與周圍像素(最多是以該像素為中心的3×3的九宮格)的均值。詳見圖2，像素 M2[1][1] 與 M2[N - 1][N - 1] 由下式給出：
圖2 平滑化圖像
2 組織工作
你可以兩人一組合作完成此次實驗任務。送出一份電子檔的 "hand-in" 。任何關于本次實驗的說明與修訂将公布在課程網站上。
3 下發檔案說明
視具體情況而定：此處插入的段落用于向學生們說明導師下發檔案 perflab-handout.tar 的方式。
首先将 perflab-handout.tar 拷貝至一個受保護的檔案夾，用于完成此次實驗。然後在指令行輸入指令：tar xvf perflab-handout.tar 這将使數個檔案被解壓至目前目錄。你可以進行修改并最終送出的唯一檔案是 kernels.c 程式 driver.c 是一個驅動程式，你可以用它來評估你解決方案的性能。使用指令：make driver 來生成驅動代碼，并用指令 ./driver 來使其運作。
檢視檔案 kernels.c，你會發現一個C 結構體：team。你需要将你小組成員的資訊填入其中。請馬上填寫，以防你忘記。
4 實作方式總覽
資料結構
圖像表示方法的核心資料結構。像素 定義為以下結構體：
typedef struct {
unsigned short red;
unsigned short green;
unsigned short blue;
} pixel;
如你所見，RGB 值擁有 16位的表示(“16位色彩”)。圖像以一個一維的“像素”數組表示，(i，j)位置的像素表示為 I[RIDX(i,j,n)]。此處 n 表示圖像矩陣的大小，RIDX 是一個宏，定義如下：
\#define RIDX(i,j,n) ((i)*(n)+(j))
查閱檔案 defs.h 的相關代碼。
Rotate
下方的C 函數用于計算源圖像 src 旋轉90°後的結果，并将結果儲存在目标圖像 dst 中。dim 表示圖像的大小。
void naive_rotate(int dim, pixel *src, pixel *dst) {
int i, j;
for(i=0; i < dim; i++)
for(j=0; j < dim; j++)
dst[RIDX(dim-1-j,i,dim)] = src[RIDX(i,j,dim)];
return;
}
以上代碼逐行掃描源圖像，将元素拷貝至目标圖像的列。你的任務是重寫這一代碼，通過 code motion，loop unrolling，blocking 等技巧使其盡可能加速運作。
查閱檔案 kernels.c 中的相關代碼。
Smooth
平滑化函數傳入源圖像 src 作為參數，并以目标圖像 dst 的形式傳回平滑化的結果。此處是部分實作：
void naive_smooth(int dim, pixel *src, pixel *dst) {
int i, j;
for(i=0; i < dim; i++)
for(j=0; j < dim; j++)
dst[RIDX(i,j,dim)] = avg(dim, i, j, src);
return;
}
avg 函數用于傳回(i，j)位置周圍像素的均值。你的任務是優化 smooth(以及 avg )函數，使其盡可能加速運作。(注：avg 是一個本地函數，你可以完全棄之不用，以其他方法實作 smooth 。)
查閱檔案 kernels.c 中的相關代碼。
性能量化
我們評估的主要參數是 CPE，機關元素消耗周期數(Cycles per Element)。如果函數在處理大小為 N×N 的圖像時需要消耗C 個周期，則 CPE 為 C/N2。表1總結了上面所寫的原始方法的性能，并将其與優化過的實作方法進行了對比。一共有5組N值。以上的結果是在 Pentium III Xeon Fish 的機器上得到的。
基于優化實作與原始實作的比率(加速)産生你代碼的得分。為了總結不同N值的整體效果，我們将取結果的幾何平均值。即：如果對于N={32, 64, 128, 256, 512}的加速分别為 R32，R64，R128， R256 以及 R512，則我們以下式計算總評得分：
表1 CPE與比率 優化vs.原始
約定
為了簡化問題，我們保證N總是32的倍數。你的代碼必須對于這樣的N值得到正确結果，而我們隻對上表列出的5個值進行檢測。
5 輔助
我們提供了支援代碼來幫助你檢測你的代碼是否正确，并衡量其性能。這一部分闡述了如何使用這些輔助代碼。本次任務的具體細節也在下面給出。
注：你允許改動的源檔案隻有 kernels.c。
版本控制
為了幫助你比較你所寫的不同版本的代碼的性能，我們允許你寫多個版本的 rotate 及 smooth。每個函數請通過 registering 函數注冊。
例如：kernels.c 中，我們提供了以下函數：
void register_rotate_functions() {
add_rotate_function(&rotate, rotate_descr);
}
在此函數中，可以一次或多次調用 add_rotate_fuction 來注冊不同版本的 rotate 函數，同時傳入的參數還包括一個 ASCII 字元串，用于描述函數功能，詳見檔案 kernels.c 。此字元串最多允許鍵入256個字元。
kernels.c 中也為 smooth 提供了類似的函數。
驅動
你寫的代碼将與我們提供的目标代碼進行連結，生成名為 driver 的二進制檔案。執行指令：
unix> make driver
來生成此二進制檔案。
每次更改 kernels.c 檔案之後，你都需要重新生成 driver 檔案。測試代碼時使用以下指令：
unix> ./driver
driver 可以以多種模式運作：
預設模式，運作函數的所有版本
自動評分模式，此模式下隻運作 rotate( ) 與 smooth( ) 函數。我們對你的 "handin" 進行評分時會采用此模式。
檔案模式，此模式下，隻有在輸入檔案中提及的函數會運作。
轉存模式，此模式下，會為每一個版本生成一行描述，并轉存在一個文本檔案中。你可以指定在轉存完成後是退出或是運作你的實作。
如果不使用任何參數，driver 将運作你全部的函數版本(預設模式)。其他模式以及選項可以通過下表的指令行參數進行指定：
-g：隻運作 rotate( ) 與 smooth( ) 函數。(自動評分模式)。
-f ：隻執行在 中指定的版本(檔案模式)。
-d ：将所有版本的名稱轉存到 中，每個版本占一行(轉存模式)。
-q：轉存之後退出。與 -d 串聯使用。例如，想在輸出轉存檔案後立即退出，鍵入：./driver -qd dumpfile.
-h：列印指令行使用方法。
組隊資訊
重要： 在開始之前，你應當在 kernels.c 檔案中的結構體填寫你隊伍的資訊(隊名，成員，郵件位址 。與 Data Lab 中的資訊相同。
6 任務詳情
優化 rotate (50 分)
此部分要求你優化 rotate 以使其達到盡可能低的 CPE。你應當先編譯 driver 然後以适合的參數運作它，檢測你的函數實作。
例如，以提供的 naive 版本運作 driver 會得到以下輸出：
unix> ./driver
Teamname: bovik
Member 1: Harry Q. Bovik
Email 1: [email protected]
Rotate: Version = naive_rotate: Naive baseline implementation:
Dim 64 128 256 512 1024 Mean
Your CPEs 14.6 40.9 46.8 63.5 90.9
Baseline CPEs 14.7 40.1 46.4 65.9 94.5
Speedup 1.0 1.0 1.0 1.0 1.0 1.0
優化 smooth (50分)
此部分要求你優化 smooth 以使其例如，以提供的 naive 版本運作 driver 會得到以下輸出：
unix> ./driver
Smooth: Version = naive_smooth: Naive baseline implementation:
Dim 32 64 128 256 512 Mean
Your CPEs 695.8 698.5 703.8 720.3 722.7
Baseline CPEs 695.0 698.0 702.0 717.0 722.0
Speedup 1.0 1.0 1.0 1.0 1.0 1.0
小建議 檢視 rotate 與 smooth 生成的對應彙編代碼。重點關注對内部循環的優化(在循環内被反複執行的那些代碼)。利用在課堂上提到的優化技巧。比起 rotate， smooth 是一個更為計算敏感的函數，是以優化方式會有些不同。
編碼規則
你可以編寫任何符合以下規則的代碼：
必須使用 ANSI C，不可以使用嵌入式的彙編語言語句。
不允許幹擾時間測量機制。任何輸出額外内容的代碼将被罰分。
你隻能夠更改 kernels.c 檔案中的代碼，允許定義宏，全局變量以及其他過程。
評分
rotate 和 smooth 各占成績的 50% 。每個函數的分數又基于以下規則：
正确性：使編譯器報錯的 bug 代碼沒有成績。能通過給定測試但無法正确處理其他測試規模的代碼也認為是不正确的。正如前文提到的，你可以認為圖像的邊長總是32的倍數。
CPE：如果你的代碼正确，且rotate 和 smooth 的平均性能分别超過了規定值 Sr 與 Ss，你将得到滿分。如果代碼正确，且性能優于 naive 函數，你可以得到一部分分數。
視具體情況而定：作為導師，你需要自己決定滿分規定值 Sr 與 Ss，以及得分細則。通常我們使用線性規則，另外，如果學生的确盡力了，可以得到約 40% 的保底分數。
送出指導
視具體情況而定：此處插入的段落用于向學生們說明每個隊伍送出 kernels.c 檔案的方式。例如，以下是我們 CMU 采用的方式。
完成實驗後，你需要送出檔案 kernels.c ，以下是送出答案的說明：
確定你在 kernels.c 中填寫了身份資訊。
確定 rotate( ) 和 smooth( ) 函數對應了你最快的版本，因為這是我們唯一考核并決定你成績的版本。
不要出現任何輸出額外資訊的語句。
隊伍名稱遵循以下形式：
"ID" ，如果你是一個人的話，ID代表你的 Andrew ID。
"ID1 + ID2" ，分别表示成員1與成員2的 Andrew ID。
應當與 kernels.c 當中結構體内所填資訊一緻。
送出你的 kernels.c ，鍵入：
make handin TEAM=teamname
teamname 如上所述。
送出之後，如果你發現有錯誤，想要送出改正後的版本，鍵入：
make hadin TEAM=teamname VERSION=2
每次送出時将版本數加一。
你可以在此處确認你的送出情況：
/afs/cs.cmu.edu/academic/class/15213-f01/L1/handin
你可以檢視以及插入此目錄，但沒有讀取和寫入檔案的權限。
祝你好運！