Title :
An Efficient Parallel Sorting Algorithm on OTIS Mesh of Trees
Author :
Lucas, Keny T. ; Jana, Prasanta K.
Author_Institution :
Dept. of Inf. Manage., Xavier Inst. of Social Service, Ranchi
Abstract :
OTIS (Optical Transpose Interconnection System) is popular model of optoelectronic parallel computers. This is a hybrid interconnection network using electronic and optical communication channels. In the recent years, many parallel algorithms for various numeric and non-numeric computations have been developed on these networks. In this paper, we propose a parallel algorithm for sorting N (=n2) data elements on an OTIS model of parallel computers, called OTIS-mesh of trees. Our algorithm is based on sparse enumeration sort (Horowitz et al., 2002) and shown to run in 4.5 log N electronic moves + 5 OTIS moves.
Keywords :
mesh generation; multiprocessor interconnection networks; parallel algorithms; parallel machines; sorting; trees (mathematics); OTIS mesh-of-trees; electronic communication channel; hybrid interconnection network; optical communication channel; optical transpose interconnection system; optoelectronic parallel computer; parallel sorting algorithm; Computer networks; Computer science; Concurrent computing; Conference management; Multiprocessor interconnection networks; Optical computing; Optical fiber communication; Optical interconnections; Parallel algorithms; Sorting; OTIS; enumeration sort; interconnection network; parallel algorithm; time complexity;
Conference_Titel :
Advance Computing Conference, 2009. IACC 2009. IEEE International
Conference_Location :
Patiala
Print_ISBN :
978-1-4244-2927-1
Electronic_ISBN :
978-1-4244-2928-8
DOI :
10.1109/IADCC.2009.4809002
