Csapp_lab3

实验报告

实验（三）

题目优化

专业航院人工智能

学　　号 7203610404

班　　级 2036017

学生彭癸龙　　　

指导教师史先俊　　

实验地点宿舍　　　

实验日期 2022.04.17　　　

计算学部

目录

第1章实验基本信息 - 3 -

1.1 实验目的 - 3 -

1.2 实验环境与工具 - 3 -

1.2.1 硬件环境 - 3 -

1.2.2 软件环境 - 3 -

1.2.3 开发工具 - 3 -

1.3 实验预习 - 3 -

第2章实验预习 - 5 -

2.1 程序优化的十大方法（5分） - 5 -

2.2性能优化的方法概述（5分） - 5 -

2.3 Linux下性能测试的方法（5分） - 6 -

2.4 Windows下性能测试的方法（5分） - 6 -

第3章性能优化的方法 - 8 -

第4章性能优化实践 - 11 -

1.代码移动 - 11 -

2.循环展开 - 12 -

3.面向编译器优化 - 13 -

4.针对cpu流水线优化 - 14 -

5.使用avx指令集进行优化 - 14 -

第5章总结 - 16 -

5.1 请总结本次实验的收获 - 16 -

5.2 请给出对本次实验内容的建议 - 16 -

参考文献 - 17 -

第1章实验基本信息

1.1 实验目的

理解程序优化的10个维度

熟练利用工具进行程序的性能评价、瓶颈定位

掌握多种程序性能优化的方法

熟练应用软件、硬件等底层技术优化程序性能

1.2 实验环境与工具

1.2.1 硬件环境

Cpu: amd ryzen7 5800h

1.2.2 软件环境

Windows11 professional 21h2

1.2.3 开发工具

Visual studio 2022 17.1.6

1.3 实验预习

优化程序的十个维度：

更快

更省（存储空间、运行空间）

更美（UI 交互）

更正确

更可靠（各种条件下的正确性、安全性）

可移植

更强大（功能）

更方便（安装、使用、帮助/导航、可维护）

更规范（格式符合编程规范、接口规范）

更易懂（能读明白、有注释、模块化—清晰简洁）

第2章实验预习

总分20分

2.1 程序优化的十大方法（5分）

更快

更省（存储空间、运行空间）

更美（UI 交互）

更正确

更可靠

可移植

更强大（功能）

更方便（使用）

更范（格式符合编程规范、接口规范）

更易懂（能读明白、有注释、模块化）

2.2性能优化的方法概述（5分）

1.一般有用的优化

代码移动

复杂指令简化

公共子表达式

2.面向编译器的优化：障碍

函数副作用

内存别名

3.面向超标量CPU的优化

流水线、超线程、多功能部件、分支预测投机执行、乱序执行、多核：分离的循环展开！

只有保持能够执行该操作的所有功能单元的流水线都是满的，程序才能达到这个操作的吞吐量界限

4.面向向量CPU的优化：MMX/SSE/AVR

5. CMOVxx等指令

代替test/cmp+jxx

6. 嵌入式汇编

7.面向编译器的优化

Ox:0 1 2 3 g

8.面向存储器的优化：Cache无处不在

重新排列提高空间局部性

分块提高时间局部性

9.内存作为逻辑磁盘：内存够用的前提下。

10.多进程优化

fork，每个进程负责各自的工作任务，通过mmap共享内存或磁盘等进行交互。

11.文件访问优化：带Cache的文件访问

12.并行计算：多线程优化：第12章

13.网络计算优化：第11章、分布式计算、云计算

14.GPU编程、算法优化

15.超级计算

2.3 Linux下性能测试的方法（5分）

oProfile是Linux平台上的一个功能强大的性能分析工具，支持两种采样(sampling)方式：基于事件的采样(eventbased)和基于时间的采样(timebased)。

基于事件的采样是oProfile只记录特定事件（比如L2 cache miss）的发生次数，当达到用户设定的定值时oProfile就记录一下（采一个样）。这种方式需要CPU内部有性能计数器(performace counter)。

使用operf进行分析可以精确定位分析（即单个过程或系统范围）。使用operf，无需初始设置 - 只需使用您需要的选项调用operf ; 然后运行OProfile后处理工具。该operf语法如下：

operf [options] [--system-wide | --pid = | [command [args]]]

典型用法如下：

operf ./my_test_program my_arg

2.4 Windows下性能测试的方法（5分）

1.Visual studio本身具有性能探测器，可以查看cpu、ram、gpu在程序执行时的资源占用情况

2. 统计运行时间，来测试性能。

3.RDTSC：

RDTSC指令, 该指令返回CPU自启动以来的时钟周期数；该时钟周期数，即处理器的时间戳。

第3章性能优化的方法

总分20分

