具有指令链接能力的多线程处理器中的机会多线程

摘要

计算装置确定具有发布序列的多个软件线程中的当前软件线程没有在一个时钟周期期间等待被发布给硬件线程的第一指令。所述计算装置识别所述发布序列中的具有等待被发布的指令的一个或多个替代软件线程。所述计算装置在所述时钟周期期间鉴于确定来自所述一个或多个替代软件线程当中的第二软件线程的第二指令与等待被发布的指令当中的任何其它指令没有相依性来选择所述第二指令。相依性鉴于从每个等待被发布的指令提取的链接比特的值而被识别。所述计算装置将第二指令发布给硬件线程。

说明书

对相关申请的交叉引用

本申请要求2014年11月12日提交的美国实用新型专利申请No.14/539116的优先权，该美国实用新型专利申请要求2014年2月6日提交的美国临时专利申请61/936428和2014年3月25日提交的美国临时专利申请No.61/969862的优先权，这些专利申请的全部公开内容通过引用并入本文。

技术领域

本公开的实施例涉及一种用于在微处理器环境中处理指令的方法和装置。更具体地说，实施例涉及用于微处理器的多线程处理，即，当在特定时钟周期期间微处理器确定目标硬件线程为空或没有有效指令要发布时，微处理器可以在该特定时钟周期期间发布被分配给其它硬件线程的指令。

背景技术

多线程并行处理技术已经被用在高性能处理器中，以减少由长流水线引起的高速处理器指令执行延迟的影响。相比于其它处理器设计，多线程并行处理技术提高了每周期指令的性能和效率。通用处理器中最常见类型的多线程是同时多线程技术(SMT)。SMT已经被用在Intel的Hyper-Threading(“Intel Hyper-Threading Technology,TechnicalUser’s Guide”中所述)、IBM的POWER5(如Clabes,Joachim等人的“Design andImplementation of POWER5Microprocessor”,Proceedings of 2004IEEE国际固态电路会议论文集中所述)、Sun Microsystem的Ultra SPARC T2(如检索2008-01-09得到的“Usingthe Cryptographic Accelerators in the UltraSPARC T1and T2Processor”,SunBluePrints Online,Sun Microsystems中所述)、以及MIPS MT(如检索2014年1月4日得到的“MIPS32Architecture”,Imagination Technologies中所述)中。

典型的基于SMT的处理器已经要求每个硬件线程在基于SMT的处理器内的流水线的每个级具有它自己的一组寄存器和附加的跟踪逻辑。这增大了硬件资源的尺寸，尤其是实现基于SMT的处理器的设计所需的线程跟踪逻辑。基于SMT的处理器所利用的线程跟踪逻辑不仅被要求跟踪硬件线程的执行，而且被要求确定该硬件线程是否已经完成了执行。因为基于SMT的处理器可以利用大量的主动执行的硬件线程，所以CPU高速缓存和相关联的转译后备缓冲器(translation look-aside buffer，TLB)的尺寸需要足够大以避免硬件线程颠簸。

尽管SMT技术可以改善单线程的性能，但是上述控制电路复杂度使得难以将SMT技术应用于需要低功耗的嵌入式处理器。

为了克服SMT控制电路复杂度并且降低功耗，已经开发了其它形式的多线程技术。块多线程(block multithreading)和交错多线程(interleaved multithreading)已经被提出。不幸的是，块多线程技术已被限于微控制器和其它低性能处理器。交错多线程技术简化了控制电路，但是当在处理器中存在比可用的硬件线程少的软件线程时，性能有损失。该技术已经在某些高性能低功率处理器中被提倡。美国专利No.6842848中描述了令牌触发的多线程技术的代表性示例。

令牌触发的多线程利用分时(time sharing)。执行的每个软件线程被处理器准许根据它自己的被分配的时钟周期来执行。每个时钟周期只有一个软件线程被准许发布命令。令牌被用于向软件线程通知该软件线程在下一个时钟周期内是否应发布指令。这进一步简化了硬件线程逻辑。在所有软件线程都已经发布了指令以前，没有软件线程可以发布第二指令。如果软件线程没有指令可用于发布，则由硬件线程发布空操作(NOP)。处理器硬件确保每个软件线程具有相同的指令执行时间。操作的结果可以在指定的保证时间段(例如，时钟周期)内完成。因此，在处理器设计中不需要与指令执行相关的检查和旁通硬件。

令牌触发的多线程技术简化了多线程处理器的硬件发布逻辑，因此，可以以非常小的功耗实现高性能。然而，与SMT技术相比，如果在一个时钟周期期间具有可执行指令的软件线程少于可用的硬件线程，则令牌触发的多线程处理器的性能提升是有限的。在这种情况下，未被分配软件线程的硬件线程必须发布NOP。

此外，为了避免软件线程之间的干扰以及简化硬件结构，常规的令牌触发的多线程利用可以使得每个周期执行少量指令的分时策略。这降低了单线程操作的处理速度。例如，如果用于上下文T₁的软件指令不在高速缓存中而是需要从外部存储器重新加载，则由于外部存储器的低速度，T₁必须等待许多个周期来重新加载指令。如果上下文T₀具有准备好的指令，则它仍必须等到在时钟周期C₁发布该指令。然而，因为分时数据路径的结构限制，时钟周期C₁仅可以被上下文T₁使用，在这种情况下，硬件线程必须发布NOP。

在执行的单个软件线程的最坏情况下，对应的常规的令牌触发的处理器的性能为1/T(其中，T为硬件线程的数量)。在以1GHz运行的10线程的令牌触发的处理器中，该处理器的性能实际上降至100MHz。

为了避免颠簸并且简化硬件线程之间的跟踪电路，在Sandblaster 2.0处理器中，每个硬件线程具有它自己的单独的指令存储器，就如2008年10月在华盛顿特区举行的Software Defined Radio技术论坛(SDR论坛08)的会议录“The Sandblaster2.0Architecture and SB3500Implementation”中所述。不幸的是，各个指令存储器不能在硬件线程之间被共享。当软件线程的数量少于硬件线程的数量时，除了性能降低之外，这还可能导致存储器资源未充分利用。

