确定性和机会性多线程

摘要

一种处理装置识别具有等待发出的指令的软件线程的集合。对于软件线程的集合中的每个软件线程，处理装置将软件线程绑定到硬件上下文的集合中的可用硬件上下文，并且将绑定到软件线程的可用硬件上下文的标识符存储到有序列表中的下一个可用条目。处理装置读取存储在有序列表的条目中的标识符。响应于与和等待发出的指令之中的任何其他指令没有依赖关系的标识符相关联的指令，处理装置向与标识符相关联的硬件上下文发出等待发出的指令。

权利要求

1.一种方法，所述方法包括：

通过处理装置识别具有等待发出的指令的软件线程的集合；

对于所述软件线程的集合中的每个软件线程，

通过所述处理装置将所述软件线程绑定到硬件上下文的集合中的可用硬件上下文；以及通过所述处理装置将绑定到所述软件线程的可用硬件上下文的标识符存储到有序列表中的下一个可用条目；

通过所述处理装置读取存储在所述有序列表的条目中的标识符；

响应于与和所述等待发出的指令之中的任何其他指令没有依赖关系的标识符相关联的指令，通过所述处理装置向与所述标识符相关联的所述硬件上下文发出所述等待发出的指令。

2.根据权利要求1所述的方法，所述方法还包括在下一个时钟周期针对所述有序列表中的下一个条目反复进行读取标识符和发出指令，直到已经访问了所述列表中的所有条目为止。

3.根据权利要求2所述的方法，还包括重复进行所述反复，直到具有所述等待发出的指令的所述软件线程中的一个或多个终止为止。

4.根据权利要求1所述的方法，其中，

响应于来自具有所述等待发出的指令的所述软件线程的软件线程的终止，通过所述处理装置从所述有序列表去除对应的标识符；以及通过所述处理装置，从硬件上下文的集合中的对应的可用硬件上下文解绑终止的软件线程。

5.根据权利要求1所述的方法，其中，

响应于向具有等待发出的指令的软件线程添加新软件线程，通过所述处理装置，将所述新软件线程绑定到硬件上下文的集合中的可用硬件上下文；以及通过所述处理装置，将绑定到所述新软件线程的所述可用硬件上下文的标识符存储到有序列表中的下一个可用条目。

6.根据权利要求1所述的方法，其中，响应于与和具有等待发出的指令之中的任何其他指令具有一个或多个依赖关系的标识符相关联的指令，通过所述处理装置，针对相关联的软件线程发出不操作或者将结果直接寄存旁路到下一个指令。

7.根据权利要求1所述的方法，其中，所述有序列表是位的阵列，并且存储在所述有序列表中的标识符是与硬件上下文的集合中的上下文编号对应的位集合。

8.根据权利要求1所述的方法，其中，所述有序列表是标签的阵列，并且存储在所述有序列表中的标识符是与所述硬件上下文的集合中的上下文编号对应的标签。

9.根据权利要求8所述的方法，其中，所述有序列表中的标签中的每个是不重复的。

10.根据权利要求1所述的方法，其中，所述有序列表是标签的链接列表，并且存储在所述有序列表中的所述标识符是与所述硬件上下文的集合中的上下文编号对应的标签。

11.根据权利要求1所述的方法，其中，基于从等待发出的指令中的每个提取的链接位的值来识别依赖关系。

12.根据权利要求1所述的方法，其中，确定与所述标识符相关联的指令与所述等待发出的指令之中的任何其他指令没有依赖关系包括：通过所述处理装置，将与所述标识符相关联的指令和所述等待发出的指令之中的其他指令分组到一组指令中；

通过所述处理装置，从所述一组指令中的每个指令提取指定位，以产生链接位序列；

通过所述处理装置，解码所述链接位序列；

通过所述处理装置，基于解码后的所述链接位序列来识别所述一组指令之间的零或更多的指令依赖关系；以及通过所述处理装置，确定与所述标识符相关联的指令与零或更多的指令流依赖关系中的零依赖关系相关联。

13.根据权利要求12所述的方法，其中，在不解码所述一组指令中的任何指令的情况下解码所述链接位序列。

14.根据权利要求12所述的方法，其中，所识别的所述一组指令内的两个或更多个指令之间的依赖关系是控制依赖关系或数据依赖关系。

15.根据权利要求12所述的方法，还包括通过所述处理装置，利用所述一组指令之间的零或更多的依赖关系来编码每个指令中的指定位，以产生链接位序列。

16.根据权利要求1所述的方法，其中，所述软件线程的集合中的软件线程的数量比所述硬件上下文的集合中的硬件上下文的数量少。

17.一种处理装置，所述处理装置包括：

存储器；

耦接到所述存储器的多个硬件线程单元；

可操作地耦接到所述存储器的所述处理装置的指令发出逻辑，所述指令发出逻辑用来：识别具有等待发出的指令的软件线程的集合；

对于所述软件线程的集合中的每个软件线程，

将所述软件线程绑定到硬件上下文的集合中的可用硬件上下文；以及将绑定到所述软件线程的可用硬件上下文的标识符存储到有序列表中的下一个可用条目；

读取存储在所述有序列表中的条目中的标识符；

响应于与和所述等待发出的指令之中的任何其他指令没有依赖关系的标识符相关联的指令，向与所述标识符相关联的所述硬件上下文发出所述等待发出的指令。

18.根据权利要求17所述的系统，还包括所述指令发出逻辑在下一个时钟周期针对所述有序列表中的下一个条目反复进行读取标识符和发出指令，直到已经访问了所述列表中的所有条目为止。

19.根据权利要求17所述的系统，还包括所述指令发出逻辑重复进行所述反复，直到具有所述等待发出的指令的所述软件线程中的一个或多个终止为止。

20.根据权利要求17所述的系统，其中，所述有序列表是存储在寄存器中的位的阵列，并且存储在所述有序列表中的标识符是与硬件上下文的集合中的上下文编号对应的位集合。

21.根据权利要求17所述的系统，其中，所述有序列表是存储在寄存器中的标签的阵列，并且存储在所述有序列表中的标识符是与所述硬件上下文的集合中的上下文编号对应的标签。

22.根据权利要求17所述的系统，其中，所述有序列表是存储在存储器中的标签的链接列表，并且存储在所述有序列表中的所述标识符是与所述硬件上下文的集合中的上下文编号对应的标签。

23.根据权利要求17所述的系统，其中，基于从等待发出的指令中的每个提取的链接位的值来识别依赖关系。

24.根据权利要求17所述的系统，还包括与所述存储器操作地耦接的所述处理装置的指令有效性预测逻辑，所述指令有效性预测逻辑用于确定与所述标识符相关联的指令与所述等待发出的指令之中的任何其他指令没有依赖关系，包括：通过所述指令有效性预测逻辑，将与所述标识符相关联的指令和所述等待发出的指令之中的其他指令分组到一组指令中；

通过所述指令有效性预测逻辑，从所述一组指令中的每个指令提取指定位，以产生链接位序列；

通过所述指令有效性预测逻辑，解码所述链接位序列；

通过所述指令有效性预测逻辑，基于解码后的所述链接位序列来识别所述一组指令之间的零或更多的指令依赖关系；以及通过所述指令有效性预测逻辑，确定与所述标识符相关联的指令与零或更多的指令流依赖关系中的零依赖关系相关联。

说明书

确定性和机会性多线程

[0001] 相关申请的交叉引用

[0002] 本申请要求2014年11月12日提交的美国专利申请号14/539342和2014年2月6日提交的美国临时专利申请号61/936428(下文中，“428申请”)的权益，美国专利申请号14/539342要求2014年6月17日提交的美国临时专利申请62/013241的权益，这些专利申请的公开内容通过引用整体并入于此。

技术领域

[0003] 本公开的示例涉及计算机架构。更具体地，所述示例涉及能够执行基于RISC的控制代码和数字信号处理器(DSP)代码的多线程指令集架构和组织。

背景技术

