数据流架构上的指令动态调度方法、数据流架构与流程

1.本发明涉及计算机体系结构领域，特别是数据流架构上的指令动态调度方法、数据流架构。

背景技术：

2.随着计算机技术研究的深入和竞争的加剧，高性能计算技术被越来越多的应用于各个领域，以解决科学研究和社会生产中所遇到的实际问题。在高性能计算领域，数据流计算体现了良好的计算性能和适用性。数据流架构通常都包括若干个或者几十个计算节点(processing element,pe)，每个计算节点具有运算能力强、控制能力弱、且复杂度小的特点，多个计算节点间通过片上网络noc(一般是2d mesh)进行互连，由片上路由(router)负责在计算节点(pe)之间传递操作数。在数据流架构中，数据流程序是通过数据流图来表示的，数据流图中的每个节点表示一条指令，每条边表示一条指令与另一条指令之间的依赖关系。数据流指令执行的基本原则是：指令所有源操作数都准备好了，且其下游指令有空闲的数据槽可以接收数据，则该指令可以发射执行，指令执行结果不会写入共享寄存器或共享缓存，而是通过依赖边直接传递给其下游目的指令。对数据流架构来说，如何将数据流图更好的调度到多个计算节点上执行是数据流计算过程中急需解决的关键问题，一个好的指令调度算法在提高数据流计算性能方面起着至关重要的作用。
3.指令调度一般分为软件实现的静态调度方法和硬件实现的动态调度方法。在数据流架构中，由于指令通信方式对软件可见，因此通常采用静态调度方式，由编译器负责完成指令在数据流计算节点上的静态放置，编译器在把程序编译为数据流图的阶段，会综合考虑计负载的均衡、指令间的通信距离以及运算单元之间的冲突等相关因素，以寻求较优的静态调度结果。在数据流架构中，静态调度方法能够保证每个计算节点全局负载的均衡性(数据流程序整个执行过程中，每个计算节点上总计算量基本相同)，但在动态执行过程中，计算节点可能存在局部负载不均衡的问题(数据流程序执行某一时间段，只有部分计算节点忙碌，而另一部分节点处于等待空闲状态)，而局部负载不均衡会浪费计算节点功能单元的计算能力，并导致数据流架构执行效率低下。

技术实现要素：

