矢量化（SIMD）樹操作

Question

什麼都在向量化樹操作的一些提示/指針？內存佈局明智的，聰明的算法，等等

一些特定領域的東西：

• 每個父節點將有相當多的（20 - 200）子節點。
• 每個節點具有子節點的概率很低。
• 樹上的操作大多是有條件的散步。
• 走在樹的性能比插入/刪除/搜索速度更重要。

Answer 1

當心，這很難實現。去年，英特爾，甲骨文和UCSC的團隊提出了一個驚人的解決方案"FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs"。他們贏得了"Best Paper Award 2010" by ACM SIGMOD。

Answer 2

由於樹的隨機性，如何進行矢量化行爲對你來說是一大利好，這並不明顯。

我會打好樹明爲（parentId的，節點數據）「節點」項目，通過的parentid排序的平面數組，這樣你就可以在節點的孩子至少參觀在一起。當然，如果你的樹不「肥」（即，一個節點的平均孩子數量低），這並不會給你太多。

你最好的賭注，雖然是真的只是強調對SIMD的蠻力，因爲你真的無法通過您的列表這個API做花哨的隨機跳躍。

編輯：我不會扔出去的正常樹類，你極有可能不過，實現SIMD方式，看看你是否真正得到什麼，我不相信你會... ...

Answer 3

怎麼樣使用頻譜圖論算法？他們應該很容易矢量化，因爲他們處理矩陣。