Title :
Fundamental data movement algorithms for reconfigurable meshes
Author :
Olariu, Stephan ; Schwing, James L. ; Zhang, Jingyuan
Author_Institution :
Dept. of Comput. Sci., Old Dominion Univ., Norfolk, VA, USA
Abstract :
A number of data movement algorithms for the two-dimensional reconfigurable mesh are presented. These include computing the prefix sum of a binary sequence and computing the prefix maxima of a sequence of real numbers. These algorithms lead to a fast algorithm to sort a sequence of n reals in O(log n/log m) time on a reconfigurable mesh of size mn*n with 3>
Keywords :
computational complexity; computational geometry; parallel algorithms; reconfigurable architectures; sorting; binary sequence; convex hull; data movement algorithms; prefix maxima; prefix sum; real numbers; reconfigurable meshes; sorting; Arithmetic; Binary sequences; Broadcasting; Computer science; Concurrent computing; Multiprocessor interconnection networks; Parallel algorithms; Parallel machines; Sorting; Very large scale integration;
Conference_Titel :
Computers and Communications, 1992. Conference Proceedings., Eleventh Annual International Phoenix Conference on
Conference_Location :
Scottsdale, AZ, USA
Print_ISBN :
0-7803-0605-8
DOI :
10.1109/PCCC.1992.200593