[0004] 在高性能处理器中已经采用了多线程并行处理技术来减少由长流水线引起的高速处理器指令执行延迟的影响。多线程并行处理技术具有比其他处理器设计改进的每周期指令性能和效率。多线程是用于硬件和软件加速两者的公知的技术。Bruton Smith circa 1979设计了Delencor HEP处理器(至于更多细节，参见“www-ee.eng.hawaii.edu/～nava/HEP/introduction.html”)。在该设计中，可从单个线程执行多个指令。Delencor HEP处理器的设计的一个要求是每个软件线程必须在发出后续指令之前完成当前指令。当每个硬件线程单元(下文中，“上下文”或“硬件上下文”，以将其与软件线程区分开)发出指令并且按顺序进行时，其可称为桶型多线程或轮转调度。

[0005] 在多线程处理器中，所有执行线程同时操作。在桶型多线程中，可允许每个硬件线程单元或上下文同时执行指令，但是只有一个上下文可在周期边界上发出指令。因此，如果存在C个上下文，则需要C个周期从所有上下文发出指令。所有上下文同时执行，但是只有一个上下文可在特定时钟周期上发出指令。暗指允许每个时钟周期、上下文发出指令和执行的线程通过递增上下文编号来执行。

[0006] 图1示出桶型多线程执行序列的示例。在该示例中，处理器按T0→T1→T2→T3→T4→T5→T6→T7→T0…的特定次序，每个时钟周期一个指令地将线程分发到上下文，一直绕该链进行，直到完成该循环并且再次到达T0为止。在具有8个上下文的处理器中，需要8个时钟周期来将线程分发到所有8个上下文。此外，单个上下文(例如，T0)可以每8个时钟周期只发出一次指令。

[0007] 图2示出非流水线式处理器中的两个指令的执行的示例。为了执行addi和muli这两个指令，每个指令进行四级操作。“addi”代表寄存器r2与直接值8相加的相加直接值(add immediate)，并且结果被存储在寄存器r0中。“multi”代表其中寄存器r3与直接值4相乘的相乘直接值，并且结果被存储在寄存器r8中。在第一级(指令取出(IF))中，从存储器取出指令addi并且进行解码。在第二级(寄存器读(RD))中，从寄存器文件读取操作数r2。在第三级(执行(Ex))中，将来自寄存器r2的操作数与直接值8相加。在第四级(写回(WB))中，将结果写入寄存器r0内。在写入结果之后，取出下一个指令(muli)。因此，为了执行N个指令，需要4个时钟节拍。

[0008] 流水线是通过注意以下内容来重叠多个指令的执行的技术：当指令离开执行的特定级时，该级是休眠的，并且如果另一个指令可用来执行，则后一指令可在完成前一指令之前开始执行。图3示出流水线式重叠执行的示例。在没有冒险的完美的流水线式机器中，完美的流水线将时钟周期减少为N+3，而不需要4N个时钟周期来执行N个指令。

[0009] 然而，流水可以没有冒险。图4示出muli指令需要addi的结果的示例。如果允许如图4中所示地执行指令，则将返回不正确的结果，因为在muli指令读取r0之前结果不被放到r0内。这被称为写后读(RAW)冒险。为了避免该冒险，流水线必须互锁从而暂停，形成所谓的流水线气泡。流水线互锁可将非确定性引入到系统中。如果N个指令没有冒险，则执行时间是N+3个时钟周期。如果每一个指令具有冒险，则执行时间是3N+1个周期。典型程序P将被限制在N+3<＝P<＝3N+1。

[0010] 图5示出桶型线程的流水线式处理器中的指令集合的执行序列的示例。在该示例中，三个独立线程正在共享执行单元的流水线式处理器上执行。第一线程执行原始的addi/muli指令序列502、504。在没有中断或长延迟负载的情况下，决没有任何流水线互锁，因为分别来自第二线程和第三线程的指令506、508被插入流水线中。因此，第一线程没有遇到任何冒险。在该示例中，N个指令将总是在N+3个周期中完成，而没有任何冒险。然而，这N个指令必须跨足够数量的线程分布，以保证无冒险执行。缺点是如果在系统中只存在单个线程，则单个线程本身将总是需要3N+1个周期来执行程序，即使指令是无冒险的。

[0011] 为了改进在多线程处理器上执行的单线程程序的性能，已经开发了多种技术。一种这样的技术是在处理器中采用的同时多线程(SMT)(至于更多细节，参见“www.cs.washington.edu/research/smt/index.html”)。在如在“Intel Hyper-Threading Technology，Technical User’s Guide”中描述的Intel的Hyper-Threading、如在Clabes、Joachim等人的2004IEEE International Solid-State Circuits Conference的论文集的“Design and Implementation of POWER5Microprocessor”中描述的IBM的POWER5、如在
2008年1月9日检索的“Using the Cryptographic Accelerators in the UltraSPARC T1and T2Processors”(Sun BluePrints Online，Sun Microsystems)中描述的Sun Microsystem的Ultra SPARC T2以及如在2014年1月4日检索的“MIPS32Architecture”中描述的MIPS MT(Imagination Technologies)中，已经采用了SMT。

[0012] 典型的基于SMT的处理器需要每个线程在基于SMT的处理器内的流水线的每一级处具有它自己的寄存器集合和额外的跟踪逻辑。这增加了硬件资源的尺寸，具体地，增加了实现基于SMT的处理器的设计所需的线程跟踪逻辑。由基于SMT的处理器采用的线程跟踪逻辑不仅需要追踪线程的执行，而且需要确定线程是否已经完成了执行。因为基于SMT的处理器可采用大量活跃地执行的硬件上下文，所以CPU高速缓存和相关联的转换后援缓冲器(TLB)的尺寸需要足够大以避免硬件上下文抖动。

[0013] 尽管SMT技术可改进单线程性能，但以上识别的控制电路复杂度致使其难以将SMT技术应用于需要低功耗的嵌入式处理器。

[0014] 利用同时多线程，多个硬件线程单元(硬件上下文)可以每个周期发出多个指令。当与诸如无序处理的超标量技术结合时，SMT所需的额外硬件并不重要。然而，在线程分发中必须谨慎，以确保所有线程都可发出指令。为了促进这点，已经开发了各种技术，包括优先级反转和抢先调度。

[0015] 同时多线程的优点是单个线程可以在每一个时钟周期向流水线发出指令。因此，只具有单个线程的程序P可没有冒险地在4级流水线上在N+3个周期中执行。事实上，SMT几乎总是利用超标量发出逻辑来实现，使得所需时钟周期的数量更进一步减少N+3/IPC(每个周期的指令)。SMT处理器的关键考虑是执行时间不再是确定性的。然而，单线程性能以额外的复杂硬件为代价而显著增强。

[0016] 为了克服SMT控制电路的复杂度并且降低功耗，已经开发了其他形式的多线程技术。已经提出了块多线程和交叉多线程。遗憾的是，块多线程技术受限于微控制器和其他低性能处理器。传统的交叉多线程技术(也称为令牌触发多线程)具有简化的控制电路，但当在处理器中存在比可用硬件上下文少的软件线程时，性能变差。在特定高性能低功率处理器中推进了该技术。在美国专利号6,842848中描述了令牌触发的多线程技术的代表性示例。

[0017] 传统的令牌触发的多线程采用了分时。通过处理器授予执行每个软件线程的许可，以按照它自己分派的时钟周期来执行。每个时钟周期只许可一个软件线程发出命令。采用令牌来告知软件线程在下一个时钟周期中软件线程是否应当发出指令。这进一步简化了硬件上下文逻辑。没有软件线程可发出第二指令，直到所有软件线程都已经发出指令为止。如果软件线程没有可用于发出的指令，则由硬件上下文发出不操作(NOP)。处理器硬件确保每个软件线程具有相同的指令执行时间。可在指定的保证时间段(例如，时钟周期)内完成操作的结果。因此，在处理器设计中不需要指令执行有关的检查和旁路硬件。

