什么是指令调度（下）
指令调度的问题与约束指令调度受到多方面的约束，如数据依赖约束、功能部件约束、寄存器约束等^[3]^，在这些约束下，寻找到最优解，降低指令流水间的stall，就是指令调度的终极目标。
指令流水间的stall主要由数据型冒险、结构性冒险、控制型冒险导致。
数据型冒险：当前指令的执行依赖与上一条指令执行的结果。数据型冒险共有三种：写后读（raw）、读后写（war）、写后写（waw）。数据冒险可能产生数据流依赖。结构型冒险：多条指令同时访问一个硬件单元的时候，由于缺少相应的资源，导致结构型冒险。控制型冒险：存在分支跳转，无法预测下一条要执行的指令，导致其产生的控制型冒险。编译器解决上述冒险的方法就是通过插入 nop 指令，增加流水间的stall来化解冒险。
下面简单介绍一下三种数据型冒险（即数据依赖）：
写后读（raw）：一条指令读取前一条指令的写入结果。写后读是最常见的一种数据依赖类型，这种依赖被称为真数据依赖（true dependence）。x = 1;y = x;读后写（war）：一条指令写入数据到前一条指令的操作数。这种依赖被称为反依赖或反相关（anti dependence）。y = x;x = 1;写后写（waw）：两条指令写入同一个目标。这种依赖被称为输出依赖（output dependence）。x = 1;x = 2;指令调度算法之表调度（list scheduling）表调度是一种贪心+启发式方法，用以调度基本块中的各个指令操作，是基本块中指令调度的最常见方法。基于基本块的指令调度不需要考虑程序的控制流，主要考虑数据依赖、硬件资源等信息。
表调度的基本思想：维护一个用来存储已经准备执行的指令的ready列表和一个正在执行指令的active列表，ready列表的构建主要基于数据依赖约束和硬件资源信息；根据调度算法以周期为单位来执行具体的指令调度，包括从列表中选择及调度指令，更新列表信息。
基本的表调度算法大致分为以下三步：
根据指令间依赖，建立依赖关系图。根据当前指令节点到根节点的长度以及指令的latency，计算每个指令的优先级。不断选择一个指令，并调度它，使用两个队列维护ready的指令和正在执行的active的指令；在每个周期：选择一个满足条件的ready的指令并调度它，更新ready队列；检查active的指令是否执行完毕，更新active列表。指令调度案例^[4]^本案例选自卡内基梅隆大学（carnegie mellon university）的compiler design课程。
假设当前cpu有两个计算单元（即每个周期可以执行两条指令）；加法指令的latency为 2 cycles，其他指令为 1 cycle。
根据数据依赖关系构建出依赖关系图。
计算指令节点优先级
优先级计算公式如下：
其中，表示当前指令节点，表示的子节点，表示 true dependency ，表示 anti-dependency 。
其中 i10 为叶节点，优先级为其latency，故结果为1；i4 为非叶节点，优先级为当前节点latency（i4 为加法指令，latency为2）+ 子节点的优先级，故结果为3。本例中无反依赖（anti-dependency）情形。执行调度
在实际执行调度时，对于同等优先级的指令，由于具体调度方案的不同，会出现不同的情况，例如本例中出现的场景，可以通过添加其他度量标准进一步优化优先级计算方案。尽管表调度方法不能保证得到最优调度结果，但它是接近最优解的。本文只是简单介绍了最基本的表调度方法，在实际应用中，存在各种基于该方法的改进方案。关于llvm编译器中的表调度算法，可以先自行阅读其源码，更多相关介绍，敬请期待。
结语本文简单介绍了指令调度的基本概念，指令调度的原因与影响以及基本的指令调度算法。
指令调度作为np完全问题目前依旧尚未有一个完美的解决方案，对指令调度算法的探索与优化尚有很大的发展空间。
llvm之父chris lattner认为“编译器的黄金时代”已经降临^[5]^。随着计算机架构的复兴，未来的n年里将是每一位编译器工程师大显身手的时代。
参考keith d. cooper, linda torczon. engineering a compiler (second edition).https://zhuanlan.zhihu.com/p/360364235andrew w.apple, maia ginsburg. modern compiler implementation in c.https://www.cs.cmu.edu/afs/cs/academic/class/15745-s19/www/lectures/l18-instruction-scheduling-pre-class.pdfhttps://zhuanlan.zhihu.com/p/502730940
训练神经网络来解决算术、代数和微积分中的基本问题
负离子发生器工作原理
SEMI公布7月份北美半导体订单出货下滑
不是小米6，小米首款骁龙835手机跑分现身
网曝富士大白炮XF150-600mm外观照：超长焦变焦镜头
什么是指令调度（下）
三晶电气IPO材料被正式受理 三年营收超15亿
切断型膜式燃气表的原理及设计
智能电磁水表在供水管网管理上的应用
LED引发新世纪光源革命
Mygica Movie Box魅影网络电影播放器
沉浸式AR一体机RealMax“干”在上海正式发布
如何让OpenHarmony编译速度“狂飙”
Allegro布线规则的设置
锤子坚果Pro是iPhone 7 Plus的弟弟吗？孪生兄弟
电池回收利用，可以解决钴资源的供应问题
国产奥迪Q3 40 TFSI上手体验评测
理解倒装芯片和晶片级封装技术及其应用
51开发板 程序1 单个LED闪烁
《废旧锂离子电池材料再生企业清洁生产规范》于2023年12月25日正式实施
指令流水间的stall主要由数据型冒险、结构性冒险、控制型冒险导致。
数据型冒险：当前指令的执行依赖与上一条指令执行的结果。数据型冒险共有三种：写后读（raw）、读后写（war）、写后写（waw）。数据冒险可能产生数据流依赖。结构型冒险：多条指令同时访问一个硬件单元的时候，由于缺少相应的资源，导致结构型冒险。控制型冒险：存在分支跳转，无法预测下一条要执行的指令，导致其产生的控制型冒险。编译器解决上述冒险的方法就是通过插入 nop 指令，增加流水间的stall来化解冒险。
下面简单介绍一下三种数据型冒险（即数据依赖）：
写后读（raw）：一条指令读取前一条指令的写入结果。写后读是最常见的一种数据依赖类型，这种依赖被称为真数据依赖（true dependence）。x = 1;y = x;读后写（war）：一条指令写入数据到前一条指令的操作数。这种依赖被称为反依赖或反相关（anti dependence）。y = x;x = 1;写后写（waw）：两条指令写入同一个目标。这种依赖被称为输出依赖（output dependence）。x = 1;x = 2;指令调度算法之表调度（list scheduling）表调度是一种贪心+启发式方法，用以调度基本块中的各个指令操作，是基本块中指令调度的最常见方法。基于基本块的指令调度不需要考虑程序的控制流，主要考虑数据依赖、硬件资源等信息。
表调度的基本思想：维护一个用来存储已经准备执行的指令的ready列表和一个正在执行指令的active列表，ready列表的构建主要基于数据依赖约束和硬件资源信息；根据调度算法以周期为单位来执行具体的指令调度，包括从列表中选择及调度指令，更新列表信息。
基本的表调度算法大致分为以下三步：
根据指令间依赖，建立依赖关系图。根据当前指令节点到根节点的长度以及指令的latency，计算每个指令的优先级。不断选择一个指令，并调度它，使用两个队列维护ready的指令和正在执行的active的指令；在每个周期：选择一个满足条件的ready的指令并调度它，更新ready队列；检查active的指令是否执行完毕，更新active列表。指令调度案例^[4]^本案例选自卡内基梅隆大学（carnegie mellon university）的compiler design课程。
假设当前cpu有两个计算单元（即每个周期可以执行两条指令）；加法指令的latency为 2 cycles，其他指令为 1 cycle。
根据数据依赖关系构建出依赖关系图。
计算指令节点优先级
优先级计算公式如下：
其中，表示当前指令节点，表示的子节点，表示 true dependency ，表示 anti-dependency 。
其中 i10 为叶节点，优先级为其latency，故结果为1；i4 为非叶节点，优先级为当前节点latency（i4 为加法指令，latency为2）+ 子节点的优先级，故结果为3。本例中无反依赖（anti-dependency）情形。执行调度
在实际执行调度时，对于同等优先级的指令，由于具体调度方案的不同，会出现不同的情况，例如本例中出现的场景，可以通过添加其他度量标准进一步优化优先级计算方案。尽管表调度方法不能保证得到最优调度结果，但它是接近最优解的。本文只是简单介绍了最基本的表调度方法，在实际应用中，存在各种基于该方法的改进方案。关于llvm编译器中的表调度算法，可以先自行阅读其源码，更多相关介绍，敬请期待。
结语本文简单介绍了指令调度的基本概念，指令调度的原因与影响以及基本的指令调度算法。
指令调度作为np完全问题目前依旧尚未有一个完美的解决方案，对指令调度算法的探索与优化尚有很大的发展空间。
llvm之父chris lattner认为“编译器的黄金时代”已经降临^[5]^。随着计算机架构的复兴，未来的n年里将是每一位编译器工程师大显身手的时代。
参考keith d. cooper, linda torczon. engineering a compiler (second edition).https://zhuanlan.zhihu.com/p/360364235andrew w.apple, maia ginsburg. modern compiler implementation in c.https://www.cs.cmu.edu/afs/cs/academic/class/15745-s19/www/lectures/l18-instruction-scheduling-pre-class.pdfhttps://zhuanlan.zhihu.com/p/502730940
训练神经网络来解决算术、代数和微积分中的基本问题
负离子发生器工作原理
SEMI公布7月份北美半导体订单出货下滑
不是小米6，小米首款骁龙835手机跑分现身
网曝富士大白炮XF150-600mm外观照：超长焦变焦镜头
什么是指令调度（下）
三晶电气IPO材料被正式受理 三年营收超15亿
切断型膜式燃气表的原理及设计
智能电磁水表在供水管网管理上的应用
LED引发新世纪光源革命
Mygica Movie Box魅影网络电影播放器
沉浸式AR一体机RealMax“干”在上海正式发布
如何让OpenHarmony编译速度“狂飙”
Allegro布线规则的设置
锤子坚果Pro是iPhone 7 Plus的弟弟吗？孪生兄弟
电池回收利用，可以解决钴资源的供应问题
国产奥迪Q3 40 TFSI上手体验评测
理解倒装芯片和晶片级封装技术及其应用
51开发板 程序1 单个LED闪烁
《废旧锂离子电池材料再生企业清洁生产规范》于2023年12月25日正式实施