Browse Prior Art Database

Parallel Algorithms for a Fixed Number of Processors

IP.com Disclosure Number: IPCOM000039175D
Original Publication Date: 1987-Apr-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 3 page(s) / 26K

Publishing Venue

IBM

Related People

Meyer auf der Heide, F: AUTHOR [+2]

Abstract

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.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

Parallel Algorithms for a Fixed Number of Processors

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. Since a heap of size n never has more than log n levels, there are precisely enough processors to manage every level. Each processor stores in its memory the contents of the nodes at its level, with each nonempty node containing a value. So long as some instruction is available, the network begins processing a new instruction at each time unit. If a POP instruction is being processed, P0 outputs the contents of its (unique) node and determines the new value to be stored in the root by querying P1 . As the POP travels down the tree, one level per unit time, Pi knows which node at level i has moved up to level i-1. Therefore, Pi can pass on the necessary information to Pi+1 so that only the immediate children of the missing node are considered when deciding which node to move from level i+1 to level i. When a PUSH instruction is being implemented, the value being PUSHed is input to P0, which compares the new value with the value currently stored in the root. If the new value is larger than the current value, the two are swapped and the current value is passed to P1; otherwise, the new value is passed to P1 . As the PUSH moves down the tree, the value being PUSHed might change, with each new value being smaller than the previous one. To assure that th...