ABSTRACT
Traditional evaluation techniques for multiprocessor systems use Markov chains and Markov reward models to compute measures such as mean time to failure, reliability, performance, and performability. In this paper, we discuss the extension of Markov models to include parametric sensitivity analysis. Using such analysis, we can guide system optimization, identify parts of a system model sensitive to error, and find system reliability and performability bottlenecks.
As an example we consider three models of a 16 processor. 16 memory system. A network provides communication between the processors and the memories. Two crossbar-network models and the Omega network are considered. For these models, we examine the sensitivity of the mean time to failure, unreliability, and performability to changes in component failure rates. We use the sensitivities to identify bottlenecks in the three system models.
- 1.M. Avriel. Nonlinear Programming: Analysis and Methods. Prentice-Hall, Englewood Cliffs, N J, 1976.Google Scholar
- 2.M. D. Beaudry. Performance Related Reliability for Computer Systems. IEEE Transactions on Computers, C-27(6):540-547, June 1978.Google ScholarDigital Library
- 3.D. P. Bhandarkar. Analysis of Memory interference in Multiprocessors. IEEE Transactz'ons on Computers, C-24(9):897-908, September 1975.Google ScholarDigital Library
- 4.C. R. Das and L. N. Bhuyan. Reliability Simulation of Multiprocessor Systems. In Proceedings of the International Conference on Parallel Processing, pages 591-598, August 1985.Google Scholar
- 5.P. M. Frank. Introduction to System Sensitivity Theory. Academic Press, New York, 1978.Google Scholar
- 6.A. Goyal, S. Lavenberg, and K. Trivedi. Probabilistic Modeling of Computer System Availability. Annals of Operations Research, 8:285-306, March 1987.Google ScholarCross Ref
- 7.P. Heidelberger and A. Goyal. Sensitivity Analysis of Continuous Time Markov Chains Using Uniformization. In P. J. Courtois G. Iazeolla and O. J. Boxma, editors, Proceedings o} the 2nd International Workshop on Applied Mathematics and Performance/Reliability Models of Computer/Communication Systems, pages 93-104, Rome, Italy, May 1987.Google Scholar
- 8.R. A. Howard. Dynamic Probabilistic Systems, Volume II: Semi-Markov and Decision Processes. John Wiley and Sons, New York, 1971.Google Scholar
- 9.J. G. Kemeny and J. L. Snell. Finite Markov Chains. Van Nostrand-Reinhold, Princeton, NJ, 1960.Google Scholar
- 10.D. Kuck. The Structure of Computers and Computations. Volume 1, John Wiley and Sons, NY, 1978. Google ScholarDigital Library
- 11.D. H. Lawrie. Access and Alignment of Data in an Array Processor. IEEE Transactions on Computers, C-24:1145-1155, December 1975.Google ScholarDigital Library
- 12.R. A. Marie, A. L. Reibman, and K. S. Trivedi. Transient Solution of Acyclic Markov Chains. Performance Evaluation, 7(3):175-194, 1987. Google ScholarDigital Library
- 13.J. F. Meyer. On Evaluating the Performability of Degradable Computing Systems. IEEE Transactions on Computers, C-29(8):720-731, August 1980.Google ScholarDigital Library
- 14.J. H. Patel. Performance of Processor-Memory Interconnections for Multiprocessors. IEEE Transactions on Computers, C-30(10):771-780, October 1981.Google ScholarDigital Library
- 15.A. Reibman and K. Trivedi. Numerical Transient Analysis of Markov Models. Computers and Operations Research, 15 (1): 19-36, 1988. Google ScholarDigital Library
- 16.A. L. Reibman and K. S. Trivedi. Transient Analysis of Cumulative Measures of Markov Chain Behavior. 1987. Submitted for publication.Google Scholar
- 17.D. P. Siewiorek. Multiprocessors: Reliability Modeling and Graceful Degradation. In Infotech State of the Art Conference on System Reliability, pages 48-73, Infotech International, London, 1977.Google Scholar
- 18.D. P. $iewiorek, V. Kini, R. Joobbani, and H. Bellis. A Case Study of C.mmp, Cm*, and C.vmp: Part iI m Predicting and Calibrating Reliability of Multiprocessor. Proceedings of the IEEE, 66(10):1200-1220, October 1978.Google ScholarCross Ref
- 19.M. Smotherman. Parametric Error Analysis and Coverage Approximations in Reliability Modeling. PhD thesis, Department of Computer Science, University of North Carolina, Chapel Hill, NC, 1984. Google ScholarDigital Library
- 20.M. Smotherman, R. Geist, and K. Trivedi. Provably Conservative Approximations to Complex Reliability Models. IEEE Transactions on Computers, C-35(4):333-338, April 1986. Google ScholarDigital Library
- 21.W. Stewart and A. Goyal. Matrix Methods in Large Dependability Models. Research Report RC-11485, IBM, November 1985.Google Scholar
- 22.K. S. Trivedi. Probability and Statistics with Reliability, Queueing and Computer Science Applications. Prentice-Hall, Englewood Cliffs, NJ, 1982. Google ScholarDigital Library
- 23.R. S. Varga. Matrix Iterative Analysis. Prentice- Hall, Englewood Cliffs, NJ, 1962.Google Scholar
Index Terms
- Sensitivity analysis of reliability and performability measures for multiprocessor systems
Recommendations
Sensitivity analysis of reliability and performability measures for multiprocessor systems
Traditional evaluation techniques for multiprocessor systems use Markov chains and Markov reward models to compute measures such as mean time to failure, reliability, performance, and performability. In this paper, we discuss the extension of Markov ...
Performability analysis method from reliability and availability
ICHIT '09: Proceedings of the 2009 International Conference on Hybrid Information TechnologyAvailability and reliability are important attributes of dependability. Many dependability analysis methodologies measure and predict availability and reliability separately. However, those methodologies cannot reflect real system characteristics since ...
Comments