- 简介
- Quicksort 简史
- GPU-Quicksort 简介
- OpenCL 1.2 中的 GPU-Quicksort
- 将 GPU-Quicksort 转为 OpenCL 2.0
- 教程要求
- 运行教程
- 总结
- 参考资料
- 关于作者
- 下载代码
简介
本教程展示了如何使用 OpenCL™ 2.0 的两个强大特性： enqueue_kernel 函数，支持您排列设备中的 kernel；work_group_scan_exclusive_add 和 work_group_scan_inclusive_add，两个添加至 OpenCL 2.0 的工作组函数，可方便扫描并减少对工作组工作项的操作。 本教程通过在 OpenCL 中实施我们自己的 GPU-Quicksort 来展示了这些特性，据我们所知，这是该算法在 OpenCL 中的首次实施。 本教程展示了一种重要的尺寸 1 NDRange 的排队 kernel 的设计模式，以执行之前为 CPU 保留的管理和调度操作。
在本教程中，您将了解如何使用面向 OpenCL 的英特尔® 工具。 面向 OpenCL™ 应用的英特尔® SDK 是专为英特尔® 架构上的 OpenCL 应用而提供的一个开发环境。 除 SDK 外，英特尔® VTune™ Amplifier XE 也能帮助分析和优化 CPU 和 GPU 上英特尔平台上的应用，并且还支持 OpenCL。 如欲了解面向 OpenCL 的英特尔工具的更多信息，请访问 http://intel.com/software/opencl。
在此感谢 Deepti Joshi、Allen Hux、Aaron Kunze、Dillon Sharlet、Adam Lake、Michal Mrozek、Ben Ashbaugh、Ayal Zaks、Yuri Kulakov、Joseph Wells、Lynn Putnam、Jerry Baugh、Jerry Makare 和 Chris Davis 在编写、审核和出版这篇文章、附带代码和编辑视频方面为我提供的帮助。 同时感谢我的妻子 Ellen 和孩子 Michael 和 Celine 对我的坚定支持与理解。
Quicksort 简史
Quicksort 是 C.A.R. (“Tony”) Hoare 在 1960 年尚在莫斯科国立大学就读时发明的一套算法。 Tony Hoare 是概率论专业研究生，指导教授为 A.N. Kolmogorov。 在皇家海军服役期间，Hoare 学习了俄语(他的叔叔是皇家海军上校)。 在研究语言机器翻译的问题时，Hoare 曾尝试按升序来排列听到的每个俄语句子中的单词。 Quicksort 算法的基本理念是围绕主元要排序的序列(主元可通过不同的方式从序列中选择)，所有小于主元的元素放到数组的左侧，所有大于主元的元素放到数组的右侧，所有等于主元的元素放到数组中间。 数组被分割后，序列的左侧和右侧将再次应用 Quicksort 算法。
