由计算机实现的方法、系统及存储介质与流程

1.本公开涉及计算机领域，具体而言，涉及由计算机实现的方法、系统及非暂时性计算机可读存储介质。

背景技术：

2.图(graph)是数据结构或数据库的一种类型，其由计算系统存储和执行，并用于建立一组对象和该组对象之间的连接(关系)的模型。各对象表示为图中由边连接或链接的节点(或顶点)。对象的特性或属性与用于表示该对象的节点相关联。
3.图可用于识别大型数据集中的依赖、聚类、相似性、匹配、类别、流、成本、中心性等。图被用在多种类型的应用中，这多种类型的应用广泛地包括但不限于图分析和图神经网络(graph neural networks,可简称为gnn)，更具体地，包括诸如在线购物引擎、社交网络、推荐引擎、映射引擎(mapping engine)、故障分析、网络管理和搜索引擎等应用。在用于面部识别的应用程序中，采样的节点(像素)可能会彼此靠近分组，而与此不同的是，在上述类型的应用程序中，采样的节点可能会通过多跳(hop)彼此分开(即两个被采样的节点之间间隔了多个其它节点)，访问可能是随机的或是不规则的。
4.图允许对关系系统中难以建模的复杂层次结构进行更快的检索和导航。与图相关联的大量处理操作包括图遍历操作，例如指针追逐，该操作读取节点以确定一个或多个边，被确定的一个或多个边指向并连接到一个或多个其他节点，这一个或多个其它节点可以依次被读取以确定相应的其他边，依此类推。
5.图数据一般包括节点结构信息和属性。节点结构信息可以包括，例如，标识节点的信息(例如，节点标识符，即节点identifier，可简称为节点id)和用于标识该节点的邻居节点的信息。属性可以包括对象的特征或性质以及这些特征或性质的值，该对象由该节点表示且该对象的特征或性质与用于表示该对象的节点相关联。例如，如果该对象表示一个人，那么其特征可能包括这个人的年龄和性别，在这种情况下，属性也包括表征年龄的值和表征性别的值。
6.图的尺寸为兆兆字节(terabytes)的级别。图可以包含数十亿个节点和数万亿条边。因此，图可以划分为多个子图，并且多个子图可以跨多个设备分布，即一个大尺寸的图可以被划分为存储在不同设备中的多个较小尺寸的子图。
7.节点采样阶段是造成与图相关的延迟的主要原因之一，每个节点和边都有相关的性能成本，因此对大尺寸的图中的数据进行访问的总通信成本(例如，引起的延迟和消耗的带宽)可能非常高。由于设备之间的信息传输增加了延迟，因此分布式图中的延迟也相应的增加。
8.减少与大尺寸的图(尤其是分布式图)相关的延迟将是有益的。

技术实现要素：

