International Journal of Computer Network and Information Security(IJCNIS)

ISSN: 2074-9090 (Print), ISSN: 2074-9104 (Online)

Published By: MECS Press

IJCNIS Vol.10, No.8, Aug. 2018

Parallel Prefix Sum Algorithm on Optoelectronic Biswapped Network Hyper Hexa-cell

Full Text (PDF, 1219KB), PP.27-35

Views:53   Downloads:19


Ashish Gupta, Bikash Kanti Sarkar

Index Terms

Optoelectronic, OTIS mesh, OTIS hyper hexa-cell, Biswapped network hyper hexa-cell


The biswapped network hyper hexa-cell is recently reported optoelectronic network architecture for delivering excellent performance especially for mapping numerical problems which demands frequent routing and broadcasting. This network contains some important benefits such as smaller diameter, higher bisection width, and lower network’s total and optical cost as compared to counter-part OTIS hyper hexa-cell network. It is also advantageous as compared to the traditional biswapped network mesh containing smaller diameter and higher minimum node degree. In this paper, we present a parallel algorithm for mapping prefix sum of 2×(6×2^(d_h-1) )^2 data elements on a dh-dimensional biswapped network hyper hexa-cell of2〖×(6×2^(d_h-1) )〗^2 processors (assuming each processor contain single data element). It demands total ((d_h- 1)×(d_h+ 1))-  ((d_h- 1)×(d_h- 2))/2+ 5d_h + 10 intra-cluster (electronic) and 3 inter-cluster (optical) moves.

Cite This Paper

Ashish Gupta, Bikash Kanti Sarkar,"Parallel Prefix Sum Algorithm on Optoelectronic Biswapped Network Hyper Hexa-cell", International Journal of Computer Network and Information Security(IJCNIS), Vol.10, No.8, pp.27-35, 2018.DOI: 10.5815/ijcnis.2018.08.03


[1]C.F. Wang and S. Sahni, Basic operations on the OTIS mesh optoelectronic computer, IEEE trans on parallel and distributed systems, Vol 9, No 12, 1998. 

[2]Marsden G, Marchand P, Harvey P, Esener S, Optical transpose interconnection system architecture, Opt Lett 18(13):1083–1085, 1993.

[3]Basel A. Mahafzah, Azzam Sleit, ·Nesreen A. Hamad, Elham F. Ahmad, Tasneem M, Abu-Kabeer, The OTIS hyper hexa-cell optoelectronic architecture, Journal of computing, Springer, 2012, 94:411–432.

[4]Wenjun Xiaoa, Behrooz Parhamib*, Weidong Chena, Mingxin Hea and WenhongWeia, Biswapped networks: a family of interconnection architectures with advantages over swapped or OTIS networks, “International Journal of Computer Mathematics”, Vol. 88, No. 13, September 2011, 2669–2684, Taylor and francis.

[5]Wenhong Wei, Qingxia Li, Ming Tao, BSN-mesh and its basic parallel algorithms”, International Journal of Grid and Utility Computing, Vol 6, Issue 3-4, pp 213-220, 2015. 

[6]A. Gupta, B. K. Sarkar, The recursive and symmetrical optoelectronic network architecture: biswapped network hyper hexa-cell, Arabian Journal of Science and Engineering, Mar 2018.

[7]P.K.Jana and B.P.Sinha, “An improved parallel prefix algorithm on OTIS mesh”, Parallel processing letters (World Scientific), pp. 429-440, Vol.16, No. 4, 2006.

[8]Dheeresh K. Mallic, Prasanta K. Jana, In Proc:”Parallel prefix on mesh of trees and OTIS mesh of trees”, PDPTA 08, 2012, Solan, Himanchal Pradesh, India.

[9]K.T.Lukas, “Parallel Algorithm for Prefix Computation on OTIS K-Ary 3-cube parallel computers”, International journal of Recent Trends in  Engineering, Vol. 1, No. 1, May 2009.

[10]P.K. Jana, “Improved parallel prefix computation on optical multi trees”, IEEE INDICON 2004.

[11]S. K. Jha, “An Improved Parallel Prefix Computation on 2D-Mesh Network”, In Proc: International Conference on Computational Intelligence: Modeling Techniques and Applications (CIMTA) 2013, pp. 919-926

[12]S.K.Jha, P.K.Jana, “Fast Parallel Prefix on Multi-Mesh of Trees”, In Proc: IEEE international conference on computer and communication technology, Motilal Nehru National Institute of Technology, Allahabad, 17-19 September 2010, pp: 641-646.

[13]P.K.Jana, B.D.Naidu, S.Kumar, M.arora, B.P.Sinha, “Parallel prefix computation on extended multi-mesh network”, Information processing letters (Elsevier Science), pp, 295-303, Vol, 84, No. 6, Oct 2002.

[14]N Rakesh, N. Nitin, “Parallel Prefix Sum Computation on Multi Mesh of Trees”, In Proc: IEEE INDICON 2009.

[15]A. Datta, Mallika De, B.P. Sinha,”Fast Parallel Algorithm for Prefix Computation in Multi-Mesh Architecture”, Parallel Processing Letters, 2017.

[16]A Gupta, B. K. Sarkar, “A new parallel approach for prefix sum on BSN mesh”, In Proc:Next Generation Computing Technologies, Apr 2016, pp. 393-396, dehradun, uttrakhand, INDIA.