发明内容

通过提供用于具有指令链接能力的多线程处理器中的机会多线程的方法和设备，在本领域中解决了上面所述的问题并且实现了技术方案。描述了用于被链接在一起的处理器指令序列的指令发布的示例。与特定硬件线程相关联的被链接的指令具有二维寄存器阵列，该二维寄存器阵列存储软件线程的线程标识号(ID)以及识别所发布的指令的值。这些ID可以分开存储。因此，当目标硬件线程为空或没有可以发布的有效指令时，多线程处理器的每个硬件线程可以在被分配给其它硬件线程的任何时钟周期发布指令。这保证了：数据和架构状态不会变得毁坏，也不会使处理结果混杂。指令预验证逻辑可以被用来预先检测下一个时钟周期内的当前软件线程指令发布位置和下一个软件线程指令发布位置。

通过提供表现出具有指令链接能力的机会多线程的计算装置，在本领域中解决了上面所述的问题并且实现了技术方案。该计算装置确定具有发布序列的多个软件线程中的当前软件线程在一个时钟周期期间没有等待被发布给硬件线程的第一指令。该计算装置识别出发布序列中的具有等待被发布的指令的一个或多个替代软件线程。该计算装置在所述时钟周期期间鉴于确定来自所述一个或多个替代软件线程当中的第二软件线程的第二指令与等待被发布的指令当中的任何其它指令没有相依性来选择该第二指令。相依性由所述计算装置鉴于从每个等待被发布的指令提取的链接比特的值来识别。所述计算装置将第二指令发布给硬件线程。

为了确定第二指令与等待被发布的指令当中的任何其它指令没有相依性，所述计算装置将等待被发布的指令当中的第一指令和其它指令分组到一个指令组中。所述计算装置从该指令组中的每个指令提取指定比特以生成链接比特序列。所述计算装置对该链接比特序列进行解码。所述计算装置鉴于解码的链接比特序列来识别指令组当中的零个或更多个指令相依性。所述计算装置确定第二指令与所述零个或更多个指令流相依性中的零个相依性(zero dependencies)相关联。

在示例中，链接比特序列是在不对指令组中的任何指令进行解码的情况下被解码的。

在示例中，指令组内的两个或更多个指令之间被识别的相依性是控制相依性或数据相依性。

在示例中，所述计算装置可以对指令组当中的具有零个或更多个相依性的每个指令中的指定比特进行编码以生成链接比特序列。

在示例中，所述计算装置可以将第一索引分配给与所述序列中的第二软件线程的位置对应的硬件线程。所述计算装置可以将第二索引分配给与时钟周期对应的硬件线程。所述计算装置可以利用第一索引和第二索引来识别第二指令最初从其发布的第二软件线程。响应于确定当前软件线程在所述时钟周期期间具有等待被发布给硬件线程的第一指令，所述计算装置可以将第一指令发布给硬件线程。

在另一个示例中，所述计算装置可以将第一索引分配给与发布序列中的当前软件线程的位置对应的硬件线程。所述计算装置可以将第二索引分配给与所述时钟周期对应的硬件线程。所述计算装置可以利用第一索引和第二索引来识别第一指令最初从其发布的当前软件线程。

在示例中，发布序列可以首先是令牌触发的多线程序列。

在示例中，所述多个软件线程中的软件线程的数量可以少于可用的硬件线程单元的数量。

附图说明

根据结合附图考虑的、对以下呈现的示例的详细描述，本发明可以被更容易地理解。在附图中，相似的标号指代类似的要素。

图1示出了其中本公开的示例可以工作的多线程处理器内的硬件线程单元的一个示例，该示例最小化当可执行软件线程少于可用的硬件线程单元时的未使用的时钟周期。

图2示出了两个独立的指令的示例，每个指令均具有为链接信息保留的对应比特。

图3示出了用于双发布流水线型的处理器的一组指令链接语义的一个示例。

图4示出了用于三发布处理器中的指令链接的语义的一个示例。

图5示出了用于四发布处理器的一组指令链接语义的一个示例。

图6示出了其中本公开的示例可以工作的用于从指令组中的指令提取链接比特、对所提取的链接比特进行解码并且产生流水线控制信号的指令相依性预测电路。

图7是例示了用于使得相依性信息、并行性信息和性能优化能够被编码在指令序列中的方法示例的流程图。

图8是例示了用于使得相依性信息、并行性信息和性能优化能够在不检查被编码在指令序列中的底层指令的情况下被解码的方法的示例的流程图。

图9是例示了用于最小化当软件线程少于硬件线程单元时多线程处理器中的未使用的时钟周期的方法示例的流程图。

图10是例示了用于确定图9的第二指令与等待被发布的指令当中的任何其它指令是否不具有相依性的方法示例的流程图。

图11示出了四线程的机会多线程流水线操作控制处理时序图，其中C_i是时钟周期标识符，T_ij是被分配给时钟周期C_i的对应的分配线程标识符。

要理解附图是为了例示本发明的构思的目的，并且可能不是按比例绘制的。

具体实施方式

本公开的示例描述了多线程计算机处理器以及操作该多线程计算机处理器的方法，该多线程计算机处理器最小化当软件线程少于硬件线程单元时该多线程处理器中的未使用的时钟周期。当被分配的硬件线程单元必须发布NOP时，未使用的时钟周期可能出现。本公开的示例提供了可以在不像令牌触发的多线程的情况那样要求所有在前的硬件线程单元都首先发布NOP的情况下将等待的指令发布给多个硬件线程单元的方法和多线程计算机处理器。被称为“机会多线程”的方法通过提供二维的标识寄存器阵列将软件线程与若干个硬件线程单元相关联来控制指令发布序列。在每个流水线级中，线程标识符(ID)可以被用于标识指令最初从其发布的软件线程。该信息可以被存储在流水线寄存器中，并且可以在每个流水线级被用于识别并跟踪多线程指令的执行状态。这消除了多个软件线程和由同一硬件线程在不同流水线中发布的指令之间的歧义。