[0018] 传统的令牌触发多线程技术简化了多线程处理器的硬件发出逻辑，并且因此，可以用极小的功耗来实现高性能。然而，与SMT技术相比，如果在时钟周期期间存在比可用硬件上下文更少的具有可执行指令的软件线程，则传统的令牌触发多线程处理器的性能改进受限。在这些情形下，没有向其分派软件线程的硬件上下文必须发出NOP。

[0019] 为了避免软件线程之间的干扰并且为了简化硬件结构，传统的令牌触发多线程采用分时策略，分时策略可以使每个周期执行少量指令。这降低了单线程操作的处理速度。例如，如果用于上下文T1的软件指令不在高速缓存中并且需要从外部存储器重新加载，则由于外部存储器的低速度，T1必须等待许多周期来重新加载指令。如果上下文T0准备好指令，则它仍必须等待在时钟周期C1处发出指令。然而，因为时分数据路径的结构限制，所以时钟周期C1可只由上下文T1使用，并且在这种情况下，硬件上下文必须发出NOP。

[0020] 在执行单个软件线程的最坏情况下，对应的传统令牌触发处理器的性能是1/T(其中，T是硬件上下文的数量)。在1GHz下运行的10线程令牌触发的处理器中，处理器的性能有效地降低至100MHz。

[0021] 为了避免在硬件上下文线程之间抖动并且简化硬件上下文线程之间的跟踪电路，在Sandblaster 2.0处理器中，每个硬件上下文具有如在“The Sandblaster 2.0Architecture and SB3500Implementation Proceedings of Software Defined Radio Technical Forum(SDR Forum’08)”(华盛顿哥伦比亚特区，2008年10月)中描述的它自己的单独指令存储器。遗憾的是，在硬件上下文之间不可共享个体指令存储器。当软件线程的数量比硬件上下文的数量少时，除了导致性能降低之外，这还会导致存储器资源未充分利用。

发明内容

[0022] 通过提供当存在比硬件线程单元少的软件线程时使多线程处理器中的未使用的时钟周期最少的处理装置，解决了本领域中的上述问题并且实现了本领域中的技术解决方案。所述处理装置识别具有等待发出的指令的软件线程的集合。对于所述软件线程的集合中的每个软件线程，所述处理装置将所述软件线程绑定到硬件上下文的集合中的可用硬件上下文并且将绑定到软件线程的可用硬件上下文的标识符存储到有序列表中的下一个可用条目。所述处理装置读取存储在所述有序列表中的条目中的标识符。响应于与和所述等待发出的指令之中的任何其他指令没有依赖关系的标识符相关联的指令，所述处理装置向与所述标识符相关联的硬件上下文发出等待发出的指令。

[0023] 在示例中，所述处理装置还可在下一个时钟周期针对所述有序列表中的下一个条目反复进行所述读取标识符和所述发出指令，直到已经访问了所述列表中的所有条目为止。在示例中，所述处理装置还可重复进行所述反复，直到具有所述等待发出的指令的所述软件线程中的一个或多个终止为止。

[0024] 在示例中，响应于来自具有所述等待发出的指令的所述软件线程中的软件线程的终止，所述处理装置可从所述有序列表中去除对应的标识符并且从硬件上下文的集合中的对应的可用硬件上下文解绑终止的软件线程。

[0025] 在示例中，响应于将新软件线程添加到具有等待发出的指令的软件线程，所述处理装置可将所述新软件线程绑定到硬件上下文的集合中的可用硬件上下文并且将绑定到所述新软件线程的所述可用硬件上下文的标识符存储到有序列表中的下一个可用条目。

[0026] 在示例中，响应于与和等待发出的指令之中的任何其他指令具有一个或多个依赖关系的标识符相关联的指令，所述处理装置可针对相关联的软件线程发出不操作或者可将结果直接寄存旁路到下一个指令。

[0027] 在示例中，所述有序列表可以是位的阵列并且存储在所述有序列表中的标识符是与硬件上下文的集合中的上下文编号对应的位集合。在示例中，所述有序列表可以是标签的阵列并且存储在所述有序列表中的标识符是与所述硬件上下文的集合中的上下文编号对应的标签。在示例中，所述有序列表可以是标签的链接列表并且存储在所述有序列表中的所述标识符是与所述硬件上下文的编号中的上下文编号对应的标签。

[0028] 在示例中，基于从等待发出的指令中的每个提取的链接位的值来识别依赖关系。

[0029] 在示例中，确定与所述标识符相关联的指令与所述等待发出的指令之中的任何其他指令没有依赖关系可包括：所述处理装置可将与所述标识符相关联的指令和所述等待发出的指令之中的其他指令分组到一组指令中。所述处理装置可从所述一组指令中的每个指令提取指定位，以产生链接位序列。所述处理装置可解码所述链接位序列。所述处理装置可基于解码后的所述链接位序列，识别所述一组指令之中的零或更多的指令依赖关系。所述处理装置可确定与所述标识符相关联的指令与零或更多的指令流依赖关系中的零依赖关系相关联。

[0030] 在示例中，可在不解码所述一组指令中的任何指令的情况下，解码所述链接位序列。在示例中，所识别的所述一组指令内的两个或更多个指令之间的依赖关系可以是控制依赖关系或数据依赖关系。

[0031] 在示例中，所述处理装置可利用所述一组指令之间的零或更多的依赖关系来编码每个指令中的指定位，以产生链接位序列。

附图说明

[0032] 根据结合附图考虑的以下呈现的示例的具体实施方式，可更容易理解本发明，并且其中类似的附图标记指代类似的元件。

[0033] 图1示出桶型多线程执行序列的示例。

[0034] 图2示出非流水线式处理器中的两个指令的执行的示例。

[0035] 图3示出流水线式重叠执行的示例。

[0036] 图4示出图1的muli指令需要addi的结果的示例。

[0037] 图5示出桶型线程的流水线式处理器中的指令集合的执行序列的示例。

[0038] 图6示出本公开的示例可操作于的当存在比可用硬件线程单元少的可执行软件线程时使未使用的时钟周期最少的多线程处理器内的硬件线程单元的一个示例。

[0039] 图7示出放大为示出由多个硬件线程单元共享以控制指令发出的信号生成的指令发出逻辑的组件的、图6的多线程处理器内的硬件线程单元的一个示例的框图。

[0040] 图8示出包括上下文ID(CID)寄存器的硬件上下文的集合的示例。

[0041] 图9示出被构造为保持跟踪多少硬件上下文正活跃地执行软件线程的标识符的有序列表。

[0042] 图10示出图7的时隙调度单元的实现方式的一个示例，其中存在三(3)个活跃的硬件上下文。

[0043] 图11示出两个独立指令的示例，所述指令中的每个具有为链接信息预留的对应位。

[0044] 图12示出双发出流水线式处理器的指令链接语义的集合的一个示例。

[0045] 图13示出3发出处理器中的指令链接的语义的一个示例。

[0046] 图14示出4发出处理器的指令链接语义的集合的一个示例。

[0047] 图15示出本公开的示例可操作于的用于从指令组中的指令提取链接位、解码所提取的链接位并且生成流水线控制信号的指令有效性预测逻辑的一个示例。

[0048] 图16是例示出使依赖关系信息、并行性信息和性能优化能够编码在指令序列中的方法的示例的流程图。

[0049] 图17是例示出在没有检查编码在指令序列中的下层指令的情况下使依赖关系信息、并行性信息和性能优化能够被解码的方法的示例的流程图。

[0050] 图18是例示出当存在比硬件线程单元少的软件线程时用于使多线程处理器中的未使用的时钟周期最少的方法的示例的流程图。

[0051] 图19是例示出用于确定与标识符相关联的指令是否与等待发出的指令之中的任何其他指令没有依赖关系的方法的示例的流程图。

[0052] 要理解的是附图是出于例示本发明的概念的目的，并且可以不按比例。

具体实施方式

[0053] 本公开的示例涉及计算机架构的领域。更具体地，示例涉及能够执行基于RISC的控制代码和数字信号处理器(DSP)代码的多线程的指令集架构和组织。示例包括包含SIMD矢量单元的现代技术和链接的指令执行的独特组合。

