近似计算并行化电路和方法以及并行信息处理装置

摘要

本发明涉及近似计算并行化电路、近似计算并行化方法和并行信息处理装置。一种近似计算并行化电路，包括：发送电路，其被配置成发送停止信号，该停止信号指示用于执行紧接在相关装置负责的迭代之前的迭代中的计算的装置停止循环携带依赖计算中的计算；以及估计电路，其被配置成生成要在发送电路发送了停止信号时提供至运算电路的估计值，作为执行所述之前的迭代中的计算的结果。

说明书

技术领域

本文中论述的实施方式涉及近似计算并行化电路、近似计算并行化方法和并行信息处理装置。

背景技术

阻碍程序并行化的因素之一是循环携带依赖。循环携带依赖(loop-carrieddependency)是在循环执行中根据先前迭代的结果来在新的迭代中执行计算。当存在循环携带依赖时，不执行以任意次序执行迭代的并行化。

然而，在迭代中，不仅存在具有循环携带依赖并且因此要顺序地执行的部分(顺序代码)，而且还存在不具有循环携带依赖并且能够并行执行的部分(并行代码)。因此，可以在保持顺序代码被执行的次序的同时使循环执行并行化。

例如，当将线程分配给迭代并且通过多线程使程序并行化时，具有循环携带依赖的变量的值要在执行特定迭代的线程与执行紧接在该特定迭代之后的迭代的线程之间彼此同步。当用于同步的时间段等于或长于用于执行顺序代码的时间段时，或者当要在很多线程之间执行同步时，用于同步的时间段是整个程序的瓶颈。

因此，存在环形缓存架构作为用于减少用于同步的时间段的技术。在环形缓存架构中，核(core)以环形形式安装。紧接在完成顺序代码的执行之后，负责执行当前迭代的核将完成信号和数据(执行结果)发送至负责执行紧接在当前迭代之后的迭代的核。在确定要使用完成信号和数据之前，将完成信号和数据缓存在与核邻近的存储器中。因此，与在确定要使用完成信号和数据之后确认完成信号并且请求数据的情况相比，可以减少用于同步的时间段。

作为与循环的并行执行有关的现有技术，存在并行执行以下循环的信息处理装置：在该循环中，用于终止循环的条件的确定取决于正在处理的数据，并且预先未知在执行迭代时满足用于终止循环的条件的迭代。信息处理装置将优先级赋予以下指令处理装置：该指令处理装置正在执行最早的迭代并且是正在并行执行循环的指令处理装置之中的指令处理装置。然后，信息处理装置将以下装置限制为具有优先级的指令处理装置：该装置用于将数据传送至存储器并且中断由除了在循环终止时检测到用于终止的条件的指令处理装置以外的指令处理装置执行的处理。在这种情况下，即使在任何指令处理装置检测到用于终止循环的条件时，处理中也不会出现超越，并且信息处理装置并行执行循环，同时保证与顺序执行代码的情况下的操作相同的操作。

[引文列表]

[专利文献]

专利文献1：日本公开特许公报第05-127904号。

发明内容

[技术问题]

为了提高环形缓存架构中的速度，考虑近似计算(AC)并行化，其中，在AC并行化中，开始执行紧接在当前迭代之后的迭代，而无需等待当前迭代中的顺序代码的执行完成。AC并行化的实现具有减少用于执行顺序代码的时间段的效果以及省略具有循环携带依赖的变量的同步的效果。

然而，在实现AC并行化的情况下，存在以下问题：停止当前迭代的执行，并且要快速地估计由于同步的省略而未确定的变量值。与未应用AC并行化的情况相比，当用于是否要执行停止和估计的确定以及用于估计值的定义和存储的开销大时，AC并行化的效果可能会降低或者速度会减小。

在一方面，本发明旨在高速停止当前迭代的执行，并且高速估计尚未确定的值。

[问题的解决方案]

