We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Estimation of Execution Time and Speedup for Bitonic Sorting in Sequential and Parallel Enviroment

by Megha Jain, Sanjay Kumar, V.k Patle
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 122 - Number 19
Year of Publication: 2015
Authors: Megha Jain, Sanjay Kumar, V.k Patle
10.5120/21811-5139

Megha Jain, Sanjay Kumar, V.k Patle . Estimation of Execution Time and Speedup for Bitonic Sorting in Sequential and Parallel Enviroment. International Journal of Computer Applications. 122, 19 ( July 2015), 32-35. DOI=10.5120/21811-5139

@article{ 10.5120/21811-5139,
author = { Megha Jain, Sanjay Kumar, V.k Patle },
title = { Estimation of Execution Time and Speedup for Bitonic Sorting in Sequential and Parallel Enviroment },
journal = { International Journal of Computer Applications },
issue_date = { July 2015 },
volume = { 122 },
number = { 19 },
month = { July },
year = { 2015 },
issn = { 0975-8887 },
pages = { 32-35 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume122/number19/21811-5139/ },
doi = { 10.5120/21811-5139 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:11:23.330929+05:30
%A Megha Jain
%A Sanjay Kumar
%A V.k Patle
%T Estimation of Execution Time and Speedup for Bitonic Sorting in Sequential and Parallel Enviroment
%J International Journal of Computer Applications
%@ 0975-8887
%V 122
%N 19
%P 32-35
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The Batcher`s bitonic sorting algorithm is one of the best parallel sorting algorithms, for sorting random numbers in modern parallel machines. Load balancing property of bitonic sorting algorithm makes it unique among other parallel sorting algorithms. Contribution of bitonic sorting algorithm can be seen in various scientific and engineering applications. Research on a bitonic sorting algorithm has been reported by various researchers in order to improve up the performance of initial batcher`s bitonic sorting algorithm. In this paper, time estimation of bitonic sort algorithm is done in both sequential as well as in parallel domain.

References
  1. Toshio nakatani, Shing-tsaan huang, Bruce W. Arden, and Satish K. Tripath. " K-Way Bitonic Sort ". IEEE Transactions on computers, VOL. 38, NO. 2, FEBRUARY 1989, page no. 283-288, 0018-9340.
  2. Stephan Olariu, Member, IEEE, M. Cristina Pinotti, Member, IEEE Computer Society, and Si Qing Zheng, Senior Member, IEEE. " An Optimal Hardware-Algorithm for Sorting Using a Fixed-Size Parallel Sorting Device ". IEEE Transactions on computers, VOL. 49, NO. 12, December 2000, page no. 1310-1324, 0018-9340.
  3. Yong Cheol Kim, Minsoo Jeon, Dongseung Kim Andrew Sohn. " Communication-Efficient Bitonic Sort on a Distributed Memory Parallel Computer* ". Parallel and Distributed Systems, 2001. ICPADS 2001. Proceedings. Eighth International Conference of 2001, page no. 165-170, 0-7695-1 153-8.
  4. John Harkins, Tarek El-Ghazawi, Esam El-Araby, Miaoqing Huang. " Performance of Sorting Algorithms on the SRC 6 Reconfigurable Computer ". Field-Programmable Technology, 2005. Proceedings. 2005 IEEE International Conference on 11-14 dec. 2005, page no. 295-296, 0-7803-9407-0.
  5. David Nassimi and Sartaj sahini. " Bitonic Sort on a Mesh-Connected Parallel Computer ". IEEE transactions on computer, VOL. c-27, NO. 1, January 1979, page no. 2-7, 0018-9340.
  6. Xie Hongwei Xue Yafeng. " An improved parallel sorting algorithm for odd sequence ". 2008 International Conference on Advanced Computer Theory and Engineering. ICACTE 08, on 20-22 Dec. 2008, page no. 356-360, 978-0-7695-3489-3.
  7. Gianfranco bilardi, Student member, IEEE, and FRANCO P. PREPARATA, FELLOW, IEEE . " An Architecture for Bitonic Sorting with Optimal VLSI Performance". IEEE TRANSACTIONS ON COMPUTERS. VOL c-33, NO. 7, JUILY 1984, page no. 646-651.
  8. J. Angermeier, E. Sibirko, R. Wanka, and J. Teich . " Bitonic Sorting on Dynamically Recon?gurable Architectures* "Parallel & Distributed Processing Workshops and PhD Forum, 2011 IEEE International Symposium on 16-20 May 2011, page no. 314-317, 1530-2075.
  9. Fiaz Gul Khan, Omar Usman Khan, Bartolomeo Montrucchio, Paolo Giaccone . " Analysis of Fast Parallel Sorting Algorithms for GPU Architectures' " . 2011 Frontiers of Information Technology, on 19-21 Dec, page no. 173-178,978-1-4673-0209-8.
  10. Zehra YILDIZ, Musa AYDIN, Güray YILMAZ . " Paralleization of Bitonic sort and radix sort algorithms on many core GPUS ". Electronics, Computer and Computation(ICECCO), 2013 International Conference on 7-9 Nov. 2013, page no. 326-329, 978-1-4799-3343-3.
  11. Majed 2. Al-Hajery and Kenneth E. Batcher " ON The Role Of K-Bits Bitonic Sorting Network In Multicast Routing* ". Parallel and Distributed Processing, 1994. Proceedings. Sixth IEEE Symposium on 26-29 Oct 1994, on 706-714 page, 0- 8186-6427-4/94.
  12. Jae-Dong Lee and Kenneth E. Batcher. " A Bitonic Sorting Network with Simpler Flip Interconnections". Parallel Architectures, Algorithms, and Networks, 1996. Proceedings, Second International Symposium on 12-14 Jun 1996, page no. 104-109, 1087-4089.
  13. Hongin Choi, Kenneth E. Batcher. " Fault Detection in Bitonic Sorting Networks". Parallel and Distributed Processing. 1995. Proceedings. seventh IEEE Symposium on 25-18 Oct 1995, page no. 266-270, 1063-6374.
  14. Jae-dong Lee and Kenneth E. Batcher. " Minimizing Communication of a Recirculating Bitonic Sorting Network ". Parallel Processing, 1996. Vol 3. Software, In the Proceeding 1 996 International Conference on Parallel Processing. At 12-16 Aug 1996, page no. 251-254 Vol 1, 0190-3918.
  15. Jae-Dong Lee and Kenneth E. Batcher. " Minimizing Communication in the Bitonic Sort ". Parallel and Distributed Systems, IEEE Transactions on, Vol. 11, NO. 5, May 2000, page no. 459-474, 1045-9219.
  16. Stanley J. Simmons. " A Bitonic-Sorter based VLSI implementation of the M-Algorithm". IEEE Pacific Rim Conference on Communications, Computers and Signal Processing June 1st - 2nd, 1989, page no. 337-340.
  17. Susumu Horiguchi Issei Numata Masayuki Kimura. " Self-Reconfigurable Algorithm of WSI Sorting Network ". In the Proceeding I991, Third International Conference on Wafer Scale Integration, on 29-31 Jan 1991, page no. 249-255. 0-8186-9126-3.
  18. Donna Quammen and Pearl Y. Wang " Bitonic Sorting on 2D-PEC: An Algorithmic Study on a Hierarchy of Meshes Network ". Parallel Processing Symposium, 1994 . Proceedings. , Eighth International, on 26-19 Apr 1994, page no. 418-423, 0-8186-5602-6.
  19. Taoufik Dachraou, Lata Narayanan *" Fast Deterministic Sorting on Large Parallel Machines ". Parallel and Distributed Processing, 1996. , Eighth IEEE Symposium on 23-26 Oct 1996, page no. 273-280, 0-8186-7683-3.
  20. Mihai Florin Ionescu and Klaus E. Schauser . " Optimizing Parallel Bitonic Sort ". Parallel Processing Symposium, 1997 . Proceedings. , Eleventh International in 1-5 Apr, page no. 303-309, 1063-7133,0-8186-7793-7.
  21. Hagen Peters, Ole Schulz-Hildebrandt, Norbert Luttenberge. " A novel sorting algorithm for many-core architectures based on adaptive bitonic sort ". 2012 IEEE 26th International Parallel and Distributed Processing Symposium, page no. 227-237.
  22. Megha Jain, Sanjay Kumar, V. K. Patle ," Bitonic Sorting Algorithm", IJCA, Volume 113-No. 13, March 2015.
  23. Sorting Networks. https://mitpress. mit. edu/sites/default/ files/Chapter%2027. pdf.
Index Terms

Computer Science
Information Sciences

Keywords

Parallel Algorithm Parallel Sorting algorithm Bitonic Sort Sorting Network OpenMP.

Powered by PhDFocusTM