逐条论述性能优化方法名称、原理、实现方案（至少10条）

3.1

1.一般有用的优化

代码移动：消除冗余重复的计算

复杂指令简化：用更简单的方法替换昂贵的操作，例如用移位代替除法

公共子表达式：重用表达式的一部分，可以让计算更简单

2.面向编译器的优化：障碍

函数副作用：函数每次调用都可能改变全局变量或者状态，这需要我们合理的在函数内修改全局变量的值

内存别名：两个不同的内存引用指向相同的位置，编译器不知道函数何时被调用，不知道内存会不会被别的函数修改，因此对函数进行内存弱优化。这要求我们养成引入局部变量的习惯

3.面向超标量CPU的优化

流水线、超线程、多功能部件、分支预测投机执行、乱序执行、多核:只有保持能够执行该操作的所有功能单元的流水线都是满的，程序才能达到这个操作的吞吐量界限。同时对于具有条件判断的语句，处理器不确定条件是否正确就执行，但结果不凡到寄存器或内存，这需要我们正确安排条件判断的位置，避免惩罚。

4.面向向量CPU的优化：MMX/SSE/AVR：cpu有向量寄存器，指令集内有向量计算的指令，使用向量计算可以加速较大数据的计算。

5. CMOVxx等指令：代替test/cmp+jxx，减少条件判断

6.嵌入式汇编：利用嵌入汇编的方法，人为的对底层进行优化

7.面向编译器的优化：利用Ox:0 1 2 3 g等优化模式不同的优化模式，对内存和速度等进行不同程度的优化

8.面向存储器的优化：Cache无处不在：重新排列提高空间局部性，分块提高时间局部性。通过优化减少cache miss

9.内存作为逻辑磁盘：内存够用的前提下。

10.多进程优化fork，每个进程负责各自的工作任务，通过mmap共享内存或磁盘等进行交互：

充分利用cpu的多核特性

11.文件访问优化：带Cache的文件访问

12.并行计算：多线程优化

13.网络计算优化

14.GPU编程、算法优化：

利用gpu编程

15.超级计算：

利用性能更强的超级计算机

第4章性能优化实践

总分60分

4.1 原始程序及说明（10分）

void imgsmth_1(long* img)
{
int i, j;
for (j = 1; j < WIDTH - 1; j++)
for (i = 1; i< HEIGHT - 1; i++)
img[i * WIDTH + j] = (img[i * WIDTH + j - 1] + img[i * WIDTH + j + 1] + img[(i - 1) * WIDTH + j] + img[(i + 1) * WIDTH + j]) / 4;
}
int main()
{
int i, j;
int a = 0;
long* img = (long*)malloc(HEIGHT * WIDTH * sizeof(long));
if (img)
{
for (i = 0; i < HEIGHT; i++)
{
for (j = 0; j < WIDTH; j++)
{
img[i * WIDTH + j] = a;
a++;
}
}
}
int loop = 100;
clock_t start = clock();
for (int i = 1; i <= loop; i++)
imgsmth_1(img);
clock_t over = clock();
free(img);
printf("%ldms", over - start);
}

在imsmoth_1里进行平滑处理，在main函数中运行100次，最终打印花费的时间。

4.2 优化后的程序及说明（20分）

1.代码移动

void imgsmth_2(long* img)
{
int i, j;
for (i = 1; i < HEIGHT - 1; i++)
for (j = 1; j < WIDTH - 1; j++)
img[i * WIDTH + j] = (img[i * WIDTH + j - 1] + img[i * WIDTH + j + 1] + img[(i - 1) * WIDTH + j] + img[(i + 1) * WIDTH + j]) / 4;
}

将i和j的顺序调换，最终运行100次花费的时间为：

2.循环展开

void imgsmth_3(long* img)
{
int i = 0, j = 0;;
int opr = i * WIDTH + j;
int left = 0, right = 0, up = 0, down = 0;
for (i = 1; i < HEIGHT - 1; i++) {
for (j = 1; j + 16 < WIDTH - 1; j=j+8)
{
opr = i * WIDTH + j;
left = i * WIDTH - 1 + j;
right = i * WIDTH + 1 + j;
up = (i - 1) * WIDTH + j;
down = (i + 1) * WIDTH + j;
img[opr] = (img[left] + img[right] + img[up] + img[down]) / 4;
opr++;
left++;
right++;
up++;
down++;
img[opr] = (img[left] + img[right] + img[up] + img[down]) / 4;
opr++;
left++;
right++;
up++;
down++;
img[opr] = (img[left] + img[right] + img[up] + img[down]) / 4;
opr++;
left++;
right++;
up++;
down++;
img[opr] = (img[left] + img[right] + img[up] + img[down]) / 4;
opr++;
left++;
right++;
up++;
down++;
img[opr] = (img[left] + img[right] + img[up] + img[down]) / 4;
opr++;
left++;
right++;
up++;
down++;
img[opr] = (img[left] + img[right] + img[up] + img[down]) / 4;
opr++;
left++;
right++;
up++;
down++;
img[opr] = (img[left] + img[right] + img[up] + img[down]) / 4;
opr++;
left++;
right++;
up++;
down++;
img[opr] = (img[left] + img[right] + img[up] + img[down]) / 4;
}
for (; j < WIDTH - 1; j++)
img[i * WIDTH + j] = (img[i * WIDTH + j - 1] + img[i * WIDTH + j + 1] + img[(i - 1) * WIDTH + j] + img[(i + 1) * WIDTH + j]) / 4;
}
}