在一方面，AC并行化电路包括发送电路，该发送电路发送停止信号，该停止信号指示用于执行紧接在相关装置负责的迭代之前的迭代中的计算的装置停止循环携带依赖计算中的计算。AC并行化电路包括估计电路，该估计电路生成要在发送电路发送了停止信号时提供至运算电路的估计值，作为执行所述之前的迭代中的计算的结果。

[本发明的有益效果]

在本发明的一方面，可以高速停止当前迭代的执行，并且可以高速估计尚未确定的值。

附图说明

图1是示出根据实施方式的并行处理系统的配置的图；

图2是示出节点的配置的图；以及

图3示出了描述并行处理系统的效果的图。

具体实施方式

在下文中，基于附图来详细描述本文中公开的AC并行化电路、本文中公开的AC并行化方法以及本文中公开的并行信息处理装置的实施方式。实施方式不限制本文中公开的技术。

实施方式

首先，描述根据实施方式的并行处理系统的配置。图1是示出根据实施方式的并行处理系统的配置的图。如图1所示，根据实施方式的并行处理系统1包括由节点#0至节点#n(n是正整数)指示的(n+1)个节点10和检查装置30。节点#0至节点#n以环形形式彼此耦接。例如，并行处理系统1是环形缓存架构并行处理系统。在并行处理系统1中，将线程分配给具有循环携带依赖的程序的迭代，并且程序通过多线程并行执行。

节点10是执行线程的信息处理装置。例如，节点#0执行迭代1的线程#0，节点#(m-1)执行迭代m的线程#(m-1)，并且节点#m执行迭代(m+1)的线程#m。节点#(m+1)执行迭代(m+2)的线程#(m+1)，……，并且节点#n执行迭代(n+1)的线程#n。

当节点10中的每一个完全处理了线程时，节点10在完成信号中设置1，在数据中设置计算结果，并且将完成信号和数据发送至相关节点10中的后续节点10。例如，当节点#(m-1)完全处理了线程#(m-1)时，节点#(m-1)在完成信号中设置1，在数据中设置计算结果，并且将完成信号和数据发送至节点#m。当节点#m完全处理了线程#m时，节点#m在完成信号中设置1，在数据中设置计算结果，并且将完成信号和数据发送至节点#(m+1)。当节点#n完全处理了线程#n时，节点#n在完成信号中设置1，在数据中设置计算结果，并且将完成信号和数据发送至节点#0。

当节点10中的每一个的前面第二个节点10完全处理了线程，并且节点10中的每一个的前一节点10开始处理线程时，相关节点10开始对时钟进行计数。然后，当由相关节点10计数的数等于预定阈值时，相关节点10将停止(删除)位设置为1，将停止位发送至前一节点10，并且使前一节点10停止线程。以前述方式，并行处理系统1执行AC并行化。

例如，当由节点#m计数的数等于预定阈值时，节点#m将停止位设置为1并且将停止位发送至节点#(m-1)。当由节点#(m+1)计数的数等于预定阈值时，节点#(m+1)将停止位设置为1，并且将停止位发送至节点#m。当由节点#0计数的数等于预定阈值时，节点#0将停止位设置为1，并且将停止位发送至节点#n。

如以上所描述的，当节点10中的每一个的前面第二个节点10完全处理了线程，并且节点10中的每一个的前一节点10开始处理线程时，相关节点10开始对时钟进行计数。然后，当由相关节点10计数的数等于预定阈值时，相关节点10将停止位设置为1，并且将停止位发送至前一节点10。

因此，节点10中的每一个可以仅通过将一位信息发送至节点10的前一节点10来高速停止该前一节点10的线程。对于允许一些错误并且作为LSI布置和布线问题、光刻图案生成问题、车辆路径问题等的优化问题，可以通过AC并行化来提高处理速度。

检查装置30耦接至节点10中的每一个。检查装置30在节点10完全处理了线程时从节点10中的每一个获取计数的等待数，并且显示计数的等待数。计数的等待数中的每一个是由从前一节点10开始处理线程时起至相关节点10完全处理了线程时的时钟指示的数。