[0054] 多线程处理器的典型设计已示出多线程处理器可按各种方式从硬件线程单元(称为上下文或硬件上下文，以将它们与软件线程区分开)发出指令。发出指令的一种方式是顺序地穿过多个上下文。使用专用流水线设计结合多线程，可以确保在调度下一个上下文来执行的同时，上下文相对于请求和使用处理器资源不冲突。

[0055] 多线程处理器的典型设计的一个问题是单线程性能会变差。在本公开的示例中，保证桶型线程的处理器有提供确定性行为的分发时隙。还可使用特定分发策略将其他线程分发给上下文，该特定分发策略以确定性的方式提供增强的单线程性能，而没有导致死锁。

[0056] 图6示出本公开的示例可以操作于的当存在比可用硬件线程单元少的可执行软件线程时使未使用的时钟周期最少的多线程处理器600的硬件线程单元的一个示例。在示例中，多线程处理器600可包括多个硬件线程单元602a-602n。硬件线程单元602a-602n中的每个可包括程序计数器(PC)603、指令存储器604、指令解码器606、包括算术逻辑单元(ALU)610的一个或多个流水线执行单元、数据存储器612和寄存器文件614。

[0057] 在一个示例中，“多组”指令可分别从指令存储器(I高速缓存)604读取并且被指令解码器606解码。可采用解码的信息来生成(被多个硬件线程单元602a-602n共享的标记为“控制”或“指令发出逻辑608”的)控制信号，所述控制信号控制数据路径和流水线的操作。直接寄存器参考可被传送到寄存器文件614(标记为RF)并且包含在寄存器文件614内的数据可被传送到包括算术逻辑单元(ALU)610的一个或多个流水线执行单元。存储在数据存储器612中的操作的结果可被写回到寄存器文件614。可更新程序计数器(PC)603并且可从指令存储器604取出下一个指令。

[0058] 本领域技术人员应当认识到，在一个示例中，多线程处理器600的元件603-614中的一个或多个可被跨硬件线程单元602a-602n共享。例如，当元件603-614中的一个或多个不代表处理器状态时，元件603-614中的一个或多个(例如，一个或多个算术逻辑单元(ALU)610、指令存储器(I高速缓存)604、数据存储器612等)可在硬件线程单元602a-602n之间共享。反之，在示例中，需要为硬件线程单元602a-602n中的每个复制代表处理器状态的元件
603-614中的任意一个。

[0059] 图7示出被放大以示出被多个硬件线程单元602a-602n共享以控制指令发出的信号生成的指令发出逻辑608的组件的、图6的多线程处理器600内的硬件线程单元的一个示例的框图。在示例中，除了以上在图6中描述的组件之外，多线程处理器600还可设置有与硬件上下文(例如，602a-602n)中的对应的上下文相关联的上下文ID(CID)寄存器616a-616n的集合、指令有效性预测逻辑618、选择器620、时隙调度单元622和分配的上下文ID阵列(ACID)寄存器624，以保持跟踪有多少硬件上下文(例如，602a-602n)正活跃地执行软件线程。指令发出逻辑608的时隙调度单元622采用由上下文ID(CID)寄存器616a-616n提供的标识符和由指令有效性预测逻辑618提供的“链接位”(分别地，CID、CHAIN)，来确定指令是否可根据选择器620所选择地发出。如果所有的硬件上下文(例如，602a-602n)都具有分派给它们的软件线程，则执行以轮转调度的方式进行，就像任何桶型线程处理器的情况一样。然而，如果存在比硬件上下文(例如，602a-602n)少的软件线程，则指令发出逻辑608的时隙调度单元622采用ACID阵列寄存器624来确定轮转调度模式。

[0060] 在示例中，处理器、计算机处理器或处理装置600(例如，多线程处理器600)可包括每个周期可发出指令的一个或多个流水线。图3是代表性示例，但本领域技术人员将认识到，现代处理器流水线可以是二十(20)级或更多以及相关联的一个或多个硬件上下文(经常称为硬件线程单元，例如，硬件线程单元602a-602n)。每个硬件上下文(例如，602a-602n)可包括如图8中所示的上下文ID(CID)寄存器(例如，616a)。存储在对应的上下文ID寄存器(例如，616a)中的上下文标识符(例如，CID 800a)可被固定，以识别其中可执行软件线程的当前硬件上下文(例如，602a-602n)。可以使用CID(例如，800a)来访问正确的寄存器文件状态并且将软件线程动态地绑定到硬件上下文(例如，602a-602n)。在示例中，对于与处理装置(例如，多线程处理器600)相关联的硬件上下文(例如，602a-602n)的集合中的每个硬件上下文，处理装置(例如，多线程处理器600)可将CID(例如，800a)的值分派给上下文ID寄存器(例如，616a-616n)中的对应的寄存器中的硬件上下文(例如，602a-602n)。

[0061] 如图9中所示，标识符的有序列表(例如，AllocatedContextIDArray(“ACID阵列”)寄存器900中的位的阵列)可被构造为保持跟踪有多少硬件上下文(例如，602a-602n)正活跃地执行软件线程。ACID阵列寄存器900可针对每个硬件上下文(例如，602a-602n)包含一位。可对应于硬件上下文(例如，602a-602n)的集合中的硬件上下文编号来设置位。

[0062] 在运行时，在处理装置(例如，多线程处理器600)上运行的操作系统可将软件线程绑定到硬件上下文(例如，602a-602n)。在一个示例实现方式中，被绑定软件线程的硬件上下文设置对应于硬件上下文的ACID阵列位位置。在运行时，处理装置600(例如，多线程处理器600)可将软件线程分派给递增排序中的上下文，以确保相邻的硬件上下文被分配。在一个示例中，假定都分派有软件线程的三个硬件上下文，处理装置600(例如，多线程处理器600)可按以下方式从软件线程发出指令：T0→T1→T2→T0等。

[0063] 图10示出图7的时隙调度单元622的实现方式的一个示例，其中存在三(3)个活跃的硬件上下文。分配上下文计数器(ACC)1002和寄存器1004设置有系统时钟信号fsys。在该示例中，设置了ACID阵列1006的3个条目(例如，设置为“1”)。ACID阵列中的这些值/标识符被馈入到寄存器1004内，寄存器1004控制向硬件上下文发出的时钟生成。利用三(3)个分配的活跃的硬件上下文，处理装置600(例如，多线程处理器600)可从软件线程T0→T1→T2→T0→T1→T2等发出指令。注意，没有活跃的软件线程的上下文T3不发出任何指令。

[0064] 对于本领域技术人员而言，应当认识到，可使用其他设备来保持跟踪活跃的硬件的数量，包括(但不限于)使用小的活跃上下文的表格的不相邻上下文，该小的活跃上下文的表格包括包含上下文标识符标签(例如，CID 0、CID 3、CID 7等)的条目。标识符标签可指示从其发出指令的当前硬件上下文。对应的标志可指示当线程开始或停止时将被修改的下一个时钟周期中应当采取的动作(例如，递增是“I”、重复是“R”)。还可使用活跃上下文和其他设备的链接列表。

[0065] 在一个示例中，标识符的有序列表1008可以是标签(例如，CID 800a-800n)的阵列(例如，ACID阵列寄存器900)。存储在有序列表1008中的标识符可以是与硬件上下文(例如，602a-602n)的集合中的上下文编号对应的标签(例如，CID 800a)。有序列表1008(例如，ACID阵列寄存器900)中的标签(例如，CID 800a-800n)中的每个可以是不重复的。

[0066] 在另一个示例中，有序列表1008(例如，ACID阵列寄存器900)可以是标签(例如，CID 800a-800n)的链接列表，并且存储在有序列表1008(例如，ACID阵列寄存器900)中的标识符是与硬件上下文(例如，602a-602n)的集合中的上下文编号对应的标签(CID 800a)。

