1. Autotuner整体结构

一开始尝试了OpenTuner的使用，安装后也成功运行了示例。在了解project1的需求后，决定尝试自己实现一个Autotuner测试MatrixMultiplication.c程序的可配置参数，根据性能选择最优配置输出。

使用Python进行项目搭建。

(1) 文件树

所有项目代码结构如下:

.
│  Autotuner.py----------------------Autotuner主程序
│  input.txt-------------------------所有输入信息(目标程序、参数组合、参数搜索算法)
│  MatrixMultiplication.c------------被测试程序
│  test.py---------------------------执行测试程序，调用Autotuner接口
│  testCounter.txt-------------------记录test的次数，每次测试创建新的测试结果文件夹
│
├─codes------------------------------代码文件夹
│  ├─input-----------------------------输入模块
│  │      InputDealer.py-----------------处理用户的三种输入
│  │
│  ├─runners---------------------------执行模块
│  │  └─C_runner-------------------------C语言程序执行模块
│  │         C_runner.py-------------------C语言程序执行程序
│  │
│  └─search_algs-----------------------参数搜索模块
│          allAlgs.py--------------------综合处理所有搜索算法
│          GreedySearch.py---------------贪心搜索算法程序
│          GridSearch.py-----------------网格搜索算法程序
│
├─result-----------------------------测试结果文件夹
  ├─test1------------------------------测试结果1
  │  │  program.c------------------------复制过来的被测程序
  │  │  result.txt-----------------------测试结果
  │  │
  │  └─tmp-----------------------------编译产生的临时文件夹
  │          out.txt---------------------获取被测文件的输出，写入其中
  │          tmp.exe---------------------编译生成的可执行文件
  │
  └─test2
      │  program.c
      │  result.txt
      │
      └─tmp
              out.txt
              tmp.exe

(2) 项目结构

整个测试过程的流程图如下所示：

详细流程：

test.py调用Autotuner.py的相关接口，执行Autotuner.test()方法开始测试。
Autotuner首先调用InputDealer处理用户的输入。
然后根据被测程序的后缀名选择合适的Runner(.c用C_runner, .py用Py_runner, .java用Java_runner等)。
再根据选择的搜索算法，调用对应的Searcher。
Searcher内部调用Runner，提供参数的同时获得Runner的反馈，执行其参数搜索算法。
最后Searcher给出最优性能的参数组合。

(3) InputDealer

整个InputDealer获取参数的详细过程如下：

----------------------------Autotuner----------------------------
Input the program, parameters combination and searching algorithm, 
then test the program to search the best combination of parameters.


Absolute address of program:
E:\_files\MajorLessons\软件系统优化\project\p1\project\
MatrixMultiplication.c

Please input the compiling parameters:

Parameters:
        `Type '\example' to view an example
        `Type '\end' to end input
param1 name :optimize_level
values :O0,O1,O2,O3
param2 name :\end

Please input the running parameters:

Parameters:
        `Type '\example' to view an example
        `Type '\end' to end input
param1 name :block_size
values :8,16,32,64,128
param2 name :\end

Supported algorithms:
        1. Grid Search
        2. Greedy Search
Input the number of algorithm to choose it:
1
Algorithm: Grid Search has been chosed.
Running parameters combination: {optimize_level: O0} {block_size: 8}
...

先后采集四种参数：

被测程序的绝对路径
编译参数空间
运行参数空间
参数搜索算法

能够处理多个编译参数和运行参数。

为方便起见，在test.py中将stdin重定向为input.txt。

input.txt:

E:\_files\MajorLessons\软件系统优化\project\p1\project\MatrixMultiplication.c
optimize_level
O0,O1,O2,O3
\end
block_size
8,16,32,64,128
\end
1

得到参数后，将其返回给Autotuner对象。

(4) Searcher

用编译参数、运行参数、runner以及测试次数iters初始化Searcher。每个Searcher必须有一个search方法，作为Autotuner搜索参数组合的接口。然后所有Searcher的信息保存在allAlgs.py中，维护一个Searcher Map:

from .GridSearch import GridSearch
from .GreedySearch import GreedySearch

ALGS_LIST = [
    'Grid Search',
    'Greedy Search',
]

algs_dict = {
    ALGS_LIST[0]: GridSearch,
    ALGS_LIST[1]: GreedySearch
}

Searcher.search()方法产生参数组合: 编译参数组合和运行参数组合，传给runnner运行，并从runnner获得反馈。

(5) Runner

不同的Runner用以运行不同语言的程序，Runner有一个.run()方法，获取编译参数和运行参数(若该程序没有编译阶段，则编译参数为None)。

2. 实现的优劣

(1) 优势

各个模块间耦合度低，模块与模块之间的交流基本只涉及一个接口，其余工作都在模块内部实现，这样使得代码可读性和可延展性很强。
结构的可扩展性很强。若要增加被测程序的类型，添加一个Runner即可；若要添加搜索算法，添加一个Searcher并加入map即可。
能满足多参数搜索。在InputDealer处也可看出，输入的参数可以不止一种，编译参数可以是多种，运行参数也可以是多种。
多次测试会生成不同的文件夹(参考了specjvm2008的result形式)，每次测试在单独的文件夹中进行，互不干扰。

