CN1808387B

CN1808387B - 用于多个多线程可编程处理核的方法和系统

Info

Publication number: CN1808387B
Application number: CN2005101191806A
Authority: CN
Inventors: S·贾因; D·F·霍珀
Original assignee: Intel Corp
Current assignee: Intel Corp
Priority date: 2004-12-30
Filing date: 2005-12-30
Publication date: 2010-05-26
Anticipated expiration: 2025-12-30
Also published as: TW200637277A; US20060159103A1; WO2006074047A1; CN1808387A; US7477641B2

Abstract

提供对分组处理线程共享的数据的存取。通常，在一个方面中，本公开内容描述了一种方法，包括在第一核上执行的第一分组处理线程上，对包括第一线程的分组处理线程之间共享的数据执行存储器读取。该方法还包括，在第一分组处理线程上，经第一分组处理线程对共享数据执行专用操作之前，确定通过存储器读取返回的数据已经被另一个核上操作的分组处理线程所改变。

Description

用于多个多线程可编程处理核的方法和系统

技术领域

本发明涉及数据存取，具体涉及对分组处理线程共享数据的存取。

背景技术

网络能够使计算机和其他的设备进行通信。例如，网络可以携带表示视频，音频，电子邮件等等的数据。典型地，经网络发送的数据被划分成称为分组的较小的消息。打个比方，分组更像是你放入邮箱的一个信封。分组典型的包括“有效负载”和“首部”。分组的“有效负载”类似于信封中的信件。分组的“首部”更像是写在信封上的信息。首部可以包括信息以帮助网络设备适当的处理分组。例如，首部可以包括识别分组目的地的地址。

在到达目的地之前，给定的分组可以经许多不同的中间网络的转发设备来“跳跃”(例如，“路由器”，“桥路”和/或“转换器”)。这些中间设备通常执行各种分组处理操作。例如，中间设备经常执行分组分类以确定如何把分组进一步朝着它的目的地转发或确定所提供的服务质量。

仔细地设计这些中间设备以保持经网络传输的业务容量的快速增加。一些体系结构使用“硬线”逻辑实现分组处理，比如专用集成电路(ASIC)。尽管ASIC能高速操作，但例如改变ASIC操作以适应网络协议中的改变被证明是困难的。

其它的体系结构使用公知的作为网络处理器的可编程设备。网络处理器能够使软件程序员快速地重编网络处理器操作。一些网络处理器具有多处理核的特性以聚积分组处理计算能力。这些核可以并行的对分组进行操作。例如，当一个核确定如何把一个分组进一步朝着它的目的地转送时，不同的核确定如何转发另一个分组。这能够使网络处理器实现与ASIC相匹敌的速度，同时保留可编程能力。

发明内容

本发明提供一种方法，包括：

在第一核上执行的第一分组处理线程上，对包括第一线程的分组处理线程之间共享数据执行存储器读取；

在第二核上执行的第二分组处理线程上，向第一分组处理线程发送对所述共享数据的一个或多个改变响应而产生的一个或多个消息；和

在第一分组处理线程上，确定经第一分组处理线程对共享数据执行专用操作之前，通过存储器读取返回的数据已经被另一个核上操作的分组处理线程改变。

本发明还提供一种具有多个多线程可编程核的系统，包括：

单一电路片上集成的多个多线程可编程核；

逻辑为：

使用通过多个多线程的可编程核提供的分组处理线程的序列来处理分组，跨越核序列的线程的序列至少包括，第一核、第二核和第三核，各个线程至少包括一个临界区，协调存取通过线程共享的数据；

其中第一核上执行的分组处理线程的序列中的线程执行操作包括：

发出第一信号到第三核，允许通过第一临界区保护的共享数据的预临界区读取；

其中第二核上执行的分组处理线程的序列中的线程执行操作包括：

执行第一临界区；和

如果在第一临界区内修改共享的数据，发送识别该改变的一个或多个消息给第三核；和

其中第三核上执行的分组处理线程的序列中的线程执行操作包括：

从第一核接收第一信号；

在从第一核接收第一信号之后，在进入协调存取共享数据的临界区之前，执行存储器存取以检索通过分组处理线程共享的数据的拷贝；

基于是否第三核接收了识别共享数据的改变的至少一个消息，确定是否由分组处理线程共享的数据已经从拷贝中改变；

如果数据没有被改变，使用临界区中检索的数据；

如果数据被改变，使用临界区中改变的数据。