图1示出了其中本公开的示例可以工作的多线程处理器100的硬件线程单元的一个示例，该示例最小化当可执行的软件线程少于可用的硬件线程单元时的未使用的时钟周期。在示例中，多线程处理器100可以包括多个硬件线程单元102a-102n。硬件线程单元102a-102n中的每个均可以包括至少一个指令存储器(I-Cache)104、程序计数器(PC)105、指令解码器(I-decoder)106、程序分支控制器(Branch)108(下文中称为“指令发布控制器108”)、一个或多个算术逻辑单元(ALU)110、数据存储器112、以及到(主随机存取)存储器(未示出)的接口总线114。多线程处理器100可以进一步设有一组二维线程标识(ID)寄存器116或两个独立的线程标识寄存器116以及指令有效性预测逻辑118。硬件线程单元102a-102n中的每个均可以设有程序实现所需的一组执行程序寄存器(未示出)。

在一个示例中，指令“组”可以分别从指令存储器(I-Cache)104读取并且被指令解码器(I-decoder)106解码。经解码的信息可以被用于产生退出指令发布控制器108的控制信号，其中指令发布控制器108控制数据路径和流水线的操作。直接寄存器引用可以被发送到寄存器文件(标记的寄存器109)，寄存器文件109内所包含的数据可以被发送到一个或多个算术逻辑单元(ALU)110(在示例中，ALU 110可以包括指令流水线和执行单元(未示出))。存储在数据存储器112中的操作的结果可以被写回到寄存器文件109。程序计数器(PC)105可以被更新，下一个指令可以从指令存储器(I-Cache)104提取。

在一个示例中，多线程处理器110可以设有指令有效性预测逻辑118。指令有效性预测逻辑118可以被配置为确定在一个时钟周期期间发布序列中准备发布的指令之间是否存在任何相依性。由指令有效性预测逻辑118提供的相依性信息可以被编码并以“链接比特”的形式输出，链接比特用于提前确定当前软件线程和任何附加的软件线程是否具有可以在下一个时钟周期内被发布的有效指令。在示例中，如果下一个硬件线程单元(例如，102a)在下一个周期内没有有效的可执行指令，但是当前硬件线程单元(例如，102b)具有正在等待的可以发布的指令，则指令有效性预测逻辑118的逻辑可以允许当前硬件线程在下一个时钟周期内发布指令。

本领域技术人员将意识到，在一个示例中，多线程处理器100的元件104-118中的一个或多个可以在硬件线程单元102a-102n间共享。例如，当元件104-118中的一个或多个(例如，一个或多个算术逻辑单元(ALU)110、指令存储器(I-Cache)104、数据存储器112等)不表示处理器状态时，元件104-118中的所述一个或多个可以在硬件线程单元102a-102n间共享。相反，在示例中，元件104-118中的表示处理器状态的任何元件需要针对硬件线程单元102a-102n中的每个硬件线程单元而被复制。

指令链接利用每个指令一个比特(下文中称为“链接比特”)来指示处理器指令序列中的并行性和指令间相依性这两者。如本文中所使用的，指令是指具有操作及操作数词组的可独立寻址单元(参见Gerrit A.Blaaw和Frederick P.Brooks,Jr.的“ComputerArchitecture:Concepts and Evolution”，Addison Wesley，第一版，1997年2月，第128页)。多个指令可以被分组在一起，以形成可以一起提取的指令组。在运行时，处理器重新组装来自指令组中的指令的链接比特，以在不必对各个指令进行解码的情况下高效地解码指令流内的相依性和并行性。该信息可以被用于产生用于指令发布的必要的流水线控制信号，消除了流水线型处理器架构中对复杂的指令间相依性检查硬件或NOP指令的需要。该过程可以与对程序员不可见的流水线效应(诸如长期负荷流水线停顿、分支分解以及其它长延时操作)共存。因为每个指令是可独立寻址的，所以跳转到指令组的中间可以被允许。然而，当跳转到指令组的中间时，整个组的相依性比特需要被重构以便链接比特解码。如果编译器对指令相依性进行分析并且产生链接比特，则程序员实际上看不见任何流水线效应，并且可以不顾及危险地对机器进行编程。

虽然可以定义与不同处理器实现兼容的一组链接比特，但是对于大多数实现，链接比特可以是实现相关的：它们的语义仅可以在它们被针对编程的处理器上被解释。在示例中，单发布流水线型处理器可以具有一个链接比特的仅两种解释。“0”值表示不链接，“1”值表示指令可以与下一个指令链接。因此，在单发布流水线型处理器中，链接比特可以仅指示指令是否是独立的以及有无危险。在另一个示例中，链接比特的逻辑可以反过来将“0”解释为表示链接，将“1”解释为表示不链接。

单发布流水线型处理器中的指令链接

链接的最简单情况是如果不存在指令间相依性则可以每个时钟周期发布一个指令的单发布流水线型处理器。图2示出了两个独立的指令202、204的示例200，指令202、204各自具有为链接信息保留的对应比特206、208。因为加法指令204是独立的并且可以被并行地执行，所以乘法指令202的链接比特206被设置为1。基于特定处理器的能力，可以将任何数量的比特链接在一起。

在示例中，对于典型的流水线型处理器，如果存在指令间相依性，则流水线必须停顿，直到相依性被分解为止。如果链接比特被设置为“1”，则这是下一个指令与当前指令链内的任何指令没有控制相依性或数据相依性的指示。因此，指令可以被立即发布。如果链接比特被设置为“0”，则这是下一个指令与当前指令链内的至少一个指令具有控制相依性和/或数据相依性的指示。因此，在当前链内的所有指令完成执行并退出流水线以前，该指令的执行都不能开始。

双发布流水线型处理器中的指令链接

双发布流水线型处理器可以被配置为如果不存在指令相依性则每个周期发布两个指令(指令组)。如果在指令组之间存在相依性，则流水线停顿，直到相依性被分解为止。如果在指令组内存在相依性，则串行地发布该指令组内的指令，即，发布第一指令，并且在第一指令完成执行并退出流水线以前停顿第二指令。

