Show simple item record

dc.contributor.advisor Hirschberg, Daniel S.
dc.creatorKumar, Manoj
dc.date.accessioned 2018-12-18T21:25:10Z
dc.date.available 2018-12-18T21:25:10Z
dc.date.issued 1981
dc.identifier.urihttps://hdl.handle.net/1911/104542
dc.description.abstract An algorithm is presented to merge two subfiles of size n/2 each, stored in the left and the right halves of a linearly-connected processor array, in 3n/2 route steps and log n compare-exchange steps. This algorithm is extended to merge two horizontally adjacent subfiles of size mXn/2 each, stored in an mXn mesh-connected processor array in row-major order, in m+2n route steps and log mn compare-exchange steps. These algorithms are faster than their counterparts proposed so far. Next, an algorithm is presented to merge two vertically aligned subfiles, stored in a mesh-connected processor array in row-major order. Finally, a sorting scheme is proposed that requires lln route steps and 2 log n compare-exchange steps to sort n elements stored in an nXn mesh-connected processor array. The previous best sorting algorithm requires 14 n route steps ( for practical values of n, 4 < n 512 ).
dc.format.extent 56 pp
dc.language.iso eng
dc.title An efficient implementation of Batcher's odd-even merge algorithm and its application in parallel sorting schemes
dc.identifier.digital RICE2177
dc.contributor.committeeMember Sinclair, James B.;Jump, J. Robert
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Electrical Engineering
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Masters
thesis.degree.name Master of Science
dc.format.digitalOrigin reformatted digital
dc.identifier.callno THESIS E.E. 1981 KUMAR
dc.identifier.citation Kumar, Manoj. "An efficient implementation of Batcher's odd-even merge algorithm and its application in parallel sorting schemes." (1981) Master’s Thesis, Rice University. https://hdl.handle.net/1911/104542.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record