（计算机科学与技术专业论文）网络应用到网络处理器资源映射研究.pdf

国防科学技术人学研究生院学位论文 摘要 为满足复杂多样的网络协议的处理能力和灵活性需求，网络处理器已经广泛应用于多 种网络设备中。网络处理器是一种支持网络协议高速实现的具有高性能i o 组件的单芯片 多处理器。它的可编程性带来许多a s i c 没有的优点。网络处理器芯片广泛采用 m p s o c ( m u l t i p r o c e s s o rs y s t e m o n c h i p ) 结构实现。 采用m p s o c 结构设计网络处理器时，设计者将面临新的挑战。随着深亚微米工艺的 迅速发展，芯片的集成度和操作频率越来越高，在单个芯片上能集成越来越多的异构处理 资源，如多个通用r i s c 处理器，各种专用协处理器和硬件加速器等。在设计的初始阶段 就使用r t l 描述语言构建一个可执行模型的传统设计方法越来越困难。为了更有效的开发 设计空间，设计必须从一个更抽象的层次上开始。网络处理器的设计过程中迫切需要一种 设计方法来帮助设计者解决面临的问题，具体来说就是：帮助设计者如何根据网络应用合 理的选择各种异构处理资源，将网络应用的各种任务映射到相应的处理资源上，形成网络 处理器的体系结构，并由此指导网络处理器的早期设计。 为了解决上述问题，本文对网络应用到网络处理器资源映射的主要技术和方法进行了 研究和分析，并将遗传算法( g a ，g e n e t i c 础g o r i t h m s ) 引入映射过程，提出了一种基于g a 的网络应用到网络处理器资源的映射方法。该方法采用加权数据流进程网络描述网络应 用，将各种异构处理资源参数化，采用遗传算法将加权数据流进程网络映射到处理资源上， 形成性能和实现代价均可预测的网络处理器体系结构模型，由此指导网络处理器的早期设 计。最后我们采用s o p c 技术在f p g a 上实现网络处理器原型。 关键词：网络处理器遗传算法s o p c 报文分派器 国防科学技术大学研究生院学位论文 a b s t r a c t d u et ot h ec o m p l e x i t ya n dd i v e r s i t yo fn e t w o r kp r o t o c o l s ，n e t w o r kp r o c e s s o rb a sb e e n w i d e l yu s e d i nn e t w o r ke q u i p m e n t st om e e it h e n e x i b t ya n dp e r f o 加1 a 1 1 c er e q u i r e m e n t s n e t w o r k p r o c e s s o ri su s l l a l l yt r e a t e da sa m u l t i p r o c e s s o rs y s t e mo na s i n 百ec h i pw h j c hc o n t a i n s m u l t i p i eh i g hp 曲f m a n c e 啪c o m p 叽c n t sa n ds u p p o n sh i 曲一s p e e dr c a 王i z a c i o no fn e t w d r k p r o t o c 0 1 n p sp m g r a m m a b i l i t y 嘶n g sm a n ya d v a n t a g e sc o m p a f e dw i t ha s i c n pc h i ph a sb e e n b r o a d l yi m p l e m e n t c db ym u l t i p r o c e s s o rs y s t e m o n c h i p ( m p s o c ) 砌i t e c t u r c d e s i 驴e r sh a v et 0f a c cn e w 曲a l l e n g e sw h e nn p i si m p l e m c n t c db ym p s o ca r c l l i t e c t u r c w i t ht h ed e v e l o p m e n to fd e c p 蚰b - m i c m t e c h n o l o g y c h i p sf r c q u e n c y 如di t c g m t i o n9 0 e s h i 曲e r ，m o f ea n dm o 碓p l o 踣脚u r c ec a ni n t e g r a t ei n t 0as i n g l e 出p 跚c h 罄af e wo f g e n e r a l - p l l t p er i s cp m s s o r ，v a f i o 璐s p e c m cc o p f o c e s s o r 卸dh 鲫如a 璋a c c c l c m t 0 i ；e t c t h et r a d i t i a ld e s i 弘m c t h o dt 0c 0 璐m l c t sc x e c u t a b l em o d e lw i t h 瑚 ll 锄印a g ea tt h ef i r s to f d e s i 印i sn o tf e 勰i b l en o w ho r d c rt 0e m d c n n yc x p l o r et h ed e s i 印s p a c co fn e m o r kp f o c e s s o r s ， t h ed e s i g np m c o d u 糟1 1 a st os a r ta tm o r ea b s t r a c tl e v e l ，y e te x e c l l t a b l em o d e l s n o 、man e w d c s i g n e t h o di sn e e d c df oh e l pd 髂i 萨e r sf t l l i sp r o b l e m ，m o r cc o n c f c t e l yi s ：h a wt 0c h o o s ea u k i n d sh e t e m g e n e o u sp m c e 鹞r 龇r c eb 鹪e d0 nn e t 、v o r ka p p l i c a t i o n sa i l dm a pt a s k s t os u i t a b l e p r o c e s sr e 妁u r c e ，t h e nf o n nn pa r c h i t c c t u r ea n dg u i d en p se a r l ys l a g ed c s i 萨b yt 1 1 i s t 0s 0 l v et h e s ep 曲l e m ss t a t e da b o v e ，t h i sp a p e rm a d ed e e ps t u d yo bt h ek c yt e c h n o l o 百e s a n dm e t h o do fm a p p i n gn e t w o r ka p p i i c a t i o n so n t op r o c e s sr e s o u r c e ，柚dp r e s e n tam a p p i n g m e t h o db a s e do ng e n e t 主ca l g o r i t l m f i r s t l y n e t 、v o r ka p p l i c a t i o n sa r cd e s c r i b e db yw e i 曲t e d d a t a n o wp m c 鼯sn e t w o r k 柚de a c hr e s o u r o ei s p a r 锄e t e r i z e da tf i s t s e c o n d l y 、犯i g h t e d d a t a f l o wp 眦路n e f w o r km 印p e do n t op a r a m e t e z e dr c s o u r c e f i n a l l y an c t w o r kp r o c e s s o r a r c b i t e c t u r em o d e li s 啪s t n l d e dt oc v a l u a t es y s t e mp c r f o n n a c e ，a n dg l l i d en e t l j l r o r kp r o c c s s o r d e s i 弘a te a r l ys t a g c a t 也el a s tp a n a t i o no ft h i sp a p e r ，w ei m p l c m e ms o p c i b a s c dn 咖0 r k p m c e s s o rp i o l o t y p ci nf p g a k e y w o 陆：n e t w o r kp r o c e s s o r g e n e t i c 舢g o d l h ，s o p c ，p a c k e td i s p a t c h c r i i 国防科学技术大学研究生院学位论文 图目录 图l 一1y 图设计方法3 图1 2s p a d e 框架的结构6 图2 1i p v 4 转换为w d p n 模型示意图一1 2 图2 2 进程的聚合操作1 3 图2 3 单进程的2 阶复制示例1 4 图2 4 网络处理器硬件结构示意图1 5 图3 1 遗传算法的基本运算过程2 3 图3 2 基于遗传算法的n p 设计流程2 5 图3 3 高度值计算示例2 7 图3 4 进程的集合表示2 9 图3 5 译码与实现3 0 图3 6 基于集合表示的交叉过程3 2 图3 7 测试实例3 4 图3 8 群体适应度变化曲线3 6 图3 9 平均延时变化曲线3 6 图3 1 0 平均使用面积变化曲线3 6 图4 1网络处理器芯片原型结构4 0 图4 2 网络处理器芯片原型的外部接口4 1 图4 3 利用s o p cb u i l d c r 创建系统模块4 3 图4 4n i o s 参数配置4 3 图4 5 报文分派器的逻辑框图4 4 图4 6 报文分派器与外部的接口4 5 图4 7 网络处理器芯片原型报文转发率4 7 图4 8 报文乱序率比较4 7 图4 9 基于哈希映射报文分派的p e 负载4 8 图4 1 0 基于轮询报文分派的p e 负载4 8 国防科学技术大学研究生院学位论文 表目录 表2 1w d p n 进程的统计参数描述1 1 表3 1 体系结构配置参数及配置约束3 5 表3 2 进程到资源的映射关系3 5 表3 3 本文的遗传算法与s g a 进化过程比较3 7 表4 1 芯片原型硬件模块功能描述表4 1 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：圈终廑周到圆鳖熊堡墨瓷噩噬盟盈窀 学位论文作者签名：堑塑日期：2 s 年p 月；日 学位论文版权使用授权书 本人完金了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：鲤簦廛垣到塑鳖矬堡墨连噩丝盘叠窥 学位论文作者签名：起型日期：w 以年f 工月；日 作者指导教师签名：赵卤i 丝日期：a 帕r 年肛月引日 国防科学技术大学研究生院学位论文 第一章绪论 进入2 1 世纪，网络发展越来越明显地呈现出宽带化和综合化的趋势。首先，随着网 络传输技术的发展，特别是光纤传输技术的成熟，网络链路速率己从1 5 5 m b i t s 、6 2 2 m b i 佻 迅速攀升到2 5 g b i t s 、1 0 g b i t s ，甚至4 0 g b i t s 。其次，由于三网合一趋势的日益增强，以 及人们需求的快速增长，要求网络能够同时承载语音、数据、多媒体以及其他形式的网络 业务。为了更好地适应网络宽带化和综合化的趋势，弥补通用处理器和a s i c 芯片在网络 处理方面的不足，同时也结合了通用处理器和a s i c 的优势，人们设计了网络处理器m p ， n e m o r kp r o c e s s o n 。 1 1 1 网络处理器介绍 1 1 研究背景 网络设备的研制开发和互联网的发展相互促进。翠期的网络设备主要由通用c p u 和专 用标准设备组成，功能依赖于软件设计，因此容易扩展，便于适应网络中出现的新协议和 新业务。这种设计的缺点是处理能力低，无法满足网络传输技术的发展以及性能的要求。 随着网络规模和接口速度的增加，网络设备厂家开发出了基于a s i c 的简单且具有固定功 能的设备。这种a s i c 设计方案有效提高了网络设备的处理性能和速度，却降低了灵活性。 当今网络规模和性能迅速增长，新业务不断出现，要求网络设备具有线速和智能的处理能 力。网络处理器便是适应这种需要的一种新兴、有效的统一解决方案。网络处理器是新一 代用来执行网络数据处理和网络报文转发的高速可编程处理器。与传统的处理器不同，它 的设计采用了全新的理念，使其既有a s i c 的高速处理能力，又有完全可编程特性。由于 n p 在网络数据处理方面的优势，它成为高速网络设备支持业务管理、安全与网络监控、 o o s 等网络功能必不可少的设备器件。网络处理器代表了未来网络设备设计的发展方向。 当前较流行的网络处理器应用包括：多业务边缘运营商系统；语音网关系统( 口电话， 删自适应层) ；无线基础设施系统( 3 g 等) ；多协议城域系统( 因特网协议、点对点 协议、删，以太网、帧中继等) ；接入系统( 无线、有线，d s l 、公共交换电话网等) ； 协议测试和监控系统。从应用上来看，网络处理器正呈现出两极化发展趋势：向上抢占在 传统核心、边缘网络中的a s i c 市场；向下进攻嵌入式产品市场，如无线基础设备、p 服 务交换机、存储区域网和多路分插复用器等。从速度上来看，2 0 0 2 年主要应用集中在1 g b i 拈 以下的应用，而2 5 g 或1 0 g 以上的应用所占份额小于1 0 ，2 0 0 5 年后的主要增长将来自 1 0 g 以上的应用。 从1 9 9 9 年到现在，已有包括数家外国大公司相继推出了自己的网络处理器产品【”。其 中包括a m c c 【2 j 的n p 7 5 1 0 ( 1 0 g b i f s ) 、n p 3 7 0 0 ，i n t e l 【3 j 的i x p 4 x x x 系列、i p x l x x x 系列、 第】页 国防科学技术大学研究生院学位论文 i x p 2 x x x 系统，f n 的5 n p 4 g ( 基于i b m 的r a i n j e r 结构) 【4 】以及c p o r t ( m o t o r o l a ) f 5 】的c 一3 x 、 c 一5 x 等。目前，国内在这方面研究很少。在网络处理器技术的研究上，我们和国外还存在 很大的差距，这对我国构建具有自主版权的高性能网络设备十分不利。因此，对网络处理 器设计方法的研究具有重要意义。 1 1 2 网络处理器的设计方法与挑战 随着深亚微米工艺的迅速发展，芯片的集成度和操作频率越来越高，在单芯片上能够 集成多个微处理器核，并通过高效的内部互连网络将协处理器、硬件加速部件和外部接口 等异构资源相互连接构成异构多处理器片上系统( m p s o c ，m u l t i p r o c e s s o r s y s t e m o n c h i p ) 1 6 j 。m p s o c 结构结合了通用处理器与a s i c 的优点，能更好地兼顾性能 与灵活性需求。另外，用可编程逻辑取代片外设备可以减少设计代价、复杂性和功耗。因 此，网络处理器芯片广泛采用m p s o c 体系结构实现，例如h 】t c li x p 2 8 0 01 7 l ，e z c b i pn p 1 1 8 】 和m mp o w e r n p1 9 j 等。基于m p s o c 的网络处理器由一组运行时软件、异构硬件资源和互 连网络构成。运行时软件运行在各个处理单元( n o c c 站i n ge l e m e n t ，p e ) 中，主要由上层 网络协议应用软件( s o f t w 疵，s w ) 、实时操作系统( r e a l 佃eo p e i a t i i l gs y s t e m ，r t 0 s ) 构成。异构硬件资源包含多个p e 、协处理器( c o p r o c 鹤s o r c o p ) 、硬件逻辑块( h 越d w a r e l o 鹰i cb l o c k ，h u ；) 、存储资源( m c m o 珊m 锄) 等。 采用m p s o c 结构设计网络处理器时，设计者将面临新的挑战1 1 0 。由于在单个芯片上 集成多种异构处理资源，如多个通用r i s c 处理器，各种专用协处理器( c o p ) 和硬件加速器 等，传统的设计方法在设计的初始阶段就使用r t l 描述语言构建一个可执行模型的方 式不再可行。针对不同的网络应用，选择合适的处理资源构建网络处理器体系结构对于设 计者来说是件非常头痛的事情。每一类处理资源都有其自身的特点。使用r i s c 处理器能 较好的解决网络处理器的可编程问题，但砌s c 处理器对某些任务的执行速度慢且硬件实 现代价大。专用的协处理器依据某一算法或任务专门设计，能加速数据的处理且硬件实现 代价相对要小，但专用的协处理器缺乏可编程性。设计者需要在通用r i s c 处理器与专用 功能单元的使用上找到最佳结合点。另外，为了提高网络处理器的处理能力，当前的网络 处理器大多集成了协处理器来完成网络处理任务。常见的协处理器包括任务的排队和查 询、模式匹配、校验和c r c 计算、加密与解密等。而不同的网络应用对数据处理有特殊 要求，需要使用特定的专用协处理器或硬件加速。上述问题最终可归结为：如何根据网络 应用合理的选择各种异构处理资源，并将网络应用的各种任务分配到相应的处理资源上， 由此指导网络处理器的早期设计。 近年来，p a u l “e v e r s e 等人提出了y 一图设计方法1 。这种设计方法采用正交化思想， 分别独立描述应用空间和体系结构空间，然后将应用映射到理想的体系结构上最终形成整 个系统。y 图设计流程分为如下几个步骤： 1 设计者分别构建高层应用模型( 包含工作负载、计算和通信任务) 和底层体系结 第2 页 国防科学技术人学研究生院学位论文 构模型( 包含各种异构资源) ，建立多处理器片上系统平台。 2 根据系统平台所确定的设计空间，将应用功能映射到参数化的体系结构上。 3 从性能、面积、功耗等方面出发，在给定功能约束和性能约束条件下评价系统设 计和实施测试，获得性能结果。 4 如果性能结果不满足设计需求，则调整应用和工作负载描述、体系结构规范和资 源分配映射策略，重新丌始新一轮的映射过程，直到满足系统设计目标为止。 整个过程如图1 1 所示。 y - 图方法可以将应用空间和体系结构空间可以分别抽象到较高层次进行描述，从而提 高了系统设计的抽象层次和开发并行度，加速系统设计开发过程。 图1 1y 图设计方法 在用y 图方法设计网络处理器时面临四个问题“： 1 如何模型化网络应用： 2 如何模型化体系结构： 3 如何执行将网络应用映射到体系结构上的映射； 4 如何评价应用一体系结构映射。 其中，网络应用到n p 处理资源的映射是一个n p 一完全问题。b am a l l o y ，e lu o y d ， 觚dm ls o 曲等人在文献【1 3 】中指出：即使是只有两个n p 的情形下，根据计算和通信 代价调度任务的过程也是一个n p 完全问题。而当前映射的算法大多是针对特定硬件结构 下的启发式映射，通用性差。在这四个问题中，我们着重对如何执行将网络应用映射到体 系结构上的映射进行了研究，并提出了基于遗传算法的映射。遗传算法是一种宏观意义下 的仿生算法，它模仿的机制是一切生命与智能的产生与进化过程。它通过模拟达尔文“优 胜劣汰、适者生存”的原理激励产生好的结构，通过模仿孟德尔遗传变异理论在迭代过程 中保持已有的结构，同时寻找更好的结构。遗传算法给我们呈现出的是一种通用的算法框 架，该框架不依赖问题的种类。隐含的并行性和全局搜索特性是遗传算法的两大特征。基 于遗传算法的上述优点，我们采用该算法从系统平台所确定的设计空间中将网络应用优化 映射到参数化的n p 处理资源上。 第3 页 国防科学技术人学研究生院学位论文 1 1 3 课题研究内容 本课题针对采用m p s o c 结构的网络处理器的设计方法学进行研究。主要研究网络应用 到网络处理器的处理资源的映射方法，即针对给定的应用模型与参数化的异构资源模型， 研究如何自动选择异构并将网络应用分配到网络处理器的异构处理资源上，从而实现资源 的优化配置并使系统满足各项设计要求。研究内容主要是以下几个方面： 1 网络应用的形式化描述模型的选择。网络应用模型定义网络应用的行为功能、工作负 载及相应的输入激励。形式化的目的是为了对影响网络处理器性能的功能行为进行深 入研究，抽象出影响系统性能的数据模型和报文处理的功能模型。我们在这方面要做 的是从多种形式化描述方式中寻找一种适合于映射算法的网络应用描述方式。 2 异构资源的建模以及体系结构表示。体系结构模型可以侧重于硬件性能，也可侧重于 系统各种属性的分析( 功耗、存储器咀及面积等) 。 3 基于遗传算法的网络应用模型到异构资源模型映射方法。遗传算法给我们呈现出的是 一种通用的算法框架，该框架不依赖问题的种类。它具有隐含的并行性和全局搜索特 性两大特征。我们重点研究如何设计用于映射的遗传算法，研究内容包括问题空间解 的编码方法，遗传算子设计方法以及个体适应度的评价方法等。 4 研究利用s o p c 技术实现网络处理器原型。 1 2 相关研究 映射就是在早期设计阶段根据网络应用的特点，选择合适的报文处理资源，形成性能 和实现代价均可预测的网络处理器体系结构抽象模型，指导网络处理器的后续设计。映射 的目标是：在满足各种性能指标情况下，充分利用各种异构资源，减小网络处理器的硬件 实现代价。 目前国际上从事网络处理器设计方法学研究的主要机构有加州大学伯克利分校【1 4 】、 w 酤h i n 出o n 大学【1 5 1 、v 姐d e r b i l t 大学【1 6 1 、c a l 洳m i a 大学1 1 7 j 等，代表人物有m a n h i 勰g r i e s 【1 御、 p a t r i c kc r o w l e ，”】、髓l n l a l lw d f l 2 0 1 等。他们在网络处理器设计方法学研究中大多都涉及到 了网络应用到网络处理器资源映射问题，但没有对该问题进行深入系统的研究或未能给出 广泛适用的解决方案。 1 2 1 研究现状 加州大学洛山矶分校的g 0 k h a l lm e m i k 和w 讯i a mh m a i l g i o n e s m i l h 【提出了一种将 在网络处理器运行的应用高效结构化的n e p a l ( n e t w o r kp m c e s s o r a p p l i c a t i o nl a n g u a g e ) 框架【2 l 】。在n e p a l 框架中，每个应用被看作由一系列相关的模块组成。一个模块是数据 包上必须执行且清晰明确的任务。网络应用的模块可以根据网络应用的需求获取。模块被 动态的映射到执行核( e x e c u t i o nc o r e ) 上。n e p a l 框架包括两个独有的重要部件：全局的动 国防科学技术大学研究生院学位论文 态模块管理器( d m m ，d y n 锄i cm o d u l em a n a g e r ) 和局部管理器( l m ，l o c a lm a n a g c r ) 。d d m 负责控制模块活动，并将模块分配到执行核上。每个执行核实现一个局部管理器l m 。l m 负责对本地模块以及后继模块信息进行搜集和分类。在n e p a l 中有两种不同的启发式模 块分配方式。一种是考虑模块的执行时间，然后尽力维持执行核间的负载平衡。另一种是 考虑模块间的数据通信量，然后尽力将有大通信量的模块分到同一个核上。 在n e p a l 框架中，如果由于小数量的执行核或大量的并发应用，处理器不能有效利 用关于模块的信息，模块间的通信开销将降低系统性能。另外，为了以模块化方式执行应 用，一些硬件需要改进，可能会增加处理器面积，降低处理器性能。动态映射很难充分利 用每种异构资源的特性。 t i l m a i l w o l f ，r 锄a s w 锄y 等人在文献 2 2 】中提出了基于有向无环图( a d a g ，a n n o t a l e d d i r c d e da c y d i cg m p h ) 的应用到处理资源映射。该方法首先将应用描述成a d a g ，然后 采用启发式映射和调度算法，以最早任务完成时间为目标进行映射。a d a g 图到网络处理 器拓扑结构的映射是一个n p 完全问题。通常采用的算法是：随机映射算法( 瑚d o m j z e d m a p p i n g ) 【捌【2 4 】i 删。其核心思想是随机选择一个有效映射，评价其性能。通过多次重复该 过程，能够选择出所有循环中的最优解决方法，这是对全局最优化的一个近似优化方法。 我们将随机映射算法分成两个阶段：( 1 ) 映射：随机的将a d a g 结点( 一个处理任务) 分配给网络处理器拓扑中的一个空闲处理单元，如果映射违反了相关性约束，则重复映射 过程，直到找到一个合法映射为止，或者尝试一定的次数为止。重复该过程直到所有的结 点都分配到网络处理器拓扑中。重复a d a g 的映射过程直到网络处理器拓扑为满( 即没有 舢) a g 能够被正确加入) 。( 2 ) 过滤：确定了一个新的映射之后，对映射进行性能评价， 并比较出优化的映射方法。如果新的映射是目前最佳选择，则重新对映射进行排序，以便 评价将来的解决方法，如果该方法不是最优的则丢弃。在映射结束时，即选择出最佳映射 方法。 随机映射算法是一种盲目的算法。而且随着系统规模的增大，映射空间将迅速膨胀。 为了加速映射过程，可以采用启发式映射方法，如局部分配技巧( p a 卫p a n i a la s s i 乒m e n t t e c h n i q u e ) 1 2 6 j 。其思想是：每个系统都存在一些关键的约束条件，通过资源约束条件的分析， 逐步缩小分配( 映射) 的搜索空间，从而加速映射过程。 荷兰的d e l f t 、l e i 矗n 大学和n l p h i l i p s 研究中心联合开发的s p a d e 。( s y s t e ml e v e l p e r f o m a i l c ea n a l y s i s 柚dd c s i 朗s p a c ee x p l o r a t i o n ) 框架旧，如图1 2 所示。它实现了仃a d e 驱动、系统级应用和体系结构联合设计方法。应用模型产生的符号化指令t r a c e 由体系结构 模型解释，开发相应的定时特性。应用模型由i ( a h n 进程网络描。s p a d e 中从网络应用到处 理资源的映射使用如下两种手段：( 1 ) 每个进程都映射到一个t r a c e 驱动的执行单元f ) e u ) 上，如果映射关系是多对一的，则t d e u 需要对多个进程的t r a c e 进行调度。( 2 ) 每个进 程端口都一对一的映射到i o 端口上，这种映射也隐式的将通道映射到通信资源和存储资 源的组合结构中( 并且可能包含用户定义模块) ，例如专用总线模型、存储器接口等。通 常，这些资源在应用模型中没有对应的等价单元。一个较为特殊的情况是，如果单个进程 第5 页 国防科学技术大学研究生院学位论文 的功能需要分布到在多个处理资源上，则设计者首先应重写应用，使得该进程能够划分成 两个或者多个进程，从而这些进程可以映射到单个的t d e u 上。 1 2 2 当前研究工作的不足 图1 2s p a d e 框架的结构 网络应用到异构网络处理器资源映射的研究工作有以下的不足： 1 当前的研究大多集中在对设计空间中的某一点映射研究。其做法是先抽象出网络 应用模型，然后针对其中一种网络处理器结构，研究如何将网络应用模型映射到 该种结构的网络处理器资源上。当网络处理器可选的结构很多时，通过遍历整个 映射点的方式找出最佳的映射是不现实的。我们需要面向整个设计空间的映射方 法。 2 当前研究的映射算法大多是在随机映射算法基础上引入启发式映射方法，设计空 间搜索的并行性差，操作起来困难。 3 当前针对映射结果的评价研究不够深入，有些是针对硬件资源消耗进行评价，有 些是针对网络处理器的性能。未对硬件资源消耗、网络处理器的性能等方面进行 完善的综合评价并建立综合评价模型。 1 3 课题研究主要成果 本文从网络处理器设计方法学的角度，对采用m p s o c 结构的网络处理器的早期设计 阶段的设计方法，尤其是针对网络应用到异构网络处理器资源映射进行了研究，取得了以 下成果： 1 利用已有的网络应用和硬件资源模型化描述方法，选择合适的描述模型，对网络 应用和硬件资源进行建模； 2 建立了网络应用到异构网络处理器资源映射的综合评价模型，为映射提供了参考。 3 设计了用于网络应用模型到网络处理器处理资源映射的遗传算法，形成了完整的 第6 页 国防科学技术人学研究生院学位论文 网络处理器早期设计方法。 4 利用f p g a 实现网络处理器原型。 1 4 论文组织结构 第一章介绍了课题研究背景，研究内容，研究现状以及课题研究主要成果。 在第二章中，我们介绍了网络应用模型化描述方法、处理资源的参数化模型以及设计 评价方法。 第三章中我们首先对遗传算法的基本原理进行简单的介绍，然后详细介绍遗传算法的 构造过程，包括问题解的编码方式，遗传算子设计等，并对构造的算法进行分析，最后采 用该算法将网络应用映射到网络处理器资源。 第四章中介绍了s o p c 技术以及基于s o p c 的网络处理器原型设计与实现。 第五章总结全文。 第7 页 国防科学技术人学研究生院学位论文 第二章系统模型与设计评价 2 1 设计问题描述 我们在网络应用到网络处理器资源的映射过程中引入遗传算法。遗传算法包含5 个基 本组成部分t z 8 j ： 1 问题解的遗传表示； 2 创建解的初始种群的方法； 3 根据个体适应值对其进行优劣判定的评价函数； 4 用来改变复制过程中产生的子个体遗传组成的遗传算子； 5 遗传算法的参数值。 如何将问题的解编码成染色体以及如何建立个体优劣的评价模型及其数学描述形式 或量化方法是构建遗传算法时首先要解决的两个问题。 在网络处理器设计中，将问题的解编码成染色体的问题首先是网络处理器应用空间和 体系结构空间的表示问题。应用空间代表了网络处理器所实现的各种网络协议功能，例如 路由器中的刀酬v 6 报文转发，企业v p n 网络中的p s e c n 应用，网络服务器上的 w 曲6 州t c l l i n g 等。体系结构空间代表各种异构资源组成的体系结构。本文中首先将抽象的 网络应用和体系结构用具体的模型进行描述，然后采用合适的方式对模型进行编码。 如何建立个体优劣的评价模型及其数学描述形式或量化方法具体说就是网络处理器 性能评价方法问题。将网络应用映射到m p s o c 体系结构上形成多种候选设计方案，性能 评价就是对各种方案的评测过程。 本章将结合当前的研究成果以及构建映射算法的实际需要，对网络应用的模型化方 法，体系结构的建模方法，映射的评价方法进行介绍。 2 2 网络应用模型 网络应用决定了网络处理器功能模型，即网络设备必须具有那些基本的处理机制( 转 发，o o s 和安全机制等) ，而不同的处理机制对处理有不同的要求，例如，有状态的处理和 无状态的处理，优先级调度和f c f s 调度等。通过对网络应用进行深入分析，才能确定新 一代网络处理器需要实现的算法集合及相互间的依赖关系，才能结合具体的数据模型，分 析每种算法的操作( 如加减乘除、字符串比较、访存、共享资源的加锁解锁等) 序列，获 得路由器操作的种类、频度、i o 需求统计信息以及对共享资源的使用方法和特点，最大程 度提高对共享资源的利用率和处理的并行性挖掘。 这些性能特性包括：程序的数据和控制相关性、处理的并行性、程序执行的复杂度。 第8 页 国防科学技术大学研究生院学仿论文 工作负载分析和应用建模是网络处理器设计空间开发的一个重要环节，空间开发往往是从 分析应用程序开始的。 2 2 1 网络处理器工作负载 从网络处理器的角度来看，网络应用即为网络处理器的工作负载。网络处理器工作负 载是指在网络处理器中执行的网络应用功能集合。工作负载并不单单是网络处理器中运行 的软件程序，它是网络应用的整个功能行为，这些功能行为可能是硬件实现，也可能是软 件实现。例如，在，v 4 p a c k e t f o 刑a r d i n g 应用场景中，工作负载是指整个狂4 报文的转发 行为。 网络处理器工作负载分析是网络处理器体系结构设计和性能评价的基础。工作负载用 于评价预期的体系结构，从而更加有效的开发潜在的体系结构空间。设计过程需要针对多 种典型应用综合考虑系统的灵活性和专用性，力图做到既能够为用户提供最大的编程、开 发灵活性，又使得系统在具体应用中具有效能。 网络处理器工作负载来源于网络处理器的应用环境，网络处理器可用于多种应用场景 中，这些应用集中地体现在以下几个方面【冽： ( 1 1 基于网络处理器的智能路由交换设备。包括路由器体系结构的研究和功能模块的 构建比如础c a t e la d 缸柚t e1 c c i l n o 】o 直e s 使用m m 的p o w e r l 岬构建其核心路由及交换设 备。 ( 2 ) 智能安全设备的应用：防火墙、v p n 及入侵检测设各等。 f 3 ) 无线网络的应用：a dh o c 无线网络中的路由设备，3 g 协议栈的实现等。 ( 4 ) 系统的监测控制或模拟设备：一些研究机构将网络处理器作为其系统测试和实验 设备，比如e m p i 血使用m o t o r o l a 的c _ 5 作为其网络模拟器用于在线速下获得网络延时、 抖动、丢失率等参数。 在网络应用的模型描述中，根据网络处理器的实际应用环境选择相应的工作负载进行 描述。 2 0 2 网络应用的描述模型介绍 应用程序模型定义应用的功能、工作负载及相应的激励输入。应用程序模型与应用领 域密切相关，不同的应用领域需要选择合适的抽象模型表示。应用程序建模多使用计算模 型( m o d e l so f c o m p u t a l i o n ，m o c ) 【3 0 l 描述，根据抽象层次可将应用模型的计算模型分为如 下几种： 形式化模型：有限状态机( f i n i t e s t a t em a c h i n e s ，f s m ) 擅长描述控制结构，但缺乏时间 特性，不擅长于描述数据流结构，因此这种结构常常与其他一些不适合于描述控制逻辑的 m o c 模型相结合共同描述应用功能。f s m 模型的扩展模型有c f s m 、e f s m 和h f s m 。 p e 啊网描述复杂数据流和控制流共存的系统。勋h n 进程网络( k a h np r o c e s sn e t w o r k s ，k p n ) 第9 页 国防科学技术大学研究生院+ 学位论文 模型由一组进程和f i f o 结构的通信通道构成，适用于描述多状态的同步系统。c s p c c s 使用顺序、选择和并行三种算子定义进程，进程间使用同步消息传递的方法通信，并将系 统间的通信通道描述为一个进程，适用于描述资源共享问题，使用并发编程语言【d f o s 。 i ( i ，n 和c s p c c s 模型的共同弱点是不适合于描述控制逻辑。 数据流模型：同步数据流( s y n c h r o n o u sd a t a n o w ，s d f ) 主要描述具有规整的计算特 征的数据流，例如流媒体信息处理、网络报文流处理等。s d f 模型的死锁和有性是可判定 的，因此特别适合于描述嵌入式实时软件和硬件行为功能。数据流模型的主要弱点是不适 合于描述控制结构。控制数据流图( c c m 仃o ld a t af l a wg r a p h ，c d f g ) 能够从程序描述的源代 码中阐述，它表示了运行时所经历的所有控制流结构。c d f g 中的数据流部分表示了应用 程序本身的并发性，控制流部分确定了数据流的同步点和运行时的动态决策点。 肘间流模型：离散时间( d i s c r e t c 面m e ，f d 是s d f 模型的一种扩展模型，在同步数据 流中引入了时间概念。连续时间( c o n t i n u o u s 豇m e ，c i ) 包含代数，差分方程求解器，因此适 合于描述带有线性或非线性代数，差分方程的物理系统。例如信号处理系统，机械系统等。 采用的工具主要有m i ，a m s 、s p i i ：c 电路模拟器等。 事件流模型：离散事件( d i s c 聆t e e v 坞d e ) 描述数字系统和电信系统，并且最擅长 描述并发硬件系统。使用高级语言( 如a c + + ) 或者系统描述语言( 如v h d l ，v c r i l o g ) 构 建d e 模拟器的方法描述模型。分布离散事件( d i s | r i b u t ed i s c r c t e e v e n t s ，d d e ) 模型与 d e 模型的本质区别是模型没有集中控制点。d e 中每个事件都精确位于全局连续时间轴上， 而d d e 中每个事件域维持本地时间轴。d d e 较适合于描述全局异步局部同步( g a l s ) 的 复杂数字系统。 可执行模型：可执行模型通常使用高级编程语言( c c + + 、j a v a ) 构建可执行的应用 程序代码。例如用于网络处理器的a i c k 、n p c l i c k 。 许多应用模型都可借助于有向无环图( 】d i r e c t e da c y c l j cg r a p h ，d a g ) 表示。可表示各种 粒度的应用，如逻辑操作级、任务级、计算和通信任务、任务级的网络流量的报文处理应 用。 由于每一种描述模型都有其优缺点，不同的应用领域需要选择合适的抽象模型表示。 一般情况下是在现有的模型基础上进行适当的假定或功能强化。在下节中我们将使用数据 流进程网络的一种演化模型来描述网络应用。 2 2 3 网络应用的w d p n 模型提取 数据流进程网络( d a t a n a wp r o c e s sn c 咐o r k ，d p n ) f 3 1 】是一种重要的数据流工作负载 的形式化模型，广泛用于数字信号处理、流媒体处理和网络通信等领域。在d p n 中应用程 序描述为一个有向图，结点表示计算单元，弧表示具有半序关系的事件流。d p n 是 k p n ( k a h np r o c e s sn e t w o r k ) | 3 2 1 的一种特例，进程之间的通信采用无限容量的f i f o 通道，从 而能够描述流处理应用。进程包含输入和输出接口、一组功能函数及相关的激活规则和一 第1 0 页 国防科学技术人学研究生院学位论文 个控制器。内部控制器使用激活规则和f i f o 通道上的阻塞读机制控制多个功能函数的执行 顺序，具有很好的并发执行特性。函数的一次执行是功能性的，即输入到输出的映