9.根据本公开的实施例提供了用于解决上述问题的方案。总的来说，根据本公开的
实施例介绍了能够在分布式图架构中进行预取的方法和系统。
10.更具体地，在本公开的实施例中，将存储在计算系统中的图在逻辑上划分为多个子图，所述多个子图存储在计算系统中的多个不同的互连设备上，所述多个子图的节点包括连接相邻子图的中心节点(hub node)。
11.在本公开的实施例中，每个互连设备将所述多个子图的中心节点的属性和节点标识符(identifier,可简称为id)存储在其他互连设备上。此外，设备上的软件或硬件预取引擎对与被采样的节点相关联的属性和节点标识符进行预取。
12.进一步地，在本公开的实施例中，与各个互连设备相连接的设备上的预取器可以将任意互连设备上的子图的节点的属性、节点标识符和其他节点结构信息预取至需要或可能需要该节点属性和节点结构信息的其它互连设备。在本公开实施例中，接口设备上设置有流量监测器以监测流量，当流量较小时，接口设备预取节点属性。
13.根据本公开的第一方面，提供了一种由计算机实现的方法，包括：访问图中的多个中心节点，所述图包括多个节点且在逻辑上被划分为多个子图，所述子图包括至少一个所述中心节点，且所述子图中的每个所述中心节点将该子图分别连接至所述多个子图中的另一个所述子图；在第二设备中存储与所述多个子图中的第一子图的中心节点相关联的属性和节点结构信息，其中所述第二设备还用于存储所述多个子图中的第二子图的信息；以及在第一设备中存储与所述第二子图的中心节点相关联的属性和节点结构信息，其中所述第一设备还用于存储所述第一子图的信息。
14.在一些实施例中，与所述第一子图的中心节点相关联的属性和节点结构信息，以及与所述第二子图的中心节点相关联的属性和节点结构信息，包括以下属性和节点结构信息中的一个或多个：相应的属性值；相应的节点标识符；以及相应的节点结构。
15.在一些实施例中，所述方法还包括：当所述第一子图的中心节点与所述第一子图的根节点的间隔为单跳时，将与所述第一子图的中心节点相关联的属性和节点结构信息预取到所述第一设备的预取缓冲器中。
16.在一些实施例中，所述方法还包括：当所述第一子图的中心节点被采样、所述第一子图的中心节点与所述第一子图的根节点的间隔为单跳，且所述第一子图的中心节点与所述第二子图的中心节点的间隔为单跳时，将与所述第二子图的中心节点相关联的属性和节点结构信息预取到所述第一设备的预取缓冲器中。
17.在一些实施例中，所述方法还包括：获取与第一中心节点相邻的根节点所相邻的多个节点的节点标识符；对与这些节点标识符对应的节点的至少一个子集进行采样；以及将被采样的所述子集中的节点的属性预取到所述第一设备的预取缓冲器中。
18.在一些实施例中，所述方法还包括：将与所述多个节点中的一个节点相关联的属性和节点结构信息预取到第三设备中的缓冲器中，所述第三设备耦合于所述第一设备和所述第二设备。
19.在一些实施例中，所述方法还包括：利用所述第三设备监测流量，其中，当所述流量的测量值满足阈值时，执行所述预取。
20.在一些实施例中，响应于来自所述第一设备的请求，所述预取包括：获取所述第二设备上与第二中心节点相邻的多个节点的节点标识符；对与这些节点标识符相对应的节点的至少一个子集进行采样；以及将所述子集中的节点的属性提取到所述第三设备的所述缓
冲器中。
21.根据本公开实施例的第二方面，提供了一种系统，包括：处理器；连接至所述处理器的存储单元；以及连接至所述存储单元的多个互连设备，所述多个互连设备包括第一设备和第二设备，所述第一设备包括存储器和至少一个缓冲器，所述第二设备包括存储器和至少一个缓冲器；其中，所述第一设备用于对图的第一子图的节点的信息进行存储，所述第二设备用于对所述图的第二子图的节点的信息进行存储，所述图包括多个子图，所述第一子图的节点包括第一中心节点，所述第二子图的节点包括第二中心节点，所述第一中心节点和所述第二中心节点通过边相互连接，所述第一设备对与所述第二中心节点相关联的属性和节点结构信息进行存储，且所述第二设备对与所述第一中心节点相关联的属性和节点结构信息进行存储。
22.在一些实施例中，所述第一设备包括访问引擎，所述访问引擎被配置为：对与所述第一中心节点相邻的根节点所相邻的多个节点的节点标识符进行预取，对与这些节点标识符相对应的节点的至少一个子集进行采样，并获取所述子集中的节点的属性。
23.在一些实施例中，与所述第一中心节点相关联的属性和节点结构信息以及与所述第二中心节点相关联的属性和节点结构信息包括以下属性和节点结构信息中的一个或多个：相应的属性值；相应的节点标识符；以及相应的节点结构。
24.在一些实施例中，当所述第一中心节点与所述第一子图的根节点的间隔为单跳时，与所述第一中心节点相关联的属性和节点结构信息被预取到所述第一设备的预取缓冲器中。
25.在一些实施例中，当所述第一中心节点与根节点分隔并被采样，且所述第一中心节点与所述第二中心节点的间隔为单跳时，与所述第二中心节点相关联的属性和节点结构信息被预取到所述第一设备的预取缓冲器中。
26.在一些实施例中，所述系统还包括：连接至所述第一设备和所述第二设备的第三设备，所述第三设备包括预取缓冲器，并且所述第三设备将与所述多个节点中的一个节点相关联的属性和节点结构信息预取到预取缓冲器中。
27.在一些实施例中，所述第三设备还包括流量监测器，其中，当所述流量监测器所测量的流量满足阈值时，所述第三设备将与所述节点相关联的属性和节点结构信息预取到所述预取缓冲器中。
28.在一些实施例中，所述第三设备被配置为：响应于来自所述第一设备的请求，获取所述第二设备上与所述第二中心节点相邻的多个节点的节点标识符，对与这些节点标识符相对应的节点的至少一个子集进行采样，并将所述子集中的节点的属性提取到所述第三设备的预取缓冲器中。
29.在一些实施例中，所述第一设备包括第一现场可编辑逻辑门阵列，所述第二设备包括第二现场可编辑逻辑门阵列，所述第三设备包括连接至所述第一设备和所述第二设备的存储交换器。
30.根据本公开实施例的第三方面，还提供了一种非暂时性计算机可读存储介质，其中，包括存储在其中的计算机可执行指令，所述计算机可执行指令包括：第一指令，用于对图进行访问，所述图包括多个子图，所述多个子图包括第一子图和第二子图，所述第一子图包括具有第一中心节点的第一节点集合，所述第二子图包括具有第二中心节点的第二节点
集合，并且所述第一子图和所述第二子图由连接所述第一中心节点和所述第二中心节点的边相连接；第二指令，用于在第一设备中存储与第二中心节点相关联的属性和节点结构信息，所述第一设备还存储与所述第一子图相关的信息；以及第三指令，用于在第二设备中存储与第一中心节点相关联的属性和节点结构信息，所述第二设备还存储与所述第二子图相关的信息。
31.在一些实施例中，所述非暂时性计算机可读存储介质还包括：第四指令，用于在所述第一中心节点与所述第一子图的根节点的间隔为单跳的情况下，将与所述第一中心节点相关联的属性和节点结构信息预取到所述第一设备的预取缓冲器中。
32.在一些实施例中，所述非暂时性计算机可读存储介质还包括：第五指令，用于在所述第一中心节点被采样、所述第一中心节点与所述第一子图的根节点的间隔为单跳，且所述第一中心节点与所述第二中心节点的间隔为单跳的情况下，将与所述第二中心节点相关联的属性和节点结构信息预取到所述第一设备的预取缓冲器中。
33.在一些实施例中，所述非暂时性计算机可读存储介质还包括：第六指令，用于获取与所述第一中心节点相邻的根节点所相邻的节点的多个节点的节点标识符；第七指令，用于对与这些节点标识符相对应的节点的至少一个子集进行采样；以及第八指令，用于将被采样的所述子集中的节点的属性预取到所述第一设备的预取缓冲器中。
34.在一些实施例中，所述非暂时性计算机可读存储介质还包括：第九指令，用于将与所述多个节点中的一个节点相关联的属性和节点结构信息预取到第三设备的缓冲器中，所述第三设备耦合于所述第一设备和所述第二设备。
35.在一些实施例中，非暂时性计算机可读存储介质还包括：第十指令，用于采用所述第三设备监测流量，且当所述流量的测量值满足阈值时，将与所述节点相关的属性和节点结构信息预取到所述第三设备中的所述缓冲器中。
36.因此，根据本公开的实施例，与在多个互连设备之间传输信息的操作相关联的等待时间被消除，从而减少了计算系统的总通信成本。除了减少通信成本之外，计算系统的资源得以被更有效地利用。
37.本领域普通技术人员在阅读以下由各个附图所示的实施例的详细描述之后，将认识到本发明的各个实施例所具有的上述目的、其它目的以及优点。
附图说明
38.包含在本说明书中的附图形成了本说明书的一部分，其中相同/相似的标号描绘了相同/相似的元件，附图示出了本公开的一些实施例，并且与具体描述一起用于解释本公开的原理。
39.图1示出了根据本公开一些实施例的示例性的存储在计算系统上并由计算系统执行的图的分布式图架构的示意图；
40.图2a示出了根据本公开一些实施例的示例性的计算系统中的组件的示意性框图；
41.图2b示出了根据本公开一些实施例的示例性的分布式图的子图到计算系统中的设备的映射关系示意图；
42.图3示出了根据本公开一些实施例的用于存储和计算子图的设备的选定元素或选定组件的示意性框图；
43.图4示出了根据本公开一些实施例的分布式图中的两个相邻子图的元素的示意图；
44.图5示出了根据本公开一些实施例的与用于存储和计算子图的设备相连接的接口设备的示意性框图；
45.图6示出了根据本公开一些实施例的一种由计算机实现的方法的流程示意图。
具体实施方式
46.现在将详细参考本公开的各种实施例，其示例在附图中示出。尽管结合这些实施例进行了描述，但应当理解，它们的意图并不是将本公开限制于这些实施例。相反，本公开的意图是覆盖可包括在由所附权利要求限定的本公开的精神和范围内的替代、修改和等同方案。此外，在本公开的以下详细描述中，阐述了许多具体细节，以便提供对本公开的透彻理解。然而，需要理解的是，可以在没有这些特定细节的情况下实践本公开。另一方面，公知的方法、过程、组件和电路没有被详细描述，以避免不必要地模糊本公开的各方面。
47.下面详细描述的某些部分是根据对计算机存储器内的数据位执行的过程、逻辑块、处理和其它符号表示的操作来呈现的。这些描述和表示是数据处理领域的技术人员所使用的手段，以最有效地将其工作的实质传达给本领域的其他技术人员。在本技术中，过程、逻辑块、处理等被构思为导致期望结果的自洽的一系列的步骤或指令。这些步骤是利用物理量的物理操作。通常，尽管不一定，这些量采取能够在计算系统中存储、传输、组合、比较和以其他方式被操纵的电或磁信号的形式。主要出于通用的原因，将这些信号称为事务、比特、值、元素、符号、字符、样本、像素等有时被证明是便利的。
48.然而，应当记住，所有这些和类似的术语都应与适合的物理量相关联，并且仅仅是应用于这些量的便利标记。除非在以下讨论中另外有显而易见的特别说明，否则应当理解，在整个本公开中，使用诸如“访问”、“预取”、“采样”、“发送”、“写入”、“读取”、“划分”、“请求”、“存储”、“记录”、“传输”、“选择”等术语的讨论是指设备或计算系统或类似的电子计算设备或系统(例如，图2a、图2b、图3和图5所示的系统)的动作和处理过程(例如，图6所示的方法)。一种计算系统或类似的电子计算设备在存储器、寄存器或其它这样用于信息存储、传输或显示的设备内对表示为物理(电学)量的数据进行操作和变换。
49.可以在存在于由一个或多个计算机或其它设备执行的某种形式的计算机可读存储介质(例如程序模块)上的计算机可执行指令的一般上下文中讨论这里描述的一些元件或实施例。作为示例而非限制，计算机可读存储介质可以包括非暂时性计算机存储介质和通信介质。通常，程序模块包括用于执行特定任务或实现特定抽象数据类型的例程、程序、对象、组件、数据结构等。在各种实施例中，程序模块的功能可以根据需要结合或分布。
50.计算机存储介质包括以任何用于存储信息(诸如计算机可读指令、数据结构、程序模块或其他数据等)的方式或技术实现的易失性和非易失性、可移动和不可移动介质。计算机存储介质包括但不限于双倍数据速率(double data rate，可简称为ddr)存储器、随机存取存储器(random access memory，可简称为ram)、静态随机存取存储器(static random access memory，可简称为sram)、或动态随机存取存储器(dynamic random access memory，可简称为dram)、只读存储器(read only memory，可简称为rom)、电可擦除可编程只读存储器(electrically erasable programmable read only memory，可简称为
eeprom)、闪存(flash memory，例如ssd)或其它存储器技术、致密盘只读存储器(compact disk read only memory，可简称为cd-rom)、数字多功能盘(digital versatile disk，可简称为dvd)或其它光存储器、盒式磁带(magnetic cassette)、磁带(magnetic tape)、磁盘存储器(magnetic disk storage)或其它磁存储设备、或可用于存储所需信息并可访问以检索该信息的任何其它介质。
51.通信介质可以体现计算机可执行指令、数据结构和程序模块，并且包括任意信息传递介质。作为示例而非限制，通信介质包括诸如有线网络或直接有线连接的有线介质，以及诸如声学、射频(radio frequency,rf)、红外和其它无线介质的无线介质。上述任何一种的组合也可以包括在计算机可读介质的范围内。
52.图1示出了根据本公开一些实施例的示例性的存储在计算系统上并由计算系统(例如，如图2a、图2b、图3和图5所示的计算系统)执行的图的分布式图架构的示意图。在图1所示的示例中，图100在逻辑上被划分为三个社区(community)或子图102、104和106，然而，子图的数量不限于此。图100包括多个节点(各个节点在图1中表示为正方形)。
53.通常，社区是图中节点的子集，因此，社区内的边的数量大于将该社区与图的其他部分相链接的边的数量。可以使用诸如但不限于以下各项的社区检测算法将图100在逻辑上划分为社区或子图：克尼根
·
林(kernighan-lin，可简称为k-l)算法；吉文
·
纽曼(girvan-newman)算法；多层次(multi-level)算法；前导特征向量(leading eigenvector)算法；以及鲁汶(louvain)算法。
54.图100中的每个节点表示一个对象，对象的属性和结构信息与表示该对象的节点相关联。节点/对象的属性可以包括该对象的一个或多个特征或性质(例如，如果该对象表示一个人，那么其特征可能包括这个人的年龄和/或性别)，且属性数据可以包括这一个或多个特征的值(例如用于表征这个人的年龄的数值，以及用于标识这个人的性别的标志)。节点/对象的结构信息例如可以包括：用于标识节点的信息(例如，节点标识符)和用于标识识别与该节点相连的其他节点的信息。
55.通过一个或多个中心节点，每个子图经由相应的边连接到相邻的子图。例如，在图1中，子图102包括中心节点121、122和123，它们通过相应的边连接到子图104的中心节点161和162。子图102中的中心节点类似地连接至子图106中的中心节点，反之亦然，子图104中的中心节点类似地连接至子图106中的中心节点。
56.邻近或相邻的子图(例如，子图102和104)通过单跳(single hop)相互连接，例如，边110将中心节点121和161相连。图100中子图的节点也通过边互连。
57.图2a示出了根据本公开一些实施例的示例性的计算系统中的组件框图。计算系统200可以用于存储和执行如图1所示的示例中图100的分布式图架构。
58.在图2a所示的示例中，计算系统200包括多个中央处理单元(central processing unit，可简称为cpu)，例如包括cpu 202。在本公开实施例中，每个cpu包括或耦合至相应的图处理单元(graphics processing unit，可简称为gpu)，例如gpu 204。在一些实施例中，各个cpu经由网络接口卡(network interface card，可简称为nic)(例如，nic 208)连接到相应的架顶式(top-of-rack，可简称为tor)开关(例如，tor开关206)。
59.在本公开实施例中，每个cpu还连接至相应的设备或集成电路，例如连接至设备211、212、213、
……
、n(即设备211～n)。在图2a所示的实施例中，设备211-n是现场可编程门
阵列(field programmable gate array，可简称为fpga)。
60.在本公开实施例中，各个设备211～n之间按照某种方式互连，从而在这些设备中，任一设备均可以与任一其它设备进行通信，向任一其它设备传输数据，并从任一其它设备接收数据。在一些实施例中，设备211～n通过全连接局域网(fully connected local network，可简称为fcln)216互连。在后文的描述(结合图3所示)中，在一些实施例中，设备211～n中的每个设备均连接至接口设备316，接口设备316例如为存储交换器(memory-over-fabric，可简称为mof)。
61.图2b示出了根据本公开一些实施例的示例性的子图102、104和106到设备211～n的映射关系示意图。在这些实施例中，设备211～n中的每个设备存储并计算各自的子图。作为一个示例，子图102由设备211进行存储和计算，子图106由设备212进行存储和计算，子图104由设备213进行存储和计算，
62.图3示出了根据本公开一些实施例的用于存储和计算子图的设备(例如，设备211)的选定元件或选定组件的示意性框图。如下文所述，设备211还有利于对节点的属性和节点结构信息(例如，节点标识符)进行预取。图2a中所示的其它设备212、213、
……
、n(即设备212～n)的配置和功能类似于设备211。设备211～n可以包括除了以下示出和描述的元件或组件之外的元件或组件，并且各元件或组件可以如图所示或以不同的方式耦合。
63.在示例中，采用设备211中的某些模块执行的功能来对其进行描述。尽管描述和说明为单独的模块，但是本公开不限于此。也就是说，例如，可以将这些模块/功能的组合集成到执行多种功能的单个模块中。
64.在图3的实施例中，示例设备211包括耦合到命令调度器306的命令编码器302和命令解码器304。设备211包括或耦合到通信(通讯)接口308(例如，高级可扩展接口，advanced extensible interface)，以与图2a所示的系统200的其他设备(例如，cpu 202)进行通信。
65.设备211还经由加载单元(load unit，可简称为ld unit)310耦合到存储单元。如上所述，设备211可以对子图102进行存储和计算。存储单元包括设备211上的存储器312(例如ddr存储器)，其用于存储子图102中节点的属性、节点标识符以及其他节点结构信息。存储单元还包括主存储器314(例如，ram)，主存储器314耦合到设备211和其他设备212～n。
66.设备211还经由接口设备316(例如，mof)耦合至其它设备212～n，以访问其它设备上的子图。下面结合图4对接口设备216进行进一步描述。
67.值得注意的是，图3所示的设备211包括预取器320、具有预取缓冲器323的一个或多个缓冲器322、邻居获取模块332、样本获取模块334、属性获取模块336和编码获取模块338。预取缓冲器323用于存储被预取的节点属性。
68.在示例性的设备211中，预取器320、预取缓冲器323、邻居获取模块332、样本获取模块334，属性获取模块336和编码获取模块338构成了在设备211上实现的访问引擎(access engine，可简称为axe)的元件。该访问引擎可以实现为硬件或软件，或硬件和软件的组合。
69.在本公开实施例中，由于中心节点的数量相对较少，因此图100(参见图1)中所有子图中的所有中心节点的属性和节点结构信息(例如，节点标识符)都可以由系统200(参见图2a)中的每个设备211～n存储。
70.在图100(参见图1)的子图中，被关注的节点在本文中称为根节点。例如，节点可以
被选择，并且该节点(根节点)的属性可以被读取或获取。
71.然而，在一些情况下，可能并不能获知根节点的所有属性。例如，如果根节点表示的对象是一个人，则这个人的年龄可能被记录，但这个人的性别可能未被记录。然而，利用社区检测算法(用于将图100中的节点组织和划分为多个社区或多个子图)，根节点的未知属性从相邻节点(本文所述的相邻节点是通过单跳连接到该根节点的节点)的属性中推论或估计获得，可选的，该根节点的未知属性还可以基于附近节点(本文所述的附近节点是通过多跳连接到该根节点的节点)的属性推论或估计获得。
72.请参见图3，邻居获取模块332用于确定并从存储器312中提取与根节点相邻或在根节点附近的节点的节点标识符。节点标识符构成相对少量的数据，因此获得那些节点标识符仅消耗相对少量的系统资源(例如，带宽)。
73.然后，样本获取模块334对具有由邻居获取模块332标识的节点标识符的节点进行采样。采样得到的样本可以包括由邻居获取模块332标识的所有节点，或者仅包括这些节点的子集。例如，可以随机地或基于分配给节点的权重来选择这些节点的子集。节点的权重例如可以基于该节点与根节点的距离来确定，该距离是通过该节点与根节点之间的跳数来测量的。
74.之后，属性获取模块336从存储器312中获取由样本获取模块334采样的节点的属性。如上所述，如果样本获取模块334采样得到的样本仅包括选定的节点子集，则所获数据量(属性)降低，从而消耗更少的系统资源。
75.接着，编码获取模块338对所获取的属性进行编码，并将其写入主存储器(例如，ram 314)，在必要时，可以访问主存储器中这些属性，以进行其他处理。
76.在根据本公开的实施例中，当设备211(参见图3)中存储的子图中的根节点被选择，且所述根节点与所述子图的中心节点被单跳(single hop)分隔时，设备211可以将属性从存储器312预取到缓冲器322中。在这种情况下，存储在与设备211相邻的设备(例如，设备212)上的相邻子图的中心节点与所述根节点通过双跳(two hops)分离。在这种情况下，将设备211上的子图的中心节点的属性预取到预取缓冲器323中，并将相邻子图(例如存储在设备212上)的中心节点的属性预取到预取缓冲器323中，将有利于减少等待时间。然后，如果对上述中心节点之一进行采样，则可以直接从预取缓冲器323中获取其属性。
77.此外，如果对上述中心节点之一进行采样，则设备211可以通过接口设备316向其他设备(例如，设备212)发送请求，以对与该其他设备上的中心节点相邻的节点的属性进行预取。
78.图4示出了根据本公开一些实施例的图100中的两个相邻子图102和106中的元素示意图。在该示例中，子图102的中心节点415和子图106的中心节点425经由边405单跳连接，即子图102的中心节点415与子图106的中心节点425互为第一跳邻居节点。子图102包含与中心节点415相邻的节点413，即，节点413与中心节点415通过边414单跳连接。在该示例中，节点413与中心节点425通过边414和边405双跳连接。类似地，子图106包括与中心节点425相邻的节点423。在该示例中，节点413不是中心节点，在本公开中可被称为内部节点或非中心节点。子图102由设备211(在此可以称为第一设备)存储和计算，子图106由设备212(在此可以称为第二设备)存储和计算。
79.在一些实施例中，当节点413被选择作为根节点时，中心节点415的属性可以被预
取到第一设备211的预取缓冲器323中。类似地，当节点423被选择作为根节点时，中心节点415的属性可以被预取到第二设备212的预取缓冲器中。并且，当节点413被选择为根节点时，中心节点425的属性可以被预取到第一设备211的预取缓冲器323中。类似地，当节点423被选择为根节点时，中心节点425的属性可以被预取到第二设备212的预取缓冲器中。
80.通过如上所述的预取操作，与在互连设备之间传输信息相关联的等待时间在许多情况下可以被减少或消除，从而减少了计算系统的总通信成本。
81.图5示出了根据本公开一些实施例的接口设备316(例如，mof)的示意性框图。除了下面示出和描述的元件或组件，设备316还可以包括其它元件或组件。设备316可以耦合到如图2a所示的计算系统200中的设备211～n，并且在本公开中可以被称为第三设备。
82.设备316耦合到设备211，可选的，耦合到设备211上的访问引擎(axe)。在图5所示的示例中，设备316包括：打包器(assembler)502，用于打包并按路线发送数据包以便于在计算系统200中的设备之间进行数据传输；分解器(dissembler)504，用于对数据包进行解包并仲裁数据传输；以及调度器506。设备316还包括模块508以执行其它功能，例如流量控制和错误检测，并且与设备212～n相连接。
83.在一些实施例中，设备316还包括预取器和预取缓冲器510。预取器可以对与中心节点相邻的节点的属性和节点结构信息(例如，节点标识符)进行预取，并将这些属性存储在预取缓冲器510中。在上述示例(例如，图4所示的示例)中，当第二设备432上的中心节点425由第一设备211采样时，与该中心节点相邻的节点(例如，节点423)也可以由第一设备211采样。在这种情况下，在一些实施例中，响应于对第二设备212上的中心节点425进行的采样，与该中心节点相邻的一个或多个节点的属性被预取到设备316上的预取缓冲器510中，并且设备211随后可以访问和读取预取缓冲器510，以获取上述一个或多个节点的属性。
84.更具体地，结合图3和图4，在一些实施例中，例如，当中心节点415或中心节点425被设备211采样时，设备211的邻居获取模块332将向设备316发送请求，以获取记录在第二设备212上并且与中心节点425相邻或邻近的节点(例如，节点423)的节点标识符。响应于来自样本获取模块334的请求，对节点(具有由设备211的邻居获取模块332标识的节点标识符，例如，节点423)进行采样，并将这些节点的属性存储在设备316上的预取缓冲器510中。如果某节点被采样，则预取缓冲器510中存储的该节点的属性由设备316发送到第一设备211。也就是说，在一些实施例中，对该节点的属性的预取操作响应于来自设备211的属性获取模块336的请求。
85.进一步地，可以使用其他更积极的预取方案，其中，可以从与根节点间隔多于单跳或双跳的节点中预取属性。
86.通过使用设备316进行预取，与互连设备之间的信息传输相关的等待时间进一步减少，从而进一步减少了计算系统的总通信成本。
87.在一些实施例中，设备316还包括流量监测器516。例如，流量监测器516对设备316中的流量(例如，消耗的带宽)进行监测，例如，当流量低(例如，低于阈值)时，节点属性被预取到设备316上的预取缓冲器510中。因此，除了减少通信开销之外，计算系统的资源还可以被更有效地利用。
88.根据本公开的实施例显著地减少了最坏情况/长尾延迟。相比于中心节点未存储在设备211～n上的基准方案，本公开实施例的仿真结果表明：如上所述，将所有设备211～n
的中心节点存储于每个设备中，可以减少47.6％的延迟；再将这一改进与设备211～n上的预取缓冲器和预取方案相结合，可以减少49.5％的延迟；将上述改进与设备316上的预取缓冲器和预取方案相结合，可以减少74.8％的延迟。
89.图6示出了根据本公开一些实施例的一种由计算机实现的方法的流程示意图600。流程示意图600中的框所表示的全部或一些操作可以被实现为驻留在某种形式的非暂时性计算机可读存储介质上的计算机可执行指令，并且可以由诸如图2a所示的计算系统200之类的计算系统执行。在下面的讨论的一个示例中，图在逻辑上被划分为：由第一设备存储和计算的第一子图，以及由第二设备存储和计算的第二子图；此方案可以容易地扩展到两个以上的子图和设备。
90.在图6所示的框602中，结合参考图4，图100中的中心节点415和425被访问。该图在逻辑上被划分为包括多个中心节点的多个子图，并且这多个中心节点用于连接这些子图，如本文先前所述。
91.在框604中，将与第一子图102的中心节点(例如，节点415)相关的属性和节点结构信息(例如，节点标识符)存储在第二设备212中，该第二设备212还用于存储第二子图106的信息；并且，将与第二子图的中心节点(例如，节点425)相关联的属性和节点结构信息(例如，节点标识符)存储在第一设备211中，该第一设备211还用于存储第一子图的信息。属性包括一个或多个节点特征或性质及其各自的值，并且如上所述，节点结构信息包括节点标识符和其他结构信息。
92.在框606中，预取节点属性。预取方案的示例在上文和下文中均进行了描述。然而，根据本公开的实施例不限于那些示例。
93.在一些实施例中，结合参考图3，确定或获取与根节点(该根节点是与中心节点相邻的根节点，例如，与中心节点415相邻的节点413)相邻的节点的节点标识符，这些节点的至少一个子集被采样，并且被采样的子集中的节点的属性被预取到第一设备211的预取缓冲器323中。
94.在一些实施例中，当第一子图的中心节点与第一子图的根节点(例如，节点413)的间隔为单跳(例如，经由边414)时，与第一子图102的中心节点(例如，节点415)相关的属性被预取到第一设备211的预取缓冲器323中。
95.在一些实施例中，当第一子图102的中心节点(例如，节点415)被采样、第一子图102与第一子图的根节点(例如，节点413)的间隔为单跳，且第一子图的中心节点与第二子图的中心节点的间隔为单跳(例如通过边405)时，与第二子图106的中心节点(例如，节点425)相关的属性被预取到第一设备211的预取缓冲器323中。
96.在一些实施例中，结合参考图5，与节点(例如，内部节点或非中心节点)相关联的属性和节点结构信息(例如，节点id)被预取到第三设备316(例如，mof)的预取缓冲器510中，第三设备316与第一设备211和第二设备212通信(耦合)。更具体地，在这些实施例中，响应于来自第一设备的请求：第二设备上的、与第二中心节点425相邻的节点的节点标识符被确定或被获取；对这些节点的至少一个子集进行采样；被采样的节点的属性被预取到第三设备316的缓冲器510中。在一些实施例中，设备316还用于监测流量，在这种情况下，如果流量的测量值满足阈值，则设备316执行预取。
97.虽然前述公开使用特定框图、流程图和示例阐述了各种实施例，但本文中描述和/
或图示的每个框图组件、流程图步骤、操作和/或组件可以使用宽范围的配置被单独地和/或集体地实现。此外，任何包含在其他组件内的组件的公开都应该被认为是示例，因为相同的功能可以通过许多其他架构来实现。
98.尽管已经以结构特征和/或方法动作的特定的语言描述了主题，但是应当理解，本公开中定义的主题不一定限于上述特定的特征或动作。相反，上面描述的特定的特征和动作是以实现本公开的示例的形式被公开的。
99.根据本发明的实施例是这样被描述的。虽然本发明已在特定实施例中被描述，但本发明不应被解释为受这些实施例的限制，而应该根据所附的权利要求来解释。