检查装置30通过以下操作来支持AC并行化的效果的验证：对当并行处理系统1执行AC并行化时的计数的等待数与当并行处理系统1未执行AC并行化时的计数的等待数进行比较，并且显示比较的结果。

接下来，描述节点10中的每一个的配置。图2是示出节点10的配置的图。尽管图2示出了节点#m的配置，但是其他节点10具有相同的配置。如图2所示，节点10包括接收器(Rx)11、多路复用器12、发送器(Tx)13、缓存存储器14、多路复用器15、核16、等待数寄存器17、等待计数器18、比较器和与电路20。节点10还包括停止信号生成电路21、估计电路22和锁存器23。

Rx 11从节点#(m-1)接收完成信号和数据，并且将所接收的完成信号和所接收的数据输出至多路复用器12。Rx 11接收排除了完成信号#m和数据#m的完成信号和数据。在这种情况下，完成信号#m由节点#m生成，并且数据#m由节点#m生成。

多路复用器12基于路径来选择从Rx 11接收的完成信号和从Rx 11接收的数据或者从核16接收的完成信号#m和从核16接收的数据#m，并且将所选择的完成信号和所选择的数据输出至Tx 13和缓存存储器14。在这种情况下，路径是用于选择从Rx 11接收的完成信号和从Rx 11接收的数据或者从核16接收的完成信号#m和从核16接收的数据#m的控制信号。当路径指示1时，选择从Rx 11接收的完成信号和从Rx 11接收的数据。当路径指示0时，选择从核16接收的完成信号#m和从核16接收的数据#m。

Tx 13将由多路复用器12输出的完成信号和由多路复用器12输出的数据发送至节点#(m+1)。

缓存存储器14存储由多路复用器12输出的完成信号和由多路复用器12输出的数据。例如，缓存存储器14存储完成信号#0至完成信号#n和数据#0至数据#n。

多路复用器15基于与电路20的输出来选择存储在缓存存储器14中的完成信号#(m-1)和存储在缓存存储器14中的数据#(m-1)或者由估计电路22生成的完成信号#(m-1)和由估计电路22生成的估计值#(m-1)，并且将所选择的完成信号和所选择的数据或值输出至核16。

当核16检测到存储在缓存存储器14中的完成信号#(m-1)指示1时，核16使用数据#(m-1)执行线程#m。然后，当核16完成线程#m的执行时，核16在完成信号#m中设置1，在数据#m中设置执行结果，将完成信号#m和数据#m输出至多路复用器12，并且将完成信号#m输出至锁存器23。

在执行AC并行化的情况下，核16将AC使能设置为1，并且将AC使能输出至与电路20。核16设置等待数寄存器17中的等待数。在AC并行化中，等待数是由从节点#(m-1)开始处理时起至节点#m开始处理时的时钟指示的数。当停止信号生成电路21输出停止信号时，核16停止执行线程#m。

等待数寄存器17存储等待数。当完成信号#(m-2)被设置为1并且存储在缓存存储器14中时，等待计数器18开始对时钟进行计数。比较器19将由等待计数器18计数的数与存储在等待数寄存器17中的等待数进行比较。当由等待计数器18计数的数等于等待数时，比较器19将1输出至与电路20。

与电路20获得比较器19的输出和AC使能的逻辑积，将指示逻辑积的结果作为停止位输出至节点#(m-1)，并且将停止位作为控制输入输出至多路复用器15。当与电路20的输出指示1时，在由节点#(m-1)进行的处理的开始之后已经经过了预定时间段，并且要执行AC并行化。因此，节点#(m-1)停止线程#(m-1)，并且多路复用器15选择估计电路22的输出。

当停止信号生成电路21从节点#(m+1)接收到停止位并且检测到停止位为1时，停止信号生成电路21生成停止信号并且将停止信号输出至核16。核16在检测到停止信号时停止线程#m。

