调度光纤网卡

!
!
收稿日期:修返日期:基金项目:国家"+(*"计划资助项目!
!
作者简介:吴佳骏()+(,%),男,博士研究生,主要研究方向为编译优化技术(-.
.
/012341315);张兆庆()+*,%),女,研究员,博导,主要研究方向为编译优3网络处理器任务调度!
吴佳骏),",张兆庆)()3中国科学院计算技术研究所,北京)###,#;"3中国科学院研究生院,北京)###&+)摘!
要:按照网络应用及678处理器架构特点建立代价模型,并且以网络应用需求为导向提出了基于时间和吞吐量的任务调度算法(9::;).
该算法兼顾网络程序的吞吐量和延迟需求自动完成网络任务的调度工作,并且在这两项评价网络程序性能的重要指标上得到了满意的结果.
关键词:网络处理器;任务调度;编译器中图分类号::8*文献标志码:=1@ABC05DE55@2-EF>GFE1@==EFHIJ04%.
B5),",KL4GGC01420E545A6784F102@12BF@,45AA@=0D5@A45@2-EF>24=>=1@ABC05D4CDEF02P9::;REF5@2-EF>4GGC01420E53:0=4CDEF02P1E5=0A@F=2FEBDGB245AC42@51S45A1EPGC@2@5@2-EF>24=>=1@ABC05D4B2EP42014CCS,-014=DEEAG@FREFP451@E5QE22FEBDGB245AC42@51S35@2-EF>GFE1@==EF;24=>=1@ABC05D;1EPG0C@F!
!
网络发展初期,其应用的数据流量较小,对网络的研究主要是在完善网络协议和构建服务体系结构上.
这个时期,网络设备主要是使用通用处理器进行网络数据处理.
但是随着各种传输技术的进步,网络带宽的增长速度逐渐超过了T8I处理能力的增长速度,而且这种差距有着进一步加大的趋势.
这时,网络设备开始更多地采用@F(它是在T语言子集上加入网络应用特征的一个扩展).
Z4>@F语言隐藏了复杂的异构多核处理器架构,展现在用户面前的是一个常用的多线程单一处理器编程环境.
;45DF0%94的编译架构是基于[VT(EG@5F@=@4F11EPG0C@F)[,]开发的,原来[VT的前端被替换为Z4>@F前端.
"!
复合式任务调度模型网络程序应用的多样化使得单一模型并不能够满足如今网络应用的需求.
通常的文件传输应用,如电子邮件和视频对延迟并不敏感.
如果包的传输在这种应用情况下慢了几秒,通常不会有太大影响;但是其他应用,如交互式应用和实时应用则对延迟非常敏感,如电话和视频会议对延迟都有非常严格的要求.
如果在电话通话过程中每句话都延迟了"=,那么用户将会认为这样的连接是不能接受的;另外,从一台服务器上播放音频或视频并不需要很低的延迟.
可以用四个参数来描述每种网络应用的需求,即可靠性、延迟、抖动、带宽.
这四个特征合起来就构成了决定一种网络应用所要的服务质量[+].
为了满足服务质量的多样化需求,本文提出了时间驱动模型和吞吐量驱动模型相结合的新型静态任务调度算法9::;第"&卷第,期"##(年,月计算机应用研究复合驱动模型示例使用例子中给定的条件,在时间驱动模型和吞吐量驱动模型下会得到不同的结果.
对于时间驱动模型,最好的解决方案是减少最大通信开销.
这种情况下,和@就会被放在同一个处理器上,8因为代码大小的限制会被放在另外的处理器上.
调度结果展示在图:中就是{(,@),8}.
如果使用吞吐量驱动模型,那么@和8最好安放在同一个处理器.
如果和@放在同一个处理器上,那么执行时间会不平衡,降低了吞吐量.
因此使用吞吐量驱动模型的调度结果是{(),(@,8)}.
虽然第二种方法比第一种方法需要更多的时间处理一个包,但是第二种调度方法会让吞吐量变大.
表:展示了详细的结果.
可以看出,对于网络应用程序的任务调度是不同于通常的并行应用程序的任务调度.
表:>时间A吞吐量驱动模型调度结果模型处理单个包的时间吞吐量时间驱动模型:B:A(CDE)F:A:G吞吐量驱动模型:C:ACF:AC>>为了使得任务调度更好地区分网络应用程序的行为,本文对编译器的编译选项进行修改,提供对网络服务质量的语言支持.
这样任务调度就可以依靠编译选项获取的程序性能取向信息,用时间和吞吐量驱动模型进行复合调度.
#>复合式任务调度算法通过前面的讨论已经初步了解网络处理器上复合式任务调度的基本特点.
但是在实际应用中影响程序的最终性能因素远比抽象模型复杂,H)"%-*32I"的调度算法必须考虑到这些因素.
下面给出影响程序吞吐率与处理延迟的主要因素.
网络应用中对分组的吞吐率取决于执行时间最长的处理阶段.
分组数据的处理延迟由任务调度长度决定,也就是从接收一个分组数据到发送出去所要的平均时间.
在复合调度模型中可以近似地把吞吐量!
表示为!
F"#$.
对于吞吐量的基本抽象描述,其有助于指导调度获得较高的吞吐量.
其中:")"表示运行关键阶段任务的处理器个数,与吞吐率成正比,所以在进行任务调度时可以通过复制关键节点来达到提高程序吞吐率的效果.
但是这个复制个数受限于可得到的处理器个数,并且关键节点随节点复制比率不停变化.
(G)$等于在关键阶段处理一个分组所需要的时间.
关键阶段是指在一个流水线中执行时间最长的瓶颈阶段.
阶段的划分是以9J为单位,也就是一个9J作为一个阶段.
网络应用程序的数据流特点决定了数据延迟不同于传统任务调度长度的效果.
传统任务调度评价性能的指标调度长度等于关键路径的执行时间,而网络应用中数据延迟性能等于处理一个分组数据的时间总和.
数据延迟%可以近似地表示为%F#&'F:('D#&'F:#&)F:*',).
其中:('表示第'个==K处理一个分组数据的执行时间.
影响执行时间的因素很多,其中包含==K的指令条数、执行频率、==K分配到的处理器类型(同一个==K在>>万方数据之和.
算法通过!
"#01&+$2')这个参数来设定调度时吞吐量与延迟的侧重关系.
!
"#34,!
"#值大时调度就更侧重吞吐量.
这个参数在编译时可以通过程序员进行设定,缺省值为5.
.
+6$7+--!
,"8#!
,"9!
"#:-2;;7$(!
,")9&/70'-/762=/)函数-2;;7$(%)((返回%的代码尺寸与)7>@A倍数的最小距离{B2;(0'-/762=/(%)C)7>@A)()7>@AD0'-/762=/(%));B&/$(&,+E6(0'-/762=/(%)*)7>@AD)7>@AFG);}整个"!
!
H调度算法分为两个阶段:+)调度IIJ到>上.
在占用最少>的情况下满足减少数据延迟的需求并且协调任务节点的执行时间.
在代码较少时直接用KL值选取节点合并.
当合并产生的节点变大到最后合并时使用.
+6$7+--来选择合并节点.
E)利用空闲的>使得数据吞吐量最大化.
具体"!
!
H算法如下:计算)7>@A8#+!
85,!
(-和KL;分配IIJ为单个&5…&+;!
85;FF合并节点,消除分组数据的通信延迟;重复BBM'-/8具有最大KL值的一对节点&%&';BBFF0'-/762=/(&%)$0'-/762=/(&')BB2;(M'-/等于空)BB{BBB中止循环;BB}BBFF检查合并后节点是否有可以继续合并的空间;BB2;(>70'-/762=/D0'-/762=/(M'-/)370'-/762=/D0'-/762=/(&!
9&%)370'-/762=/FG分配网络配置任务到&N60+.
/2;(有节点未被分配){BB分配剩余节点到&N60+.
/;BB调度完成;}计算关键的值/FF利用任务复制手段最大化任务的吞吐量;'&(!
8O&O到>7,(上;BB重新计算关键的值/;BB!
99;}算法首先计算)7>@A和各条边的KL,计算过程的时间复杂度为0(1),1等于KK的数目.
然后循环依次分配节点到>上,循环的时间复杂度是0(+),+等于IIJ的个数.
循环内需要选取具有最大KL的节点,其时间复杂度为0(1).
当合并到最后节点时选取最小.
+6$7+--的时间复杂度为0(+),算法计算.
+6$7+--的时间复杂度为0(+G).
循环内需要更新节点的KL值,更新KL值的时间复杂度为0(1).
最后计算关键值,并且选取关键进行复制的时间复杂度等于0(>7,(7,(TH#@>、RP>TU#@>、三个千兆光纤网口;另外还有一个LAL@发包机和三块千兆光纤网卡.
这三个部分构建成一个完整的网络测试平台.
$Q"B测试例子测试例子是使用T+V/&语言编写的三个网络应用程序:+)"WX6Y2$0%[54],包含对LI分组的转发和路由功能,它最主要的是对LI提供路由功能.
按照最长匹配法在路由表中查找对应LI分组的转发地址,然后把分组转发到目标网络中.
E)>I"H[55](I"H,使用MIJ[54,55]规定的分组集合作为程序测试输入集合.
除了对上面提到的三个程序进行性能测试,还使用了其他网络应用例子进行正确性测试,如M@!
(,/$Y'&V+--&/66$&+,6.
+$2',)、Z'H、报头压缩程序以及>U[加F解密应用.
$Q#B测试结果测试中的三个程序使用分组转发率作为评估网络程序性能的指标.
优化选项时,D\W9*/+V所有优化选项被打开,各种优化是相互依赖的.
其中包含基本的标量优化、2,.
2,/优化、*+V/$+00/660',所以可以使用来调度的>个数最多只有六个.
调度算法按照使用一个>逐步递增到使用六个>进行了测试.
从性能测试结果可以看到,在>个数低于四个时,增加>处理器个数,对应程·RW·计算机应用研究G44]年万方数据序性能也得到了线性提高.
当!
"个数超过四个时,带宽利用率接近饱和,程序的性能增长变得平缓.
这时,硬件的访存带宽成了限制程序性能提升的瓶颈.
图#中每条曲线都代表使用$%&个!
"时获取的性能.
这三个程序都在时达到了$--.
的分组转发率.
其中!
/01更达到2)*+,的"3/#&$$开发板极限转发率.
图#4分组转发率测试结果测试结果表明,通过156789:;06生成的代码性能已经可以与专为--手工编写的汇编代码性能媲美.
地址转换很好地完成了在两个不同架构处理器内核之间的地址协调工作,保证了两个异构处理器之间数据的安全共享.
01算法的自动调度结果也满足了网络应用程序对高性能的需求.
这种技术的使用使得建构一个整合的统一编译平台成为可能.
基于整合编译器开发平台使得程序员面对与传统类似的开发环境时,程序编写的工作强度大大降低,并且取得了与手工编写汇编代码相近的性能.
%4结束语网络程序不同于普通程序,网络应用具有较高的并行性.
但是网络应用中的并行性是数据并行性,而且网络程序评价性能指标的延迟时间和吞吐量也与普通任务调度追求的调度长度不同.
本文提出了针对网络应用特性的任务调度算法01.
在下一步的研究工作中,可以把静态调度算法01移植到动态调度系统中,实现自适应的网络任务调度,针对变化的网络状况采用不同的调度策略,以期获得更好的调度效果.
参考文献:[$]T&#U-2$#&'[2])12'[>]WLX31L3"W,YZ3[K#T--+9F896DD:78:@5AIFD;+BA@AD:I9FA78:7AIFM:788N:MA[!
]'X:BB,*F9F,L]:'[U]_'[T]中国科学院计算技术研究所'基于开放源代码编译器L]P#'$["JKL0]'(#--2;-U;$()'S]'5@@+:KK:+C;F9I',FN9IACF98A'7A@K9A6MDA;9ABA6,A;#'$'5@D'[S]\3"3J\Z!
\1'PFD+N@A97A@GF9H,[!
]'>@5AM'\D,@A9M6D:/9A7@:IAX6BB/9A,,,#--#'[$-]3A@GF9H/9FIA,,:78cF9ND')'S]'5@@+:KKGGG'7+CF9ND'F98K@AI5:7CFK!
/01JA7I5D69H'+MC'(上接第#S页)[2(])0d33Y,1ZPY"d/W,1Z0[!
\33OIA+@:F7676BE;,:,CF97F7;,@9:I@B678N68A,[W]#--#,01(S):ST;$-S'[2&]WLWa,PX\3)J!
,d,1=($):(S;&S'[2U]X",03P12->2'6BE:[,'7'],#-->:$-&;$$2'[>-]P]$]单锦辉,王戟,齐治昌'面向路径的测试数据自动生成方法述评[W]'电子学报,#-->,0=($):$-S;$$2'[>#]!
\d"]a,1Z!
/3"]!
''A*N88:78+9F896DAOIA+@:F7,[P]KK/9FIFC@5A$>@5'[>2]\J]\X\!
1''"OIA+@:F7;,6CA@E:78A7A9:IIFD+F7A7@,["JKL0]'#--2U;-(]'5@@+:KKGGG'*FF,@'F98KDF9AK8A7A9:IVAOIA+@:F7V,6CA@E'5@DB'[>>]]L!
\3L_1Yd\'"OIA+@:F7567MB:78:7IFD+F7A7@;*6,AM,E,@ADMA^ABF+DA7@[P]KK/9FIFCPL!
/1\P'#--$:(T-;(T&'[>(]c"ZJ&])Z"P,c:(U(;(T#'[>U]]LJT]闫伟'面向对象单元测试中的异常测试研究[']'武汉:华中科技大学图书馆,#-->'[>S]毛澄映,卢炎生'Pff程序异常处理的分析与测试技术研究[W]'小型微型计算机系统,#--&,=1(2):>T$;>T('[(-]毛澄映,卢炎生'分支测试中测试路径用例的简化生成方法[W]'计算机研究与发展,#--&,>0(#):2#$;2#T'[($]卢炎生,毛澄映'面向对象簇级测试中类间测试序确定方法研究[W]'小型微型计算机系统,#--(,=(&):SS(;SSS'[(#]]\P"d3,P0\]YW,!
\3'"]Y,76N@FD6@AMC96DA;GF9HCF9,@9NI@N96B@A,@;M6@68A7A96@:F7[P]KK/9FIFC\1"'ST'X6G6;:::<"""PFD+N@A91FI:A@E/9A,,,$SST:#T(;#TT'·U2·第T期吴佳骏,等:网络处理器任务调度444万方数据