DocumentCode :
1679655
Title :
A O(√N) time sorting algorithm for the mesh connected architecture
Author :
Elgindy, Hossam
Author_Institution :
Sch. of Comput. Sci., McGill Univ., Montreal, Que., Canada
fYear :
1991
Firstpage :
950
Abstract :
The use of data duplication in systolic architectures to improve the computational time of problems constrained by a large information flow is studied. Its use is demonstrated by presenting an efficient algorithm for sorting N items on a mesh connected computer of N processors. The algorithm has an O(N1/3 log N) running time and requires the use of O(N2/3) memory locations per processor
Keywords :
computational complexity; parallel algorithms; sorting; computational time; data duplication; information flow; memory locations; mesh connected architecture; mesh connected computer; sorting algorithm; systolic architectures; Algorithm design and analysis; Broadcasting; Computer architecture; Computer networks; Computer science; Data flow computing; Digital audio players; Indexing; Parallel algorithms; Sorting;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Electrotechnical Conference, 1991. Proceedings., 6th Mediterranean
Conference_Location :
LJubljana
Print_ISBN :
0-87942-655-1
Type :
conf
DOI :
10.1109/MELCON.1991.161999
Filename :
161999
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=1679655
بازگشت