| Two Papers on a Tree-Structured Parallel Computer. (2002) | |||||||||
Abstract | |||||||||
| This report consists of two papers describing various aspects of a new tree-structured parallel computer. The first paper, 'A tree machine for searching problems' by J. L. Bentley and H. T. Kung, describes the basic architecture of the machine. A set of N elements can be maintained on an N-processor version of the machine such that insertions, deletions, queries and updates can all be processed in 2 lg N time units. The queries can be very complex, including problems arising in ordered set manipulation, data bases, and statistics. The machine is pipelined so that M successive operations can be performed in M-1 + 2 lg N time units. The paper studies both the basic machine structure and a VLSI implementation of the machine. The second paper, 'A parallel algorithm for constructing minimum spanning trees' by J. L. Bentley, shows how an (N/lg N)-processor version of the machine can solve the problem of constructing minimum spanning trees in time proportional to N lg N. This algorithm is an improvement over existing algorithms in several ways. (Author). Sponsored in part by Grant NSF-MCS78-23676. | |||||||||
Details der Publikation | |||||||||
| |||||||||