一种流式数据流图关键路径的加速方法、加速系统、装置及芯片

摘要

本发明公开一种流式数据流图关键路径的加速方法、加速系统、装置及芯片，其中所述方法包括以下步骤：确定数据流中的关键节点；在所述关键节点之前增加前驱节点，在所述关键节点之后增加后继节点；复制关键节点形成多个关键子节点；待传输数据经过所述前驱节点后，选择其中一个可用的关键子节点，并经由选定的所述关键子节点从所述后继节点中输出所述待传输数据。本发明只对数据流图当中单个操作数存储空间进行优化，使得单个操作数存储空间当中的关键路径中的关键操作可以并行执行，从而缩短了数据流图中关键路径的执行时间，执行效率较传统结构有明显优势。

说明书

技术领域

本发明涉及数据流体系结构技术领域，特别涉及一种流式数据流体系结构关键路径的加速方法、加速系统、装置及芯片。

背景技术

当前超级计算领域首功耗限制在推向E级计算这一节点时遇到了巨大的阻力，数据流体系结构以其优秀的并行特点和性能功耗比再次获得了广泛的关注。数据流体系结构计算大规模的科学计算，首先需要使用数据流语言编写可在数据流体系结构中执行的程序；之后需要将数据流语言编写的程序翻译成数据流图，表明程序中模块之间的依赖关系以及指令之间的依赖关系；得到数据流图之后，需要将数据流图映射到物理的数据流处理单元上；最后需要计算的数据，以流的方式源源不断地注入数据流处理器中执行。数据流体系中的数据可以直接在指令之间传递，缓解了传统冯诺依曼结构中存在的指令相关和数据相关问题带来的时延和功耗问题，提高了指令的并行度。

数据流内核部分需要支持数据流指令到数据流图的正确映射，传统的映射方式是将数据流图中的操作(这里的操作，既可以指单条指令，也可以指多条顺序指令构成的指令集，可以使指令、模块、任务等粒度)与数据流图中的节点一一映射(一条操作只对应数据流图中的一个节点)。在一个数据流图当中，不同的节点的执行效率是不同的，在数据流图中常常存在着有相同后继节点的不同节点，例如加法操作节点中的2个操作数来自于不同的2个前驱节点(前驱节点可能是访存节点，也可能是其他的计算几点等)。由于节点之间的执行速率不同，那么存在节点中需要执行的源数据不能同时到达，而节点需要所有源数据到达之后才能够执行。那么节点的执行的开始时间取决于最晚到达节点源数据的时间，而数据流动慢的相互间存在依赖的节点集称之为关键路径。如图1所示，如果节点3较节点2执行速率慢，那么将路径1-3-4称之为关键路径。关键路径会造成数据流图中的节点的功能部件利用率低，并且也直接决定单个数据流图中的数据流图执行效率。

为了能够缓解数据流图中关键操作(关键路径上的低效率的操作)给程序带来的长延迟的影响，提高数据流图中节点中功能部件的执行效率，通常采用的方法是将整个数据流图复制多份，形成多个操作数存储空间，给数据提供了多条通路，使得程序中不同的操作数存储空间能够并行的执行，掩盖掉关键路径中的关键操作带来的延迟影响，如图1所示。但是使用复制多套数据流图的方法存在着以下2个关键问题：

1、复制多个操作数存储空间的方法并不能解决操作数存储空间中关键操作执行慢的问题。采用上面的方法，是给数据提供了多条可走的通路，但是对于每条通路而言，数据通路执行效率还是没有改变的。

2、采用多个操作数存储空间的方法会导致存储空间爆炸。采用这个方法，当关键操作的执行效率足够慢时，必须要足够多的储存空间来掩盖关键操作带来的延迟影响。而一个操作数存储空间为整个数据流图的物理存储空间，并且会对数据流处理器之间传输数据带来压力。当需要足够多的操作数存储空间时，会导致存储空间爆炸。

基于以上存在的问题，传统的加速关键路径操作的方法对硬件的要求巨大，而且并没有从根本上缓解单个操作数存储空间的关键路径的执行效率，需要一种在可接受的存储空间的范围内，对数据流图关键路径的加速方法。

发明内容

