背景技术
数据可以通过多个表存储在关系数据库中。表格根据数据库模式(诸如星形模式)彼此引用。可以提交查询——诸如SQL查询——以针对表格进行处理，以便返回所请求的数据。该处理可涉及任何数量的操作，其可实现关系代数，其示例包括连接(join)、分组(group by)、排序(order by)等。在许多系统中，处理查询时的性能瓶颈在于执行关系的联合。一个这样的示例是在在线分析处理(OLAP)中，其允许用户从多个视角交互地分析多维数据。已经发现，在使用图形处理单元(GPU)的系统中，可以显著加速大关系的联合。
在基于散列的联合算法中，GPU可以使用构建表(其还可以被称为“维度表”)来在构建阶段中创建散列表，然后在探测阶段中用来自探测表(其也可以被称为“事实表”并且通常大于构建表)的条目来探测散列表。构建阶段可涉及从构建表读取行，对其连接键(join key)上的行进行散列以计算散列值，以及将其有效载荷(以及可选地其键或指向键的指针)插入到散列表中对应于散列值的位置处。在探测阶段期间，GPU可从探测表读取行，对其连接键上的行进行散列以计算散列值，且使用所述行的散列值来探测散列表中的匹配行。然而，虽然使用GPU可加速此过程，但由于单个GPU的速度或存储器容量，单个GPU可能不总是足以足够快地或根本不足以连接输入表。例如，单个GPU可能不具有足够的存储器来存储用于连接的散列表，或可能由于用于建立和/或探测散列表的随机存储器访问的数目而比所想要的更慢地执行连接。
发明内容
本公开的实施例提供了使用多个GPU对散列表的有效且可扩展的构建和探测。具体地，本公开提供了用于有效地和可扩展地使用多个GPU来构建散列表、探测散列表和物化(materialize)探测散列表的结果的方法，其可以用于实现多GPU连接。
虽然常规方法提供用于使用单个GPU来实现表的连接，但本公开描述了用于利用多个GPU来实现表的连接的解决方案。描述了用于建立散列表、探测散列表和物化探测的结果的不同方法，这些方法中的一些可以结合其他方法或与其他方法一起使用。所公开的方法可在处理连接操作中利用多个GPU的存储器，以增加系统可用的有效存储器容量。所公开的方法还可在处理连接操作时利用并行执行的多个GPU的处理能力，以相对于常规方法减少连接的运行时间。
在不同示例中，可以使用全局位置标识符(ID)在多个GPU上并行地执行构建和/或探测散列表所需的随机存储器访问。全局位置ID可从条目的数据(从条目的一个或更多个键)计算并且标识与条目相关联的全局位置(例如，在散列表中)。在构建散列表时，可向每个GPU分配散列表的一个或更多个部分(例如，分区)，且GPU可从构建表中的条目计算全局位置ID，以针对一条目确定是否使用所述条目执行插入和/或要在何处执行插入。在探测散列表时，GPU可从探测表中的条目计算全局位置ID，以针对条目确定是否使用条目执行探测和/或要在何处执行探测。
本公开进一步描述用于在物化散列连接操作的探测阶段中的结果时协调GPU的方法，这可允许对全局输出缓冲区的并行写入。在一些方法中，在GPU中的每个GPU可访问的存储器中维持到全局输出缓冲区的全局偏移，以指示每个GPU应将结果的一部分写入何处。当GPU用于写入结果的一部分(例如，直接地，没有本地缓存)时，可递增全局偏移以考虑全局偏移缓冲区中的结果的该部分的大小。在其他方法中，GPU可将结果的部分写入到本地或初始输出缓冲区。为了将结果的部分物化到全局输出缓冲区，GPU可以计算本地或初始输出缓冲区大小的排斥和(exclusive sum)。排斥和可向每个本地或初始输出缓冲区提供到全局输出缓冲区的全局偏移，以指示应将来自本地或初始输出缓冲区的结果的部分写入到全局输出缓冲区中的何处。
附图说明
1.以下参照所附附图详细描述用于使用多个GPU对散列表有效且可扩展地构建和探测的本系统和方法，其中：
2.图1是根据本公开的一些实施例的多GPU分布式处理系统的示例系统图；
3.图2是示出了根据本公开的一些实施例的使用多个GPU的散列表的分布式构建的示例的示图；
4.图3是示出了根据本公开的一些实施例的将散列表复制到多个GPU的示例的示图；
5.图4是示出了根据本公开的一些实施例的使用多个GPU和固定散列表分区对散列表进行分布式探测的示例的示图；
6.图5是示出了根据本公开的一些实施例的使用多个GPU和固定探测表部分来对散列表进行分布式探测的示例的示图；
7.图6是示出了根据本公开的一些实施例的使用多个GPU和全局偏移变量对散列表的分布式探测的结果进行物化的示例的示图；
8.图7是示出了根据本公开的一些实施例的使用多个GPU和本地输出缓冲区的大小来物化散列表的分布式探测的结果的示例的示图；
9.图8是示出了根据本公开的一些实施例的用于使用多个GPU分布式构建散列表的方法的流程图，其中构建表条目与本地散列表分区相关联；
10.图9是示出了根据本公开的一些实施例的用于使用多个分布式构建散列表的方法的流程图，其中构建表条目与远程散列表分区相关联；
11.图10是示出了根据本公开的一些实施例的用于使用多个GPU对散列表进行分布式探测的方法的流程图，其中探测表条目与本地散列表分区相关联；
12.图11是示出了根据本公开的一些实施例的用于使用多个GPU对散列表进行分布式探测的方法的流程图，其中探测表条目与远程散列表分区相关联；
13.图12是示出了根据本公开的一些实施例的用于使用多个GPU和全局偏移变量对散列表的分布式探测的结果进行物化的方法的流程图；
14.图13是示出了根据本公开的一些实施例的用于使用多个GPU和本地偏移缓冲区的大小来物化散列表的分布式探测的结果的方法的流程图；以及
15.图14是适合用于实现本公开一些实施例的示例计算设备的框图。
具体实施方式
本公开提供了使用多个GPU对散列表的有效且可扩展的构建和探测。在各个方面，本公开提供了用于使用多个GPU来有效地和可扩展地构建散列表、探测散列表和物化探测散列表的结果的方法，其可以用于实现多GPU连接或涉及散列表的构建和/或探测的其他操作。
在不同示例中，可以使用全局位置标识符(ID)在多个GPU上并行地执行构建和/或探测散列表所需的随机存储器访问。全局位置ID可从条目的数据(从条目的一个或更多个键)计算且识别与条目相关联的全局位置(例如，在散列表中和/或在特定GPU处)。例如，散列值可从每个条目的键计算，且用于导出条目的全局位置ID。全局位置ID的示例包括散列表的全局散列值索引、散列表的全局桶ID、GPU ID和/或散列表分区ID。在构建散列表时，可向每个GPU分配散列表的一个或更多个部分(例如，分区)，且GPU可从构建表中的条目计算全局位置ID，以针对一条目确定是否使用条目执行插入和/或要在何处执行插入。
在一些方法中——为了使用多个GPU以分布式方式构建散列表——每个GPU可以被指派或分配散列表的分区，并且用于操作的构建表可以跨GPU分布(例如，每个GPU具有一个或更多个构建表分区)。每个散列表分区可覆盖散列表中的地址(连续值)的不同范围(使用开放寻址的值的一个或更多个桶的集合)。每个GPU可从GPU的构建表部分的条目读取数据且从每个条目的数据确定该条目的全局位置ID。如果GPU使用全局位置ID确定用于插入的对应位置在GPU的散列表分区内，那么GPU可将有效载荷(和键或条目索引)插入其中。否则，有效载荷可以不被插入到GPU的散列表分区中，而是可以被插入在与用于插入的位置相关联的GPU处。由此，用于将条目插入到散列表中的对GPU存储器的随机存储器访问的次数可跨GPU分布且并行化。
在GPU处理GPU的构建表部分中的至少一些(例如，完整分区)之后，GPU可将表示构建表的经处理部分的至少一个未插入条目的构建表数据传递到另一GPU。构建表数据的处理和传递可继续，直到完全构建散列表。双缓存可用于重叠构建表数据的处理和传递。针对每个条目，在GPU之间交换的经处理的构建表数据可以包括足以执行条目的插入的数据，如有效载荷和相应的键和/或散列值。在GPU最初包括多个构建表部分的示例中，当GPU从另一GPU接收构建表数据时，其可连同初始构建表部分一起处理所接收的构建表数据。
在一些示例中，使用交换或路由算法(诸如环形交换)来传递经处理的构建表数据。在环交换中，GPU可在逻辑上布置成环，使得每个GPU具有左邻居和右邻居。当将构建表数据传递到另一GPU时，每个GPU可在相同方向上将构建表数据传递到邻居，而不管该邻居是否对应于用于插入由构建表数据捕获的条目的位置。在多对多GPU通信不可用或不合需要的情况下，可使用此方法。
在其他示例中(例如，作为环形交换的替代方案)，GPU可基于确定(使用全局位置ID)另一GPU对应于用于将条目插入到散列表中的位置而将条目的构建表数据直接提供到特定GPU。在一些示例中，其他GPU可使用所接收的构建表数据来在本地执行该插入。在其他示例中，GPU可使用构建表数据来将条目远程插入到其他GPU的散列表分区中，例如通过使用到对等GPU的系统范围的原子操作。
本公开还部分地提供了用于散列表的分布式探测的方法。在复制的散列表方法中，每个GPU具有可用于并行化探测阶段的操作的散列表的本地副本。复制的散列表方法可使用构建阶段来形成散列表的跨GPU分布的分区，这些分区随后被合并以形成本地副本。在经分区的散列表方法中，每个GPU具有散列表的用以并行化探测阶段的操作的相应分区，因此可不需要散列表分区的合并。
当探测表的大小与构建表相比变得更大时，复制的散列表方法可能更期望用于连接操作中。例如，虽然由于跨GPU合并散列表分区以创建本地副本，复制散列表方法的构建阶段可能比经分区的散列表方法花费更长时间，但探测阶段可能更快，因为每个GPU可在本地探测散列表的任何部分，从而减少GPU间业务。经分区的散列表方法可用以减少用于存储散列表的存储器要求，因为每个GPU不需要存储完整散列表的本地副本。还可以根据本公开使用混合方法——其中一个或更多个GPU包括完整副本并且一个或更多个其他GPU包括一个或更多个散列表分区。
对于使用经分区的散列表方法的分布式探测，可向每个GPU提供探测表的一部分，且GPU可使用来自本地探测表部分的条目来探测散列表分区。在探测散列表时，GPU可从探测表中的条目计算全局位置ID以针对条目确定是否使用条目执行探测和/或要在何处执行探测(例如，类似于构建阶段)。由此，针对使用条目的对散列表的探测，对GPU存储器的随机存储器访问的次数可跨GPU分布且并行化。
在GPU处理GPU的探测表部分中的至少一些(例如，完整分区)之后，其可将表示探测表的经处理部分的至少一个未经探测条目的探测表数据传递到另一GPU。探测表数据的处理和传递可继续，直到已针对所有探测表条目探测了散列表为止，这可在探测表分区已访问所有GPU和/或不存在剩余条目要探测时。双缓存可用于重叠探测表数据的处理和传递。针对每个条目，在GPU之间交换的经处理的探测表数据可以包括足以针对该条目执行探测散列表的数据，诸如一个或更多个相应的键、有效载荷和/或散列值。
在一些示例中，使用交换或路由算法(诸如环形交换)来传递经处理的探测表数据。在其他示例中(例如，作为环形交换的替代方案)，GPU可基于确定(使用全局位置ID)另一GPU对应于针对条目探测散列表的位置而将该条目的探测表数据直接提供到特定GPU。在一些示例中，该另一GPU可使用所接收的探测表数据来在本地执行该探测。在其他示例中，GPU可使用探测表数据来远程探测另一GPU的散列表分区。
在其他示例中，除了或替代GPU将探测表数据提供给另一GPU，GPU可提供对应于散列表分区或部分的散列表数据。例如，GPU可交换用于探测的散列表数据，且每个GPU可使用相同的本地探测表部分进行探测，直到探测表被完全处理(例如，用于散列表分区的每个散列表数据已访问每个GPU和/或已针对每个探测表条目产生结果)。
在进一步方面，探测表可被重新布置以基于条目的散列表索引来形成提供给GPU的探测表部分。例如，探测表可被布置以使得每个GPU从探测表接收对应于用于使用那些条目进行探测的位置的条目。例如，探测表部分可被配置以使得每个探测表部分的条目包括散列到对应GPU上的散列表分区的范围中的键。在一些示例中，可使用对应的全局位置ID将条目指派给探测表部分。
本公开进一步描述了用于在物化探测散列表的结果时协调GPU的方法，该方法可以允许对全局输出缓冲区的并行写入。在一些方法中，在GPU中的每个GPU可访问的存储器中维持到全局输出缓冲区的全局偏移，以指示每个GPU应将结果的一部分写入何处。当GPU要写入结果的一部分(例如，直接地，不具有本地缓存)时，可递增全局偏移以考虑全局偏移缓冲区中的结果的部分的大小(可能使用原子存储器操作)。在其他方法中，GPU可将结果的部分写入到本地或初始输出缓冲区。为了将结果的部分物化到全局输出缓冲区，GPU可以计算本地或初始输出缓冲区大小的排斥和。排斥和可为每个本地或初始输出缓冲区提供到全局输出缓冲区的全局偏移，以指示应将来自本地或初始输出缓冲区的结果的部分写入到全局输出缓冲区中的何处。
参见图1，图1是根据本公开的一些实施例的多GPU分布式处理系统100的示例系统图。应当理解，本文这种和其他布置仅作为示例被阐述。除了所示的那些布置和元素之外或代替所示的那些布置和元素，可以使用其他布置和元素(例如，机器、接口、功能、顺序、功能分组等)，并且一些元素可以一起省略。进一步，本文描述的许多元件是可被实现为分立或分布式组件或结合其他组件、并在任何合适的组合和位置中实现的功能实体。本文中描述为由实体执行的不同功能可由硬件、固件和/或软件执行。例如，不同功能可由执行存储在存储器中的指令的处理器执行。作为示例，多GPU分布式处理系统100可以在图14的计算设备1400的一个或更多个实例上实现。
多GPU分布式处理系统100(也被称为“系统100”)可以包括，多个GPU(例如，两个或更多个)，诸如GPU 102A和GPU 102B，至GPU 102N(也被称为“GPU 102A-102N”)，一个或更多个CPU，诸如CPU 104，和一个或更多个数据存储，诸如一个或更多个数据存储106。
虽然在GPU 102A中示出，但是GPU 102A-102N中的每一个可以包括例如接口管理器110、散列表构建器112、散列表探测器114、结果管理器116、位置确定器118、数据过滤器120和GPU存储器122的单独实例。
系统100可被配置为对来自存储在数据库106中的表的数据执行任何数量的操作——诸如涉及构建表140、探测表142和散列表144的操作138——以产生一个或更多个结果146。在一些实施例中，操作138可以由查询引擎130执行，作为执行查询的一部分。查询引擎130包括查询接口132和操作处理器134。查询接口132和/或操作处理器134的功能可以使用一个或更多个计算设备来实现，诸如GPU 102A-102N、一个或更多个CPU 104和/或其他设备。
作为概述，查询接口132可以被配置为从用户和/或软件接收查询，并且操作处理器134可以被配置为执行查询。处理查询可涉及执行任何数量的操作，其可实现关系代数，关系代数的示例包括连接、分组、排序等。操作138是操作的一个这样的示例，其可以是连接操作。GPU 102A到102N可用于操作138的一个或更多个部分的多GPU分布式处理。例如，GPU102A-102N的分布式处理可用于从构建表140构建散列表144，使用探测表142探测散列表144，物化操作138的结果146，和/或提供其他分布式处理和存储能力。
提供了GPU 102A的组件的概述，其对于GPU 102A-102N中的每一个可以是类似的。接口管理器110被配置为管理GPU 102A对数据的接收以及来自GPU 102A的数据的发送。散列表构建器112被配置成实现用于使用构建表140来构建散列表(诸如散列表144)的功能，这可涉及使用构建表条目来插入到散列表中。散列表探测器114被配置为实现用于使用探测表142探测散列表(例如，散列表144)的功能，其可涉及使用探测表条目探测散列表。结果管理器116被配置为实现用于物化操作的结果(诸如操作138的结果146)的功能。位置确定器118被配置为确定位置(例如，使用全局位置ID)以促进散列表构建器112、散列表探测器114、结果管理器116和/或GPU 102A的其他部件中的一个或更多个的功能。该位置可对应于散列表144的分区和/或桶以用于在其中插入条目或在其中探测条目，和/或包括散列表144的分区和/或桶的GPU。
数据存储106可包括计算机可读介质，并且可被配置为存储查询引擎130可针对其执行查询的数据(例如，关系表的数据)。尽管被描绘为单个组件，但数据库106可被体现为一个或更多个数据存储，并且可在云中和/或以任何合适的方式跨一个或更多个数据存储分布以供存储。作为不同示例，一个或更多个数据存储可以托管在系统100的其他组件的外部和/或至少部分地托管在系统100的一个或更多个其他组件内，诸如GPU 102A-102N、CPU104和/或主机计算系统或其设备。
在不同示例中，数据库106中的至少一些数据可存储在多个表上。表根据数据库模式(诸如星形模式)彼此引用。例如，数据可被存储在数据存储106的一个或更多个关系数据库中。为了确定和从数据库106检索信息，系统100可使用任何数量的操作(诸如操作138)来处理数据，这些操作可实现关系代数，其示例包括连接、分组、排序等。
在一些实施例中，查询引擎130用于根据诸如在线分析处理(OLAP)之类的方法来实现操作，其允许用户或软件通过向查询接口132提交查询来从多个角度交互式地分析多维数据。然而，查询引擎130可以用于实现涉及针对数据执行操作(诸如连接操作)的任何合适的数据处理技术。例如，查询——诸如SQL查询——可以被提交至查询引擎130的查询接口132，用于对数据进行处理以便返回所请求的数据。
操作138可以是由查询定义的操作，例如对应于关系的连接。就这一点而言，结果146可以指操作(例如，连接操作)的输出集合，其可以是查询的输出集合或者用于产生查询的输出集合的中间集合。然而，操作138和/或其一个或更多个部分(诸如构建散列表144、探测散列表144或物化探测散列表144的结果)可在查询执行的上下文之外实践(例如，使用操作处理器134)。换言之，本公开的各方面不必限于特定操作和/或系统。此外，操作138的这些不同部分可以在任何合适的时间和由不同的系统执行(例如，系统100不需要执行操作138的所有这些部分)。同样在一些示例中，可建立散列表144且可在多个不同操作中探测散列表144，例如针对每个操作使用不同的探测表。
构建表140可指从其创建散列表144的关系。这可以是例如来自数据存储106中的数据的给定表的一个或更多个列。构建表140也可被称为维度表。探测表142可指针对从构建表140创建的散列表144探测的关系。这可以是例如来自给定表的一个或更多个列。探测表142也可以被称为事实表，并且通常大于构建表140。散列表144可对应于从构建表创建的数据结构，且可用于GPU 102A-102N的快速随机访问，以加速操作138。散列表144可对应于用以计算到对应值的桶或槽阵列中的散列索引的散列函数。散列索引也可称为散列值。由于散列函数中的缺陷，在散列函数为多于一个条目生成相同散列索引的情况下可能发生冲突。在不同实施例中，可使用寻址模式(诸如开放寻址)来实现散列表144。在任何示例中，可以使用具有线性探测的开放寻址来解决冲突。开放寻址可以提供一种用于处理冲突的方法。在开放寻址中，所有元素可存储在散列表本身中。可通过探测或搜索阵列(探测序列)中的替代位置直到找到目标条目或找到未使用的阵列条目槽，来解决散列冲突，其可指示散列表中不存在此键。在线性探测中，探测之间的间隔可以是固定的。
构建表140、探测表142和/或散列表144的一个或更多个部分可存储在CPU 104的CPU存储器124、GPU 102A-102N的GPU存储器122和/或其他存储位置中和/或跨CPU 104的CPU存储器124、GPU 102A-102N的GPU存储器122和/或其他存储位置分布。对于不同的实施例，数据的分布和位置可以变化。CPU 104的CPU存储器124、GPU 102A-102N的GPU存储器122和/或其他存储装置可包括随机存取存储器(RAM)。例如，CPU存储器124可指代附接到CPU104的RAM，其也可称为系统存储器。进一步，GPU存储器122可指代附接到GPU的RAM，其也可被称作设备存储器。在不同示例中，一个或更多个CPU 104中的每一个可以对应于图14的计算设备1400中的一个或更多个。进一步，每个计算设备1400可以托管GPU 102A-102N中的一个或更多个。例如，一个或更多个CPU 104可对应于CPU 1406，并且GPU 102A-102N中的一个或更多个可对应于GPU 1408。
当使用基于散列的连接算法执行操作138时，系统100可在构建阶段中使用构建表140来创建散列表144，随后在探测阶段中用来自探测表142的条目(例如，行)来探测散列表144。构建阶段可涉及系统100从构建表140读取条目150(例如，行)，对其键152(例如，连接键)上的条目进行散列以计算散列值，以及在位置(例如，行)处将其有效载荷154插入到散列表144的条目156中，具有对应于该散列值的散列索引。除了有效载荷154之外，键152或用于定位键152的指针也可被插入到散列表144的条目156中。在探测阶段期间，系统100可以从探测表142读取条目160，对其键152(例如，连接键)上的条目160进行散列以计算散列值，以及使用条目160的散列值来探测散列表144中的匹配条目156，其用于提供结果146的条目162。条目162可包括构建表140的条目150的条目ID 164和探测表142的条目160的匹配条目ID 166。由于不同的键可散列到相同的散列值，所以匹配可检查由散列表144中的条目156识别的一个或更多个键与探测表条目的键匹配。系统100可以使用GPU 102A-102N来处理操作138的一个或更多个部分，与使用一个GPU相比，这可以增加系统100可用的速度和/或存储器容量。
本公开部分地提供用于使用GPU 102A-102N以分布式方式构建散列表144的方法。现在参见图2，图2是示出了根据本公开的一些实施例的使用GPU 102A-102N分布式构建散列表144的示例的示图。然而，本公开考虑用于以分布式方式构建散列表144的许多潜在变化。进一步，这些变体中的许多变体可以用于构建用于分布式探测的分区散列表或用于分布式探测的复制散列表。例如，为了形成复制的散列表，经分区的散列表可跨GPU 102A-102N合并。图3用于描述合并散列表分区的示例。
操作处理器134可为GPU 102A-102N中的每一个指派或分配用于操作138的散列表144和构建表140的相应部分(例如，一个或更多个分区)。例如，可向GPU 102A指派散列表分区244A和构建表部分240A，可向GPU 102B指派散列表分区244B和构建表部分240B，且可向GPU 102N指派散列表分区244N和构建表部分240N。
本文中的分区可指代表示较大数据结构的一部分的连续分配。每个散列表分区244A-244N可覆盖散列表中的值(例如，连续值)的一个或更多个桶的不同集合(例如，使用开放寻址)。数据结构的进一步分区大小可以基本上等效(例如，在可被GPU和/或分区的数目整除时相等)。另外，在各个实施例中，每个分配可以不重叠。例如，散列表144可分区为实质上相等大小的N个分区，其中每个GPU 102A-102N被分配各自的分区，且N还可表示GPU的数目。假设本地分区大小为A，散列表分区244A可具有范围从0至A-1的全局散列表索引，假设本地分区大小为B，散列表分区244B可具有范围从A至B-1的全局散列表索引等等。构建表140和探测表142的分区可被类似地布置。
散列表144和/或构建表140的所分配部分可跨GPU 102A-102N分布和/或可在GPU102A-102N中的对应GPU可访问的存储器中。例如，散列表144的部分被分配给该GPU的GPU存储器122中的特定GPU。示例包括在GPU 102A的GPU存储器122中分配的GPU 102A的散列表分区244A。构建表140的部分可被类似地布置，或可在一个或更多个CPU 104的CPU存储器124中，诸如包括存储构建表的指派部分的对应GPU的主机系统的CPU 104。在任何示例中，构建表140的部分可存储在GPU存储器122中或可在由所有GPU 102A-102N或其子集可访问的CPU存储器124中。
一般来说，散列表144和构建表140的部分的存储位置可基于系统100的组件、能力和配置而变化。例如，在一些实施例中，GPU 102A-102N中的不止一个可能能够从相同的CPU存储器124和/或相同的GPU存储器122直接读取和写入到相同的CPU存储器124和/或相同的GPU存储器122，在这种情况下，每个GPU的散列表144和/或构建表140的部分可在相同的存储器中。然而，即使不支持直接读取和写入，GPU仍可以共享存储器位置，在这种情况下，可以使用大容量存储器副本，尽管潜在地效率较低。
在一些示例中，GPU 102A-102N可以在多次迭代中构建散列表144。例如，图2示出了使用GPU 102A-102N以分布式方式构建散列表144的迭代200A和迭代200B。在迭代200A中，GPU 102A-102N中的每一个的散列表构建器112可(并行地)从GPU的构建表部分(例如，分区)的条目读取数据且使用GPU的位置确定器118来从该数据作出哪个GPU被指派用于每个条目的该散列表分区和/或该GPU是否包括用于该条目的该散列表分区的确定210。
例如，GPU 102A的散列表构建器112可从构建表部分240A读取条目，且GPU 102A的位置确定器118可针对每个条目作出哪个GPU包括用于插入条目的散列表分区和/或GPU102A是否包括该散列表分区的确定210。这可包括位置确定器118对条目的键进行散列以计算散列值，以及使用散列值来导出条目的全局位置ID。如本文中所描述的，全局位置ID的示例包括散列表144的全局散列值索引、散列表144的全局桶ID、散列表分区的分区ID和/或标识用于插入到散列表144中的对应位置的GPU ID。如果GPU的位置确定器118使用全局位置ID确定插入是针对GPU的散列表分区，那么GPU可在其中插入对应条目。否则，条目可不插入到GPU的散列表分区中，而是可在与插入相关联的GPU处插入。
作为非限制性示例，位置确定器118可使用等式(1)计算单个分区的分区大小P_Size：
P_Size＝Hashtbl_Size/K (1)
其中Hashtbl_Size是散列表144的大小(例如，桶的数量)，并且K是GPU 102A-102N的数量。位置确定器118还可使用等式(2)计算散列表索引Hash_Idx：
Hash_Idx＝Key_Hash％Hashtbl_Size (2)
其中Key_Hash是构建表140的条目的键的散列。
位置确定器118还可以使用等式(3)将指定GPU的GPU ID计算为D_GPU：
D_GPU＝Hash_Idx/P_Size (3)
每个GPU可以被分配范围从0至K-1的GPU ID，并且如果位置确定器118确定D_GPU等于GPU的GPU ID并且GPU的GPU ID小于K-1，则散列表构建器112可以在GPU处执行插入。进一步地，如果位置确定器118确定D_GPU大于或等于GPU的GPU ID并且GPU的GPU ID等于K-1，则散列表构建器112可以在GPU处执行插入。否则，插入可不在GPU处执行，使得其可在指定GPU处执行。应注意，等式和决策可基于分区和散列表144的配置而变化。在本示例中，全局位置ID可以指代或对应于Hash_Idx。本示例假设P_Size对于分区是恒定的。然而，在其他示例中，P_Size可针对不同分区而不同。
作为使用等式(1)、(2)和(3)的示例，假设K＝16并且Hashtbl_Size＝1024，使得使用等式(1)的P_Size＝64。接下来，假设Key_Hash＝793434，使得使用等式(2)的Hash_Idx＝858。由此，使用等式(3)，D_GPU＝13。如果当前GPU具有为10的GPU ID，那么GPU的散列表构建器112可不在GPU处执行插入。
通过使用全局位置标识符确定是否将条目插入到GPU的本地散列表分区中，用于构建散列表144的插入可有效地分布在GPU 102A-102N上且并行化，从而减少对应随机存储器访问对散列表144的总体构建时间的影响。
在进一步方面，基于GPU的散列表构建器112处理GPU的构建表部分的至少一部分(例如，完整的本地分区)，散列表构建器112可使用接口管理器110来向另一GPU提供构建表数据的对应部分以供进一步处理。构建表数据可对应于图2中的构建表部分242A-242N，并且可分别从构建表部分240A-240N生成或对应于构建表部分240A-240N。例如，GPU 110A的接口管理器110可将构建表部分242A(对应于构建表部分240A)提供到GPU 102B，GPU 110B的接口管理器110可以向GPU 102N提供构建表部分242B(对应于构建表部分240B)，并且GPU110N的接口管理器110可以向GPU 102A提供构建表部分242N(对应于构建表部分240N)。提供或传递数据到另一GPU的GPU可指代GPU推送数据和/或传输数据到另一GPU的存储器，和/或向GPU提供对GPU和/或CPU存储器中的数据的访问。例如，在GPU能够访问彼此的GPU存储器的情况下，不需要切换数据，因为数据可以由其他GPU远程访问。进一步，在一些示例中，此切换可由操作处理器134和/或交换算法执行，且GPU可为或可不为切换中的主动参与者。
构建表部分242A-242N可以包括例如代表来自相应的构建表部分240A-240N的一个或更多个条目的构建表数据。对于条目，这可包括有效载荷和对应的键、键的散列值、条目的指定GPU ID、条目的散列表索引和/或条目的全局位置ID。在一些实施例中，提供散列值、指定GPU ID、散列表索引和/或全局位置ID可通过允许不同GPU在不计算值的情况下使用那些值来减少处理。
在一些示例中，构建表部分242A-242N可从构建表部分240A-240N生成，其中每个GPU的数据过滤器120和/或操作处理器134可滤除GPU已插入到GPU散列表分区中的条目的条目数据。这可允许后续操作对较少的构建表条目进行操作和/或减少GPU间业务量。在一些示例中，包括未经滤除的条目的条目数据的构建表数据可不直接推送到下一GPU。例如，可首先在软件管理的本地分级缓冲区中收集构建表数据。这可导致GPU102A-102N之间的负载不平衡。在构建表140在CPU存储器124中的情况下，可通过将输入划分成更小的分区来解决此负载不平衡，该更小的分区以轮询(round robin)方式分布在GPU 102A-102N上。
迭代200B可以类似于迭代200A，但是使用构建表部分242A-242N代替构建表部分240A-240N。例如，在迭代200B中，GPU 102A-102N中的每一个的散列表构建器112可(并行地)从GPU的构建表部分(例如，分区)的条目读取数据且使用GPU的位置确定器118来从该数据作出哪个GPU被指派用于每个条目的该散列表分区和/或该GPU是否包括用于该条目的该散列表分区的确定210。
类似地，如果GPU的位置确定器118使用全局位置ID确定插入是针对GPU的散列表分区的，那么GPU可在其中插入对应条目。否则，条目可不插入到GPU的散列表分区中，而是可稍后在与插入相关联的GPU处插入。
同样类似于迭代200A，基于GPU的散列表构建器112处理GPU的构建表部分的至少一部分(例如，完整的本地分区)，散列表构建器112可使用接口管理器110来向另一GPU提供构建表数据的对应部分以供进一步处理。构建表数据可对应于图2中的构建表部分246A-246N，并且可分别从构建表部分242A-242N生成或对应于构建表部分242A-242N。
迭代200A和200B中所说明的构建表部分的处理和将构建表数据提供到不同GPU可继续，直到构建了散列表144为止。在任何示例中，在GPU 102A-102N之间交换的数据(例如，构建表数据)可存储在其一个或更多个缓冲区中并从其一个或更多个缓冲区处理。在一些示例中，GPU 102A-102N中的每一个包括用于双倍缓存数据的多个缓冲区。例如，在诸如迭代200A之类的每个迭代中，GPU 102A可处理来自活动缓冲区的例如表示构建表部分240A的构建表数据，且从GPU 102A的分级缓冲区中的另一GPU接收例如表示构建表部分242N的构建表数据。在下一和/或后续迭代(诸如迭代200B)中，缓冲区的角色可以切换。GPU 102A-102N中的每一个可执行类似于GPU 102A的缓存。使用缓存，GPU 102A-102N可以使数据处理与GPU 102A-102N之间的经处理数据的交换重叠。
在一些示例中，使用交换或路由算法(例如，环形交换)将构建表数据提供给另一GPU。在一些示例中，交换或路由算法被配置为使得每个GPU看到构建表140的所有元素。在其他示例中，交换或路由算法被配置为使得每个GPU至少看到GPU将插入到GPU的散列表分区中的构建表140的元素。
在环交换中，GPU 102A-102N可在逻辑上布置成环，使得每个GPU具有左邻居和右邻居。例如，在图2中，GPU 102A的左邻居可为GPU 102N，而GPU 102A的右邻居可为GPU102B。当每个GPU向另一GPU提供构建表数据时，GPU可以在相同方向上向邻居GPU提供数据，诸如图2中的右邻居。使用环形交换，构建表140可仅被读取一次(例如，经由比较窄的CPU-GPU互连)，并且随后其每个部分可在环中的GPU 102A-102N之间来回传递，直到来自构建表的每个值被插入到散列表144中。
构建散列表144中的瓶颈可由随机存储器访问引起，该随机存储器访问可由执行原子比较和交换操作引起，且通常具有比GPU间带宽显著低的吞吐量。使用本文描述的方法，此瓶颈的吞吐量可减少至少K倍(与使用单个GPU相比)，其中K是GPU 102A-102N的数目，其中每个GPU 102A-102N在构建表140上传递K次(最坏情况)以供插入。平均来说，在每个传递中，构建表140的仅1/K个条目可能需要比较和交换操作。
虽然GPU 102A-100N中的每个GPU被示出为包括单个构建表部分240A-240N，但是在GPU最初包括多个构建表部分(例如，分区)的示例中，当GPU从另一个GPU接收构建表数据时，其可以处理接收到的构建表数据以及初始构建表部分以供插入。例如，在迭代200A中，GPU 102A可以从构建表部分240A和至少一个其他构建表部分开始。然而，GPU 102A可能不处理迭代200A中的所有初始构建表部分，并且可能不在迭代200A中向不同GPU提供所有构建表部分。然后，在迭代200B中，GPU 102A可以处理构建表部分242N以及其他初始构建表部分中的一个或更多个。进一步注意的是，尽管图2将GPU 102A-102N中的每一个示出为具有单个散列表分区，但是GPU 102A-102N中的任何一个可以被分配任何数量的散列表分区。
作为前述内容的示例，操作处理器134可将构建表140分区成大于GPU 102A-102N的数量的多个分区。在迭代200B中，每个GPU 102A-102N可读取初始构建表分区和在迭代200A中从左邻居GPU接收的构建表分区。随后，已通过数据过滤器120进行的过滤且未落入当前GPU的散列表分区中的所有构建表条目可被推送到右邻居(例如，使用本地分级缓冲区)。在GPU间带宽高于访问构建表140的链路的带宽的情况下，此方法可为有益的，因为可在较大部分上平滑窄链路上的流量。
在一些实施例中，当GPU 102A-102N中的一个或更多个的位置确定器118确定(例如，使用确定210)用于插入条目的指定GPU并且GPU不是指定GPU时，该条目的条目数据(例如，有效载荷、散列值和/或键等)可由GPU基于该确定提供到指定GPU。例如，可将条目数据直接提供(例如，推送)到指定GPU(例如，到其分级缓冲区)，且指定GPU可执行将对应条目插入到散列表144的本地分区中。这可以在GPU102A-102N中的每一个管理K-1个分级缓冲区的情况下实现。作为另一示例，GPU可执行条目到指定GPU的散列表144的分区中的远程插入，例如在系统100支持用于对等GPU的原子操作的情况下。
在可能进行远程插入的实现方式中，构建表部分240A-240N可以不在GPU 102A-102N之间交换。例如，可以不需要迭代200B，并且可以在构建表140上的单次传递中构建散列表144。然而，在任何示例中，取决于不同潜在因素，远程插入可由GPU 102A-102N中的一些GPU而不是其他GPU来执行，和/或可针对构建表140中的条目而不是其他条目的一些扫描来执行。
本公开部分地提供了用于合并跨多个GPU(诸如GPU 102A-102N)分布的散列表的方法。例如，GPU 102A-102N中的每一个可包括由操作处理器134分配给GPU且从构建表140构造的相应散列表分区。可使用本文描述的方法或其他合适的方法来构建散列表分区。在以分布式方式探测散列表分区的情况下，可采用本文中所描述的用于使用散列表分区对散列表进行分布式探测的方法。然而，在其他实施例中，散列表分区可被合并以在一个或更多个GPU 102A-102N上复制散列表144，并且复制的散列表副本可用于散列表的分布式探测。
现在参见图3，图3是示出了根据本公开的一些实施例的将散列表144复制到GPU102A-102N的示例的示图。操作处理器134可使用一个或更多个阶段(如阶段300A和阶段300B)来合并散列表144的分区。在阶段300A中，GPU 102A-102N中的每一个可将指派给其的散列表分区(例如，并行地)推送到所有其他GPU的输出散列表。例如，GPU 102A可将散列表分区244A推送到所有GPU 102A-102N，包括其自身，GPU 102B可将散列表分区244B推送到所有GPU 102A-102N，包括其自身，且GPU 102N可将散列表分区244N推送到所有GPU 102A-102N，包括其自身，如图3所示。在GPU 102A-102N中的每一个分别拥有散列表144的非重叠分区的实施例中，阶段300A可以与连续的大容量对等存储器拷贝或合并写入无冲突地执行。同样，在一些实施例中，一旦GPU 102A-102N已经完成处理其最终构建表数据，GPU102A-102N中的每一个就可以开始阶段300A，诸如在阶段300A不在原地执行的情况下(例如，每个GPU的输出散列表是单独的初始空数据结构)。
在散列表分区244A-244N包括冲突(诸如冲突310A、310B和310N)的实施例中，可执行阶段300B。例如，由于散列表冲突，散列表分区244A-244N中的每一个可能已使用散列表分区的所指派范围之外的一些散列表条目。在所示出的示例中，线性探测可用于所指派范围外的所有散列表条目，使得该条目在GPU的GPU存储器122中是连续的并且在所指派范围的末尾之后直接在该条目处开始。为了确保溢出散列表分区的指派范围的末尾的冲突被附加在散列表分区的指派范围之后并且不被插入指派范围中(例如，由于循环环绕)，每个GPU可分配大于其所指派范围(例如，完整散列表的大小)的数据结构。在全局屏障之后，可以在阶段300B中处理这些条目。
在阶段300B中，GPU 102A-102N中的每一个的接口管理器110可执行对散列表分区244A-244N的冲突310A-310N的线性扫描(例如，针对每个GPU，用于N个分区的N个线性扫描)。在这样做时，接口管理器110可直接从每个对等散列表分区读取每个溢出条目，并且就在经处理的分区的末尾之后在散列表条目处开始。接口管理器110可以运行线性扫描，直到找到第一空条目，因为在该点处可以解决所有溢出冲突。由线性扫描找到的每个键/条目可由散列表构建器112插入本地GPU 102A-102N的输出散列表中，如图3中所示。
为了产生针对GPU 102A-102N中的每一个的经复制散列表，每个GPU可插入所有其他GPU的溢出，该溢出可包括归因于不在原地合并的GPU自身的溢出。因此，阶段300B可以包括由GPU并行地但冗余地在每个GPU上执行溢出的插入。在阶段300B之后，GPU 102A-102N中的每一个可在本地存储器(例如，GPU的GPU存储器122)中具有散列表144的完整副本。
本公开还部分地提供用于探测跨多个GPU(诸如GPU 102A-102N)分布的散列表的方法。例如，GPU 102A-102N中的每一个可包括从构建表140构建的各自的散列表分区。可使用本文描述的方法或其他合适的方法来构建散列表分区。在散列表分区用于分布式探测的情况下，可采用本文描述的用于使用散列表分区对散列表进行分布式探测的方法。然而，本公开还提供使用散列表的多个完整本地副本的散列表的分布式探测，诸如其中使用本文中所描述的方法(例如，利用图3)或其他合适的方法跨GPU合并散列表分区的情况。
操作处理器134可向GPU 102A-102N中的每一个指派和/或分布探测表142的相应部分(例如，一个或更多个分区)以用于操作138的，且GPU 102A-102N中的每一个可使用GPU的散列表探测器114来使用GPU的探测表部分来探测散列表144。
类似于关于图2所描述的构建表部分，探测表142的部分可以跨GPU 102A-102N分布和/或可以存储在GPU 102A-102N中的对应GPU可访问的存储器中。例如，可将探测表142的指派给特定GPU的部分维持在该GPU的GPU存储器122中，或一个或更多个CPU 104的CPU存储器124中，例如包括指派给探测表的一部分的对应GPU的主机系统的CPU 104。在任何示例中，探测表142的部分可在全部GPU 102A-102N或其子集可访问的GPU存储器122中或CPU存储器124中。例如，利用存储在CPU存储器124中的探测表142，操作处理器134可跨所有GPU102A-102N大体上均匀地对探测表142分区(例如，在可被GPU和/或分区的数目整除时相等)。GPU 102A-102N中的每一个的散列表探测器114可(并行地)从其指派的探测表部分读取条目/值且在本地探测散列表144。在来自探测表142的每个值仅被读取一次的情况下，所有GPU 102A-102N可以直接从固定的系统存储器读取值或者可以在分级管线中处理该值。如果探测导致散列表144中的匹配键，则结果管理器116可以对结果(例如结果146)进行物化。
提供了用于探测跨GPU 102A-102N分布的散列表的不同示例。在一些方法中，散列表部分可在GPU 102A-102N之间交换，且探测表部分可被固定(pin)到GPU 102A-102N(未交换)。在其他方法中，可将散列表部分和探测表部分两者固定到GPU 102A-102N。在其他方法中，散列表部分可被固定到GPU 102A-102N，并且探测表部分可在GPU 102A-102N之间交换。
现在参见图4，图4是示出了根据本公开的一些实施例的使用多个GPU和固定散列表分区对散列表进行分布式探测的示例的示图。
操作处理器134可为GPU 102A-102N中的每一个指派或分配散列表144和探测表142的相应部分(例如，一个或更多个分区)以用于操作138。例如，可向GPU 102A指派散列表分区244A和探测表部分442A，可向GPU 102B指派散列表分区244B和探测表部分442B，且可向GPU 102N指派散列表分区244N和探测表部分442N。
在不同示例中，操作处理器134将探测表142分区成大小大体上相等的N个分区，其中GPU 102A-102N中的每一个被分配相应分区，且N还可表示GPU的数目。散列表144和/或探测表142的指派部分可以跨GPU 102A-102N分布和/或可以存储在GPU 102A-102N中的对应GPU可访问的存储器中。例如，散列表144的指派给特定GPU的部分可维持在该GPU的GPU存储器122中。一个示例包括GPU 102A的散列表分区244A被维持在GPU 102A的GPU存储器122中。探测表142的部分可被类似地布置，或者可在一个或更多个CPU 104的CPU存储器124中，诸如包括分配给探测表142的一部分的对应GPU的主机系统的CPU 104。在任何示例中，探测表142的部分可在GPU存储器122中或在所有GPU 102A-102N或其子集可访问的CPU存储器124中。一般来说，散列表144和探测表142的部分的存储位置可基于系统100的组件、能力和配置而变化。
GPU 102A-102N可在多次迭代中探测散列表144。例如，图4示出了使用GPU 102A-102N以分布式方式探测散列表144的迭代400A和迭代400B。在迭代400A中，GPU 102A-102N中的每一个的散列表探测器114可(例如，并行地)扫描所指派的探测表部分，且可执行对存储于该GPU上的散列表分区的探测(例如，当条目的位置对应于散列表部分/分区时)。例如，GPU 102A的散列表探测器114可从探测表部分442A扫描条目，且GPU 102A的散列表探测器114可针对每个条目作出GPU 102A是否可在散列表分区244A中包括匹配条目的确定410。这可包括散列表探测器114对条目的键进行散列以计算散列值，以及使用散列值来确定散列表分区244A是否可包括匹配的条目(例如，基于全局位置ID)。
在一些示例中，可以使用位置确定器118来执行确定410。例如，GPU 102A-102N中的每一个的散列表探测器114可使用GPU的位置确定器118来作出哪个GPU被指派用于每个条目的散列表分区和/或GPU是否包括用于该条目的散列表分区的确定410。例如，GPU 102A的散列表探测器114可从探测表部分442A读取条目，且GPU 102A的位置确定器118可针对每个条目作出哪个GPU包括用于探测条目的散列表分区和/或GPU 102A是否包括散列表分区的确定410。这可包括位置确定器118对条目的键进行散列以计算散列值，以及使用散列值来导出全局位置ID，诸如散列表144的全局散列值索引、散列表144的全局桶ID、散列表144的分区ID，和/或识别用于探测散列表144的对应位置的GPU ID。如果GPU的位置确定器118使用全局位置ID确定探测是针对GPU的散列表分区的，那么GPU可探测其中的对应条目。否则，条目可不用于探测GPU的散列表分区，但可稍后用于探测包括对应的散列表分区的GPU。
在位置确定器118由散列表探测器114使用的示例中，位置确定器118可使用等式(1)、(2)和(3)和/或其他合适的等式来确定全局位置ID。通过使用全局位置ID确定是否针对GPU的本地散列表分区来探测条目，可跨GPU 102A-102N并行化散列表144的探测，从而减少对应随机存储器访问对散列表144的总探测时间的影响。
在进一步方面，基于GPU的散列表探测器114处理GPU的探测表部分的至少一部分(例如，完整的本地分区)，散列表探测器114可使用接口管理器110来将探测表数据(例如，完整部分和/或未探测或匹配的部分)提供给另一GPU以供进一步处理。探测表数据可表示图4中的探测表部分444A-444N，且可分别从探测表部分442A-442N产生或对应于探测表部分442A-442N。例如，GPU 110A的接口管理器110可将探测表部分444A(对应于探测表部分442A)提供到GPU 102B，GPU 110B的接口管理器110可将探测表部分444B(对应于探测表部分442B)提供到GPU 102N，并且GPU 110N的接口管理器110可以向GPU 102A提供或传递探测表部分444N(对应于探测表部分442N)。提供或传递数据到另一GPU的GPU可指代GPU推送数据和/或传输数据到另一GPU的存储器，和/或向GPU提供对数据的访问。
探测表部分444A-444N可由例如表示来自对应探测表部分442A-442N的一个或更多个条目的探测表数据组成。对于条目，这可包括对应键、键的散列值、条目的指定GPU ID、条目的散列表索引和/或条目的全局位置ID。在一些实施例中，提供散列值、指定GPU ID、散列表索引和/或全局位置ID可通过允许不同GPU在不计算值的情况下使用那些值来减少处理。
在一些示例中，可从探测表部分442A-442N生成探测表部分444A到444N，其中每个GPU的数据过滤器120和/或操作处理器134可从GPU已匹配到GPU散列表分区的条目滤除条目数据和/或其条目。这可允许后续操作对较少的探测表条目进行操作和/或减少GPU间业务。在一些示例中，可不将包括被过滤掉的条目的条目数据的探测表数据推送到下一GPU。例如，可首先在软件管理的分级缓冲区中收集探测表数据。这可导致GPU 102A-102N之间的负载不平衡。在探测表142在CPU存储器124中的情况下，可通过将输入划分成较小的分区来解决此负载不平衡，该较小的分区以轮询方式分布在GPU 102A-102N上。
迭代400B可类似于迭代400A，但使用探测表部分444A-444N代替探测表部分442A-442N。例如，在迭代400B中，GPU 102A-102N中的每一个的散列表探测器114可(并行地)扫描所指派的探测表部分且执行与存储在该GPU上的散列表分区的连接(例如，当条目的位置对应于散列表部分/分区时)。类似地，可使用位置确定器118，且如果位置确定器118使用全局位置ID确定条目包括GPU的散列表分区中的散列值，那么GPU可针对GPU的散列表分区进行探测。否则，条目可不用于探测GPU的散列表分区，但可稍后用于探测包括对应散列表分区或探测的位置的GPU。
同样类似于迭代400A，基于GPU的散列表探测器114处理GPU的探测表部分的至少一部分(例如，完整的本地分区)，散列表探测器114可使用接口管理器110来将探测表数据(例如，完整部分和/或未探测部分)提供到另一GPU以供进一步处理。这些经处理部分可表示图4中的探测表部分446A-446N，且可分别从探测表部分444A-444N生成或对应于探测表部分444A-444N。
迭代400A和400B中所说明的对探测表部分的处理和将探测表数据提供到不同GPU可继续，直到对散列表144探测来自探测表的所有条目为止。在任何示例中，在GPU 102A-102N之间交换的数据(例如，探测表数据)可存储在其一个或更多个缓冲区中并从其一个或更多个缓冲区处理。在一些示例中，GPU 102A-102N中的每一个包括用于双倍缓存数据的多个缓冲区。例如，在例如迭代400A的每个迭代中，GPU 102A可处理来自活动缓冲区的探测表数据(例如表示探测表部分442A)，且从GPU 102A的分级缓冲区中的另一GPU接收探测表数据，例如表示探测表部分444N。在下一迭代和/或后续迭代(诸如迭代400B)中，缓冲区的角色可以切换。GPU 102A-102N中的每一个可执行类似于GPU 102A的缓存。使用缓存，GPU102A-102N可以使数据处理与GPU 102A-102N之间的经处理数据的交换重叠。
在一些示例中，使用交换或路由算法(例如，本文中所描述的环形交换)将探测表数据提供到另一GPU。在一些示例中，交换或路由算法被配置为使得每个GPU看到探测表142的所有元素。在其他示例中，每个GPU可不看到探测表142的所有元素，且交换或路由算法可被配置为使得每个GPU看到GPU将针对GPU的散列表分区进行探测的探测表142的至少元素。
交换或路由算法的另一示例是分层交换。在分层交换中，操作处理器134可在逻辑上将GPU 102A-102N分组成M个GPU的集合，其中M小于GPU的数目N。在探测散列表144的开始处，GPU 102A-102N的每个集合S可共同地包括跨越该集合中的GPU的GPU存储器122中的若干分区的探测表142的完整副本，使得在每个集合S中复制探测表分区。当在GPU之间交换探测表数据时，可在每个集合S内交换(例如，在以轮询方式过滤之后)分区。此方法可将探测表数据的传递数从N减少到M，这对于可能不提供所有GPU之间的快速二等分带宽且有效地受通信吞吐量限制的GPU-GPU连接拓扑来说可是期望的。例如，来自GPU 102A-102N之间的全(all-to-all)互连的压力可被卸载，因为GPU可在探测散列表144的第一迭代期间仅全通信，但在接下来的M-1个迭代中，GPU可在集合内通信。分层交换可类似地用于构建散列表144，此类方法在本文中描述(例如，使用构建表140代替探测表142)。
虽然GPU 102A-102N中的每一个被示出为包括单个探测表部分442A-442N，但在GPU最初包括多个探测表部分(例如，分区)的示例中，当GPU从另一GPU接收到探测表数据时，其可处理所接收到的探测表数据以及初始探测表部分。例如，在迭代400A中，GPU 102A可以从探测表部分442A和至少一个其他初始探测表部分开始。然后，在迭代400B中，GPU102A可以处理探测表部分444N以及其他初始探测表部分中的一个或更多个。进一步注意的是，尽管图4示出了具有单个散列表分区的GPU 102A-102N中的每个GPU，但是GPU 102A-102N中的任何GPU可以被分配任何数量的散列表分区。
作为示例，在迭代400A中，GPU 102A-102N中的每一个的散列表探测器114可扫描所指派的探测表分区，且针对存储在该GPU上的部分散列表执行探测(例如，当条目的位置对应于散列表部分/分区时)。并行地，能够以轮询方式将探测表数据发送到对等GPU。这可以重复，直到所有探测表分区在所有GPU 102A-102N上被处理。类似于构建阶段的实施例，其中数据过滤器120过滤探测表142，GPU 102A-102N中的每一个可以将仅表示尚未被过滤掉的键和值的探测表数据推送到下一GPU的分级缓冲区。使用这种方法，可以最小化GPU间流量，并且后续传递可以对更少的值进行操作。
尽管图4示出了散列表分区被固定到GPU 102A-102N并且探测表部分在GPU 102A-102N之间交换的方法，如本文该，散列表数据可在GPU 102A-102N之间交换并且探测表部分可被固定到GPU 102A-102N。例如，现在参见图5，图5是示出根据本公开的一些实施例的使用GPU 102A-102N和固定探测表部分542A-542N对散列表进行分布式探测的示例的示图。
图5中的迭代500A和迭代500B可以分别类似于图4中的迭代400A和迭代400B。然而，在迭代500A中，可扫描探测表部分542A-542N以对散列表部分544A-544N进行探测，并且散列表部分546A-546N可对应于散列表部分544A-544N(例如，从其生成)并且由GPU 102A-102N交换。在迭代500B中，可扫描探测表部分542A-542N以对所交换的散列表部分546A-546N进行探测，并且散列表部分548A-548N可对应于散列表部分546A-546N(例如，从其生成)并且由GPU 102A-102N交换。在这样做时，可以针对每个GPU做出一个或更多个确定510，其可以类似于一个或更多个确定410。
作为示例，在迭代500A中，GPU 102A-102N中的每一个可扫描一个或更多个探测表部分542A-542N中所指派的一个或更多个探测表部分，并且可针对存储在该GPU上的散列表部分544A-544N执行探测(例如，当条目的位置对应于散列表部分/分区时)。并行地，可例如以轮询方式将散列表部分546A-546N中的对应散列表部分发送到对等GPU和/或提供到对等GPU。这可重复，直到所有GPU上的所有散列表部分被处理或所有探测表条目被匹配到散列表144为止。例如，在GPU 102A-102N包括N个GPU的情况下，可将散列表144拆分成N个分区(每个GPU一个)。在此示例中，在探测表142上可存在N个传递。然而，在每次传递时，可仅针对来自探测表部分542A-542N的键的子集来访问对应的散列表分区。尤其是，对GPU的访问可针对具有落入GPU处的散列表分区范围中的散列值的那些键。照此，跨所有N个传递的所有GPU 102A-102N的随机访问的总数可以等于探测表142中的键的总数。
上述方法的性能可能受到每次迭代中的以下定时中的最慢定时的限制：(1)探测表142的分区大小/对探测表的顺序访问，其为GPU存储器122的单个GPU存储器吞吐量或访问CPU存储器的GPU的存储器吞吐量(以扫描探测表分区)；(2)探测表142的分区大小/GPU存储器122的随机单个GPU存储器吞吐量/N(以访问散列表144，平均1/N的值将落入当前散列表分区中)；以及(3)散列表144的分区大小/每GPU二分区带宽(以交换散列表分区)。如果探测表实际上在GPU存储器中，那么顺序GPU存储器访问常常比随机GPU存储器访问快一个数量级，使得(2)或(3)将为主要因素，这取决于探测表142和散列表144的大小。如果探测表在CPU存储器中，那么(1)可变成瓶颈。
如本文所描述的，在一些方法中，散列表部分和探测表部分两者可被固定到GPU102A-102N。例如，当GPU 102A的位置确定器118作出哪个GPU被指派针对条目的散列表分区(例如，取决于散列索引)并且GPU不同于GPU 102A的确定410/510时，GPU 102A可直接访问对应GPU以对散列表分区执行探测。具体地，GPU 102A可以远程访问对应GPU的GPU存储器122。其他GPU 102B-102N可类似地表现。对远程GPU存储器122的直接访问可通过将远程GPU存储器122映射到执行远程访问的GPU的寻址空间中来执行，这可使用统一存储器来促进。统一存储器可以指从GPU 102A-102N和/或CPU 104中的任一个可访问的单个存储器地址空间。使用统一存储器，应用程序可分配可从在CPU或GPU上运行的代码读取或写入到该代码的数据。作为另一示例，GPU 102A可将用于条目的探测表数据提供到对应GPU以用于由接收GPU进行探测(例如，到其分级缓冲区)，而不是远程地执行直接访问。其他GPU 102B-102N可类似地表现。
虽然在不同示例中，散列表部分和/或探测表部分可被固定到GPU 102A-102N，但在其他示例中，一些散列表部分和/或探测表部分可在GPU 102A-102N之间交换，且其他散列表部分和/或探测表部分可被固定。进一步，GPU存储器122的用于探测的远程访问可集成到任何所描述的示例中，且可针对GPU 102A-102N中的一些GPU而非其他GPU来执行，和/或可针对探测表142中的条目的一些扫描而非其他扫描来执行，这取决于不同潜在因素。因此，本文描述的方法的不同混合和组合是可能的。
如本文中所描述，操作处理器134可向GPU 102A-102N中的每一个指派或分配用于操作138的探测表142的相应部分(例如，一个或更多个分区)，且GPU 102A-102N中的每一个可使用GPU的散列表探测器114来使用GPU的探测表部分探测散列表144。在任何示例中，此可包括操作处理器134在探测阶段开始时(在发生探测之前)重新布置探测表142的条目以减少GPU间通信。在不同示例中，操作处理器134可至少部分地基于指派给GPU的散列表144的范围来确定用于GPU的探测表142的一部分。例如，操作处理器134可使用全局位置标识符基于条目落入指派给GPU(例如，在GPU的GPU存储器122中)的散列表144的范围内而将条目指派给GPU。使用此方法，操作处理器134可将探测表142的一个或更多个条目重新布置成若干分区(例如，等于GPU 102A-102N的数目)，其中每个分区可仅保持落入分配给对应GPU的散列表分区的范围中的键。可在CPU 104上和/或GPU 102A-102N上执行重新布置。
在一些示例中，为了重新布置探测表142的条目，探测表数据可不在适当位置(inplace)移动，但可从探测表142复制到对应探测表分区中的连续位置(例如，以使吞吐量最大化)。对于每个GPU，可使用共享存储器分级探测表分区，以避免对GPU全局存储器的随机存储器访问。GPU 102A-102N可各自例如通过生成0-N-1个桶来填充探测表分区，其中N为GPU的数目。在GPU 102A-102N填充探测表分区之后，这些分区可被交换(例如，GPU之间的全互换，其中每个GPU将其桶K发送到GPU K)和串接(例如，以从来自其他GPU的桶形成单个分区)，以使得最终每个GPU具有探测表分区，该探测表分区具有落入本地散列表分区的范围中的键。使用此方法，每个探测表分区索引可绑定到对应的散列表分区范围(例如，通过对键进行散列且除以散列表分区大小以确定条目的探测表分区索引)。
本公开还部分地提供了用于物化跨多个GPU(诸如GPU 102A-102N)分布的探测散列表的结果的方法。例如，GPU 102A-102N中的每一个可包括散列表144的相应散列表分区和/或散列表144的复制副本。散列表144可以由GPU 102A-102N使用在此描述的方法或其他适合的方法来探测以产生结果146。
现在参见图6，图6是示出了根据本公开的一些实施例的使用GPU 102A-102N和全局偏移变量604对散列表144的分布式探测的结果进行物化的示例的示图。GPU 102A-102N可以使用全局偏移变量604来将至少一些结果物化到在GPU 102A-102N之间共享的至少存储器606。例如，GPU 102A-102N可以将结果146物化到存储器606中的全局输出缓冲区608。存储器606可包括可由GPU中的每一个访问的CPU存储器或GPU存储器。
在各种示例中，全局偏移变量604可驻留在与存储器606相同或不同的存储器602中，且可包括CPU存储器或GPU存储器。在一些实施例中，全局偏移变量604驻留在可由GPU102A-102N中的每一个访问的GPU 102A-102N中的一个或更多个GPU的GPU存储器122中，且可用于协调对全局输出缓冲区608的写入。全局偏移变量604可包括变量，且变量的值可用于跟踪和定义结果应写入到全局输出缓冲区608的何处的全局偏移。例如，为了物化结果146，GPU 102A-102N中的每一个可使用具有系统宽范围的原子操作，其将全局偏移变量604递增将由GPU物化的结果146(或值)的数目。随后可将对应结果146写入到全局输出缓冲区608中由原子操作返回的全局偏移变量604的值处。例如，GPU 102A可将结果146中的结果610A写入到全局输出缓冲区608中由全局偏移变量604定义的位置处，且可基于结果610A的数目递增全局偏移变量604。类似地，GPU 102B可将结果146中的结果610B写入到全局输出缓冲区608中由全局偏移变量604定义的位置处，且全局偏移变量604可基于结果610B的数目而递增。进一步，GPU 102N可将结果146中的结果610N写入到全局输出缓冲区608中由全局偏移变量604定义的位置处，且全局偏移变量604可基于结果610N的数目而递增。
现在参见图7，图7是示出了根据本公开的一些实施例的使用多个GPU和本地输出缓冲区的大小对散列表的分布式探测的结果进行物化的示例的示图。在不采用全局偏移变量的情况下，诸如在GPU 102A-102N中的一个或更多个不能访问或使用全局偏移变量604的情况下，或者出于性能原因，GPU可以将其在本地存储器(诸如本地GPU存储器)中产生的部分结果物化。例如，GPU 102A可将结果610A物化到GPU 102A的本地输出缓冲区，GPU 102B可将结果610B物化到GPU 102B的本地输出缓冲区，且GPU 102N可将结果610N物化到GPU 102N的本地输出缓冲区。GPU 102A-102N可以进一步物化从本地输出缓冲区到全局输出缓冲区608的结果610A-610N，以形成结果146。为此，GPU 102A-102N可以计算本地输出缓冲区大小的排斥前缀和。
为了说明排斥前缀总和，假设GPU 102A-102N包括具有以下本地输出缓冲区大小的四个GPU：5、8、2和10。此阵列的排斥前缀和将为0、5、13、15，其中当前大小值从该和中排除，且将在当前大小值之前的一切相加。例如，对于第四条目(10)，排斥前缀和可计算为5+8+2。该前缀和序列可分别定义每个本地输出缓冲区中的结果146的部分的全局偏移。例如，在GPU 102A是以上示例中的本地输出缓冲区大小为5的GPU的情况下，可使用全局偏移0(例如，指示全局输出缓冲区608的开始地址)来物化结果610A。GPU 102A-102N中的每一个可使用结果146的部分的对应全局偏移值将结果146的对应部分写入(例如，并行推送)到全局输出缓冲区608。
在不同实施例中，图6和图7的方法可以组合，如在具有全连接的GPU的多个岛的系统上。例如，可以在每个全连接的岛内使用图6的方法，然后可以使用图7的方法来合并来自岛的结果146的部分。在进一步的示例中，可以在CUDA统一存储器中分配全局偏移变量604，并且可以使用具有系统宽范围的原子的软件仿真来实现图6的方法。
现在参见图8，方法800和在此描述的其他方法的每个框包括可以使用硬件、固件和/或软件的任何组合执行的计算过程。例如，不同功能可由执行存储在存储器中的指令的处理器执行。该方法还可体现为存储在计算机存储介质上的计算机可用指令。这些方法可由独立的应用、服务或托管服务(独立地或与另一托管服务组合)或另一产品的插件来提供，仅举几例。此外，通过示例的方式，相对于多GPU分布式处理系统100(图1)来描述该方法。然而，这些方法可以另外地或可替代地由任何一个系统或系统的任何组合来执行，包括但不限于在此描述的那些系统。
图8是示出了根据本公开的一些实施例的用于使用多个GPU分布式构建散列表的方法800的流程图，其中构建表条目与本地散列表分区相关联。在框B802，方法800包括接收构建表的部分。例如，在迭代200A中，GPU 102A的接口管理器110可以接收构建表部分240A。
在框B804处，方法800包括从构建表的该部分中的条目计算全局位置标识符。例如，GPU 102A的位置确定器118可由构建表部分240A中的条目来计算全局ID，其将来自GPU102A-102N的指定GPU识别为被分配了散列表144的散列表分区244A(和/或识别用于插入条目的散列表分区244A)。例如，可针对由GPU 102A的散列表构建器112执行的确定210进行计算。
在框B806处，方法800包括：基于全局位置标识符执行条目在散列表的散列表分区中的插入。例如，GPU 102A的散列表构建器112可基于将GPU 102A识别为指定GPU(和/或识别用于插入条目的散列表分区244A)的全局ID来执行条目在散列表分区244A中的插入。该插入可以例如响应于由GPU 102A的散列表构建器112执行的确定210而做出。
在使用方法800构建散列表之后，可探测散列表的至少一部分。例如，GPU 102A的散列表探测器114可使用探测表142的至少一部分来探测散列表144的至少一部分以产生结果146中的一个或更多个。在一些示例中，可合并散列表分区244A-244N以形成经复制的副本，且探测可针对散列表144的本地副本。在其他示例中，探测可针对散列表分区244A。进一步，探测和结果物化可使用任何合适的方法来执行，包括本文描述的那些方法。虽然主要针对迭代200A描述了方法800，但方法800可类似地应用于迭代200B。进一步，方法800可应用于其中GPU 102A-102N可将条目从本地构建表部分远程插入到分配给其他GPU的散列表分区中的实施例，在这种情况下，来自本地构建表部分的数据可不被提供给其他GPU以供那些GPU执行插入，并且可能不需要迭代200B。
现在参见图9，图9是示出了根据本公开的一些实施例的用于使用多个GPU分布式构建散列表的方法900的流程图，其中构建表条目与远程散列表分区相关联。在框B902处，方法900包括接收构建表的部分。例如，在迭代200A中，GPU 102A的接口管理器110可以接收构建表部分240A。
在框B904处，方法900包括从构建表的该部分中的条目计算全局位置标识符。例如，GPU 102A的位置确定器118可由构建表部分240A中的条目来计算全局ID，其将来自GPU102A-102N的指定GPU识别为被分配了散列表144的散列表分区244N(和/或识别用于插入条目的散列表分区244N)。例如，可针对由GPU 102A的散列表构建器112执行的确定210进行计算。
在框B906处，方法900包括基于该全局位置标识符发送表示该条目的数据以用于将该条目插入散列表的散列表分区中。例如，GPU 102A的接口管理器110可基于将指定GPU识别为不同于GPU 102A(和/或识别散列表分区244N以用于插入条目)的全局位置标识符来发送表示条目的数据，以用于将条目插入散列表分区244N中该指定GPU处。此发送可例如响应于由GPU 102A的散列表构建器112执行的确定210而作出，且该条目可包括在提供给GPU102B的构建表部分242A中。稍后，GPU 102B可将数据提供到GPU 102N，GPU 102N可执行到散列表分区244N中的插入。在其他示例中，数据可由GPU 102A或GPU 102B发送到GPU 102N，作为到散列表分区244N中的远程插入的部分。进一步，GPU 102A向其提供数据的GPU可以取决于所采用的交换或路由算法。
在使用方法900构建散列表之后，可探测散列表的至少一部分。例如，GPU 102A的散列表探测器114可使用探测表142的至少一部分来探测散列表144的至少一部分，以产生结果146中的一个或更多个。在一些示例中，可合并散列表分区244A-244N以形成经复制的副本，且探测可针对散列表144的本地副本。在其他示例中，探测可针对散列表分区244A。进一步，探测和结果物化可使用任何合适的方法来执行，包括本文描述的那些方法。虽然主要针对迭代200A描述方法900，但方法900可类似地应用于迭代200B。进一步，方法900可应用于其中GPU 102A-102N可执行将条目从本地构建表部分远程插入到分配给其他GPU的散列表分区的实施例，在这种情况下，来自本地构建表部分的数据可不被提供给其他GPU以供那些GPU执行插入，并且可能不需要迭代200B。
现在参见图10，图10是示出了根据本公开的一些实施例的用于使用多个GPU对散列表进行分布式探测的方法1000的流程图，其中探测表条目与本地散列表分区相关联。在框B1002处，方法1000包括接收探测表的部分。例如，在迭代400A中，GPU 102A的接口管理器110可以接收探测表部分442A。
在框B1004处，方法1000包括从探测表的该部分中的条目计算全局位置标识符。例如，GPU 102A的位置确定器118可由探测表部分442A中的条目来计算全局ID，其将来自GPU102A-102N的指定GPU识别为包括用于探测该条目的散列表144的散列表分区244A(和/或识别该散列表分区244A应使用该条目来探测)。例如，可针对由GPU 102A的散列表探测器114执行的确定410进行计算。
在框B1006处，方法1000包括基于全局位置标识符执行对散列表的散列表分区的探测。例如，GPU 102A的散列表探测器114可基于将GPU 102A识别为指定GPU(和/或识别散列表分区244A应使用该条目来探测)的全局ID来使用该条目执行对散列表分区244A的探测。例如，可响应于由GPU 102A的散列表探测器114执行的确定410来执行探测。
在框B1008处，方法1000包括将对散列表的探测的一个或更多个结果(如果存在)提供到全局输出缓冲区。例如，GPU 102A的散列表探测器114可以使用结果管理器116来将结果146中的一个或更多个结果物化到全局输出缓冲区，诸如图6和图7的全局输出缓冲区608。探测和结果物化可使用任何合适的方法来执行，包括本文描述的那些方法。虽然主要针对迭代400A描述方法1000，但是方法1000可以类似地应用于迭代400B。进一步，方法1000可应用于其中GPU 102A-102N可使用来自本地探测表部分的条目执行远程探测以对其他GPU上的表分区进行散列的实施例，在这种情况下，来自本地探测表部分的数据可不被提供给其他GPU以供那些GPU执行探测，并且可能不需要迭代400B。
进一步地，方法1000还可以应用于关于图5所描述的方法。例如，GPU 102A可使用来自块B1004的全局ID来确定是否在块B1006处在迭代500A中探测散列表部分544A，和/或可使用来自块B1004的全局ID来确定是否在块B1006处在迭代500B中探测散列表部分546A。
现在参见图11，图11是示出了根据本公开的一些实施例的用于使用多个GPU对散列表进行分布式探测的方法1100的流程图，其中探测表条目与远程散列表分区相关联。在框B1102处，方法1100包括接收探测表的部分。例如，在迭代400A中，GPU 102A的接口管理器110可以接收探测表部分442A。
在框B1104处，方法1100包括从探测表的该部分中的条目计算全局位置标识符。例如，GPU 102A的位置确定器118可由探测表部分442A中的条目来计算全局ID，其将来自GPU102A-102N的指定GPU识别为包括用于探测该条目的散列表144的散列表分区244N(和/或识别该散列表分区244N应使用该条目来探测)。例如，可针对由GPU 102A的散列表探测器114执行的确定410进行计算。
在框B1106处，方法1100包括基于全局位置标识符发送表示条目的数据，以用于对散列表的散列表分区进行探测。例如，GPU 102A的接口管理器110可基于将指定GPU识别为不同于GPU 102A(和/或识别散列表分区244N应使用该条目来探测)的全局位置标识符使用指定GPU处的条目来发送表示用于探测散列表分区244N的条目的数据。此发送可例如响应于由GPU 102A的散列表探测器114执行的确定410而作出，且该条目可包括在提供给GPU102B的探测表部分444A中。稍后，GPU 102B可将数据提供到GPU 102N，GPU 102N可执行到散列表分区244N中的探测。在其他示例中，数据可由GPU 102A或GPU 102B发送到GPU 102N，作为到散列表分区244N中的远程探测的部分。进一步，GPU 102A向其提供数据的GPU可以取决于所采用的交换或路由算法。
在框B1108处，方法1100包括将对散列表的探测的一个或更多个结果(如果存在)提供到全局输出缓冲区。例如，GPU 102A的散列表探测器114可以使用结果管理器116来将结果146中的一个或更多个结果物化到全局输出缓冲区，诸如图6和图7的全局输出缓冲区608。探测和结果物化可使用任何合适的方法来执行，包括本文该的那些方法。虽然主要针对迭代400A描述方法1100，但是方法1000可以类似地应用于迭代400B。进一步，方法1000可应用于其中GPU 102A-102N可使用来自本地探测表部分的条目执行远程探测以对其他GPU上的表分区进行散列的实施例，在这种情况下，来自本地探测表部分的数据可不被提供给其他GPU以供那些GPU执行探测，并且可能不需要迭代400B。
进一步地，方法1100还可以应用于关于图5所描述的方法。例如，GPU 102A可使用来自框B1104的全局ID来确定是否在框B1106处在迭代500A中探测散列表部分544A，和/或可使用来自框B1104的全局ID来确定是否在框B1106处在迭代500B中探测散列表部分546A。
现在参见图12，图12是示出了根据本公开的一些实施例的用于使用多个GPU和全局偏移变量对散列表的分布式探测的结果进行物化的方法1200的流程图。在框B1202处，方法1200包括探测散列表的至少一部分以确定由GPU执行的对散列表的分布式探测的一个或更多个结果(如果存在)。例如，图6的GPU 102A-102N的散列表探测器114可使用本文描述的任何合适的方法或其他合适的方法来执行对散列表144的分布式探测。GPU 102A例如可以确定结果610A，该结果610A可以是探测的结果146的一部分。
在框B1204处，方法1200包括基于来自由GPU共享的全局偏移变量的全局偏移变量来确定全局输出缓冲区中的偏移，以便将结果(如果存在)物化到全局输出缓冲区。例如，GPU 102A的结果管理器116可以从全局偏移变量604确定全局输出缓冲区608中的偏移。
在框B1206处，方法1200包括使用偏移将一个或更多个结果(如果存在)物化到全局输出缓冲区。例如，GPU 102A的结果管理器116可在全局输出缓冲区608中对应于偏移的位置处将结果610A物化到全局输出缓冲区608。
现在参见图13，图13是示出了根据本公开的一些实施例的用于使用多个GPU和本地偏移缓冲区的大小来物化对散列表的分布式探测的结果的方法1300的流程图。在框B1302处，方法1300包括探测散列表的至少一部分，以确定由GPU执行的对散列表的分布式探测的一个或更多个结果(如果存在)。例如，图7的GPU 102A-102N的散列表探测器114可使用本文描述的任何合适的方法或其他合适的方法来执行对散列表144的分布式探测。GPU102A例如可以确定结果610A，该结果610A可以是探测的结果146的一部分。
在框B1304处，方法1300包括将一个或更多个结果(如果存在)存储在本地输出缓冲区中。例如，GPU 102A的结果管理器116可以将结果610A存储到GPU 102A的本地输出缓冲区。
在框B1306处，方法1300包括从由GPU使用的本地偏移缓冲区的大小确定全局输出缓冲区中的偏移，用于将结果(如果存在)物化到全局输出缓冲区。例如，结果管理器116可以使用GPU 102A-102N的本地输出缓冲区的大小来计算本地输出缓冲区的排斥前缀和，其可以包括全局输出缓冲区608中的结果610A的偏移。
在框B1306处，方法1300包括使用偏移将一个或更多个结果(如果存在)物化到全局输出缓冲区。例如，GPU 102A的结果管理器116可在全局输出缓冲区608中的对应于偏移的位置处将结果610A物化到全局输出缓冲区608。
图14是适合用于实现本公开一些实施例的示例计算设备1400的框图。计算设备1400可以包括直接或间接耦合以下设备的互连系统1402：存储器1404、一个或更多个中央处理单元(CPU)1406、一个或更多个图形处理单元(GPU)1408、通信接口1410、输入/输出(I/O)端口1412、输入/输出组件1414、电源1416以及一个或更多个呈现组件1418(例如，显示器)。GPU 102A-102N中的一个或更多个GPU可以对应于一个或更多个GPU 1408和/或被包括在计算设备1400的一个或更多个实例化中。进一步，CPU 104中的一个或更多个可以对应于一个或更多个CPU 1406中的一个或更多个CPU和/或被包括在计算设备1400的一个或更多个实例化中。进一步，本文描述的不同存储器可对应于存储器1404和/或计算设备1400的一个或更多个实例化。
尽管图14的各个框被示为经由互连系统1402与线路连接，但这并不旨在是限制性的，并且仅是为了清楚起见。例如，在一些实施例中，呈现组件1418(诸如显示设备)可被认为是I/O组件1414(例如，如果显示器是触摸屏)。作为另一个示例，CPU 1406和/或GPU 1408可以包括存储器(例如，存储器1404可以表示除了GPU 1408、CPU 1406和/或其他组件的存储器之外的存储设备)。换言之，图14的计算设备仅是说明性的。在如“工作站”、“服务器”、“膝上型计算机”、“台式计算机”、“平板电脑”、“客户端设备”、“移动设备”、“手持式设备”、“游戏控制台”、“电子控制单元(ECU)”、“虚拟现实系统”和/或其他设备或系统类型之类的类别之间不进行区分，因为所有都被考虑在图14的计算设备的范围内。
互连系统1402可以表示一条或更多条链路或总线，诸如地址总线、数据总线、控制总线或其组合。互连系统1402可包括一种或更多种总线或链路类型，诸如工业标准体系结构(ISA)总线、扩展工业标准体系结构(EISA)总线、视频电子标准协会(VESA)总线、外围组件互连(PCI)总线、外围组件互连快速(PCIe)总线和/或另一类型的总线或链路。在一些实施例中，部件之间存在直接连接。作为示例，CPU 1406可直接连接到存储器1404。进一步，CPU 1406可直接连接到GPU 1408。在组件之间存在直接或点对点连接的情况下，互连系统1402可以包括用于执行连接的PCIe链路。在这些示例中，PCI总线不需要被包括在计算设备1400中。
存储器1404可包括各种各样的计算机可读介质中的任何介质。计算机可读介质可以是可由计算设备1400访问的任何可用介质。计算机可读介质可以包括易失性和非易失性介质，以及可移除和不可移除介质。作为示例而非限制性地，计算机可读介质可包括计算机存储介质和通信介质。
计算机存储介质可以包括以用于存储诸如计算机可读指令、数据结构、程序模块和/或其他数据类型的信息的任何方法或技术实现的易失性和非易失性介质和/或可移动和不可移动介质。例如，存储器1404可存储计算机可读指令(例如，其表示程序和/或程序元素，例如操作系统)。计算机存储介质可以包括但不限于RAM、ROM、EEPROM、闪存或其他存储器技术、CD-ROM、数字多功能盘(DVD)或其他光盘存储装置、磁带盒、磁带、磁盘存储装置或其他磁存储设备、或可用于存储期望的信息且可由计算设备1400访问的任何其他介质。如本文所使用的，计算机存储介质不包括信号本身。
计算机存储介质可以在诸如载波之类的调制数据信号或其他传输机制中包括计算机可读指令、数据结构、程序模块和/或其他数据类型，并且包括任何信息输送介质。术语“调制数据信号”可以指这样的信号，该信号使它的特性中的一个或更多个以这样的将信息编码到该信号中的方式设置或改变。举例而言且非限制性地，计算机存储介质可包括诸如有线网络或直接有线连接之类的有线介质，以及诸如声音、RF、红外和其他无线介质之类的无线介质。任何以上该的组合也应当包括在计算机可读介质的范围内。
CPU 1406可经配置以执行计算机可读指令以控制计算设备1400的一个或更多个组件以执行本文所描述的方法和/或过程中的一个或更多个。CPU 1406中的每一个可以包括能够同时处理多个软件线程的一个或更多个核(例如，一个、两个、四个、八个、二十八个、七十二个等等)。CPU 1406可包括任何类型的处理器，并且可以包括不同类型的处理器，这取决于实现的计算设备1400的类型(例如具有用于移动设备的较少核的处理器以及具有用于服务器的更多核的处理器)。例如，取决于计算设备1400的类型，处理器可以是使用精简指令集计算(RISC)实现的高级RISC机器(ARM)处理器或者使用复杂指令集计算(CISC)实现的x86处理器。除了一个或更多个微处理器或者诸如数学协处理器之类的补充协处理器之外，计算设备1400还可以包括一个或更多个CPU 1406。
GPU 1408可由计算设备1400使用以渲染图形(例如，3D图形)或执行的通用计算。例如，GPU 1408可用于GPU上的通用计算(GPGPU)。GPU 1408可以包括能够同时处理数百或数千个软件线程的数百或数千个核。GPU 1408可响应于渲染命令(例如，经由主机接口接收的来自CPU 1406的渲染命令)而生成输出图像的像素数据。GPU 1408可包括用于存储像素数据或任何其他合适数据(例如，GPGPU数据)的图形存储器(例如，显示存储器)。显示存储器可作为存储器1404的部分而被包括。GPU1408可包括并行操作(例如，经由链路)的两个或更多个GPU。链路可以直接连接GPU(例如，使用NVLINK)或可以通过交换机(例如，使用NVSwitch)连接GPU。当组合在一起时，每个GPU 1408可生成用于输出的不同部分或用于不同输出的像素数据或GPGPU数据(例如，用于第一图像的第一GPU和用于第二图像的第二GPU)。每个GPU可包括其自己的存储器，或可与其他GPU共享存储器。
通信接口1410可以包括一个或更多个接收器、发送器和/或收发器，其使得计算设备1400能够经由电子通信网络与其他计算设备通信，包括有线和/或无线通信。通信接口1410可以包括使能通过若干不同网络中的任何网络进行通信的组件和功能，该网络例如无线网络(例如Wi-Fi、Z波、蓝牙、蓝牙LE、ZigBee等等)、有线网络(例如通过以太网或无线带宽通信)、低功率广域网(例如LoRaWAN、SigFox等等)和/或因特网。
I/O端口1412可以使得计算设备1400能够逻辑地耦合到包括I/O组件1414、呈现组件1418和/或其他组件在内的其他设备，其中一些可以内置到(例如集成到)计算设备1400中。说明性I/O组件1414包括麦克风、鼠标、键盘、操纵杆、游戏垫、游戏控制器、碟形卫星天线、扫描仪、打印机、无线设备等等。I/O组件1414可以提供处理用户生成的空中手势、语音或其他生理输入的自然用户接口(NUI)。在一些示例中，输入可以传输至适当的网络元件以便进一步处理。NUI可以实现语音识别、手写笔识别、面部识别、生物特征识别、屏幕上和邻近屏幕的手势识别、空中手势、头部和眼睛跟踪以及与计算设备1400的显示器关联的触摸识别(如下文更详细地描述的)的任意组合。计算设备1400可以包括诸如立体照相机系统之类的深度照相机、红外照相机系统、RGB照相机系统、触摸屏技术以及这些的组合，以用于手势检测和识别。此外，计算设备1400可以包括使能运动检测的加速度计或陀螺仪(例如作为惯性测量单元(IMU)的部分)。在一些示例中，加速度计或陀螺仪的输出可以由计算设备1400用来渲染沉浸式增强现实或者虚拟现实。
电源1416可以包括硬接线电源、电池电源或者其组合。电源1416可以向计算设备1400供电以使得计算设备1400的组件能够操作。
呈现组件1418可以包括显示器(例如监视器、触摸屏、电视屏幕、平视显示器(HUD)、其他显示器类型或者其组合)、扬声器和/或其他呈现组件。呈现组件1418可以接收来自其他组件(例如GPU 1408、CPU 1406等等)的数据，并且输出该数据(例如作为图像、视频、声音等等)。
本公开可以在由计算机或者诸如个人数字助理或其他手持式设备之类的其他机器执行的、包括诸如程序模块之类的计算机可执行指令的机器可使用指令或者计算机代码的一般背景下进行描述。通常，包括例程、程序、对象、组件、数据结构等等的程序模块指的是执行特定任务或者实现特定抽象数据类型的代码。本公开可以在各种各样的系统配置中实践，这些配置包括手持式设备、消费电子器件、通用计算机、更专业的计算设备等等。本公开也可以在其中任务由通过通信网络链接的远程处理设备执行的分布式计算环境中实践。
如在本文中使用的，“和/或”关于两个或更多元素的叙述应当解释为仅指一个元素或者元素组合。例如，“元素A、元素B和/或元素C”可以包括仅仅元素A，仅仅元素B，仅仅元素C，元素A和元素B，元素A和元素C，元素B和元素C，或者元素A、B和C。此外，“元素A或元素B中的至少一个”可以包括元素A中的至少一个，元素B中的至少一个，或者元素A中的至少一个和元素B中的至少一个。
本文详细地描述了本公开的主题以满足法定要求。然而，描述本身并非意在限制本公开的范围。相反地，本发明人已经设想到，要求保护的主题也可以以其他的方式具体化，以包括与本文中结合其他当前或未来技术描述的步骤不同的步骤或者相似的步骤的组合。而且，尽管术语“步骤”和/或“块”在本文中可以用来隐含采用的方法的不同元素，但是这些术语不应当被解释为暗示本文公开的各个步骤之中或之间的任何特定顺序，除非明确描述了各步骤的顺序。
机译： 使用多个GPU的哈希表的有效且可扩展的构建和探查
机译： 使用多个GPU的哈希表的有效且可扩展的构建和探查
机译： 使用多个高速缓存模拟进行动态高速缓存分配调整，以有效地构建高速缓存实用程序曲线
