1. 今天我們要看一些代表性的程序，以及這些程序中使用的技術，用于提取并行性和處理我們討論過的問題。主要問題是確保在處理器之間有合理的平衡，并避免由于通信造成的過多開銷。

2. 到目前為止，我們一直在討論并行計算的一般原則，包括執(zhí)行部分和通信部分?，F(xiàn)在我們將使用一些示例來說明一些問題以及它們在不同領域中的解決方法。然后我們將開始討論如何測量和評估系統(tǒng)性能的問題。我們將詳細討論共享內存，因為硬件設計對于理解什么類型的結構可以運行得快，什么類型的結構可能代價高是非常重要的。最后我們將進行考試。

3. 我們今天要看的是來自課程網(wǎng)頁上列出的一本書的海洋模擬，這是一個典型的網(wǎng)格求解問題。我們還將研究星系的建模和演化，以及如何處理不規(guī)則的空間劃分。我們將研究掃描，就像你們在當前作業(yè)的第二部分中所做的那樣，你會發(fā)現(xiàn)它也可以用在第三部分。我們還將從掃描推廣到分段掃描。已經(jīng)學過210的人已經(jīng)接觸過這些想法。我們還將討論射線追蹤和圖形學，以將它們綜合起來。

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

5. 通過構建樹結構和遍歷樹結構可以計算出每個節(jié)點的引力作用。

6. 工作負載不均勻，但通信模式較好。

7. 數(shù)據(jù)在內存中的存儲方式可以隨機化或定期重新分配。

8. SCAN算法可以用于計算數(shù)組的前綴和。

9. 通過二叉樹的優(yōu)化，可以實現(xiàn)最高效的二進制加法。

10. 通過二叉樹的優(yōu)化，可以實現(xiàn)線性數(shù)量的工作。

11. 通過分割數(shù)組和并行計算，可以實現(xiàn)更高效的掃描算法。

12. 使用warp級別的掃描可以最小化計算步驟。

13. 掃描算法可以用于渲染圖像和其他應用領域。

14. 光線追蹤是通過逆向追蹤光線的方向來確定物體的技術。

15. 數(shù)據(jù)結構如Barnes-Hut四叉樹可以用于光線追蹤，以實現(xiàn)空間劃分和跟蹤光線。

16. Packet ray tracing是一種將光線分組并并行處理的技術，以提高效率。

17. 光線追蹤在GPU上的映射存在分歧問題，需要進行周期性的重新分組和重組。

18. 并行計算的挑戰(zhàn)在于選擇合適的數(shù)據(jù)結構和技術來劃分工作、保持負載平衡和通信局部性。