[0067] 该“截断(truncated)”上下文指令发出可将指令间冒险引入流水线中。然而，如图5中所示，上下文T0(502)最初在后续寄存器文件读取之前被保证有四个时钟周期(从而避免任何冒险)，现在随着“截断”线程发出，在流水线中出现真正的冒险。可采用指令链接来要么将结果直接寄存旁路到下一个指令，要么在必要时在额外的时钟周期暂停处理器以保证正确的结果。还可利用动态逻辑来实现避免风险；然而，动态逻辑倾向于耗散大量功率。

[0068] 注意，当分配所有上下文时，可禁用截断上下文调度需要的任何额外逻辑，从而使功率耗散最小化。

[0069] 如果在系统中存在单个线程并且链接位识别后续指令可发出，则多线程桶型处理器可在不需要复杂的冒险检测电路的情况下获得峰值单线程性能。

[0070] 再参照图6至图10，在一个示例中，处理装置600(例如，多线程处理器600)的指令发出逻辑608可被构造为识别具有等待发出的指令的软件线程的集合。对于软件线程的集合中的每个软件线程，指令发出逻辑608可被构造为将软件线程绑定到硬件上下文(例如，602a-602n)的集合中的可用硬件上下文(例如，602a)。对于软件线程的集合中的每个软件线程，指令发出逻辑608可被构造为将绑定到软件线程的可用硬件上下文(例如，602a)的标识符(例如，上下文标识符(CID)(例如，800a))存储到标识符的有序列表1008(例如，ACID阵列寄存器900)中的下一个可用条目。在示例中，指令发出逻辑608可被构造为读取存储在有序列表1008(例如，ACID阵列寄存器900)的条目中的标识符(例如，CID 800a)。如果与标识符(例如，CID 800a)相关联的指令与等待发出的指令之中的任何其他指令没有依赖关系，则指令发出逻辑608可被构造为向与标识符(例如，CID 800a)相关联的硬件上下文(例如，
602a)发出等待发出的指令。指令发出逻辑608可被构造为在下一个时钟周期中针对标识符的有序列表1008(例如，ACID阵列寄存器900)中的下一个条目反复进行所述读取标识符(例如，CID 800a)和所述发出指令，直到已经访问了列表中的所有条目为止。指令发出逻辑608可被构造为重复进行所述反复，直到具有等待发出的指令的软件线程中的一个或多个终止为止。

[0071] 在示例中，如果处理装置600(例如，多线程处理器600)终止来自具有等待发出的指令的软件线程的软件线程，则指令发出逻辑608可被构造为从标识符的有序列表1008(例如，ACID阵列寄存器900)中去除对应的标识符(例如，CID 800a)，并且将终止的软件线程从硬件上下文(例如，602a-602n)的集合中的对应的可用硬件上下文(例如，602a)解绑。

[0072] 在示例中，如果处理装置600(例如，多线程处理器600)向具有等待发出的指令的软件线程添加新软件线程，则指令发出逻辑608可被构造为将新软件线程绑定到可用硬件上下文(例如，602a-602n)的集合中的可用硬件上下文(例如，602b)，并且将绑定到新软件线程的可用硬件上下文(例如，602b)的标识符(例如，CID 800a)存储到标识符的有序列表1008(例如，ACID阵列寄存器900)中的下一个可用条目。

[0073] 在一个示例中，多线程处理器600可设置有指令有效性预测逻辑618。指令有效性预测逻辑618可被构造为确定在时钟周期期间准备好要发出的指令之间是否存在任何依赖关系。由指令有效性预测逻辑618提供的依赖关系信息可被编码并且以“链接位”的形式输出，用来预先确定当前线程和任何额外线程是否具有可在下一个时钟周期中发出的有效指令。在示例中，基于由指令有效性预测逻辑618从等待发出的指令中的每个提取的链接位的值，可通过处理装置600(例如，多线程处理器600)的指令有效性预测逻辑618来识别依赖关系。指令有效性预测逻辑618可被构造为将与标识符相关联的指令和等待发出的指令之中的其他指令分组到一组指令中。指令有效性预测逻辑618可被构造为利用一组指令之间的零或更多的依赖关系来编码每个指令中的指定位，以产生链接位序列。

[0074] 在示例中，确定与标识符相关联的指令与等待发出的指令之中的任何其他指令是否没有依赖关系还可包括：指令有效性预测逻辑618可被构造为从一组指令中的每个指令提取指定位，以产生链接位序列。指令有效性预测逻辑618可被构造为解码链接位序列。指令有效性预测逻辑618可被构造为基于解码后的链接位序列来识别一组指令之间的零或更多的指令依赖关系。指令有效性预测逻辑618可被构造为确定与标识符相关联的指令与零或更多的指令流依赖关系中的零依赖关系相关联。

[0075] 在示例中，可在不解码一组指令中的任何指令的情况下，解码链接位序列。在示例中，所识别的一组指令内的两个或更多个指令之间的依赖关系可以是控制依赖关系或数据依赖关系。如果指令有效性预测逻辑618确定与标识符(例如，CID 800a)相关联的指令与等待发出的指令之中的任何其他指令具有一个或多个依赖关系，则处理装置600(例如，多线程处理器600)可被构造为针对相关联的软件线程发出不操作(NOP)。在另一个示例中，处理装置600(例如，多线程处理器600)可将结果直接寄存旁路到下一个指令。

[0076] 指令链接每个指令采用一位(下文中，称为“链接位”)，来指示处理器指令序列中的并行性和指令间依赖关系两者。如本文中使用的，指令指的是具有操作和操作数短语的可独立寻址单元(参见Gerrit A.Blaaw和Frederick P.Brooks,Jr.,“Computer Architecture：Concepts and Evolution”，Addison Wesley,第一版，1997年2月，第128页)。多个指令可被分组到一起，以形成可一起取出的指令组。在运行时，处理器重新汇编来自指令组中的指令的链接位，以在不必解码个体指令的情况下高效地解码指令流内的依赖关系和并行性。可采用该信息来生成指令发出所必需的流水线控制信号，从而消除对流水线式处理器架构中的NOP指令或复杂的指令间依赖关系检查硬件的需要。该过程可与对于编程者不可见的流水线效果(诸如，长负载流水线暂停、分支分解和其他长延迟操作)共存。由于每个指令是可独立寻址的，因此可允许跳至指令组的中间。然而，当跳至指令组的中间时，整个组的依赖关系位需要被重构用于链接位解码。如果编译器分析指令依赖关系并且生成链接位，则编程者实际上没有看到任何流水线效果并且可在不考虑冒险的情况下对机器编程。

[0077] 虽然可能可以定义要与不同处理器实现方式兼容的链接位的集合，但是对于大多数实现方式，链接位可以是依赖于实现方式的：它们的语义仅在它们被编程用于的处理器上可被解释。在示例中，单发出流水线式处理器可以只具有一个链接位的两个解释。“0”值指代无链接而“1”值指代指令可被与下一个指令链接。因此，在单发出流水线式处理器中，链接位可以仅指示指令是否独立以及有还是没有冒险。在另一个示例中，链接位的逻辑可被颠倒以将“0”解释为指代链接而将“1”解释为指代无链接。

[0078] 单发出流水线式处理器中的指令链接

[0079] 链接的最简单情况是如果没有指令间依赖关系则可以每个时钟周期发出一个指令的单发出流水线式处理器。图11示出两个独立指令1102、1104的示例1100，指令1102、1104中的每个具有为链接信息预留的对应位1106、1108。相乘指令1102的链接位1106被设置为1，因为相加指令1104是独立的并且可并行地执行。可基于特定处理器的能力将任意数量的位链接在一起。

[0080] 在示例中，对于典型的流水线式处理器，如果存在指令间依赖关系，则流水线必须暂停，直到依赖关系被分解为止。如果链接位被设置为“1”，则这是下一个指令与当前指令链内的任何指令没有控制或数据依赖关系的指示。因此，指令可被立即发出。如果链接位被设置为“0”，则这是下一指令与当前指令链内的至少一个指令具有控制和/或数据依赖关系的指示。因此，该指令的执行在当前链中的所有指令完成执行并且退出流水线之前无法开始。