指令组中的每个指令具有链接比特。因此，在双发布处理器中，每个指令组可用两个链接比特，因此，可以编码4种情形。在示例中，一个链接比特可以被用于指示垂直并行性(组间并行性)，而第二个链接比特可以被用于指示水平并行性(组内并行性)。

图3示出了用于双发布流水线型处理器的一组指令链接语义的一个示例。链接比特i1和i2可以分别取自指令组中的第一指令和第二指令。链接比特i1是组内并行性比特。如果组内并行性比特为1，则该组中的第二指令可以与该组中的第一指令并行发布。如果组内并行性比特为0，则该组中的第二指令必须等待，直到第一指令已经完成执行为止。链接比特i2是组间并行性比特。如果组间并行性比特为1，则下一个执行组可以在当前执行组之后在下一个时钟周期进入流水线。如果组间并行性比特为0，则下一个执行组必须等待，直到当前执行组已经完成执行为止。

三发布流水线型处理器中的指令链接

如果不存在指令相依性，则三发布流水线型处理器可以每个周期发布三个指令(指令组)。如果在指令组之间存在相依性，则流水线停顿，直到相依性被分解为止。如果在指令组内存在相依性，则该指令组内的指令如链接比特所指示的那样被串行地或部分并行地发布。指令组中的每个指令具有单个链接比特。因此，在三发布处理器中，每个指令组可用三个链接比特，从而得到8个语义组合。一个链接比特可以被用于指示垂直并行性(跨指令组)，而其它两个链接比特可以被用于指示水平并行性(在指令组内)。

图4示出了用于三发布处理器中的指令链接的语义的一个示例。用于图4中所指示的链接比特组合的指令链接的语义的示例提供了水平并行性中的最大灵活性。图4中的x的值指示链接比特可以为0或1。链接比特i1、i2和i3可以分别取自指令组中的第一指令、第二指令和第三个指令。链接比特i1和i2是组内并行性比特。如果i1或i2为1，则组中的下一个指令可以与组中的当前指令并行发布。如果i1或i2为0，则下一个指令必须等待，直到当前执行指令已经完成执行为止。链接比特i3是组间并行性比特。如果i3为1，则下一个执行组可以在当前执行组之后在下一个时钟周期中进入流水线。如果i3为0，则下一个执行组需要等待，直到当前执行组已经完成执行为止。

如果水平并行性中的完全灵活性不是必要的，则两个链接比特可能足以对垂直并行性和水平并行性(所有三个指令是否被一起发布)进行编码。第三个链接比特可以被用于对附加信息进行编码。

四发布流水线型处理器中的指令链接

如果不存在指令相依性，则四发布流水线型处理器每个周期发布4个指令。如果在指令组之间存在相依性，则流水线可以停顿，直到相依性被分解为止。如果在指令组内存在相依性，则指令组内的指令可以如链接比特所指示的那样被串行地或部分并行地发布。

指令组中的每个指令具有单个链接比特。因此，在四发布处理器中，每个指令组可用四个链接比特，从而得到16种语义组合。一个链接比特可以被用于指示垂直并行性(跨指令组)，其它三个链接比特可以被用于指示水平执行的其它可能性(执行指令组内的指令)。

图5示出了用于四发布处理器的一组指令链接语义的一个示例。图5中的x的值指示链接比特可以为0或1。链接比特i1、i2、i3、i4可以分别取自指令组中的第一指令、第二指令、第三个指令和第四个指令。链接比特i4是组间并行性比特。如果i4为1，则下一个执行组可以在当前执行组之后在下一个时钟周期中进入流水线。如果i4为0，则下一个执行组必须等待，直到当前执行组已经完成执行为止。链接比特i1、i2和i3可以被用于指示组内并行性。在示例中，链接比特i1、i2和i3的一些组合指示组中的指令内的可能的并行性(001x、010x、011x、100x)，其它组合指示组中的指令内的强制并行性(101x、110x、111x)。可能的并行性揭示了可用的并行性，但是处理器可以或者可以不使用它。不管指令是并行地还是顺序地被执行，结果都保持相同。强制并行性指示指令必须被并行地执行以获得期望的结果。

通过利用链接，相依性可以跨整个指令序列被编码。在图4的示例中，三发布机器可以利用三个链接比特(每个指令一个)来对8种可能的相依性类型进行编码。在此意义上，链接可以扩展到指令组。例如，从三个指令的链接比特解码的“000”可以被解释为当前组内的所有指令都不被链接并且下一个指令组可以不与当前指令组链接。

在一个示例中，在多发布处理器中，链接比特之一可以被保留用于组间并行性以指示当前指令组之后的下一个指令组是否包含与当前指令组的任何控制或数据相依性。如果不存在相依性，则下一个指令组可以在没有任何流水线停顿的情况下与当前指令组同时地沿着流水线向下发布。指令组内的其它链接比特可以描述组内并行性信息，该组内并行性信息指示当前指令组中的指令之间的并行性和相依性。

链接比特也可以对性能提升技术进行编码，诸如通知处理器使用旁通值，而不是再次从寄存器文件读取旁通值。在一些情况下，这可以降低处理器浪费的功率。

有利地，并行性和相依性这两者都可以跨整个指令组被编码。链接比特可以被用于对在执行期间帮助在流水线型处理器中快速地产生必要的流水线控制信号的指令间相依性、组间相依性和性能优化进行编码，由此消除对复杂的相依性检查硬件的需求。

返回到图1，在一个示例中，指令有效性预测逻辑118可以被配置为确定：在一个时钟周期期间，具有发布序列的多个软件线程中的当前软件线程没有等待被发布给硬件线程单元的第一指令。指令有效性预测逻辑118可以被配置为识别发布序列中具有等待被发布的指令的一个或多个替代软件线程。指令有效性预测逻辑118可以被配置为在所述时钟周期期间鉴于确定来自所述一个或多个替代软件线程当中的第二软件线程的第二指令与等待被发布的指令当中的任何其它指令没有相依性来选择该第二指令。可以鉴于从每个等待被发布的指令提取的链接比特的值来识别相依性。指令发布控制器108可以被配置为将第二指令发布给硬件线程单元。

