Automatic Instruction Set Extension
通用指令系统已可以满足大部分应用的功能需求；但对于特定应用，为了获取更高性能、更优的能效比，指令系统扩展成为重要的技术手段之一。传统的指令系统扩展流程需要较多的人工参与，有较高的时间成本，其结果也一定程度依赖于经验。因此，我们有必要通过设计自动化的方法来加速这一流程，并使用设计空间探索的方法提升结果质量。
本文提出了一个基于软硬件协同设计方法的指令系统扩展流程。该流程针对RISC架构下的多输入单输出指令，实现了从应用程序的高层次描述生成扩展指令，根据目标函数进一步筛选扩展指令，和在LLVM中间代码中应用扩展指令的过程。实验表明，该流程可以有效且快速地发现、选择和应用扩展指令。
本文的贡献有：
- 在指令集生成上，实现了根据给定应用的C代码，在其中遍历MISO指令的流程；
- 设计了一种扩展指令的正规表示形式，该形式易于阅读，且不包含重复的指令；
- 在指令集选择上，实现了使用遗传算法进行指令集选择的过程；
- 在指令应用上，实现了在程序的LLVM中间代码中应用扩展指令的流程；
- 在6个测试程序上进行了实验，验证了上述流程的有效性。
- 参考 Getting Started with the LLVM System，请将LLVM加入
PATH中
- 在本目录运行
make即可，它会自动和LLVM库链接 - 生成的可执行程序为
main
- 使用Perf工具记录程序的热点函数，采样率为999Hz
$ perf record -F 999 <exe_path>
- 生成分析报告，可根据运行时间占比得到热点函数
$ perf report
- 使用LLVM编译程序生成LLVM IR，生成文件的后缀名为
.bc$ clang -emit-llvm -O3 -c -o hello.bc hello.c
- 从LLVM IR中提取出热点函数，单独作为一个
.bc文件存放$ llvm-extract -func=a -o a.bc hello.bc
- 假设最大输入为2，使用下面指令遍历MISO
$ ./main enum -max-input 2 -o result.miso.txt a.bc
- 先安装遗传算法库
$ pip3 install geneticalgorithm
- 直接运行Python脚本
$ python3 genetic.py
- 注：目前脚本没有输入，如果要改输入的path需要直接改脚本
我使用了Atasu K et al., IJPP 2003的算法，该算法可以完整地遍历DAG中所有多输入单输出的指令（可限制输入数），缺点是算法复杂度较高
- 子图：图的节点的一个子集和在该子集中的节点之间直接连接的所有边构成的图
- 可调度性：若图中一个节点的输入来自于图外，而且向上追溯又依赖于图中另一个节点的输出，则这样的指令不能在硬件的一个周期内执行，称为不可调度；我们只遍历可调度的指令
- DAG的每个节点都可以选或不选，故对于一个节点数为N的DAG，可以构造一颗高度为N的完全二叉树，每个节点的左右子节点分别代表选或不选
- 对于每个节点，只在它的上锥形区域的节点中找以该节点为输出的子图，相当于固定这个节点为输出
- 若一个子图的输出数超过1，则立即剪枝，因为不可能再通过向上扩展减少输出数；输入数则不能作为剪枝标准，因为继续扩展可能减小
我使用带引用的后缀表达式来表示MISO指令
- 后缀表达式即操作符写在操作数之后的表达式；由于MISO指令只有一个输出，故后缀表达式可以很方便地表示MISO指令
- 由于MISO指令不一定是树，可能是图，所以我允许对先前的计算结果引用
- 使用后缀表达式的好处是可以线性书写；而且若对操作数给定顺序，可以让同构的图有相同的表达式
- 如下图所示，三个MISO指令都可以用带引用的后缀表达式来表示
- 对于第1条指令，
AND是一个聚合指令，有3个操作数，所以写作AND3 - 对于第2条指令，输入
$1被引用了两次，在第二次出现时写作@1 - 对于第3条指令，
LSHR（逻辑右移）的两个操作数顺序不可颠倒，故在图中用#1、#2区分，但表达式中可省略
- 我使用遗传算法进行指令集合选择
- 候选列表中的每条MISO指令都可以选或不选，故若有
N条候选的MISO指令，我就构造一个长度为N的bit向量，让遗传算法框架优化这个向量 - 我使用性能和面积作为双重标准，故最终得到的不是单一结果，而是一条Pareto曲线
由于实验分为两个步骤，下面我分别展示两个步骤的结果
- 在6个热点函数上搜索得到的MISO指令条数和所用时间如下表
- 可以看到，我的工具可以在<1s内搜索到全部MISO指令，证明了它的高效
- 这些函数都可以找到数十至数百条MISO指令，说明有很大利用空间
- 我将遗传算法与随机搜索对比，可以看到遗传算法的收敛速度显著高于随机搜索，而且最终的结果也优于随机搜索，证明遗传算法是有效的
- 下图是在6个热点函数上设置2入1出的结果
- 可以看到，
BF_encrypt在增加面积的情况下有较大的性能提升，说明它适用于用扩展指令的方法提高性能 sha_transform和get_block则无论增加多大的面积，性能提升都在5%以内，说明它们很难从扩展指令中受益
- 下图是在6个热点函数上分别设置2入、3入和4入的结果
- 可以看到，通常增加输入数可以获得更好的性能，但同时也需要更大的面积