技术特征：

1.一种由计算机实现的方法，其中，包括：访问图中的多个中心节点，所述图包括多个节点且在逻辑上被划分为多个子图，所述子图包括至少一个所述中心节点，且所述子图中的每个所述中心节点将该子图分别连接至所述多个子图中的另一个所述子图；在第二设备中存储与所述多个子图中的第一子图的中心节点相关联的属性和节点结构信息，其中所述第二设备还用于存储所述多个子图中的第二子图的信息；以及在第一设备中存储与所述第二子图的中心节点相关联的属性和节点结构信息，其中所述第一设备还用于存储所述第一子图的信息。2.根据权利要求1所述的方法，其中，还包括：当所述第一子图的中心节点与所述第一子图的根节点的间隔为单跳时，将与所述第一子图的中心节点相关联的属性和节点结构信息预取到所述第一设备的预取缓冲器中。3.根据权利要求1所述的方法，其中，还包括：当所述第一子图的中心节点被采样、所述第一子图的中心节点与所述第一子图的根节点的间隔为单跳，且所述第一子图的中心节点与所述第二子图的中心节点的间隔为单跳时，将与所述第二子图的中心节点相关联的属性和节点结构信息预取到所述第一设备的预取缓冲器中。4.一种系统，其中，包括：处理器；连接至所述处理器的存储单元；以及连接至所述存储单元的多个互连设备，所述多个互连设备包括第一设备和第二设备，所述第一设备包括存储器和至少一个缓冲器，所述第二设备包括存储器和至少一个缓冲器；其中，所述第一设备用于对图的第一子图的节点的信息进行存储，所述第二设备用于对所述图的第二子图的节点的信息进行存储，所述图包括多个子图，所述第一子图的节点包括第一中心节点，所述第二子图的节点包括第二中心节点，所述第一中心节点和所述第二中心节点通过边相互连接，所述第一设备对与所述第二中心节点相关联的属性和节点结构信息进行存储，且所述第二设备对与所述第一中心节点相关联的属性和节点结构信息进行存储。5.根据权利要求4所述的系统，其中，所述第一设备包括访问引擎，所述访问引擎被配置为：对与所述第一中心节点相邻的根节点所相邻的多个节点的节点标识符进行预取，对与这些节点标识符相对应的节点的至少一个子集进行采样，并获取所述子集中的节点的属性。6.根据权利要求4所述的系统，其中，与所述第一中心节点相关联的属性和节点结构信息以及与所述第二中心节点相关联的属性和节点结构信息包括以下属性和节点结构信息中的一个或多个：相应的属性值；相应的节点标识符；以及相应的节点结构。7.根据权利要求4所述的系统，其中，当所述第一中心节点与所述第一子图的根节点的间隔为单跳时，与所述第一中心节点相关联的属性和节点结构信息被预取到所述第一设备的预取缓冲器中。8.根据权利要求4所述的系统，其中，当所述第一中心节点与根节点分隔并被采样，且所述第一中心节点与所述第二中心节点的间隔为单跳时，与所述第二中心节点相关联的属
性和节点结构信息被预取到所述第一设备的预取缓冲器中。9.根据权利要求4所述的系统，其中，还包括：连接至所述第一设备和所述第二设备的第三设备，所述第三设备包括预取缓冲器，并且所述第三设备将与所述多个节点中的一个节点相关联的属性和节点结构信息预取到预取缓冲器中。10.根据权利要求9所述的系统，其中，所述第三设备还包括流量监测器，其中，当所述流量监测器所测量的流量满足阈值时，所述第三设备将与所述节点相关联的属性和节点结构信息预取到所述预取缓冲器中。11.根据权利要求9所述的系统，其中，所述第三设备被配置为：响应于来自所述第一设备的请求，获取所述第二设备上与所述第二中心节点相邻的多个节点的节点标识符，对与这些节点标识符相对应的节点的至少一个子集进行采样，并将所述子集中的节点的属性提取到所述第三设备的预取缓冲器中。12.一种非暂时性计算机可读存储介质，其中，包括存储在其中的计算机可执行指令，所述计算机可执行指令包括：第一指令，用于对图进行访问，所述图包括多个子图，所述多个子图包括第一子图和第二子图，所述第一子图包括具有第一中心节点的第一节点集合，所述第二子图包括具有第二中心节点的第二节点集合，并且所述第一子图和所述第二子图由连接所述第一中心节点和所述第二中心节点的边相连接；第二指令，用于在第一设备中存储与第二中心节点相关联的属性和节点结构信息，所述第一设备还存储与所述第一子图相关的信息；以及第三指令，用于在第二设备中存储与第一中心节点相关联的属性和节点结构信息，所述第二设备还存储与所述第二子图相关的信息。

技术总结

本公开涉及由计算机实现的方法、系统及存储介质，其中，存储在计算系统中的图在逻辑上分为子图，子图存储在计算系统中的不同互连设备上，子图的节点包括连接相邻子图的中心节点。每个设备在其他设备上存储子图的中心节点的属性和节点结构信息，设备上的软件或硬件预取引擎预取与采样节点相关的属性和节点结构信息。与互连设备对接的设备上的预取器还可以预取其他设备上子图的节点的属性和节点结构信息，接口设备上设置有流量监测器以监测流量，当流量较小时，接口设备预取节点属性和节点结构信息。点结构信息。点结构信息。