Parallel Algorithms for a Fixed Number of Processors
Original Publication Date: 1987-Apr-01
Included in the Prior Art Database: 2005-Feb-01
The first of two proposed algorithms maintains a heap on a chain or circular network having a fixed number of processors. In this algorithm, the address of a node of the heap can be accessed without the use of pointers, and any algorithm for a heap of n elements must maintain the conditions that (1) the root of each subtree contains a maximal element of that subtree, and (2) if the heap is capable of containing up to n elements at one time, then the number of levels of the heap never exceeds log n. In a network of log n processors, P0, ..., P(log n)-1, which is configured as a chain with P0 receiving all input, processor Pi is assigned the management of level i of the heap, with the root being at level 0, its children at level 1, and so on.