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

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

3天内不再提示

随机仲裁器的算法实现

CHANBAEK 来源:奇异白勺书 作者:Kim71 2023-09-19 09:35 次阅读

01仲裁机制

提出占用资源的模块需要产生一个访问请求request,所有的请求输入仲裁器之后,仲裁器需要根据仲裁算法,返回一个grant来响应某一模块的请求。

仲裁器只能让一个模块得到许可,因为资源(总线)同一时刻只能由一个模块占用。

常见的仲裁机制有以下三种:

  • 固定优先级仲裁器Fixed Priority Arbiter
  • 轮询仲裁器Round Robin Arbiter
  • 伪随机仲裁器Pseudo Random Arbiter

固定优先级: 即事先确定好各个模块的访问优先级,当多个请求发起时,按照优先级从高到低来给出许可,某些情况下,部分请求的优先级必须高于其它请求(比如车控系统中的刹车请求),这时就要采用固定优先级的仲裁算法;

轮询: 当某次请求被许可之后,则下一个优先级的请求会被置成最高,若下一次需要仲裁的请求中没有最高优先级对应的请求,则维持优先级顺序(按照基础优先级顺序执行本轮仲裁),直到最高优先级请求被响应。

例如:初始优先级从高到低1-2-3,现在来了一波请求序列123-13-23-123-13,那么每轮分别是哪个请求被许可?

答:每轮最高优先级 1-2-2-3-1,被响应许可的顺序 1-1-2-3-1

*也有一种轮询机制是优先级反转的,一个请求被响应许可之后,它的优先级就降到最低。

伪随机: 通过伪随机算法随机赋予请求优先级。

02算法实现

1、Fixed Arbiter

设 req_i [3:0], 由于是固定优先级,可以事先约定:低位优先级高,高位优先级低

(注意仲裁器的输入端口已经确定好优先级,因此外部请求信号连接时应根据仲裁器规定的优先级顺序按需求连接)

在这个前提下,仲裁的本质其实就是从低位到高位寻找第一个“1”

那么有没有什么逻辑操作可以快速定位一个序列中从低到高的第一个“1”呢?

显然,减1操作就符合这个需求。在二进制的减1操作中,低位如果是0,就会向前借位,结果是1,直到借位的那一位是1,结果才得0,因此只需要根据结果从低到高的第一个0在哪一位就能确定哪一位该被许可响应。

假设这次请求req_i = 4'b1010,即第二和第四个设备发起了请求,那么req_i-1 = 4’b1001,可以从低到高的第一个0位于第二位,也就是req_i[1]对应的请求可以被响应。

那么如何将这个算法用简单的逻辑实现呢,用序列检测的方法去遍历req_i-1的结果显然过于复杂且耗时,会大大拖累性能。最好能用一个简单的组合逻辑就把这个0所在的位找出来。

可以观察到,对req_i-1的结果按位取反后,得到~(req_i-1)= 4‘b0110,与req_i只有一位相同,且那一位就是被响应许可的位。于是gnt [3:0]的逻辑就呼之欲出了:

gnt_o = req_i & ~(req_i-1);

其实也很好理解,减1操作,相当于对参与运算的低两位10进行了取反,对于被减数来说,前两位10其实并没有变化,直接落到结果对应的位上,所以对结果进行取反得到0110,再和被减数本身按位与,得到的结果是0010,直接筛选出了被借位的那个“1”

2、Round Robin Arbiter

有了固定优先级仲裁器的珠玉在前,轮询仲裁器的算法自然就跃然纸上。既然核心思想就是通过减1操作来找出需要被响应的请求,那么已经响应过的请求直接让它不参与减1计算即可。被减数是外部输入的req_i,是不能动的,但是减数是可以操作的,假如req_i[0]的请求刚被响应过,那么只需要让减数的1左移一位得到0010,就相当于让最低位不参与计算,那么按照轮询规则,下一个被响应的请求就是req_i[1]

图片

但凡事皆有例外,固定优先级的减1操作可以保证一定能检索到优先级最高的那个请求(只要req_i不是全0),但是轮询算法因为减数的移位会把低位排除计算,可能出现没被排除计算的请求位没有1,而被排除的请求位有1的情况,如下图所示,此时根据我们的算法得到的结果是0000,低两位的设备发起了请求,但是仲裁器却没有输出,出现了功能错误。

图片

这是由于我们没有将被排除计算的低位请求加入循环移位的仲裁机制中,如果高位均没有发起请求,仲裁器还是需要按照约定的优先级顺序给低位的请求发起响应。

根据这个思路,自然就能想到:当高位没有发起请求,而低位有请求时,按照固定优先级顺序算法再计算一次。但是问题又来了,引入新的逻辑来判断gnt_o的输出以及再进行一次仲裁又会拖慢响应速度,最好有个一步到位的算法,能同时解决两种情况下的轮询仲裁。

回归到优先级算法的本质,上图中 gnt_o输出全0的原因是向上借位溢出,向上借位的本质又是高几位进行减1操作,那么让req_i变成我们需要借位的那个“高几位”不就行了吗?

图片

如图,将req_i和gnt_o进行double拓宽,这样就能兼顾高位有无请求两种情况了。最后一步,就是将double过的gnt_o再变回原来的位宽。根据算法,double_gnt_o要么高四位有效,要么低四位有效,而且是独热的(One-hot),因此只需要将前四位与后四位进行按位或操作就可以得到正确的gnt_o

assign double_reqs = {2{reqs_i}};
assign double_gnts = ~(double_reqs - priority_flag) & double_reqs;
assign gnts_o = double_gnts[2*REQ_NUM:REQ_NUM] | double_gnts[REQ_NUM-1:0];

