VECTORIZATION OF TREE TRAVERSALS

A simple method for vectorizing tree searches, which operates by processing all relevant nodes at the same depth in the tree simultaneously, is described. This procedure appears to be general, assuming that gather-scatter operations are vectorizable, but is most efficient if the traversals proceed monotonically from the root to the leaves, or vice versa. Particular application is made to the hierarchical tree approach for computing the self-consistent interaction of N bodies. It is demonstrated that full vectorization of the requisite tree searches is feasible, resulting in a factor ∼4-5 improvement in cpu efficiency in the traversals on a CRAY X-MP. The overall gain in the case of the Barnes-Hut tree code algorithm is a factor ∼2-3, implying a net speed-up of ≈400-500 on a CRAY X-MP over a VAX 11/780 or SUN 3/50. © 1990.