(2) 劣势

未使用多线程运行测试，可能会导致效率低下。opentuner是采用多线程进行测试的。
用户接口可能过于冗杂。但是考虑到需要输入目标程序，不得不使用这种形式。opentuner是将待测程序直接放在代码中。

3. Greedy Search

我自行设计了一种参数搜索算法，命名为“贪心搜索算法”，但在一定程度上，我更愿意叫他梯度下降搜索算法。下面展示其思想。

**Greedy Search执行的流程： **

随机选取一种参数组合，并测试，得到测试时间。
访问该参数组合的邻域，并对领域的每种组合进行测试。
在邻域的所有测试结果中选择一个时间最短的，然后将当前参数组合改为该参数组合。
重复2,3步，直到当前参数组合耗时为其邻域内耗时最短的，退出，并认为当前参数组合为最优参数组合。

名词解释：

**邻域： ** 保持其他参数不变，只前后改变一种参数，并只在左右1格的范围内改变。如：当前参数组合为{optimize level: O2, block size: 16}，则其邻域为：

optimize level: O1, block size: 16
optimize level: O3, block size: 16
optimize level: O2, block size: 8
optimize level: O2, block size: 32

当然，在搜索的过程中，会检查该邻域是否访问过了。若已经访问过，则会跳过。因为当前选择的参数组合不是邻域参数组合，说明当前参数组合的运行时间要比邻域的短，所以甚至不用访问该邻域的运行时间，直接跳过即可。

用图像来解释即为：

这种访问邻域然后选择最优的点进入，有些类似函数空间上的梯度下降，但并不准确，因此我称其为贪心搜索算法。

4. Grid Search和Greedy Search的比较

(1) 运行效率

**Grid Search: **

Algorithm: Grid Search has been chosed.
Running parameters combination: {optimize_level: O0} {block_size: 8}
Average time cost: 318.987372s
Running parameters combination: {optimize_level: O0} {block_size: 16} 
Average time cost: 271.838465s
Running parameters combination: {optimize_level: O0} {block_size: 32} 
Average time cost: 254.311087s
Running parameters combination: {optimize_level: O0} {block_size: 64} 
Average time cost: 244.821887s
Running parameters combination: {optimize_level: O0} {block_size: 128} 
Average time cost: 241.217270s
Running parameters combination: {optimize_level: O1} {block_size: 8} 
Average time cost: 82.647090s
Running parameters combination: {optimize_level: O1} {block_size: 16} 
Average time cost: 59.657127s
Running parameters combination: {optimize_level: O1} {block_size: 32} 
Average time cost: 55.773572s
Running parameters combination: {optimize_level: O1} {block_size: 64} 
Average time cost: 50.092287s
Running parameters combination: {optimize_level: O1} {block_size: 128} 
Average time cost: 41.875394s
Running parameters combination: {optimize_level: O2} {block_size: 8} 
Average time cost: 80.311958s
Running parameters combination: {optimize_level: O2} {block_size: 16}
Average time cost: 60.672041s
Running parameters combination: {optimize_level: O2} {block_size: 32} 
Average time cost: 58.227193s
Running parameters combination: {optimize_level: O2} {block_size: 64} 
Average time cost: 52.674716s
Running parameters combination: {optimize_level: O2} {block_size: 128} 
Average time cost: 44.953127s
Running parameters combination: {optimize_level: O3} {block_size: 8} 
Average time cost: 73.855066s
Running parameters combination: {optimize_level: O3} {block_size: 16} 
Average time cost: 54.200823s
Running parameters combination: {optimize_level: O3} {block_size: 32} 
Average time cost: 36.591904s
Running parameters combination: {optimize_level: O3} {block_size: 64} 
Average time cost: 27.134263s
Running parameters combination: {optimize_level: O3} {block_size: 128} 
Average time cost: 21.869392s

Best combination:
optimize_level: O3
block_size: 128
Average time cost: 21.869392

Total time of the experiment: 10740.233052s

**Greedy Search: **

Algorithm: Greedy Search has been chosed.
Running parameters combination: {optimize_level: O2} {block_size: 64} 
Average time cost: 57.523089s
Running parameters combination: {optimize_level: O1} {block_size: 64} 
Average time cost: 50.706293s
Running parameters combination: {optimize_level: O3} {block_size: 64} 
Average time cost: 27.557757s
Running parameters combination: {optimize_level: O2} {block_size: 32} 
Average time cost: 59.431044s
Running parameters combination: {optimize_level: O2} {block_size: 128} 
Average time cost: 48.006461s
Running parameters combination: {optimize_level: O3} {block_size: 32} 
Average time cost: 37.255367s
Running parameters combination: {optimize_level: O3} {block_size: 128} 
Average time cost: 22.398077s

Best combination:
optimize_level: O3
block_size: 128
Average time cost: 22.398077

Total time of the experiment: 1542.825604s