4.针对现有技术的不足，本发明提出数据流架构上的指令动态调度方法、数据流架构，能够解决数据架构动态执行过程中计算节点局部负载不均衡的问题，从而提升数据流架构的执行效率。
5.具体而言，本发明提供了以下的技术方案：
6.作为本发明的第一方面，本发明提供了一种数据流架构上的指令动态调度方法，包括：
7.在一个时间点时，计算计算节点的负载信息；
8.接收与所述计算节点相邻的多个相邻节点的负载信息，其中所述计算节点分别与
多个所述相邻节点通过专用互连总线连接；
9.根据多个所述相邻节点的负载信息，从指令存储单元中选择一优先调度指令；
10.以及
11.执行所述优先调度指令。
12.在本发明一实施例中，根据所述相邻节点的负载信息，从指令存储单元中选择一优先调度指令，包括：
13.根据多个所述相邻节点的负载信息，在所述相邻节点中查目的方向动态执行负载最低的相邻节点；以及
14.从所述指令存储单元中选择一优先调度指令，其中，所述优先调度指令的目的方向为所述目的方向动态执行负载最低的相邻节点。
15.在本发明一实施例中，根据多个所述相邻节点的负载信息，在所述相邻节点中查目的方向动态执行负载最低的相邻节点，包括：
16.根据多个所述相邻节点的负载信息，查指令处于“ready”状态的指令条数最少的相邻节点；
17.其中，所述目的方向动态执行负载最低的相邻节点为指令处于“ready”状态的指令条数最少的相邻节点。
18.在本发明一实施例中，所述时间点为指令流水线中的时间拍。
19.在本发明一实施例中，所述计算节点的相邻节点的数量为四。
20.作为本发明的第二方面，本发明还提供了一种数据流架构，包括：
21.多个计算节点，相邻两个所述计算节点通过专用互连总线连接；
22.其中，一个所述计算节点包括：
23.指令存储单元，所述指令存储单元内存储指令；
24.负载统计模块，用于实时计算计算节点的负载信息，其中所述计算节点分别与多个所述相邻节点通过专用互连总线连接；
25.收发模块，与所述负载统计模块通信连接，用于实时接收与所述计算节点相邻的多个相邻节点的负载信息，并将所述计算节点的负载信息发送至相邻节点；
26.指令发射选择模块，用于根据多个所述相邻节点的负载信息，从所述指令存储单元中选择一优先调度指令；以及
27.运算单元，所述运算单元用于执行所述优先调度指令。
28.在本发明一实施例中，当所述计算节点可保存的指令条数最多为2^n时，所述专用互连总线的线宽为2n，其中n为大于或者等于一的整数。
29.本发明实施例提供的一种数据流架构上的指令动态调度方法，在对计算节点上已经静态分配的数据流指令进行调度时，即在一个计算节点上选择一条指令进行调度执行时，同时考虑该计算节点的所有相邻节点的负载情况，即，基于该计算节点所有的相邻节点的负载情况来选择指令调度，例如优先选择目的方向负载低的指令进行调度，通过加速负载低计算节点数据供应来提高其计算负载，以缓解数据流程序动态执行过程中，计算节点存在的局部负载不均衡性问题，从而提高数据流架构的执行效率。
附图说明
30.图1为本发明一实施例的一种数据流架构上的指令动态调度方法的流程示意图；
31.图2为本发明另一实施例的一种数据流架构上的指令动态调度方法的流程示意图；
32.图3为本发明实施例的一种数据流架构的结构示意图；
33.图4为本发明实施例的一种数据流架构中的一个计算节点的结构示意图；
34.图5所示为本发明实施例提供的一个计算节点在cycle1时该计算节点的指令动态调度示意图；
35.图6所示为本发明实施例提供的一个计算节点在cycle2时该计算节点的指令动态调度方法示意图。
具体实施方式
36.下面将结合本发明实施例中的图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有付出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
37.图1所示为本发明一实施例提供的一种数据流架构上的指令动态调度方法的流程示意图，如图1所示，该数据流架构上的指令动态调度方法，包括以下步骤：
38.步骤s101：在一个时间点时，计算计算节点的负载信息；
39.具体的，一个时间点即为指令流水线中的时间拍。
40.步骤s102：接收与所述计算节点相邻的多个相邻节点的负载信息，其中所述计算节点分别与多个所述相邻节点通过专用互连总线连接；
41.具体的，专用互连总线能够用于实时收集邻居节点的负载信息，即通过专用互连总线，可以使得计算节点实时获取与其相邻的计算节点的负载信息，与此同时，也可以将其自身的负载信息传送给其他相邻的计算节点。
42.步骤s103：根据多个所述相邻节点的负载信息，从指令存储单元中选择一优先调度指令；以及
43.步骤s104：执行所述优先调度指令。
44.即该计算节点从指令存储单元中选取的指令，就是在当前计算节点的运算单元中执行。执行的结果是通过router发送给其他计算节点。
45.本发明实施例提供的一种数据流架构上的指令动态调度方法，在对计算节点上已经静态分配的数据流指令进行调度时，即在一个计算节点的选择一条指令进行调度执行时，同时考虑该计算节点的所有相邻节点的负载情况，即，基于该计算节点所有的相邻节点的负载情况来选择指令调度，例如优先选择目的方向负载低的指令进行调度，通过加速负载低计算节点数据供应来提高其计算负载，以缓解数据流程序动态执行过程中，计算节点存在的局部负载不均衡性问题，从而提高数据流架构的执行效率。
46.具体的，如图2所示，根据所述相邻节点的负载信息，从指令存储单元中选择一优先调度指令，即步骤s103包括以下步骤：
47.步骤s1031：根据多个所述相邻节点的负载信息，在所述相邻节点中查目的方向
动态执行负载最低的相邻节点；
48.步骤s1032：从所述指令存储单元中选择一优先调度指令，其中，所述优先调度指令的目的方向为所述目的方向动态执行负载最低的相邻节点；
49.具体的，当一个计算节点周围有东、南、西、北四个相邻计算节点时，处于“ready”状态指令条数最少的相邻节点有东相邻计算节点和北相邻计算节点时，从所述指令存储单元中选择一优先调度指令，其中，所述优先调度指令的目的方向为东相邻计算节点或北相邻计算节点。
50.即本发明实施例在对计算节点上已经静态分配的数据流指令进行调度时，选取优先调度的指令时，指令选取的依据为：计算节点的所有相邻接节点中处于“ready”状态指令条数最少的相邻节点，即目的方向动态执行负载最低的相邻节点，即在选择调度指令时，是以该计算节点的所有相邻接节点进行考虑，通过加速负载低计算节点数据供应来提高其计算负载，以缓解数据流程序动态执行过程中，计算节点存在的局部负载不均衡性问题，从而提高数据流架构的执行效率。
51.具体的，在至少一个所述相邻节点中查目的方向动态执行负载最低的相邻节点，即步骤s1032具体包括：
52.根据多个相邻节点的负载信息，查处于“ready”状态的指令条数最少的相邻节点；其中，目的方向动态执行负载最低的相邻节点为处于“ready”状态的指令条数最少的相邻节点。
53.即在对计算节点上已经静态分配的数据流指令进行调度时，即在一个计算节点的选择一条指令进行调度执行时，通过加速负载低计算节点数据供应来提高其计算负载，以缓解数据流程序动态执行过程中，计算节点存在的局部负载不均衡性问题，从而提高数据流架构的执行效率。
54.可选的，一个计算节点的相邻节点的数量为四，例如一个计算节点周围可以有位于该计算节点东、南、西、北四个方向上的四个相邻节点。
55.作为本发明的第二方面，本发明实施例提供了一种数据流架构，如图3所示，该数据流架构包括：
56.多个计算节点pe，相邻两个所述计算节点pe通过专用互连总线连接；
57.其中，如图4所示，一个所述计算节点pe，包括：
58.指令存储单元100，用于存储指令；
59.负载统计模块200，用于实时计算计算节点pe的负载信息，其中所述计算节点pe分别与多个所述相邻节点通过专用互连总线500连接；
60.收发模块300，用于实时接收与所述节点相邻的多个相邻节点的负载信息，并将所述计算节点pe的负载信息发送至相邻节点；
61.指令发射选择模块400，用于根据多个所述相邻节点的负载信息，从指令存储单元，即指令存储单元中选择一优先调度指令；以及
62.运算单元600，运算单元执行所述优先调度指令。
63.即该计算节点中的指令发射选择模块400从指令存储单元中选取的指令，就是在当前计算节点的运算单元600中执行。执行的结果是通过router发送给其他计算节点。
64.具体的，当指令发射选择模块400在选择优先调度指令时，首先根据该计算节点pe
的多个相邻节点的负载信息，查指令处于“ready”状态的指令条数最少的相邻节点；以及从所述指令存储单元中选择一优先调度指令，其中，所述优先调度指令的目的方向为所述目的方向动态执行负载最低的相邻节点。例如，当一个计算节点pe周围有东、南、西、北四个相邻节点时，根据东、南、西、北四个相邻节点的目的方向动态执行负载，目的方向动态执行负载最低的相邻节点，例如北相邻节点的目的方向动态执行负载小于东相邻节点的目的方向动态执行负载，那么目的方向动态执行负载最低的相邻节点则为北相邻节点，那么该计算节点pe的北相邻节点则为调度指令的方向。
65.即本发明实施例在对计算节点上已经静态分配的数据流指令进行调度时，选取优先调度的指令时，指令选取的依据为：处于“ready”状态的指令条数最少的相邻节点，即在选择调度指令时，是以该计算节点pe的所有相邻接节点进行考虑，通过加速负载低计算节点pe数据供应来提高其计算负载，以缓解数据流程序动态执行过程中，计算节点pe存在的局部负载不均衡性问题，从而提高数据流架构的执行效率。
66.可选的，当所述计算节点pe可保存的指令条数最多为2^n时，
67.，专用互连总线的线宽为2n，其中n为大于或者等于一的整数。
68.可选的，计算节点pe呈阵列排列，16个计算节点pe通过2d mesh网络实现互连，此外计算节点pe间还设置有专用互连总线。如图3所示，每个计算节点pe(除阵列边缘计算节点外)都与其(东、西、南、北)四个邻居节点通过专用互连总线进行连接，而位于阵列边缘的计算节点pe，当它有几个邻居节点，即与几个邻居节点互连，例如位于阵列边缘的计算节点pe有2个邻居节点，那么该计算节点pe则与该2个邻居节点通过专用互连总线进行连接。而当每个计算节点pe上最多可存储2^n条指令时，专用互连总线位宽为2n(n bit编码)。
69.为了更好的理解数据流架构上的节点调度方法，下面通过一个具体的实施例来描述数据流架构上的节点调度方法。
70.如图3所示，数据流架构包括16个计算节点，且16个计算节点呈4x4阵列排列。其中，如图4所示，一个计算节点pe除了包括指令存储单元100之外，还包括负载统计模块200，用于实时计算计算节点的负载信息，其中所述计算节点pe分别与多个相邻节点通过专用互连总线连接；收发模块300，用于实时接收与节点相邻的多个相邻节点的负载信息，并将计算节点pe的负载信息发送至相邻节点；指令发射选择模块400，用于根据多个相邻节点的负载信息，从指令存储单元中选择一优先调度指令，运算单元600则对该优先调度指令进行执行，执行的结果为通过router发送至其他计算节点。
71.其中，数据流架构上的节点调度方法分为两个阶段进行介绍：
72.cycle 1:
73.如图5所示，此时间点，该计算节点的4个相邻的相邻计算节点分别为：south、west、north、east四个方向的相邻计算节点，此时负载统计模块和收发模块将当前计算节点和相邻计算节点的负载信息(“ready”指令条数)提供给指令发射选择模块，指令发射选择模块基于相邻计算节点的“ready”指令条数由少到多(即：负载由低到高)对当前计算节点和相邻计算节点进行排序：south《west《north《self《east，并根据排序结果，说明south相邻计算节点动态执行负载最低，因此，在指令存储单元中选择优先调度指令，该优先调度指令的目的方向为south，并发送到运算单元600进行执行，执行的结果通过router发送至其他计算节点。
74.cycle 2:
75.如图6所示，此时间点，指令发射选择模块基于负载统计模块和收发模块提供的“ready”指令条数得到的排序结果为：west《east《self《north《south，因此，选择了inst0作为优先调度指令，发送到运算单元600进行执行，执行的结果通过router发送至其他计算节点。
76.本发明实施例还提供了一种电子设备，电子设备包括一个或多个处理器和存储器。
77.处理器可以是中央处理单元(cpu)或者具有数据处理能力和/或指令执行能力的其他形式的处理单元，并且可以控制电子设备中的其他组件以执行期望的功能。
78.存储器可以包括一个或多个计算机程序产品，所述计算机程序产品可以包括各种形式的计算机可读存储介质，例如易失性存储器和/或非易失性存储器。所述易失性存储器例如可以包括随机存取存储器(ram)和/或高速缓冲存储器(cache)等。所述非易失性存储器例如可以包括只读存储器(rom)、硬盘、闪存等。在所述计算机可读存储介质上可以存储一个或多个计算机程序指令，处理器可以运行所述程序指令，以实现上文所述的本技术的各个实施例的数据流架构上的指令动态调度方法以及/或者其他期望的功能。在所述计算机可读存储介质中还可以存储诸如输入信号、信号分量、噪声分量等各种内容。
79.除了上述方法和设备以外，本技术的实施例还可以是计算机程序产品，其包括计算机程序指令，所述计算机程序指令在被处理器运行时使得所述处理器执行本说明书上述描述的根据本技术图1、图2所示实施例的一种数据流架构上的指令动态调度方法的步骤。
80.所述计算机程序产品可以以一种或多种程序设计语言的任意组合来编写用于执行本技术实施例操作的程序代码，所述程序设计语言包括面向对象的程序设计语言，诸如java、c++等，还包括常规的过程式程序设计语言，诸如“c”语言或类似的程序设计语言。程序代码可以完全地在用户计算设备上执行、部分地在用户设备上执行、作为一个独立的软件包执行、部分在用户计算设备上部分在远程计算设备上执行、或者完全在远程计算设备或服务器上执行。
81.此外，本技术的实施例还可以是计算机可读存储介质，其上存储有计算机程序指令，所述计算机程序指令在被处理器运行时使得所述处理器执行本说明书上述描述的根据本技术各种实施例的数据流架构上的指令动态调度方法的步骤。
82.所述计算机可读存储介质可以采用一个或多个可读介质的任意组合。可读介质可以是可读信号介质或者可读存储介质。可读存储介质例如可以包括但不限于电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者任意以上的组合。可读存储介质的更具体的例子(非穷举的列表)包括：具有一个或多个导线的电连接、便携式盘、硬盘、随机存取存储器(ram)、只读存储器(rom)、可擦式可编程只读存储器(eprom或闪存)、光纤、便携式紧凑盘只读存储器(cd-rom)、光存储器件、磁存储器件、或者上述的任意合适的组合。
83.以上结合具体实施例描述了本技术的基本原理，但是，需要指出的是，在本技术中提及的优点、优势、效果等仅是示例而非限制，不能认为这些优点、优势、效果等是本技术的各个实施例必须具备的。另外，上述公开的具体细节仅是为了示例的作用和便于理解的作用，而非限制，上述细节并不限制本技术为必须采用上述具体的细节来实现。
84.本技术中涉及的器件、装置、设备、系统的方框图仅作为例示性的例子并且不意图
要求或暗示必须按照方框图示出的方式进行连接、布置、配置。如本领域技术人员将认识到的，可以按任意方式连接、布置、配置这些器件、装置、设备、系统。诸如“包括”、“包含”、“具有”等等的词语是开放性词汇，指“包括但不限于”，且可与其互换使用。这里所使用的词汇“或”和“和”指词汇“和/或”，且可与其互换使用，除非上下文明确指示不是如此。这里所使用的词汇“诸如”指词组“诸如但不限于”，且可与其互换使用。
85.还需要指出的是，在本技术的装置、设备和方法中，各部件或各步骤是可以分解和/或重新组合的。这些分解和/或重新组合应视为本技术的等效方案。
86.提供所公开的方面的以上描述以使本领域的任何技术人员能够做出或者使用本技术。对这些方面的各种修改对于本领域技术人员而言是非常显而易见的，并且在此定义的一般原理可以应用于其他方面而不脱离本技术的范围。因此，本技术不意图被限制到在此示出的方面，而是按照与在此公开的原理和新颖的特征一致的最宽范围。
87.为了例示和描述的目的已经给出了以上描述。此外，此描述不意图将本技术的实施例限制到在此公开的形式。尽管以上已经讨论了多个示例方面和实施例，但是本领域技术人员将认识到其某些变型、修改、改变、添加和子组合。
88.最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明实施例技术方案的精神和范围。