附图说明

图1A-1C示例了线程处理分组。

图2A-2B示例了采样分组处理体系结构。

图3是多核处理器图。

图4是网络转送设备的图。

具体实施方式

网络设备执行各种操作以处理分组。这些操作可以包括分组分类，确定如何转送分组，等等。为了对大容量快速到达的分组执行这些操作，一些设备具有多核处理器的特性，其中不同的核同时在分组上并行操作。在一些处理器中，核可以执行多线程。线程可以进一步屏蔽某些操作的等待时间，比如存储器存取。例如，在一个线程发出存储器读取之后，可以执行不同的线程，同时第一线程等待被检索的数据。

广泛的软件体系结构可以被用于处理分组。例如，图1A图示了采样分组处理体系结构，其中通过线程102来处理分组104。线程102可以具有系列分组处理阶段的特性，比如解封包阶段，分组分类阶段，计量阶段，排队阶段等等。通过使用相同的线程对分组执行操作，有关分组的数据可以被快速的保留在可存取的局部存储器中。

尽管不同的线程可以对不同的分组进行操作，但线程仍然需要共享对相同数据的存取。例如，不同的分组可能属于相同的分组流(例如，异步传输模式(ATM)电路或传输控制协议/网际协议(TCP/IP)连接)。因此，不同的线程可以竞争存取以更新有关数据流(例如，接收的分组流数)。为协调存取该共享的数据，线程可以具有通过每个线程执行的指令(阴影部分)的一个或多个临界区的特性。通过防止多于一个的线程在一个时间上执行临界区的共享数据的存取操作，临界区保护共享的数据。例如，临界区可以使用在它能继续临界区执行之前线程获得的一个锁定(例如，相互排斥(互斥))。在获得锁定之后，线程能读取、修改、和把共享数据写回到存储器。线程接着可以解除该锁定以允许其他的线程访问。

尽管确保了共享数据中的相干性，如上所述，基于进入临界区，实现临界区的线程要经历一个延迟，等待通过线程102执行的共享数据的初始存储器读取的完成。例如，如图1A所示，在进入临界区之后，线程102发出一个读取以存取由不同线程共享的数据。由于有关存储器操作的等待时间，线程102会等待用于完成存取的相当长的时间周期。在“锁定步骤”实现过程中，其中每个线程必须在固定的时间周期内完成每个临界区，存储器存取会用少量时间留下线程102以便在读取完成之后对共享数据执行操作。

如图1B所示，为避免有关共享数据的初始临界区读取的等待时间，在线程102执行到达临界区之前，线程102可以发出存储器读取操作以启动对来自存储器的共享数据的存储器读取(标记的MR)。在所示例子中，共享数据的检索值具有任意的标记值“a”。如图所示，通过使用检索的复制，在进入临界区之后，线程102可以避免启动存储器存取等待时间，实质上是把等待时间移到更便利的时间。

然而，使用图1B的共享数据的复制，假设在线程102的读取和线程102的进入之间的时间周期中共享数据没有被改变成临界区。如图1C所示，为在此情况下保留共享数据中的相干性，核执行线程102可以从另一个核接收一个或多个消息，该另一个核表示对共享数据作出改变的其它核上的一个或多个线程。更新的值(任意标记的“Δ”)可以完全地替代由线程102作出的“早期的”复制或只更新少量的数据元素。如图所示，通过使用更新的值替代复制(“a”)，线程102能保留数据相干性，同时仍然避免临界区内部的高成本的读取操作。也就是说，线程102使用通过预临界区读取获得的数据和/或包括在更新消息中的数据。在两种情况下，存储器读取以检索共享数据不需要基于进入临界区。

概括的说，在缺少更新消息的情况下(图1B)，线程102可以安全地假设在到达临界区之前从存储器复制的值(“a”)可以被使用。然而，当更新消息表示对共享数据的改变时(图1C)，线程102使用更新的数据(“Δ”)替代较早从存储器复制的数据。