3、Pseudo random Arbiter

随机仲裁器其实就很好实现了,每次有请求到来时,让减数中独热的那一位出现在随机的位置上,就实现了优先级的随机生成。本文不再赘述。

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 算法
    +关注

    关注

    23

    文章

    4608

    浏览量

    92847
  • 信号
    +关注

    关注

    11

    文章

    2790

    浏览量

    76736
  • 仲裁器
    +关注

    关注

    0

    文章

    12

    浏览量

    6640
收藏 人收藏

    评论

    相关推荐

    如何在Virtex-II Pro上实现仲裁

    (同步RAM)。地址为12位,数据为8位。我想在Virtex-II pro上实现仲裁,两个PowerPcs同时独立运行。我计划在两台电源上同时运行2个不同的程序,并使ppcs想要访问共享内存。我假设两个
    发表于 05-28 12:37

    如何在VHDL中实现简单优先级仲裁

    本文着眼于仲裁的用例和优点,以及在VHDL中实现简单优先级仲裁仲裁是任何现代计算机系统的重
    发表于 12-23 06:38

    深入探讨一下AHBzongxia仲裁仲裁

    1、AHB仲裁仲裁随着AMBA总线-AHB系列的逐步推进,现在在AHB总线中,基本能用来让主从机传输数据的要素都已经补齐了,所以最后一个功能部分,我们将深入的探讨一下,如果多个主机同时需要获得
    发表于 06-09 17:30

    如何配置sequence的仲裁算法和优先级及中断sequence的执行

    出来当前transaction产生自哪个sequence,以及是循环的第几次。仿真结果如下,可以看得出来在没有配置仲裁算法的情况下,即使我们为sequence都分配了权重值,sequencer对三个
    发表于 09-23 14:35

    PCI总线仲裁的设计及实现

    本文简要介绍了PCI 总线的仲裁机制, 完成了PCI 总线仲裁核心的设计、实现。通过ModelSim 进行了软件仿真,最后在XILINX 公司的FPGA 上加以了验证。
    发表于 09-03 08:18 27次下载

    SOC总线仲裁算法的研究

    集成到SOC 中的功能模块越来越多,对于共享总线的SOC 系统,片上仲裁是使得各个模块有效运作的必要手段。本文论述了SOC 仲裁的基本原理,首先从目前SOC 系统中常用的仲裁算法
    发表于 09-15 15:35 14次下载

    SOC总线仲裁算法的研究

    集成到SOC中的功能模块越来越多,对于共享总线的SOC系统,片上仲裁是使得各个模块有效运作的必要手段。本文论述了SOC仲裁的基本原理,首先从目前SOC系统中常用的仲裁算法入手
    发表于 07-17 17:07 38次下载

    OPB总线仲裁的RTL设计与FPGA实现

    本文详细介绍了OPB总线仲裁的信号和仲裁机理。在QuartusII8.0平台上,分别用固定优先级算法和LRU算法,用硬件描述语言(veri
    发表于 07-17 18:10 25次下载

    基于EPLD的PCI总线仲裁的设计与实现

    摘 要: 以自行研制开发的PCI高速总线背板为背景,系统地论述了PCI总线的仲裁机制、总线的缺省占用、仲裁信号协定及优先级仲裁算法,给出了采用EPLD
    发表于 06-20 13:32 1141次阅读
    基于EPLD的PCI总线<b class='flag-5'>仲裁</b><b class='flag-5'>器</b>的设计与<b class='flag-5'>实现</b>

    随机块模型学习算法

    主要挑战.提出一种精细随机块模型及其快速学习算法,该学习方法基于提出的模型与最小消息长度推导出一个新成本函数,利用期望最大化参数估计方法,实现了边评价模型边估计参数的并行学习策略。以此方式显著降低
    发表于 01-09 18:20 1次下载

    基于分组机制的位仲裁查询树防碰撞算法

    提出了一种基于分组机制的位仲裁查询树(G BAQT, bit arb itration query tree bas ed on gro uping mechanis m)算法。该算法根据标签lD
    发表于 02-26 11:22 0次下载

    如何进行SOC总线仲裁算法的研究资料说明

    集成到SOC 中的功能模块越来越多,对于共享总线的SOC 系统,片上仲裁是使得各个模块有效运作的必要手段。本文论述了SOC 仲裁的基本原理,首先从目前SOC 系统中常用的仲裁算法入手,
    发表于 06-26 14:32 5次下载
    如何进行SOC总线<b class='flag-5'>仲裁</b><b class='flag-5'>算法</b>的研究资料说明

    如何实现RFID系统上行链路的多标签冲突检测算法

    提出一种应用于RFID 系统上行链路的多标签冲突检测算法, 并给出了参考实现电路。依算法, 对电子标签进行随机分群, 在群间做随机避让, 在
    发表于 01-15 17:04 3次下载
    如何<b class='flag-5'>实现</b>RFID系统上行链路的多标签冲突检测<b class='flag-5'>算法</b>

    基于SaaS的替代性纠纷在线仲裁系统

    互联网仲裁近年来成为数字经济领域法律纠纷的一种重要解决机制,实现了“线上争议、线上解决”。然而,现有互联网仲裁系统并不能满足高要求的正当程序及充分保障当事人合法权利,符合仲裁法律程序的
    发表于 06-15 14:51 9次下载

    基于Python实现随机森林算法

    机器学习算法是数据挖掘、数据能力分析和数学建模必不可少的一部分,而随机森林算法和决策树算法是其中较为常用的两种算法,本文将会对
    的头像 发表于 09-21 11:17 1204次阅读
    基于Python<b class='flag-5'>实现</b><b class='flag-5'>随机</b>森林<b class='flag-5'>算法</b>