HASH GAME - Online Skill Game GET 300

　　摘要 摘要 随着互联网络的高速发展，人们对于网络处理的速度和灵活性提出了更大 的要求，为了满足人们的这些需求，提出了网络处理器的解决方案。网络处理 器是一种可编程的新型网络设备，一方面有类似于ASIC的处理速度方面的优 势，另一方面也有基于CPU的网络设备的灵活性的优势。 网络处理器中快速总线接口承载着多核处理单元以及其他单元之间的数据 通路和控制通路，是决定网络处理器性能的关键单元之一。哈希单元是一种硬 件实现哈希索引的功能模块，在网络地址过滤、网络分流方面具有重要的应用。 本文以高性能网络处理器研究为背景，主要研究了网络处理器的快速总线接口 的结构机制、设计要点。并提出了一种适用于网络处理器应用的哈希单元。论 文首先对快速总线接口中的PULL，PUSH引擎，以及存储单元的设计进行研究设 计。然后比较了现有的三种用于硬件的哈希实现方式，分析了这几种方法的固 有缺憾，在此基础上提出了一种新的硬件哈希方法，这种方法可以针对网络流 的特点优化降低冲突率。然后介绍了电路上的实现方式，提出一种预计算的公 式法来实现。 进行功能仿真，与SDK上微码得到的结果进行对比，分别验证了一次哈希操作， 连续两次哈希操作，以及连续三次哈希操作的功能上正确性。然后进行FPGA板 级测试与性能分析，选用的器件为Virtex．4 果表明设计的哈希单元可以达到最大的频率为217．287MHZ，对于实际测试中 100MHZ频率的FPGA板，可以达到吞吐率为1．6Gbps。 关键词：网络处理器哈希单元地址过滤 网络处理器快速总线接口中哈希单元的设计与研究 ABSTRACT ABSTRACT Withthe ofInternetand havea demandson development technology,peoplebig the ofnetworkandits meetthese for speed flexibility．To requirements，solutions network havebeen isanew ofnetwork processor proposed．Networkprocessortype other theone hasthe of the has eouipment，onhand，it advantageASIC，on hand,it the ofCPU．basednetwork flexibility advantages equipment． ahardwareinnetwork and thehardware HashunitiS module processorprovides indexofhashindex．1thas inbothaddressfilterandnetwork importantapplications basedontheresearchof network distribution．This paper high-performanceprocessor, fastbusinterfaceandhashunit bvhardwareare and implemented analyzed methodsforhardware ofhashindexare researched．Firstly,three implementations selectedsomecertainbitsofthe XOR discussed：Directly address，hashingusing CRC better folding。andhashingusingCRC．Hashingusing providesrelatively resultsinthethree has hash．collisioninsomecases．This methods．However,itlarge anewmethodsto hardwarehash on paper,propose provide index，basedCRC，which can someofthebadsituationofthe adiustparameters(byregistervalues)，toadapt hashindex．Thishardwarestructureofhashcan the improveflexibilityapparently． the a table． Thendiscusses establishlook-up engineeringimplementmethod，propose Thewhole andRTLlevel are with design descriptioncompletedVerilogHDL． andfunctionalverificationiS also withtheresultsin accomplishedcompared ModelsimandSDK．Atlast．the ofthe iSdiscussed synthesisoptimizationdesign the withXilinxISE．Theresultsshowthatthe ofthehashunitcanachieve design minimumclock is themaximum canreach period6．645ns，and frequency l50．480MHZ．whichcanmeetthe forthe systemrequirementsfrequency． word：NetworkProcessorHashUnitAddressFilt Key 网络处理器快速总线接口中哈希单元的设计与研究 第一章绪论 第一章绪论弟一早硒记 1．1课题背景介绍 过去的十几年里，网络设备和因特网迅猛发展，并且他们之间也互相促进着 对方的发展，而因特网的普及【l】，也促进着网络技术的更新和激发更多网络应 用。在早期时候，网桥或者路由器主要是由～些专用设备以及CPU构成，因此 功能的实现主要通过软件方面的编程来实现，依赖于软件的设计，这种设备的 优点在于：易于扩展，适应性强，对于网络中出现的新协议能很好的调整与之 适应。当然这种设备的缺点也同样明显：处理能力有限，因此在网络设备对于 速度要求越来越高的今天，很难满足日益增加的对于速度的要求了。 随着因特网规模扩大以及对于速度要求越来越高的需求，很多网络设备厂 商把目光放在了基于ASIC的网络设备上，这种设备的优势恰恰是过去基于通 用CPU网络所没有的，基于ASIC的网络设备减轻了CPU的负担，大部分的分 组数据可以通过特有的快速通路通过系统【2】。基于ASIC的网络处理设备将一些 耗时并且关键的任务交与专用的集成电路模块来完成，比如说路由表的查找， 数据分组的分类以及转发等等。这样可以实现某些固定功能的快速操作。 随着网络的迅猛发展，更多的网络服务出现了，因此网络设备对于灵活性 的需求也越来越高。可能简单的基于ASIC的网络设备跟不上对于网络服务的 更新需要。可见下一代的网络设备需要相对告诉的网络处理能力而且还要有很 强的灵活性，网络处理器应运而生。 网络处理器是可编程的，使得程序员有很高的灵活性，这种可编程特性使 得可以缩短网络处理器的设计并且快速进入市场。可以看出可以使用网络处理 器技术可以降低成本和减少更新设备的时间，比使用AISC的解决方案节约成 本，而且使用网络处理器可以降低长期成本。网络处理器一般有以下的功能： 为用户提供可编程的缓冲管理器，可以根据管理算法做出转发或者丢弃的决定。 其次，可以根据算法调度数据分组的传输。最后可以实现数据流的修正，包括 包头的修改，根据相关协议对数据进行封装。 1．2互联网的分层结构 1．2．1网络协议与网络分层 全球各地的人用着各种不同厂商出产的电脑，上面装着各种各样的系统， 2 网络处理器快速总线接口中哈希单元的设计与研究 令人惊奇的是，他们之间可以通过互联网相互通信。实际上，这一切都得益于 网络协议的出现，现在广泛应用的互联网协议是叫做“TCP／IP”的协议【3】，它 起源于六十年代末期美国政府所资助的一个关于网络分组交换的研究项目。发 展到现在，TCP／IP协议已经被称之为‘‘互联网的基础”，而广域网(WAN)已 经包含超过150万台分布于全球各地的电脑了。 现在所有的通信设备必须遵照一定的规范细节来进行相互之间的通信，包 括语法细节，和语义细节。同时网络设备工程师考虑到协议规范的管理性，将 网络通信上传输的细节分为几个不同的层次，分别进行规范的制定，这样当这 些孤立的协议被分别研究后，就合成为一个所谓的“协议集”的不同层次协议 的集合。 如图所示TCP／IP协议通常被划分为四层的协议系统，如图所示。分别为 链路层、网络层、运输层以及应用层。每一个网络层次分别对应于不同过程的 规范协议。 应用层 应用协议_一115数据甲元卜一p 砬用层 传输联 传输协议·一114 数抛单元卜_’ 传输层 网络层 ：嚣叫H3 数据荦元 卜 刚络层 数据链路层 -_{12 数据啦元 IDT卜-数据链路层 1．1网络分层与协议 链路层：一般包括电子计算机操作系统中的设备驱动以及计算机中的网络 接口卡。有时候这个层次也被称之为数据链路层或者是网络接口层，它也是整 个网络协议的最低层【41。 网络层：也被称之为互联网层、IP层。主要负责处理分组在网络的行为， 计算机之间的通信。它主要是负责接受来自运输层的分组请求，将分组组成为 IP数据包，同时填充包头，并将之发送到目标路由器上，最终发送到链路层中 的网络接口。 运输层：主要是提供两台计算机应用程序的端到端的通信。TCP(传输控 制协议)和UDP(用户数据报协议)的TCP主要为两台计算机提供比较高的可 靠性的数据通信。UDP则是简单的将数据报的分组传送到另一台计算机，但是 不能保证安全性，所以可靠性必须由应用层来提供。 第一章绪论 应用层：应用层主要负责处理特定的应用程序。包括类似于：远程登录、 FTP文件传输协议、SMTP简单邮件传送协议等。 从上面的简单介绍可以看出： to l、应用层和运输层使用的是端到端的协议(EndEnd)，而网络层使用 to 的是逐跳(HopHop)的协议。 2、网络层的IP协议提供的是一种不可靠的服务，它只关心IP数据包的传 输，尽可能的把分组从起始地址传送到目的地址。 ’3、TCP在不可靠的IP层上提供了一种可靠的运输层，主要通过超时重传、 发送和接受端到端的确认分组等机制。 1．2．3网络地址和数据封装 对于互联网上的每一台主机都有一个对应的地址【5】，也称之为IP地址，长 度是32比特。都具有一定的格式，下面是五类网络地址格式： 码是网络号码，后面三段号码为本地计算机号码；B类地址的范围是从128．0．0．0 到191．255．255．255，B类地址的前两段号码是网络号码，后面两段号码为本地 三段号码是网络号码，最后一段号码为本地计算机号码；D类地址的范围是从 244．0．0．0到239．255．255．255，第一个字节以“1110”开始，它是一个专门保留的 地址。它并不指向特定的网络，目前这一类地址被用在多点广播(Multicast) 中。多点广播地址用来一次寻址一组计算机，它标识共享同一协议的一组计算 可见A类地址可以容纳的主机数是256的三次方，既。B类 地址可以容纳的主机数是256的二次方，为65534台。而C类地址可以容纳的 主机数是254台。 当应用程序用TCP传输时，数据逐一的经过每一个协议层，其中每一层都 对收到的数据进行一些处理，比如增加首部信息【6l。在数据经过TCP协议的时 候被称之为TCP报文，在经过IP协议(在IP层传输时)称为IP数据报，而在 以太网传输的比特流则称为数据帧。 1．3典型的网络处理器结构 简单介绍一下XDNP的基本结构，可以看出主要是由Strong—ARM核、微 4 网络处理器快速总线接口中哈希单元的设计与研究 RISC微处理器的流水结构，可以运行在166MHz下。内部具有4G字节的地址 空间，通过七个内部的片选信号控制对地址的选择。Strong．ARM核主要负责协 议层次平面以及应用程序的处理，对可编程微处理器ME、存储器以及其他一些 资源进行管理。在路由器应用中，主要用于维护路由表，对异常分组进行处理 等。 。 微处理器ME：微处理器ME是一种利用硬件实现多线程调度的处理器， XDNP中包括六个这样的微处理器，也叫做微引擎。支持32比特的RISC指令 集，特别适合应用于网络通信。每个微处理器支持四个线个线 程。具有lK大小的指令存储区，以及128个32比特的通用寄存器(General PurposeRegister)和128个32比特的传输寄存器(TransferRegister)。 快速总线接口FBh快速总线接口主要为MAC层服务，包括数据从MAC 拉到快速总线接口的RxFIFO中，以及从TxFIFO推到快速总线接口外面。快速 总线接口中包括RxFIFO、TxFIFO，控制状态寄存器CSR、大小为4K的 Scratchpad寄存器，主要用于线程之间的通信。以及一个用于产生48位和64 位哈希索引的哈希单元。 SRAM控制器：网络处理器中的一种主要存储单元。数据的存储和读取比 较快，适用于存储对速度要求比较高的存储任务，比如存储查找表。 SDRAM控制器：网络处理器中另一种主要的存储部件，相对于SRAM存 储速度比较慢，但是存储容量大，适合应用于存储对于速度要求不高，但是对 于数据量要求比较高的情况。比如存储大容量的数据包，以及系统执行的微码。 1．2网络处理器的基本结构 如图所示的网络处理器有以下几个典型特点： l、多线程：硬件的多线程处理器可以在同一时间内并发处理不同控制线程 的指令。因此这样的处理器至少拥有2个以上的独立的程序计数器，用于不同 控制线程的指令计数。线程切换开销很小，零到几个时钟周期，多线程处理器 拥有很多的寄存器组，用以存储保存数据，保护现场。当某个线程进入休眠状 态时，线程切换逻辑仲裁则判断他们设备的请求信号，判断下一个进入运行的 第一章绪论 线程。之前进入休眠状态的线程则通过独立的程序计数器、信号事件状态和一 些相关的寄存器组保存下来，用以下次线程激活的时候恢复线、微代码：网络处理器提供的微引擎技术，可以通过微代码对微引擎进行 编程，用以满足网络处理器在不同场合的应用。微引擎的微码类似于汇编语言。 代码执行效率很高并且具有可重用性，每个微引擎都有独立的微代码存储区， 大小是IK，宽度是32比特，在系统初始化阶段将微代码写入存储区。 3、分布式的存储结构：提供多种存储结构，专用的读写存储器对SRAM和 SDRAM的访问。微引擎可以很快的对存储体中的数据进行访问。 1．4论文的主要内容和章节安排 本论文主要研究的工作重点是： l、分析快速总线接口的设计背景，包括网络处理器体系结构以及TCP／IP协 做了RTL级的研究设计。 2、分析了硬件哈希单元的数学背景，介绍了有限域的概念，介绍了CRC。 分析了几种哈希算法，并提出一种新的哈希方法。 3、对本文新哈希方法提出一种易于电路上实现的方案，进行RTL级代码的 描述，并进行仿线、对本文设计的电路进行FPGA的后仿真和板级测试，并进行性能分析。 本文主要的章节安排如下： 第一章：论述了因特网的主要分层结构，TCP／IP结构各层作用。以及 典型的网络处理器的体系结构特点，最后对本文所做的研究意义进行说明。 第二章：分析了哈希单元设计的数学背景，介绍了有限域和循环冗余校 验码的基本知识，论述了传统的按比特的循环冗余校验码和按字节实现的循 环冗余校验码。 第三章：对网络处理器中的快速总线接口的Pull engine和Pushengine 进行RTL级研究设计，主要分析了状态机的设计与设计要点。然后对 Scratchpad电路层次的研究设计，最后介绍哈希指令和数据分流。 第四章：介绍哈希单元的工程实现。首先比较几种现有的哈希方法，在 此基础上提出一种新的哈希硬件实现方法，提出这种方案的RTL实现方法。 第五章：搭建验证平台并对哈希单元进行功能验证。同时对本文提出的 这种方法的哈希单元进行逻辑综合与优化。进行FPGA板级的测试与性能分 析。 第六章：结束语，总结全文工作结果。 6 网络处理器快速总线接口中哈希单元的设计与研究 第二章HASH单元设计基础算法分析 第二章HASH单元设计基础算法分析 2．1有限域 2．1．1有限域的定义 有限域运算是密码学研究的重要内容，主要包括有限域上的加法和减法，有 限域上的乘法、取模，以及有限域上的求逆等。在密码学、数字信号处理、编 码理论以及超大规模集成电路上有限域都有着重要应用【71。下面是有限域的定 义。 假设尸是素数，则由整数集合{0，l…尸}就组成了一个有限域，或者称之为迦 术运算： 数，其中0≤r≤P一1。 乘法@：假设a．b∈GF(P)，那么a圆b=s，其中S是口．b被尸除得到的余数， 其中0≤J≤P一1。 这里有限域对于数学运算是封闭的，也就是说对于有限域GF(P)内部的任 意两个元素做加法或者乘法(上面所定义的加法和乘法)，’所得到的结果仍然 是属于有限域内的【81。 2．1．2有限域与多项式 迦罗瓦域的元素的个数称之为迦罗瓦域的阶【91，特别的其中阶数为2”的有 限域叫做二元域，用符号记为GF(2”)，一般二元域GF(2”)中元素可以用多项式 基的表示方法，也就是说二元域GF(2”)中元素可以用次数为最高n．1次的二进 制多项式来表示。其中多项式的系数来自GF(2)，也就是取{O，1)中的元素。 在有限域GF(2”)中二元域的多项式乘法需要遵循有限域内的加减法法则。 由于后面需要用到二元域中的两个次数为七的多项式的乘积，所以这里以两个 七次多项式乘机为例说明。对于两个二元域的多项式A和B的乘积，设A为： 这里a[71，a【6】一直到a[O】都是属于GF(2)的，也就是只能取得也就是取{0， 1)。 设B为： 这里b[7】，b【6卜。直到b【0】都是属于GF(2)的，也就是只能取得也就是取{O，l}。 那么对于AoB可以得到一个最高次数为14的多项式C。假设多项式C的形式 网络处理器快速总线接口中哈希单元的设计与研究 C=c[14]x14+413]x13+c[12V2+411ixn+c[10]xlo+c[9]x9 +c【8】x8+d7]x7+c【6】x6+c【5】x5+c[4】x4+c[3]x3+42]x2c[qx+c[o】 同样的，这里c[14]，c【13】一直到c[0】都是属于GF(2)的，也就是只能取得也就 是取{0，ll。 容易得到c[14]、c【13】到c【0]的数值，需要注意的是这里的加法遵循有限域 的加减法法则，100=l，101=0。那么 c[14】=a【7】b【7】 a【7】b[6】^a【6】b【7】 c[13】2 c[12】=a【7】b【5】“a【6】b【6】“a【5】b[7】 c[1 1】=a[7】b【4】“at6]N5】“a15]b[6】^a【4】b【7】 c【l0】2a【7】b【3】^a[6]b【4】^a[5lb[5】“a[4lb[6】“a【3】b【7】 c【8】2 c[7】2 ^a[Olb[7】 c【6】=a【6】b【O】^a[Slb[1】^a[4lb[2】^a【3】b【3】^a【2】b【4】^a[1lb[5】^a【O】b【6】 c15】2 c14]=a【4]b【0】^a【3】b【l】“a[2lb[2】^a[I】b[3】^a[Olb【4】 c【3】=a【3]b【0】“a【2】b【l】“a[1】b【2】^a[Olb[3】 c12】-a[2Jb[O]“a【1】b[1]I“a[0lb[2】 c[1】-a[1]b【0】“a【0】b【l】 c[O】-a【0】b【0】 这样就得到了二元域内的两个最高7次多项式乘积所得的最高14次多项式的系 数。容易看出二元域的相加都是用异或来表示。 2．2循环冗余效验码(ERE) Check，中文名称为循环冗余校验【101。它 CRC的全称为CyclicRedundancy 是一类重要的线性分组码，编码和解码方法简单，检错和纠错能力强，在通信 领域广泛地用于实现差错控制。实际上，除数据通信外，CRC在其它很多领域 也是大有用武之地的。例如我们读软盘上的文件，以及解压一个ZIP文件时， 偶尔会碰到“BadCRC”错误，由此它在数据存储方面的应用可略见一斑。差错控 制理论是在代数理论基础上建立起来的。这里我们着眼于介绍CRC的算法与实 现，对原理只能捎带说明一下。若需要进一步了解线性码、分组码、循环码、 纠错编码等方面的原理，可以阅读有关资料。CRC算法广泛用于数字信号处理 等领域，现在已经有成熟和比较经典的现成代码可以参考。 2．2．1 CRC简单介绍 利用CRC进行检错的过程可简单描述为…】：在发送端根据要传送的k位二 第二章HASH单元设计基础算法分析 9 进制码序列，以一定的规则产生一个校验用的r位监督码(CRC码)，附在原始信 息后边，构成一个新的二进制码序列数共k+r位，然后发送出去。在接收端，根 据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。这个 规则，在差错控制理论中称为“生成多项式” 在代数编码理论中，将一组数据流表示为一个多项式，然后通过处理多项 式的系统来处理数据流，比如数据流“1101”可以用多项式表示为，+，+l； 1001 数据流“101 1”可以用多项式表示为：x7+矿+X4+x+l。 设编码前的原始信息多项式为尸(X)，尸(X)的最高幂次加l等于k；生成 CRC的信息多项式为丁(X)。 发送方编码方法：将尸(X)乘以，(即对应的二进制码序列左移r位)，再 这里余式与原始信息构成了发送的传输字段。可见，传输字段由两部分组， 1001”即与之 原始信息字段和校验字段组成。举个例子，假设信息字段为“101 对应的多项式为：X6+X4+X34，而这里假设生成的多项式为： 的多项式进行乘运算：X4朋(曲=一o+矿+x7+x4，对应的二进制数据为： “”。然后采用多项式除法，得到余数为“l101”，也就是得到的 CRC校验码为“1101”。所以发送方发送的数据最后为：“1011001110l”前 7bit为原始的信息字段，后4bit为得到的CRC校验码，这两部分共同组成了发 送方发送信息数据。 在接收方方面，如果说发送的数据流，转为多项式表示，如果可以被二进 制除尽，那么证明数据正确，如果不能除尽，说明数据传输错误。 2．2．2按字节实现的CRC 在实际的计算机应用中，大多是以字节为单位进行处理的，因此研究按字节 进行CRC运算就显得非常重要。这里设一个数据流用多项式表示为： b(x)=玩@)28”+吒一l(x)2M”u+…+6l(x)+60(x) 这里％【叫表示一个字节的多项式。 在计算这个多项式的CRC码时，第一步是左移16bit(就是乘2”)得到 b(x)216=玩@)28，，26+屯一。(X)2s(n-1)216+。．+6lG)26+60章)2‘，然后除以g(曲得到： —b(x)—26：垒垒鲨2孙+丝=!!兰堡1 2sc—t)+…+—bt(x—)2+刍垒鲨 g(x) g(曲 g(x) g(x) g(x) (2．1) 这里我们令垒竺娑：吼(x)+婴 (2．2) gL石J gLxJ 将之带入(2．1)，得到 !壁 网络处理器快速总线接口中哈希单元的设计与研究 等砘∽+妒+警2聊-I)+．．．+等23+等协3， 其中，：，(x)28={‰8(力28+‰8(x))28 一’ =‰8(x)216+‰80)23 这里，赢是，；，(功的高8位，白。是，：，(x)的低8位。 最后整理得到 学一Ⅵ学+唑铲澎㈣+．-．+等23+等 (2-4) 再令 ． r．t8(x)28 ；％(功+掣 g(功 g(功 ．g(x) (2．5) ’ 将之带入上式(2．4)，得到 等吲班8Ⅵ‰∽+等沙㈣，+．．．+等23+等协6， ‘一I(x)28={气．-K)h8(功28+气n-I)／s@))28 其中 2铀)^8(x)216+铀)，8(x)28 继续化简，得到 等吲班跏州班蛳叫+篙2跏-I)+等筹28忙2k．．+等署28+笔等 ：％∞2h+孙，(力2蛳-1)+{fi．-,，ls，(X，)2s．+坠盟警号坐皇鲨沪埘+．．．+坐芝2。+业鲨。 g【xJ g(功 g(x) g(x) (2．7) 最终得到 因此可以看出求一个以字节为基本组成的数据流，可以通过迭代的办法逐渐 求解。先从最高位的第一个字节开始，先算出第一个字节的CRC码，然后迭代， 通过公式 血!!生竺+匕§g!±堡=』趔兰：： g(石) g(x) 刚小等 像9) 算出第2步迭代的CRC码(利用预计算的方法将结果实现计算出来，一共2陋个 预计算结果)。显然利用这种预计算的查表方法，可以提高CRC的运算速度。 第三章快速总线接口设计研究 第三章快速总线接口设计研究 FBI(快速总线接口)是网络处理器与IX总线，它主要包含有片 态寄存器等。微处理器(ME)通过快速总线接口的推、拉引擎来使用这些硬件 的命令队列，以及推拉的状态机。 SRAM SDRAM 丫T f7 V V lIl】 ml二 SP,AM传输寄存器 SDRAM传输寄存器 』 参考指 争 ， 1『 、 快速总线接口 SCMTCIP RFI阳 }I^sH TFIFO AI) cSRS 图3．1数据交换总线与相关单元的结构关系图 FBI(快速总线接口)单元以微包进行数据的传输单位。微包是64B的传输 单元。对于一个以太帧，通常被分为若干个微包进行传输。快速总线接口中的 接受状态机，主要负责进行微包的接收。发送状态机则负责数据微包的发送。 这两个状态机相互独立运行，这样提高了数据的传输速度。接收状态机位于 PULL引擎中，发送状态机位于推引擎中，这里的推和拉都是相对于快速总线命令的处理与译码 推拉引擎的工作是由指令控制的，指令来自于FBI外部的命令总线。对于 外部的指令需要分三步来进行判断(1)判断指令是否有效(2)判断指令是否 12 网络处理器快速总线接口中哈希单元的设计与研究 为发往FBI单元的指令(3)根据指令判断是PULL指令还是PUSH指令，来选 择送入相应的指令队列中。 可以看出，通过将60位命令总线的相应位数剥离出来，组成了主要的判断 字段是ref 和 cmd epyt．type。 -=e 9：§11 ； 龋●l秘tel_t：搬捷 lna,t：re_lms【S 删i辨 c=,a l ； yylrat l{tm_taat：rc_鼬【3：l，,--_taat：船bw￡27：261 wr 值，产生相应的信号，包括拉引擎队列写使能信号pullque en；推引擎队列 wren， 标记信号 ，和快写标记 的写使能信号push scratchpad 信号 wr 。．．que flag 命令由cmd type和ref_type共同决定，如下表所示： 表3．1参考指令类型 Oll000 1ll000 11l00l Oll010 Ollloo {tel_type， cmd_type} Scratch写 CSR写 指令操作 CSR读 Scratch读 CSR快写 0ll110 lllllO 11110l 0lllll {ref_type， cmd type l J 指令操作 RxFIFO读Scratch位写Scratch增1TxFIFO写 3．1．1 Pull引擎 拉引擎(PULLENGINE)是在微处理器的指令控制下，将外部的数据，“拉” 进内部的硬件部件中113】。除了微处理器的命令之外，PULL引擎也支持Ready 总线对微引擎SRAM传输寄存器的autopush操作。 PULL引擎中指令优先级最高的是STRONGARM指令，主要是负责状态 寄存器的改写，系统初始化，因此优先级最高；其次优先级的是SDRAM对微 处理器的PULL队列的指令，包括微处理器对于状态寄存器的改写、清零和微 处理器对SCRATCHPAD的操作类指令。 如图是PULL引擎的状态机。 第三章快速总线PULL引擎状态机图 拉引擎这里的仲裁机制分为两个层次来进行判断的。 A善湛工rE ：l糟口in l￡‘獭蜥躐：缒：淤：酶遍娩确一二’￡I WR—C5震 ； nx七一5Ease。STROHG_ARM else lf‘嚣d譬藏∞曩-；￡工￡。一wj?一req—be土n；乙fla口_—l二’毫二’ DATA ； nxc—oc薹te_WAIT_SDRAM 毒1撕lf{pull_que_empⅥ_n血?9酶二’ I ? 勰l毒cace DKCO。￡跹一INSTRC ei嚣e ； 盎x七一s仨量te·ARBITE 第一层：首先判断外部的命令式来自于哪个队列，是通过相应队列的FLAG 的。这里STRONGARM是来自STRONG SDRAM直接写TFIFO的命令，类似于DMA操作。PULLQUE是从ME中发 wrcsr 出的，优先级较低。(1)当strong_armbeing_flag=l时，进入状态 时， 进入 WAIT—SDRAM—DATA状态；(3)当pull_que_empty_n=l ME DECODEINSTRC状态。这是第一层的判断。 14 网络处理器快速总线接口中哈希单元的设计与研究 图3．3PULL引擎第一层次指令判断图 第二层： CSR写 (1)对于来自于STRONG—ARM的命令。当StrongARM 状态寄存器CSR的初始配置。执行完毕然后重新返回ARBITER状态。 图3．3来自STRONGARM的指令分支图 rd 并且SDRAM写RxFIFO请求队列的有效标志位rxfifo req_valid_flag=l时进 图3．4来自SDRAM的指令分支图 状态进行次一级判断，看是什么样的指令，这是通过从ME传输过来指令的 第三章快速总线接口设计研究 ， 等状 态 。 l 、 若 SCRA—INCR SCRA—TEST—CLRBIT {cmd_type，scratch_flag}=4’blllO，则系统进入ME．邗IFO—WR状态2、若 l {cmd_type，scratch_flag}=4’b 1 {cmd_type，scratch_flag}=4’b00l，则系统进入到SCRA—WR状态4、若 101 {cmd_type，scratch_flag}=4bl，则系统进入SCRA—INCR状态5、 {cmd_type，scratch_flag}=4’b110l，系统进入SCRA—TEST—CLRBIT状态 图3．5PULL引擎来自ME的指令分支图 TFIFO 其中ME WR：是ME进行的写TxFIFO的操作。首先指令译码单元 通过对指令中指定的FIFO地址以及相关参考数量，判断并形成与之对应的 数据装载到对应的TxFIFO控制域中，完成对于TxFIFO的控制域的写入。 MECSR WR是ME进行状态寄存器写的操作，将微处理器中SRAM传输寄 存器的相关数据读到状态寄存器中。SCRAWR：ME进行SCRATCH的写操作， 将微处理器中的SRAM传输寄存器内容传到SCRATCHPAD单元内部。 SCRA 1NCR：SCRATCH的自增一操作。 3．1．2Push引擎 推引擎主要负责将数据从FBI内部“推”到外部单元中，如传输到微处理 器中的SRAM传输寄存器、ARM核、或者SDRAM存储器中。这些行为是通 过微处理器、ARM核以及SDRAM存储器相应的指令执行来实现的。 由于STRONGARM进行的控制状态寄存器的写功能，通常用于系统的初 始化，因此具有最高的优先级；然后优先级略低于STRONGARM优先级的指 中，提高了数据的传输速度。最后相应的指令是微处理器的指令，包括微处理 16 网络处理器快速总线接口中哈希单元的设计与研究 器对于某些状态寄存器的改写，对SCRATCHPAD的访问，数据改写和清零。 图3．6 PUSH引擎的状态机图 这里的状态判断也是分两层来完成的。控制整个模块工作的核心是由一个状 态机来实现的，一共有七个状态，分别为IDLE、ARBITRAGE、 EXECUTE—SDRAM—CMD。 系统响应各种指令的优先级如图所示： 表3．2push引擎的指令优先级 指令类型 优先级 Strong_arm核 l Scratchpad指令 2 3 SDRAM的DMA指令 Push队列 4 如下图，系统复位后，由初始状态IDLE跳入ARBITRAGE(判断仲裁)状 态。(1)在ARBITER这个状态时，系统会自动向SDRAM发出读请求信号， 然后检测是有无从SDRAM过来的读请求；如果没有检测到SDRAM的请求， 系统会自动判断Push命令队列里是有待执行的ME指令，如果有待执行的ME 第三章快速总线接口设计研究 指令，则会执行读取指令。这是第一层的判断。 PUSH引擎第一层次指令判断图 valid (2)当数据返回请求队列为空(dretum req rd valid 输请求队列中有读RxFIFO的DMA传输请求(rxfifo req flag=1)时， SDRAM RD 进入RD CMD状态。SDRAM 状态，此状态下推引擎响应SDRAM读接收FIFO的直接内存存取请求。推引擎 断仲裁)状态； 图3．8来自SDRAM指令分支图 (2)如果是从ME发出的指令，Push指令队列的队列空标志queempty．n=l PUSH (表示队列中有待执行的参考指令)，进入DECODECMD状态， ME DECODEINSTRC状态为数据处理单元指令译码状态，此时内部相关逻辑 依据指令内指令类型和scratch标记字段决定拉引擎接下来将要执行何种操作。 相关逻辑会对{cmd_type，scratch_flag}字段进行译码。 CSRREAD状态。 4’b0001)时，进入MEREAD 13 网络处理器快速总线接口中哈希单元的设计与研究 4’bl 100)时，进入ME—RFIFO—READ状态。 当执行完成后根据指令中的信号完成(sig_done)标志位的有效与否来决定 在DONE状态下是否向ME发送信号完成(sig_done)信息，然后再跳回 ARBIRAGE状态； 图3．9。PUSH引擎来自ME指令分支图 如果既没有SDRAM读请求，PUSH队列中也没有待执行的ME指令，则系 统会保持在ARBIRAGE状态，并在奇数时钟周期向SDRAM发送请求允许信号， 在偶数时钟周期作出仲裁。 推引擎主要的指令详细功能如下 1MEREAD RFIFO：微处理器进行读TxFIFO的操作。主要用于Pull命令 队列中的TxFIFO读。首先指令译码单元通过对指令中指定的FIFO地址以及相 关参考数量，判断并形成与之对应的TxFIFO读使能和TxFIFO读地址，TxFIFO 控制域中相应的数据传到微处理器中SRAM传输寄存器，完成对于TxFIFO的 数据的的读出。 2MEREAD CSR：微处理器进行状态寄存器读的操作。主要用于PULL 命令队列的状态寄存器的读。首先指令译码单元判断指令类型(instruc type)， 如果是该指令，则判断奇偶周期(oddeven)以及状态机的控制计数器。如果 达到相应要求，则将状态寄存器中相关数据读到微处理器中SRAM传输寄存器 中。 MEREAD 3 SCRATCH：微处理器进行SCRATCH的读操作。主要用于 PULL命令队列中的STRATCH读。通过判断指令中的首地址、参考传输量 (refent)，以及奇偶周期和状态机计数器，来进行相应的操作，将 SCRATCHPAD单元内部的内容存到微处理器中的SRAM传输寄存器内。 4SDRAMREAD l讧lFO：SDRAM进行的TFIFO读操作。这是一种 第三章快速总线 量并将产生相应的TxFIFO读使能以及读地址。这样来将TFIFO单元中数据读 到SDRAM中，提高了数据的传输速度。 3．2快速交换总线Scratchpad存储器 102432比特，STRONGARM以及微处理器(ME)都可以通过指令来访问它。 对于Scratchpad，有三种基本的指令操作，一是读写操作，二是比特操作，最后 是自动加一操作。其中微处理器ME可以通过相应指令进行上面的三种操作， 而STRONG ARM只能进行基本的读写操作。 读写操作：包括微处理器ME和STRONGARM的读写操作。假设微处理 器ME进行写操作，数据存在微处理器的SRAM传输寄存器中，然后发送一条 读写指令到FBI的命令队列中，当队列中的这条指令执行时，首先从SRAM传 输寄存器中读取需要的数据，然后写入Scratchpad存储器中，并通知相应的线 程指令写操作结束。假设微处理器ME进行读操作，命令首先放在命令队列中 排队，当队列中这条指令得到执行的时候，对Scratchpad进行读操作，将 程指令读操作结束。 比特操作：微处理器可以对Scratchpad进行比特的操作。主要包括两种操 作，一是对32位的比特指定位进行置数的操作，另外一种就是对指定位置进行 清零的操作。当微处理器进行比特写操作时候，先将比特掩码读进寄存器中， 然后进行比特写的操作。 自加一操作：微处理器可以对Scratchpad进行自加一操作。这里的自加一 操作指的是32位比特中指定位的自加一，指令首先被放在PULL队列中，如果 指令被执行，则从Scratchpad中读出数据，并且对之的指定位置进行自加一操 作，并写回。最后通知相应的线程指令读操作结束。 下面介绍了Scratchpad的功能，下面从电路的角度进行描述。 X1024的双端13片上SRAM以及控制逻辑组成。 Scratchpad存储器由32bit 如图所示： 网络处理器快速总线接口中哈希单元的设计与研究 图3．10 Scratchpad电路结构图 对于片上SRAM的输入，是Scratchpad存储器外部输入进行一些逻辑运算来实 现，下面进行分析： wrenin incrresultwren setbitresultwrell 其中写使能WEN=scratch clr—bit—result—wr—en · 写地址WADDR=scratchwraddrin 读地址RADDR： rden—lbl 时 addrin 当origin_data RADDR=scratch…wr rdell rdaddrin 当scratch in一1-bl时RADDR=scratch wren 数据输入DIN当scratchin=1时进行写操作。 2 DIN me—data—to—scratch resultwr 当incr en=l时进行加一操作 DIN=me—data—to—scratch+l bitresultwr 当set en=l时进行置位操作 I DIN=me—data—to—scratchscreen—code bitresultwr 当clr en=l时进行清0操作 code) DIN=me—data—to—scratch(-screen code datato 其中screencode是当输入信号screenlatchen为高时，me scratch 的延迟一个时钟周期的信号。 3．2．2状态寄存器 快速总线接口的CSR对整个系统的正常运行起非常重要的作用。它主要具 有以下几个主要方面的作用： 第三章快速总线 配置IX总线接口，以及配置HASH单元。 设置线程之间的通信信号，为线程之间的通信提供了可能。 提供了微处理器运行的状态信息，为检视微处理器ME的运行状态提供了 可能。 STRONG ARM以及微处理器ME都可以通过相应指令来操作状态寄存器 CSR，除了GETCMD和CYCLECMD寄存器，其他的FBI寄存器都是每条指 令读一个寄存器的值出来。GETCMD映射为一个深度为8宽度为32BIT的 FIFO，每一条指令可以读4个深度的数据。而读CYCLECMD寄存器则返回一 个64位的数值到微处理器ME的两个SRAM传输寄存器中。 微处理器ME支持一种快写指令(FASTWR)，这种快写指令没有经过 PULL队列以及PUSH队列而是直接写FBI的状态寄存器，提高了写的性能。 这种快写指令只有微处理器ME支持，而STRONGARM则没有这种快写状态 寄存器的指令。快写指令提供了lO比特的立即数到参考命令上，这降低了PULL 引擎从微处理器传输寄存器中读数据的需要。 快速总线接口中CSR控制状态寄存器，有一些状态寄存器用于快速总线接 口的数据接收和发送，以下是对部分状态寄存器设计的简单描述： 1、就绪轮询模块 此模块中的状态寄存器主要是启动READYBUS、另外查询网卡端口发送 和接收的就绪状态。 countdefault： READYBUS 快速交换总线 rdybushcnys．，器存寄个一的 它作为存放READYBUS来获取网卡端口就绪状态的轮询周期，状态寄存器的 写参考指令可以将数据写入此寄存器中。 ： READYBUS rdybusetalpmet．的样这个3有共，器存寄储存令指微 progx 位置，因此对于每一个寄存器来说，都可以存储4条这样的指令，那么就能够 存入12条这样的指令。READYBUS运行的时候，首先按照一定的顺序取出这 些微指令并根据取出来的内容来决定何种操作，一般操作的类型为：搜索网卡 指定的端口的接收就绪状态，搜索网卡指定端口的发送就绪状态。特别的，状 态寄存器的写参考指令可以访问这个寄存器。 flowctl mask：这个状态寄存器是用于存储流控的相应数据，当 READY BUS每次执行一条指令时，则将这个寄存器里的值发到外部特定的网 卡中去。 t READYBUS ME ：用来控制 的寄存器。微处理器 ltcrdybus_etalpme．过通 CSR写参考指令来配置，来启动READYBUS、并设置READYBUS的工作模 网络处理器快速总线接口中哈希单元的设计与研究 式。 ’ 2、接收控制模块和发送控制模块 这个模块的状态控制寄存器主要是用来处理外部数据的接收和发送 rEv．req：用来获取接收请求的寄存器。微处理器ME通过状态寄存器写参 考指令向此寄存器发送一个接收请求。接收请求包括接收请求的类型：快端口 或者慢端口请求；线程的信息；接收缓存RxFIFO号：数据放置的FIFO号；网 卡和端口号等。 rcv cnth用来控制接收的寄存器。该寄存器中的信息包括：接收信息的 FIFO中的单元号、数据的长、线程信息和快速端口号等。微处理器单元通过状 态寄存器的读参考指令来读取其中信息并据此对相应FIFO单元中的数据进行 转移。 xmit_ptr：发送指针。指向一个待发送的TxFIFO单元。每完成一次发送请 求，指针就自动加l。包处理单元线程通过状态寄存器读指令来读取这个寄存器， 并用以确定何时发布一个发送请求。 xmit validate：发送有效寄存器。当某一个TxFIFO单元被写入一个状态数 据，发送线程就会发出一个FAST WR指令，来将相应的单元号读到这个寄存 器中。 ． 3、HASH单元模块 HASH单元模块中的状态寄存器主要配置HASH计算过程中需要的乘数。 hash 64hi：64HASH HASH 位 乘数的高32位。它与64位 relipitlum．数乘 的低32组成64位HASH乘数。用来产生64位的HASH索引。 hash 64 位 乘数的低32位。它与64位 乘数 HASH 的高32组_．m成ult6ip4i位lerHSAHIo：乘64数。H用A来SH产生64位的HSAH。引索 hash 48hi：48位HASH乘数的高32位。它与48位HASH乘数 multipiler 的低32组成48位HASH乘数。用来产生48位的HASH索引。 hash 48Io：48位HASH乘数的低32位。它与48位HASH乘数 multipiler 的高32组成48位HASH乘数。用来产生48位的HASH索引。 3．3快速交换总线中的HASH单元 HASH单元位于快速总线中，是用来提供HASH索引的硬件部件【141。 位的HASH操作，输入一个48比特的数据，同时得到一个48位的哈希索引。 而HASH一64则是提供64位的HASH操作，输入一个64比特的数据，得到一 个64位的哈希索引。执行HASH操作完全是通过微处理器ME中的相关指令来 第三章快速总线接口设计研究 进行的，也就是说只有微处理单元ME可以方针HASH单元。 2．3．1Hash指令 Hash指令的执行同时需要推拉引擎协同完成【15】。首先微处理单元向FBI单 元的命令队列发出Hash命令，将微处理单元中SRAN传输寄存器中的需要产生 哈希索引的数据读到FBI单元中，然后等待哈希运算的进行，等到哈希运算完 成以后，向PUSH引擎发出命令请求，将得到的哈希索引值读回到微处理器中 SRAM传输寄存器中。如果指令中有signal的选项，那么快速总线接口单元就 向微处理器单元发送信号，表示Hash操作已经完成。 一条哈希指令可以执行一到三条哈希操作。哈希单元内部有专门存储输入数 据的暂存器，因此哈希指令的执行的时候，快速总线接口的Pull引擎首先将输 入数据存储在内部的暂存器中，这样每次都要对Pull引擎进行一次服务请求， Pull引擎的任务仲裁器赋予一个正在进行的Hash操作较高的优先级，而新的请 求的Hash操作比较低的优先级。 微引擎的基本哈希指令格式如下： Hashl 48[$sram_xferreg]，optional_token Hash2_48[$sram_xferreg]，optional_token Hash3_48[$sram_xferreg]，optional_token Hash I_64[$sram_xferreg]，optidnal．_token Hash2_64[$sram_xferreg]，optional_token Hash3_64[$sram_xferreg]，optional_token $sramxfer ：ger．于用也且并，据数入输了供提，址地首的器存寄续连组一示表 存储得到的哈希索引。这里SRAM传输寄存器都是以$开头的。 optional_token ·sig ：enod_相知通件事号信的口接线总速快用，时毕完行执令指考参当示表 或defer[1]--起使用。 ·ctx swap：表示当微处理单元执行内存访问时，切换线程，当访问完毕后在 done同时使用。 唤醒本线程。不能和sig ·defer[1]：应该与ctxswap同时使用。表示在线程切换之前，执行该指令的 下一条指令。不能和br!=signal一起使用。 ·voluntary：paws．换交，后以行执程线他其许允且并用调起发程线擎引微在 上下文。当另外的线程有机会执行的时候就交换上下文，否则继续在本线 网络处理器快速总线接口中哈希单元的设计与研究 运行。 实际上每次微处理器进行哈希操作的时候，首先将输入数据写进微处理器中 一组连续的SRAM传输寄存器中，然后执行哈希指令操作。实际上每一个哈希 索引需要两个传输寄存器的空间，在48比特的哈希索引操作里，哈希单元自动 忽略了第一个传输寄存器的最高的16比特数据。 2．3．2 Hash单元与数据分流 在不同的场合，可以对于数据流有不同的定义【16】。相同的“流”可能是具 有相同的源网络地址的数据，也可以是具有相同的源网络地址以及目的网络地 址，或者是同时属于相同的TCP连接。 在大多情况下，将源IP地址，目的IP地址，源端口号，目的端口号，以及 协议作为关键字，组成五元域‘171。而哈希表具有如下结构： 表3．3hash表基本结构 大小(比特) 描述 32 源IP地址 32 目的IP地址 16 源端口 16 目的端口 8 协议类型 24 冲突的下一索引地址 8 数据包发往的设备 首先将关键字通过硬件的哈希单元，计算得到相应的哈希索引，然后取结果 的某些位作为哈希索引，在哈希表中查找，如果没有这个表项，则建立新的表 项，根据后面设备的利用率来得到数据包发往的设备号。 随着时间的经过，要对表进行淘汰【l引，否则存储空间可能被耗尽。如果某 个流不很久不再网络中使用，则应该将之对应的表项删除，这样可以降低冲突 率。可以采用定时清理的方法，如果某个流经过，则给于一个新的标记，经过 一段时间标记如果没有更新则将这个表项淘汰。 第三章快速总线本章小结 本章主要讲述快速总线接口(FBI)的相关模块的设计。快速总线接口包括 寄存器CSR，哈希单元。分析了PULL引擎和PUSH引擎的设计，这两个推拉 引擎相互独立于对方，这样提高了数据的传输速率。重点描述了推拉引擎的状 态机对于来自于STRoNGARM，ME，以及SDRAM的指令请求如何仲裁等的 设计细节，然后从快速总线接口中的存储部件的电路层次进行设计。最后介绍 Hash指令以及Hash单元在数据分流方面的应用。 26 网络处理器快速总线接口中哈希单元的设计与研究 第四章HASH单元的工程实现 第四章HASH单元的工程实现 随着网络规模的越来越大，网络传输速度也要求越来越快，网络中地址变 得越来越多，因此需要更强大的能力去辨别区分网络地址。这个问题实际上也 可以类似于假设存在一个很大规模的数据库，在这个数据库中寻找一个有特定 关键词的地址。举个例子来说，在局域网内的网卡适配器需要确认局域网内多 目的点传送的地址。用于连接多个局域