[0081] 双发出流水线式处理器中的指令链接

[0082] 双发出流水线式处理器可被构造为如果不存在指令依赖关系则每一个周期发出两个指令(指令组)。如果指令组之间存在依赖关系，则流水线被暂停直到该依赖关系被分解为止。如果指令组内存在依赖关系，则指令组内的指令被串行地发出，即，第一指令被发出并且在第一指令完成执行并且退出流水线之前第二指令被暂停。

[0083] 指令组中的每个指令都具有链接位。因此，在双发出处理器中，每个指令组有两个链接位可用，并且因而4种场景可被编码。在示例中，一个链接位可被用来指示垂直并行性(组间并行性)并且第二链接位可被用来指示水平并行性(组内并行性)。

[0084] 图12示出了双发出流水线式处理器的指令链接语义的集合的一个示例。链接位i1和i2可以分别从指令组中的第一和第二指令取得。链接位i1是组内并行性位。如果组内并行性位是1，则组中的第二指令可被与组中的第一指令并行地发出。如果组内并行性位是0，则在第一指令已经完成执行之前第二指令必须等待。链接位i2是组间并行性位。如果组间并行性位是1，则下一个执行组可以在当前执行组之后在下一时钟周期中进入流水线。如果组间并行性位是0，则在当前执行组已经完成执行之前下一执行组必须等待。

[0085] 3发出流水线式处理器中的指令链接

[0086] 如果不存在指令依赖关系，则3发出流水线式处理器可以每一个周期发出三个指令(指令组)。如果指令组之间存在依赖关系，则流水线被暂停直到依赖关系被分解为止。如果指令组内存在依赖关系，则指令组内的指令如由链接位所指示地被串行地或者部分并行地发出。指令组中的每个指令都具有单个链接位。因此，在3发出处理器中，每个指令组有三个链接位可用，从而产生8种语义组合。一个链接位可被用来指示(跨指令组的)垂直并行性并且其他两个链接位可被用来指示(指令组内的)水平并行性。

[0087] 图13示出了3发出处理器中的指令链接的语义的一个示例。图13中指示的链接位组合的指令链接的语义的示例在水平并行性中提供了最大灵活性。图13中的x的值指示链接位可以是0或1。链接位i1、i2和i3可以分别从指令组中的第一、第二和第三指令得到。链接位i1和i2是组内并行性位t。如果i1或i2是1，则组中的下一个指令可被与组中的当前指令并行地发出。如果i1或i2是0，则在当前执行的指令已经完成执行之前下一指令必须等待。链接位i3是组间并行性位。如果i3是1，则下一执行组可以在当前执行组之后在下一时钟周期中进入流水线。如果i3是0，则在当前执行组已经完成执行之前下一执行组需要等待。

[0088] 如果水平并行性中的完全灵活性并非必需，则两个链接位可以足够来对垂直和水平并行性进行编码(所有三个指令被一起发出或不一起发出)。第三链接位可被用来对额外的信息进行编码。

[0089] 4发出流水线式处理器中的指令链接

[0090] 如果不存在指令依赖关系，则4发出流水线式处理器每一个周期发出四个指令。如果指令组之间存在依赖关系，则流水线可被暂停直到依赖关系被分解为止。如果指令组内存在依赖关系，则指令组内的指令可以如由链接位所指示被串行地发出或者部分并行地发出。

[0091] 指令组中的每个指令都具有单个链接位。因此，在4发出处理器中，每个指令组有四个链接位可用，从而产生16种语义组合。一个链接位可被用来指示(跨指令组的)垂直并行性并且其他三个链接位可被用来指示水平执行(在指令组内执行指令)的其他可能性。

[0092] 图14示出了4发出处理器的指令链接语义的集合的一个示例。图14中的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)。可能的并行性揭示了可用的并行性，但是处理器可以使用它或者可以不使用它。无论指令是并行地执行还是顺序地执行，结果保持不变。强制并行性指示指令必须被并行地执行以获得期望的结果。

[0093] 通过采用链接，可跨指令序列对依赖关系进行编码。在图13的示例中，3发出机器可以采用三个链接位(每个指令一个)来编码8种可能的依赖关系类型。在这个意义上，链接可被扩展为多组指令。例如，从三个指令的链接位解码出的“000”可被解释为当前组内的所有指令未被链接并且下一组指令不可与当前组指令链接。

[0094] 在一个示例中，在多发出处理器中，可以为组间并行性预留链接位中的一个以指示当前组指令之后的下一组指令是否包含与当前组指令的任何控制或数据依赖关系。如果不存在依赖关系，则下一组指令可被与当前组指令并发地沿着流水线向下发出，而没有任何流水线暂停。指令组内的其他链接位可以描述组内并行性信息，其指示当前指令组中的指令之间的并行性和依赖关系。

[0095] 链接位还可以对性能改进技术进行编码，诸如通知处理器使用旁路值而非从寄存器文件再次读取它。在一些情形下，这可以减少通过处理器耗散的功率。

[0096] 有利地，可以跨一组指令对并行性和依赖关系两者进行编码。可以采用链接位来对指令间依赖关系、组间依赖关系和性能优化进行编码，指令间依赖关系、组间依赖关系和性能优化在执行期间帮助快速地生成流水线式处理器中的必需的流水线控制信号，从而消除对复杂的依赖关系检查硬件的需要。

[0097] 本公开的示例涉及改进桶型线程处理器中的单线程性能。更具体地，可采用如在‘428申请中描述的来自链接指令的信息，来高效地确定可在没有冒险的情况下发出的指令。利用该信息，如果存在比硬件上下文少的软件线程，则可继续从相同的软件线程向相同的硬件上下文发出指令。

[0098] 在‘428申请中描述了方法和设备，由此编译器或编程者识别并行性和指令间依赖关系并且使用分布于多个指令的指令格式的单个位来编码该信息。这可被称为指令链接。处理器随后在运行时重新汇编这些位以确定指令流内的指令间依赖关系和并行性。处理器使用该信息来生成必要的流水线控制信号(如图6和图7中所示，标记为“控制”或指令发出逻辑608)，以改进执行时间或者暂停流水线以满足指令间依赖关系，而不需要复杂的依赖关系检查硬件、长指令序列或复杂的发出逻辑。诸如寄存器旁路信息之类的其他类型的性能优化可被编码到链接位中。

[0099] 本领域技术人员应认识到，等待发出指令的任意数量(例如，一个或多个)的软件线程可被分组在一起并且可通过采用链接位来识别等待发出指令的一组线程之间的依赖关系。

[0100] 图15示出本公开的示例可操作于的用于从指令组中的指令提取链接位、解码所提取的链接位并且生成流水线控制信号的指令有效性预测逻辑618的一个示例。指令有效性预测逻辑618可包括指令准备发出逻辑1503、链接位编码器1505和链接位解码器1508。指令准备发出逻辑1503可被构造为识别软件线程序列中的每个线程在特定时钟周期期间是否具有等待发出的指令。指令准备发出逻辑1503可被进一步构造为将等待发出的指令的集合分组到一组指令(下文中，“指令组1506”)中。

[0101] 链接位编码器1505可被构造为从由指令准备发出逻辑1503所识别的指令流1501接收指令组1506。链接位编码器1505可被构造为识别接收到的指令组1506之间的零或更多的指令流依赖关系。链接位编码器1505可被构造为编码接收到的指令组1506的每个指令中的一位，以产生包含指令组1506之间的零或更多的编码指令流依赖关系的链接位序列。

[0102] 链接位解码器1508可被构造为从指令组1506中的指令1504a-1504n提取链接位1502、解码所提取的链接位1502并且生成用于在不检查指令序列中编码的下层指令的情况下使依赖关系信息、并行性信息和性能优化能够被解码的流水线控制信号。在图15中，链接位解码器1508可被构造为解码从所提取的链接位1502接收的编码后的链接位组合的语义并且可被构造为为指令发出控制器1510生成适当的控制。

