Vettorializzazione (SIMD) Funzionamento dell'albero

Question

Quali sono alcuni suggerimenti/indicatori generali per vettorizzare le operazioni dell'albero? layout di memoria saggio, algoritmo di saggio, ecc

Alcuni dominio cose specifiche:

• Ogni nodo padre avrà un bel po '(20 - 200) nodi figlio.
• Ogni nodo ha una bassa probabilità di avere nodi figlio.
• Le operazioni sull'albero sono per lo più passeggiate condizionali.
• Le prestazioni di passaggio sull'albero sono più importanti delle velocità di inserimento/eliminazione/ricerca.

Answer 1

Attenzione, questo è molto difficile da implementare. L'anno scorso un team di Intel, Oracle e UCSC ha presentato una straordinaria soluzione "FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs". Hanno vinto il "Best Paper Award 2010" by ACM SIGMOD.

Answer 2

A causa della natura casuale degli alberi non è immediatamente evidente come le vettovaglie in viaggio sarebbero un grande vantaggio per voi.

Disporrei l'albero come una matrice piatta di elementi "nodo" (genitore, dati nodo), ordinati per parentid, in modo da poter visitare almeno i figli di un nodo insieme. Naturalmente questo non ti dà molto se il tuo albero non è "grasso" (cioè un basso numero di bambini in media per un nodo).

La soluzione migliore è in realtà solo per enfatizzare la forza bruta di SIMD, perché con questa API non è possibile eseguire salti casuali di fantasia nell'elenco.

Edit: non vorrei buttare via il normale classe di albero è molto probabile che, però, implementare il modo SIMD e vedere se davvero guadagna nulla, non sto convinto si vuole ...

Answer 3

E che dire degli algoritmi di teoria del grafico spettrale? Dovrebbero essere molto facili da vettorializzare, dato che si occupano di matrici.