0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

什么是指令调度(下)

jf_78858299 来源:姜海波 毕昇编译 作者:姜海波 毕昇编译 2023-02-02 09:36 次阅读

指令调度的问题与约束

指令调度受到多方面的约束,如数据依赖约束、功能部件约束、寄存器约束等^[3]^,在这些约束下,寻找到最优解,降低指令流水间的stall,就是指令调度的终极目标。

指令流水间的stall主要由数据型冒险、结构性冒险、控制型冒险导致。

  • 数据型冒险:当前指令的执行依赖与上一条指令执行的结果。数据型冒险共有三种:写后读(RAW)、读后写(WAR)、写后写(WAW)。数据冒险可能产生数据流依赖。
  • 结构型冒险:多条指令同时访问一个硬件单元的时候,由于缺少相应的资源,导致结构型冒险。
  • 控制型冒险:存在分支跳转,无法预测下一条要执行的指令,导致其产生的控制型冒险。

编译器解决上述冒险的方法就是通过插入 NOP 指令,增加流水间的stall来化解冒险。

下面简单介绍一下三种数据型冒险(即数据依赖):

  1. 写后读(RAW):一条指令读取前一条指令的写入结果。写后读是最常见的一种数据依赖类型,这种依赖被称为真数据依赖(true dependence)。
    x = 1;
    y = x;
    
  2. 读后写(WAR):一条指令写入数据到前一条指令的操作数。这种依赖被称为反依赖或反相关(anti dependence)。
    y = x;
    x = 1;
    
  3. 写后写(WAW):两条指令写入同一个目标。这种依赖被称为输出依赖(output dependence)。
    x = 1;
    x = 2;
    

指令调度算法之表调度(List Scheduling)

表调度是一种贪心+启发式方法,用以调度基本块中的各个指令操作,是基本块中指令调度的最常见方法。基于基本块的指令调度不需要考虑程序的控制流,主要考虑数据依赖、硬件资源等信息

表调度的基本思想:维护一个用来存储已经准备执行的指令的ready列表和一个正在执行指令的active列表,ready列表的构建主要基于数据依赖约束和硬件资源信息;根据调度算法以周期为单位来执行具体的指令调度,包括从列表中选择及调度指令,更新列表信息。

基本的表调度算法大致分为以下三步:

  1. 根据指令间依赖,建立依赖关系图。
  2. 根据当前指令节点到根节点的长度以及指令的latency,计算每个指令的优先级。
  3. 不断选择一个指令,并调度它,
    • 使用两个队列维护ready的指令和正在执行的active的指令;
    • 在每个周期:选择一个满足条件的ready的指令并调度它,更新ready队列;检查active的指令是否执行完毕,更新active列表。

指令调度案例^[4]^

本案例选自卡内基梅隆大学(Carnegie Mellon University)的Compiler Design课程。

假设当前CPU有两个计算单元(即每个周期可以执行两条指令);加法指令的latency为 2 cycles,其他指令为 1 cycle。

  1. 根据数据依赖关系构建出依赖关系图。
    图片
  2. 计算指令节点优先级
    优先级计算公式如下:
    其中,表示当前指令节点,表示的子节点,表示 "true dependency" ,表示 "anti-dependency" 。
    图片
    其中 I10 为叶节点,优先级为其latency,故结果为1;I4 为非叶节点,优先级为当前节点latency(I4 为加法指令,latency为2)+ 子节点的优先级,故结果为3。本例中无反依赖(anti-dependency)情形。
  3. 执行调度
    图片
    在实际执行调度时,对于同等优先级的指令,由于具体调度方案的不同,会出现不同的情况,例如本例中出现的场景,可以通过添加其他度量标准进一步优化优先级计算方案。尽管表调度方法不能保证得到最优调度结果,但它是接近最优解的。

本文只是简单介绍了最基本的表调度方法,在实际应用中,存在各种基于该方法的改进方案。关于LLVM编译器中的表调度算法,可以先自行阅读其源码,更多相关介绍,敬请期待。

结语

本文简单介绍了指令调度的基本概念,指令调度的原因与影响以及基本的指令调度算法。

指令调度作为NP完全问题目前依旧尚未有一个完美的解决方案,对指令调度算法的探索与优化尚有很大的发展空间。

LLVM之父Chris Lattner认为“编译器的黄金时代”已经降临^[5]^。随着计算机架构的复兴,未来的N年里将是每一位编译器工程师大显身手的时代。

参考

  1. Keith D. Cooper, Linda Torczon. Engineering a Compiler (Second Edition).
  2. https://zhuanlan.zhihu.com/p/360364235
  3. Andrew W.Apple, Maia Ginsburg. Modern Compiler Implementation in C.
  4. https://www.cs.cmu.edu/afs/cs/academic/class/15745-s19/www/lectures/L18-Instruction-Scheduling-pre-class.pdf
  5. https://zhuanlan.zhihu.com/p/502730940
声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 处理器
    +关注

    关注

    68

    文章

    19214

    浏览量

    229468
  • cpu
    cpu
    +关注

    关注

    68

    文章

    10840

    浏览量

    211393
  • 指令调度器
    +关注

    关注

    0

    文章

    4

    浏览量

    1495
