Page 449 - 《软件学报》2025年第12期

5830 软件学报 2025 年第 36 卷第 12 期

8. for j ← 1 to N do
9. pht j [index] ← R.tuple[location] OR pv j [index] ← R.tuple[location].payload
10. end for
11. i ← i + 1, location ← i + start
12. until i > R_slice_length k
13. end for
14. probe 阶段
15. for thread k in all threads do
16. start ← startoffset k in S 表
17. i ← 1, location ← i + start
18. sum ← 0
19. repeat
20. key ← S.tuple[location].key
21. index ← (Hash(key) OR key)
22. numaid ← get_numa_id(thread k )
23. sum ← sum + (pht numaid [index].payload OR pv numaid [index])

24. until i > S_slice_length k
25. end for
26. return sum
2.2.2 粗粒度复制策略 (coarse-grained replication)
如图 4(b) 所示, 每个 NUMA 节点内的 R 表分区独立创建哈希表/向量, 然后将其复制到其他 NUMA 节点中,
从而提供多入口的哈希表/向量探测. 该策略创建 NUMA 局部的哈希表/向量, 通过粗粒度的复制降低跨 NUMA
写操作延迟, 探测阶段保证了 NUMA 访问的局部性, 但增加了多哈希表/向量探测代价, 适用于创建阶段跨 NUMA
写代价较大的连接负载. 基于粗粒度复制策略的 NUMA 节点内私有哈希表或私有向量连接算法如算法 3 所示.

算法 3. 基于粗粒度复制策略的 NUMA 节点内私有哈希表或私有向量连接算法.

Input: R 表, S 表, 私有哈希表 (pht k_m ) 或私有向量 (pv k_m ), k, m ∈ [0, N), N 对应于 NUMA 节点数;
Output: sum: 连接成功计数.
1. build 阶段
2. for thread k in all threads do
3. start ← startoffset k in R 表
4. i ← 1, location ← i + start
5. repeat
6. key ← R.tuple[location].key
7. index ← (Hash(key) OR key)
8. numaid ← get_numa_id(thread k )
9. pht numaid_numaid [index] ← R.tuple[location] OR pv numaid_numaid [index] ← R.tuple[location].payload
10. i ← i + 1, location ← i + start

11. until i > R_slice_length k
12. end for