International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 14, No. 1, 8 Feb. 2022
Cover page and Table of Contents: PDF (size: 472KB)
Optimized Parallel Counting Sort Algorithm for Distinct Numeric Values on Biswapped Hyper Hexa-Cell Optoelectronic Network
Full Text (PDF, 472KB), PP.69-80
Views: 0 Downloads: 0
Author(s)
Ashish Gupta
1,*
Index Terms
Optoelectronic, Biswapped, Parallel Algorithm, Hyper Hexa-Cell, Counting Sort
Abstract
The optoelectronic Biswapped-Hyper Hexa-Cell is a recently reported recursive and a symmetrical architecture of Biswapped Family. This symmetrical network has claimed and proved to be advantageous in terms of network diameter, bisection width, minimum node-degree and network cost compared to its counterpart architecture of OTIS family named ‘OTIS Hyper Hexa-Cell’ and traditional grid-based architecture of Biswapped family named ‘Biswapped-Mesh’. In this paper, we present a novel and efficient parallel algorithm for counting sort for sorting distinct numeric values on dh-dimensional Biswapped-Hyper Hexa-Cell optoelectronic network. The parallel algorithm demands 10d_h+12+ log_2〖S_A 〗 electronic and 10 optical moves, where SA is the size of count array: Acip[SA], and SA equals to maximal minus minimal numeric value plus one. On the basis of analysis, it is concluded that proposed algorithm delivers better performance since speedup and efficiency improved for worst case scenario (difference between maximal and minimal data values becomes larger) with the increase of only few communication moves required for sorting.
Cite This Paper
Ashish Gupta, "Optimized Parallel Counting Sort Algorithm for Distinct Numeric Values on Biswapped Hyper Hexa-Cell Optoelectronic Network", International Journal of Computer Network and Information Security(IJCNIS), Vol.14, No.1, pp.69-80, 2022. DOI: 10.5815/ijcnis.2022.01.06
Reference
[1] W. D. Hills, G. L. Steele, Data parallel algorithm, Communications of the ACM, vol. 29, no. 12, pp. 1170-1183.
[2] G. Marsden, P. Marchand, P. Harvey, S. Esener, Optical transpose interconnection system architecture, Opt. Lett. vol. 18, no.13, pp.1083–1085, 1993.
[3] W. Xiao, B. Parhami, W. Chena, Ma Hea and W. Wei. Biswapped networks: a family of interconnection architectures with advantages over swapped or OTIS networks, International Journal of Computer Mathematics, vol. 88, no. 13, pp. 2669–2684, 2012.
[4] B. A. Mahafzah, A. Sleit, A. Nesreen. E. F. Hamad. Ahmad, Tasneem M, Abu-Kabeer. The OTIS hyper hexa-cell optoelectronic architecture, Journal of computing, vol. 94, pp. 411–432, 2012.
[5] W. Wei, Q. Li and M. Tao. BSN-mesh and its basic parallel algorithms. International Journal of Grid and Utility Computing, vol. 6, no. 3-4, pp. 213-220, 2015.
[6] C. Zhao. Efficient load balancing on biswapped networks. Cluster Computing, vol. 17, no. 2, pp. 403-411, 2014.
[7] S. Ling and W. Chen. Node-to-Set Disjoint Paths in Biswapped Networks. The computer journal. vol. 57, no. 7, pp. 953-967, 2014.
[8] W. Chen and S. Ling, Node-pancyclic properties of biswapped networks based on cycles in their factor networks. The Computer Journal. vol. 60, no. 1, pp.1-12, 2017.
[9] A. Gupta A and B. K. Sarkar, The recursive and symmetrical optoelectronic network architecture: Biswapped network hyper hexacell. Arabian Journal of Science and Engineering. vol. 43, no. 12, pp. 7635-7653, 2018.
[10] A. Gupta and B. K. Sarkar. Biswapped-Torus Network-A new efficient Node-Symmetrical Optoelectronic Network. National Academy Science Letters. 2020; Online First.
[11] A. Gupta and B. K. Sarkar. BSN MOT: A Fast and Cost-efficient Optoelectronic Architecture. IETE Technical Review. 2010; Online First.
[12] A. Datta, M. De and B. P. Sinha, Fast Parallel Algorithm for Prefix Computation in Multi-Mesh Architecture, Parallel Processing Letters. vol. 27, pp. 1750009-1-1750009-12, 2017.
[13] P.K. Jana, B. D. Naidu, S. Kumar, M. Arora and B. P. Sinha, Parallel Prefix Computation on Extended Multi-Mesh Network. Information Processing Letters. vol. 84, pp. 295-303, 2002.
[14] Ashish Gupta and Bikash Kanti Sarkar, A new parallel approach for prefix sum on BSN mesh, Proc. 2nd Int. Conf. on Next Generation Computing Technologies (Dehradun, Uttrakhand, 2016).
[15] Ashish Gupta, Bikash Kanti Sarkar,"Parallel Prefix Sum Algorithm on Optoelectronic Biswapped Network Hyper Hexa-cell", International Journal of Computer Network and Information Security, Vol.10, No.8, pp.27-35, 2018.
[16] A. Gupta and B. K. Sarkar, Parallel Algorithm for LaGrange’s Interpolation on BSN-Mesh, In Proc. Int. Conf. Intelligent Communication, Control and Devices, (Dehradun, 2016), pp. 673-682.
[17] A. Gupta and B. K. Sarkar, An efficient parallel approach for mapping binomial series (special cases) on biswapped network mesh. In Proc. Smart and Innovative trends in next generation computing technologies (Dehradun, 2018), pp. 263-275.
[18] A. Al-Adwan, B.A. Mahafzah, and A. Sharieh, Solving traveling salesman problem using parallel repetitive nearest neighbor algorithm on OTIS-Hypercube and OTIS-Mesh optoelectronic architectures. J Supercomput. vol. 74, pp. 1–36, 2018.
[19] A. Al-Adwan, A. Sharieh and B. A Mahafzah, Parallel heuristic local search algorithm on OTIS hyper hexa-cell and OTIS mesh of trees optoelectronic architectures. Appl Intell. vol 49, pp. 661–688, 2019.
[20] A. Al-Adwan, R. Zaghloul, B. A. Mahafzah, A. Sharieh, Parallel quicksort algorithm on OTIS hyper hexa-cell optoelectronic architecture. Journal of Parallel and Distributed Computing. vol. 141, pp. 61-73, 2020.
[21] Volodymyr Lytvynenko, Olena Kryvoruchko, Irina Lurie, Nataliia Savina, Oleksandr Naumov, Mariia Voronenko, "Comparative Studies of Self-organizing Algorithms for Forecasting Economic Parameters", International Journal of Modern Education and Computer Science, Vol.12, No.6, pp. 1-15, 2020.
[22] Yajnaseni Dash, Sanjay Kumar, V.K. Patle,"Evaluation of Performance on Open MP Parallel Platform based on Problem Size", International Journal of Modern Education and Computer Science, Vol.8, No.6, pp.35-40, 2016.
[23] Peng Zeng,Zhong-Shan Deng,Jing Liu,"Parallel Algorithms for Freezing Problems during Cryosurgery", International Journal of Information Engineering and Electronic Business, vol.3, no.2, pp.11-19, 2011.