PerfLab 文档中文翻译

权利保留 转载禁止

CS 213，2001年秋季
实验任务 L4：代码优化
发布日期：11月11日
截止：12月25日23:59

任务领头人：Sanjit Seshia (sanjit+213@cs.cmu.edu)

1 介绍

此次实验进行内存敏感代码的优化。图像处理提供了许多能够通过优化而得到改良的函数。在此次实验中，我们将考虑两种图像处理操作：roate， 此函数用于将图像逆时针旋转90°；以及smooth，对图像进行“平滑”或者说“模糊”处理。

对于此次实验，我们将认为图像是以一个二维矩阵 M 来表示的，并以 M_i,j 来表记（i，j）位置的像素值。像素值是由红，绿，蓝（RGB）三个值构成的三元组。我们仅考虑方形图像。以 N 来表记图像的行数（同时也是列数）。行和列均以C风格进行编号——从0到 N - 1 。

在这种表示方法之下，rotate 操作可以借由以下两种矩阵操作的结合来简单实现：

• 转置：对于每个（i，j），交换 M_i,j 与 M_j,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; /* R value */
unsigned short green; /* G value */
unsigned short blue; /* B value */
} 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); /* Smooth the (i,j)th pixel */
return;
}

avg 函数用于返回（i，j）位置周围像素的均值。你的任务是优化 smooth（以及 avg ）函数，使其尽可能加速运行。（注：avg 是一个本地函数，你可以完全弃之不用，以其他方法实现 smooth 。）
查阅文件 kernels.c 中的相关代码。

性能量化

我们评估的主要参数是 CPE，单位元素消耗周期数（Cycles per Element）。如果函数在处理大小为 N×N 的图像时需要消耗C 个周期，则 CPE 为 C/N²。表1总结了上面所写的原始方法的性能，并将其与优化过的实现方法进行了对比。一共有5组N值。以上的结果是在 Pentium III Xeon Fish 的机器上得到的。

基于优化实现与原始实现的比率（加速）产生你代码的得分。为了总结不同N值的整体效果，我们将取结果的几何平均值。即：如果对于N={32, 64, 128, 256, 512}的加速分别为 R₃₂，R₆₄，R₁₂₈， R₂₅₆ 以及 R₅₁₂，则我们以下式计算总评得分：

表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: bovik@nowhere.edu
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 的平均性能分别超过了规定值 S_r 与 S_s，你将得到满分。如果代码正确，且性能优于 naive 函数，你可以得到一部分分数。

视具体情况而定：作为导师，你需要自己决定满分规定值 S_r 与 S_s，以及得分细则。通常我们使用线性规则，另外，如果学生的确尽力了，可以得到约 40% 的保底分数。

提交指导

视具体情况而定：此处插入的段落用于向学生们说明每个队伍提交 kernels.c 文件的方式。例如，以下是我们 CMU 采用的方式。

完成实验后，你需要提交文件 kernels.c ，以下是提交答案的说明：

• 确保你在 kernels.c 中填写了身份信息。
• 确保 rotate( ) 和 smooth( ) 函数对应了你最快的版本，因为这是我们唯一考核并决定你成绩的版本。
• 不要出现任何输出额外信息的语句。
• 队伍名称遵循以下形式：
     "ID" ，如果你是一个人的话，ID代表你的 Andrew ID。
     "ID₁ + ID₂" ，分别表示成员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
  你可以查看以及插入此目录，但没有读取和写入文件的权限。

祝你好运！