障碍同步电路、障碍同步方法以及并行信息处理装置

摘要

提供了障碍同步电路、障碍同步方法以及并行信息处理装置。一种障碍同步电路，其对由多个处理电路并行执行的多个处理执行障碍同步，该障碍同步电路包括：第一确定电路，其被配置成确定多个处理电路中已经完成处理的第一处理电路的数目是否等于或大于第一阈值；以及指示电路，其被配置成在通过第一确定电路确定该数目等于或大于第一阈值的情况下，指示多个处理电路中尚未完成处理的第二处理电路强制停止处理。

说明书

技术领域

本文所讨论的实施方式涉及障碍同步电路、障碍同步方法以及并行信息处理装置。

背景技术

在多个处理单元执行并行处理的同时彼此同步的并行信息处理装置中，存在障碍同步作为彼此同步的方法。此处，处理单元是用于使用处理装置的单元。例如，中央处理单元(CPU)的核是处理装置，并且线程是处理单元。并行信息处理装置具有多个核，并且每个核执行所分配的线程。

图7是用于说明障碍同步的图。在图7中，在线程#1至#n(n是2或大于2的整数)中并行执行第i(i是1或大于1的整数)个处理，并且最晚的处理在线程#n中完成。如图7所示，在障碍同步中，除了最晚的线程#n以外的线程等待直至第i个处理在线程#n中完成，并且当第i个处理在线程#n中完成时，第(i+1)个处理在线程#1至#n中启动。

作为相关技术的技术，存在当执行近似计算时从过度近似计算误差中恢复的处理器。该处理器包括：存储装置，其被配置成在近似中执行一组计算之前接收处理器的状态的快照；以及指示符，其指示在近似中执行该组计算时累积的误差的量。当处理器检测到所累积的误差的量超过误差限制时，将处理器的状态从存储恢复到快照。

[引文列表]

[专利文献]

[专利文献1]国际专利申请的日本国家公布第2016-524748号

发明内容

[技术问题]

在图7所示的障碍同步中，存在如下问题：首先完成处理的处理单元(线程)等待直至所有剩余的处理单元完成该处理。

根据本公开内容的一方面，目的是减少处理单元在障碍同步中的等待时间并提高处理速度。

[问题的解决方案]

一方面，一种障碍同步电路，其对由多个处理电路并行执行的多个处理执行障碍同步，该障碍同步电路包括第一确定电路和指示电路。第一确定电路被配置成：确定多个处理电路中已经完成处理的第一处理电路的数目是否等于或大于第一阈值，并且指示电路被配置成：在通过第一确定电路确定该数目等于或大于第一阈值的情况下，指示多个处理电路中尚未完成处理的第二处理电路强制停止该处理。

另一方面，一种障碍同步电路，其对由多个处理电路并行执行的多个处理执行障碍同步，该障碍同步电路包括第一确定电路和指示电路。第一确定电路确定自多个处理电路中的任一处理电路完成处理起经过的时间是否等于或大于第一阈值。指示电路在通过第一确定电路确定该经过的时间等于或大于第一阈值的情况下指示未完成处理的处理电路强制停止该处理。

[本发明的有益效果]

一方面，本公开内容可以提高处理速度。

附图说明

图1是用于说明根据示例的AC并行化的图；

图2是示出根据示例的并行信息处理装置的配置的图；

图3是示出AC单元的配置的图；

图4A是示出用于指定AC并行化的程序的示例的图；

图4B是示出用于指定AC并行化的程序的示例的图；

图5是示出设置电路确定阈值m的处理的流程的流程图；

图6是示出设置电路确定阈值c的处理的流程的流程图；以及

图7是用于说明障碍同步的图。

具体实施方式

在下文中，将参照附图详细描述在本申请中公开的障碍同步电路、障碍同步方法以及并行信息处理装置的示例。这些示例不限制所公开的技术。

首先，将描述根据示例的近似计算(AC)并行化。图1是用于说明根据示例的AC并行化的图。在图1中，寄存器指示n个线程的处理状态。与完成了处理的线程相对应的位为1，并且与未完成处理的线程相对应的位为0。

