代码之家 › 专栏 › 技术社区 › slacy

多核机器上更快的基本数据结构?

parallel-processing data-structures multithreading

slacy · 技术社区 · 17 年前

您能否利用拥有多个CPU的事实,在多核机器上构建更快的基本数据结构(即链表、哈希表、集合、skiplist、bloom筛选器、红黑树等)?

我对pthread做了一些初步的实验,发现pthread_create()大约需要30us,但是一个简单的hash_映射插入所需的时间要比在单个内核上少得多。因此,我很难想象创建一个更快的散列图<>,因为同步原语和线程创建非常慢。我还可以想象并行的树遍历和平衡,但同样,同步原语似乎会使运行时更长,而不是更短。

我仍然觉得“我有更多的CPU,因此,我应该能够做得更快”,但我不能为这句话的证明或反证明绞尽脑汁。我在C++中已经做了相当多的实验,但是现在我怀疑其他语言可以为这个任务提供更好的解决方案(Erlang?)。思想?

编辑细节:我认为有几种经常使用的编程/数据结构范例可能会加快速度。例如,我发现自己经常编写这样的代码(实际数据已替换为“rand()”)

static const int N = 1000000; 
static const int M = 10000000; // 10x more lookups 
hash_map<int, int> m; 
// batch insert a bunch of interesting data 
for (int i = 0; i < N; i++) m[rand()] = rand(); 

// Do some random access lookups. 
for (int i = 0; i < M; i++) m[rand()]++;

这种范例通常用于名称-值设置&配置数据、批处理等。10倍(或更高)的查找/插入比率是传统哈希图的组成部分<&燃气轮机;非常适合这种手术。

这可以很容易地分成两半,分别是插入阶段和查找阶段,在并行世界中,这两半之间可能有一些“刷新队列”操作。更困难的是交错插入+查找版本:

hash_map<int, int> m; 

for (int i = 0; i < N; i++) { 
   if (rand() % LOOKUP_RATIO == 0) 
     hash_map[rand()]++;  // "lookup" 
   else 
     hash_map[rand()] = rand();  // "insert" 
}

在这种情况下,插入可以是异步的,只要插入队列在每次查找之前被刷新,并且如果查找比率足够大(例如,>1000),那么它就变得非常类似于上面的批处理示例,但有一些队列。然而,排队意味着同步原语。

想象一下下面的片段:

hash_map<int,int> a;
hash_map<int,int> b; 
for (int i = 0; i < N; i++) { 
  // the following 2 lines could be executed in parallel 
  a[rand()] = rand(); 
  b[rand()] = rand(); 
}

因此,可以通过以下方式“并行”执行查找:

int lookup(int value) { 
  // The following 2 lines could be executed in parallel: 
  v1 = a[value]; 
  v2 = b[value]; 
  if (v1)  // pseudo code for "value existed in a" 
    return v1; 
  else 
    return v2; 
}

8 回复 | 直到 17 年前

Rob Lachlan 17 年前

问题是共享数据本身就是并行计算的祸根。理想情况下,您希望每个核心处理单独的数据,否则将有与同步相关的开销。(如何在没有共享状态的情况下进行通信?通过消息传递。)

此外,谈论数据结构正在加速也有点奇怪。我发现更自然地谈论正在加速的数据结构上的操作,因为不同数据结构上的不同操作具有不同的特征。您是否希望加快特定类型的访问速度?

编辑,作为对额外细节的回应:我假设目标是拥有一个可以并行访问的单个散列映射,其基础可以是多个散列表,但它将作为单个散列表透明地呈现给此数据结构的用户。当然,我们会担心在锁上花太多时间旋转。在这个级别上,我们还必须注意缓存一致性问题。也就是说,如果内核或处理器具有指向相同数据的单独缓存,并且其中一个修改了数据,那么另一个上的缓存数据将无效。如果这种情况反复发生,可能会带来巨大的成本,并行性可能比在单个内核上运行更糟糕。所以我对共享数据非常谨慎。

