On subcube dependability in a hypercube

Abstract

In this paper, we present an analytical model for computing the dependability of hypercube systems. The model, referred to as task-based dependability (TBD), is developed under the assumption that a task needs at least an m-cube (m < n) in an n-cube for its execution. Two probabilistic terms are required for computing this dependability. The first is the probability of any x nodes working out of 2ⁿ nodes. The second term is a conditional probability that at least a connected m-cube exists among those x working nodes. This term is computed using a recursive expression. Two dependability measures, reliability and availability, are analyzed in this paper. A combinatorial enumeration is used in the reliability analysis, and a machine repairman model is used in the availability analysis to find the first probability. The machine repairman model is modified to capture imperfect coverage and imprecise repair. The TBD model is also extended to find multitask dependability. Numerical results are presented for n-cubes with different task requirements and are validated through extensive simulation. It is observed that an m-cube requirement is highly restrictive compared to the simple 2^m-connected node requirement.

References

1. 1 Y. Saad and M. H. Schultz, "Topological Properties of Hypercube," IEEE Trans. on Computers, Vol. (2-37, July 1988, pp. 867--872.
2. 2 B. Becket and H. U. Simon, "ttow robust is the ncube?," Proc. 27th Annual Symp. on Foundations Computer Sci., Oct. 1986, pp. 283-291.
3. 3 L. N. Bhuyan a.Jld D. 1~. Agrawa, l, "(~enera.lized ltypercube and Hypcrbua Structures for a Computer Network," IEEE Trans. on Computers, Apr. 1984, pp. 323-333.
4. 4 W. Najjar and J. L. Gaudiot, "Reliability and Performance Modeling of ttypercube Based Multiprocessor," 2nd Int. Workshop on Applied Mathematics and Performance/Reliability Models for Computer Communication Systems, Italy, May 1987.
5. 5 J. Kim, C. R. Das, Woei Lin, and T. Y. Feng, "Reliability Evaluation of Hypercube Multicomputers," IEEE Tran. on Reliability, Special Issue on Reliability of Parallel and Distributed Computing Networks, Apr. 1989, pp. 121-129.
6. 6 S. Abraham and K. Padmanabhan, "Reliability of the Hypercube," Proc. Int. Conf. on Parallel Processing, Vol. I, Aug 1988, pp 90--94.
7. 7 J. C. Laprie and A. Coste, "Dependability: A Unifying Concept for Reliable Computing," Proc. FTCS-12, June 1982, pp. 18-21.
8. 8 C. R. Das and J. Kim "An Analytical Model for Computing Hypercube Availability," Proe. FTCS- 19, Jun. 1989, pp. 530-537.
9. 9 3. Lee. }2. Shragowitz, and S. Sahni, "A ltypercube Algorithm for the 0/1 Knapsack Problem," Proc. 1987 Int. Conf. on Pa.rallel Processing, Aug. 1987, pp. 699-706.
10. 10 M. S. Chen and K. G. Shin, "Processor Allocation i~ an N-cube Multiprocessor using Gray Codes," IEEE Trans. on Computers, Vol C-36, Dee. 1987, pp. 1396-1407.
11. 11 3. Kim, C. R. Das, and W. Lin, " A Processor Allocation Scheme for Hypercube Computers," Proc. Int. Conf. on Parallel Processing, Vol. II, Aug. 1989, pp. 231-238.
12. 12 J. Hastad, T. Leighton, and M. Newman, "Reconfiguring a Hypercube in the Presence of Faults", Proc. 28th Annual Symp. on Foundations Comput, er Sci., Oct. 1987, pp. 274-284.
13. 13 R. Geist, K. S. Trivedi, et. al., "Design of the Hybrid Automated Reliability Predictor," Proc. IEEE/AIAA 5th Digital Avionics System Conference, Nov. 1983.
14. 14 A. Goyal, W. C. Carter, et. al., "The System Availability Estimator," Proc. FTCS-16, 1986, pp. 84- 89.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Model development and analysis

      • Modeling methodologies

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

• Theory of computation

  • Randomness, geometry and discrete structures