Chinese, Simplified 字幕

← cs344_unit4_23_l_快速分类

埋め込みコードを取得する
2言語

Showing Revision 3 created 05/12/2013 by Michael Xiao.

  1. 我们最后要讨论的排序算法是串行处理器中最有效算法之一;
  2. 这就是快速排序。由于算法的控制复杂性,
    它在GPU上是更复杂的一种算法
  3. 所以让我们回顾一下快速排序算法是干什么的。
  4. 第一,它从它的输入中选择一个主元素,一个特定元素,
  5. 然后,它将把它输入中的所有元素和主元素比较,
  6. 然后它使用这种比较把输入分为3个子数组。
  7. 那些比主元素小的,那些等于主元素的,那些大于
  8. 主元素的,然后它对每子数组调用快速排序,
  9. 持续运行直到整个输入被排序。
  10. 作为一个例子,让我们看看某特定阵列,选择主元素等于3,
  11. 所以我们这里要做的就是将这些元素中的每个元素和主元素比较。
  12. 接着我们要决定它们是否等于、 大于或小于主元素。
  13. 然后我们会把它划分为3个数组,那些小于主元素的,
  14. 那些等于主元素的,和那些大于主元素的,
  15. 然后我们会对这些数组的每个调用快速排序,进行同样的操作。
  16. 所以当我们有 2 和 1,让我们假设我们选择 2 作为主元素,
  17. 然后我们会将这划分为小于和等于主元素。
  18. 这并不需要递归因为它仅有一个单个元素。
  19. 让我们假设我们在这里选择 4 作为主元素,这是大于主元素的,这是等于主元素的,
  20. 而现在我们有一个完全排序的数组。
  21. 所以在 GPU 上执行这个算法是非常具有挑战性的。
  22. 我们已经看到的其他算法描述起来很简单,而且他们也不递归。
  23. 这一个更加复杂,并且直到最近,GPU也根本不支持递归。
  24. 事实上,我们在这节课中使用的 GPU 目前不支持递归。
  25. 我们怎么可以采取这种看似只有递归的算法
    并借助我们已经学过的原语将它映射到GPU呢?
  26. 为此,我提及这个例子有两个原因。
  27. 第一是你已经学会了在GPU上执行快速分类的所需的所有东西。
  28. 第二点,激发以本机方式支持递归的 GPU 新功能的好处。
  29. 所以我们可以通过使用分段的概念来实现不需要递归的快速排序。
  30. 记得分段的操作,像扫描,只在单个段内执行 ;
  31. 一个分段的操作不会影响其他分段。
  32. 这听起来有点像递归,但事实上它以一个相似的方式来映射。
  33. 对于快速排序,当我们开始处理初始数组,
  34. 我们将使用分发、 映射和压缩来最终将其分成 3 段。
  35. 我们可以使用分段的扫描来做这些必要的操作来实现它,
  36. 包括在分段内分发一个主元素用于比较,和拆分一个段,
  37. 这是与我们在基数排序时拆分一个特定的位的方式相似。
  38. 快速排序很有趣因为它向你展示了分段多么有用,
  39. 他们可以让你镜像你在递归过程使用的相同方法,而不必实际使用递归。
  40. 但是,在这里我必须坦白,
  41. 去实现它真的是一个挑战,同样,更快地执行也是一个挑战。
  42. 所以这是非常令人兴奋的,最新的视频GPU支持一个更灵活的编程模型,该模型内核可以实际调用,
  43. 可以启动其他内核,这让快速分类的递归调用变得更加简单。
  44. 我们在本课中不使用这一新功能。
  45. 我们的代码正在其上运行的亚马逊实例目前没有这些支持新功能的新GPU,
  46. 但它真的很令人兴奋的,所以当我们进入到第7单元,
  47. 我们将看看它到底是什么样的和它如何应用于快速排序。