[0103] 在一个示例中，链接位解码器1508可被构造为从一组指令中的每个指令(例如，指令组1506中的指令1504a-1504n)提取指定位来产生链接位1502序列。链接位解码器1508可解码链接位1502序列。可在不解码一组指令中的任何指令(例如，指令组1506中的指令1504a-1504n)的情况下，解码链接位1502序列。链接位解码器1508可基于解码后的链接位
1502序列来识别一组指令(例如，指令组1506中的指令1504a-1504n)之间的零或更多的指令依赖关系。在示例中，任何所识别的一组指令(例如，指令组1506中的指令1504a-1504n)内的两个或更多个指令之间的依赖关系可以是控制依赖关系或数据依赖关系。链接位解码器1508然后可确定指令组1506中的一个或多个指令与零或更多的指令流依赖关系中的零依赖关系相关联。

[0104] 指令发出逻辑608可被构造为使用控制信号614来控制指令组内的指令的(串行、并行或部分并行)发出。指令发出逻辑608可被构造为从链接位解码器1508接收命令并且可生成流水线控制信号以在必要时暂停流水线级618a-618n(包括例如流水线时钟1524a-1524n、流水线级逻辑1526a-1526n和对应的寄存器1528a-1528n)中的指令发出。流水线状态监视器620可被构造为监视当前在流水线级1518中执行的指令并且向指令发出逻辑608提供反馈1522，以在暂停之后重启指令发出。本公开的示例中的不同于VLIW和可见流水线设计的重要考虑在于生成流水线控制，使得编译器或编程者看不到任何流水线效果。

[0105] 如果指令有效性预测逻辑618确定与标识符(例如，CID800a)相关联的指令与等待发出的指令之中的任何其他指令具有一个或多个依赖关系，则指令发出逻辑608可指示处理装置600(例如，多线程处理器600)针对相关联的软件线程发出不操作(NOP)。在另一个示例中，处理装置600(例如，多线程处理器600)可将结果直接寄存旁路到下一个指令。

[0106] 图16是例示出用于使得能够将依赖关系信息、并行性信息和性能优化编码在指令序列中的方法1600的示例的流程图。方法1600可以例如由图6、图7和图15中的计算机处理器的指令有效性预测逻辑618的链接位编码器1505或者由其他类型的计算机处理器来进行，并且可包括硬件(例如，电路、专用逻辑、可编程逻辑、微代码等等)、软件(例如，在处理装置上运行的指令)或其组合。在一个示例中，方法600可以由图6、图7和图15中的计算机处理器的指令有效性预测逻辑618的链接位编码器1505进行。

[0107] 如在图16中示出，为了允许使得依赖关系信息、并行性信息和性能优化能够被编码在指令序列中，在方框1605处，在多线程处理器600上执行的链接位编码器1505接收指令流1501。在方框1610处，链接位编码器1505从指令流1501中选择一组指令(例如，指令组1506中的指令1504a-1504n)。

[0108] 在方框1615处，链接位编码器1505识别所选择的一组指令(例如，指令组1506中的指令1504a-1504n)之间的零或更多的指令流依赖关系。在方框1620中，链接位编码器1505编码所选择的一组指令(例如，指令组1506中的指令1504a-1504n)中的每个指令中的一位，以产生包含一组指令(例如，指令组1506中的指令1504a-1504n)之间的零或更多的编码后的指令流依赖关系的链接位1502序列。

[0109] 在一个示例中，编码后的链接位1502序列可指示所选择的一组指令(例如，指令组1506中的指令1504a-1504n)中的两个或更多个指令可并行地执行。在另一个示例中，编码后的链接位1502序列可指示所选择的一组指令(例如，指令组1506中的指令1504a-1504n)中的两个或更多个指令可串行地执行。在另一个示例中，编码后的链接位1502序列可指示所选择的一组指令(例如，指令组1506中的指令1504a-1504n)中的两个或更多个指令必须并行地执行。在另一个示例中，解码后的链接位1502序列可指示所选择的一组指令(例如，指令组1506中的指令1504a-1504n)可部分并行地且部分串行地执行。

[0110] 在示例中，链接位编码器1505要放置在所选择的一组指令(例如，指令组1506中的指令1504a-1504n)中的指令的数量可以基于将在其上执行所选择的一组指令的处理器(例如，处理器600)的发出宽度。在示例中，链接位编码器1505要放置在所选择的一组指令(例如，指令组1506中的指令1504a-1504n)中的指令的数量可以进一步基于当软件线程的数量少于或等于可用硬件上下文(例如，602a-602n)的数量时等待从软件线程发出的指令的数量。

[0111] 在示例中，链接位编码器1505可识别所选择的一组指令(例如，指令组1506中的指令1504a-1504n)内的两个或更多个指令之间的依赖关系作为控制依赖关系或数据依赖关系。

[0112] 在示例中，编码后的链接位1502的序列中的一个或多个位可以可操作来优化可执行程序的性能。编码后的链接位1502序列可以可操作来起流水线控制信号的作用。

[0113] 在一个示例中，在方框1625处，链接位编码器1505可将所选择的一组指令划分成第一组指令和第二组指令。在方框1630处，链接位编码器1505可识别第一组指令和第二组指令之间的零或更多的指令流依赖关系。在方框1635处，链接位编码器1505可以利用第一组指令与第二组指令之间的零或更多的指令流依赖关系对编码后的链接位序列进一步进行编码。在示例中，编码后的链接位序列中的一位可指示第一组指令可与第二组指令并行地执行。

[0114] 图17是例示出用于在不检查编码在指令序列中的下层指令的情况下使得依赖关系信息、并行性信息和性能优化能够被解码的方法1700的示例的流程图。方法1700可以由图6、图7和图15中的多线程处理器600进行，并且在一个示例中，可主要由图6、图7和图15的指令有效性预测逻辑618(例如，电路、专用逻辑、可编程逻辑、微代码等)的链接位解码器1508进行。

[0115] 如图17中所示，在方框1705处，多线程处理器600的链接位解码器1508接收指令流。在方框1710处，链接位解码器1508从指令流中选择一组指令(例如，指令组1506中的指令1504a-1504n)。在方框1715处，链接位解码器1508从指令流的每个指令(例如，1504a-1504n)提取指定位1502，以产生链接位1502序列。在方框1720处，链接位解码器1508解码链接位1502序列。在方框1725处，链接位解码器1508基于解码后的链接位1502序列来识别所选择的一组指令(例如，指令组1506中的指令1504a-1504n)之中的两个或更多个指令之间的零或更多的依赖关系。在示例中，所识别的所选择的一组指令1504a-1504n之中的两个或更多个指令之间的依赖关系可以是控制依赖关系或数据依赖关系。

[0116] 在方框1730处，链接位解码器1508基于所识别的所选择的一组指令(例如，指令组1506中的指令1504a-1504n)之中的两个或更多个指令之间的零或更多的依赖关系(例如，向指令发出控制器1510)输出控制信号，以使一个或多个流水线级1518执行所选择的一组指令(例如，指令组1506中的指令1504a-1504n)。可在不解码所选择的一组指令(例如，指令组1506中的指令1504a-1504n)中的任何指令的情况下，通过链接位解码器1508来解码链接位1502序列。

[0117] 在示例中，解码后的链接位1502序列中的剩余位可向指令发出控制器1510指示所选择的一组指令1504a-1504n中的两个或更多个指令可由流水线级1518并行地执行。在另一个示例中，解码后的链接位1502序列中的剩余位可向指令发出控制器1510指示所选择的一组指令1504a-1504n中的两个或更多个指令可由流水线级1518串行地执行。在另一个示例中，解码后的链接位1502序列中的剩余位可向指令发出控制器1510指示所选择的一组指令1504a-1504n中的两个或更多个指令必须由流水线级1518并行地执行。在另一个示例中，解码后的链接位1502序列中的剩余位可向指令发出控制器1510指示所选择的一组指令可由流水线级1518部分并行地且部分串行地执行。

