平码五不中公式规律
  • / 21
  • 下载费用:30 金币  

通过使用分布的令牌有效地重运行和重试冲突的推测线程.pdf

关 键 ?#21097;?/dt>
通过 使用 分布 令牌 有效地 运行 重试 冲突 推测 线程
  专利查询网所有?#35797;?#22343;是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
摘要
申请专利号:

CN201310628253.9

申请日:

2013.11.29

公开号:

CN103914336A

公开日:

2014.07.09

当前法律状态:

授权

有效性:

有权

法?#19978;?#24773;: 授权|||实质审查的生效IPC(主分类):G06F 9/46申请日:20131129|||公开
IPC分类号: G06F9/46 主分类号: G06F9/46
申请人: 国际商业机器公司
发明人: M·欧玛克特; R·E·西尔维拉; M·G·斯图德莱; 王愷婷
地址: 美国纽约
优?#28909;ǎ?/td> 2012.12.28 US 13/730,427
专利代理机构: 中国国际贸易促进委员会专利商标事务所 11038 代理人: 叶勇
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

CN201310628253.9

授权公告号:

||||||

法律状态公告日:

2017.04.12|||2014.08.06|||2014.07.09

法律状态类型:

授权|||实质审查的生效|||公开

摘要

一种通过使用分布的令牌有效地重运行和重试冲突的推测线程。公开了一种用于在对称多处理SMP环?#25345;?#37325;运行推测线程的方法。在一个实施例中,这?#22336;?#27861;包括在运行时间检测终止的线程和确定终止的线程是否是最旧的终止的线程。在终止的线程是最旧的终止的线程的情况下,方法对与最旧的终止的线程相关的绝对线程号设定用于分配的高优先级请求。方法还包括检测高优先级请求被设定,并且作为响应,修改最旧的终止的线程的本地分配令牌。修改提示最旧的终止的线程重试与其绝对线程号相关的工作单元。最旧的终止的线程随后通过更新后继线程的本地分配令牌启动后继线程的重试。还公开相应的装置和计算机程序产品。

权利要求书

权利要求书
1.  一种用于在对称多处理SMP环?#25345;?#26377;效地重运行和重试冲突的推测线程的方法,该方法包括:
在运行时间检测终止的线程;
确定终止的线程是否是最旧的终止的线程;
在终止的线程是最旧的终止的线程的情况下,对分配给最旧的终止的线程的绝对线程号设定用于分配的高优先级请求;
检测高优先级请求被设定;和
响应于检测高优先级请求被设定,修改最旧的终止的线程的本地分配令牌,其中,修改提示最旧的终止的线程重试与其绝对线程号相关的工作单元。

2.  根据权利要求1的方法,其中,检测高优先级请求被设定包含通过最旧的终止的线程以外的线程检测。

3.  根据权利要求1的方法,其中,修改本地分配令牌包含将本地分配令牌设为与最旧的终止的线程的先前的本地分配令牌不同的值,其中,差异提示最旧的终止的线程重试与其绝对线程号相关的工作单元。

4.  根据权利要求1的方法,还包括终止比最旧的终止的线程更新的所有还没有终止的线程。

5.  根据权利要求4的方法,其中,终止比最旧的终止的线程更新的所有线程包含使比最旧的终止的线程更新的所有线程的推测标识符无效。

6.  根据权利要求1的方法,其中,允许最旧的终止的线程重试包含向最旧的终止的线程分配新的推测标识符。

7.  根据权利要求1的方法,其中,确定终止的线程是否是最旧的终止的线程包含确定终止的线程的本地提交令牌是否等于终止的线程的绝对线程号。

8.  一种用于在对称多处理SMP环?#25345;?#26377;效地重运行和重试冲突 的推测线程的装置,该装置包括:
至少一个处理器;
与至少一个处理器耦合并存储使得至少一个处理器完成以下的过程的计算机指令的至少一个存储器装置:
在运行时间检测终止的线程;
确定终止的线程是否是最旧的终止的线程;
在终止的线程是最旧的终止的线程的情况下,对分配给最旧的终止的线程的绝对线程号设定用于分配的高优先级请求;
检测高优先级请求被设定;和
响应检测高优先级请求被设定,修改最旧的终止的线程的本地分配令牌,其中,修改提示最旧的终止的线程重试与其绝对线程号相关的工作单元。

9.  根据权利要求8的装置,其中,检测高优先级请求被设定包含通过最旧的终止的线程以外的线程检测。

10.  根据权利要求8的装置,其中,修改本地分配令牌包含将本地分配令牌设为与最旧的终止的线程的先前的本地分配令牌不同的值,其中,差异提示最旧的终止的线程重试与其绝对线程号相关的工作单元。

11.  根据权利要求8的装置,还包括使得至少一个处理器终止比最旧的终止的线程更新的所有还没有终止的线程的计算机指令。

12.  根据权利要求11的装置,其中,终止比最旧的终止的线程更新的所有线程包含使比最旧的终止的线程更新的所有线程的推测标识符无效。

13.  根据权利要求8的装置,其中,允许最旧的终止的线程重试包含向最旧的终止的线程分配新的推测标识符。

14.  根据权利要求8的装置,其中,确定终止的线程是否是最旧的终止的线程包含确定终止的线程的本地提交令牌是否等于终止的线程的绝对线程号。

说明书

