Operaciones de árbol de vectorización (SIMD)

Question

¿Cuáles son algunos consejos/indicadores generales sobre la vectorización de las operaciones de árbol? Diseño de memoria inteligente, sabia algoritmo, etc.

Algunos de dominio cosas específicas:

• Cada nodo padre tendrá un buen número de (20 - 200) nodos hijos.
• Cada nodo tiene una baja probabilidad de tener nodos secundarios.
• Las operaciones en el árbol son principalmente caminatas condicionales.
• El rendimiento de caminar sobre el árbol es más importante que las velocidades de inserción/eliminación/búsqueda.

Answer 1

Cuidado, esto es muy difícil de implementar. El año pasado, un equipo de Intel, Oracle y UCSC presentó una sorprendente solución "FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs". Ganaron el "Best Paper Award 2010" by ACM SIGMOD.

Answer 2

Debido a la naturaleza aleatoria de los árboles, no es inmediatamente obvio cómo vectorizar los paseos sería una gran ventaja para usted.

Me gustaría colocar el árbol como una matriz plana de (parentid, datos de nodo) elementos de "nodo", ordenados por parentid, por lo que al menos puede visitar los elementos secundarios de un nodo. Por supuesto, esto no le da mucho si su árbol no es "gordo" (es decir, un número bajo de niños para un nodo).

Su mejor opción aunque en realidad es sólo para enfatizar en la fuerza bruta de SIMD, porque realmente no se puede hacer saltos al azar de lujo a través de su lista con esta API.

Editar: Yo no tirar el árbol de la clase normal, es muy probable que tenga, sin embargo, poner en práctica la forma SIMD y ver si realmente se gana nada, no estoy convencido de que lo hará ...

Answer 3

¿Qué pasa con el uso de algoritmos de teoría gráfica de espectro? Deberían ser mucho más fáciles de vectorizar, ya que tratan con matrices.