图2A-2B说明了在为多线程多核环境设计的软件体系结构中，该技术的使用。如图2A所示，在该体系结构中，通过各自的线程102a-102i来处理每个分组104a-104i。在所示的例子中，每个线程102a-102i具有多个临界期(critical stage)的特点(任意标记的X，Y和Z)。通过不同的线程102a-102进入的每个临界期由一个信令方案控制。就是说，在进入那个临界区之前，每个线程等待来自完成给定的临界区的先前的线程的信号。例如，在执行临界区Y之前，线程102d等待来自线程102c的信号。当线程102c完成临界区Y时，线程102c把该信号(图2A中线程102c和102d之间的实箭头)提供给线程102d。同样的，线程102e在进入给定的临界区之前等待来自线程102d的信号，线程102f等待来自线程102e的信号，等等。允许进入给定临界区的每个线程发送的信号链生成进入临界区的线程102a-102i的序列。如图所示，线程序列横跨多个核，每个核提供一些线程集。序列可以“回绕”(未示出)。也就是说，线程102i可以发信号给线程102a以便进入给定的临界区来用于下一个分组。

如图2A所示，除了信令序列中的下一个线程以进入完成的临界区外，线程还可以发出允许预临界区读取的一个信号。例如，如图所示，线程102c不仅发出信号给线程102d，允许线程102d进入临界区Y，线程102c还发出信号(线程102c和102g之间所示的虚线)给核100c，允许核100c上的线程102d-102f启动由临界区Y保护的共享数据的预临界区读取(标记的MR(Y))。如图所示，触发预临界区读取的信号在线程序列中跳跃由中间的核100b提供的线程102d-102f的集。

如图所示，可以通过在先前临界区的末端上执行的一个或多个指令来提供预临界区读取(例如，在临界区X的末端上出现的MR(Y))。这样，随着线程102d进入临界区Y，线程102g可以启动将在线程102g进入临界区Y之前完成的预临界区读取(MR(Y))。

如图2B所示，最后，通过线程102d，102e，和102f顺序地执行临界区Y之后，核100c上的线程120g从线程102f接收允许进入临界区Y的信号。再次的，由于从线程102c早先接收的信号，在线程102g进入临界区Y之前，线程102g已经把用于临界区Y的共享数据复制在局部核100c存储器中。然而，潜在地，在线程102g的预临界区读取之后/期间，插入执行临界区Y的线程102d-102f的任何线程可能已经更改了共享的数据。因此，如图所示，线程102d-102f可以写入表示对共享数据改变(标记的“Δ”)的消息给执行线程102g的核100c，线程102g执行预临界区读取。表示数据更新的消息可以包括流识别符和可变值的序列，并且潜在地，字段识别符表示哪个数据值已经被改变。流识别符可以由首部数据的元组(例如，IP源和目标地址以及传送层源和目标端口)形成。如果该消息被发送，线程102g可以使用更新的数据替代在预临界区读取中获得的数据。在两种情况下，可以避免临界区内读取共享数据有关存储器操作的等待时间。

图2A-2B处于方便示例简化了实施的一些方面。例如，图2A示例了允许进入临界区的单一的信号和允许预临界区读取的单一的信号。在操作中，线程102c在如此配置的每个临界区(例如，X，Y，Z)的完成上可以发出两种类型的信号。此外，线程102f和102i(和其他的核线程)可以类似的提供这样的信号给线程序列中下游的线程/核。另外，这些信号也可以“回绕”。例如，在线程102f完成临界区X之后，线程102f可以发信号给线程102a以便对下一个分组执行用于临界区“X”的预临界区读取。

尽管图2A-2B示例了提供三个线程的核，但核可以提供更多或更少的线程(例如8或16)。同样的，处理器典型地包括多于三个的核(例如，8或16)。此外，尽管图2A-2B示例了单一线程处理的给定的分组，但可以通过多于一个的线程来处理分组。例如，第一核可以执行用于分组的第一操作集并传送分组到第二核以用于下一个操作集。

可以在广泛的硬件环境中实现该技术。例如，图3图示了网络处理器200的例子。所示的网络处理器200是

因特网交换网络处理器(IXP)。其他的网络处理器具有不同的设计特性。

所示的网络处理器200特点在于，在单一集成半导体片上汇集处理核202。每个核202可以是用于分组处理所设计的精简指令集计算(RISC)处理器。例如，核202可以不提供一般由通用处理器的指令集所提供的浮点或整除指令。各自的核202可以提供执行的多个线程。例如，核202可以存储用于不同线程的多个程序计数器和其他的上下文数据。

