PARALLEL ORGANIZATION OF THE BISECTION ALGORITHM

A parallel organization for recursive bisection type algorithms is presented. The transformation to parallel form is illustrated with reference to the determination of the eigenvalues of a symmetric matrix. The parallel form requires (a) infrequent synchronization and (b) relatively few data transfers between the processors executing the algorithm and thus is ideally suited for execution on Multiple Instruction Multiple Data (MIMD) type parallel computers. The performance of the algorithm is classified in a system independent manner so that users can predict its efficiency for most parallel computers. This classification into (i) potential speedup with varying numbers of processor (ii) overheads arising from synchronization and (iii) overheads arising from data transfer can be made without running the algorithm on a computer. The algorithm was tested on a two processor MIMD system at Loughborough University.