Title :
Prefix computation using a segmented bus
Author :
Li, Y. ; Zheng, S.Q.
Author_Institution :
Dept. of Comput. Sci., Louisiana State Univ., Baton Rouge, LA, USA
fDate :
31 Mar-2 Apr 1996
Abstract :
Prefix computation is a fundamental problem in parallel computing. The authors consider prefix computation on a new bus-based parallel architecture, the segmented bus system. The authors show that prefix computation on N elements can be carried out in O(N/p+log p) time using a segmented bus that connects p processors. This algorithm can be generalized to k-dimensional meshes connected by segmented buses with the same performance
Keywords :
computational complexity; parallel algorithms; parallel architectures; system buses; O(N/p+log p) time; bus-based parallel architecture; k-dimensional meshes; parallel computing; prefix computation; segmented bus; Binary trees; Broadcasting; Computer science; Concurrent computing; Hypercubes; Parallel architectures; Parallel processing; Processor scheduling; Sorting; Switches;
Conference_Titel :
System Theory, 1996., Proceedings of the Twenty-Eighth Southeastern Symposium on
Conference_Location :
Baton Rouge, LA
Print_ISBN :
0-8186-7352-4
DOI :
10.1109/SSST.1996.493540