如图所示，网络处理器200还具有的特性是，至少一个接口202能携带处理器200和其它网络部件之间的分组。例如，处理器200可以具有开关结构接口202(例如，公共交换接口(CSIX))，能够使处理器200发送分组到连接到该结构的其它处理器或电路系统。处理器200也可以具有接口202(例如，系统分组接口(SPI))，能够使处理器200与物理层(PHY)和/或链路层设备通信(例如，MAC或成帧器设备)。处理器200还包括例如用于与主机或其他网络处理器通信的接口208(例如外部设备互连(PCI)总线接口)。

如图所示，处理器200还包括通过核202共享的其它部件，比如散列核，通过核共享的内部便笺式存储器，和存储控制器206、212，该存储控制器206、212提供对所述核共享的外部存储器的存取。网络处理器200还包括附加的处理器210(例如，

)，该附加的处理器210通常被编程来执行包括在网络操作中的“控制面板”任务。然而，核处理器210也可以处理“数据面(data plane)”任务。

核202经核210或其他的共享资源可以与其他的核202通信。核202也可以经相邻的寄存器互通，寄存器起到直接有线连接到相邻的核202的作用。下一个相邻的寄存器可以被用作相邻核之间的先入先出(FIFO)队列。可替换的，核202可以与非相邻的核通信，例如，经过移动核的传送寄存器之间的数据的控制和状态寄存器代理反射操作。

除了给定数量的局部核202RAM之外，各个核202可以具有多种局部存储器元素。例如，每个核202可以包括传送寄存器，该传送寄存器缓冲从核202外部的目标中读取/写入到核202外部的目标中的数据(例如，存储器或另一个核)。附加地，每个核可以具有发送到其它元素的排队命令的命令FIFO队列。除了传送寄存器之外，各个核202还可以具有其它的局部核存储器，比如内容可寻址的存储器(CAM)。

网络处理器的特性可以被用于实现上述的技术，例如，核的CAM可以被用于确定是否共享的数据已经被更新。例如，CAM可以存储共享数据的ID(例如，分组流和，潜在的，字段识别符)和指出共享数据当前被存储的位置(例如，在一个或多个传送寄存器或局部核RAM中)。当一个核接收共享数据更新消息时，核上执行的线程可以相对于当前存储在CAM中的流ID来比较消息的流ID。匹配表明更新消息对应于预临界区读取所获得的共享数据并且线程可以相应的把更新的值写入到局部RAM中，并且在预定的存储器位置中设置相应的“脏(dirty)”位，该“脏”位表明在局部核存储器中使用该值来代替传送寄存器。当进入临界区时，线程可以检查相关的“脏”位以确定哪个数据被使用。在CAM“失误”的事件中，当不需要更新的数据时核可以忽略更新消息。

潜在地，CAM可以被逻辑的划分成段以识别不同的临界区的共享数据。例如，CAM的第一集入口可以被用于存储用于所执行的临界区的共享数据ID，同时CAM的下一集入口被用于存储跟着的临界区的共享数据ID。例如，临界区识别符可以预先考虑存储在CAM中的流的标识密钥或固定数的入口(例如1-8)可以被分配给该部分。在该实施中，核的第一线程开始临界区之前(例如，临界区X)，线程还清除有关下一个临界区(例如Y)的CAM段以便开始着手Y的预临界区读取可以被存储在CAM分段中。

为了示例上述技术的应用，将使用图3所示的网络处理器体系结构的特性来重述图2A-2B。在该实施例中，当核100a的最后线程102c退出临界区Y时，如果需要的话，线程102c通过下一个到核100b的相邻寄存器连同使核100b线程进入临界区Y的下一个相邻信号，来发送共享数据ID和更新临界区Y的核100a执行所影响的共享数据。在命令把共享数据写到外部存储器之后，通过把命令置于核100a命令FIFO中，核100a也朝着核100c中的线程102g发送信号。由于在命令FIFO中顺序的处理命令，当信号到达核100c时，保证由执行临界区Y的核100a修改的数据的回写朝着它的目的地移动。当接收该信号时，核100c中的线程被允许启动用于临界区Y的存储器读取(例如，到SRAM或DRAM)并在核100c的传送寄存器中存储共享的数据。通过存储相应的共享数据ID的CAM入口和传送寄存器中的共享数据的拷贝的位置可以跟踪预临界区读取的结果。