如图1所示，在根据示例的AC并行化中，当在n个线程中的m(1≤m

如以上所描述的，在根据实施方式的AC并行化中，障碍同步电路强制停止未完成处理的(n-m)个线程，并且不等待这(n-m)个线程完成处理。因此，可以缩短等待时间并提高处理速度。在允许一定程度的误差的优化问题例如LSI布置及布线问题、光刻图案创建问题以及递送计划问题中，可以通过根据本示例的AC并行化来提高处理速度。例如，在遗传算法(GA)中，当通过n个线程并行执行用于在第i个处理中生成第i代的个体的处理时，准确度由于在每一代中强制停止(n-m)个线程而降低，但是处理速度提高。

接下来，将描述根据实施方式的并行信息处理装置的配置。图2是示出根据实施方式的并行信息处理装置的配置的图。如图2所示，根据实施方式的并行信息处理装置100包括CPU 1和主存储器2。CPU 1是执行程序的中央处理单元。主存储器2是存储由CPU 1执行的程序以及在程序中使用的数据的随机存取存储器(RAM)。并行信息处理装置100可以包括多个CPU 1和多个主存储器2。

CPU 1包括AC单元10、n个核20、n个L1高速缓存30以及L2高速缓存40。AC单元10耦接至每个核20。每个核20耦接至对应的L1高速缓存30。每个L1高速缓存30耦接至L2高速缓存40。

AC单元10是障碍同步电路并且执行障碍同步，从完成了处理的线程在其处运行的核20向该障碍同步电路通知处理的完成。AC单元10基于模式(mode)执行处理。

当模式为0时，AC单元10不执行AC并行化，而是执行正常的障碍同步。例如，AC单元10等待从所有核20通知处理完成。

当模式为1时，如果从完成了处理的线程在其处运行的核20向AC单元10通知处理完成，则AC单元10确定完成了处理的线程的数目是否等于或大于阈值m。然后，当完成了处理的线程的数目等于或大于阈值m时，AC单元10确定满足同步条件并且向未完成处理的核20发送强制停止信号。

此外，当从第一次完成处理的线程在其处运行的核20向AC单元10通知处理完成时，AC单元10开始对时钟数进行计数。然后，AC单元10确定时钟数是否等于或大于阈值c(c是正整数)。当时钟数等于或大于阈值c时，AC单元10确定满足同步条件并且向未完成处理的核20发送强制停止信号。

当模式为2时，AC单元10收集关于AC并行化的数据。AC单元10收集：时间s，在该时间s处，核20中的任一核第一次完成处理；时间m

核20是执行处理的处理装置。核20执行线程。当线程的处理完成时，核20向AC单元10通知该线程的处理完成。此外，当核20从AC单元10接收到强制停止信号时，核20强制停止线程。然而，核20可以一起接收对线程的处理结果的估计值与强制停止信号。在这种情况下，线程可以使用估计值执行下一处理。

L1高速缓存30是存储在主存储器2中存储的指令和数据中的一些指令和数据的高速缓存。核20从L1高速缓存30读取指令和数据并执行指令。当不存在要由核20访问的指令或数据时，L1高速缓存30从L2高速缓存40获取指令或数据。

L2高速缓存40是存储在主存储器2中存储的指令和数据中的一些指令和数据的高速缓存。与L1高速缓存30的容量和访问速度相比，L2高速缓存40具有较大的容量和较慢的访问速度。当不存在要由L1高速缓存30访问的指令或数据时，L2高速缓存40从主存储器2获取指令或数据。

图3是示出AC单元10的配置的图。如图3所示，AC单元10包括加法电路11、m寄存器电路12、比较电路13、或电路14、c寄存器电路15、计数器电路16、或电路17、P寄存器电路18以及输出电路19。此外，AC单元10包括设置电路51、设置电路52、计时器电路61、时间获取电路62、SME寄存器电路63、读取电路64、k寄存器电路71、读取电路72、模式确定电路81以及初始化电路91。

加法电路11输入在每个核20完成线程的处理的情况下要被设置为1的完成信号，并输出为1的完成信号的数目。在线程的处理未完成的情况下，每个核20将完成信号设置为0。m寄存器电路12存储阈值m。阈值m由程序指定。然而，阈值m可以如稍后所描述的由设置电路51确定。

比较电路13将从加法电路11输出的数目与存储在m寄存器电路12中的阈值m进行比较，并且在从加法电路11输出的数目变得等于或大于阈值m时，向或电路17输出1。当模式信号指示0或2时，在m寄存器电路12中设置n。此处，模式信号是用于指定模式的信号。由模式信号指示的值由模式确定电路81确定。此外，当模式信号指示2时，在从加法电路11输出的数目为1、m或n的情况下，比较电路13向时间获取电路62输出1。

或电路14输入完成信号并输出完成信号的逻辑和。c寄存器电路15存储阈值c。阈值c由程序指定。然而，阈值c可以如稍后所描述的由设置电路52确定。

当模式信号指示1时，计数器电路16在或电路14的输出为1时开始对时钟进行计数。然后，计数器电路16将计数值与存储在c寄存器电路15中的阈值c进行比较，并且在计数值为阈值c时向或电路17输出1。

或电路17将比较电路13的输出与计数器电路16的输出的逻辑和输出。P寄存器电路18针对每个核20存储从核20输出的完成信号。

当或电路17的输出为1时，输出电路19基于P寄存器电路18向未完成处理的核20发送强制停止信号。输出电路19可以一起发送对处理结果的估计值与强制停止信号。例如，AC单元10存储过去的执行结果和执行结果的平均值，并且输出电路19将过去的执行结果的平均值作为估计值发送。

此外，输出电路19将被指示强制停止的线程的编号与障碍同步的次数相关联地累积在k寄存器电路71中。例如，输出电路19通过将从每个核20通知的线程编号与核20相关联地存储来根据P寄存器电路18指定线程编号。

设置电路51输入m信号并在m寄存器电路12中设置阈值m。此处，m信号是指示阈值m的信号。当模式信号指示0或2时，设置电路51基于来自模式确定电路81的指令来在m寄存器电路12中设置核20的数目n。

设置电路52输入c信号并在c寄存器电路15中设置阈值c。此处，c信号是指示阈值c的信号。

计时器电路61在障碍同步的情况下对时间进行计数。一旦从比较电路13接收到1，则时间获取电路62从计时器电路61获取时间，并将该时间存储在SME寄存器电路63中。SME寄存器电路63存储时间s、时间m

k寄存器电路71将输出电路19指示强制停止的线程的编号作为强制停止线程编号与障碍同步的次数相关联地存储。读取电路72从k寄存器电路71每次读取强制停止线程编号，并输出强制停止线程编号。

模式确定电路81输入模式信号并确定由模式信号指示的值。然后，当由模式信号指示的值为1时，模式确定电路81操作计数器电路16。此外，当由模式信号指示的值为0或2时，模式确定电路81指示设置电路51在m寄存器电路12中设置n。此外，当由模式信号指示的值为2时，模式确定电路81向比较电路13通知模式为2。

初始化电路91输入初始化信号，将P寄存器电路18初始化为0，并且启动计时器电路61。当线程的并行处理启动时生成初始化信号。

图4A至图4B是示出用于指定AC并行化的程序的示例的图。图4A示出了未指定AC并行化的程序，并且图4B示出了指定了AC并行化的程序。如图4B所示，阈值m和阈值c由set_AC_parameter(m,c)指定。此外，AC并行化的位置和模式由start_AC_region(mode)和end_AC_region(mode)指定。此外，时间s、时间m

此外，通过set_AC_parameter(m,c)生成m信号和c信号，并且基于m信号和c信号在m寄存器电路12和c寄存器电路15中设置阈值m和阈值c。此外，通过start_AC_region(mode)生成模式信号和初始化信号，基于该初始化信号对P寄存器电路18进行初始化，并且启动计时器电路61。

代替通过程序指定阈值m和阈值c，设置电路51和设置电路52可以分别确定阈值m和阈值c。图5是示出设置电路51确定阈值m的处理的流程的流程图，并且图6是示出设置电路52确定阈值c的处理的流程的流程图。

如图5所示，设置电路51将n设置给m，指示核20执行线程(步骤S1)，并且获取准确度A(步骤S2)。然后，设置电路51接收准确度a

然后，设置电路51确定a

另一方面，当a

如以上所描述的，由于设置电路51确定阈值m，因此AC单元10可以优化AC并行化功能。图5中示出的处理可以由AC单元10外部的装置执行，并且AC单元10可以接收由外部装置确定的阈值m。

如图6所示，设置电路52测量第一线程完成时的时钟数c

然后，设置电路52确定a

另一方面，当a

如以上所描述的，由于设置电路51确定阈值c，因此AC单元10可以优化AC并行化功能。图6中示出的处理可以由AC单元10外部的装置执行，并且AC单元10可以接收由外部装置确定的阈值c。

如以上所描述的，在本实施方式中，比较电路13将完成了处理的核20的数目与阈值m进行比较，并确定完成了处理的核20的数目是否等于或大于阈值m。然后，当完成了处理的核20的数目等于或大于阈值m时，输出电路19向未完成处理的核20发送强制停止信号。因此，AC单元10可以减少障碍同步中的等待时间并提高处理速度。

此外，在本实施方式中，当模式为1时，计数器电路16确定自核20中的任一核第一次完成处理起经过的时间是否等于或大于阈值c。然后，当自核20中的任一核第一次完成处理起经过的时间等于或大于阈值c时，输出电路19向未完成处理的核20发送强制停止信号。因此，AC单元10可以减少障碍同步中的等待时间并提高处理速度。

此外，在本实施方式中，模式确定电路81确定模式，并指示设置电路51在模式为1的情况下操作计数器电路16，并且在模式为0或2的情况下将n设置到m寄存器电路12。此外，在模式为2的情况下，模式确定电路81向比较电路13通知模式为2。因此，模式确定电路81可以基于模式来控制AC单元10的操作。

此外，在本实施方式中，m寄存器电路12存储阈值m，并且设置电路51确定阈值m的最优值并在m寄存器电路12中设置最优值。此外，比较电路13将存储在m寄存器电路12中的阈值m与通知完成的核20的数目进行比较。因此，AC单元10可以优化AC并行化功能。

此外，在本实施方式中，c寄存器电路15存储阈值c，并且设置电路52确定阈值c的最优值并在c寄存器电路15中设置最优值。此外，计数器电路16将存储在c寄存器电路15中的阈值c与自第一次接收到处理的完成通知起经过的时间进行比较。因此，AC单元10可以优化AC并行化功能。

此外，在本实施方式中，k寄存器电路71将强制停止线程编号与障碍同步的次数相关联地存储，并且读取电路72从k寄存器电路71读取强制停止线程编号和障碍同步的次数并将其输出。因此，AC单元10可以提供对分析AC并行化功能有用的信息。

此外，在本实施方式中，输出电路19向被指示强制停止的线程发送线程的处理结果的估计值，因此，AC单元10可以在不减少线程数目的情况下提供AC并行化功能。

此外，在本实施方式中，SME寄存器电路63存储时间s、时间m

在本实施方式中，描述了将线程分配给核20的情况。然而，可以代替线程将其他处理单元例如处理分配给核20。可替选地，可以代替核20将线程分配给其他处理装置例如处理器或CPU。在将线程分配给CPU的情况下，并行信息处理装置包括多个CPU，并且AC单元被设置在CPU的外部。

此外，在本实施方式中，在模式为1的情况下，描述了比较电路13和计数器电路16两者均进行操作的情况，但是可以细分模式为1的情况。例如，可以提供3种模式，即仅比较电路13进行操作的模式、仅计数器电路16进行操作的模式以及比较电路13和计数器电路16两者均进行操作的模式。