CSAPP LAB之archlab，pipeline、循环展开、CPE=7.40
此lab主要是针对CSAPP第四章的内容，主要是学习设计和优化Y86-64处理器，分成了3个部分，第一部分熟悉Y86-64指令，第二部分熟悉pipeline的设计，第三部分结合前两部分综合优化，获得尽可能低的CPE。
优化建议
我相信大部分人都是来看partC的优化的，所以先说说优化思路，按着思路再自己试试，实在想不出来再看答案。
必须添加iaddq指令；
此lab，%rax默认为0，不需要xor；
循环展开；
有数据冒险，可以通过psim -g调试发现冒险的地方，插入其他指令规避；
有控制冒险，要合理安排跳转；
一个测试条件可以同时跟jl、je、jg；
着重优化非循环部分/数据少的部分；
需要用到三叉树；
剧透一下，hcl文件只改iaddq，通过优化ncopy代码是可以得满分的。
进阶优化：
修改hcl文件，解决掉数据冒险，可以看书的家庭作业4.57。
配置问题
或者是环境配置问题，毕竟lab很老了，很多东西都更新了，可以根据出现的错误提示一步步解决。
1、可能需要安装tcl、tk、flex、bison
2、可能要修改Makefile
Makefile中的TKINC的tcl头文件路径是tcl8.5，目前系统下载的是8.6，以后可能还会更新，改成对应的版本号。
3、可能代码发生了改变
tcl的代码结构发生了变化，改变了使用方法，不过可以添加-DUSE_INTERP_RESULT到Makefile中解决，忽略相关的警告。
4、可能提示找不到变量matherr
把它注释掉就好，
第一部分
将examples.c中的三个函数改写成Y86-64汇编程序，这个不难，没啥好说的，直接上代码吧。
sum.ys
rsum.ys
copy_block.ys
第二部分
添加iaddq指令，目的是熟悉hcl语言，后续要用到iaddq。具体改动看下面的diff，这个也不算难，理解了hcl可以很容易搞定。
第三部分
这部分才是这个lab的重头戏，通过修改ncopy.ys和pipe-full.hcl让ncopy.ys跑的尽可能快，几个要求是：
ncopy要适用任意数组大小；
ncopy要能过YIS；
ncopy的目标文件不能大于1000字节；
pipe-full.hcl要能过../y86-code 和 ../ptest的测试，尤其是这点，benchmark不检查对错，如果psim有问题，benchmark可能会得到很低的CPE，误以为自己得了满分。
3.1、代码和模拟器测试：
1、保证代码正确：
./correctness.pl
2、保证模拟器正确
(cd ../y86-code; make testpsim)
(cd ../ptest; make SIM=../pipe/psim TFLAGS=-i)
3、保证二者结合正确
./correctness.pl -p
通过了上面的测试，才能保证代码和模拟器都OK。
运行./benchmark.pl查看最终的CPE和得分。
3.2、原始ncopy.ys和pipe-full.hcl得分
3.3、hcl添加iaddq指令，ncopy.ys改为iaddq指令，速度明显提升；
3.4、循环展开
到此，需要进一步对代码动手了，方法是第五章的循环展开，由于目标代码长度1000bytes的限制，最多只能展开到10。另外，针对此lab，%rax默认为0，可以去掉xorq %rax,%rax这句，不过实际应用不能这样。
刚开始的思路是先展开（8-10）次循环，剩下的展开4次循环，之后2次，最后1次，（简称n421，以后都这么叫）通过判断rdx选择执行的路径组合，展开10次（10421）的CPE能到7.69，提升明显。代码见附1。
对于以上结果不满意，复制3个数据会分成2+1，这比较慢，想想改为n4321，3也独立出来，这次展开8次最快，CPE到7.60。代码见附2。
仍然不满意，4以下的路径是3-2-1-0，
下图可知1的权重很大，减少它的CPE很关键。
汇编可以一个条件执行多个跳转，而跳转有小于（jl）、等于（je）和大于（jg），
所以可以用三叉树构建跳转路径，减少指令数。
因为处理器有分支预测，并且默认是要跳转的，所以要把概率大的或者紧要的部分紧挨着测试条件，因为一旦预测错误，就会多出两条bubble。按照上面的树，构造出n4r213（r2表示root2，2是根，左在前，右在后，0第一个不算CPE，永远放到分支最后，而且可能会跟10冲突，故省略），我测试84r213最快，得到下面的结果，可见优化有效，CPE已经非常接近7.5了。这里还可以以1为根，感兴趣的小伙伴可以自己测试，看看是快是慢。代码见附3.
就差1.1就满分了，继续努力。我们发现循环展开部分已经无法优化了（最多是8、9、10的差别），后边1、2、3也到头了，问题就在中间的4了。之前的代码都是小于4的直接执行0、1、2、3的部分，大于等于4的先执行4次展开，再根据结果执行0、1、2、3，这里就拖慢了性能，我们换个思路进一步优化。
这次我们把非循环部分都独立出来，用上面树的思想得到具体的数，然后直接跳到对应的地方执行，如下图所示。这里以3为根，原因还是要尽量靠近循环次数少的，尽可能减少其指令数。（CPE=指令数/数据个数，数据越少，非复制部分占比越大。这里的定义好像跟第五章的CPE有点差别，我们知道这里啥意思就可以了）。
分支部分的代码如下所示（9r31264578）：
上图右边只是示意图，具体实现还需要优化，因为mrmovq和rmmovq 如果前后挨着，会有装载/使用冒险，第二条rmmovq指令会产生一个暂停，这会降低性能，可以使用加载转发技术，修改hcl文件解决这个问题，不过我们先不动hcl文件，想办法在它们之间插入一条其他指令，取代这个暂停就好，具体办法是把上一条指令的判断正负插入他们中间，如下：（可读性非常差，一不小心就混乱了，一定要仔细）
通过以上努力，我们得到了最终的版本，实测展开9次和10次CPE=7.49，满分啦。代码见附4。
到此，只增加iaddq指令的优化就做到这里了，或许还能提高，就交给感兴趣的小伙伴自行尝试吧。
3.5、加载转发
之前的版本虽然满分但还是有缺陷，或者是不可避免的会有一个暂停（如下图，rdx为8），
或者是执行一条没用的跳转（如下图，rdx为7，跳到这里），
这都是装载/使用冒险带来的副作用，看来必须把它解决掉才能得到完美的版本。加载转发具体原理可以看原书家庭作业4.57，我们在添加iaddq指令的pipe-ful.hcl文件中进一步做以下修改：
重新make并测试，都OK就得到了改进版的psim。
这样在ncopy里写代码就没有之前的限制了，mrmovq和rmmovq可以挨着，没有暂停。这里我人为加了个要求，就是寄存器只用调用者保存的，因为实际写程序，用被调用者保存寄存器是需要入栈和出栈的，这里虽没有要求，但规范还是要的。
此时的性能瓶颈就只在分支的安排上了，展开越多，分支的可能性越多，脑子想哪个更快难度很大，具体效果还需要实验，我实测展开10次最好，分支是10r312645789，CPE=7.40，这已经超过文档中老师的最好7.48，其他分支情况可能是7.44、7.45、7.46，差距不是太大。我都怀疑自己是不是弄错了，希望小伙伴们也试试，看能否复现。
最优版本ncopy代码如下：
最优版本pipe-full.hcl如下：
这里或许没人看，我就说点悄悄话，我们通过上面的过程可以看到，修改指令和循环展开获取的性能提升非常明显，这些优化是显而易见的，也是比较容易的，性价比很高。而后续的优化包括分支优化、加载转发，提升不算大，但是难度却不小，花了大量的时间，CPE的提升只有0.1，性价比不高。
不过，容易的谁都能做到，而能把不容易的做到，才能体现出自己产品的优势。很多好的系统和处理器或许就是在这些细节上有精益求精的要求，日积月累下让这些小的优势积累成了大的壁垒，成为了自己产品的核心竞争力。个人认为不应该忽视这些细枝末节的优化，累积的多了就会成为突变。
俗话说：不积跬步无以至千里，或许就是这个道理。
附1：10421
附2：84321
附3：84r213
附4：满分-只改iaddq指令