说明书通过使用分布的令牌有效地重运行和重试冲突的推测线程
?#38469;?#39046;域
本发明涉及通过使用分布的令牌在SMP环?#25345;?#26377;效地重运行和重试冲突的推测线程的装置和方法。
背景?#38469;?
称为线程级推测(speculation)(TLS)的推测执行(SE)需要依次开?#23478;约?#20381;次线程提交(commit)。工作负载一般分成称为绝对线程号(ATN)的一系列的工作单元,这些工作单元依次被分配给一组的n个线程。完整回合的分配将工作单元分配给线程T0、T1、…、Tn-2、Tn-1。通过依次分配线程并依次提交它们,保持程序语义。
当前SMP系?#25345;?#34892;推测执行的方式是低效的并且难以调试。例如,当前SMP系统需要内核以跟踪大量的冲突的事件(例如,使得线程终止的事件)。当大量的冲突的事件达到阈值时,内核修改这里称为“分配令牌”的全局变量,以启动终止的线程的重试。在用户空间中操作的线程还需要更新分配令牌。作为结果,需要锁定?#21592;?#25252;分配令牌。实现在内核与SMP运行时间之间共享的锁定使得设计低效且难以调试。例如,以下?#22659;?#29992;于启动推测的一系列的代码。在决定代码中也存在类似的锁定序列。