技术特征：

1.一种数据流架构上的指令动态调度方法，其特征在于，包括：在一个时间点时，计算计算节点的负载信息；接收与所述计算节点相邻的多个相邻节点的负载信息，其中所述计算节点分别与多个所述相邻节点通过专用互连总线连接；根据多个所述相邻节点的负载信息，从指令存储单元中选择一优先调度指令；以及执行所述优先调度指令。2.根据权利要求1所述的数据流架构上的指令动态调度方法，其特征在于，根据所述相邻节点的负载信息，从指令存储单元中选择一优先调度指令，包括：根据多个所述相邻节点的负载信息，在所述相邻节点中查目的方向动态执行负载最低的相邻节点；以及从所述指令存储单元中选择一优先调度指令，其中，所述优先调度指令的目的方向为所述目的方向动态执行负载最低的相邻节点。3.根据权利要求2所述的数据流架构上的指令动态调度方法，其特征在于，根据多个所述相邻节点的负载信息，在所述相邻节点中查目的方向动态执行负载最低的相邻节点，包括：根据多个所述相邻节点的负载信息，查指令处于“ready”状态的指令条数最少的相邻节点；其中，所述目的方向动态执行负载最低的相邻节点为指令处于“ready”状态的指令条数最少的相邻节点。4.根据权利要求1所述的数据流架构上的指令动态调度方法，其特征在于，所述时间点为指令流水线中的时间拍。5.根据权利要求1所述的数据流架构上的指令动态调度方法，其特征在于，所述计算节点的相邻节点的数量为四。6.一种数据流架构，其特征在于，包括：多个计算节点，相邻两个所述计算节点通过专用互连总线连接；其中，一个所述计算节点包括：指令存储单元，所述指令存储单元内存储指令；负载统计模块，用于实时计算计算节点的负载信息，其中所述计算节点分别与多个所述相邻节点通过专用互连总线连接；收发模块，与所述负载统计模块通信连接，用于实时接收与所述计算节点相邻的多个相邻节点的负载信息，并将所述计算节点的负载信息发送至相邻节点；指令发射选择模块，用于根据多个所述相邻节点的负载信息，从所述指令存储单元中选择一优先调度指令；以及运算单元，所述运算单元用于执行所述优先调度指令。7.根据权利要求6所述的数据流架构，其特征在于，当所述计算节点可保存的指令条数最多为2^n时，所述专用互连总线的线宽为2n，其中n为大于或者等于一的整数。

技术总结

本发明提出一种数据流架构上的指令动态调度方法、数据流架构，解决了现有技术中数据架构动态执行过程中计算节点局部负载不均衡的问题。本发明实施例提供的一种数据流架构上的指令动态调度方法，在对计算节点上已经静态分配的数据流指令进行调度时，同时考虑该计算节点的所有相邻节点的负载情况，即，基于该计算节点所有的相邻节点的负载情况来选择指令调度，例如优先选择目的方向负载低的指令进行调度，通过加速负载低计算节点数据供应来提高其计算负载，以缓解数据流程序动态执行过程中，计算节点存在的局部负载不均衡性问题，从而提高数据流架构的执行效率。而提高数据流架构的执行效率。而提高数据流架构的执行效率。