Independent Spanning Trees on Systems-on-chip Hypercubes Routing

Authors: Eduardo Sant'Ana da Silva, Andre Luiz Pires Guedes, Eduardo Todt

Abstract:

Independent spanning trees (ISTs) provide a number of advantages in data broadcasting. One can cite the use in fault tolerance network protocols for distributed computing and bandwidth. However, the problem of constructing multiple ISTs is considered hard for arbitrary graphs. In this paper we present an efficient algorithm to construct ISTs on hypercubes that requires minimum resources to be performed.

Keywords: Hypercube, Independent Spanning Trees, Networks On Chip, Systems On Chip.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1077705

References:

[1] J. Duarte, E.P., A. Brawerman, and L. Albini, "An algorithm for distributed hierarchical diagnosis of dynamic fault and repair events," in Parallel and Distributed Systems, 2000. Proceedings. Seventh International Conference on, 2000, pp. 299 -306.
[2] A. Zehavi and A. Itai, "Three tree-paths," Journal of Graph Theory, vol. 13, pp. 175-188, 1988.
[3] A. Itai and M. Rodeh, "The Multi-Tree Approach to Reliability in Distributed Networks," Information and Computation, vol. 79, pp. 43- 59, 1984.
[4] J. Cheriyan and S. N. Maheshwari, "Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs," J. Algorithms, vol. 9, no. 4, pp. 507-537, 1988.
[5] K. Obokata, Y. Iwasaki, F. Bao, and Y. Igarashi, "Independent spanning trees of product graphs," in Graph-Theoretic Concepts in Computer Science, ser. Lecture Notes in Computer Science, F. d-Amore, P. Franciosa, and A. Marchetti-Spaccamela, Eds. Springer Berlin / Heidelberg, 1997, vol. 1197, pp. 338-351.
[6] A. Huck, "Independent Trees in Planar Graphs Independent trees," Graphs and Combinatorics, vol. 15, pp. 29-77, 1999. (Online). Available: http://dx.doi.org/10.1007/s003730050030
[7] Z. Ge and S. L. Hakimi, "Disjoint rooted spanning trees with small depths in deBruijn and Kautz graphs," SIAM Journal on Computing, vol. 26, no. 1, pp. 79-92, 1997. (Online). Available: www.scopus.com
[8] T. Hasunuma and H. Nagamochi, "Independent spanning trees with small depths in iterated line digraphs," Discrete Applied Mathematics, vol. 110, no. 2-3, pp. 189 - 211, 2001. (Online). Available: http://www.sciencedirect.com/science/article/pii/S0166218X00002699
[9] S.-M. Tang, Y.-L. Wang, and Y.-H. Leu, "Optimal Independent Spanning Trees on Hypercubes," J. Inf. Sci. Eng., vol. 20, no. 1, pp. 143-156, 2004.
[10] J.-S. Yang, S.-M. Tang, J.-M. Chang, and Y.-L. Wang, "Parallel construction of optimal independent spanning trees on hypercubes," Parallel Comput., vol. 33, no. 1, pp. 73-79, 2007.
[11] J.-S. Yang, J.-M. Chang, and H. Chan, "Independent Spanning Trees on Folded Hypercubes," Parallel Architectures, Algorithms, and Networks, International Symposium on, vol. 0, pp. 601-605, 2009.
[12] A. A. Rescigno, "Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security," Information Sciences, vol. 137, no. 1-4, pp. 259 - 276, 2001. (Online). Available: http://www.sciencedirect.com/science/article/pii/S0020025501001219
[13] S.-M. Tang, J.-S. Yang, Y.-L. Wang, and J.-M. Chang, "Independent Spanning Trees on Multidimensional Torus Networks," IEEE Transactions on Computers, vol. 59, pp. 93-102, 2010.
[14] J.-S. Yang, J.-M. Chang, S.-M. Tang, and Y.-L. Wang, "On the independent spanning trees of recursive circulant graphs g(cdm,d) with d┬┐2," Theoretical Computer Science, vol. 410, no. 21-23, pp. 2001 - 2010, 2009. (Online). Available: http://www.sciencedirect.com/science/article/pii/S0304397508009122
[15] ARM, "AMBA Specification and Multilayer AHB specification (rev2.0)," http://www.arm.com/armtech/AXI/.
[16] IBM, "CoreConnect Specification," http://www.ibm.com/.
[17] Sonics, "SMART interconnect," http://www.sonicsinc.com/.
[18] "Wishbone Specification," http://www.opencores.org/wishbone/.
[19] "Altera Avalon Interface Specification," http://www.altera.com/.
[20] L. Benini and G. D. Micheli, "Networks on Chips: A New SoC Paradigm," Computer, vol. 35, pp. 70-78, 2002.
[21] F. Karim, A. Nguyen, and S. Dey, "An interconnect architecture for networking systems on chips," Micro, IEEE, vol. 22, no. 5, pp. 36 - 45, sep/oct 2002.
[22] J. Owens, W. Dally, R. Ho, D. Jayasimha, S. Keckler, and L.-S. Peh, "Research Challenges for On-Chip Interconnection Networks," Micro, IEEE, vol. 27, no. 5, pp. 96 -108, sept 2007.
[23] A. Hemani, T. Meincke, S. Kumar, A. Postula, T. Olsson, P. Nilsson, J. Oberg, P. Ellervee, and D. Lundqvist, "Lowering power consumption in clock by using globally asynchronous locally synchronous design style," in Design Automation Conference, 1999. Proceedings. 36th, 1999, pp. 873 -878.
[24] K. Srinivasan, K. Chatha, and G. Konjevod, "Linear-programming-based techniques for synthesis of network-on-chip architectures," Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, vol. 14, no. 4, pp. 407 -420, april 2006.