鉴于以上情况,需要用于有效地在SMP环?#25345;?#37325;运行和重试冲突的推测线程的装置和方法。在理想情况下,这种装置和方法将去除与分配令牌相关的锁定要求。
发明内容
响应现有?#38469;?#30340;当前状态,特别是响应当前可用的装置和方法还没有完全解决的现有?#38469;?#20013;的问题和需求,开发了本发明。因此,装置和方法被开发以更有效地在对称多处理(SMP)环?#25345;?#37325;运行推测线程。本发明的特征和优点从以下的描述和所附的权利要求将变得更?#29992;?#26174;,或者可通过以下阐述的本发明的实际被掌握。
与以上一致,这里公开一种用于在对称多处理(SMP)环?#25345;?#37325;运行推测线程的方法。在一个实施例中,这?#22336;?#27861;包括在运行时间检测终止的线程和确定终止的线程是否是最旧的终止的线程。在终止的线程是最旧的终止的线程的情况下,方法对与最旧的终止的线程相关的绝对线程号设定用于分配的高优先级请求。方法还包括检测高优先级请求被设定,并且作为响应,修改最旧的终止的线程的本地分配令牌。修改提示最旧的终止的线程重试与其绝对线程号相关的工作单元。
这里还公开和要求相应的装置和计算机程序产品。
附图说明
为了更容易理解本发明的优点,通过参照在附图中?#22659;?#30340;特定的实施例,给出以上简要描述的更具体的描述。应当理解,这些附图仅?#22659;?#26412;发明的典型的实施例,因此不应被视为限制其范围,因此,通过使用附图用附加的特定性和?#38468;?#25551;述和解释本发明,其中,
图1是表示可实现根据本发明的装置和方法的计算系统的一个例子的高级框图;
图2是表示被配置为执行对称多处理(SMP)的计算系统(即, ?#24067;?#24179;台)的一个例子的高级框图;
图3是表示在操作系统和?#24067;?#24179;台的顶部运行的根据本发明的SMP运行时间的一个实施例的高级框图;
图4是表示通过图3所示的SMP运行时间的依次开始阶段进展的各种线程的高级框图;
图5是表示在通过图3所示的SMP运行时间的依次开始阶段的进展之后终止的线程的例子的高级框图;
图6是表示图3所示的SMP运行时间的操作的状态图;
图7是表示根据本发明的SMP运行时间的另一实施例的高级框图;
图8是表示图7所示的SMP运行时间的操作的状态图;?#32422;?
图9是表示在图8的“等待开始”状态上实现的各种条件的处理流程图,这些条件包含越狱条件。
具体实施方式
很容易理解,可通过各种不同的构成配置和设计在这里的示图中一般描述和?#22659;?#30340;本发明的部件。因此,在附图中代表的本发明的实施例的以下的更详细的描述不是要限制要求权利的本发明的范围,而仅是为了代表根据本发明的当前设想的实施例的某些例子。参照附图,可以最好地理解当前描述的实施例,在这些附图中,类似的部分由类似的附图标记表示。
本领域?#38469;?#20154;员很容易理解,本发明?#21830;?#29616;为装置、系统、方法或计算机程序产品。并且,本发明可采取可在这里一般均称为“模块”或“系统”的?#24067;?#23454;施例、被配置为操作?#24067;?#30340;软件实施例(包含固件、驻留软件、微代码等)或组合软件和?#24067;?#26041;面的实施例。并且,本发明可采取在其中存储有计算机可用程序代码的表现的任何可触知介质中体现的计算机可用存储介质的形式。
可以利用一个或多个计算机可用或计算机可读存储的?#25105;?#32452;合?#28304;?#20648;计算机程序产品。计算机可用或计算机可读存储介质可例如为但 不限于电子、磁、光学、电磁、红外或半导体系统、装置或设备。计算机可读存储介质的更具体的例子(非限制性的列表)可包含以下方面:具有一个或多个导线的电连接、?#38408;?#24335;计算机盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、可?#21015;?#21487;编程只读存储器(EPROM或快?#21015;?#23384;储器)、?#38408;?#24335;光盘只读存储器(CDROM)、光学存储装置或磁存储装置。在本文件的上下文中,计算机可用或计算机可读存储介质可以是可包含、存储或传输供指令执行系统、装置或设备使用或者与其关联的程序的任何介质。
可通过包括诸如Java、Smalltalk或C++等的面向对象的编程语言、诸如“C”编程语言的常规的过程编程语言、诸如JavaScript的脚本语言或类似的编程语言的一个或多个编程语言的?#25105;?#32452;合书写用于实施本发明的操作的计算机程序代码。也可在诸如汇编语言的?#22270;?#32534;程语言中书写用于实现本发明的计算机程序代码。
以下参照方法、装置、系统和计算机程序产品的流程图和/或框图描述本发明的实施例。应当理解,可通过计算机程序指令或代码实?#33267;?#31243;图和/或框图的各块和流程图和/或框图中的块的组合。这些计算机程序指令可被提供给通用计算机、特定用途计算机或其它的可编程数据处理装置的处理器以制成机器,使得通过计算机或其它可编程数据处理装置的处理器执行的指令产生用于实现在流程图和/或框图块中规定的功能/作用的手段。
这些计算机程序指令也可存储于计算机可读介质中,这些计算机程序指令可指导计算机或其它可编程数据处理装置以特定的方式起作用,使得存储于计算机可读介质中的指令产生包括实现在流程图和/或框图块中规定的功能/作用的指令的制造物品。计算机程序指令也可被加载到计算机或其它可编程数据处理装置上,以使得在计算机或其它可编程装置上执行的一系列的操作步骤产生计算机实现的过程,使得在计算机或其它可编程装置上执行的指令提供用于实现在流程图和/或框图块中规定的功能/作用的处理。
现在参照图1,?#22659;?#35745;算系统100的一个例子。给出计算系统100 ?#21592;?#31034;可实现根据本发明的装置和方法的环境的一个例子。计算系统100仅作为例子被给出并且不是要限制。事实上,除了表示的计算系统100以外,在这里公开的装置和方法可适用于各种不同的计算系统。在这里公开的装置和方法也可潜在地跨着多个计算系统100分布。
如所示的那样,计算系统100包含至少一个处理器102,并且可包含多于一个的处理器102。处理器102可与存储器104操作连接。存储器104可包含一个或多个?#19988;资源?#20648;装置,诸如硬盘驱动器104a、固态驱动器104a、CD-ROM驱动器104a、DVD-ROM驱动器104a或带驱动104a等。存储器104还可包含诸如只读存储器104b(例如,ROM、EPROM、EEPROM和/或快?#21015;碦OM)的?#19988;资源?#20648;装置或诸如随机存取存储器104c(RAM或操作存储器)的?#36164;源?#20648;器。总线106或多个总线106可互连处理器102、存储器104和其它的装置以使得数据和/或指令在其间穿过。
为了实现与外部系统或装置的通信,计算系统100可包含一个或多个端口108。这些端口108?#21830;?#29616;为有线端口108(例如,USB端口、串行端口、Firewire端口、SCSI端口、并行端口等)或无线端口108(例如,蓝牙、IrDAt)。端口108可使得能够实现与一个或多个输入装置110(例如,键盘、鼠标、触摸屏、照相机、麦克风、扫描仪、存储装置等)和输出装置112(例如,显示器、监视器、扬声器、打印机、存储装置等)的通信。端口108还使得能够实现与其它计算系统100的通信。
在某些实施例中,计算系统100包含适于连接计算系统100与诸如LAN、WAN或因特网的网络116的网络适配器114。这种网络116可使得计算系统100能够与一个或多个服务器118、工作站120、个人计算机120、移动计算装置或其它的装置连接。网络116还可使得计算系统100能够通过路由器122或其它的装置122与另一网络连接。这种路由器122可允许计算系统100与服务器、工作站、个人计算机或位于不同的网络上的其它装置通信。
参照图2,?#22659;?#34987;配置为用于对称多处理(SMP)的计算系统100 的一个例子。如图所示,SMP计算系统100(也称为对称多处理器100或对称多处理器系统100)包含与单个共享存储器104c连接并被单个操作系统(OS)实例控制的多个处理器200a~c。处理器102a~c可通过使用总线106、纵横开关或芯片上网格网络等被互连。假定系统100中的各任务不是同时由多个处理器102a~c执行,SMP计算系统100可允许任?#26410;?#29702;器102a~c在任何任务上工作,而?#36824;?#35813;任务的数据是位于存储器104c的哪个位置。通过?#23454;?#30340;操作系统支撑,SMP计算系统100可在处理器102a~c之间移动任务以平衡工作负载。在某些实施例中,SMP计算系统100中的各处理器102可具有其自身的本地一级(L1)高速缓存200a~c,?#32422;?#36895;数据存取并减少系统总线106上的流量。处理器102a~c还可共享二级(L2)高速缓存202。
参照图3,在某些实施例中,根据本发明的SMP计算系统100包含?#24067;?#24179;台300(即,处理器102a~c、总线106、高速缓存200a~c、存储器104c等)。支持对称多处理(SMP)的操作系统302可在?#24067;?#24179;台300的顶部运行,并且,SMP运行时间304可在操作系统302的顶部运行。如图3所示,SMP运行时间304使用各种全局变量306、308、310以在对称多处理(SMP)环?#25345;?#37325;运行和重试冲突的线程。这些变量包含分配令牌306、高优先级(即“Hipri?#20445;?#35831;求308和提交令牌310中的一个或多个。以下详细?#33268;跾MP运行时间304使用这些变量306、308、310的方式。如以下表示的那样,这些变量306、308、310可按减少需要锁定分配令牌306的方式被SMP运行时间304使用。即,SMP运行时间304以不需要在内核(即,操作系统302)和SMP运行时间304之间实?#27490;?#20139;的锁定的方式使用变量306、308、310。
参照图4,如上所述,也称为线程级推测(TLS)的推测执行(SE)需要依次开?#23478;约?#20381;次线程提交。工作负载一般分成称为绝对线程号(ATN)的一系列的工作单元,这些工作单元依次被分配给一组的n个线程。完整回合的分配将工作单元分配给线程T0、T1、…、Tn-2、Tn-1。通过依次分配线程并依次提交它们,保持程序语义。
为了确保并行化的代码产生与串行执行即单个线程时相同的输出,必须满足以下的准则:在两个线程a和b等待推测标识符(这里,称为“specID?#20445;?#19988;线程已被分配分别具有ATN值x和y的工作单元的方案中,如果x<y,那么线程a应接收比线程b更新的specID。并且,在线程具有连续的ATN的情况下,应在分配给线程的specID之间不存在间隙。
图4是表示通过SMP运行时间304的依次开始阶段400进展的多个线程T0、T1、T2和T3的高级框图。在正常的操作模式下,线程选择阶段对于各线程分配唯一ATN值。图4表示线程选择阶段被分配分别具有ATN0、1、2和3的四个线程T0、T1、T2和T3工作单元的方案。全局计数器,即前面?#33268;?#30340;分配令牌306,被用于?#36816;?#20204;的ATN值的次序开始线程。在?#22659;?#30340;例子中,分配令牌306被初始化为零以允许具有ATN=0的线程开始。
各线程在接收与特定的ATN相关的工作单元之后前进到图4所示的依次开始阶段。如图所示,依次开始阶段400包含分配令牌轮询阶段402、分配阶段404和分配令牌增加阶段406。在分配令牌轮询阶段402中,各线程对分配令牌306轮询,并选择其接收specID的机会。当分配令牌306等于线程的ATN值时,线程前进到分配阶段404。在分配阶段404中,线程被分配?#24067;pecID。在接收specID之后,线程前进到分配令牌增加阶段406,该分配令牌增加阶段406将分配令牌加1,以允许下一线程通过依次开始阶段400前进。通过使用该协议,只有单个线程在任何给定的时间通过分配阶段404。
参照图5,在线程被重运行并且需要重试其工作单元的情况下,诸如在线程由于冲突而终止的情况下,出现以上的协议的复?#26377;浴?#22312;重运行方案中,事先分配specID的线程在执行其工作单元时终止并且为?#31169;?#25910;更新的specID返回到依次开始阶段400。注意,这种线程仍具有它在终止之前具有的相同的ATN。但是,到线程终止为止,分配令牌306将增加为高于线程的ATN值。并且,到线程终止为止,具有更大的ATN的其它线程可能已通过依次开始阶段前进并接收 specID。图5表示这?#22336;?#26696;。
如图5所示,在通过依次开始阶段400前进之后,线程T0在工作单元处理阶段502中处理其工作单元。在完成其工作单元时,T0前进到依次提交阶段,在依次提交阶段中,它等待全局计数器(例如,前面?#33268;?#30340;提交令牌310)等于其ATN。当提交令牌310等于其ATN时,T0提交在工作单元处理阶段502中执行的工作。
假定第二线程T1已通过依次开始阶段400前进,并且,当其由于冲突或其它的问题终止时,在工作单元处理阶段502中处理其工作单元。并且,假定在时间T1上终止,T2已通过依次开始阶段400前进并接收specID。假定线程T2将分配令牌306增加到3,由此允许线程T3开始通过依次开始阶段400前进。到线程T2终止时,线程T2为了重试其工作单元返回到依次开始阶段400。分配给线程T2的ATN值保持不变。
由于到T2返回到依次开始阶段400为止分配令牌306在线程T2的ATN之上增加,因此,线程T2在正常的操作模式下将得不到重试其工作单元的机会。即,分配令牌306将决不等于T2的ATN,由此防止T2通过依次开始阶段400重新前进。简单地将分配令牌306?#27425;?#21040;T2的ATN由此允许T2再一次通过依次开始阶段400前进,可在分配令牌306上产生急流(race)(即,会在尝试重试其工作单元的终止的线程与当前通过依次开始阶段400的线程之间产生急流,它们中的每一个尝试更新分配令牌306)。这?#22336;?#26696;会使得程序死机。
为了消除以上?#33268;?#30340;急流条件,最旧的终止的线程可设定事先?#33268;?#30340;高优先级请求变量308而不是直?#26377;?#25913;分配令牌306。高优先级请求变量308可识别最旧的终止的线程的ATN并指示最旧的终止的线程希望再进入分配阶段404并接收新的specID,由此允许最旧的终止的线程重试其工作单元。ATN等于分配令牌306的较新的线程在进入分配令牌轮询阶段402时将检测高优先级请求变量308被设定。较新的线程可然后将分配令牌306设为等于在高优先级请求变量308中识别的ATN。这将允许最旧的终止的线程通过依次开始阶段400重新 前进并接收新的specID。将关于图6更详细地?#33268;?#35813;方法。
参照图6,?#22659;?#34920;示重运行和重试冲突(即,终止)的线程时的SMP运行时间的操作的状态图600。作为例子,将关于一组线程T0、T1、T2和T3?#33268;?#29366;态图600。假定T0首先被分配602具有ATN=0的工作单元,然后,线程在步骤604中通过轮询分配令牌306等待。当线程T0检测到分配令牌306等于线程的ATN时,线程T0检查用于分配的高优先级请求308。假定高优先级请求308不被设定,线程T0接收610specID并更新612分配令牌306(即,增加分配令牌306以允许下一线程T1(ATN=1)进入依次开始阶段400并接收specID)。
一旦线程T0更新612分配令牌306,线程T0就开始处理614其工作单元。假定线程T0完成其工作单元,线程T0等待616以提交618工作单元(即,使得其永久)。等待616可包含等待616提交令牌310等于线程的ATN,由此授权线程T0提交618其工作单元。作为替代方案,线程T0可在处理614其工作单元时经历冲突,这会使得?#24067;?#20013;断产生并被发送到内核624。在这种情况下,线程T0可前进到步骤626并等待终止。等待626终止可包含等待626提交令牌310等于线程的ATN,使得线程T0可终止并返回步骤604,在该步骤604中,它可等待重试其工作单元。如果提交令牌310增加以等于线程的ATN由此允许其终止,那么线程T0将获知它是最旧的终止的线程。即,线程T0将获知具有比线程T0的ATN低的ATN的线程将成功地被提交,原因是提交令牌310增加以等于线程T0的ATN。在本说明书中,“最旧的终止的线程”被定义为ATN等于提交令牌310的终止的线程。这是十分重要的,原因是只有最旧的终止的线程被允许设定高优先级请求308。在线程T0是最旧的终止的线程的情况下,线程T0将设定620用于分配的高优先级请求308等于其ATN并返回步骤604,在该步骤604中,它可等待重试其工作单元。
另一方面,如果线程T0在不经历冲突的情况下完成其工作单元,那么线程T0可前进到步骤616,在该步骤616中,它可等待提交令牌310等于其ATN并由?#31169;?#25910;用于提交618其工作单元的授权。如果提 交令牌310等于线程T0的ATN并且线程T0能够成功地提交其工作单元,那么线程T0可更新(即,增加)提交令牌310并返回步骤602,在该步骤602中,它可接收新的ATN和相关的工作单元。线程T0可然后以前?#23159;?#36848;的方式通过新的工作单元通过状态图600前进。
另一方面,如果提交令牌310等于线程T0的ATN但线程T0不能成功提交其工作单元,那么线程T0可设定用于分配的高优先级请求308等于其ATN。如上所述,设定高优先级请求308可指示线程T0希望重试其工作单元并由此愿意减小分配令牌306以使其等于其ATN。线程T0可然后返回步骤604以等待重试其工作单元。
当最旧的终止的线程终止并且设定高优先级请求308时,所有比最旧的终止的线程更新的线程将终止(如果它们还没有)并返回步骤604,原因是这些线程需要重新依次开始和提交。例如,假定线程T0在步骤616或步骤626中终止并设定620高优先级请求308。并且假定,到线程T0终止并设定高优先级请求308为止,较新的线程T1(ATN=1)和T2(ATN=2)已通过依次开始阶段400并接收了specID,由此允许它们处理它们的工作单元。并且假定线程T3(ATN=3)在步骤604上等待进入依次开始阶段400。当分配令牌306增加到3时,线程T3将进入依次开始阶段400并检查606用于分配的高优先级请求308。在本例子中,线程T3将看到高优先级请求308被设为线程T0的ATN。在进行这种观察时,线程T3将分配令牌?#26723;?08到0(即,T0的ATN)、清除608高优先级请求308并返回步骤604。当分配令牌306下?#26723;?时,线程T0(在步骤604?#26800;?#24453;)将检测到其ATN等于分配令牌306并且再进入依次开始阶段400,由?#31169;?#25910;新的specID。
当分配令牌306下?#26723;?时,先前已通过依次开始阶段400并接收了specID的线程T1和T2将处理614它们的工作单元、在步骤616?#26800;?#24453;提交它们的工作单元或者在步骤626?#26800;?#24453;终止它们的工作单元。在终止和设定高优先级请求308时,线程T0可使这些线程的specID无效化。这将使得对于线程T1和T2产生?#24067;?#20013;?#24076;?#30001;?#31169;?#32447;程T1和T2到重运行到开?#23478;?#27425;开始阶段400(即,步骤604)的开始。当分 配令牌306增加为高于0时,这些线程将然后依次重试。作为替代方案,线程T1和T2可被配置为检测分配令牌306什么时候低于它们的ATN,并且作为响应,返回步骤604以重?#36816;?#20204;的工作单元。
?#22659;?#30340;方法600具有这样一种益处,即,由于在?#25105;?#26102;间只有一个线程可通过依次开始阶段400,因此,不需要锁定分配令牌306。只有通过依次开始阶段400的线程可修改分配令牌306。通过依次开始阶段400的线程将增加分配令牌306,或者,如果高优先级请求308被设定,则将分配令牌306设为在高优先级请求308中识别的ATN值。这不需要共享的锁定并防止分配令牌306上的急流。在线程是最旧的终止的线程并且所有其它的线程已通过依次开始阶段400前进的情况下,最旧的终止的线程在这种情况下可被允许修改分配令牌306以等于其ATN,并由此重试其工作单元。
公开的?#38469;?#20351;得明显的性能提高,并且更容易调试。这是由于内核可通过将较新的线程的无效性留给SMP运行时间304,而保持最小化。
在某些实施例中,为了使分配的specID的数量最少化,SMP运行时间304可被配置为推测地运行最旧的线程。最旧的线程可具有直?#26377;?#25913;主存储器104c的特权,而不是在L2高速缓存202中缓存。在?#25105;?#32473;定的时间,只有单个线程可被允许非推测地运行。已推测地运行或者由于已获得specID要推测地运行的线程,即使变为最旧的线程,也可以不切换到非推测地行动。这是由于,非推测地运行的决定可在分配阶段404内进行,并且不能在后面的时间改变。
一般参照图7~9,在某些实施例中,关于图3~6?#33268;?#30340;SMP运行时间304可被修改以使存储器流量最小化。关于图3~6?#33268;?#30340;SMP运行时间304使用全局令牌306、310以实现静态调度方案。调度方案是静态的,原因是线程的执行的次序是已知的-即,各线程具有固定的前任和后任线程。即,如果线程执行具有ATN的工作单元,那么下一线程将执行具有ATN+1的工作单元。通过使用全局令牌以协调这种线程的执行,虽然是功能上的,也可能不是在所有的计算结构中 ?#38469;?#26368;佳或必须的。
例如,在诸如图2所示的SMP计算系统100中,各处理器核心102a~c共享同一L2高速缓存202。各处理器核心102支持给定数量N(例如,4个)?#24067;?#32447;程,使得特定的核心102的各?#24067;?#32447;程共享核心的L1高速缓存200。一旦核心102上的线程?#30424;?#20840;局令牌306、310,轮询令牌306、310的其它核心102上的线程将使得它们在令牌306、310的本地(L1高速缓存)复制无效化。线程然后会均在大致相同的时间遭受L1错失,由此使得到L2高速缓存202的流量的浪涌取得更新的令牌306、310。
在某些实施例中,SMP运行时间304可被设计?#21592;?#20813;这种流量浪涌或者使其最小化,特别是在执行线程的次序不清楚的情况下。在本申请中,分配的次序是已知,并且,当令牌被更新时,只需要获知单个?#24067;?#32447;程(即,下一?#24067;?#32447;程)和核心102,使得它可被分配specID。图7~9公开避免以上?#33268;?#30340;流量浪涌或者使其最小化的SMP运行时间304的替代性实施例。本实施例利用分布的令牌以确保依次开?#23478;约?#20381;次线程提交,同时仍消除在常规的实现中使用的锁定要求或者使其最小化。本实施例,作为对于所有的?#24067;?#32447;程使用单个全局分配令牌306和单个全局提交令牌310的替代,对于各线程700使用全局分配令牌702和本地提交令牌706。即,各线程700具有其自身的分配令牌702和提交令牌706。以下更详细地描述使用令牌的方式。
关于图7~9?#33268;?#30340;分布令牌方案明显提高性能。例如,考虑使用在图3~6中公开的方案的16核心Blue Gene/Q处理器的较差情况的方案,这里,各核心具有四个?#24067;?#32447;程。假定核心0上的线程?#30424;?#20196;牌并且核心15上的线程是后任,那么核心15上的线程的全局令牌的无效化的L1复本会取(4循环×14)?#21592;?#24471;被更新。这假定核心1~14在核心15之前请求更新的全局令牌。
平均而言,对于Blue Gene/Q处理器,如果来自后任线程的请求离其前任线程7个核?#27169;?#37027;么更新全局令牌的平均等待时间为7×4循环。相反,使用在图7~9描述的分布令牌方案,观察更新令牌的等待 时间从平均28个循环减少到4个循环。可能对于分配令牌和提交令牌均观察到这种等待时间减少。在图7~9中公开的分布令牌方案是在图3~6中公开的全局令牌方案的自然?#30001;臁?
图7表示使用用于确保依次开?#23478;约?#20381;次提交线程700a~c的分布令牌方法的SMP运行时间304的一个实施例。如图所示,使用分布令牌方法,各线程700被分配其自身的本地分配令牌702和提交令牌706。另外,各线程700被分配先前本地分配令牌704、“终止”标签708、“最旧终止”标签710和“较新线程杀死?#20445;╕TK)标签712。这些令牌702、704、706和标签708、710和712作为例子而不是限制被给出。以下更详细地描述使用这些令牌和标签的方式。在该特定的实施例中,SMP运行时间304还使用全局高优先级(“hipri?#20445;?#35831;求714和全局阈值716。阈值716可被设为比SMP计算系统100中的线程数大的?#25105;?#20540;。
参照图8,?#22659;?#34920;示使用分布令牌方法的SMP运行时间304的操作的状态图800。状态图800基于与图6的状态图600相同的静态调度方案。在图6的状态图600中,全局分配令牌306可采取范围为从0到ATN的数量减1的值。相反,在图8的状态图800中,即使在重运行环境下,线程的本地分配令牌702也总是增加。并且,与图6的状态图600不同,线程的本地分配令牌702不与其ATN相比较。事实上,如以下更详细地解释的那样,线程的本地分配令牌702与其前面的本地分配令牌704相比较。简言之,线程将在线程的本地分配令牌702与其前面的本地分配令牌704之间的差值为非零时接收specID。
如图8所示,“等待开始”状态806被用于使新近的(fresh)开始线程(即,还没有终止的线程)与重运行线程(即,已终止线程)同步化。由于“等待开始”状态806管理新近的开始线程和重运行线程,因此,用于?#27704;搿?#31561;待开始”状态806的条件比?#27704;?#22270;6所述的“等待开始”状态604所需要的明显更复?#21360;?#20197;下关于图9描述?#27704;搿?#31561;待开始”状态806的条件。
参照图9,同时继续一般参照图8,?#22659;?#34920;示由“等待开始”状态 806上的线程执行的方法900的流程图。如图所示,在“等待开始”状态806上,线程首先检查902其“终止”标签708是否被设定(指示线程是重运行线程,而不是新近的开始线程)?#32422;?#20854;提交令牌706是否等于其ATN(指示,如果是重运行线程,则它是否是最旧的终止的线程)。如果两个条件均成立,那么线程设定904其“最旧终止”标签710(指示线程是最旧的终止的线程)并且前进到步骤906。如果线程确定步骤902中的条件中的一个或多个不成立,则线程直接前进到步骤906。
在步骤906中,线程检查其“最旧终止”标签710是否被设定?#32422;?#39640;优先级请求714是否被设为-1(在本公开中,-1的值指示高优先级请求714不被设定-即,没有线程请求分配)。如果两个条件均成立,则线程将高优先级请求714设为其?#24067;?#32447;程ID并且前进到步骤910。如果步骤906中的条件中的一个或多个不成立,则线程直接前进到步骤910。
在步骤910中,线程检查其“最旧终止”标签710是否被设定(指示它是最旧的终止的线程)?#32422;?#20854;“较新线程杀死?#20445;╕KT)标签是否被设定(指示比最旧的终止的线程更新的线程还没有被“杀死”或者无效化)。如果两个条件均成立,那么线程(即,最旧的终止的线程)使比自身更新的所有线程的specID无效化(即,“杀死?#20445;?#32447;程然后设定912其YTK标签712以指示所有较新线程被杀死。线程然后前进到步骤914。如果步骤910中的条件中的?#25105;?#20010;被评价为不成立,那么线程直接到步骤914。
步骤914在这里被称为“?#27704;?#26465;件”。即,如果线程满足在步骤914中规定的条件,那么线程被允许?#27704;搿?#31561;待开始”状态806并前进到状态图800的其它步骤。如上所述,由于?#27704;?#26465;件914被设计为使新近的开始线程与重运行线程同步化,因此,?#27704;?#26465;件914有些复?#21360;?#22914;图9的?#27704;?#26465;件914所示,如果线程的本地分配令牌702不等于其前面的本地分配令牌704且线程的“终止”标签708不被设定或者线程的“最旧终止”标签710被设定或者线程的本地分配令牌702 减去其本地分配令牌704大于前面?#33268;?#30340;阈值716,那么线程将其前面的本地分配令牌704设定916为其本地分配令牌702的当前值并且?#27704;?16“等待开始”状态806。否则,线程保持在“等待开始”状态806并且返回方法900的顶部以重复方法步骤。
重新参照图8,现在?#33268;?#21253;括新近的开始线程(不是重运行线程)的方案,原因是它与状态图800有关。一般地,新近的开始线程将在开始状态802上(如果它还没有处理工作单元)或者在步骤834上(如果它已成功处理工作单元)开始。新近的开始线程然后将在步骤804中接收工作单元和相关的ATN并前进到“等待开始”状态806。如果不存在可用的工作,那么新近的开始线程移动到结束状态805。在“等待开始”状态806上,新近的开始线程循环,直到其本地分配令牌702与其前面的本地分配令牌704不同(由此满足?#27704;?#26465;件914)。当?#27704;?#26465;件914被满足时,线程将其前面的本地分配令牌704设为其本地分配令牌702的当前值(有效地捕获线程的本地分配令牌702的当前值)并?#27704;搿?#31561;待开始”状态806。新近的开始线程然后前进到步骤808,在该步骤808中,线程确定高优先级请求714是否被设为-1。在本公开中,被设为-1的高优先级请求714指示没有线程重运行(即,终止)并且正在请求specID。相反,被设为-1以外的值的高优先级请求714指示线程已重运行并且正在请求specID。
假定高优先级请求714被设为-1(即,没有重运行线程)。在这种情况下,新近的开始线程前进到步骤816以接收specID。新近的开始线程然后进到步骤818。由于本例子中的线程不是最旧的终止的线程,因此,新近的开始线程前进以将下一线程的本地分配令牌702设为820新近的开始线程的本地分配令牌702加1。这将在下一线程的本地分配令牌702与其前面的本地分配令牌704之间产生非零差,由此允许它?#27704;搿?#31561;待开始”状态806并接收specID。以这?#22336;?#24335;,接收specID的各线程可使得下一线程?#27704;搿?#31561;待开始”状态806并接收specID,由此确保线程依次开始。
在步骤824中,新近的开始线程开始处理824其工作单元。当工 作单元完成时,新近的开始线程前进到“等待提交”状态826,在这里,它可等待提交在步骤24中执行的工作。一般地,线程将在“等待提交”状态826?#26800;?#24453;,直到其提交令牌706被设为等于其ATN的值。当其提交令牌706等于其ATN时,线程将离开“等待提交”状态826并提交832其工作单元。假定提交成功,那么新近的开始线程将下一线程的提交令牌706设定834为新近的开始线程的ATN值加1。这允许具有下一ATN值的线程提交其工作单元。在这?#22336;?#24335;,线程将依次提交。在步骤834中设定下一线程的提交令牌706之后,线程将返回步骤804,在这里,它将接收新的工作单元和相关的ATN。如果没有工作单元可用,那么线程将前进到最终状态805。
如果当在步骤824中处理其工作单元的同时线程经历使得?#24067;?#20013;断产生并发送到内核828的冲突,那么线程将中断处理(即,终止)并设定828其“终止”标签708。线程然后返回“等待开始”状态806,在这里,它将等待?#27704;?#24182;接收新的specID,由此允许它重试其工作单元。类似地,如果步骤832上的线程无法提交其工作单元,那么线程将终止,设定836其“终止”标签708,并且返回“等待开始”状态806。
类似地,在线程在步骤826?#26800;?#24453;提交时,线程可通过另一线程被无效化。例如,最旧的终止的线程可使比最旧的终止的线程更新的所有线程无效化以确保线程重新开始并依次提交。如果在等待“等待提交”状态826的同时,线程确定其specID被无效化(参见步骤830),那么线程将终止,设定836其“终止”标签708并返回“等待开始”状态806,在这里,它可重试其工作单元。
为了理解?#24065;?#20010;或多个线程终止并且返回“等待开始”状态806时出现什么,考虑包含五个线程T0、T1、T2、T3和T4的方案。作为例子,假定线程T0成功地完成其工作单元,而线程T1、T2和T3接收specID但在提交它们的工作单元之前终止。并且,假定线程T4还没有接收specID。在本例子中,线程T1会是最旧的终止的线程。
在该方案中,假定线程T1终止并返回“等待开始”状态806。在 通过图9所示的步骤902、906、910之后,当线程T0设定T1的提交令牌等于其ATN时,线程T1将确定它是最旧的终止的线程。线程T1然后将设定904其“最旧终止”标签710,由?#31169;?#20854;自身确定为最旧的终止的线程。线程T1还将高优先级请求714设为其?#24067;?#32447;程ID并使较新的线程T2和T3无效化,由此使得这些线程终止并返回“等待开始”状态806(假定它们还没有终止并?#26131;?#36523;返回“等待开始”状态806)。在使较新的线程T2和T3无效化时,线程T1设定其YTK标签712以指示较新的线程被无效化。
在这一点上,线程T1、T2和T3均等待“等待开始”状态806以重?#36816;?#20204;的工作单元。假定线程T4的本地分配令牌702被设为与其前面的本地分配令牌704不同的值,由此允许T4?#27704;搿?#31561;待开始”状态806。在?#27704;搿?#31561;待开始”状态806时,T4将在步骤808上观察高优先级请求714被设为-1以外的值。线程T4可然后确定810它是否是在高优先级请求714中识别的?#24067;?#32447;程。如果它不是在高优先级请求714中识别的线程(在本例子中是这种情况),那么线程T4将在高优先级请求714中识别的线程(在本例子中为线程T1)的本地分配令牌702设为其(即,T4的)本地分配令牌702的值加1。这允许线程T1?#27704;搿?#31561;待开始”状态806并接收816specID。线程T4然后将返回“等待开始”状态806并等待其接收specID并处理其工作单元的机会。
当线程T1在“等待开始”状态806中观察到其本地分配令牌702与其前面的本地分配令牌704不同并且其“最旧终止”标签710被设定时,T1将?#27704;搿1将然后观察808高优先级请求714被设为其?#24067;?#32447;程ID。T1将清除高优先级请求714(通过将高优先级请求714设为-1)。线程T1将然后前进以接收specID。由于T1是最旧的终止的线程,因此它通过将线程T2的本地分配令牌702设定822为其(即,T1的)本地分配令牌702加前面?#33268;?#30340;阈值716,而开始分配新一代的令牌。
当线程T2看到其本地分配令牌702减其前面的本地分配令牌704大于阈值716时,它将?#27704;搿?#31561;待开始”状态806并接收816specID。 线程T2然后将线程T3的本地分配令牌702设为线程T2的本地分配令牌702加1。线程T3然后将看到其本地分配令牌702减去其前面的本地分配令牌704大于阈值716。在响应中,线程T3将?#27704;搿?#31561;待开始”状态806并接收specID。线程T3然后将线程T4的本地分配令牌702设为线程T3的本地分配令牌702加1。线程T4然后将?#27704;搿?#31561;待开始”状态806,原因是其“终止”标签708不被设定并且其本地分配令牌702不等于其前面的本地分配令牌704。线程T4?#21830;?#20195;性地?#27704;耄?#21407;因是其本地分配令牌702减其前面的本地分配令牌704大于阈值716。在?#25105;?#30340;情况下,假定存在更多的要完成的工作,线程T4接收specID并将分配令牌?#31361;?#32447;程T0。
从以上的?#33268;?#21487;以看出,?#27704;?#26465;件914成功地使新近的开始线程?#32422;?#32456;止的线程(即,具有它们设定的“终止”标签708的线程)同步化。?#27704;?#26465;件914进一步被配置为识别最旧的终止的线程,使得较新的线程可被无效化。
图8所示的状态图800的其它特征是?#26723;?#27880;意的。例如,在清除高优先级请求714(即,将高优先级请求714设为-1)之后,在步骤814中执行“msync?#20445;?#23384;储器同步化)。该msync被执行,使得系?#25345;?#30340;所有线程在分配转到下一线程(通过设定下一线程的本地分配令牌702)之前观察到高优先级请求714的清除。这是由于,如果下一线程错误地观察到高优先级请求714被设定,那么下一线程可立即将分配转回当前的线程,由此使得死锁。在一些计算结构(例如,PowerPC基础结构)中,可能需要在步骤808的开始执行“isync?#20445;?#25351;令同步化)以确保在离开处理900之后从存储器加载高优先级请求714。这是由于Power PC基础结构具有从存储器失序执行负载的能力。Isync指令用作防止出现这种情况的防护。
另一?#26723;?#27880;意的特征是,在状态图800中,最旧的终止的线程被配置为在步骤814中清除高优先级请求714。这是由于,所有的其它的线程可能已通过分配点,并且,作为结果,最旧的终止的线程需要设定?#32422;?#28165;除高优先级请求714。如果在系?#25345;?#23384;在承认通过将分配 令牌转回最旧的终止的线程设定高优先级请求714的另一较新的线程,那么最旧的终止的线程也应清除高优先级请求714。
类似于图6所示的状态图600,?#22659;?#30340;状态图800减少或消除原子操作的需要。所有对于变量的更新均由单个线程执行。这不需要在特定的变量上共享锁定?#32422;?#38450;止其上面的急流。
附图中的框?#38469;境?#26681;据本发明的各种实施例的系统、方法和计算机可用存储介质的可能的实现的结构、功能和操作。关于这一点,框图中的各块可代表包含用于实?#27490;?#23450;的逻辑功能的一个或多个可执行指令的代码的模块、段或部分。还应注意,在一些替代性的实现中,关于块?#33268;?#30340;功能可以按?#33268;?#30340;次序以外的次序出现。例如,连续出现的两个功能事实上根据包括的功能可以按相反的次序被执行。还应注意,可通过执行特定功能或作用的基于特殊用途?#24067;?#30340;系统或者特殊用途?#24067;?#21644;计算机指令的组合,实现框图的各块和框图的块的组合。

关于本文
本文标题:通过使用分布的令牌有效地重运行和重试冲突的推测线程.pdf
链接地址:http://www.pqiex.tw/p-6115829.html
关于我们 - 网?#26087;?#26126; - 网站地图 - ?#35797;?#22320;图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
平码五不中公式规律 极速快3开奖历史记录 六人升级棋牌规则 3d组三遗漏周期 浙江11选5推荐专家 三分彩开奖号码 体彩新疆11选5开奖结 澳洲幸运8开奖时间 极速快3app 甘肃11选5专家预测 分分彩计划软件下载