在示例中，为了确定第二指令与等待被发布的指令当中的任何其它指令没有相依性，指令有效性预测逻辑118可以将第一指令和等待被发布的指令当中的其它指令分组到指令组中。指令有效性预测逻辑118可以从该指令组的每个指令提取指定比特以生成链接比特序列。指令有效性预测逻辑118可以对该链接比特序列进行解码。链接比特序列可以在不对指令组中的任何指令进行解码的情况下被解码。指令有效性预测逻辑118可以鉴于经解码的链接比特序列来识别指令组当中的零个或更多个指令相依性。在示例中，指令组内的两个或更多个指令之间的任何识别出的相依性可以是控制相依性或数据相依性。指令有效性预测逻辑118然后可以确定第二指令与零个或更多个指令流相依性中的零个相依性相关联。

在一个示例中，多线程处理器100可以进一步设有一组二维的线程标识(ID)寄存器116或两个独立的线程标识寄存器116(下文中称为“线程ID寄存器116”)。可以使得该信息在每个流水线级是可用的。多线程处理器100可以利用线程ID寄存器116来在每个流水线级跟踪多个软件线程的指令执行以确保指令被适当地重新组装并且状态被分配给该指令所属的原始软件线程。

在示例中，不再要求每个软件线程的指令发布周期是固定的，并且如果有效指令可用于从任何软件线程发布，则不要求硬件线程单元发布NOP。

如果特定硬件线程单元(例如，102a)中的指令经历了高速缓存缺失，则高速缓存缺失不阻止其它指令在被分配给经历了高速缓存缺失的该硬件线程单元的时钟周期上发布。每个指令，不管它是在哪个时钟周期内被发布的，都携带唯一线程标识符(ID)，该ID允许该指令与该指令起源的原始软件线程相关联。

如果存在等待在下一个时钟周期内发布的有效指令，则硬件线程单元(例如，102a)可以从分配给该硬件线程单元(例如，102a)的软件线程发布指令。如果不存在等待的指令，则发布逻辑可以分配来自当前软件线程的指令。

因为存在每个软件线程可以在线程周期期间多次发布指令的机会，所以线程ID寄存器116被提供用于跟踪和识别在不同时钟周期发布的软件线程和指令。

在一个示例中，指令发布控制器108可以被配置为将第一索引分配给与所述序列中的第二软件线程的位置对应的硬件线程单元。指令发布控制器108可以被配置为将第二索引分配给与时钟周期对应的硬件线程单元。指令发布控制器108可以被配置为利用第一索引和第二索引来识别第二软件线程，其中第二指令最初发布自第二软件线程。在一个示例中，响应于指令发布控制器108确定当前软件线程在所述时钟周期期间具有等待被发布给硬件线程单元的第一指令，指令发布控制器108可以将第一指令发布给硬件线程单元。

在另一个示例中，指令发布控制器108可以被配置为将第一索引分配给与发布序列中的当前软件线程的位置对应的硬件线程单元。指令发布控制器108可以被配置为将第二索引分配给与所述时钟周期对应的硬件线程单元。在一个示例中，指令发布控制器108可以利用第一索引和第二索引来识别当前软件线程，其中第一指令最初发布自当前软件线程。

图6示出了指令相依性预测电路118的一个示例。指令相依性预测电路118可以包括指令准备发布逻辑603、链接比特编码器605以及链接比特解码器608。指令准备发布逻辑603可以被配置为识别具有发布序列(例如，循环的令牌触发的线程序列)的软件线程序列中的每个软件线程在特定时钟周期期间是否具有等待被发布的指令。准备发布逻辑603可以被进一步配置为将等待发布的指令集合分组到指令组(下称为“指令组606”)中。

链接比特编码器605可以被配置为从指令准备发布逻辑603识别的指令流601接收指令组606。链接比特编码器605可以被配置为识别接收的指令组606当中的零个或更多个指令流相依性。链接比特编码器605可以被配置为对所接收的指令组606的每个指令中的比特进行编码以生成包含指令组606当中的零个或更多个编码指令流相依性的链接比特序列。

链接比特解码器608可以被配置为从指令组606中的指令604a-604n提取链接比特602，对所提取的链接比特602进行解码，并且产生流水线控制信号，这些流水线控制信号用于使得相依性信息、并行性信息和性能优化能够在不检查被编码在指令序列中的底层指令的情况下被解码。在图6中，链接比特解码器608可以被配置为对从所提取的链接比特602接收的经编码的链接比特组合的语义进行解码，并且可以被配置为对指令发布控制器610产生适当的控制。

在一个示例中，链接比特解码器608可以被配置为从指令组的每个指令(例如，指令组606中的指令604a-604n)提取指定比特以生成链接比特序列602。链接比特解码器608可以对链接比特序列602进行解码。可以在不对指令组中的任何指令(例如，指令组606中的指令604a-604n)进行解码的情况下对链接比特序列602进行解码。链接比特解码器608可以鉴于经解码的链接比特序列602来识别指令组(例如，指令组606中的指令604a-604n)当中的零个或更多个指令相依性。在示例中，指令组(例如，指令组606中的指令604a-604n)内的两个或更多个指令之间的任何被识别的相依性可以是控制相依性或数据相依性。链接比特解码器608然后可以确定指令组606中的一个或多个指令(例如，第二指令)与所述零个或更多个指令流相依性中的零个指令流相依性相关联。