针对现有技术的不足，本发明提出一种加速数据流图关键路径的方法，系统及其装置。

本发明首先提供一种流式数据流图关键路径的加速方法，包括以下步骤：

确定数据流中的关键节点；

在所述关键节点之前增加前驱节点，在所述关键节点之后增加后继节点；

复制关键节点形成多个关键子节点；

待传输数据经过所述前驱节点后，选择其中一个可用的关键子节点，并经由选定的所述关键子节点从所述后继节点中输出所述待传输数据。

根据本发明提出的流式数据流图关键路径的加速方法，其中，所述前驱节点包括第一标志位，第一选择逻辑和第一转发逻辑；所述第一标志位用于表示所述关键子节点能否接收数据，所述第一选择逻辑根据所述第一标志位从多个关键子节点中选择一个可用的关键子节点，所述第一转发逻辑用于接收所述第一选择逻辑选定的关键子节点，并将待传输数据转发至所述选定的关键子节点。

根据本发明提出的流式数据流图关键路径的加速方法，其中，所述后继节点包括第二标志位，第二选择逻辑和第二转发逻辑；所述第二标志位用于表示所述关键子节点中的数据是否有效，所述第二选择逻辑根据所述第二标志位选择数据有效的关键子节点，所述第二转发逻辑通过所述第二选择逻辑选择的数据有效的关键子节点，将待传输数据通过所述后继节点输出。

根据本发明提出的流式数据流图关键路径的加速方法，其中，当其中一个所述关键子节点中存有数据时，其对应的所述第一标志位置为“该关键子节点不可用”；当其中一个所述关键子节点中未存有数据时，其对应的所述第一标志位置为“该关键子节点可用”；当其中一个所述关键子节点中存储的数据有效时，其对应的所述第二标志位置为“可以转发该关键节点的数据”；当其中一个所述关键子节点中存储的数据无效时，其对应的所述第二标志位置为“不能转发该关键节点的数据”。

本发明还提供一种流式数据流图关键路径的加速系统，包括：

多个关键子节点，由数据流中的一个关键节点复制而成，所述多个关键子节点能够执行相同的操作；

前驱节点，位于所述多个关键子节点之前，用于从所述多个关键子节点中选择可用的关键子节点以传输数据；

后置节点，位于所述多个关键子节点之前，用于从所述多个关键子节点中选择数据有效的关键子节点，并将其中的有效数据传送出去。

根据本发明提出的流式数据流图关键路径的加速系统，其中，所述前驱节点包括第一标志位，第一选择逻辑和第一转发逻辑；所述第一标志位用于表示所述关键子节点能否接收数据，所述第一选择逻辑根据所述第一标志位从多个关键子节点中选择一个可用的关键子节点，所述第一转发逻辑用于接收所述第一选择逻辑选定的关键子节点，并将待传输数据转发至所述选定的关键子节点。

根据本发明提出的流式数据流图关键路径的加速系统，其中，所述后继节点包括第二标志位，第二选择逻辑和第二转发逻辑；所述第二标志位用于表示所述关键子节点中的数据是否有效，所述第二选择逻辑根据所述第二标志位选择数据有效的关键子节点，所述第二转发逻辑通过所述第二选择逻辑选择的数据有效的关键子节点，将待传输数据通过所述后继节点输出。

根据本发明提出的流式数据流图关键路径的加速系统，其中，当其中一个所述关键子节点中存有数据时，其对应的所述第一标志位置为“该关键子节点不可用”；当其中一个所述关键子节点中未存有数据时，其对应的所述第一标志位置为“该关键子节点可用”；当其中一个所述关键子节点中存储的数据有效时，其对应的所述第二标志位置为“可以转发该关键节点的数据”；当其中一个所述关键子节点中存储的数据无效时，其对应的所述第二标志位置为“不能转发该关键节点的数据”。

本发明同时还提供一种包括上述流式数据流图关键路径的加速系统的装置。

本发明同时还提供一种包括上述流式数据流图关键路径的加速系统的芯片。

与现有技术相比，本发明的有益效果在于：

