Abstract
Mesh of trees (MOT) is well known for its small diameter, high bisection width, simple decomposability and area universality. On the other hand, OTIS (Optical Transpose Interconnection System) provides an efficient optoelectronic model for massively parallel processing system. In this paper, we present OTIS-MOT as a competent candidate for a two-tier architecture that can take the advantages of both the OTIS and the MOT. We show that an \(n^{4}_{-}\) processor OTIS-MOT has diameter 8log n ∗+1 (The base of the logarithm is assumed to be 2 throughout this paper.) and fault diameter 8log n+2 under single node failure. We establish other topological properties such as bisection width, multiple paths and the modularity. We show that many communication as well as application algorithms can run on this network in comparable time or even faster than other similar tree-based two-tier architectures. The communication algorithms including row/column-group broadcast and one-to-all broadcast are shown to require O(log n) time, multicast in O(n 2log n) time and the bit-reverse permutation in O(n) time. Many parallel algorithms for various problems such as finding polynomial zeros, sales forecasting, matrix-vector multiplication and the DFT computation are proposed to map in O(log n) time. Sorting and prefix computation are also shown to run in O(log n) time.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agostino SD (2006) Lossless image compression by block matching on a mesh of trees. In: Proc of data compression conference, p 443
Akl SG (1989) The design and analysis of parallel algorithms. Prentice Hall, Englewood Cliffs
Balkan AO, Qu G, Vishkin U (2009) Mesh-of-trees and alternative interconnection networks for single-chip parallelism. IEEE Trans Very Large Scale Integr (VLSI) Syst 17:141–1432
Balkan AO, Qu G, Vishkin U (2006) A mesh-of-trees interconnection network for single-chip parallel processing. In: Proc of intl conf on application-specific systems, architectures and processors, pp 73–80
Balkan AO, Michael NH, Qu G, Vishkin U (2007) Layout-accurate design and implementation of a high-throughput interconnection network for single-chip parallel processing. In: Proc of the 15th IEEE symposium on high-performance interconnects, pp 21–28
Cormen TH, Leiserson CE, Rivest RL (1999) Introduction to algorithms. Prentice Hall of India, New Delhi
Cosnard M, Fraigniaud P (1990) Finding the roots of a polynomial on an MIMD multicomputer. Parallel Comput 15:75–85
Das D, De M, Sinha BP (1999) A new network topology with multiple meshes. IEEE Trans Comput 68:536–551
Day K et al (2002) Topological properties of OTIS-networks. IEEE Trans Parallel Distrib Syst 13:359–366
Day K (2004) Optical transpose k-ary n-cube networks. J Syst Archit 50:697–705
Durand E (1960) Solutions numeriques des equations algebriques. Mason, Paris. Tome I
Efe K (1996) Mesh-connected trees: a bridge between grids and meshes of trees. IEEE Trans Parallel Distrib Syst 7:1281–1291
Freeman TL (1989) Calculating polynomial zeros on local memory parallel computer. Parallel Comput 12:351–358
Freeman TL, Bane MK (1991) A synchronous polynomial zero-finding algorithms. Parallel Comput 17:673–681
Hildebrand FB (1956) Introduction to numerical analysis. McGraw-Hill, New Work
Hussain HM, Prasanna VK (1994) Efficient parallel computation on the reduced mesh of trees organization. J Parallel Distrib Comput 20:121–135
Jana PK (2006) Polynomial interpolation and root finding on OTIS-mesh. Parallel Comput 32:301–312
Jana PK (2004) Multi-mesh of trees with its parallel algorithms. J Syst Archit 50:193–206
Jana PK, Sinha BP (2006) An improved parallel prefix algorithm on OTIS-mesh. Parallel Process Lett 16:429–440
Jana PK, Sinha BP (1997) Fast parallel algorithms for forecasting. Comput Math Appl 34:39–49
Lee Y, Horng S, Kao T (1997) Parallel computation of the Euclidean distance transform on the mesh of trees and the hypercube computer. Comput Vis Image Underst 68:109–119
Leighton FT (1992) Introduction to parallel algorithms and architectures: array, trees and hypercubes. Morgan Kaufman, San Mateo
Lucas KT, Mallick DK, Jana PK (2008) Parallel algorithm for conflict graph on OTIS triangular array. In: Lecture notes in computer science, vol 4904. Springer, Heidelberg, pp 274–279
Lucas KT, Jana PK (2009) An efficient parallel sorting algorithm on OTIS mesh of trees. In: Proc of IEEE intl advance comp conf, 6–7 March, 2009, Patiala, India, pp 175–180
Lucas KT, Jana PK (2010) Sorting and routing on OTIS-Mesh of trees. Parallel Process Lett 20:145–154
Mallick DK, Jana PK (2008) Parallel prefix on mesh of trees and OTIS mesh of trees. In: Proc of the intl conf on parallel and distributed processing techniques and appl, Las Vegas, Nevada, USA, pp 359–364
Marrakchi Z, Mrabet H, Masson C, Mehrez H (2007) Efficient mesh of tree interconnect for FPGA architecture. In: Proc of the intl conf on field-programmable technology, pp 269–272
Marrakchi Z, Mrabet H, Masson C, Mehrez H (2007) Mesh of tree: unifying mesh and MFPGA for better device performances. In: Proc. of the 1st intl symposium on networks-on-chip, pp 243–252
Marsden GC, Marchand PJ, Harvey P, Esener SC (1993) Optical transpose interconnection system architectures. Opt Lett 18:1083–1085
Nath D, Maheshwari SN, Bhatt PCP (1983) Efficient VLSI networks for parallel processing based on orthogonal trees. IEEE Trans Comput C-32:569–581
Parhami B (2005) Swapped interconnection networks: topological, performance and robustness attributes. J Parallel Distrib Comput 65:1443–1452
Parhami B (2005) The Hamiltonicity of swapped networks built of Hamiltonian component networks. Inform Process Lett 19:441–445
Rajasekaran S, Sahni S (1998) Randomized routing, selection and sorting on the OTIS-mesh optoelectronic computer. IEEE Trans Parallel Distrib Syst 9:833–840
Sahni S, Wang CF (1997) BPC permutation on the OTIS-mesh optoelectronic computer. In: Proc of the 4th intl conf massively parallel processing using optical interconnections, pp 130–135
Sahni S (2001) Models and algorithms for optical and optoelectronic parallel computers. Int J Found Comput Sci 12:249–264
Salinger P, Tvrdik P (2002) Broadcasting in all-output-port mesh of trees with distance-insensitive switching. J Parallel Distrib Comput 62:1272–1294
Salinger P, Tvrdık P (2002) Optimal broadcasting and gossiping in one-port meshes of trees with distance-insensitive routing. Parallel Comput 28:627–647
Sinha BP, Bandyopadhyay S (2004) OMULT: an optical interconnection system for parallel computing. In: Proc of the intl conf on computers and devices for comm, Jan 1–3, 2004, Kolkata, India
Wang CF, Sahni S (2001) Matrix multiplication on the OTIS-mesh optoelectronic computer. IEEE Trans Comput 50:635–646
Wang CF, Sahni S (1998) Image processing on the OTIS-mesh optoelectronic computer. IEEE Trans Parallel Distrib Syst 11:97–109
Wang CF, Sahni S (1998) Basic operations on the OTIS-mesh optoelectronic computer. IEEE Trans Parallel Distrib Syst 12:1226–1236
Wang CF, Sahni S (1998) OTIS optoelectronic computers. In: Li K, Pan Y, Zhang SQ (eds) Parallel computation using optical interconnections. Kluwer Academic, Dordrecht
Wheelwright SC, Makridakis S (1980) Forecasting methods for management. Wiley, New York
Zane F, Marchand P, Paturi R, Esener S (2000) Scalable network architectures using the optical transpose interconnection system (OTIS). J Parallel Distrib Comput 60:521–538
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Jana, P.K., Mallick, D.K. OTIS-MOT: an efficient interconnection network for parallel processing. J Supercomput 59, 920–940 (2012). https://doi.org/10.1007/s11227-010-0479-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11227-010-0479-y