指令发布控制器610可以被配置为使用控制信号614来控制指令组内的指令的发布(串行、并行或部分并行)，或者指令发布控制器610可以使用控制信号616来控制下一个指令组的发布。指令发布控制器610可以被配置为从链接比特解码器608接收命令，并且如果必要的话，可以产生停顿流水线级618a-618n(包括例如流水线时钟624a-624n、流水线级逻辑626a-626n以及对应的寄存器628a-628n)中的指令发布的流水线控制信号。流水线状态监视器620可以被配置为监视当前在流水线级618中执行的指令并且将反馈622提供给指令发布控制器610以在停顿之后重新开始指令发布。不同于VLIW和可见流水线设计，本公开的示例中的重要考虑是，流水线控制被产生为使得编译器或程序员看不见任何流水线效应。

在一个示例中，指令发布控制器610可以被配置为基于从准备发布逻辑603接收的控制信号616来确定具有发布序列的多个软件线程中的当前软件线程在一时钟周期期间没有等待被发布给硬件线程单元(例如，102a)的第一指令。指令发布控制器610可以被配置为基于从链接比特解码器608接收的控制信号616来识别发布序列中具有等待被发布的指令的一个或多个替代软件线程。指令发布控制器610可以被配置为：基于从链接比特解码器608接收的控制信号616，鉴于链接比特解码器608确定来自所述一个或多个替代软件线程当中的第二软件线程的第二指令与等待被发布的指令当中的任何其它指令没有相依性，在所述时钟周期期间选择该第二指令。相依性可以由链接比特解码器608鉴于链接比特解码器608从每个等待被发布的指令提取的链接比特的值来识别。在示例中，指令发布控制器610可以被配置为将第二指令发布给硬件线程单元。

图7是例示了用于使得相依性信息、并行性信息和性能优化能够被编码在指令序列中的方法700的示例的流程图。方法700可以例如由图1和6的计算机处理器或其它类型的计算机处理器的链接比特编码器605执行，并且可以包括硬件(例如，电路、专用逻辑、可编程逻辑、微码等)、软件(例如，在处理装置上运行的指令)、或它们的组合。在一个示例中，方法700可以由图1和6的计算机处理器100的链接比特编码器605执行。

如图7中所示，为了允许使得相依性信息、并行性信息和性能优化能够被编码在指令序列中，在方框705，在多线程处理器100上执行的链接比特编码器605接收指令流601。在方框710，链接比特编码器605从指令流601选择指令组指令(例如，指令组606中的指令604a-604n)。

在方框715，链接比特编码器605识别所选择的指令组(例如，指令组606中的指令604a-604n)当中的零个或更多个指令流相依性。在方框720，链接比特编码器605对来自所选择的指令组的每个指令(例如，指令组606中的指令604a-604n)的比特进行编码以生成链接比特序列602，该链接比特序列602包含指令组(例如，指令组606中的指令604a-604n)当中的零个或更多个编码指令流相依性。

在一个示例中，经编码的链接比特序列602可以指示所选择的指令组(例如，指令组606中的指令604a-604n)中的两个或更多个指令可以被并行地执行。在另一个示例中，经编码的链接比特序列602可以指示所选择的指令组(例如，指令组606中的指令604a-604n)中的两个或更多个指令必须被串行地执行。在另一个示例中，经编码的链接比特序列602可以指示所选择的指令组(例如，指令组606中的指令604a-604n)中的两个或更多个指令必须被并行地执行。在另一个示例中，经编码的链接比特序列602可以指示所选择的指令组(例如，指令组606中的指令604a-604n)可以被部分并行地、部分串行地执行。

在示例中，链接比特编码器605要放置在所选择的指令组(例如，指令组606中的指令604a-604n)中的指令的数量可以基于所选择的指令组将在其上被执行的处理器(例如，处理器100)的发布宽度。

在示例中，链接比特编码器605可以将所选择的指令组(例如，指令组606中的指令604a-604n)内的两个或更多个指令之间的相依性识别为控制相依性或数据相依性。

在示例中，经编码的链接比特序列602中的一个或多个比特可以能操作为优化可执行程序的性能。经编码的链接比特序列602可以能操作为充当流水线控制信号。

在一个示例中，在方框725，链接比特编码器605可以将所选择的指令组划分为第一指令组和第二指令组。在方框730，链接比特编码器605可以识别第一指令组和第二指令组之间的零个或更多个指令流相依性。在方框735，链接比特编码器605可以进一步对经编码的具有第一指令组和第二指令组之间的零个或更多个指令流相依性的链接比特序列进行编码。在示例中，经编码的链接比特序列中的比特可以指示第一指令组可以与第二指令组并行地执行。

图8是例示了用于使得相依性信息、并行性信息和性能优化能够在不检查被编码在指令序列中的底层指令的情况下被解码的方法800的示例的流程图。方法800可以由图1的多线程处理器100执行，并且在一个示例中，可以主要由图1和6的指令相依性预测电路118(例如，电路、专用逻辑、可编程逻辑、微码等)的链接比特解码器608执行。

如图8所示，在方框805，多线程处理器100的链接比特解码器608接收指令流。在方框810，链接比特解码器608从指令流选择指令组(例如，指令组606中的指令604a-604n)。在方框815，链接比特解码器608从指令流的每个指令(例如，604a-604n)提取指定比特602以生成链接比特序列602。在方框820，链接比特解码器608对链接比特序列602进行解码。在方框825，链接比特解码器608鉴于经解码的链接比特序列602来识别所选择的指令组(例如，指令组606中的指令604a-604n)当中的两个或更多个指令之间的零个或更多个相依性。在示例中，所选择的指令组604a-604n当中的两个或更多个指令之间的被识别的相依性可以是控制相依性或数据相依性。

在方框830，链接比特解码器608(例如，向指令发布控制器610)输出控制信号，以使一个或多个流水线级618鉴于所选择的指令组(例如，指令组606中的指令604a-604n)当中的两个或更多个指令之间的被识别的零个或更多个相依性来执行所选择的指令组(例如，指令组606中的指令604a-604n)。可以在不对所选择的指令组(例如，指令组606中的指令604a-604n)中的任何指令进行解码的情况下由链接比特解码器608对链接比特序列602进行解码。