[0118] 在示例中，要放置在所选择的一组指令1504a-1504n中的指令的数量可以基于多线程处理器600的发出宽度。在示例中，链接位编码器1505要放置在所选择的一组指令(例如，指令组1506中的指令1504a-1504n)中的指令的数量可以进一步基于当软件线程的数量少于或等于可用硬件上下文(例如，602a-602n)的数量时等待从软件线程发出的指令的数量。

[0119] 在示例中，链接位编码器1508可被构造为使用链接位1502来识别所选择的一组指令内的组内依赖关系。因此，在方框1735处，链接位解码器1508可将所选择的一组指令1504a-1504n和相关联的链接位1502划分成第一组指令和第二组指令，以识别(例如，组之间的)组内依赖关系。

[0120] 在方框1740处，链接位解码器1508可基于解码后的链接位1502序列来识别从指令流选择的第一组指令中的指令和第二组指令中的指令之间的零或更多的依赖关系。在方框1745处，链接位解码器1508可基于所识别的第一组指令中的指令和第二组指令中的指令之间的零或更多的依赖关系，(例如，向指令发出控制器1510)输出控制信号，以使一个或多个流水线级1518执行第二组指令。在示例中，解码后的链接位1502序列中的一位可指示第一组指令可与第二组指令并行地执行。所识别的第一组指令中的一个或多个指令和第二组指令中的一个或多个指令之间的依赖关系可以是控制依赖关系或数据依赖关系。

[0121] 在示例中，解码后的链接位1502序列中的一个或多个位可以可操作来优化多线程处理器600的性能。在示例中，解码后的链接位1502序列可以可操作来起用于流水线级1518的流水线控制信号的作用。

[0122] 图18是例示出当存在比硬件线程单元(例如，602a-602n)少的软件线程时使多线程处理器中的未使用的时钟周期最少的方法1800的示例的流程图。方法1800可例如由图6和图7中的(例如，多线程的)计算机处理器600进行，并且可包括硬件(例如，电路、专用逻辑、可编程逻辑、微代码等)、软件(例如，在处理装置上运行的指令)或其组合。在一个示例中，方法1800可由图6和图7的(例如，多线程的)计算机处理600的指令发出逻辑608进行。

[0123] 如图18中所示，为了当存在比硬件线程单元少的软件线程时使在多线程处理器100中的未使用时钟周期最少，在方框1805处，在多线程处理器600(例如，处理装置600)上执行的指令发出逻辑608可识别具有等待发出的指令的软件线程的集合。在方框1810处，对于软件线程的集合中的每个软件线程，指令发出逻辑608可将软件线程绑定到硬件上下文的集合(例如，602a-602n)中的可用硬件上下文(例如，602a)。在方框1815处，对于软件线程的集合中的每个软件线程，指令发出逻辑608可将绑定到软件线程的可用硬件上下文(例如，602a)的标识符(例如，上下文标识符(CID)(例如，800a))存储在标识符的有序列表1008(例如，ACID阵列寄存器900)中的下一个可用条目。在方框1820处，指令发出逻辑608可读取存储在有序列表1008(例如，ACID阵列寄存器900)的条目中的标识符(例如，CID 800a)。在方框1825处，如果与标识符(例如，CID 800a)相关联的指令与等待发出的指令之中的任何其他指令没有依赖关系，则在方框1830处，指令发出逻辑608可向与标识符(例如，CID 
800a)相关联的硬件上下文(例如，602a)发出等待发出的指令。

[0124] 在方框1825处，如果指令发出逻辑608确定与标识符(例如，CID 800a)相关联的指令与等待发出的指令之中的任何其他指令具有一个或多个依赖关系，则在方框1835处，指令发出逻辑608可指示处理装置600(例如，多线程处理器600)针对相关联的软件线程发出不操作(NOP)。在另一个示例中，处理装置600(例如，多线程处理器600)可将结果直接寄存旁路到下一个指令。指令发出逻辑608可重复进行所述反复，直到具有等待发出的指令的软件线程中的一个或多个终止为止。

[0125] 在示例中，在方框1840处，如果处理装置600(例如，多线程处理器600)终止来自具有等待发出的软件线程的软件线程，则在方框1845处，指令发出逻辑608可从标识符的有序列表1008(例如，ACID阵列寄存器900)去除对应的标识符(例如，CID 800a)并且将终止的软件线程从硬件上下文(例如，602a-602n)的集合中的对应的可用硬件上下文(例如，602a)解绑。

[0126] 在示例中，如果处理装置600(例如，多线程处理器600)向具有等待发出的指令的软件线程添加新软件线程，则指令发出逻辑608可将新软件线程绑定到可用硬件上下文(例如，602a-602n)的集合中的可用硬件上下文(例如，602b)，并且将绑定到新软件线程的可用硬件上下文(例如，602b)的标识符(例如，CID 800a)存储到标识符的有序列表1008(例如，ACID阵列寄存器900)中的下一个可用条目。

[0127] 在框1850处，如果不再有具有等待发出的指令的软件线程，则执行终止。在方框1850处，如果在标识符的有序列表1008(例如，ACID阵列寄存器900)中存在更多条目，则指令发出逻辑608可在下一个时钟周期针对标识符的有序列表1008(例如，ACID阵列寄存器
900)中的下一个条目反复进行所述读取标识符(例如，CID 800a)并且所述发出指令，直到已经访问了列表中的所有条目为止。

[0128] 图19是例示出用于确定与标识符相关联的指令是否与等待发出的指令之中的任何其他指令没有依赖关系(图18中的方框1825)的方法1900的示例的流程图。方法1900可例如由图1和图6的(例如，多线程的)计算机处理器600进行，并且可包括硬件(例如，电路、专用逻辑、可编程逻辑、微代码等)、软件(例如，在处理装置上运行的指令)或其组合。在一个示例中，方法1000可由图1和图6的(例如，多线程的)计算机处理器100的指令有效性预测逻辑618进行。

[0129] 如图19中所示，在方框1905处，在多线程处理器600(例如，处理装置600)上执行的指令有效性预测逻辑618可将等待发出的指令之中的第一指令和其他指令分组到一组指令(例如，指令组1506中的指令1504a-1504n)中。在方框1910处，指令有效性预测逻辑618可从一组指令(例如，指令组1506中的指令1504a-1504n)中的每个指令提取指定位，以产生链接位1502序列。在方框1915处，指令有效性预测逻辑618可解码链接位1502序列。可在不解码一组指令中的任何指令的情况下解码链接位1502序列。在方框1920处，指令有效性预测逻辑618可基于解码后的链接位1502序列来识别一组指令(例如，指令组1506中的指令1504a-1504n)之间的零或更多的指令依赖关系。在示例中，所识别的一组指令内的两个或更多个指令之间的依赖关系可以是控制依赖关系或数据依赖关系。在方框1925处，指令有效性预测逻辑618可确定与标识符(例如，CID 800a)相关联的指令是否与零或更多的指令流依赖关系中的零依赖关系相关联。在方框1925处，如果与标识符(例如，CID 800a)相关联的指令与零或更多的指令流依赖关系相关联，则处理终止。

[0130] 在示例中，可在不解码一组指令中的任何指令的情况下，解码链接位序列。在示例中，所识别的一组指令内的两个或更多个指令之间的依赖关系可以是控制依赖关系或数据依赖关系。在方框1925处，如果指令有效性预测逻辑618确定与标识符(例如，CID 800a)相关联的指令与等待发出的指令之中的任何其他指令具有一个或多个依赖关系，则在方框1930处，指令有效性预测逻辑618将控制信号传送到指令发出逻辑608，指令发出逻辑608使处理装置600(例如，多线程处理器600)针对相关联的软件线程发出不操作(NOP)。在另一个示例中，处理装置600(例如，多线程处理器600)可将结果直接寄存旁路到下一个指令。

[0131] 要理解的是，上面的描述旨在是例示性而非限制性的。在阅读并理解上面的描述之后，许多其他示例对于本领域技术人员将是明显的。因此，本公开的范围应当参照所附的权利要求连同这些权利要求所享有的全部等同范围来确定。