Abstract
OTIS (Optical Transpose Interconnection System) optoelectronic architecture is an attractive high-speed interconnection network. As a continuation for the research work performed on OTIS, this paper investigates broadcast and global combine communication operations on the promising all-port wormhole-routed OTIS-Mesh using the Extended Dominating Node (EDN) approach, referred to as EDN-OTIS-Mesh. The performance of broadcast and global combine operations is evaluated, both analytically and by simulation, in terms of the number of communication steps, latency, and latency improvement. A comparative study is conducted among three interconnection networks’ architectures: the single-port wormhole-routed OTIS-Mesh, all-port wormhole-routed OTIS-Mesh, and all-port wormhole-routed EDN-OTIS-Mesh. The obtained analytical and simulation results show that the broadcast and global combine operations on all-port EDN-OTIS-Mesh significantly outperform the single-port and all-port OTIS-Mesh.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Duato, J., Yalamanchili, C., Ni, L.: Interconnection Networks: An Engineering Approach. IEEE Computer Society Press, Los Alamitos (1997)
Trobec, R., Brostnik, U., Janezic, D.: Communication performance of d-meshes in molecular dynamics simulation. J. Math. Chem. 45(2), 503–512 (2009)
Park, S.-Y., Hariri, S.: A high performance message-passing system for network of workstations. J. Supercomput. 11(2), 159–180 (1997)
Park, S.-Y., Hariri, S.: ACS: An adaptive communication system for heterogeneous wide-area ATM clusters. Clust. Comput. 2(3), 229–246 (1999)
Marsden, G., Marchand, P., Harvey, P., Esener, S.: Optical transpose interconnection system architectures. Opt. Lett. 18(13), 1083–1085 (1993)
Tsai, Y., McKinley, P.: An extended dominating nodes to collective communication in wormhole-routed 2D meshes. In: Proceedings of the IEEE Scalable High Performance Computing Conference, pp. 199–206, TN (1994)
Tsai, Y., McKinley, P.: An extended dominating node approach to broadcast and global combine in multiport wormhole-routed mesh networks. IEEE Trans. Parallel Distrib. Syst. 8(1), 41–58 (1997)
Tsai, Y., McKinley, P.: A dominating set model for broadcast in all-port wormhole-routed 2D mesh networks. In: Proceedings of the Eighth ACM International Conference on Supercomputing, pp. 126–135, England (1994)
McKinley, P., Tsai, Y., Robinson, D.: Collective communication in wormhole-routed massively parallel computers. Computer 28(12), 39–50 (1995)
Hartmann, O., Kühnemann, M., Rauber, T., Rünger, G.: An adaptive extension library for improving collective communication operations. Concurr. Comput.: Pract. Exp. 20(10), 1173–1194 (2008)
Mahafzah, B., Jaradat, B.: The load balancing problem in OTIS-Hypercube interconnection networks. J. Supercomput. 46(3), 276–297 (2008)
Matsuda, M., Kudoh, T., Kodama, Y., Takano, R., Ishikawa, Y.: The design and implementation of MPI collective operations for clusters in long-and-fast networks. Clust. Comput. 11(1), 45–55 (2008)
Pjesivac-Grbovic, J., Angskun, T., Bosilca, G., Fagg, G., Gabriel, E., Dongarra, J.: Performance analysis of MPI collective operations. Clust. Comput. 10(2), 127–143 (2007)
Kenyon, C., Schabanel, N.: The data broadcast problem with non-uniform transmission times. Algorithmica 35(2), 146–175 (2008)
Dvorak, V.: Communication performance of mesh- and ring-based NoCs. In: Seventh International Conference on Networking (ICN 2008), pp. 156–161 (2008)
Chen, Y.-S., Chiang, C.-Y., Chen, C.-Y.: Multi-node broadcasting in all-ported 3-D wormhole-routed torus using an aggregation-then-distribution strategy. J. Syst. Archit. 50(9), 575–589 (2004)
Barnett, M., Payne, D., Van de Geijn, R., Watts, J.: Broadcasting on meshes with wormhole routing. J. Parallel Distrib. Comput. 35(2), 111–122 (1996)
Shang, W., Yao, F., Wan, P., Hu, X.: On minimum m-connected k-dominating set problem in unit disc graphs. J. Comb. Optim. 16(2), 99–106 (2008)
Krishnamoorthy, A., Marchand, P., Kiamilev, F., Esener, S.: Grain-size considerations for optoelectronic multistage interconnection networks. Appl. Opt. 31(26), 5480–5507 (1992)
Najaf-abadi, H., Sarbazi-azad, H.: An empirical comparison of OTIS-mesh and OTIS-hypercube multicomputer systems under deterministic routing. In: Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05), Workshop 14, vol. 15 (2005)
Zhao, C., Xiao, W., Qin, Y.: Hybrid diffusion schemes for load balancing on OTIS-Networks. In: Proceedings of the 7th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP), China, 2007. Lecture Notes in Computer Science, vol. 4494, pp. 421–432. Springer, Berlin (2007)
Qin, Y., Xiao, W., Zhao, C.: GDED-X schemes for load balancing on heterogeneous OTIS-networks. In: Proceedings of the 7th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP), China, 2007. Lecture Notes in Computer Science, vol. 4494, pp. 482–492. Springer, Berlin (2007)
Zhao, C., Xiao, W., Parhami, B.: Load-balancing on swapped or OTIS networks. J. Parallel Distrib. Comput. 69(4), 389–399 (2009)
Najaf-abadi, H., Sarbazi-azad, H.: Comparative evaluation of adaptive and deterministic routing in the OTIS-hypercube. In: Proceeding of Ninth Asia-Pacific Computer Systems Architecture Conference (ACSAC 2004), Beijing, China. Lecture Notes in Computer Science, vol. 3189, pp. 349–362. Springer, Berlin (2004)
Day, K., Al-Ayyoub, A.: Topological properties of OTIS-networks. IEEE Trans. Parallel Distrib. Syst. 13(4), 359–366 (2002)
Wei, W., Xiao, W.: Algorithms of basic communication operation on the biswapped network. In: Proceedings of the 8th International Conference on Computational Science (ICCS 2008), Part I, Krakow, Poland, 2008. Lecture Notes in Computer Science, vol. 5101, pp. 347–354. Springer, Berlin (2008)
Day, K.: Optical transpose k-ary n-cube networks. J. Syst. Archit. 50(11), 697–705 (2004)
Wang, C., Sahni, S.: Basic operations on the OTIS-mesh optoelectronic computer. IEEE Trans. Parallel Distrib. Syst. 9(12), 1226–1236 (1998)
Rajasekaran, S., Sahni, S.: Randomized routing, selection, and sorting on the OTIS-mesh. IEEE Trans. Parallel Distrib. Syst. 9(9), 833–840 (1998)
Wilkinson, B.: Computer Architecture Design and Performance, 2nd edn. Prentice Hall, New York (1996)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mahafzah, B.A., Tahboub, R.Y. & Tahboub, O.Y. Performance evaluation of broadcast and global combine operations in all-port wormhole-routed OTIS-Mesh interconnection networks. Cluster Comput 13, 87–110 (2010). https://doi.org/10.1007/s10586-009-0117-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10586-009-0117-8