009-【CMU15-418】【并行计算架构和编程】【中英字幕】【Paralle

1. 今天我们要看一些代表性的程序，以及这些程序中使用的技术，用于提取并行性和处理我们讨论过的问题。主要问题是确保在处理器之间有合理的平衡，并避免由于通信造成的过多开销。

2. 到目前为止，我们一直在讨论并行计算的一般原则，包括执行部分和通信部分。现在我们将使用一些示例来说明一些问题以及它们在不同领域中的解决方法。然后我们将开始讨论如何测量和评估系统性能的问题。我们将详细讨论共享内存，因为硬件设计对于理解什么类型的结构可以运行得快，什么类型的结构可能代价高是非常重要的。最后我们将进行考试。

3. 我们今天要看的是来自课程网页上列出的一本书的海洋模拟，这是一个典型的网格求解问题。我们还将研究星系的建模和演化，以及如何处理不规则的空间划分。我们将研究扫描，就像你们在当前作业的第二部分中所做的那样，你会发现它也可以用在第三部分。我们还将从扫描推广到分段扫描。已经学过210的人已经接触过这些想法。我们还将讨论射线追踪和图形学，以将它们综合起来。

4. 使用聚合信息可以提高计算效率。

5. 通过构建树结构和遍历树结构可以计算出每个节点的引力作用。

6. 工作负载不均匀，但通信模式较好。

7. 数据在内存中的存储方式可以随机化或定期重新分配。

8. SCAN算法可以用于计算数组的前缀和。

9. 通过二叉树的优化，可以实现最高效的二进制加法。

10. 通过二叉树的优化，可以实现线性数量的工作。

11. 通过分割数组和并行计算，可以实现更高效的扫描算法。

12. 使用warp级别的扫描可以最小化计算步骤。

13. 扫描算法可以用于渲染图像和其他应用领域。

14. 光线追踪是通过逆向追踪光线的方向来确定物体的技术。

15. 数据结构如Barnes-Hut四叉树可以用于光线追踪，以实现空间划分和跟踪光线。

16. Packet ray tracing是一种将光线分组并并行处理的技术，以提高效率。

17. 光线追踪在GPU上的映射存在分歧问题，需要进行周期性的重新分组和重组。

18. 并行计算的挑战在于选择合适的数据结构和技术来划分工作、保持负载平衡和通信局部性。