Independent Spanning Trees on Systems-on-chip Hypercubes Routing
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:60696", author = "Eduardo Sant'Ana da Silva and Andre Luiz Pires Guedes and Eduardo Todt", title = "Independent Spanning Trees on Systems-on-chip Hypercubes Routing", 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.", volume = "7", number = "3", pages = "402-4", }