收藏 人收藏

    评论

    相关推荐

    FreeRTOS任务调度器的三种调度算法讲解(

    配置如下时,调度算法就会变成不带时间片的抢占式调度
    的头像 发表于 03-21 13:46 2652次阅读
    FreeRTOS任务<b class='flag-5'>调度</b>器的三种<b class='flag-5'>调度</b>算法讲解(<b class='flag-5'>下</b>)

    应急通信调度指挥系统的原理

      应急通信调度指挥系统的原理  从威廉希尔官方网站 层面,我们提到的应急通信调度指挥系统原理,如图所示,主要包括四个方面:信息采集、信息传递、信息处理以及指令下达和执行 。其中,虚框内表示急需  1.信息采集
    发表于 12-29 17:21

    编译器优化的静态调度介绍

    量与指令调度相关性更强,下面简单介绍一这两种模式。  流水线  将指令执行过程分成多个阶段,每个阶段使用不同的硬件资源,从而使得多条指令
    发表于 03-17 17:07

    基于ARM Cortex-M3的μCOS-II任务调度硬件指令实现

    本文首先多UC/OS-II的任务调度算法做了详细的分析, 然后介绍了基于基于ARM Cortex-M3的COS-II的任务调度硬件指令实现
    发表于 03-25 15:13 270次下载
    基于ARM Cortex-M3的μCOS-II任务<b class='flag-5'>调度</b>硬件<b class='flag-5'>指令</b>实现

    同时多线程处理器的指令调度器设计

    同时多线程处理器的指令调度器设计_李乐
    发表于 01-08 14:55 0次下载

    云环境基于动态蚁群遗传算法的调度方法研究_尚志会

    云环境基于动态蚁群遗传算法的调度方法研究_尚志会
    发表于 01-30 23:17 0次下载

    柔性负荷调度,发电调度的补充

    的负荷,包含具备需求弹性的可调节负荷或可转移负荷,具备双向调节能力的电动汽车、储能、蓄能,以及分布式电源、微网等。传统发电调度中,机组需按照调控指令完全响应,而柔性负荷调度在满足电网调度
    发表于 05-24 14:44 7114次阅读
    柔性负荷<b class='flag-5'>调度</b>,发电<b class='flag-5'>调度</b>的补充

    Storm环境基于权重的任务调度算法

    问题,提出一种Storm环境基于权重的任务调度算法(TSAW-Storm)。该算法首先根据各任务的CPU资源占用情况以及任务间的数据流大小,分别确定拓扑的点权和边权;并利用最大化边权增益的思想,逐步构建起各工作节点中承载的任务集合,在保证集群负载均
    发表于 04-17 10:52 0次下载
    Storm环境<b class='flag-5'>下</b>基于权重的任务<b class='flag-5'>调度</b>算法

    如何在云计算环境进行资源调度算法的研究

    云计算作为一种新兴的商业计算模型被提出以来,经过学术界与产业界的不断推进,云计算正逐渐从理论走向实践,国家也投入巨额人力物力来促进“云计算”在我国落地。基于云环境的资源调度是一个重要研究方向,云
    发表于 01-02 15:18 4次下载
    如何在云计算环境<b class='flag-5'>下</b>进行资源<b class='flag-5'>调度</b>算法的研究

    机场智能调度系统的功能及应用方案

    根据机场地勤运作特点和业务需求,易华录提供了一体化端到端的机场无线地勤调度解决方案,为机场运作提供高效、安全、可靠并且高性价比的特有的机场调度系统,统一承载语音通话、集群语音、工作流指令、信息发布
    发表于 11-16 10:49 3160次阅读

    HLS优化设计的最关键指令

    Unroll 指令在 for 循环的代码区域进行优化,这个指令不包含流水线执行的概念,单纯地将循环体展开使用更多地硬件资源实现,保证并行循环体在调度地过程中是彼此独立的。
    的头像 发表于 01-14 09:41 2583次阅读

    云环境HEDSM工作流调度策略综述

    针对传统算法处理云环境中任务调度时出现的寻优性能差以及寻优方案不能满足用户多样性需求的问题,在考虑任务完成时间、完成成本以及资源闲置率3个优化目标的情况,文中通过模拟启发弌算法调度过程(初始化
    发表于 05-29 15:39 6次下载

    异构环境的多DAG任务调度算法综述

    异构环境的多DAG任务调度算法综述
    发表于 06-21 15:15 13次下载

    什么是指令调度(上)

    指令调度是指对程序块或过程中的操作进行排序以有效利用处理器资源的任务^[1]^。指令调度的目的就是通过重排指令,提高
    的头像 发表于 02-02 09:36 2912次阅读
    什么是<b class='flag-5'>指令</b><b class='flag-5'>调度</b>(上)

    基于优先级调度的嵌入式实时操作系统内核详解()

    基于优先级调度的嵌入式实时操作系统内核详解()
    的头像 发表于 09-06 12:46 866次阅读
    基于优先级<b class='flag-5'>调度</b>的嵌入式实时操作系统内核详解(<b class='flag-5'>下</b>)