芯片间时间触发消息堆叠调度方法_臧光界.pdf
《芯片间时间触发消息堆叠调度方法_臧光界.pdf》由会员分享,可在线阅读,更多相关《芯片间时间触发消息堆叠调度方法_臧光界.pdf(9页珍藏版)》请在咨信网上搜索。
1、http:/DOI:10.13700/j.bh.1001-5965.2021.0553芯片间时间触发消息堆叠调度方法臧光界1,2,李峭2,*,王彤2,熊华钢2(1.中国航空研究院,北京100029;2.北京航空航天大学电子信息工程学院,北京100191)摘要:时间触发(TT)通信方式应用于芯片间互连网络,以保证航空电子通信任务之间消息传递的严格时间确定性。当航空电子任务具有多种操作模式,属于不同模式的芯片间的时间触发调度表会重叠占用时隙,提出芯片间时间触发消息堆叠调度方法,以提高利用网络资源的灵活性和效率,同时减小应用层消息由于等待时间触发时间窗的排队延迟。仿真实验表明:与超调度方法相比,所提
2、方法能够减小芯片间互连网络中时间触发消息的总端到端延迟和链路平均时隙占用率,对于端到端延迟时间较长且链路平均承载消息传输较多的场景,采用所提方法减少端到端延迟的效果更显著。关键词:芯片间互连;时间触发消息;操作模式;堆叠调度;端到端延迟中图分类号:TP393文献标志码:A文章编号:1001-5965(2023)07-1838-09在综合模块化航空电子系统(integratedmodularavionics,IMA)是最常见的航空电子系统体系架构1的基础上,分布式综合模块化航空电子系统(distributedIMA,DIMA)采用具有时间触发(time-triggered,TT)能力的交换式网络
3、实现安全关键性消息的严格周期确定性,如 SAEAS6802 标准定义的时间触发以太网(time-triggeredethernet,TTE)2。随着可综合模块逐渐朝着微小化方向发展,综合化互连将不仅局限于局域网,片上系统(systemonchip,SoC)之间也可以进行综合化互连3。例如,欧洲的 DREAMS(DistributedReal-timeArchitectureforMixed-criticalitySystems)项目提出了多核芯片构成的混合关键性流量网络模型,旨在实现网络的安全性和实时性,提高应对突发情况的能力4。Paukovits5和 Kopetz6等提出了时间触发片上网络(
4、time-triggeredsystem-on-chip,TTSoC)的概念,Urb-ina 通过 TTE 实现了多个多核芯片互连的跨层次体系结构7,文献 89 对片内和片间互连通信方式进行了研究,提出了实现片内片间通信的综合互连网络模型。传统上 TT 消息在网络中传输依照离线生成的调度表。文献 1011 提出了基于满足性模理论(satisfiabilitymodulotheories,SMT)的 TTE 调度方法,对消息的端到端延迟、任务的优先级等进行约束,得到 TT 消息的调度表。文献 12 提出一种基于贪婪随机自适应搜索算法的 TTE 调度方法。随着混合关键性系统的规划与设计方式的进展,
5、需要改进调度方法提高其灵活性,使其可以在一定程度上不需要重新离线配置,就可以承载意料之外的关键流量。文献 13 提出了一种芯片间互连网络 TT 消息调度方法,文献 14 使用免疫算法对芯片间 TT 消息调度方法进行了优化,但都未提出提高其灵活性以对新加入 TT 消息进行调度的方法。文 献 15 提 出 使 用 拓 展 的 软 件 定 义 网 络(software-definednetworking,SDN)来实现动态的数据包处理和调度;文献 16 通过调整现有流量在各收稿日期:2021-09-15;录用日期:2022-01-16;网络出版时间:2022-02-1511:34网络出版地址: J.
6、北京航空航天大学学报,2023,49(7):1838-1846.ZANG G J,LI Q,WANG T,et al.Stacking scheduling method for time-triggered messages in off-chip networkJ.Journal of BeijingUniversity of Aeronautics and Astronautics,2023,49(7):1838-1846(in Chinese).2023年7月北京航空航天大学学报July2023第49卷第7期JournalofBeijingUniversityofAeronautics
7、andAstronauticsVol.49No.7端口的触发时间来为新加入消息预留时隙,但是该方法改变了原有消息的实时性需求,且在网络规模较大、流量较多时难以实现。以上方法都属于超调度方法(super-scheduleapproach),即不考虑通信任务所属的模式,只是将其所有模式中的消息依次调度。网络互连通信中的所谓“模式”,指实现各种给定功能的不同工作阶段,在不同模式中,网络传输的消息不同。文献 17 提出了一种堆叠调度方法(stackedschedulingapproach,SSA),将不同模式下的 TT 消息堆叠在同一时隙,该方法的目的在于为偶发消息预留带宽;文献 18 给出了堆叠调度
8、方法的具体实施方案,但只适用于交换机控制模式切换的情况,并只考虑了芯片间互连中交换结构均集中于各个端口的情况。基于以上研究现状,本文提出一种芯片间综合化互连网络 TT 消息堆叠调度方法,使 TT 消息的调度综合考虑了 TT 消息的顺序、模式及芯片间互连网络的拓扑等因素,并根据给定的芯片数量及消息的属性、所属模式、顺序关系等条件,给出生成芯片间互连拓扑结构和 TT 消息调度表的方法。该方法可使链路对网络带宽的利用率达到最大,并尽可能减小流量的端到端延迟,提高芯片间互连网络的灵活性和适应性。1系统模型1.1芯片间互连结构芯片间互连的拓扑结构可以是规则的(如网格形),也可以根据应用要求设计呈现不规则
9、的拓扑,而前者可以被看作后者的特例。为了一般性,本文提出并讨论的调度方法可以适用于不规则的拓扑结构。图 1 为不规则的互连拓扑结构。V1l1l12l11l21l15l9l17l4V5V2V4V6V7V3图1芯片间互连结构示意Fig.1Sketchmapofoff-chipinterconnection图 1 中,V1V7 表示芯片,在网络拓扑中以节点形式表示,芯片之间通过开放式的介质无关接口建立物理链路,进行全双工通信,目前常用的芯片间互连方式有 SPI 总线协议、I2C 总线协议、RapidIO 架构等。图中芯片之间的连线表示物理链路,芯片的物理链路数量和布局根据数据传输的需求确定,在一般情
10、况下是不对称的。为使链路序号反映链路两端节点,不失一般性,对链路序号 i 的标定依据式(1)进行:i=n1k=nsk(nd)(1)式中:n 为网络芯片数;s 和 d 分别为该链路两端芯片编号的较小值和较大值。G(i,j)=1G(i,j)=0可以使用 n 阶对称矩阵 G 在算法中表示芯片间互连网络的拓扑结构,n 为网络中芯片的数量,其主对角线上各元素为 0,其他元素中若,则认为芯片 Vi 与 Vj 由物理链路直接相连,若则认为 2 个芯片不由物理链路直接互连。1.2芯片间互连 TT 消息模型M=m1,m2,mni=1,2,n设在芯片间互连网络中传输的 n 条消息集合为,其中,第 i 条 TT 消
11、息 mi()的属性可表示为mi=(2)式中:pi为消息周期;si为消息长度;pathi以 TT 消息源节点、中转节点、目的节点编号的有序数列表示 TT 消息的传输路径;oi为消息在经过各条物理链路上的发送起始时间偏移量;modei为该 TT 消息在该网络中所处的模式,TT 消息不会在自身不处于的模式中产生。在堆叠调度方法中,默认所有TT 消息的周期、长度和模式已知,计算每条 TT 消息的发送起始时间偏移量和路径,并由此规划芯片间互连网络的拓扑。1.3堆叠调度原理所谓堆叠,即在同一时隙内,同时安排 2 条或更多的 TT 消息传输,被堆叠的 TT 消息不属于同一模式,因此不会同时产生和传输引发冲突
12、。传统的TT 网络中,事先已为每条周期性消息分配一段固定的传输时隙,因此,在一条物理链路的某段时隙,即使该时隙上没有对应 TT 消息的实例传输,系统也不会将其分配给其他消息。在对多模式网络进行调度时,若采用超调度方法,则在多模式情况下会导致很低的带宽利用率和很差的适应性。堆叠调度方法则避免了对带宽和时隙的浪费,提高了网络的适应性。例如,某 TT 网络中的一条物理链路在一段时间之内的 TT 消息传输情况如图 2 和图 3 所示。设该网络具有 3 种操作模式,分别为 mode1、mode2、mode3,在该链路上有 6 条 TT 消息传输,分别为 m1、m2、m3、m4、m5、m6,周期均为 T,
13、其中,m1、m2属于mode1,m3、m4属于 mode2,m5、m6属于 mode3。使用第7期臧光界,等:芯片间时间触发消息堆叠调度方法1839时间窗来表示 TT 消息在链路上的调度结果19,当使用超调度方法进行调度时,如图 2 所示,虽然由于不需要在各芯片中加入模式转换功能使得调度更加容易实现,但是在该调度方法下,时间资源要按多种模式下 TT 消息负载之和预留,因此留给低优先级流量的时隙更少,当该链路所在网络处于运行状态时,如果有新的消息在线加入,网络将很难为其在该链路上分配时隙,导致该网络具有较差的灵活性和适应性。图 3 为该链路采用堆叠调度方法的调度结果。转换请求消息包含有要求目的节
14、点转换为指定模式的信息,模式转换请求消息可通过修改的协议控制帧(modifiedprotocolcontrolframe,MPCF)传输,MPCF 是具有最小长度的标准以太网帧(46Byte),与普通协议控制帧(protocolcontrolframe,PCF)不同,其类型字段被设置为 0 x0619,且将 PCF 的保留和透明时钟字段都改为数据加载字段。MPCF 与PCF 具有相同的优先级,高于 TT 和 RC 流量,为避免干扰时钟同步过程,MPCF 在同步过程之外传输。当网络的操作模式变化时,由一个或几个节点发出模式转换请求消息,通过链路传输至网络的其他节点,收到转换请求消息的节点在该网络
15、中所有 TT 消息的超周期末尾时转换模式,使用新模式下的调度表。与超调度方法相比,堆叠调度方法增加了链路时隙的利用率,能够在运行过程中为更多必要的事件触发消息分配时隙,增加了TT 网络的灵活性和适应性,同时减小了被堆叠消息的端到端延迟。1.4芯片间网络模式切换方法在由交换机和端系统组成的交换式网络中,由网络中的主节点发送模式更改消息,从节点接收模式更改消息后在该超周期的末尾改变操作模式20。但是在芯片间互连时间触发网络中,网络的拓扑及每个节点需要处理的消息数在调度完成之前都不确定,因此并不能设定一个或多个可以产生和传输模式更改消息的主节点。在模式更改消息设计方面,若模式更改消息的传输路径与该模
16、式下 TT 消息的传输路径不同,则很可能出现模式更改消息早于某条 TT 消息帧到达其目的或中转节点的情况,在此情况下,由于该节点的模式已被改变,将不会为该TT 消息帧提供接收或转发服务,造成 TT 消息的丢失;另外,若某条 TT 消息在网络中的跳数较多,当全局时钟到达超周期的末尾时,该 TT 消息可能还未完成传输过程,此时更改模式同样会造成消息的丢失。在交换式 TT 网络的模式切换方法基础上,提出一种以单条 TT 消息为单位,依节点顺序依次切换模式方法,即当前模式需要切换时,该模式下每条 TT 消息的起始节点在发送当前 TT 消息的最后一帧后紧接着发送一条与此 TT 消息传输路径相同的模式转换
17、请求消息,路径上的每一个转发节点芯片在接收到此模式转换请求后即停止对应 TT 消息的转发和接收服务,当一个节点接收到所有该模式下此节点接收和转发的 TT 消息对应的模式转换请求时,改变该节点的 工 作 模 式。图 4 为 该 模 式 转 换 方 法 的 一 个实例。path1=V1,V3,V4path2=V2,V3,V4图4 中,操作模式1 包含2 条TT 消息,m1的传输路径,TT 消息 m2的传输路径,当网络从模式 1 切换至模式2 时,m1的起始节点 V1 和 m2的起始节点 V2 分别沿传输路径发送模式转换请求消息 cm1和 cm2。如图4(a)所示,假设cm1先于cm2发送,V1 发
18、送cm1后进入模式 2,V2 此时还处于模式 1,在图 4(b)中,V2 发送 cm2后进入模式 2,此时 cm1已先到达V3,由 V3 接 收 后 向 V4 转 发,此 时 V3 停 止 对m1的接收和转发服务,但仍属于模式 1,仍为模式 1 的其他消息提供服务,在图 4(c)中,当 cm2到达 V3 后,V3 已接收到模式 1 的所有模式转换请求 消 息,V3 切 换 为 模 式 2,同 理,V4 在 接 收 到cm1和 cm2后也切换为模式 2,整个网络模式切换完成,如图 4(d)所示。m1m2m3m4m5m6时间模式T0mode1/2/3图2物理链路在多模式情况下使用超调度方法的调度结
19、果Fig.2Schedulingresultsofphysicallinkusingsuper-scheduleapproachinmulti-modem5m3m1m2m4m60Tmode1mode2mode3模式时间图3物理链路在多模式情况下使用堆叠调度方法的调度结果Fig.3Schedulingresultsofphysicallinkusingstacking-scheduleapproachinmulti-mode1840北 京 航 空 航 天 大 学 学 报2023年2本文方法oi=toji对于一条 TT 消息 mi,若其发送起始时间偏移量,则其第 j 帧的发送时间满足:oji=t+
20、jpi(3)因此对于一组 TT 消息,只要确定了其第一个超周期内的偏移量,即可确定每条 TT 消息在所有时段上的调度结果。设 ci为 mi的执行时间,满足:ci=sir(4)式中:r 为网络数据传输速率。在一条物理链路上,可供调度的时间资源被记为 S,A 为一定数目的整数集合,其中会出现几组连续的整数,将非空集合 A 中出现的连续整数组中的数字最多的那一组的数字个数记为 LLC(A),集合H 表示一个超周期内所有时间,集合 U 表示超周期内已被调度的所有时刻,集合 R 表示一个超周期内可调度的空余时间,则有U R=H(5)U R=(6)mi在该链路上可调度的条件为20ci LLC(R)(7)若
21、 mi需经多个中转节点转发,其在前一链路上传输的结束时间为 te,后一链路上传输的开始时间为 ts,这 2 个参数应满足:te ts(8)图 1 所示拓扑用矩阵表示为G=0100100100010100010010010010110000000010010110010(9)由于拓扑是不确定的,可以先假设所有节点之间都是互相连接的,再分别在每个模式下对消息依序在各链路上寻找时隙,在此期间对已使用端口数等于其最大端口数的芯片周围链路进行“剪枝”,即切断与其相连但未被使用的链路。根据以上规定和原则提出芯片间网络 TT 消息堆叠调度方法的具体算法,在该算法中定义了几种操作函数,包 括 模 式 提 取
22、函 数 checkmode、链 路 检 查 函 数linkavailable、时隙匹配函数 LLCavailable 及剪枝函数 cutedges,具体步骤如下。输入输入:TT 消息集合 M,芯片数量 n,消息数量msg,模式数 mo,各芯片端口数 a。输出:输出:拓扑矩阵 G,调度表 S。1:functionOFFCHIPSTKS St G fillbyone(n)E2:,i 13:fortomoMicheckmode(M,i)msgisize(Mi)4:,for j 15:tomsgiroutej=kshortestpath(sourcej,destj,G)6:rtn size(route
23、j)7:for k 18:tortnlinkavailable(G,routej(k)=true9:ifLLCavailable(St,routej(k)=true10:ifpathjroutej(k)11:St Stsinglesche(routej(k),cj,St)12:13:break14:endif15:endifV1V1V2V3V3V4V4V4cm1cm2cm1cm2模式1模式2V2V1V1V3V3V2V2V4(a)V1发送模式转换请求消息cm1(b)V2发送模式转换请求消息cm2(c)V3接收cm1、cm2后转为模式2(d)所有芯片转换为模式2图4芯片间互连网络模式切换过程实例F
24、ig.4Anexampleofmode-changeinoff-chipinterconnectionnetwork第7期臧光界,等:芯片间时间触发消息堆叠调度方法1841G cutedges(pathj,G,St)16:17:endfor18:endforS SSt,St 19:20:endfor21:endfunction首先,对 TT 消息按照重要性排序,若无已给出的重要性规定,则优先调度周期小的消息。为了给通过 MPCF 传输的模式转换消息预留时隙,在计算每条 TT 消息的帧长时,都在其原长度的基础上加上 MPCF 的长度,这样在没有模式转换请求的情况下,该预留时隙也可供其他事件触发消
25、息传输使用,在一定程度上减少了事件触发消息的拥塞。在本文方法中,首先假设所有芯片之间均互相连通,函数 fillbyone(n)表示创建一个所有元素均为1 的 n 阶方阵。然后按照模式消息链路的顺序 依 次 调 度,对 于 原 始 消 息 列 表 M,使 用 函 数checkmode 将其中属于 modei的所有消息提取出来组成新的消息列表 Mi。路径确定方面,可以使用k 最短路径方法(k_shortestpaths)20,依据拓扑和消息的源节点和目的节点确定 k 条实现传输的最短路径,依次判定该路径是否可行。函数 linkavailable和 LLCavailable 分别用来判断该路径在拓扑
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 芯片 时间 触发 消息 堆叠 调度 方法 臧光界
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。