在示例中，经解码的链接比特序列602中的剩余比特可以向指令发布控制器610指示所选择的指令组604a-604n中的两个或更多个指令可以被流水线级618并行地执行。在另一个示例中，经解码的链接比特序列602中的剩余比特可以向指令发布控制器610指示所选择的指令组604a-604n中的两个或更多个指令可以被流水线级618串行地执行。在另一个示例中，经解码的链接比特序列602中的剩余比特可以向指令发布控制器610指示所选择的指令组604a-604n中的两个或更多个指令必须被流水线级618并行地执行。在另一个示例中，经解码的链接比特序列602中的剩余比特可以向指令发布控制器610指示所选择的指令组可以被流水线级618部分并行地、部分串行地执行。

在示例中，要放置在所选择的指令组604a-604n中的指令的数量可以基于多线程处理器100的发布宽度。

在示例中，链接比特解码器608可以被配置为使用链接比特602来识别所选择的指令组内的组内相依性。因此，在方框835，链接比特解码器608可以将所选择的指令组604a-604n和相关联的链接比特602划分为第一指令组和第二指令组以便识别组内(例如，第一指令组和第二指令组之间的)相依性。

在方框840，链接比特解码器608可以基于经解码的链接比特序列602来识别第一指令组的指令和第二指令组的指令之间的零个或更多个相依性。在方框845，链接比特解码器608可以(例如，向指令发布控制器610)输出控制信号，以使一个或多个流水线级618基于第一指令组的指令和第二指令组的指令之间的被识别的零个或更多个相依性来执行第二指令组。在示例中，经解码的链接比特序列602中的比特可以指示第一指令组可以与第二指令组并行地执行。第一指令组的一个或多个指令和第二指令组的一个或多个指令之间的被识别的相依性可以是控制相依性或数据相依性。

在示例中，经解码的链接比特序列602中的一个或多个比特可以能操作为优化多线程处理器100的性能。在示例中，经解码的链接比特序列602可以能操作为充当流水线级618的流水线控制信号。

图9是例示了用于最小化当软件线程少于硬件线程单元(例如，102a-102n)时多线程处理器中的未使用的时钟周期的方法900的示例的流程图。方法900可以例如由图1和6的(例如，多线程)计算机处理器100执行，并且可以包括硬件(例如，电路、专用逻辑、可编程逻辑、微码等)、软件(例如，在处理装置上运行的指令)、或它们的组合。在一个示例中，方法900可以由图1和6的(例如，多线程)计算机处理器100的指令有效性预测逻辑118和指令发布控制器610执行。

如图9中所示，为了最小化当软件线程少于硬件线程单元时多线程处理器100中的未使用的时钟周期，在方框905，在多线程处理器100(例如，计算装置100)上执行的指令有效性预测逻辑118可以确定：在一时钟周期期间，具有发布序列的多个软件线程中的当前软件线程没有等待被发布给硬件线程单元(例如，102a)的第一指令。在方框910，多线程处理器100的指令发布控制器610可以识别发布序列中具有等待被发布的指令的一个或多个替代软件线程。在方框915，指令发布控制器610可以在所述时钟周期期间鉴于指令有效性预测逻辑118确定来自所述一个或多个替代软件线程当中的第二软件线程的第二指令与等待被发布的指令当中的任何其它指令没有相依性来选择该第二指令。相依性可以由指令有效性预测逻辑118鉴于从等待被指令发布控制器610发布的每个指令提取的链接比特的值来识别。在方框920，指令发布控制器610可以将第二指令发布给硬件线程单元(例如，102a)。

在示例中，指令发布控制器610可以将第一索引(例如，在线程ID寄存器116中)分配给与序列中的第二软件线程的位置对应的硬件线程单元(例如，102a)。指令发布控制器610可以将第二索引(例如，在线程ID寄存器116中)分配给与所述时钟周期对应的硬件线程单元(例如，102a)。在示例中，指令发布控制器610可以利用第一索引和第二索引来识别第二指令最初从其发布的第二软件线程。在示例中，响应于指令有效性预测逻辑118确定当前软件线程在所述时钟周期期间具有等待被发布给硬件线程单元(例如，102a)的第一指令，指令发布控制器610可以将第一指令发布给硬件线程单元(例如，102a)。

在另一个示例中，指令发布控制器610可以将第一索引(例如，在线程ID寄存器116中)分配给与发布序列中的当前软件线程的位置对应的硬件线程单元(例如，102a)。指令发布控制器610可以将第二索引(例如，在线程ID寄存器116中)分配给与所述时钟周期对应的硬件线程单元(例如，102a)。

在示例中，多线程处理器100可以利用第一索引和第二索引来识别第一指令最初从其发布的当前软件线程。

在示例中，发布序列可以初始是令牌触发的多线程序列。在示例中，所述多个软件线程中的软件线程的数量可以少于可用的硬件线程单元的数量。

图10是例示了用于确定图9的第二指令是否与等待被发布的指令当中的任何其它指令没有相依性的方法1000的示例的流程图。方法1000可以例如由图1和6的(例如，多线程)计算机处理器100执行，并且可以包括硬件(例如，电路、专用逻辑、可编程逻辑、微码等)、软件(例如，在处理装置上运行的指令)、或它们的组合。在一个示例中，方法1000可以由图1和6的(例如，多线程)计算机处理器1000的指令有效性预测逻辑118执行。

如图10中所示，为了确定图9的第二指令是否与等待被发布的指令当中的任何其它指令没有相依性，在方框1005，在多线程处理器100(例如，计算装置100)上执行的指令有效性预测逻辑118可以将第一指令和等待被发布的指令当中的其它指令分组一个指令组(例如，指令组606中的指令604a-604n)中。在方框1010，指令有效性预测逻辑118可以从该指令组(例如，指令组606中的指令604a-604n)的每个指令提取指定比特以生成链接比特序列602。在方框1015，指令有效性预测逻辑118可以对链接比特序列602进行解码。链接比特序列602可以在不对指令组中的任何指令进行解码的情况下被解码。在方框1020，指令有效性预测逻辑118可以鉴于经解码的链接比特序列602来识别指令组(例如，指令组606中的指令604a-604n)当中的零个或更多个指令相依性。在示例中，指令组内的两个或更多个指令之间的任何被识别的相依性可以是控制相依性或数据相依性。在方框1025，指令有效性预测逻辑118可以确定第二指令与所述零个或更多个指令流相依性中的零个相依性相关联。