将循环展开后进行100次执行，运行时间为：

3.面向编译器优化

编译器可以进行一定程度的优化。

使用O1优化：

运行时间为

使用O2优化：

运行时间为：

4.针对cpu流水线优化

循环内计算时间隔两个单位进行平滑处理，因为间隔两个单位的数组元素进行平滑处理时数据上没有相互依赖，可以让流水线满载。

void imgsmth_5(long* img) {
int i, j;
for (i = 1; i < HEIGHT - 1; i++){
for (j = 1; j +3< WIDTH - 1; j=j+4){
int opr = i * WIDTH + j;
int up = (i - 1) * WIDTH + j;
int down = (i + 1) * WIDTH + j;
img[opr] = (img[opr- 1] + img[opr+ 1] + img[up] + img[down]) / 4;
img[opr + 2] = (img[opr + 3] + img[opr + 1] + img[up + 2] + img[down + 2]) / 4;
}
for (j = 2; j + 3 < WIDTH - 1; j = j + 4) {
int opr = i * WIDTH + j;
int up = (i - 1) * WIDTH + j;
int down = (i + 1) * WIDTH + j;
img[opr] = (img[opr - 1] + img[opr + 1] + img[up] + img[down]) / 4;
img[opr + 2] = (img[opr + 3] + img[opr + 1] + img[up + 2] + img[down + 2]) / 4;
}
}
}

运行100次花费时间为：

5.使用avx指令集进行优化

Amd五代锐龙支持avx2指令集，可以使用avx指令集进行优化。

void imgsmth_6(long long* img) {
__m256i _cal_left, _cal_right, _cal_up, _cal_down, _cal_data;
int i = 1, j = 1;
long long id;
long long* identity;
for (i = 1; i < HEIGHT - 1; i++) {
for (j = 1; j + 8 < WIDTH - 1; j = j + 4) {
id = i * WIDTH + j;
identity = img + id;
_cal_left = _mm256_loadu_si256((__m256i*) (identity - 1));
_cal_right = _mm256_loadu_si256((__m256i*)(identity + 1));
_cal_up = _mm256_loadu_si256((__m256i*) (identity -WIDTH));
_cal_down = _mm256_loadu_si256((__m256i*)(identity + WIDTH));
_cal_data = _mm256_add_epi64(_cal_left, _cal_right);
_cal_data = _mm256_add_epi64(_cal_data, _cal_up);
_cal_data = _mm256_add_epi64(_cal_data, _cal_down);
_cal_data = _mm256_srli_epi64(_cal_data, 2);
_mm256_storeu_si256((identity), _cal_data);
}
}
}

最终运行时间为：

4.3 优化前后的性能测试（10分）

1）没有优化 925

2）代码移动 676

3）循环展开 840

4）o1 731

5）o2 795

6) avx 330

4.4 面向泰山服务器优化后的程序与测试结果（15分）

或4.2的优化方法分析：结合自己计算机的硬件参数，分析优化后程序的各个参数选择依据。（15分）

对服务器优化未进行avx优化，这里使用gcc的-O2选项进行优化，时间如上图所示。

Arm的霓虹指令集提供了与x86和x64架构通用的MMX和SSE矢量指令集中的SIMD功能，但鉴于时间问题为进行相关的优化。

4.5 还可以采取的进一步的优化方案（5分）

可以针对cache进行优化，还可以针对线程进行优化，五代锐龙具有16线程，但十二章未能进行学习，因而无法继续优化。

第5章总结

5.1 请总结本次实验的收获

进一步了解了如何优化程序

学习了常用的程序性能评价工具

了解了avx指令集

复习了优化的相关细节

5.2 请给出对本次实验内容的建议

线程优化在书上的第十二章，但是课程已经结束还未进行讲解，如果能学习了第十二章后运用线程优化的话会更好

注：本章为酌情加分项。

参考文献

为完成本次实验你翻阅的书籍与网站等

https://docs.microsoft.com/zh-cn/cpp/intrinsics/x64-amd64-intrinsics-list?view=msvc-170