估计电路22将完成信号#(m-1)设置为1，并且设置数据#(m-1)中的估计值。例如，估计电路22使用0或先前值作为估计值。可替选地，估计电路22可以使用过去值之中的最大值、最小值、中间值、移动平均值等作为估计值。过去值存储在缓存存储器14中。由于估计电路22以前述方式设置数据#(m-1)中的估计值，因此并行处理系统1可以高速估计数据#(m-1)。

锁存器23将完成信号#m视为使能信号，并且保持等待计数器18的值。锁存器23中保持的计数的等待数由检查装置30读取。

接下来，描述并行处理系统1的效果。图3示出了描述并行处理系统1的效果的图。图3的(a)示出了现有技术中的执行时间的示例。图3的(b)示出了实施方式中的执行时间的示例。

如图3的(a)所示，在现有技术中，在线程#0执行并行代码和顺序代码之后，线程#0将完成信号和数据发送至线程#1，执行并行代码，并且终止处理。当线程#1在执行并行代码之后暂停并且从线程#0接收到完成信号和数据时，线程#1执行顺序代码，将完成信号和数据发送至线程#2，执行并行代码，并且终止处理。当线程#2在执行并行代码之后暂停并且从线程#1接收到完成信号和数据时，线程#2执行顺序代码，将完成信号和数据发送至线程#3，执行并行代码，并且终止处理。

另一方面，如图3的(b)所示，在本实施方式中，在线程#0执行并行代码和顺序代码之后，线程#0将完成信号和数据发送至线程#1，执行并行代码，并且终止处理。当线程#1在执行并行代码之后暂停并且从线程#0接收到完成信号和数据时，线程#1执行顺序代码。当在完成信号的接收之后经过了预定时间段时，线程#1被线程#2停止。当线程#2在执行并行代码之后暂停、线程#1接收到完成信号并且经过了预定时间段时，线程#2将停止信号发送至线程#1，并且使用估计值执行顺序代码。然后，线程#2将完成信号和数据发送至线程#3，执行并行代码，并且终止处理。

相比于图3的(a)，在图3的(b)中，减少了用于由线程#1执行顺序代码的时间段，并且省略了用于发送和接收完成信号和数据的时间段，所述时间段用于在线程#1与线程#2之间同步数据。因此，并行处理系统1可以减少执行时间。

如以上所描述的，在实施方式中，当完成信号#(m-2)被设置为1并且存储在缓存存储器14中时，节点#m的等待计数器18开始对时钟进行计数。然后，比较器19将由等待计数器18计数的数与存储在等待数寄存器17中的等待数进行比较。当由等待计数器18计数的数等于等待数时，比较器19将1输出至与电路20。与电路20计算AC使能与比较器19的输出的逻辑积，并且将计算结果作为停止位输出至节点#(m-1)。

估计电路22将完成信号#(m-1)设置为1，并且设置数据#(m-1)中的估计值。然后，多路复用器15基于与电路20的输出，选择存储在缓存存储器14中的完成信号#(m-1)和存储在缓存存储器14中的数据#(m-1)或者由估计电路22生成的完成信号#(m-1)和由估计电路22生成的估计值#(m-1)，并且将所选择的完成信号和所选择的数据或值输出至核16。

因此，节点#m确定是否要停止由节点#(m-1)执行的线程#(m-1)。当节点#m确定要停止线程#(m-1)时，节点#m可以指示节点#(m-1)高速地停止线程#(m-1)，并且可以高速地估计节点#(m-1)的计算结果。

在实施方式中，当节点#m的停止信号生成电路21从节点#(m+1)接收到停止位并且停止位为1时，节点#m的停止信号生成电路21生成用于停止线程#m的停止信号并且将停止信号输出至核16。因此，节点#m可以基于来自节点#(m+1)的指令来快速地停止线程#m。

在实施方式中，由于节点#m的锁存器23将完成信号#m视为使能信号并且保持等待计数器18的值，因此节点#m可以提供用于验证AC并行化的效果的数据。

尽管实施方式描述了执行线程的情况，但是节点10可以执行其他处理单元。尽管实施方式描述了核16执行线程的情况，但是其他运算装置也可以执行线程。