本文中论述的实施方式涉及屏障同步系统、并行信息处理设备和用于存储屏障同步程序的非暂态计算机可读存储介质。
背景技术：
在由多个信息处理设备并行处理多个处理单元的并行处理系统中，存在作为使所述多个处理单元同步的方法的屏障同步。此处，处理单元是使用信息处理设备的单元，并且是例如进程。
图13是用于描述屏障同步的图。图13中，进程#1至进程#n并行执行第i处理，并且进程#n完成最后的处理。如图13所示，在屏障同步中，除了最后的进程#n以外的进程等待，直到进程#n完成第i处理，并且当进程#n完成第i处理时，进程#1至进程#n开始第(i 1)处理。
图14是用于描述屏障同步中在信息处理设备之间的通信的图。在图14中，通过p表示的节点是用于执行屏障同步的进程操作的信息处理设备。如图14所示，用于执行屏障同步的进程操作的信息处理设备形成二叉树。当二叉树中的最下层处的信息处理设备自身完成进程的处理时，如通过实线所示，将完成通知发送至主信息处理设备。第二层或更高层处的信息处理设备在自身完成进程的处理并且所有下级信息处理设备的完成通知可用时，如通过实线所示，将完成通知发送至主信息处理设备。
最上级处的信息处理设备从所有下级信息处理设备接收完成通知，并且其自身完成进程的处理，确定所有信息处理设备完成了进程的处理，并且如通过虚线所示，向所有下级信息处理设备通知处理已完成。被通知处理已完成的信息处理设备开始下一处理。
注意，作为相关技术的技术，存在一种同步处理电路，该同步处理电路通过使用具有树结构的多个节点来执行对多个处理装置中的一部分处理装置或全部处理装置的同步处理。具有树结构的节点包括位于最下级处并且分别对应于所述多个处理装置的多个叶节点、位于最上级处的根节点以及除了根节点和叶节点以外的多个内部节点。在该树结构中，不仅从从节点向主节点通知逻辑值，而且从主节点向从节点通知逻辑值。每个内部节点均具有内部节点选择单元，内部节点选择单元选择是向主节点通知通过对从内部节点的从节点通知的逻辑值执行逻辑运算而获得的逻辑值，还是向主节点通知从主节点通知的逻辑值的取反。
技术实现要素：
[技术问题]
在屏障同步中，存在进程之间的处理时间的差异，因此存在以下问题：首先完成处理的进程等待，直到所有进程的处理完成。
根据本发明的一方面，目的在于在屏障同步中减少等待时间并且提高处理速度。
[问题的解决方案]
根据实施方式的一方面，提供了一种屏障同步系统，该屏障同步系统包括多个信息处理设备，多个信息处理设备被配置成在通过屏障同步进行同步的情况下执行并行处理，每个信息处理设备被配置成作为树结构中的多个节点中的一个节点并且与多个节点中的其他节点中的一个或更多个节点相关联。在示例中，多个信息处理设备中的每一个包括：完成信息存储装置；以及控制电路，其中，各个信息处理设备的完成信息存储装置被配置成存储包括与作为各个信息处理设备的自身设备的处理的完成有关的信息的完成信息，在自身设备与下级信息处理设备相关联的情况下，完成信息还包括与下级信息处理设备的处理的完成有关的信息，下级信息处理设备是多个信息处理设备之一，并且作为树结构中的与自身设备相比的较下级的节点来操作，其中，各个信息处理设备的控制电路被配置成：当各个信息处理设备被配置成作为位于树结构中的根处的根节点来操作时，通过使用完成信息存储装置来获得多个节点中的并行处理的当前状态；确定所获得的并行处理的当前状态是否达到给定条件；响应于指示所获得的并行处理的当前状态达到给定条件的确定结果，通过使用完成信息存储装置从多个信息处理设备中指定信息处理设备，所指定的信息处理设备是尚未完成处理的设备；以及指示所指定的信息处理设备在多个信息处理设备中的所有信息处理设备均已经完成处理之前强制中止处理。
[本发明的有益效果]
根据本发明的一方面，在屏障同步中，可以减少等待时间，并且可以提高处理速度。
附图说明
图1是用于描述根据示例的通过并行处理系统的ac并行化的图；
图2示出了根据示例的并行处理系统的配置；
图3示出了节点的配置；
图4示出了ac单元的功能配置；
图5示出了指定ac并行化的程序的示例；
图6是示出用于确定阈值m的处理的流程的流程图；
图7是示出用于确定阈值c的处理的流程的流程图；
图8是示出当自身节点完成处理时的通知处理的流程的流程图；
图9是示出当从从节点接收到完成通知时的转发处理的流程的流程图；
图10是示出当模式＝1时确定单元的处理的流程的流程图；
图11是示出当从主节点接收到强制中止通知时的转发处理的流程的流程图；
图12示出了网络接口装置的硬件配置的示例；
图13是用于描述屏障同步的图；以及
图14是用于描述屏障同步中在信息处理设备之间的通信的图。
具体实施方式
下文中，将参照附图来详细描述本申请中公开的屏障同步系统、用于屏障同步的方法和并行信息处理设备的示例。注意，该示例不限制本文中公开的技术。
[示例]
首先，将描述根据示例的由并行处理系统进行的近似计算(ac)并行化。图1是用于描述根据示例的由并行处理系统进行的ac并行化的图。在图1中，二叉树处的节点10是执行并行处理的信息处理设备。节点10中的编号是用于标识节点10的编号。节点10的编号为7。
每个节点10的处理状态由1位的位信息表示。位信息“1”指示处理完成，并且位信息“0”指示处理未完成。每个节点10具有指示其自身和与其自身相比的较下级的节点10的处理状态的位向量。根节点10具有保持所有节点10的位信息的位向量。
在图1中，节点#1、节点#2、节点#3和节点#4中的每个节点具有1位的位向量。节点#1、节点#2和节点#3中的每个节点的位向量为(1)，指示自身节点完成了处理。节点#4的位向量为(0)，指示自身节点未完成处理。
节点#5和节点#6中的每个节点具有3位的位向量。节点#5的位向量为(1，1，1)，指示自身节点、节点#1和节点#2完成了处理。节点#6的位向量为(1、1、0)，指示自身节点和节点#3完成了处理，而节点#4未完成处理。
节点#7具有7位的位向量。节点#7的位向量为(1、1、1、1、1、1、0)，指示自身节点10、节点#5、节点#1、节点#2、节点#6和节点#3完成了处理，而节点#4未完成处理。
当完成了处理时，如通过实线所示，二叉树中最下层处的节点10将1设定到位向量，并且向主节点10发送完成通知。在图1中，当完成了处理时，节点#1和节点#2将1设定到位向量，并且向节点#5发送完成通知。当完成了处理时，节点#3和节点#4将1设定到位向量，并且向节点#6发送完成通知。
当完成了处理时，如通过实线箭头所示，第二层或更高层处的节点10将1设定到相应的位向量，并且当存在主节点10时，向主节点10发送完成通知。此外，当从从节点10接收到下级节点10之一的完成通知时，第二层或更高层处的节点10将相应的位向量设定为1，并且当存在主节点10时，向主节点10转发接收到的完成通知。
在图1中，当完成了处理时，节点#5将位向量中的与节点#5相对应的位设定为1，并且向节点#7发送完成通知。此外，当从节点#1或节点#2接收到完成通知时，节点#5将位向量中的与节点#1或节点#2相对应的位设定为1，并且向节点#7转发接收到的完成通知。
当完成了处理时，节点#6将位向量中的与节点#6相对应的位设定为1，并且向节点#7发送完成通知。此外，当从节点#3或节点#4接收到完成通知时，节点#6将位向量中的与节点#3或节点#4相对应的位设定为1，并且向节点#7转发接收到的完成通知。
当完成了处理时，节点#7将位向量中的与节点#7相对应的位设定为1。
当位向量中的1的数目为m或大于m时，如通过虚线箭头所示，根节点10沿二叉树向未完成处理的节点10发送强制中止(杀死)通知。换言之，当位向量中的1的数目为m或大于m时，根节点10将强制中止通知发送至包括其中未完成在受管理的节点10上的处理的节点10的从节点10。此处，受管理的节点10是包括在以自身节点10作为根的部分二叉树中的节点10。接收到强制中止通知的从节点10在处理未完成时中止处理，并且将强制中止通知发送至包括其中对未完成在受管理的节点10上的处理的节点10的从节点10。
在图1中，m为5。由于位向量中的1的数目为5或大于5，因此节点#7将强制中止通知发送至节点#6，节点#6包括其中未完成在受管理的节点10上的处理的节点#4。节点#6将强制中止通知转发至节点#4，节点#4包括其中未完成在受管理的节点10上的处理的节点#4。
如上所述，在根据示例的ac并行化中，当位向量中的1的数目为m或大于m时，根节点10沿二叉树将强制中止通知发送至其中未完成处理的节点10。因此，根据示例的并行处理系统可以在屏障同步中减少等待时间并且提高处理速度。
接下来，下面描述根据示例的并行处理系统的配置。图2示出了根据示例的并行处理系统的配置。如图2所示，根据示例的并行处理系统1包括多个节点10。所述多个节点10耦接至网络2。每个节点10经由网络2执行与连接在二叉树中的节点10的用于屏障同步的通信。
图3示出了节点10的配置。如图3所示，节点10包括存储器11、中央处理单元(cpu)12、网络接口装置13和系统控制单元14。
存储器11是存储程序和在程序的执行期间的结果的随机存取存储器(ram)。cpu12是用于从存储器11读取程序并且执行程序的中央处理单元。
网络接口装置13经由网络2与另一节点10通信。网络接口装置13包括ac单元20。ac单元20执行与屏障同步有关的处理。
系统控制单元14控制整个节点10。例如，系统控制单元14在存储器11与cpu12之间或者在cpu12与网络接口装置13之间交换数据和通知。
图4示出了ac单元20的功能配置。如图4所示，ac单元20包括状态存储单元21、接收单元22、转发处理单元23、发送单元24、阈值存储单元25、确定单元26、时间存储单元27、进程存储单元28、阈值设定单元29、时间读取单元30和进程读取单元31。
状态存储单元21存储位向量。接收单元22在存在从节点10时从从节点10接收完成通知和标识号，并且在存在主节点10时从主节点10接收强制中止通知。此处，标识号是用于标识节点10的编号。然后，接收单元22将接收到的完成通知、标识号和强制中止通知传递至转发处理单元23。
当从系统控制单元14向转发处理单元23通知自身节点10的处理完成时，转发处理单元23将位向量中的与自身节点10对应的位设定为1，并且当存在主节点10时，将自身节点10的标识号和完成通知发送至主节点10。转发处理单元23经由发送单元24发送完成通知和标识号。
当从接收单元22接收到完成通知和标识号时，转发处理单元23将位向量中的与标识号相对应的位设定为1，并且当存在主节点10时，经由发送单元24将完成通知和标识号转发至主节点10。
当从接收单元22接收到强制中止通知时，转发处理单元23参考位向量，并且在自身节点10未完成处理时，指示系统控制单元14中止处理。此外，当从接收单元22接收到强制中止通知时，转发处理单元23参考位向量，并且经由发送单元24将强制中止通知转发至包括其中未完成在受管理的节点10上的处理的节点10的从节点10。当转发强制中止通知时，转发处理单元23向发送单元24指定转发目的地的从节点10的标识号。
发送单元24将从转发处理单元23接收到的完成通知发送至主节点10，并且将强制中止通知发送至其标识号由转发处理单元23指定的从节点10。此外，当自身节点10是根节点10时，发送单元24基于来自确定单元26的指令将强制中止通知发送至从节点10。
当自身节点10为根节点10时，阈值存储单元25存储阈值m和阈值c(c是正整数)。由确定单元26使用阈值m和阈值c。
当自身节点10为根节点10时，确定单元26基于通过程序指定的模式来执行处理。当模式为0时，确定单元26执行正常屏障同步。换言之，当位向量中的所有位均为1时，确定单元26完成处理之间的同步。
当模式为1时，确定单元26执行ac并行化。换言之，确定单元26确定位向量中的1的数目是否为阈值m或大于m，当位向量中的1的数目为阈值m或大于m时，确定满足同步条件，并且强行中止其中未完成处理的进程。
此外，当位向量中的一位首先为1时，确定单元26在s中存储当前时间。注意，此处，时间是由计数器计数的计数。例如，s是寄存器。然后，在当前时间为(s 阈值c)或比(s 阈值c)长时，确定单元26确定满足同步条件，并且强行中止其中未完成处理的进程。
此外，确定单元26将在节点10中操作的被指示强制中止的进程的编号与屏障同步的次数相关联地存储在进程存储单元28中。例如，确定单元26通过存储从每个节点10通知的与节点10相关联的进程号，根据位向量来指定进程号。
当模式为2时，确定单元26收集关于ac并行化的数据。确定单元26收集位向量中的一位首先为1的时间s、位向量中的1的数目为阈值m或大于阈值m的时间mt、以及位向量中的所有位均为1的时间e。例如，所收集的时间s、时间mt和时间e是通过程序检索的。
确定单元26包括第一确定单元26a、第二确定单元26b和中止指示单元26c。当模式为1时，第一确定单元26a确定位向量中的1的数目是否为阈值m或大于阈值m，并且当数目为阈值m或大于阈值m时，第一确定单元26a指示中止指示单元26c强制中止其中未完成处理的进程。
当模式为1时，第二确定单元26b在位向量中的一位首先为1时将当前时间存储在s中。然后，第二确定单元26b确定当前时间是否为(s 阈值c)或比(s 阈值c)长，并且在当前时间为(s 阈值c)或比(s 阈值c)长时，第二确定单元26b指示中止指示单元26c强制中止其中未完成处理的进程。
当模式为1并且第一确定单元26a或第二确定单元26b指示强制中止其中未完成处理的进程时，中止指示单元26c基于位向量来指定其中未完成处理的节点10。然后，当所指定的节点10包括自身节点10时，中止指示单元26c指示系统控制单元14强制中止处理。
此外，当所指定的节点10包括另一节点10时，中止指示单元26c将强制中止通知发送至包括受管理的所指定的节点10的从节点10。在强制中止通知被发送至的从节点10中，强制中止通知由转发处理单元23处理。中止指示单元26c经由发送单元24发送强制中止通知。
注意，中止指示单元26c可以将处理结果的估计值和强制中止的指示传递至系统控制单元14。此外，中止指示单元26c可以将处理结果的估计值和强制中止的指示发送至包括其中未完成在受管理的节点10上的处理的节点10的从节点10。例如，ac单元20存储过去执行结果和执行结果的平均值，并且中止指示单元26c发送过去执行结果的平均值作为估计值。
当自身节点10为根节点10时，时间存储单元27存储由确定单元26收集的时间s、时间mt和时间e。当自身节点10为根节点10时，进程存储单元28将被指示强制中止的进程的编号与屏障同步的次数相关联地存储。
当自身节点10为根节点10时，阈值设定单元29将阈值m和阈值c存储在阈值存储单元25上。阈值m和阈值c是通过程序指定的。阈值设定单元29经由系统控制单元14从cpu12接收通过程序指定的阈值m和阈值c。
当自身节点10为根节点10时，时间读取单元30从时间存储单元27读取时间s、时间mt和时间e，并且将这些时间经由系统控制单元14发送至cpu12。当自身节点10为根节点10时，进程读取单元31从进程存储单元28读取与屏障同步的次数相关联的进程号，并且将进程号经由系统控制单元14发送至cpu12。
图5示出了指定ac并行化的程序的示例。如图5所示，阈值m和阈值c通过“set_ac_parameter(m，c)”指定。此外，ac并行化的位置和模式由“start_ac_region(mode)”和“end_ac_region(mode)”指定。此外，时间s、时间mt和时间e是通过“get_ac_value(&s，&m，&e)”获取的。
此外，阈值m和阈值c通过“set_ac_parameter(m，c)”传递至根节点10的阈值设定单元29。此外，模式通过“start_ac_region(mode)”传递至根节点10的确定单元26，每个节点10的位向量被清0，并且重置时间。
注意，代替通过程序指定阈值m和阈值c，阈值设定单元29可以确定阈值m和阈值c。图6是示出用于确定阈值m的处理的流程的流程图。
如图6所示，阈值设定单元29将n设定到m，指示节点10执行进程(步骤s1)并且获取精确度a(步骤s2)。然后，阈值设定单元29接收精确度ac和误差t(步骤s3)。此处，ac是所需精确度，并且ac<a。此外，t是在ac的情况下的误差，并且是能够确保所需精确度的误差。然后，阈值设定单元29将n/2设定到m，指示节点10执行进程(步骤s4)，并且获得精确度a(步骤s5)。
然后，阈值设定单元29确定ac与a之间的差的绝对值是否小于t(步骤s6)。当绝对值较小时，阈值设定单元29将通过将yx加到n/2而获得的值或者通过从n/2减去yx而获得的值设定到m，并且指示节点10执行进程(步骤s7)。此处，x是执行步骤s7的次数。此外，yx为n/2x 1。例如，y1为(n-m)/2＝n/22，并且y2为n/23。此外，阈值设定单元29在a≥ac时将通过将yx加到n/2而获得的值设定到m，并且在a<ac时将通过从n/2减去yx而获得的值设定到m。然后，阈值设定单元29返回至步骤s5。
另一方面，当ac与a之间的差的绝对值不小于t时，阈值设定单元29利用当前值确定m(步骤s8)。
如上所述，由于阈值设定单元29确定了阈值m，因此ac单元20可以优化ac并行化功能。注意，可以由ac单元20的外部装置执行图6所示的处理，并且ac单元20可以接收由外部装置确定的阈值m。
图7是示出用于确定阈值c的处理的流程的流程图。如图7所示，阈值设定单元29测量当完成第一进程时的时钟数c0和当完成所有进程时的时钟数call(步骤s11)，并且获取当完成所有进程时的精确度a(步骤s12)。然后，阈值设定单元29接收精确度ac和误差t(步骤s13)。然后，阈值设定单元29将(call-c0)/2设定到c，指示节点10执行进程(步骤s14)，并且获得精确度a(步骤s15)。
然后，阈值设定单元29确定ac与a之间的差的绝对值是否小于t(步骤s16)。然后，当ac与a之间的差的绝对值小于t时，阈值设定单元29将通过将yx加至(call-c0)/2而获得的值或者通过从(call-c0)/2减去yx而获得的值设定到c，并且指示节点10执行进程(步骤s17)。此处，x是执行步骤s17的次数。此外，yx为(call-c0)/2x 1。例如，y1为(call-c0)/22并且y2为(call-c0)/23。此外，阈值设定单元29在a≥ac时将通过将yx加至(call-c0)/2而获得的值设定到c，并且在a<ac时将通过从(call-c0)/2减去yx而获得的值设定到c。然后，阈值设定单元29返回至步骤s15。
另一方面，当ac与a之间的差的绝对值不小于t时，阈值设定单元29利用当前值确定c(步骤s18)。
如上所述，由于阈值设定单元29确定了阈值c，因此ac单元20可以优化ac并行化功能。注意，可以由ac单元20的外部装置执行图7所示的处理，并且ac单元20可以接收由外部装置确定的阈值c。
接下来，将参照图8至图11来描述ac单元20的处理流程。图8是示出当自身节点10完成处理时的通知处理的流程的流程图。如图8所示，当转发处理单元23从系统控制单元14接收到处理的完成通知(步骤s21)时，转发处理单元23将位向量中的与自身节点10相对应的位设定为1(步骤s22)。然后，当存在主节点10时，转发处理单元23将自身节点10的标识号和完成通知发送至主节点10(步骤s23)。
如上所述，由于转发处理单元23将自身节点10的标识号和完成通知发送至主节点10，因此可以向主节点10通知完成了自身节点10的处理。
图9是示出当从从节点10接收到完成通知时的转发处理的流程的流程图。如图9所示，当从从节点10接收到完成通知和标识号(步骤s31)时，转发处理单元23将位向量中的与标识号相对应的位设定为1(步骤s32)。然后，当存在主节点10时，转发处理单元23将完成通知和标识号发送至主节点10(步骤s33)。
如上所述，由于转发处理单元23将从从节点10接收的标识号和完成通知转发至主节点10，因此根节点10可以指定所有节点10的完成状态。
图10是示出在模式＝1时由判定确定单元26进行的ac并行化处理的流程的流程图。注意，图10中的ac并行化处理在位向量中的一位被设定为1时开始，并且周期性地开始。
如图10所示，确定单元26确定是否位向量中的一位首先被设定为1(步骤s41)，并且当1被首先设定时，确定单元26将当前时间设定到s(步骤s42)。
然后，确定单元26确定位向量中的1的数目是否为m或大于m(步骤s43)，并且当位向量中的1的数目并非为m或大于m时，确定当前时间是否为(s c)或比(s c)长(步骤s44)。然后，在当前时间并非(s c)或比(s c)长时，确定单元26结束ac并行化处理。
另一方面，在当前时间为(s c)或比(s c)长时，或者当位向量中的1的数目为m或大于m时，确定单元26在自身节点10未完成处理时指示系统控制单元14强制中止处理(步骤s45)。然后，确定单元26沿二叉树向未发送完成通知的下级节点10发送强制中止通知(步骤s46)。
如上所述，当位向量中的1的数目为m或大于m或者当前时间为(s c)或比(s c)长时，确定单元26强制中止用于其中未完成处理的节点10的处理。因此，ac单元20可以减少屏障同步中的等待时间。
图11是示出当从主节点10接收到强制中止通知时的转发处理的流程的流程图。如图11所示，当转发处理单元23从主节点10接收到强制中止通知(步骤s51)时，并且当自身节点10未完成处理时，转发处理单元23指示系统控制单元14强制中止处理(步骤s52)。然后，当存在从节点10时，转发处理单元23将强制中止通知发送至包括其中未完成在受管理的节点10上的处理的节点10的从节点10(步骤s53)。
如上所述，由于转发处理单元23将从主节点10接收到的强制中止通知转发至包括其中未完成在受管理的节点10上的处理的节点10的从节点10，因此其中未完成处理的节点10可以接收强制中止通知。
接下来，将描述网络接口装置13的硬件配置的示例。图12示出了网络接口装置13的硬件配置的示例。如图12所示，网络接口装置13包括微处理器单元(mpu)13a、只读存储器(rom)13b和ram13c。
mpu13a是读取并执行存储在rom13b中的固件(程序)的处理装置。rom13b是存储固件的非易失性存储装置。ram13c是存储由固件使用的数据的存储装置。
mpu13a包括pr41、mr42、cr43、cnt44、sr45、mr46和er47。pr41是用于存储位向量的寄存器。状态存储单元21由pr41实现。mr42是用于存储阈值m的寄存器。cr43是用于存储阈值c的寄存器。阈值存储单元25由mr42和cr43实现。cnt44对时间进行计数。sr45是用于存储时间s的寄存器。mr46是用于存储时间mt的寄存器。er47是用于存储时间e的寄存器。时间存储单元27由sr45、mr46和er47实现。
如上所述，在示例中，每个节点10存储位向量。然后，当模式为1时，根节点10的第一确定单元26a基于位向量将已经完成处理的节点10的数目与阈值m进行比较，并且确定已经完成处理的节点10的数目是否为阈值m或大于阈值m。然后，当已经完成处理的节点10的数目为阈值m或大于阈值m时，中止指示单元26c基于位向量来指定其中未完成处理的节点10，并且指示所指定的节点10强制中止。因此，ac单元20可以减少屏障同步中的等待时间并且提高处理速度。
此外，在示例中，当模式为1时，根节点10的第二确定单元26b基于位向量来检测节点10之一首先完成处理的时间点，并且确定从检测到的时间点开始的经过时间是否为阈值c或比阈值c长。然后，当自节点10之一首先完成处理开始的经过时间为阈值c或比阈值c长时，中止指示单元26c基于位向量来指定其中未完成处理的节点10，并且指示所指定的节点10强制中止。因此，ac单元20可以减少屏障同步中的等待时间并且提高处理速度。
此外，在示例中，当所指定的节点10包括自身节点10时，中止指示单元26c指示系统控制单元14强制中止进程。此外，当所指定的节点10包括另一节点10时，中止指示单元26c参考位向量，并且将强制中止通知发送至包括受管理的所指定的节点10的从节点10。然后，在接收到强制中止通知的从节点10中，转发处理单元23参考位向量，并且当自身节点10未完成处理时，指示系统控制单元14强制中止处理。此外，当存在从节点10时，转发处理单元23参考位向量，并且将强制中止通知转发至包括其中未完成在受管理的节点10上的处理的节点10的从节点10。因此，中止指示单元26c可以指示其中未完成处理的节点10强制中止。
此外，在示例中，ac单元20在模式为0时执行正常屏障同步，在模式为1时执行ac并行化，并且在模式为2时收集用于ac并行化的数据。因此，用户可以通过由程序指定模式来控制ac单元20的操作。
此外，在示例中，阈值存储单元25存储阈值m和阈值c，并且阈值设定单元29确定阈值m和阈值c的最优值并且将最优值存储在阈值存储单元25中。然后，第一确定单元26a将存储在阈值存储单元25中的阈值m与已经完成处理的节点10的数目进行比较，并且第二确定单元26b将存储在阈值存储单元25中的阈值c与自节点10之一首先完成处理开始的经过时间进行比较。因此，ac单元20可以优化ac并行化功能。
此外，在示例中，进程存储单元28将强制中止进程号与屏障同步的次数相关联地存储，并且进程读取单元31从进程存储单元28读取并输出强制中止进程号和所述次数。因此，ac单元20可以提供对ac并行化功能的分析有用的信息。
此外，在示例中，由于中止指示单元26c将进程的处理结果的估计值发送至被指示强制中止的进程，因此ac单元20可以在不减少进程的数目的情况下提供ac并行化功能。
此外，在示例中，时间存储单元27存储时间s、时间mt和时间e，并且时间读取单元30从时间存储单元27读取并输出时间s、时间mt和时间e。因此，ac单元20可以提供对ac并行化功能的分析有用的信息。
注意，在示例中，描述了将进程分配至节点10的情况，并且代替进程，可以将另一处理单元如线程分配至节点10。
此外，在示例中，描述了当模式为1时第一确定单元26a和第二确定单元26b两者均操作的情况，并且可以细分模式为1的情况。换言之，还可以提供以下三种模式：其中仅第一确定单元26a操作的模式，其中仅第二确定单元26b操作的模式以及其中第一确定单元26a和第二确定单元26b两者均操作的模式。
此外，在示例中，描述了将二叉树配置用于同步通信的情况，并且节点10可以配置另一树结构用于同步通信。
此外，在示例中，所有节点10均包括阈值存储单元25、确定单元26、时间存储单元27、进程存储单元28、阈值设定单元29、时间读取单元30和进程读取单元31，并且仅根节点10可以包括这些功能单元。
本文中提供的所有示例和条件语言意在用于帮助读者理解本发明和由发明人为了促进本领域技术贡献的构思的教导目的，并且不应被解释为限于这样的具体叙述的示例和条件，说明书中这样的示例的组织也不涉及对本发明的优势和劣势的展示。尽管已经详细地描述了本发明的一个或更多个实施方式，但是应当理解的是，在不脱离本发明的精神和范围的情况下，可以对本发明做出各种改变、替换和变换。
[引文列表]
[专利文献]
日本特开专利公布第2014-63278号。
[附图标记列表]
1并行处理系统
2网络
10节点
11存储器
12cpu
13网络接口装置
13ampu
13brom
13cram
14系统控制单元
20ac单元
21状态存储单元
22接收单元
23转发处理单元
24发送单元
25阈值存储单元
26确定单元
26a第一确定单元
26b第二确定单元
26c中止指示单元
27时间存储单元
28进程存储单元
29阈值设定单元
30时间读取单元
31进程读取单元
41pr
42mr
43cr
44cnt
45sr
46mr
47er
1.一种屏障同步系统，包括：
多个信息处理设备，其被配置成在通过屏障同步进行同步的情况下执行并行处理，每个信息处理设备被配置成作为树结构中的多个节点中的一个节点，并与所述多个节点中的其他节点中的一个或更多个节点相关联，
其中，所述多个信息处理设备中的每一个包括：
完成信息存储装置；以及
控制电路，
其中，各个信息处理设备的完成信息存储装置被配置成存储包括与作为所述各个信息处理设备的自身设备的处理的完成有关的信息的完成信息，在所述自身设备与下级信息处理设备相关联的情况下，所述完成信息还包括与所述下级信息处理设备的处理的完成有关的信息，所述下级信息处理设备是所述多个信息处理设备之一，并且作为所述树结构中比所述自身设备低级的节点来操作，
其中，所述各个信息处理设备的控制电路被配置成：当所述各个信息处理设备被配置成作为位于所述树结构中的根处的根节点来操作时，
通过使用所述完成信息存储装置来获得所述多个节点中的并行处理的当前状态；
确定所获得的所述并行处理的当前状态是否达到给定条件；
响应于指示所获得的所述并行处理的当前状态达到所述给定条件的确定结果，通过使用所述完成信息存储装置从所述多个信息处理设备中指定信息处理设备，所指定的信息处理设备是尚未完成所述处理的设备；以及
指示所指定的信息处理设备在所述多个信息处理设备中的所有信息处理设备均已经完成所述处理之前强制中止所述处理。
2.根据权利要求1所述的屏障同步系统，
其中，所述当前状态的所述获得被配置成通过使用所述完成信息存储装置来获得完成数目，所述完成数目是与所述多个信息处理设备中的已经完成所述处理的信息处理设备的数量相对应的数目，
其中，所述确定被配置成：基于所述完成信息存储装置，确定完成数目是否等于或大于第一阈值，所述第一阈值为小于所述多个信息处理设备的数量的值，
其中，所述指定被配置成：响应于指示所述完成数目等于或大于所述第一阈值的确定结果，通过使用所述完成信息存储装置从所述多个信息处理设备中指定所述信息处理设备。
3.根据权利要求1所述的屏障同步系统，
其中，所述根节点的所述控制电路被配置成：
基于所述完成信息存储装置，检测所述信息处理设备之一首先完成所述处理的时间点；以及
确定从检测到的时间点开始的经过时间是否等于或大于第二阈值，
其中，响应于指示所述经过时间等于或大于所述第二阈值的确定结果来执行对所述信息处理设备的所述指定。
4.根据权利要求2所述的屏障同步系统，其中，
所述根节点的所述控制电路被配置成：
在所指定的信息处理设备包括所述根节点的情况下，指示所述根节点强行中止所述处理；以及
在所指定的信息处理设备包括其他节点的情况下，向所述其他节点发送强制中止通知；以及
所述其他节点中的每个节点的控制电路被配置成：响应于接收到所述强制中止通知，
参考作为所述其他节点中的所述每个节点的自身设备的完成信息存储装置；
指示所述自身设备强行中止所述处理；以及
当所述自身设备与所述下级信息处理设备相关联时，将强制中止通知发送至所述下级信息处理设备。
5.根据权利要求2所述的屏障同步系统，其中，
所述根节点的所述控制电路被配置成：
通过使用指示模式的值来执行确定，所述模式与要在所述屏障同步系统中执行的屏障同步操作相对应。
6.根据权利要求2所述的屏障同步系统，其中，
所述根节点的所述控制电路被配置成：
调整所述第一阈值；以及
通过使用经调整的所述第一阈值来执行所述确定。
7.根据权利要求2所述的屏障同步系统，其中，
所述根节点的所述控制电路被配置成：
将处理单元的标识符与所述屏障同步的次数相关联地存储，所述处理单元与被指示强制中止所述处理的所指定的信息处理设备相关联；以及
读取并输出所存储的标识符和所述次数。
8.根据权利要求2所述的屏障同步系统，
其中，所述强制中止的所述指示被配置成将估计结果发送至所指定的信息处理设备，所述估计结果与在完成了所述处理的情况下预期的结果相对应，所发送的估计结果被配置成指示所指定的信息处理设备通过使用所述估计结果来执行接下来的处理。
9.根据权利要求2所述的屏障同步系统，其中，
所述根节点的所述控制电路被配置成：
存储包括第一时间、第二时间和第三时间的多个时间，所述第一时间是所述信息处理设备之一已经首先完成所述处理的时间，所述第二时间是所述完成数目已经达到所述第一阈值的时间，所述第三时间是所述多个信息处理设备中的所有信息处理设备都已经完成所述处理的时间；以及
读取并输出所存储的时间中的任何时间。
10.一种并行信息处理设备，被配置成：在通过屏障同步与屏障同步系统中的其他并行信息处理设备进行同步的情况下执行并行处理，所述并行信息处理设备和所述其他并行信息处理设备是所述屏障同步系统中的多个并行信息处理设备之一，所述多个并行信息处理设备中的每一个被配置成作为树结构中的多个节点中的一个节点，并且与所述多个节点中的其他节点中的一个或更多个节点相关联，所述并行信息处理设备包括：
完成信息存储装置；以及
控制电路，
其中，所述完成信息存储装置被配置成存储包括与作为所述并行信息处理设备的自身设备的处理的完成有关的信息的完成信息，在所述自身设备与下级信息处理设备相关联的情况下，所述完成信息还包括与所述下级信息处理设备的处理的完成有关的信息，所述下级信息处理设备是所述其他并行信息处理设备之一，并且作为所述树结构中比所述自身设备低级的节点来操作，以及
其中，所述控制电路被配置成：当所述并行信息处理设备被配置成作为位于所述树结构的根处的根节点来操作时，
通过使用所述完成信息存储装置来获得所述多个节点中的并行处理的当前状态；
确定所获得的所述并行处理的当前状态是否达到给定条件；
响应于指示所获得的所述并行处理的当前状态达到所述给定条件的确定结果，通过使用所述完成信息存储装置从所述多个并行信息处理设备中指定信息处理设备，所指定的信息处理设备是尚未完成所述处理的设备；以及
指示所指定的信息处理设备在所述多个并行信息处理设备中的所有并行信息处理设备均已经完成所述处理之前强制中止所述处理。
11.根据权利要求10所述的信息处理设备，
其中，所述当前状态的所述获得被配置成通过使用所述完成信息存储装置来获得完成数目，所述完成数目是与所述多个并行信息处理设备中的已经完成所述处理的信息处理设备的数量相对应的数目，
其中，所述确定被配置成：基于所述完成信息存储装置，确定完成数目是否等于或大于第一阈值，所述第一阈值为小于所述多个并行信息处理设备的数量的值，
其中，所述指定被配置成：响应于指示所述完成数目等于或大于所述第一阈值的确定结果，通过使用所述完成信息存储装置从所述多个并行信息处理设备中指定所述信息处理设备。
12.根据权利要求10所述的信息处理设备，
所述控制电路被配置成：
基于所述完成信息存储装置，检测所述信息处理设备之一首先完成所述处理的时间点；以及
确定从检测到的时间点开始的经过时间是否等于或大于第二阈值，
其中，响应于指示所述经过时间等于或大于所述第二阈值的确定结果来执行对所述信息处理设备的所述指定。
13.一种非暂态计算机可读存储介质，用于存储使并行信息处理设备的处理器执行同步处理的屏障同步程序，所述并行信息处理设备是屏障同步系统中的多个并行信息处理设备之一，所述并行信息处理设备被配置成在通过屏障同步与其他并行信息处理设备进行同步的情况下执行并行处理，所述多个并行信息处理设备中的每一个被配置成作为树结构中的多个节点中的一个节点，并且与所述多个节点中的其他节点中的一个或更多个节点相关联，
所述同步处理包括：
当所述信息处理设备被配置成作为位于所述树结构中的根处的根节点来操作时，
访问完成信息存储装置，所述完成信息存储装置被配置成存储包括与作为所述并行信息处理设备的自身设备的处理的完成有关的信息的完成信息，在所述自身设备与下级信息处理设备相关联的情况下，所述完成信息还包括与所述下级信息处理设备的处理的完成有关的信息，所述下级信息处理设备是所述其他并行信息处理设备之一，并且作为所述树结构中比所述自身设备低级的节点来操作，
通过使用所述完成信息存储装置来获得所述多个节点中的并行处理的当前状态；
确定所获得的所述并行处理的当前状态是否达到给定条件；
响应于指示所获得的所述并行处理的当前状态达到所述给定条件的确定结果，通过使用所述完成信息存储装置从所述多个并行信息处理设备中指定信息处理设备，所指定的信息处理设备是尚未完成所述处理的设备；以及
指示所指定的信息处理设备在所述多个并行信息处理设备中的所有并行信息处理设备均已经完成所述处理之前强制中止所述处理。
14.根据权利要求13所述的非暂态计算机可读存储介质，其中，
其中，所述当前状态的所述获得被配置成通过使用所述完成信息存储装置来获得完成数目，所述完成数目是与所述多个并行信息处理设备中的已经完成所述处理的信息处理设备的数量相对应的数目，
其中，所述确定被配置成：基于所述完成信息存储装置，确定完成数目是否等于或大于第一阈值，所述第一阈值为小于所述多个并行信息处理设备的数量的值，
其中，所述指定被配置成：响应于指示所述完成数目等于或大于所述第一阈值的确定结果，通过使用所述完成信息存储装置从所述多个并行信息处理设备中指定所述信息处理设备。
15.根据权利要求13所述的非暂态计算机可读存储介质，
所述同步处理还包括：
基于所述完成信息存储装置，检测所述信息处理设备之一首先完成所述处理的时间点；以及
确定从检测到的时间点开始的经过时间是否等于或大于第二阈值，
其中，响应于指示所述经过时间等于或大于所述第二阈值的确定结果来执行对所述信息处理设备的所述指定。
技术总结