本发明只对数据流图当中单个操作数存储空间进行优化，使得单个操作数存储空间当中的关键路径中的关键操作可以并行执行，从而缩短了数据流图中关键路径的执行时间，执行效率较传统结构有明显优势。

附图说明

图1为传统数据流图关键路径加速实现方式；

图2为流式数据流结构的关键路径加速方法相对传统方法改变；

图3为Map节点的结构图；

图4为Merge节点的结构图；

图5为流式数据流结构的关键路径加速方法实施例。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有付出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

请参阅图2，其中左边为传统的数据流体系结构，右边为使用本发明的方法的得到的新的数据流图。其中图2左边的节点3为关键操作节点，图2右边3.1和3.2是关键子节点，并且可以做同样的操作，子节点3.1、3.2均连接同一个Map节点和Merge节点。

本发明提出的一种加速关键路径的方法具体包括：

在单个操作数存储空间当中，将关键操作节点复制多份得到多个关键子节点。每一个关键子节点可以做相同的操作，但是关键子节点之间没有依赖关系，并且所有关键子节点具有相同的前驱节点(Map)和后继节点(Merge)，前驱节点和后继节点中具有可以识别数据去向/来自于哪个关键子节点的标志位。复制多份的关键操作的节点就是给操作数存储空间在关键路径上提供了多条数据通路，对于每一次的数据，其流过的指令个数和传统结构是一样的。

在关键操作子节点之前加入Map节点，即所有的关键子节点的前驱节点就是Map节点，在没有加入Map节点的时候，只有一个关键节点，数据只有单条通路。在加入了Map节点之后，并且有多个相同的关键子节点，提供了多条数据通路。Map节点负责将前驱节点的数据分发给关键子节点。Map节点的结构如图3所示，在Map节点中存在标志位，选择逻辑及转发逻辑三个模块。标志位为关键子节点给予Map节点的反馈，标志着关键子节点中是否空闲，如果关键子节点不空闲，则标志位标志着不能够继续向该关键子节点传输数据，如果关键子节点空闲，则在标志位当中标志着可以向该关键子节点传输数据。选择逻辑的主要功能为从其众多后继节点的标志位当中选取一个可用的关键子节点，选取了这个子节点之后，选择逻辑清空这个子节点的标志位，置该关键子节点的标志位为“该节点不空闲”。转发逻辑的功能是接收选择逻辑选取的关键节点，将该次数据转发到此关键节点。

在关键子节点之后加入Merge节点，也是所有关键子节点的后继节点，在传统的操作数存储空间当中，只有一条数据通路，在新提出的加速关键路径的方法，基于以上提出的两种结构，有多个关键子节点形成了多条数据通路，Merge节点的主要功能是将关键子节点中的数据串行发送给后继节点。Merge节点的结构如图4所示，在Merge节点中存在着标志位、选择逻辑、转发逻辑三个模块。其中标志位为关键子节点给予Merge节点的反馈，标志着关键子节点给予Merge节点的数据是否有效，如果数据无效，则标志位标志着Merge不能转发该关键子节点的数据，如果关键子节点数据有效，则在标志位当中标志着可以转发该关键子节点传输过来的数据。选择逻辑的主要功能为从其众多后继节点的标志位当中选取一个可用的关键子节点，选取了这个子节点之后，选择逻辑清空这个子节点的标志位，置该关键子节点为“数据无效”。转发逻辑的功能是接收选择逻辑选取的关键子节点，将该关键子节点的数据转发到Merge节点的后继节点。

Map节点和Merge节点的结构均有标志位、选择逻辑、转发逻辑三个模块，并且标志位均为关键子节点对这两个特殊节点的反馈。不同的是，Map节点中的标志位是标志着关键子节点中是否空闲可用，是否能向其转发新的数据；而Merge节点中的标志位则标志着关键子节点中的数据是否有效可用，是否能够将关键子节点的数据转发出去。Map节点是将数据分发至关键子节点，Merge节点是将关键子节点的数据转发出来。另外，Map节点是一条数据流分发到多条数据通路中的一条，而Merge节点是将多条数据通路中的数据，选择一条至其后继节点。从物理上看，Map节点的通路是一对多通路，而Merge节点的通路是多对一的通路，但是从逻辑上来看，Map节点与Merge节点数据只有一条逻辑通路。

