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

fYear

2009

fDate

6-7 March 2009

Firstpage

175

Lastpage

180

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 (=n²) 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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/IADCC.2009.4809002

Filename

4809002