The OTIS hyper hexa-cell optoelectronic architecture. (English) Zbl 1239.90013
Summary: Optical transpose interconnection system (OTIS) is an optoelectronic architecture that promises to be a great choice for future-generation parallel systems. OTIS combines the advantages of electronic and optical links, where electronic links are used for short distances which require low material cost, and optical links are used for long distances which provide high speed network with low power consumption. Taking into account the advantageous characteristics of OTIS and based on the attractive properties of hyper hexa-cell (HHC) interconnection topology from low diameter and good minimum node degree, this paper introduces a new optoelectronic architecture referred to as OTIS hyper hexa-cell (OHHC). This paper also provides an evaluation and a comparison of the new topology with OTIS-mesh in terms of the following topological properties: size, diameter, maximum and minimum node degree, bisection width, total cost and optical cost. The results of this study proved the excellence of the proposed OHHC over OTIS-mesh in terms of diameter, minimum node degree, bisection width, and optical cost.
MSC:
| 90B10 | Deterministic network models in operations research |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
optoelectronic architectures; OTIS networks; interconnection networks; topological propertiesReferences:
| [1] | El-Rewini H, Abd-El-Barr M (2005) Advanced computer architecture and parallel processing. Wiley, New York |
| [2] | Grama A, Gupta A, Karypis G, Kumar V (2003) Introduction to parallel computing. Addison Wesley, Reading · Zbl 0861.68040 |
| [3] | Patterson D, Hennessy J (2009) Computer organization and design: the hardware/software interface. Morgan Kaufmann, Boston · Zbl 1213.68005 |
| [4] | Chen Y-J, Horng S-J (1997) Medial axis transform on mesh-connected computers with hyperbus broadcasting. Computing 59(2): 95–114 · Zbl 0889.68154 · doi:10.1007/BF02684474 |
| [5] | Verdoscia L, Vaccaro R (1999) An adaptive routing algorithm for WK-recursive topologies. Computing 63(2): 171–184 · Zbl 0979.68503 · doi:10.1007/s006070050057 |
| [6] | Marsden G, Marchand P, Harvey P, Esener S (1993) Optical transpose interconnection system architecture. Opt Lett 18(13): 1083–1085 · doi:10.1364/OL.18.001083 |
| [7] | Zane F, Marchand P, Paturi R, Esener S (2000) Scalable network architectures using the optical transpose interconnection system (OTIS). J Parallel Distrib Comput 60(5): 521–538 · Zbl 0969.68649 · doi:10.1006/jpdc.2000.1627 |
| [8] | Day K, Al-Ayyoub A (2002) Topological properties of OTIS-networks. IEEE Trans Parallel Distrib Syst 13(4): 359–366 · doi:10.1109/71.995816 |
| [9] | Parhami B (2005) Swapped interconnection networks: topological, performance, and robustness attributes. J Parallel Distrib Comput 65(11): 1443–1452 · Zbl 1101.68349 · doi:10.1016/j.jpdc.2005.05.002 |
| [10] | Coudert D, Ferreira A, Muñoz X (2000) Topologies for optical interconnection networks based on the optical transpose interconnection system. Appl Opt 39(17): 2965–2974 · doi:10.1364/AO.39.002965 |
| [11] | Melhem R (2007) Low diameter interconnections for routing in high-performance parallel systems. IEEE Trans Comput 56(4): 502–510 · Zbl 1368.94193 · doi:10.1109/TC.2007.1004 |
| [12] | Sahni S, Wang C-F (1997) BPC permutations on the OTIS-mesh optoelectronic computer. In: Proc 4th int conf on massively parallel processing using optical interconnections (MPPOI’97), Montreal, Canada, 22–24 June, pp 130–135 |
| [13] | Hashemi-Najafabadi H, Sarbazi-Azad H (2005) An empirical comparison of OTIS-mesh and OTIS-hypercube multicomputer systems under deterministic routing. In: Proc 19th IEEE int parallel and distributed processing symposium (IPDPS’05), Washington, DC, USA, 4–8 April, p 262a |
| [14] | Rajasekeran S, Sahni S (1998) Randomized routing, selection, and sorting on the OTIS-mesh. IEEE Trans Parallel Distrib Syst 9(9): 833–840 · doi:10.1109/71.722217 |
| [15] | Lucas K, Jana P (2010) Sorting and routing on OTIS-mesh of trees. Parallel Process Lett 20(2): 145–154 · Zbl 1519.68067 · doi:10.1142/S0129626410000119 |
| [16] | Lucas K (2010) Parallel enumeration sort on OTIS-hypercube. IC3 (1):21–31 · Zbl 1213.68691 |
| [17] | Lucas K (2009) Parallel algorithm for sorting on OTIS-ring of computer. In: Proc of the 2nd Bangalore annual compute conference (COMPUTE ’09), Bangalore, India, 9–10 January. ACM, New York, pp 1–5 |
| [18] | Lucas K, Jana P (2010) Parallel algorithms for finding polynomial roots on OTIS-torus. J Supercomput 54(2): 139–153 · doi:10.1007/s11227-009-0312-7 |
| [19] | Lucas K, Mallick D, Jana P (2008) Parallel algorithm for conflict graph on OTIS-triangular array. In: Lecture notes in computer science, vol 4904. Springer, Heidelberg, pp 274–279 · Zbl 1131.68586 |
| [20] | Lucas K (2009) Parallel algorithm for prefix computation on OTIS k-ary n-cube parallel computer. Int J Recent Trends Eng 1(1): 560–562 |
| [21] | Wang C-F (1998) Algorithms for the OTIS optoelectronic computer. PhD thesis, Department of Computer Science, University of Florida, Florida, USA |
| [22] | Wang C-F, Sahni S (1998) Basic operations on the OTIS-mesh optoelectronic computer. IEEE Trans Parallel Distrib Syst 9(12): 1226–1236 · doi:10.1109/71.737698 |
| [23] | Wang C-F, Sahni S (2001) Matrix multiplication on the OTIS-mesh optoelectronic computer. IEEE Trans Comput 50(7): 635–646 · doi:10.1109/12.936231 |
| [24] | Mahafzah B, Jaradat B (2008) The load balancing problem in OTIS-hypercube interconnection networks. J Supercomput 46(3): 276–297 · doi:10.1007/s11227-008-0191-3 |
| [25] | Zhao C, Xiao W, Parhami B (2009) Load-balancing on swapped or OTIS networks. J Parallel Distrib Comput 69(4): 389–399 · doi:10.1016/j.jpdc.2009.01.002 |
| [26] | Mahafzah B, Tahboub R, Tahboub O (2010) Performance evaluation of broadcast and global combine operations in all-port wormhole-routed OTIS-mesh interconnection networks. Clust Comput 13(1): 87–110 · doi:10.1007/s10586-009-0117-8 |
| [27] | Hashemi-Najafabadi H, Sarbazi-Azad H (2007) Mathematical performance modelling of adaptive wormhole routing in optoelectronic hypercubes. J Parallel Distrib Comput 67(9): 967–980 · Zbl 1125.68335 · doi:10.1016/j.jpdc.2007.04.012 |
| [28] | Abdullah M, Abuelrub E, Mahafzah B (2011) The chained-cubic tree interconnection network. Int Arab J Inf Technol 8(3): 334–343 |
| [29] | Day K, Tripathi A (1994) A comparative study of topological properties of hypercubes and star graphs. IEEE Trans Parallel Distrib Syst 5(1): 31–38 · doi:10.1109/71.262586 |
| [30] | Latifi S, Zheng S-Q (1995) Determination of Hamiltonian cycles in cube-based networks using generalized gray codes. Comput Electr Eng 21(3): 189–199 · doi:10.1016/0045-7906(95)00001-B |
| [31] | Mahafzah B, Jaradat B (2010) The hybrid dynamic parallel scheduling algorithm for load balancing on chained-cubic tree interconnection networks. J Supercomput 52(3): 224–252 · doi:10.1007/s11227-009-0288-3 |
| [32] | Saad Y, Schultz M (1988) Topological properties of hypercubes. IEEE Trans Comput 37(7): 867–872 · doi:10.1109/12.2234 |
| [33] | Hayes J, Mudge T, Stout Q, Colley S, Palmer J (1986) Architectures of a hypercube supercomputer. In: Proc 1986 int conf on parallel processing (ICPP’86), PA, USA, August. IEEE Computer Society Press, pp 653–660 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