与传统的加速关键路径方法不同，传统的方法是通过复制多个操作数存储空间来增加指令之间的并行，是在指令级层面上增加程序的并行性，其每复制一次操作数存储空间，就需要将整个数据流图复制一份，每一个操作数存储空间的关键路径仍然存在。而本发明中提出的方法为对操作数存储空间进行优化，对于同一个操作数存储空间提出了多条数据通路，是更细粒度的优化方法，并且本发明提出的方法与传统方法可以复用，以达到更高的执行效率。

同时本发明还提出了一种流式数据流图关键路径的加速系统及包含该系统的装置。

请继续参阅图5，本实施例中将会说明单个操作数存储空间在6个基础时间基础拍内，操作数存储空间中的数据流动情况，其中A节点与B节点为关键子节点，其均可以实现相同的功能。假设在初始化的时候，数据图中并没有数据流通，从第1个时间拍开始，数据流图中开始灌入第N次的数据。假设关键子节点执行需要2-3个时间拍才能够结束。

步骤501：第N次数据到达Map节点，Map节点判断其后继节点，发现A节点与B节点均处于空闲状态，其状态位为11，其将数据转发至A节点(假设第N次数据需要在关键操作中执行3个时间拍)，并且将状态位置为01。节点A接收到第N次数据，开始执行(执行了第1个时间拍)；节点B中没有数据，没有执行。而Merge节点的状态位为00，没有有效数据，所以其并没有向其后继结点转发数据。

步骤502：第N+1次数据到达Map节点，Map节点判断其后继节点，发现状态位为01，Map节点将第N+1次数据转发至B节点(假设第N+1次数据需要执行2个时间拍)，并且将状态位置为00。节点A正在执行第N次的数据(执行了1个时间拍)，节点B开始执行第N+1次数据(执行了0个时间拍)。而Merge节点的状态位为00，没有有效数据，所以其并没有向其后继结点转发数据。

步骤503：第N+2次数据到达Map节点，Map节点判断其后继节点，发现状态位为00，并没有转发N+2次的数据。节点A正在执行第N次的数据(执行了2个时间拍)，节点B开始执行第N+1次数据(执行了1个时间拍)。而Merge节点的状态位为00，没有有效数据，所以其并没有向其后继结点转发数据。

步骤504：因为上次N+2次数据没有被转发，所以当拍还是第N+2次数据到达Map节点，Map节点判断其后继节点，发现状态位为00，并没有转发N+2次的数据。节点A正在执行第N次的数据(执行了3个时间拍)，节点B开始执行第N+1次数据(执行了2个时间拍)。节点A的数据和节点B的数据同时执行完毕，并且将Merge节点的状态位置为11；Merge节点的状态位为11，选取B节点的数据进行转发，并且将其状态位置为10。

步骤505：因为上次N+2次数据没有被转发，所以当拍还是第N+2次数据到达Map节点，Map节点判断其后继节点，发现状态位为11，Map节点将第N+2次数据转发至B节点(假设第N+2次数据需要执行2个时间拍)，并且将状态位置为10。节点A处于空闲状态，节点B开始执行第N+2次数据(执行了0个时间拍)。Merge节点的状态位为10，选取A节点的数据进行转发，并且将其状态位置为00。

步骤506：第N+3次数据到达Map节点，Map节点判断其后继节点，发现状态位为01，Map节点将第N+3次数据转发至A节点(假设第N+3次数据需要执行2个时间拍)，并且将状态位置为00。节点A开始执行第N+3次的数据(执行了0个时间拍)，节点B开始执行第N+2次数据(执行了1个时间拍)。Merge节点的状态位为00，没有有效数据，所以其并没有向其后继结点转发数据。

本领域普通技术人员可以理解：附图只是一个实施例的示意图，附图中的模块或流程并不一定是实施本发明所必须的。

本领域普通技术人员可以理解：实施例中的装置中的模块可以按照实施例描述分布于实施例的装置中，也可以进行相应变化位于不同于本实施例的一个或多个装置中。上述实施例的模块可以合并为一个模块，也可以进一步拆分成多个子模块。

最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明实施例技术方案的精神和范围。