差异显而易见。Greedy Search的搜索空间(7种组合)较Grid Search的搜索空间(20种组合)要小很多，整体运行时间也差异很大，Grid Search的搜索时间是Greedy Search的6倍多。并且Greedy Search也成功找到了正确的最优组合。

Greedy Search的运行效率一定程度上取决于初始点的选择。这次运气比较好，选择的初始点离最终点比较近。若初始点选为了{O0, 8}，可能耗时会大很多，但是必然低于Grid Search。

(2) 结果准确性

虽然上面的结果显示Greedy Search找到了全局最优的参数组合，但是这并不是一种必然。上面提到过，Greedy Search的搜索方法类似于梯度下降法，因此很容易陷入局部最优点。因此Greedy Search提供的结果不一定是全局最优点。Grid Search的搜索结果如下：

显然，{O1, 128}就是一个局部最优点，因此若初始点变化一下，最终结果就有可能陷入局部最优点，从而给出一个错误的答案。

而比较起来，Grid Search给出的结果是一个全局最优的，而且是必然的。

(3) 算法改进

从两种算法的分析比较来看，Greedy Search可以做以下改进，一定程度上减小其进入局部最优点的概率。

一开始随机选取的参数组合从1个变为多个，并且要尽可能覆盖整个参数空间。然后从这些参数组合中选择最优的参数组合，以其为起点进行Greedy Search。这样能减小陷入局部最小点的概率。
邻域可以从$n^2$个组合变为$n^3$，其中$n$为所有参数的种类数。在上面的参数组合的情况，即邻域从上,下,左,右的4个组合变为上,下,左,右,左上,右上,左下,右下8种组合，这样虽然每次的搜索范围变大了，但是可以更快地下降到局部最优点，并且搜索范围也更全面，不易错过全局最优点。

5. 结果分析

所有参数组合的结果如图所示：

(1) Block Size越大，程序运行效率越快

对于每个优化等级，显然Block Size取得越大，程序运行的时间越短。改变Block Size实际上是在改变访问对缓存的读取模式。由于MatrixMultiply.c的数组大小是4096*4096的，显然不可能把所有数值都存进内存。因此数组元素的访问必然涉及磁盘的读写。而改变Block Size可以改变对缓存的读取模式。Block Size越大，缓存页的使用就越充分（前提是Block Size没有超过缓存页的大小），因此缓存使用越充分，程序运行的效率就越高。

(2) 优化等级影响

首先，O0优化等级和其他优化等级程序的差异是显著的，因此无论何种等级的优化，较之无优化程序都能提升一定效率（单就这个程序来说）。

O1: 尝试减少代码大小，缩短代码执行时间，不会执行需要消耗大量编译时间的优化。对于大函数的编译优化会占用更多的时间和内存。
O2: 与-O1类似，会提升编译时间和代码性能，几乎开启除了时空权衡优化外的所有优化项
O3: 在-O2级别的基础上，开启了更多的优化项，最高优化等级，以编译时间、代码大小、内存为代价获取更高的性能。在部分情况下可能会降低性能。

O1

通俗来说，O1优化可以省略一些必然性的计算，比如:

1 2	int i = 1; int y = i+1;

会被优化为：

1 2	int i = 1; int y = 2;

对于矩阵乘法，一些必然性的加法乘法会被直接优化，减少运算量，因此大大增大了效率。

O2

而到了O2优化，可以明显发现，大部分Block Size使用了O2优化后，效率与O1优化相差无几，甚至还低于O1优化。我搜索了一下，发现O2优化打开了这个选项：

-fforce-mem：在做算术操作前，强制将内存数据copy到寄存器中以后再执行。这会使所有的内存引用潜在的共同表达式，进而产出更高效的代码，当没有共同的子表达式时，指令合并将排出个别的寄存器载入。这种优化对于只涉及单一指令的变量, 这样也许不会有很大的优化效果. 但是对于在很多指令(必须数学操作)中都涉及到的变量来说, 这会时很显著的优化, 因为和访问内存中的值相比,处理器访问寄存器中的值要快的多。

对于单变量涉及多计算时，这个优化效率很明显，但是对于频繁访问内存的矩阵乘法来说，该优化可能效果并不明显，甚至会让效率降低。

O3

O3优化的效率要显著优于前两种优化。尤其是在Block Size更大的时候。似乎Block Size越大，O3的效果越明显。我搜索到了相关的优化内容：

1
2
3

-fweb：构建用于保存变量的伪寄存器网络。 伪寄存器包含数据, 就像他们是寄存器一样, 但是可以使用各种其他优化技术进行优化, 比如cse和loop优化技术。这种优化会使得调试变得更加的不可能，因为变量不再存放于原本的寄存器中。 

-frename-registers：在寄存器分配后，通过使用registers left over来避免预定代码中的虚假依赖。这会使调试变得非常困难，因为变量不再存放于原本的寄存器中了。

这两者针对的是变量的访问，对于矩阵乘法来说，要反复存取矩阵中的变量，因此该优化能显著提升效率。至于其优化效果随着Block Size的变大而增强，我猜测是伪寄存器访问缓存的效率越来越高。