我的直觉是拥有一个线程池,每个线程都拥有哈希表的不同部分。散列将首先从键映射到散列表部分,然后映射到该部分内的偏移量。更新将作为消息传递给拥有该哈希表部分的线程。这样,就没有人试图同时修改同一个东西。自然,这在具有异步消息传递并发特性的语言(Erlang)中比在其他语言中更容易实现。

Mike 17 年前

我每天都在处理这个问题。我发现像链表这样的东西真的很有用,因为你可以让你的并行算法的每一个线程构造自己的链表,然后在你完成的时候把它们缝合在一起。只要线程真正独立,几乎没有开销

如果每个线程都有数据数组要使用,我发现为每个线程分配一个较小的数组来处理几乎总是更好的,然后在完成后将小数组合并回主数组-事实上,如果您在集群环境中,甚至不可能使用“同一”数组!

如果您正在为CUDA(GPU)环境编写代码,您将很快了解到,整个世界可以(不,应该!)在操作之前重新构建为一个数组:)

Javier 17 年前

首先,我认为比较不合适 pthread_create() 使用hashmap操作计算时间。在争用和非争用情况下,与(取消)锁定时间相比,效果更好。

不过,您是对的,同步时间是瓶颈,而且越来越糟糕,因为它们必须转到CPU间总线/网桥/通道,而大多数其他数据结构都试图留在缓存中(甚至在卷影寄存器中)。

解决此问题有两个主要方向:

更好的共享结构:检查无锁结构和/或事务性内存。两者都试图通过用“try-check-commit/rollback”替换“lock-modify-release”循环来最大化可访问性。在大多数情况下,检查应该成功,因此回滚不应该影响平均性能。通常,检查/提交是以原子方式完成的,因此它在CPU带宽方面很昂贵,但比传统的锁要少得多。
减少共享:这是erlang/haskell语言所强调的。线程间通信更像是带有参数的函数调用,而不是共享内存,这使得传输小消息变得简单而廉价。这是更具可伸缩性的,因为只有两个进程必须同步,并且(理论上)可以使用具有更低延迟的非RAM通道。

我很惊讶没有人对无锁结构有任何意见。检查 this (pdf)及 this (视频)关于Java中的无锁哈希表实现,它可以(几乎)线性扩展到300个CPU

Tom Ritter 17 年前

我认为您需要查看数据结构并询问“这其中有什么可以异步完成?”

对于很多数据结构,我所看到的几乎没有。

但对于一些更为深奥或使用较少的结构,我敢打赌是有的。我打赌重新平衡某些种类的树木是可以并行的。我打赌遍历图可能是(尽管这可能是算法多于数据结构)。我敢打赌,遍历双链接列表(从每一端)可能会很困难。

Zan Lynx 17 年前

我不相信在一次查找中有太多的并行性。但是,如果您要查找整个项目列表,则情况就不同了。

或者选择一大串要插入的项目。将哈希表划分为每个CPU区域,并划分键列表。然后,每个CPU可以将项目填充到自己的哈希表中。

这也适用于向量、B+树和二叉树,尽管我相信哈希表可以构造为需要稍微少一点的更新锁定。

fjxx 15 年前

请看这篇CACM文章- 多核时代的数据结构 http://cacm.acm.org/magazines/2011/3/105308-data-structures-in-the-multicore-age/fulltext

本文的早期版本如下: http://www.cs.tau.ac.il/~shanir/concurrent-data-structures.pdf

TMN 17 年前

需要考虑的是,每个数据结构都有一个(或一个小的池)线程,并将访问视为“服务”。也就是说,它不会让线程在哈希映射中查找某些内容,而是向为该数据结构提供服务的线程发出同步请求。这将锁定操作本地化(只有为请求提供服务的线程必须知道锁定技术),但可能会使请求队列成为瓶颈。

我认为,正如其他人所说,利用并行性的最佳方法是通过您的算法,而不是数据结构。

twk Mark Adler 17 年前