Tree machines and divide-and-conquer algorithms

A tree machine consists of a number of processors (each with its own memory) mutually connected via communication branches so as to form a binary tree. Two processors may communicate only via a common communication link. Such a tree machine is a completely general, concurrent processing engine and can be used for problems decomposed in a hierarchical way. Implementation of divide-and-conquer algorithms on a tree machine is discussed. Algorithms for which a tree machine can be effective are characterized. Examples are shown and it is proven that for a class of k-dimensional divide-and-conquer algorithms the running time may be reduced from 0(N logk−1 N) on a sequential machine to 0(kN) on a tree machine