在示例中，当图1的多线程处理器100具有四个硬件线程单元(T0-T3)时，一开始，指令执行可以被调度为将由硬件线程单元T0发布的第零个软件线程，接着是将由硬件线程单元T1发布的第一个软件线程，接着是将由硬件线程单元T2发布的第二软件线程，最后接着是将由硬件线程单元T3发布的第三个软件线程。时钟节拍可以分别跟随对应的硬件线程单元下标/索引；例如，初始的第零时钟周期(C0)，接着是第一时钟周期(C1)，接着是第二时钟周期(C2)，最后接着是第三时钟周期(C3)。

在一个示例中，硬件线程单元T0、T1、T2和T3(例如，102a-102d)可以以如下方式发布指令：如果硬件线程单元T0、T1、T2和T3(例如，102a-102d)全都具有分配给它们的软件线程，则每个硬件线程单元T0、T1、T2和T3(例如，102a-102d)将具有准备好并且等待被发布的指令。因此，多线程处理器100的指令发布控制器610可以继续执行如下：时钟周期C0、C1、C2和C3将分别被分配给与硬件线程单元T0、T1、T2和T3(例如，102a-102d)对应的软件线程。在令牌触发的多线程处理器中，不需要(一个或多个)线程ID寄存器116。在该示例中，指令发布控制器610分配标识寄存器，并且分别记录将被发布的每个指令为T₀₀、T₁₀、T₂₀和T₃₀。

在另一个示例中，硬件线程单元T0、T1、T2和T3(例如，102a-102d)可以以如下方式发布指令：如果软件线程少于硬件线程单元102a-102d，则硬件线程单元T0、T1、T2和T3(例如，102a-102d)中的一些将没有要发布的指令。在令牌触发的处理器中，硬件线程单元T0、T1、T2和T3(例如，102a-102d)将被要求发布NOP。

如果有个硬件线程单元(例如，102a)没有准备好发布的指令并且其它硬件线程单元(例如，102b、102c)具有正在等待的有效指令，则其它硬件线程单元(例如，102b、102c)之一(例如，前一个硬件线程单元)可以占据指定的时钟周期并且发布指令。在该示例中，指令发布控制器610查阅链接比特602以确定任何指令间相依性是否会禁止发布来自特定软件线程的进一步指令。如果链接比特602允许另一个软件线程发布额外的指令，并且软件线程少于硬件线程单元(例如，102a-102d)，则多线程处理器100的指令发布控制器610可以发布额外的指令。

因此，多线程处理器100的指令发布控制器610可以继续执行如下：假定硬件线程单元T1在时钟周期C1没有有效指令，但是硬件线程单元T0具有由指令有效性预测电路118确定的有效指令，那么可以利用经解码的链接比特来确定硬件线程单元T0是否可以发布额外的指令。如果硬件线程单元T0被允许发布，则硬件线程单元T0在时钟周期C1内发布额外的指令。额外的指令将被标识为T₀₁，并且被记录在相关联的识别寄存器116中。

图11示出四线程的机会多线程流水线操作控制处理时序图，其中，C_i是时钟周期标识符，T_ij是分配给时钟周期C_i的对应的被分配的线程标识符。中国专利申请No.201110361140.8(下称为“'40.8申请”)中描述了机会多线程的一个示例，该申请的全部内容通过引用并入本文。标题为“Method>

在图11所示的示例中，控制逻辑以硬件线程单元T₀开始。硬件线程单元T₀在时钟周期C₀发布指令。指令被分配标记T_0,0。在时钟周期C₁，指令发布控制器610确定硬件线程单元T₁是否具有准备好被发布的指令。如果硬件线程单元T₁具有准备好发布的指令，则硬件线程单元T₁发布指令T_1,0。如果硬件线程单元T₁没有准备好被发布的指令，那么如果硬件线程单元T₀具有准备好被发布的指令，则硬件线程单元T₀发布指令T_0,1。如果硬件线程单元T₀或硬件线程单元T₁都没有准备好发布的指令，则没有指令发布(例如，多线程处理器发布NOP)。

在时钟周期C₂，指令发布控制器610确定硬件线程单元T₂是否具有准备好被发布的指令。如果硬件线程单元T₂具有准备好被发布的指令，则指令发布控制器610将允许硬件线程单元T₂发布指令T_2,0。否则，指令发布控制器610可以确定硬件线程单元T₁和/或硬件线程单元T₀是否具有准备好被发布的指令。如果硬件线程单元T₀、T₁之一具有准备好被发布的指令，则指令发布控制器610将发布来自具有准备好的指令的硬件线程单元的指令。如果硬件线程单元T₀、T₁都具有准备好的指令，则控制逻辑可以用先进先出调度、优先权调度、循环调度或任何其它期望的调度策略来发布指令。

在时间周期C3，指令发布控制器610确定对于硬件线程单元T₃是否有等待发布的指令。如果硬件线程单元T₃具有准备好被发布的指令，则指令发布控制器610将允许硬件线程单元T₃发布指令T_2,0。否则，指令发布控制器610可以确定在其它硬件线程中是否存在等待发布的指令。如果仅有一个硬件线程单元具有准备好的指令，则指令发布控制器610将发布该指令。如果有多于一个的硬件线程单元具有准备好的指令，则控制逻辑可以用先进先出调度、优先权调度、循环调度或任何其它期望的调度策略来发布指令。线程指令发布对时钟周期C4、C5和C6以类似的方式继续，直到所有的软件线程都已经完成了发布至少一个指令。

要理解，以上描述的意图是说明性的，而非限制性的。在阅读和理解以上描述后，许多其它示例对于本领域技术人员来说将是显而易见的。因此，本公开的范围应参考所附权利要求书、连同这些权利要求有权享有的等同物的完整范围来确定。