（计算机科学与技术专业论文）多pe网络处理器体系结构及实现技术研究.pdf

里堕型兰垫查查兰竺窒圭堕兰垡笙苎 摘要 网络处理器是路由器中进行报文转发处理的关键设备。由于报文处理具有内在的并 行性，网络处理器采用了多种并行技术来加速报文的处理。本文对网络处理器的并行体 系结构进行了深入研究，将网络处理器采用的并行技术分成三个层次上的并行，分别是 p e ( p r o c e s s i n ge l e m e n t ，处理单元) 内部的并行，p e 问的并行，p e 与协处理器之间的并行。 在对网络处理器并行技术的分析基础上，本文提出了y h n p 网络处理器的体系结构， 对主要的数据通路和功能部件进行了详细设计，用v e f i l o g 硬件描述语言进行了描述，并 在m o d e l s i m 5 5 下运行通过。 然后本文对y h n p 网络处理器设计中的几个关键问题进行了讨论，主要是p e 的调 度和报文分派策略的问题。采用的研究方法是首先对报文处理模型进行抽象，提出了一 个具有一般意义的报文处理时间模型，并用c + + 语言实现了一个模拟器。然后分别采用 了数学分析和程序模拟的方法来对p e 的调度和报文分派策略的问题进行研究，阐明了 p e 调度的原理和实现方法以及一种简单有效的报文分派策略。 关键词：网络处理器，报文并行处理，多线程，报文分派 国防科学技术大学研究生院学位论文 a b s t r a c t n e t w o r kp r o c e s s o r sa r et h ek e yd e v i c e st od op a c k e t sf o r w a r d i n gi nt h er o u t e r s a st h e r ei s i n h e r e n t p a r a l l e l i s m i nt h e p a c k e t sp r o c e s s i n g ，n e t w o r kp r o c e s s o r sa d o p tm a n yp a r a l l e l t e c h n o l o g i e st oa c c e l e r a t et h ep r o c e s s i n go ft h ep a c k e t s t h ep a r a l l e l a r c h i t e c t u r e so ft h e n e t w o r kp r o c e s s o r sa r ee x p l o r e di nt h i sa r t i c l ea n dt h ep a r a l l e lt e c h n o l o g i e sa d o p t e db yt h e n e t w o r kp r o c e s s o r sa r cd i v i d e di n t ot h r e e a s p e c t s t h e y a r e t h e p a r a l l e l i s m i n s i d et h e p e s ( p r o c e s s i n ge l e m e n t ) ，t h ep a r a l l e l i s mb e t w e e nt h ep e sa n dt h ep a r a l l e l i s mb e t w e e np e s a n dc o p r o c e s s o r s t h ef e a t u r e so fn e t w o r kp r o c e s s i n gd e c i d et h a tt h ep a r a l l e l i s mi n s i d et h e p e si sn o tt h em a i nd i r e c t i o no f d e v e l o p m e n t s o t h ee m p h a s e sa r ep u to nt h ek e y t e c h n o l o g i e s o f t h el a s tt w o p a r a l l e l i s mm e t h o d s b a s e do nt h ea n a l y s i so ft h ep a r a l l e lt e c h n o l o g i e sa d o p t e db yt h en e t w o r kp r o c e s s o r s ，ay h n p n e t w o r k p r o c e s s o ra n d i t sa r c h i t e c t u r ea r ep r e s e n t e d t h em a i nd a t a p a t h sa n df u n c t i o n a lu n i t s a r e d e s i g n e d i nd e t a i l a l lo ft h e ma r ed e s c r i b e dw i t hv e r i l o gl a n g u a g ea n dp a s s e di n m o d e l s i m 5 5 t h e ns e v e r a lk e yp r o b l e m si nt h ed e s i g no f n pn e t w o r kp r o c e s s o ra r ed i s c u s s e d t h e s e p r o b l e m sm a i n l y i n c l u d et h e s c h e d u l i n go fp e sa n dt h ep a c k e t sd i s p a t c h i n gs t r a t e g i e s a b s t r a c ti sm a d et ot h ep a c k e t sp r o c e s s i n gm o d e la n dag e n e r i ct i m i n gm o d e lo fp a c k e t s p r o c e s s i n g i s p r e s e n t e d as i m u l a t o ro fs u c hat i m i n gm o d e li si m p l e m e n t e dw i t l l c + + l a n g u a g e w i t hb o t hm a t h e m a t i ca n a l y s i sa n dp r o g r a m ss i m u l a t i o na r eu s e dt os t u d yt h ek e y p r o b l e m sm e n t i o n e da b o v e t h ep r i n c i p l ea n di m p l e m e n tm e t h o d so f p es c h e d u l i n ga n da e f f e c t i v ea n d s i m p l es t r a t e g yo f p a c k e t sd i s p a t e h i r i gi sa c h i e v e d k e y w o r d s ：n e t w o r kp r o c e s s o r ，p a c k e t sp a r a l l e lp r o c e s s i n g ，m u l t i t h r e a d s ，t h r e a d ss c h e d u l i n g ， p a c k e t sd i s p a t h i n g i i 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一n ：r - 作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目： 垒望圆鳌烛堡墨篮丞垄拉丞塞塑拉苤煎蕉 学位论文作者签名： 蠲颦 日期：2 口0 2 年1 1 月2 口日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 垒望圆签丛堡墨焦丕缱尥丞塞垫拉盔盈窥 学位论文作者签名：型室 作者指导教师签名 日期：2 0 0 1 年f f 月z 日 日期：j 岁7 年，月；日 里堕型堂垫查奎堂竺窒竺堕兰竺笙苎 第一章绪论 1 1 课题背景 近年来，n t e m e t 的发展十分迅猛，新的业务层出不穷，这种发展形势对路由器的报 文处理能力提出了新的要求，传统的a s i c 芯片和通用微处理器相结合的处理方式暴露 出种种弊端，一种新的处理方式一使用网络处理器进行报文处理一应运而生。网络处理 器已经成为路由器设计中的关键部件，它的性能对整个路由器的性能有很大的影响。目 前，网络处理器产品的市场均由国外产品所占领，国内在这方面几乎是空白。方面， 这说明在网络先进技术上我们和国外还存在很大的差距；另一方面，这种格局对于我们构 建具有自主版权的高性能网络路由器十分不利。因此，网络处理器关键技术的研究具有 重要意义。 1 1 1 路由器的发展简述 网络处理器的出现和路由器的发展是密不可分的。最早的路由器在8 0 年代问世之初， 只有一个通用微处理器，它既负责完成报文转发的实时业务，也负责路由计算、路由表 建立和修改维护、网络管理等系统功能，并且这些功能全部由软件来实现。但是随着 i n t e m e t 规模的不断扩大，由于通用微处理器的处理能力和软件结构的限制，这种传统的 路由器已经发展到了极限。它的报文转发速率不足1 m p p s ；另外时延较大，也不能保证 实时业务传送中的服务质量【l 】。 为了解决早期路由器的速度问题，人们对其结构进行了改变。路由计算、管理控制 等非实时业务和报文转发的实时业务被分开，前者由通用微处理器完成，而后者则由专 用的报文转发和交换硬件来完成。路由器由输入、输出模块和交换开关三部分组成。输 入模块负责报文的接收和转发处理，报文经过交换开关进入输出模块以决定报文的流向。 其中，通过报文转发硬件的数据流量占整个系统的9 9 以上，因而报文转发硬件是系统 的性能瓶颈，为了达到较高的转发速度，一般采用专用集成电路芯片( a s i c ) 来实现。这 种路由器用硬件实现逐个的报文转发处理，报文在数据通路上线速交换，因此也称为线 速路由交换机。采用a s i c 芯片实现报文转发硬件的思想成为设计的主流，并一直持续 到最近几年吐 随着i n t e r n e t 的迅速发展，新的协议和新的应用不断出现，对路由器设计有了新的要 求。例如，新的多媒体网络应用的出现以及不断增加的i n t e m e t 网络用户、主机和域， 人们对i n t e m e t 网络提出了更高的服务要求：增加网络通信带宽和速度、支持多媒体话 音和图像的传送、保证网络的可靠性和安全性等等。这要求传统的路由器必须具有一定 的灵活性，以保证对新的业务的支持能力，甚至要“预见”今后一两年内可能出现的业 务，为之保留扩展能力。在这样的情况下，采用a s i c 芯片实现报文转发硬件的弊端逐 渐显露出来。首先，由于网络协议和应用的复杂化以及对网络设备的智能要求的提高， 使得a s i c 设计变得复杂，庞大，导致研发的风险加大，成本增高，研发周期延长；第 二，研发周期延长导致上市时间延迟加大，而新的应用出现的速度越来越快，使得新的 基于a s i c 芯片的路由器产品的发布可能总是赶不上新的需求；第三，对于用户而言， 一旦选择了基于a s l c 芯片的路由器，面对新的业务的增长，将无法及时的更新服务以 适应新的情况，更换设备的成本较大；第四，a s i c 芯片的设计受制于集成电路的制造 第1 页 国防科学技术大学研究生院学位论文 工艺，而目前集成电路的制造工艺已经接近硅半导体的物理极限，要想进一步提高集成 度十分困难。因此，采用a s i c 芯片构建路由器的设计思想陷入困境。而网络处理器的 出现则改变了这种状况。网络处理器是一个“专用指令处理器”( a p p l i c a t i o ns p e c i f i c i n s t r u c t i o np r o c e s s o la s i p ) i ”，它有自己的指令集，路由器设计者和最终用户可以根据应 用的特点，通过软件开发平台编写出专门的处理程序在网络处理器上运行，从而获得较 好的性价比；同时，一旦应用发生改变，也可以通过迅速更新软件来适应应用的变化， 而不需要更新硬件设备。因此，具有灵活性的网络处理器取代限制较大的a s i c 芯片， 成为路由器报文转发的核心设备。 1 1 2 报文处理的并行性 在当前的网络环境下，单个处理器一般很难满足报文处理的要求，链路带宽和处理 器的处理速度之间的差距越来越大，即使处理器的性能在不断提高，报文到达的速度比 单个处理器的处理速度还是快很多。然而，由于报文之间的相关性比较小，尤其是报文 流与报文流之间，几乎没有任何相关，因此，报文处理可以很容易的分布到多个处理器 上进行。也就是说，对不同报文的处理存在内在的并行性。同时，一些在传统的计算机 上进行并行处理经常遇到的问题，比如复杂的同步机制和处理器之间的通信等等，在报 文并行处理上要简单得多。所以，网络处理器很自然的采用了并行处理的结构。当前已 经面世的商用网络处理器都包含多个处理单元【3 j 【“。 1 2 课题研究内容及主要工作 根据报文之间的处理相关性小的特点，网络处理器设置了多个p e ( p r o c e s s i n g e l e m e n t ，处理单元) ，每个p e 独立的处理一个报文，这样同时可以处理多个报文。报文 处理过程中，有一些公共的操作，比如查找转发表等，需要访问共享资源，网络处理器 一般使用一个协处理器来完成这类对共享资源的访问。为了隐藏访问共享资源的延迟， p e 上可以同时运行多个线程，当一个线程在访问共享资源时，可以将这个线程切换出去， 调入一个准备好的线程运行，从而提高了p e 与协处理器之间的并行性。 本课题主要研究具有多p e 多线程特征的网络处理器的体系结构及其实现技术。本文 提出了y h n p 网络处理器的体系结构，y h n p 网络处理器具有多个并行配置的p e ，每 个p e 上可以运行多个线程；还有一个共享的搜索引擎，做为查找转发表的协处理器。 本文对y h n p 网络处理器的报文存储和控制、分派调度等部分进行了设计和模拟实现， 并对设计中的关键问题进行了研究。这些关键问题主要是p e 的调度问题和报文的分派 策略的选择，而p e 调度问题的实质是p e 数目和线程数目与系统性能之间的关系的问题。 本文提出了一个报文处理的时间模型，基于这个时间模型对以上问题进行了探讨，其结 果对y h n p 网络处理器的设计提供了有力的支持。 第2 页 里堕型兰垫查查兰堕窒生堕兰些丝苎 1 3 课题研究成果 在本课题的研究中主要取得了如下成果： - 提出了y h n p 网络处理器的体系结构并对主要功能部件进行了模拟实现； - 建立了一个网络处理器报文并行处理的时间模型； - 对y h n p 网络处理器设计中的关键问题进行了研究，阐明了p e 调度的原理及实现 方法，得到了一个简单有效的报文分派策略。 1 4 论文的组织 本文各个章节的组织如下： 第一章介绍课题背景、课题内容以及论文的组织结构。 第二章介绍网络处理器的并行体系结构。包括网络处理器的组成和所采用的并行技 术分类。 第三章提出y h n p 网络处理器的体系结构及主要功能部件的实现。 第四章对y h n p 网络处理器设计中的几个关键问题进行了研究。 第五章展望了课题的下一步工作。 最后是结束语和致谢。 第3 页 国防科学技术大学研究生院学位论文 第二章网络处理器并行体系结构 2 1 网络处理器在路由器中的地位 根据网络处理论坛n p f 5 1 对网络处理器软硬件接口的划分，网络处理器在路由器中 的地位如图2 - 1 所示。2 - l ( a ) 表示在路由器硬件层次中网络处理器的地位，网络处理器和 物理层芯片构成路由器的输入输出模块，负责报文的接收和转发处理。c s i x l 1 与 c s i x l 2 分别是网络处理器与交换开关、网络处理器之间的接口规范，由n p f 制订。2 1 ( b ) 表示在路由器软件层次中网络处理器的地位。网络处理器上运行的主要是第三层( 口) 和 第四层的转发微码，完成第三层和第四层协议中报文转发部分的功能，而协议栈中较复 杂的路由协议和管理协议则由通用微处理器完成。通用微处理器与网络处理器之间通过 n p f 制订的c p l x 接口规范进行通信。需要注意的是，2 - 1 ( b ) 所表示的软件层次是n p f 所推荐的方式，实际上网络处理器的功能可以不只包含报文转发的功能，还包含控制管 理的功能。网络处理器的功能可以划分为两个平面，一个是数据平面，完成报文转发的 功能，特点是对速度的要求较高，数据并行性大，计算量小；另一个是控制管理平面， 完成除报文转发以3 1 - 的控制管理功能，特点是计算量大，数据并行性小，对速度的要求 较低。 l i交换开关子系统 【鬻 i 匝弦巨霉矧刖 h 隐陌森司 ( a ) ( b ) 图2 1 网络处理器在路由器中的地位 2 2 网络处理器的组成 网络处理器具有一个单芯片多处理器多线程的体系结构，其核心部分是多个处理单 元( p r o c e s s i n ge l e m e n t ，简称p e ) ，每个p e 都是一个简单的微处理器，可以同时运行多 个线程，每个线程对应处理一条报文。网络处理器的核心思想就是利用前后报文相关性 小的特点，充分开发报文处理的并行性，从而提高报文处理速度。 一个典型的网络处理器的结构如图2 2 所示。 第4 页 国防科学技术大学研究生院学位论文 2 2 1 物理接口子系统与交换开关接口子系统 物理接口子系统与物理层芯片相连，负责接收来自物理层的位流，形成报文并存放 到报文缓冲里。目前支持的接口主要有o c 一1 9 2 ( s p l 4 2 ) ，o c 一4 8 ，o c - 1 2 ，千兆百兆以太 网端口等等。交换开关接口子系统提供到交换开关的接口，另外还包括交换开关的输入 输出报文队列的维护和交换信元的切分及重组。 外部 2 2 2 存储与缓冲子系统 图2 - 2 网络处理器的组成 存储与缓冲子系统包括网络处理器内部的存储器及报文缓冲和到外部存储系统的接 口。存储器带宽是网络处理器性能瓶颈之一。这是因为，按照存储转发的思想，所有报 文进入网络处理器之后必须缓存，如果要求线速处理报文，即报文输出的速度与输入的 速度匹配，那么存储器带宽至少应该是端口速率的2 倍( 同时考虑输入和输出) ，而要取 得较好的性能，就要达到3 - 4 倍【9 】。也就是说，如果端口速率为2 5 g b p s ( o c 一4 8 ) ，那么 存储器带宽就要到达8 - 1 0 g b p s 。这对于目前的存储器而言是一个巨大的挑战。 2 2 3 p e 子系统 p e 是网络处理器的核心部件，它实际上是一个功能比较简单的微处理器核，主要完 成报文转发和协议处理的工作。大多数网络处理器的p e 都支持多线程，由硬件保证线 程之间的切换开销接近0 。根据p e 所采用的体系结构的不同，可以划分为两类： 1 1 基于r i s c 的体系结构。其特点是直接将多个现成的r i s c 微处理器核集成到一个 芯片中。r i s c 技术成熟，现成的核比较多，软件开发环境也比较容易构造，开发的程序 也具有一定的通用性。缺点就是程序效率不高，另外在一个芯片上集成的数目有限。这 样的例子有i n t e li x p l 2 0 0 1 3 i 。 2 1 针对网络应用进行了优化的体系结构，主要是指令集优化。由于进行了优化，使 第5 页 国防科学技术大学研究生院学位论文 得p e 更加适合进行报文转发处理，从而提高处理速度，有资料显示其性能比基于r i s c 的p e 高1 0 倍以上| 7j 。但是专门的指令集需要专门的编译和优化程序的支持，程序没有 通用性，并且硬件开发的成本比前者高。这样的例子有m m c 的n p 系列网络处理器，采 用了所谓n i s c m e t w o r k n s t r u c t i o ns e tc o m p u t i n g ) 的体系结构1 6 j 。 另外，根据p e 的功能划分和组织结构的不同，可以分为并行和串行两种方式，如图 2 3 所示。前者的多个p e 以并行的方式工作，每个p e 完成同样的工作，都要完成一个 报文的完整的处理流程；后者将一个报文的处理流程划分为许多段，每个p e 完成其中 一段的操作，以流水的方式工作。还有些网络处理器的p e 可以动态配置成并行或者串 行的方式工作8 1 。 2 2 4 通用微处理器 图2 - 3 并行方式与串行方式 通用微处理器主要完成的功能包括启动初始化，代码加载，与主控通信，控制管理 功能和一些高层协议的处理。简单的说，与报文转发关系不大的“杂活”都交给通用微 处理器去做。这体现出网络处理器对功能划分的一种思想：控制管理层面上的功能交给 通用微处理器去完成，数据转发层面上的功能交给p e 去完成。对于没有通用微处理器 的网络处理器，这些功能由外部主控完成，或者由专门的协处理器来完成。 2 2 5 协处理器子系统 协处理器是一种硬件加速单元，由硬件完成某些特别的任务，提高处理速度。协处 理器完成的任务一般是关键路径上比较固定的、适合用硬件来实现的任务，比如分类， c r c 校验，匹配，查表，存储器访问，数据复制，缓冲和队列管理，策略控制等等1 0 】。 协处理器分为两种，种是异步协处理器，一旦p e 向异步协处理器提出请求，就可 以接着往下进行处理；另一种是同步协处理器，p e 向同步协处理器提出请求后，必须等 待结果的返回。 第6 页 国防科学技术大学研究生院学位论文 协处理器可以是一个简单的硬件单元，也可以是一个可编程的微处理器；可以集成 在网络处理器内部，也可能放到片外作为一个单独的部件。片内的协处理器自身不对指 令进行译码，p e 采用专用的协处理器指令负责触发并控制协处理器的执行。p e 与协处 理器相结合的方式达到了灵活性和高性能的要求：通过p e 来实现可编程性和灵活性， 而由协处理器来保证速度和性能。 2 3 1 并行技术分类 2 3 网络处理器中的并行技术 为了最大限度提高报文处理速度，网络处理器采用了多种并行技术。按照并行的粒 度和层次的不同，可以归纳为如图2 - 4 所示的层次结构。 广指令级并行 j ，p e 内部并行1 il 线程级并行 f 器鬻柔l 邮并行丁黼 il 串行配置p e i 广线程切换 l p e 与协处一 理器的并行l异步协处 理器指令 2 3 2 p e 内部的并行 图2 4 网络处理器采用的并行技术 p e 内部的并行包括指令级并行和线程级并行。指令级并行属于传统的体系结构技术范 畴，因此凡是在通用微处理器上能提高指令级并行的技术都可以用于p e ，比如超标量，超 流水，超长指令字( v l i w ) ，t r a c ec a c h e 等等。例直l c i s c o 的p x f 处理器采用v l l w 结构，每 个节拍可执行两条指令，通过使用先进的编译技术可获得线程内的指令级并行【1 1 。而 c l e a r w a t e r 的网络处理器采用多发射的超标量结构，可在运行时自动获得指令级并行而不需 编译器的支持。 线程级并行的获得主要通过同时多线程( s m t ) 技术。采用这项技术的有x s t r e a ml o g i c 公司的网络处理器”“，它在一个周期内可以同时执行8 个线程的指令。但是，从另一个角 度看，p e 内部的线程级并行并没有太大好处，因为在p e 之间，线程级并行是一件很自然的 事情，完全可以把一个复杂的支持同时多线程的p e 分解成多个简单的只支持单线程的p e 。 这里有必要解释一下p e 支持的多线程与同时多线程的区别。同时多线程是指在同一时 第7 页 国防科学技术大学研究生院学位论文 刻p e 内部有多个线程处于执行的状态，基于前面提到的原因，多数网络处理器在p e 内部并 不采用同时多线程，只是给每个线程提供一组独立的上下文寄存器和存储空间，而计算资 源只有一个，对于各个线程而言是分时共享的。当一个线程处于执行状态时，其它线程就 不能处于执行状态，换句话说，同一时刻p e 内部只有一个线程处于执行状态。i 因此，多线 程并不能加快单个报文的处理速度，它的作用主要是隐藏延迟。我们把p e 内部线程的切换 放入p e 与协处理器并行的范畴，这一问题我们将在下文中讨论。 p e 内部采用指令级并行还会带来线程切换开销增大的问题。比如，如果一个p e 的执行 内核具有5 级流水线深度，那么在进行线程切换时，保存流水线各段的状态的开销将远远 大于一个结构简单的p e 。 2 3 3 p e 间的并行 p e 之间的并行是网络处理器内部的主要并行方式之一。前面已经提到，p e 有两种 配置方式：并行和串行。并行配置的p e 采用的是资源重复的并行思想，串行配置的p e 采用的是时间重叠的并行思想。每一种配置方式都有两种实现方法：专用任务处理单元 和基于r i s c 的处理单元。图2 5 揭示了它们之间的关系【8 1 。表2 - i 将并行与串行方式作 每个单元都是专用任务单元 每个处理单元完成专门的任务 - 每个报文顺序通过每个单元 ( i ) 专用任务单元的串行配置 - 每个单元都是r i s c 芯片 每个处理单元完成专门的任务 一 每个报文顺序通过每个单元 ( b ) 基于r i s c 单元的串行配置 - 每个单元都是专用任务单元 每个单元都是r i s c 芯片 - 每个处理单元完成专门的任务 - 每个处理单元处理一个报文 - 每个报文被分成n 个部分同时处理 ( c ) 专用任务单元的并行配置( d ) 基于r i s c 单元的并行配置 图2 - 5 不同处理单元的不同配置 了比较，表2 - 2 将专用任务处理单元和基于r i s c 的处理单元作了比较。 图2 - 5 ( c ) 是将专用任务处理单元和并行配置方式相结合的并行处理模型，一个报文被 分成可以并行处理的n 个部分，每一部分由一个专用的p e 来处理，从而能使处理速度 第8 页 国防科学技术大学研究生院学位论文 提高n 倍。然而几乎没有一个网络处理器采用这样的结构，因为报文内部的并行性很有 限，一些主要的操作，比如提取m 地址，查找下一跳口地址，修改报文头等必须顺序 执行。因此，目前网络处理器广泛采用的是其它三种方式，它们的共同特点是开发报文 处理之间的并行性。 另外，采用并行p e 配置的网络处理器，在某些新的网络应用( 如i l a s e c ) 的处理上 还存在问题。这些应用对每个报文的处理是与其本身的序列号相关的，并且需要修改某 些网络处理器本地的控制数据。这就要求必须串行处理属于同一个会话的报文。而目前 多数网络处理器采用的并行p e 配置无法满足这一要求。 表2 - 1 并行与串行方式的比较 并行方式串行方式 并行思想资源重复时间重叠 p e 工作每个p e 功能相同，完成整个报多个简单的p e ，每个完成从一个 方式文的处理复杂功能中分解出的简单任务 采用多线程，利用线程切换隐藏 多线程一般不采用多线程 延时 存储系统层次型的共享存储器每个处理单元有自己的存储器 负载不易平衡，处理的速率取决 负载平衡负载容易平衡 于处理速度最慢的一个阶段 可以对报文处理的全过程进行 优化难易优化，而针对某些处理的优化比 可针对某些处理专门对p e 进行 较困难 优化 灵活性具有更多的可编程性与灵活性灵活性较低 没有特殊限制，但是处理某些必 适用场合适合处理任务明确的串型数据流 须串行处理的任务时效率较低 表2 2 专用任务处理单元与基于r i s c 的处理单元的比较 专用任务处理单元基于r i s c 的处理单元 p e一般是自定逻辑，完成特定任务与通用微处理器类似 指令集每个处理单元的指令集不同每个处理单元的指令集相同 编译及代码容易生成高效的代码，并且代码对编译要求高，且生成的代码 量较小较大，需要更多的指令存储器 软件开发每个处理单元需要单独的开发环开发环境单一 环境境，单独的编译器 灵活性较小较大 可以针对特定的任务，对体系结一般只对指令集进行优化 优化 构及指令集进行优化 并行模型适用于分时共享或时间重叠适用于资源重复 适用场合适合于统一，明确的任务没有特殊限制 2 3 4p e 与协处理器之间的并行 采用并行配置方式的p e ，一般需要多个协处理器来辅助处理报文。前面已经提到 协处理器的执行有同步和异步两种方式。在同步方式下p e 和协处理器是串行工作的， 第9 页 国防科学技术大学研究生院学位论文 即只有从协处理器得到执行结果，p e 才执行下一条指令。对于异步方式，p e 不必等待 协处理器的结果就可执行下一条指令，这时p e 和协处理器是并行执行的。 因此，p e 与协处理器之间的并行也有两种方式。一种是p e 与异步协处理器之间的 并行，p e 与协处理器同时处理同一个报文的不同部分，这种并行是同一条控制流内部的 并行。有些网络处理器设置有校验和( c h e c k s u m ) 协处理器，就属于这样的例子1 4 j 。一旦 p e 发出请求，在校验和协处理器处理的同时，p e 可以做提取m 的工作。 另一种方式是p e 与同步协处理器之间的并行。因为访问同步协处理器需要等待返回结 果，因此可在一个p e 上同时执行多个线程，一旦p e 执行了同步协处理器指令，而协处理器 又不能立刻返回结果时，p e 立刻进行一次线程的切换，由另一个就绪的线程开始执行。目 前几乎所有的网络处理器都采用线程切换方式来提高p e 和协处理器间处理的并行性。显 然，这种并行是不同控制流之间的并行，在同一时刻，p e 与协处理器处理的是不同报文的 不同阶段的任务。 p e 内的线程一般是一段处理某种类型报文的程序，p e 为每个线程固定分配一组寄存器 和固定大小存储器空间，因此切换时不需要保存现场，达到所n o 开销切换。p e 能够提供 的寄存器数目和存储器空间决定了p e 最多能支持的线程的数目。i b mn p 4 g s 3 中每个p e 最 多支持两个线程，它为每个线程提供8 个3 2 位的指令栈，1 6 个3 2 位的通用寄存器，大小为 1 k b 的私有存储空间，其它资源都是共享的【4 j 。 利用多线程隐藏访问延迟在m p p 中得到广泛应用，因此可以借鉴m p p 的思想来实现网 络处理器的多线程机制。 表2 3 比较了当前流行的网络处理器采用的并行技术。其中p e 和协处理器间并行度 用每个p e 上可同时执行的线程个数来衡量，加号表示还有异步协处理器。由表中数据 可知，当前网络处理器采用的并行技术主要是p e 闯的并行和p e 和协处理器之间的并行。 而网络处理本身的特点决定了p e 内部指令级并行不是技术发展的主要方向。 表2 - 3 当前网络处理器采用的并行技术【l 】【3 】 4 1 1 6 7 】【3 8 】 公司 i n t e li mm o t o r o l at e s s ec i s c om m c e z e h i p d ( p 1 2 0n p 7 1 2 产品4 g s 3c 5i q 2 0 0 0 p ) ( fn p 一1 0 o p e 间并行度 61 61 643 224 指令级并行 度 l1112 11 p e 和协处理 器间并行度 42 +45不详 8不详 p e 类型通用通用通用通用专用通用专用 p e 配置方式并行并行并串行并行串行并行串行 此外，目前网络处理器的p e 配置方式以并行方式居多，所以本课题主要研究具有并 行结构的p e 之间的并行技术以及p e 与协处理器之间的并行技术。以后本文所提到的网 络处理器模型，除非特别声明，均指并行配置p e 的网络处理器。 第1 0 页 里堕型兰垫查奎堂竺壅生堕兰笪笙奎 2 4 本章小结 本章首先介绍了网络处理在路由器中的位置和网络处理器的组成，然后重点分析总 结了网络处理器所采用的并行技术。网络处理器采用的并行技术可以分为p e 内部的并 行，p e 之间的并行和p e 与协处理器之间的并行。对报文并行处理具有重要意义的是p e 之间的并行和p e 与协处理器的并行技术，这也是本课题所关注的重点。 第1 1 页 国防科学技术大学研究生院学位论文 第三章y h n p 网络处理器体系结构及实现 y h n p ( y i n h en e t w o r kp r o c e s s o r ) 网络处理器是我们在研制和实现银河玉衡核心路 由器报文转发部件的基础上提出的一个网络处理器设计方案，它具有结构简单，可扩展 性强的特点。总体结构如图3 - 1 所示。 叫 上行报文存储区u f s 一 上 叫控制器u f s c 斗一一 上l 一 i p itt 一 t p 交 换物 物 围回 h 图 开 交 关 换 理 理 嚼+回回， 接 网 层 层 芯 接 片 口 络 口 一 雹 4 1 -一 rr 叫控制器f ：s f10 一下行报文存储区d f s 一 ，报文数据流控制流 图3 - 1y h n p 网络处理器的结构示意图 y h n p 网络处理器主要包含以下功能部件： 物理层接口( p i ) 。物理层接口p i 负责从物理层芯片接收或者向物理层芯片发送 第二层数据帧，物理层芯片完成第二层数据帧以下的封装和到电信号或者光信 号的转换。物理层芯片不是网络处理器的一部分，网络处理器向下( 对物理层) 只提供第二层数据帧接口，这样使得网络处理器具有较大的灵活性，与不同的 物理层芯片相连可以满足不同情况的需求。 上行报文存储区( u f s ) 及其控制器( u f s c ) 。上行指的是从物理端口到交换网 络的方向。上行报文存储区u f s 存放从物理层接口p i 进入网络处理器的报文1 ， 控制器u f s c 负责u f s 的管理、报文的输入和输出、报文缓冲队列的组织，并 给p e 系统提供访问u f s 的接口。 分派调度部件( d s ) 。分派调度部件d s 完成报文的分派和p e 的调度。d s 监测 p e 系统中每个p e 资源利用的情况以及上、下行报文存储区控制器中报文缓冲 队列的情况，决定报文的分派。同时d s 还监测p e 系统的负载情况，动态调整 参与报文处理的p e 的数目，使p e 系统在不同负载下效率最优。 p e 系统。p e 系统包括多个r i s c 处理器( 即p e ) 和一个共享的搜索引擎( 协处 理器) 。多个p e 采用并行配置的工作方式，每个p e 上可以运行多个线程，一个 线程完成一个报文的处理。搜索引擎完成转发表的查找。多个p e 共享一个搜索 引擎。 1 一般而言，第二层数据格式被称为帧，第三层及以上的数据格式被称为报文。由于本文并不涉及帧或者报文的语义 因此不加区分 第1 2 页 国防科学技术大学研究生院学位论文 下行报文存储区( d f s ) 及其控制器( d f s c ) 。下行是指从交换网络到物理端口 的方向。下行报文存储区d f s 存放从交换开关接口s f i 进入网络处理器的报文， 控制器d f s c 负责d f s 的管理、报文的输入和输出、报文缓冲队列的组织，并 给p e 系统提供访问d f s 的接口。 交换开关接口( s f i ) 。交换开关接口s f i 与交换网络相连，完成报文在网络处理 器与交换网络之间的传送与接收。在传送时，s f i 要对报文进行封装，加上提供 给交换网络的控制信息，然后切分成一定大小的信元：在接收时则反过来，接 收信元并重组，去掉封装信息，在d f s c 的控制下存放到d f s 中。 报文在网络处理器中的处理流程如下： 接收： 1 ) 报文以第二层数据帧的形式从物理层接口p i 进入网络处理器，在上行报文存储 区控制器u f s c 的控制下，存放到上行报文存储区u f s ； 2 ) 在分派调度部件d s 的控制下，报文信息被分派到p e 系统进行处理，p e 将修 改之后的信息存回u f s ； 3 ) u f s c 将完成处理的报文送到交换开关接口s f i ，经过s f i 的处理后送往交换网 络； 发送： 1 ) s f i 从交换网络接收信元并重组成数据报文，在下行报文存储区控制器d f s c 的 控制下，存放到下行报文存储区d f s 2 ) 在分派调度部件d s 的控制下，报文信息被分派到p e 系统进行处理，p e 将修 改之后的信息存回u f s ； 3 ) d f s c 将完成处理的报文送到物理层接口p i ，通过p i 发送到物理层芯片： 本课题主要完成了y h n p 网络处理器总体结构的设计和主要数据通路的设计与实 现，使用v e r i l o g 硬件描述语言对报文存储区控制器u f s c 和d f s c 、分派调度部件d s 进行了描述，并在m o d e l s i m 5 5 下通过了模拟运行。下面将详细论述u f s c 和d s 的实 现以及p e 部分的设计，由于d f s c 与u f s c 很类似，故本章不专门讨论d f s c 。 3 1u f s 报文存储系统及控制器 因为路由器是按照存储转发的模式工作，所以必须对进入网络处理器的报文进行存 储。在y i - i n p 网络处理器中，进入网络处理器的报文将被存放在上行报文存储区u f s 中。本节将提出一种报文的存储组织方式，而不是具体的存储器配置方案。u f s 的控制 器u f s c 完成的主要功能有：1 ) u f s 的管理；2 ) 报文的接收与存储；3 ) 生成并维护 报文控制缓冲区( p a c k e tc o n t r o lb u f f e r , p c b ) ；4 ) 报文向交换开关接口s f i 的发送控制； 5 ) 提供p e 的访存接口。u f s c 的结构如图3 2 所示。 第1 3 页 国防科学技术大学研究生院学位论文 图3 - 2 u f s c 的结构 3 1 1 报文在u f s 中的组织及相关数据结构 u f s 用于存储从物理层进入网络处理器的报文。整个存储空间被分成固定大小的若 干个块，称为数据块( d a t ab l o c k ，d b ) ，每个数据块d b 对应一个缓冲控制块( b u f f e r c o n t r o lb l o c k ，b c b ) ，b c b 有两个域，一个是指向所对应的数据块d b 的指针d a ，另 一个是指向下一个b c b 的指针n a 。b c b 要单独存储，因此整个u f s 是数据块d b 和 缓冲控制块b c b 的总和。数据块d b 的大小和数目可以在具体实现时根据应用来确定， 在本节的讨论和程序实现中，我们假定每个d b 为6 4 字节，一共2 5 6 个d b ，因此存放 数据的缓冲一共1 6 k 字节；b c b 的每个域均为1 个字节，因此b c b 一共占用5 1 2 字节。 在实现中，可以采用不同的存储器来存放d b 和b c b ，可以放在片内也可以放在片外。 空闲的b c b 以链表的形式组织在一起，u f s c 中有两个寄存器b c b _ h e a d 和 b c bt a i l 分别记录了空闲b c b 链表的第一个单元的地址和最后一个单元的地址。当有 新的报文到达时，从b c bh e a d 所指向的单元顺序为其分配b c b 。报文控制块p c b 记 录了报文的第一个b c b 块的位置，因此一个p c b 块对应一条报文。p c b 有三个域，分 别是顺序号n o 、颜色标记f l a g 、报文的第一个b c b 的地址b a 。顺序号n o 用于报 文的定序，颜色标记f l a g 有三种意义：w h i t e 表示已经接收了一个新的报文，正在 排队等待处理：g r e y 表示正在处理；b l a c k 表示已经处理完毕，等待发送给交换开 关接口s f i 。f l a g 域只需要2 位，n a 域需要8 位。由于顺序号是循环计数，所以n o 域的位数取决于f e 的个数，如果n o 域为6 位，则可以支持6 4 个p e ，这在一般情况 下已经足够，因此我们将n o 域设置为6 位。这样一个p c b 块大小为2 个字节。f c b 块被组织在p c b 缓冲区中，这个缓冲区构成了p e 的输入队列，在分派调度单元d s 的 控制下，u f s c 将p c b 分派给p e 进行处理。以上的数据结构如图3 - 3 所示。 第1 4 页 国防科学技术大学研究生院学位论文 ： b c bt a 【l 一 - l 。一i 一i 一 。一1 。一l i l i ll l ；b c b 块 b c bh e a d 空闲b c b 队列 p c b 缓冲区 图3 3 报文的组织方式 3 1 2 报文的接收控制 报文的接收控制逻辑负责与物理层接口p i 通信并接收报文，如图3 - 4 所示。报文接收控 制逻辑里的b c bh e a d 寄存器和b c b _ t a i l 寄存器保存了空闲b c b 链表的头指针 存控 fp c b