核100c线程继续执行，直至到达临界区Y为止。当核100c线程到达临界区Y时，线程检查来自核100b的信号，该信号通知更新的数据消息已经被排队在核100c的下一个相邻寄存器中。如果信号是可用的，线程使用来自下一个相邻寄存器的共享数据ID以便进行CAM搜索。如果ID匹配CAM入口，从存储器读取进入核传送寄存器的预临界区数据被废弃并需要用核100c的下一个相邻寄存器中的包括在当前的更新消息中的数据来更新。在这点上，用于CAM入口的脏位可以被设置并更新存储在局部核存储器中的数据。下一个相邻寄存器中的入队到核100c的所有更新消息(例如，(共享数据ID，var)配对)已经被处理之后，核100c上的线程可以依次进入临界区Y。线程可以访问脏位(dirty bit)以确定是否从传送寄存器或局部核存储器来存取共享的数据。

如上所述，临界区的顺序可以“回绕”。例如，线程102a执行的临界区X跟随线程102i执行的临界区X。为提供这样的回绕信令，CAP可以被用于写信号和对没有通过下一个相邻电路系统直接连接的核更新消息。

图4图示了使用上述技术处理分组的网络设备。如图所示，设备特性在于，汇集通过交换结构310(例如，横臂或共享存储器交换结构)互连的线路卡300(“刀形开关”)。该交换结构例如可以符合CSIX或其他的结构技术，比如超文本传送，Infiniband，PCI，Packet-Over-SONET，RapidIO，和/或UTOPIA(用于ATM的通用测试和操作PHY接口)。

各个线路卡(例如300a)可以包括处理网络连接上的通信的一个或多个物理层(PHY)设备302(例如光学，有线，和无线的PHY)。PHY在不同网络媒体携带的物理信号和数字系统所使用的比特(例如，“0”-s和“1”-s)之间翻译。线路卡300还可以包括成帧器设备(例如，以太网，同步光学网络(SONET)，高级数据链接(HDLC)成帧器或其他的“层2”设备)304，可以对帧执行操作，比如纠错和/或校正。所示的线路卡300还可以包括一个或多个网络处理器306，执行用于经PHY302接收的分组的分组处理操作，和经交换结构310把分组直接送到提供出口接口的线路卡以便转送该分组，潜在地，网络处理器306可以执行“层2”的任务来代替成帧器设备304。

尽管图3和4描述了网络处理器以及结合网络处理器的设备的特定例子，但该技术可以实现于包括网络处理器，通用处理器(例如中央处理单元(CPU))的各类结构体系中，以及不同于所示设计的网络设备。此外，该技术可以被广泛的用于各类网络设备(例如，路由器，开关，桥路，集线器，业务产生器，等等)。术语分组可以应用于IP(网际协议)数据报，TCP(传输控制协议)片段，ATM(异步传输模式)单元，以太网帧，连同其他的协议数据单元。

在此所使用的电路系统包括硬件电路系统，数字电路，模拟电路，可编程的电路系统等等。可编程电路系统可以运行在计算机程序上，比如在制造的产品上(比如只读存储器或其他的存储媒体)所包括的指令。

其他的实施例也都在下面权利要求书的范围之内。

Claims

1.一种方法，包括：

2.权利要求1的方法，其中对分组处理线程之间共享的数据执行存储器读取包括，在接收了通过允许存储器读取的第三核上执行的第三处理线程发出的信号之后，执行该存储器读取。

3.权利要求1的方法，

进一步包括，发送一个或多个消息到第一核，通过另一个核上执行的线程识别共享数据的改变。

4.权利要求1的方法，

其中所述确定包括，确定是否第一线程接收了识别对共享数据的至少一个更新的一个或多个消息。

5.权利要求4的方法，

其中一个或多个消息包括经执行第一线程的处理器核和另一个处理器核之间的直接连接所接收的一个或多个消息。

6.权利要求1的方法，

其中所述确定包括，基于有关分组处理线程所处理的分组的识别符来执行查找。

7.一种具有多个多线程可编程核的系统，包括：

单一电路片上集成的多个多线程可编程核；

逻辑为：

执行第一临界区；和

从第一核接收第一信号；

如果数据没有被改变，使用临界区中检索的数据；

如果数据被改变，使用临界区中改变的数据。

8.权利要求7的系统，

其中经第二核和第三核之间的直接连接从第二核到第三核发送一个或多个消息。

9.权利要求7的系统，

其中确定是否通过分组共享的数据已经被改变包括，基于有关一个分组的识别符来执行查找。

10.权利要求9的系统，其中查找包括内容可寻址存储器(CAM)搜索。

11.权利要求10的系统，其中CAM被逻辑地分段成有关线程所执行的不同临界区的入口集。