Chinese, Simplified subtitles

← 链接很糟糕

Get Embed Code
2 Languages

Showing Revision 3 created 05/02/2013 by adeptHanLi.

  1. 那么,让我们来想想在一个并行环境中链接会如何表现。
  2. 为了构造,也即是说我们把许多项放入哈希表,每线程1个。
  3. 我们来查看一下,这就是说我们有很多键可以在哈希表查看。
  4. 同样,每个线程1个。可是链接有两个主要的劣势。第一,
  5. 我们说我们在查看很多项目,每个线程1个,而且我们知道去查
  6. 一个项,我们为这个项计算哈希函数。这种并行方式不错。
  7. 这只是一个运算图。然而更有问题的,是查找排列于哈希桶中的链接。
  8. 所以, 我们在这里有很多线程,每个线程都最终会在
  9. 不同的哈希桶查看。此特殊哈希桶有三个项,线程2的哈希桶
  10. 有2个项,但是线程1的哈希桶有很多,很多个项。
  11. 一些线程,像线程2,可能很快就找到了他们的项目。一些线程,
  12. 像线程1,举个例,可能不得不在一个冗长的链接表访问很多,甚至所有项
  13. 才能找到它的项。因为在Warp算法中的线程,
  14. 是在 Lock帧同步中运行,一个Warp的运行时间完全依赖于在Warp中最慢的查找时间。
  15. 另外一个在Warp中的线程必须等待 直到此最慢
  16. 项被找到,才能运行。而这种行为方式,你可以想象,是糟糕的。