Jen-Chih Lin1 , Steven K.C. Lo1 , Shih-Jung Wu This email address is being protected from spambots. You need JavaScript enabled to view it.2 and Huan-Chao Keh2
1Department of Information Management, Jin-Wen Institute of Technology, Taipei, Taiwan 231, R.O.C. 2Department of Information Science & Information Engineering, Tamkang University, Tamsui, Taiwan 251, R.O.C.
Received: June 10, 2005 Accepted: September 30, 2005 Publication Date: June 1, 2006
The Incrementally Extensible Hypercube (IEH) is a generalization of interconnection network that is derived from the hypercube. Unlike the hypercube, the IEH can be constructed for any number of nodes. That is, the IEH is incrementally expandable. In this paper, the problem of embedding and reconfiguring ring structures is considered in an IEH with faulty nodes. There are a novel embedding algorithm proposed in this paper. The embedding algorithm enables us to obtain the good embedding of a ring into a faulty IEH with unbounded expansion, and such the result can be tolerated up to O(n*⌊log2m⌋) faults with congestion 1, load 1, and dilation 4. The presented embedding methods are optimized mainly for balancing the processor loads, while minimizing dilation and congestion as far as possible.
Keywords: Incrementally Extensible Hypercube (IEH), Fault-Tolerant, Embedding, Linear Array, Ring
REFERENCES
[1] Armstrong, J. R. and Gray, F. G., “Fault Diagnosis in a Boolean n Cube Array of Microprocessors,” IEEE Trans. on Computers, Vol. 30, pp. 587590 (1981).
[2] Day, K. and Al-Ayyoub, A. E., “Fault Diameter of k-ary n-cube Networks,” IEEE Trans. on parallel and distributed systems, Vol. 8, pp. 903907 (1997).
[3] Jen-Chih Lin, “Simulation of Cycles in the IEH Graph,” International Journal of Hjgh Speed Computing, Vo1. 10, pp. 327342 (1999).
[4] Lin, J. C. and Keh, H. C, “Reconfiguration of Complete Binary Trees in Full IEH Graphs and Faulty Hypercubes,” International Journal of High performance computing Applications, Vo1. 15, pp. 5563 (2001).
[5] Lin, J. C and Hsien, N. C., “Reconfiguring Binary Tree Structures in a Faulty Supercube with Unbounded Expansion,” Parallel Computing, Vo1. 8, pp. 471 483 (2002).
[6] Lin, J. C. and Lo, S. K. C., “Embedding Complete Binary Trees into Faulty Flexible Hypercubes with Unbounded Expansion” Informatica, Vol. 27, pp. 7580 (2003).
[7] Rennels, D. A., “On Implemanting Fault-tolerance in Binary Hypercubes,” Proc. 16th Inter. Symp. on Faulttolerant Computing, pp. 344349 (1986).
[8] Yang, P. J., Tien, S. B. and Raghavendra, C. S., “Embedding of Rings and Meshes onto Faulty Hypercube Using Free Dimensions,” IEEE Trans. on Computers, Vol. 43, pp. 608618 (1994).
[9] Hastad, J., Leighton, T. and Newman, M., “Reconfiguring a Hypercube in the Presence of Faults,” Proc. of 19th ACM Conf. on Theory of Computing, pp. 274284 (1987).
[10] Akers, S. B. and Krishnamurthy, B., “A Group-Theoretic Model for Symmetric Interconnection Networks,” IEEE Trans. on Computers, Vol. 38, pp. 555 565 (1989).
[11] Hayes, J. P. and Mudge, T. N., “Hypercube Supercomputing,” Proc. IEEE, Vol. 77, pp. 18291842 (1989).
[12] Saad, Y. and Schultz, M., “Topological Properties of Hypercube,” IEEE Trans. on Computers, Vol. 37, pp. 867871 (1988).
We use cookies on this website to personalize content to improve your user experience and analyze our traffic. By using this site you agree to its use of cookies.
