NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
Finding maximum on an array processor with a global busThe problem of finding the maximum of a set of values stored one/processor on an n x n array of processors is analyzed. The array has a time-shared global bus in addition to conventional processor-processor links. A two-phase algorithm for finding the maximum is presented that uses conventional links during the first phase and the global bus during the second. This algorithm is faster than algorithms that use either only the global bus or only the conventional links. Two types of interconnection patterns (the eighth nearest neighbor and the fourth nearest neighbor) are analyzed. In both cases it is shown that the time required to find the maximum using the two-phase algorithm is 0(n to the 2/3-power) assuming the propagation speed of the global bus to be a constant independent of the size of the array. In the case where the propagation speed is logarithmic in the number of processors, the time to find the maximum is 0(/n-squared log n/1/3), for both types of arrays. Extensions to q-dimensional arrays show that the two-phase algorithm is superior for any fixed value of q.
Document ID
19840045554
Acquisition Source
Legacy CDMS
Document Type
Reprint (Version printed in journal)
Authors
Bokhari, S. H.
(University of Engineering and Technology Lahore, Pakistan)
Date Acquired
August 12, 2013
Publication Date
February 1, 1984
Publication Information
Publication: IEEE Transactions on Computers
Volume: C-33
ISSN: 0018-9340
Subject Category
Computer Operations And Hardware
Accession Number
84A28341
Funding Number(s)
CONTRACT_GRANT: NAS1-14472
CONTRACT_GRANT: NAS1-15810
Distribution Limits
Public
Copyright
Other

Available Downloads

There are no available downloads for this record.
No Preview Available